 |
A Text Categorization Technique based on a Numerical Conversion of a Symbolic Expression and an Onion Layers AlgorithmDepartment of Archives and Libraries Science, University of Ionian, Palaia Anaktora, 49100, Corfu, Greece Email: {mpoulos, sozon, vchris}@ionio.gr Key features: References; Figures 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, A1, A2, A3, A4; Tables 1, 2, 3, 4, 5, 6
AbstractThe dramatic increase in the amount of content available in digital forms gives rise to large-scale digital libraries, targeted at millions of users. As a result, it has become a necessary to categorize large texts (documents). The paper develops a novel method where text categorization is achieved via a reduction in the original data information using numerical conversion of a symbolic expression and an onion layers algorithm. Three different semantic categories were considered and five texts selected from each category for submission to a text categorization procedure using the proposed method. The results and the statistical evaluation of this procedure showed that the proposed method may be characterized as highly accurate for text categorization purposes.Keywords: text categorization, onion algorithm, computational geometry 1 IntroductionText categorization is the process of grouping texts into one or more predefined categories based on their content. Automatic text categorization can play an important role in a wide variety of more flexible, dynamic and personalized information management tasks as well as: real-time sorting of email or files into folder hierarchies; topic identification to support topic-specific processing operations; structured search and/or browsing; or finding texts that match long-standing interests or more dynamic task-based interests (Anick and Vaithyanathan 1997). A number of statistical classification and machine learning techniques have been applied to text categorization, including regression models, Bayesian classifiers, decision trees, nearest neighbour classifiers, neural networks, and support vector machines (Weston et al. 1997).Classification technologies should be able to support category structures
that are very general, consistent across individuals, and relatively static
(e.g. Dewey Decimal or Library of Congress classification systems, Medical
Subject Headings (MeSH), or Yahoo!'s topic hierarchy), as well as those
that are more dynamic and customized to individual interests or tasks.
Until now the first step in text categorization has been to transform texts,
which are typically strings of characters, into a representation suitable
for the learning algorithm and the classification task. Each document is
represented as a vector of words, as is typically done in information retrieval
(Salton and McGill 1983).
For most text retrieval applications, entries are weighted to reflect the
frequency of terms in texts and the distribution of terms across the collection
as a whole. For text classification, simpler binary feature values (i.e.
a word either occurs or does not occur in a document) are often used instead.
For example, in the most commonly used text representation, the vector
space model, a vector of words represents each text. A word-by-text matrix
A
is used for a collection of texts, where each entry represents the occurrence
of a word in a text, i.e. Classification of the aforementioned vectors has been based on several learning techniques, including multivariate regression, nearest neighbour classifiers, probabilistic Bayesian models, decision trees, and neural networks. Overviews of this text classification work can be found in Lewis and Hayes (1994), Yang (1999), Joachims (1998) and Dumais et al. (1998). Furthermore, in the semantic text categorization reduction technique, latent semantic analysis (LSA) (Deerwester et al. 1990), there is an approach to automatic indexing and information retrieval that attempts to overcome common problems in information retrieval. The first problem is termed synonym and refers to the fact that there are many names for the same object. The second problem is called polysemy, and refers to the fact that most words have more than one meaning. Recently, machine learning algorithms have been applied successfully to automatic text categorization problems, with a large number of unique words (over 15000). However, it has not yet been clarified, particularly for large-scale problems with more than a million feature terms, to what degree the following two factors work to the detriment of each other: the reduction of the classification error using computationally-intensive machine learning algorithms, and the loss of information due to the selection of feature terms before applying the expensive learning algorithms. Specifically, in the learning procedure the algorithm of Slonim and Tishby (2001), which is based on the Bayesian classifier, is O(n3k) in complexity where n is the total number of words and k is the number of classes. Furthermore, the philosophy of the aforementioned methodology is justified because a Bayesian classifier presents a weakness in the point sets for large dimensions (Domingos and Pazzani 1997). It is known that high dimensionality, which presents a classified vector S of words, creates classification problems. These arise from the asymptotic error rate of the nearest neighbour rule (Toussaint et al. 1984). This problem is solved partially by the Voronoi diagram of S, which partitions the plane convex polygonal Voronoi cells. This paper attempts to improve the performance of the naive text categorization methods by using the concept of probability weighted amount of information, and also by incorporating morphological information and probabilistic language modelling techniques in extracting and computing the weights of feature terms. Thus, our analysis is based on the advantages of the Voronoi diagram and we reduce the complexity of this transformation by using the onion algorithm of Bremner et al. (2003). The idea behind this implementation is to use the convex hull subroutine recursively to extract the outmost convex hull (S1 smallest convex polygon) of the given points (characters). In particular, we have developed a method based on an onion polygon each point of which represents a character of the document. For the numerical conversion of each character we used a specific numerical representation of the conversion strings which equates to double precision of ASCII characters. In this novel way we avoid the problems of vector representation by converting the entire text into a unique set of numbers (more details of this method are given in section 2.1). This conversion took place in order for all the features of the characters of a document to be represented in the Cartesian plane, and used in the computational geometry. Furthermore, a characteristic of the onion layers method (Borgefors et al. 1992) is that all the features are sorted in an ideal way and all specific features of documents, such as spaces and punctuation marks, have a domain role in the final reduction. This method may be characterized as a continuation of our latest research, such as specific feature extraction for fingerprint verification via onion layers (Poulos et al. 2003), and the study of the encephalogram where the feature of a convex polygon gave positive results in diagnostic biometrical tests (Poulos et al. 1999). The aim of this paper is to describe the proposed algorithm in depth and with examples, and, furthermore, to compare it statistically with the similar LSA reduction method in order to extract significant conclusions regarding the statistical assurance of this method. 2 MethodIn brief, our proposed method is divided into the following stages:
2.1 Preprocessing stageIn this stage we suppose that a selected text is an input vector ,
where 
represent the characters of the selected text. Then, using a conversion
procedure where a symbolic expression (in our case an array of characters
of a text) is converted to ASCII characters in string arithmetic values,
we obtained a numerical value vector 
where these values ranged between 1-128.
In our case this conversion was achieved by using the double.m function of the Matlab language. This function converts strings to double precision and equates with converting an ASCII character to its numerical representation. For better comprehension we give the following example via Matlab: >> S = 'This is a message to test the double "command".' >> double(S) ans = Columns 1 through 12 84 104 105 115 32 105 115 32 97 32 109 101 Columns 13 through 24 115 97 103 101 32 116 111 32 116 101 115 116 Columns 25 through 36 32 116 104 101 32 100 111 117 98 108 101 32 Columns 37 through 46 34 99 111 109 109 97 110 100 34 46 2.2 Processing stageOur proposed method is based on the following proposition:The set of elements of vectorThus, the smallest convex layer 
of the original set of vector 
carries specific information. In particular, vector
may be characterized as a common geometrical area of all the elements of
vector .
In our case, this consideration is valuable because this subset may be
characterized as representing the significant semantics of the selected
text.
ImplementationWe consider the set of characters of a selected text to be vector .
The algorithm starts with a finite set of points 
in the plane. The following iterative process is considered. Let 
be the set 
minus all the points on the boundary of the hull of  .
Similarly, define  .
The process continues until the set is 
(see Figure 1). The hulls 
are called the layers of the set, and the process of peeling away the layers
is called onion peeling for obvious reasons (Figure 1). More details of
the algorithmic construction of the proposed convex polygon and onion algorithm
are presented in the Appendix.
Figure 1. Onion layers of a set of points 2.3 Categorization stageIn our case we considered that the smallest convex layer that has depth 3 (Figure 1) carries specific information (Poulos et al. 2003), because this position gives a geometrical interpretation of the semantics of the selected text. In other words, the smallest convex polygon (layer) depicts a particular geometrical area in which the values of these semantics range. This structure has also been used for example in statistics to define a generalization of the concept of the median into two-dimensional data (O'Rourke et al. 1982). This feature may be characterized as unique to each selected text because the two following conditions (Poulos et al. 1999) are ensured:
and the depth (i) of this layer, which is a subset of the original
text set S values. In more detail, the smallest onion layer
is a matrix that contains the set of convex coordinate values of the smallest
onion layer, in other words, 
where x represents the frequency of each converted character and y the numerical value of each character. Taking into account the specific features of the aforementioned variables it is easy to ascertain that these may be used in the next stage. 2.4 Decision stage of computational geometry methodIn this stage subset
intersects a new subset  ,
which came from the processing of another set  ,
on the Cartesian plane (Figure 2).
Figure 2. Decision stage between two different onion algorithm procedures The correlation of investigated subsets If the above subsets are intersected, the degree of correlation is extracted
by using the fraction of the common intersection and the area of the original
convex set. In more detail, if we consider that
In our case if
In this way degree 
Figure 4. Case of categorization in the same category. The green area is the common area of the compared text categorization documents 3 Experimental part3.1 Data acquisitionIn this study we tested the proposed method in three different semantic categories:
3.2 Implementation of the algorithmThe implementation of the algorithm takes place using the following steps.In the preprocessing stage we selected a text from each category and submitted it for numerical conversion using the following algorithm implemented via Matlab function double.m. For example, we took the following text from the third category (AIDS and Virus), which we called C1: West German chemical group Bayer AG <BAYG.F> said it had received claims for damages from haemophiliacs who allege they were infected with AIDS through a blood plasma produced by a Bayer subsidiary. Bayer's shares fell 13 marks to close at 292 in Frankfurt today. Dealers said a newspaper report about possible huge claims for damages triggered off the share selling in Bayer, other pharmaceuticals and insurance companies. Bayer said in a statement it was insured against claims and had received two.This text was submitted to numerical conversion, and a vector of a set number 
was constructed.
The same procedure was followed for other selected texts from the three categories. In the processing stage vector This procedure was repeated for the other vectors until we finally isolated
the 15 smallest convex polygons or vectors An example of this procedure is presented in Figures 5 and 6. 
Figure 5. Implementation of the onion polygon of text C1 using vector
Figure 6. Isolation of the smallest convex polygon of text C1 or vectors  ,  In the categorization stage vectors We considered that the intersected coordinate vectors were
For example, we used the following second text from the third category (Aids and Virus), which we called C2: Bristol-Myers Co <BMY> said it would seek Food and Drug Administration permission to test its AIDS vaccine in humans by the end of March. A company spokesman said the company will file an investigational new drug application by the end of the month, requesting the FDA to allow testing of the vaccine in humans. Scientists at the company's Genetic Systems unit created an AIDS vaccine, which Bristol-Myers said produced antibodies to the AIDS virus in mice and monkeys. The vaccine consists of smallpox virus.We also used the following text, which we called B1, from the second category, Computational Geometry: In this paper, fingerprint segmentation for secure Internet verification purposes is investigated. The novel application of computational geometry algorithms in the fingerprint segmentation stage showed that the extracted feature (characteristic polygon) may be used as a secure and accurate method for fingerprint-based verification over the Internet. On the other hand, the proposed method promisingly allows very small false acceptance and false rejection rates, as it is based on specific segmentation,Figures 7 and 8 show the implementation of the intersection of semantic texts from the same categories, C1 and C2, where we obtained a large convex polygon C12 (green) (  ).
In contrast, in Figures 9 and 10 show that the intersection of semantic
texts C1 and B1 are zero (B1∩C1=0).
Figure 7. Intersection of two semantic texts, C1 and C2, using the onion algorithm 
Figure 8. Isolation of the intersection (green) of the two smallest
convex polygons of semantic texts C1 (blue)
and C2 (red)
In the decision stage degree First, we calculated the area of each convex subset
In Matlab this procedure was calculated as follows:
and was repeated for all text cases. The 4 ResultsIn this part the results of the implementation of the proposed algorithm for text categorization purposes are presented in Table 1. More specifically, we extracted the
degrees of correlation using Equation 1. In total we obtained 15 x 15 = 225
degrees of correlation for the three semantic categories.
5 Statistical evaluationIn this section a statistical evaluation between the most used information retrieval method, latent semantic indexing (LSI), and the proposed method is attempted. In particular, we tested the five texts of the same semantic category C (AIDS-virus). To compare the two techniques we used rank correlation among several variables of the chi-square control. In the following paragraphs we develop the procedure followed in order to yield the normalized matrices for each method and, thereafter, apply them to the selected statistical method.5.1 Concordance: rank correlation among several variablesThe concept of correlation between two variables can be expanded to consider association among more than two, as shown for multiple correlations (Kendall 1962). Such association is readily measured non-parametrically by a statistic known as Coefficients of Concordance. In our case this correlation, W, gave the perfect criterion of agreement among five selected sets of data. In other words, this test investigates if the data of columns are in agreement. The correlation W was employed by the following equation:
where M is the number of variables being correlated and n is the number of data per variable, Ri is the sum of the values of each column for i=1 ... n. We can ask whether a calculated sample, W, is significant, that
is, whether it represents an association different from zero in the population
that was sampled. A simple way to find out the relationship between the
Kendall Coefficients of Concordance, W, and the Friedman chi-square
and then employ the critical values of .
5.2 Latent semantic indexingIn the first stage we created Table 2 to sort out all the conceptual contents of the documents. In particular, the local weight (Lij) of each term is represented by each row in Table 2, and every document is represented by each column. Thus, an individual entry in Table 2, aij, represents the weights of the terms i in document j, where, in our case, i=1...88 and j=1...5. More specifically, the term document matrix can be expressed as a vector consisting of the weights of each term and mapped in a vector space (Tokunaga 1999):
where: Lij is the local weighting. This approach defines the weights wij in each document. Let Pij denote the occurrence probability of ti (terms frequency) and dj (documents). We ascribe significance to a term's occurrence, on the grounds that it represents a document's topics more than other factors do. Therefore, we base wij on the term occurrence probability Pij in each document, and we define a local weighting Lij as follows:
The LSI method uses an algebraic model of document retrieval, using a matrix technique known as singular value decomposition. Thus, using the SVD function of Matlab, we obtained three separate matrices from the original table A, as represented in Table 2, of Lij elements. The first matrix is a term by concept matrix B. The second matrix is a concept by concept matrix (see Table 3). The third matrix is a concept by document matrix D. One important note is that multiplying B x C x D may not necessarily yield the original Table 2, since many of the concepts may be very small and not worth keeping. In our case, we used the normalized matrix B (Table 3) of dimensionality 5 x 5 in order to conceptually compare the LSI method with our proposed method.
In the next stage the data of Table 3 can be tested using the top-down
correlation technique (see Equation 2). The null hypothesis (H0)
of this test is that there is an agreement regarding the investigated data
of the columns of Table 3. In our case, according to Equation (2),
M=5
was the number of investigated documents, n=5 were the conceptual
values after reduction, and R was the sum of the rank score (see
Table 3). Then, W=0.0059 and thus 5.3 Onion layers methodIn this stage we obtained the five sets of data for each document (Table 4) using the method described in section 3.2. It should be noted that each set contains the points of the smallest convex polygon plus a number of points ranging between 0-2 (see Figure 1).
The next stage was to transform the data of Table 4 in order for each pair of data to be represented by a value. Thus, for the whole set we calculated the magnitude of each pair point (xij,yij) from the origin 0 of the coordinate system using the following formula:
where: i=1, 5 is the number of elements of each smallest convex layer and j=1, 5 is the number of documents. We then obtained the first five values (Table 5) for each document in order to compare these statistically with those of the of LSI method (Table 3) and normalized the data in Table 6.
In this stage the data of Table 6 can be tested using the top-down correlation
technique (Equation 2). The null hypothesis (H0) of this
test is that there is an agreement regarding the investigated data of the
columns of Table 6. In our case and according to Equation (2), M=5
was the number of investigated documents, n=5 were the conceptual
values after reduction, and R was the sum of the rank score (see
Table 6). Then W=0.0003 and thus 6 Analysis and discussionAs can be seen from the results in Table 1, the proposed method correctly categorized all tested texts.The statistical evaluation method based on rank correlation (section
5.1) of our proposed method and the LSI method (section
5.2) showed that they have the same level significance (0.99 < P
< 0.95), although our proposed method may be considered to be superior
to the LSI method because the reduction technique is independent of the
number of documents and the number of terms involved. In more detail, the
method promises a great reduction in the original information. For example,
a selected text of 500 characters is now represented by a convex polygon
(categorization stage) of two vectors Furthermore, for smaller texts (100 words in length) we avoid the training procedure and, in this way, the complexity of the proposed method is reduced dramatically in comparison with traditional methods. For training on longer texts this method may be applied as follows:
7 Conclusions and future work7.1 ConclusionThis paper has explained a text categorization technique that combines numeric conversion of a symbolic expression and a computational geometric algorithm. The proposed technique is suitable for the specific partitioning of digital library collections, and semantic categorization of emails and abstracts. This method may be characterized as a supervised method because it is based on the claim that an unknown text categorization vector (smallest convex polygon) is compared with a particular text categorization vector the class of which is already known. Thus, a practical way to see if this method is able to classify an unknown document vector correctly is to test it with a particular number of different predetermined semantic document vectors and let the system decide which of these vectors is geometrically nearest the unknown vector according to the method described in section 3.2.An example of this is the experiment in which five test categories (of 5 x 100 word documents per category) were used to test this technique. Statistical information was collected from the experiment and used to corroborate our findings:
7.2 Future workA way to improve our proposed method in future would be to develop numerical conversion of a symbolic expression based on a different encoding method. In this way, we propose to extend the encoding to a larger 8-bit conversion. The aim of this proposition is for each character of each word to be described in a more specific way. Phonetic conversion in place of ASCII conversion may provide an even more accurate solution in our proposed method.The next aim of this study is to increase the text length in each processed document to more than 100 words. Furthermore, this system has the ability to investigate the relation of the position of one convex polygon to that of another in the Cartesian plane. Thus, in this study we considered the degree a of the intersection of convex polygons as a measure of comparison. However, in future the centre of gravity of a convex polygon may be used as a measure of comparison and treated as a vector (O'Rourke 1995). In our latest work modified the proposed method to construct an anti-spam filter. Finally, this method may be considered to be a preliminary study and the next aim is to apply it to a real test collection. However, the statistical conclusion and the results of the 15 tested documents show that we are moving in the right direction. ReferencesAnick, P. and Vaithyanathan, S. (1997) "Exploiting Clustering and Phrases for Context-Based Information Retrieval". In Proceedings of SIGIR'97: the 20th International Conference on Research and Development in Information Retrieval (ACM Press), pp. 314-322Borgefors, G., Ragnemalm, I. and Sanniti di Baja, G. (1992) "Feature extraction on the Euclidean distance transform". In Progress in Image Analysis and Processing II, edited by V. Cantoni, M. Ferretti, S. Levialdi, R. Negrini and R. Stefanelli, (World Scientific: Singapore), pp. 115-122 Bose, P. and Toussaint, G. (1995) "No Quadrangulation is Extremely Odd". In 6th International Symposium on Algorithms and Computation (formerly SIGAL International Symposium on Algorithms), pp. 340-358 Bremner, D., et al. (2003) "Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries". In Proceedings of the 8th Workshop on Algorithms and Data Structures (WADS 2003), Ottawa, Ontario, Canada, July 30-August 1 http://citeseer.ist.psu.edu/593554.html Deerwester, S., Dumais, S. T., et al. (1990) "Indexing by latent semantic analysis". Journal of the American Society for Information Science, 41(6), 391-407 http://citeseer.ist.psu.edu/deerwester90indexing.html Domingos, P. and Pazzani, M. J. (1997) "On the optimality of the simple Bayesian classifier under zero-one loss". Machine Learning, 29(2-3), 103-130 http://citeseer.ist.psu.edu/domingos97optimality.html Dumais, S. T., Platt, J., Heckerman, D. and Sahami, M. (1998) "Inductive Learning Algorithms and Representations for Text Categorization". In Proceedings of the 7th International Conference on Information and Knowledge Management (ACM Press), pp. 148-155 Graham, R. L. (1972) "An efficient algorithm for determining the convex hull of a finite planar set". Information Processing Letters, 1, 132-133 Joachims, T. (1998) "Text categorization with support vector machines: Learning with many relevant features". European Conference on Machine Learning (ECML), pp. 123-132 http://citeseer.ist.psu.edu/joachims97text.html Jones, S. and Paynter, G. W. (2002) "Automatic Extraction of Document Keyphrases for Use in Digital Libraries: Evaluation and Applications". Journal of the American Society for Information Science and Technology, 53(8), 653-677 Kendall, M. G. (1962) Rank Correlation Methods, 3rd edition (Charles Griffin: London), p. 199 Lewis, D. D. and Hayes, P. J. (1994) ACM Transactions on Information Systems, special issue on text categorization, 12(3), July O'Rourke, J., Chien, J., Olson, C. and Naddor, T. (1982) "A new linear algorithm for intersecting convex polygons". Computer Graphics and Image Processing, 19 (4), 384-391 O'Rourke, J. (1995) Computational Geometry in C (Cambridge University Press: New York), p. 47 Poulos, M., Rangoussi, M., et al. (1999) "Parametric person identification from the EEG using computational geometry". Proceedings of the Sixth International Conference on Electronics, Circuits and Systems (ICECS'99), Pafos, Cyprus, September, pp. 1005-1012 Poulos, M., Magkos, E., Chrissikopoulos, V. and Alexandris, N. (2003) "Secure Fingerprint Verification Based on Image Segmentation using Computational Geometry Algorithms". In Proceedings of the IASTED International Conference Signal Processing Pattern Recognition & Application, pp. 308-312 http://www.ionio.gr/~mpoulos/papers/Fingerprint%20verification.pdf Salton, G. and McGill, M. (1983) Introduction to Modern Information Retrieval (McGraw-Hill) Slonim, N. and Tishby, N. (2001) "The power of word clusters for text classification". In 23rd European Colloquium on Information Retrieval Research (ECIR) http://www.cis.upenn.edu/group/datamining/ReadingGroup/papers/textclass-infobottleneck.pdf Tokunaga, T. (1999) Computation and Language Volume 5: Information Retrieval and Natural Language Processing (University of Tokyo Press) Toussaint, G., Bhattacharya, B. and Poulsen, R. (1984) "The application of Voronoi diagrams to nonparametric decision rules". In Proceedings of Computer Science and Statistics: 16th Symposium of the Interface Weston, J., et al. (1997) "Density Estimation Using Support Vector Machines". Technical Report CSD-TR-97-23, Royal Holloway College, University of London http://citeseer.ist.psu.edu/weston98density.html Yang, Y. (1999) "An evaluation of statistical approaches to text categorization". Journal of Information Retrieval, Vol 1, No. 1/2, 67-88 http://citeseer.ist.psu.edu/yang97evaluation.html LinksReuters-21578 collection http://www.daviddlewis.com/resources/testcollections/reuters21578/AppendixThis Appendix describes the algorithms used in the text categorization method. Section A1 describes the algorithm for constructing a two-dimensional convex polygon, and section A2 outlines an onion algorithm. In our case we considered that the point P=Pxy is a converted character, where Py on the y-axis represents the corresponding value of a text character and Pxon the x-axis represents the frequency of this character.A1 Construction of a two-dimensional convex polygonGraham (1972) proposed an algorithm of complexity O(n logn) which computed the convex hull of a given set of n points on the 2D plane. This algorithm proceeds in three phases.Phase 1. The highest y-coordinate, which is clearly
on the hull, is used as the pivot (Figure A1).
Figure A1. The original points Phase 2. The points are sorted in order of increasing
angle about the pivot. A horizontal ray P0, emanating
from the pivot, is rotated counter-clockwise. The first point that the
ray contacts is sorted as the first point (P1). In the
same way, the remaining points are sorted, until the ray returns to its
original horizontal position (Figure A2).
Figure A2. Sorting procedure Phase 3. The horizontal ray, emanating from the pivot (P0),
begins to rotate counter-clockwise and stops at the first point sorted
in phase 2. Then these points, the first and the second (P0,
P1),
form the new axis of rotation. Using point P1
as the
pivot, the third point of the convex polygon is determined as the first
point of contact on rotation of the new axis (Figure A3).
Figure A3. Final phase of the construction of the convex polygon This procedure is repeated until a phase where the first point of contact of the rotating ray is again P0. Then the hull is closed. Algebraic explanation of the area of a convex polygonSuppose the x and y coordinates of a point piare denoted by (xi, yi) and there are n total points in the plane. If we considered that the algebraic area (or the signed area) of the oriented triangle p1, p2, p3 is ,
then  determinant  .
The sign of the algebraic area is positive if and only if the orientation
of the triangle is counter-clockwise. Consider any n-vertex simple
polygon P whose vertices around its boundary in some orientation
(clockwise or counter-clockwise) are A.2 Onion layers of a set of pointsLet P be a set of n points in R2, and let (H0, H1, ... ,Hk) be the onion of P, that is, H0 is the convex hull of P. Now remove the points on the boundary of H0from P and let H1 be the convex hull of what remains in P, and so on until no more points are left in P (see the example in Figure A4).
Figure A4. Onion layers of a set of points Thus, the construction of the onion is produced by iterative application of the gift-wrapping algorithm and shows that it takes a total time of O(d*n log n). |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
,
where 
is the weight of word i in text j. Determining the
weight and the frequency of words in a text is common to all existing methods.
and
the corresponding areas of these convex polygons are 
, 
and 
,
then the degree 
(1)
,
then the system decides that the two compared subsets 
where n=1 ... 15
and 
from the second text. Then the convex polygon, which was produced by chance
intersection, had 
and 
coordinate vectors. This algorithm was implemented via the following Matlab
function:
was calculated as follows.
and 
followed by the area of their common intersection 
.
Then degree 
and 
and 
(2)
(3)
(4)
(5)
(see Equation 3). Comparing it to the chi-square distribution with a
degrees of freedom í=5-1= 4 and 
,
we
had non-rejection of the null hypothesis (H0) of the
agreement regarding the conceptuality of the compared documents (0.99 <
P
< 0.95).
(6)
(see Equation 3). On comparing it to the chi-square distribution with degree
of freedom í=5-1=4 and 
or 96.4%
. Let
O denote the origin in the plane of P. Then the algebraic area of
the convex polygon P is 
,
where where we assume 
.
Here again, the sign is positive if and only if the given orientation is
counter-clockwise around the boundary of P. Thus, any simple polygon
P
with more than three vertices (i.e. n > 3) has at least one diagonal.
A diagonal is a line segment that connects two non-adjacent vertices of
P
and has no intersection with the exterior of P.