Adapt Clustering Methods for Arabic Documents

Veiw figure View Figure

View next figure

Different cluster methods like, ‘groups linkage’, ‘centroid’ and ‘ward's’ method respectively have been used and tested, in addition to available alternatives like ‘euclidean distance’ and ‘cosine’, after many iterative operations, ‘Ward's’ method and Euclidean distance measure have been selected, for the reason that they provide best clustering results against others methods. Figure 2 shows the proximity matrix of Document/Document (distance matrix D)after applying ‘Ward's’ method and ‘Euclidean distance’ measure. The next illustrate the implemented formulas used to obtained Distance matrix D. all formulas were obtained from ^{[15, 16]}.

‘Centroid method’

‘Ward’s method’

The total deviance (T) of the p variables, corresponding to n times the trace of the variance–covariance matrix, can be divided in two parts: the deviance.

Within the groups (W) and the deviance between the groups (B), so T = W + B.

The total deviance (T) can be denoted by:

Groups (W) are given by the sum of the deviances of each group and can be denoted by:

W_k represents the deviance of the p variables in the k_ith group and can be denoted by:

The deviance between the groups, (B) is given by the calculated sum on all the variables and can be denoted by:

‘Cosine measure’

‘Euclidean distances’

The introduced methods above amid to put the similar documents in different groups by calculating the similarities between the documents. Let us consider the following input matrix obtained from matrix, assumed all the way that the input data are in the form of a matrix, illustrated in Figure 1, the obtained Proximity matrix from matrix shown in Figure 1 is described in Figure 2.

Figure 2. fragment of obtained Proximity matrix

Download as

Veiw figure View Figure

View previous figure

View next figure

To extend the procedure of clustering described in ^[15], we perform the following:

Consider every row vector as a point and rearrange the row vectors according to their similarity, in Figure 2 the row vectors ordersare d1d2d3d4d5d6d7d8d9d10d11d12 d13d14d15d16d17, next if we rearrange the row vectors orders to d4d17d7d11d6d15d13d14d1d12d8d16d9d10d3d5.

Table 1 illustrates the steps of creating clusters from Figure 2.

Table 1. The steps of creating clusters

Download as

Veiw figure View Table

View next table

3.3. Experiment # 2

The proposed idea illustrates that, to cluster the collected text into groups of similar documents based on the idea of analyzing and extracting the first word only from each document then group all documents which have the same first word together.

The next procedure illustrates the proposed approach:

1-Read First Document Di from Corpus

2-Extract only first keyword (fk) (eliminate any stop words or signs)

3-Find the frequency (fr) of extracted first keyword over the document Di

4-Add Address of the document, first keyword (fk) and frequency (fr)

5-Repeat all steps for all documents in the corpus

Table 2 shows a sample of the output after performing the above procedure:

Table 2. Extracted sample from the corpus

Download as

Veiw figure View Table

View previous table

View next table

Reorganize the table horizontally until formulating groups of similar documents based on matching first keywords. (Table 3 shows this operation after reorganization the rows in the above table).

Table 3. Reorganized rows

Download as

Veiw figure View Table

View previous table

View next table

4. Evaluation and Results

Evaluating the results of the obtained grouping means verifying that the groups are consistent with the primary objective of the cluster analysis, to satisfy the conditions of internal cohesion and external separation. Choosing the right number of groups is fundamentally important. Here we evaluate the results obtained from experiment one and experiment two, considering the factor of how many new words appear each time versus new extracted words from new documents. It was hard to compare all the obtained clusters from experiment one and Two, furthermore we select only the largest clusters considering size factor(number of documents).

Figure 3 shows the results derived from largest clusters obtained from experiment.

One using basic clustering methods.

Figure 3. Number of new words against number of documents

Download as

Veiw figure View Figure

View previous figure

View next figure

Figure 3 illustrate that out of 200 to 170 new words continue to appear in this cluster. This means that there are some files which is not related to the cluster, and this in general will affect the final results of any research experiment oriented to a specific domain.

Figure 4 shows the obtained results from experiments two.

Figure 4. Using first word clustering

Download as

Veiw figure View Figure

View previous figure

Figure 4 illustrate that out of 100 to 75 new words continue to appear in this cluster. This means that there are some files which are not related to the cluster, but the later is better than the former. Our consideration is, as the numbers of extracting new words each time reduces as we keep on testing other documents. This factor can be considered as a fact that the cluster contains similar and related documents, which are used to describe a specific domain. Regarding the obtained results from both experiments, the proposed approach was able to remove/filter about 100 dissimilar documents from the text collection.

Table 4 shows the finding and comparison between the basic clustering methods and the new developed method.

Table 4. Finding and results

Download as

Veiw figure View Table