Corpus Characteristics-Based Method to Centroids Number Determination for Clustering Text Documents

INTRODUCTION

Generating large volumes of textual information by large companies or organizations requires the ability to organize this information for decision-making, research, or knowledge extraction; otherwise, storing this information does not make sense. Finding the necessary information from a large amount of data is a complex but necessary task for the daily activities of most institutions, companies and government entities. One of the widely used techniques to alleviate this problem is text document clustering. Text document clustering allows us to separate similar text documents into different clusters.

We can find several research efforts on text document clustering in the literature. Recently, extensive studies have been carried out on this topic where different methods have been reported in the literature.^[1–14] In these studies, K-Means is one of the most commonly used algorithms for document clustering due to its ease of implementation, direct parallelization and relatively low computational cost.^[15] However, K-Means presents some difficulties, such as the handling of the high dimensionality of vectors used for representing documents, which considerably increases the algorithm’s execution times; this has encouraged the development of new alternatives and variants of the algorithm. One of the recently developed algorithms makes use of the advantages of inverted lists for document retrieval, avoiding the comparison word by word of each document through a similarity function; this solution is presented in the FPAC algorithm,^[16] improving the execution time considerably, without decreasing the quality of the clusters. To improve the cluster quality, Improved-FPAC^[17] proposes defining multiple centroids for each cluster, which allows to increase the representativeness, without sacrificing too much the execution time.

In Bejos S, et al,^[17] the authors experimented using different values for the number of centroids (parameter l) ranging from 5 to 30. They suggested using a fixed value l=10 for every corpus due to observing a decline in clustering quality beyond this threshold value in several corpora. However, we hypothesize that the value of this parameter should be defined according to the characteristics of the corpus to be clustered. For this reason, this paper proposes a corpus characteristics-based method for determining the number of centroids per cluster for Improved-FPAC. Our experimental analysis revealed a discernible correlation between the characteristics of a corpus (number of documents, number of words, number of classes or clusters) and the l value that produced the best clustering quality for this corpus. According to our experiments on public standard corpora, the method proposed in this paper allows Improved-FPAC to enhance its clustering quality results. The contribution of this paper is a method for determining the number of centroids per cluster (a parameter of the Improved-FPAC algorithm denoted as l) based on some of the characteristics of the corpus to cluster, such as the number of documents, number of words and number of classes or clusters. The proposed method facilitates the determination of a good value for l instead of adopting a uniform fixed value for all corpora, as suggested in Improved-FPAC. The proposed method avoids executing the Improved-FPAC algorithm several times to find a good value for the parameter l (the number of centroids) that provides good clustering results.

The rest of the paper is organized as follows. In the Second Section, we present the related work. In Section 3, our proposed method is introduced. The experimental study appears in Section 4. Finally, Section 5 discusses our conclusions and future work.

Related Work

Currently, document clustering is widely studied and we can find several algorithms reported in the literature.^[16–23] Among these algorithms, one that has reported good results is Improved-FPAC.^[17] As commented in the Introduction Section, this algorithm is based on k-means and follows an information retrieval approach to build the clusters. Since in this paper we introduce a method for determining the number of centroids per cluster to be used in Improved-FPAC, in the rest of the section, we will review the main ideas of this algorithm.

Improved-FPAC consists of 6 steps:

• Selection of the initial centroids (one per cluster).
• Construction of the initial clusters as in FPAC.
• Selection of multiple centroids per cluster.
• Non-Centroids Assignment with multiple centroids per cluster.
• Evaluation of the stop condition.

Selection of initial centroids

The process of selecting the initial centroids (k centroids) in the clustering algorithm involves the following steps: Initially, one centroid (c₁) is randomly chosen from all the documents in the corpus being analyzed. To ensure diversity among the centroids, the next centroid (c₂) is selected randomly from the documents that have not been included in the previously retrieved list of c₁. This process is repeated for each subsequent centroid, where each new centroid (c₃ and beyond) is selected randomly from the remaining documents that have not been part of the retrieved lists of the previously selected centroids (c₁, c₂, ...). The process continues until k initial cluster centroids have been chosen. This approach helps to achieve a diverse and representative set of initial centroids for the subsequent clustering process.

Construction of the initial clusters as in FPAC

To build the initial clusters, a non-centroid document d is assigned to a cluster by utilizing the initial centroids c₁, ..., c_k as queries to retrieve k ranked lists (r) of documents r₁, ..., r_k. Subsequently, if the document d is recovered solely in one ranked list, r_j, it is included in the cluster corresponding to centroid c_j. However, if the document d is retrieved in multiple ranked lists, it is assigned to the cluster where the normalized similarity score is maximized. If no centroid retrieves the document d, it is randomly assigned to any of the k clusters. This procedure facilitates the initial assignment of documents to clusters based on their similarity to the centroids, thus initializing the clustering process.

Selection of multiple centroids

After building the initial k clusters using Improved-FPAC, the algorithm proceeds to compute l centroids per cluster, where l is calculated whit Equation 2. To achieve this, each cluster C_i is divided into l disjoint subsets and these subsets are stored in l lists. Improved-FPAC iterates through the documents assigned to each cluster and distributes them into the disjoint subsets one by one until all documents within the cluster are distributed in the lists.

This partitioning allows each cluster to be covered by multiple subsets and within each subset; a centroid is computed as the average vector of the document vectors it contains. As a result, each cluster C_i obtains l centroids, providing a more granular representation of the cluster’s characteristics.

In summary, Improved-FPAC dynamically determines l centroids for each cluster C_i by dividing the cluster’s documents into l disjoint subsets and calculating centroids based on the average vectors of each subset. This approach contributes to the algorithm’s ability to achieve more refined clustering results.

Non-Centroids Assignment with multiple centroids

For assigning a non-centroid document d to a cluster, Improved-FPAC uses each of the l centroids as a query to retrieve a ranked list r for the cluster C_i. The normalized retrieval score is then computed for each centroid in each cluster C_i. Document d is assigned to the cluster C_i where the sum of the normalized retrieval scores is maximum. In the same way as in the construction of the initial clusters, the documents not retrieved by any centroid are randomly assigned to any of the k clusters.

Evaluation of the stop condition

The selection of multiple centroids and Non-Centroids Assignment with multiple centroids is repeated until the number of documents that change cluster between one iteration and another is not greater than a percentage defined as the stop condition; in Bejos S, et al.^[17] 10% was used. Below, Figure 1 illustrates the diagram of Improved-FPAC.

Click to enlarge

Although in Bejos S, et al,^[17] the authors report that Improved-FPAC with ten centroids for each cluster obtains good results in their experiments. However, determining the value of this parameter is generally not easy; it forces the user to rely on trial and error, which is impractical. For this reason, in the following section, a method to determine the number of centroids for Improved-FPAC from the characteristics of the corpus to be clustered is introduced.

Our method

This section introduces a method, based on the corpus characteristics, to calculate the number of centroids per cluster for the Improved-FPAC algorithm (parameter l). This was accomplished by analyzing the results of the Improved-FPAC algorithm using different values of l across various corpora utilized in the experiments conducted by Bejos S, et al.^[17] The algorithm was executed starting with a value of l=10 (as recommended in Bejos S, et al),^[17] Then incrementally increased by 10 in each execution until reaching l=200. Higher values were avoided as they did not significantly improve clustering quality. This behavior was consistent across all the used corpora. The F-Score metric was used to evaluate clustering quality for each value of l across the various corpora.

Table 1 shows the characteristics of each corpus used, i.e., number of documents (Docs), number of words (Words) and number of classes (Class). Additionally, the last column presents the number of centroids per cluster (l) that yielded the best F-Score results for the corpus among 20 executions conducted with values ranging from 10 to 200. We chose the F-Score measure because it is commonly used for evaluating information retrieval and document classification algorithms, which are the basis of Improved-FPAC.

From the experiments performed with the Improved-FPAC algorithm, we observed that the more documents with different vocabulary in a cluster, the more centroids are required to represent the cluster. Note that the larger a cluster is, the more documents it will contain (and the number of terms will likely increase), thus more centroids will be required to represent the cluster.

On the other hand, the greater the number of clusters in which the documents are clustered, in general, the number of documents in each cluster decreases;^[24] therefore, a smaller number of centroids will be required to represent the documents within a cluster.

From the above, we can infer that the number of documents and the vocabulary size (Words) are directly related to the number of centroids needed to represent the clusters. In contrast, the number of clusters (k) is inversely related to the number of centroids required to represent a cluster. Given that a larger k results in more clusters, each with fewer documents, fewer centroids will be needed to represent each cluster. Conversely, if k is small, there will be fewer clusters, but each will contain more documents, requiring more centroids to represent each cluster. Hence, according to the above discussion, we propose the following expression to relate these corpus characteristics:

By plotting the value of Expression 1 against the value of l that produced the best results from the twenty executions when ranging l from 10 to 200 for each corpus (y-axis), we obtain a set of points on the plane (one for each corpus); using these points, we can find a trend line to calculate the l value for the improved-FPAC algorithm for an unknown corpus from its characteristics. See Figure 2, where x is the normalized value of Expression 1 and y is the number of centroids per cluster (l) that produced the best results for the corpus, among all the executions performed by varying the value of l between 10 and 200. The graph in Figure 2 represents the trend line for all corpora (each corpus corresponds to a point on the graph). Then, a logarithmic trend line was adjusted using regression employing the residual sum of squares.^[25]

Click to enlarge

The following expression represents the trend line computed in Microsoft Excel:

This trend line will allow us to calculate the number of centroids per cluster to be used in the Improved-FPAC algorithm from the characteristics of the corpora.

As can be seen, in practice, applying our method requires evaluating the expression 7, 2 where x is as specified in expression 1. In Figure 3, we show the workflow when applying improved-FPAC using the proposed method to compute the number of centroids per cluster (parameter l).

Click to enlarge

It is necessary to mention that the value obtained from expression 2 must be truncated to an integer to define the value of l for each corpus. Additionally, if the value of l is less than 10, l is set to 10; if greater than 200, l is set to 200. In the next section, we show that applying our proposed method to determine a value for parameter l, which considers the corpus’s characteristics, produces good clustering results, as evidenced in Tables 4 and 5.

EXPERIMENTS AND RESULTS

This section will show the experiments to assess the proposed method to calculate the number of centroids per cluster for the Improved-FPAC algorithm.

For the experiments, 20 corpora were used. The characteristics of each corpus are shown in Table 3. The 10 Dataset Classification, German, IMDB Movie Reviews, Medical Dataset, Ohsumed, two corpora built from Reuters-21578 and Text Classification on Email corpora were downloaded from the Kaggle website.¹ In addition, six corpora were generated from the ones used for developing our proposal and six were generated from the News Category corpus, also downloaded from the Kaggle website. Table 2 shows the details for building these corpora. The quality of the clusters was evaluated using Rand Index (RI), Recall, Precision, F-Score, Purity and Normalized Mutual Information (NMI), in the same way as in Bejos S, et al.^[17] Below, we briefly explain the confusion matrix, which is fundamental for understanding RI, Recall and Precision. Subsequently, we provide detailed explanations of each of these measures.

The confusion matrix provides a tabular representation of clustering outcomes regarding an already known clustering (ground truth) in terms of True Positives (TP), False Positives (FP), True Negatives (TN) and False Negatives (FN).

True Positives (TP)

This is the number of pairs of documents that the clustering algorithm puts together in the same cluster and they are together in a cluster in the already known clustering.

False Positives (FP)

This is the number of pairs of documents that the clustering algorithms puts together in the same cluster and they are in different clusters in the already known clustering.

True Negatives (TN)

This is the number of pairs of documents that the clustering algorithm puts in different clusters and they are in distinct clusters in the already known clustering.

False Negatives (FN)

This is the number of pairs of documents that the clustering algorithm puts in different clusters and they are in the same cluster in the already known clustering.

Next, we explain each measure used to evaluate the experiments:

RI

Rand Index measures the similarity between two clusterings by considering all pairs of documents and calculating the number that are either in the same or in different clusters in both clusterings. It provides a score between 0 and 1, where higher values indicate better agreement between the clusterings, considering the confusion matrix is defined as follows:

Recall

Recall measures how well a clustering algorithm identifies objects that should be together in a cluster. It is the ratio of true positives to the sum of true positives and false negatives. It is defined as follows:

Precision

Precision measures how accurate a clustering algorithm is when it puts instances together in a cluster. It is the ratio of true positives to the sum of true and false positives. It is defined as follows:

F-Score (F1-Score)

It is defined as the harmonic mean of the clustering algorithm’s precision and recall and is defined as follows:

Purity

Purity assesses how well the clusters built by a clustering algorithm correspond to known cluster in the ground truth. It calculates the proportion of documents in a cluster that belong to the most common class in that cluster. It Is defined as follows:

Where:

- N is the total number of documents in the dataset.

-C_i is the predicted cluster to which the i-th document belongs.

-T_j is the true or actual cluster to which the j-th document belongs in the ground truth.

-Intersection (C_i, T_j) represents the size of the intersection between C_i and T_j.

NMI

NMI quantifies the amount of shared information between two clusterings, considering both agreement and randomness. NMI provides a normalized score ranging from 0 to 1, where higher values indicate better agreement between the clusterings and it is defined as follows:

Where:

- MI stands for Mutual Information between the predicted clusters C and the true clusters T .

- H (C) represents the Entropy of the predicted clusters C.

- H (T ) represents the Entropy of the true clusters T .

Concerning the parameter k and the termination criterion within Improved-FPAC, we established that the count of clusters to be constructed (parameter k) matches the count of classes present in each corpus. The maximum number of iterations was set to 10 because, in our experiments, the Improved-FPAC algorithm usually stops before reaching this number of iterations;^[17] we can also observe this fact in the last column of Tables 4, 5 and 6, which shows the maximum number of iterations (Max Iter) performed for each corpus and each method. In our experiments, the maximum value of 10 was reached only in two of the corpora (r26 and r30). The stopping criterion (convergence) was defined as having less than 10% of documents reassigned to different clusters between two iterations.

As information retrieval system for Improved-FPAC, we used the Apache Lucene implementation version 7.3.² A Red Hat Enterprise Linux Server Release 7.5 (Maipo) with 160 processors and 128 GB of memory was used for running all our experiments. Our method was applied to each corpus to determine the value of the parameter l. Once the value of l was determined, the Improved-FPAC algorithm was executed with this value and the quality of the resulting clustering was evaluated. Due to the randomness of Improved-FPAC in steps 1 and 4, the algorithm was executed ten times in each corpus and the average quality of the 10 executions is reported. On the other hand, the Improved-FPAC algorithm was applied ten times in each corpus using l=10 as the number of centroids as suggested in.^[17] Additionally, in the same way as in,^[17] we included the results obtained by Scalable K-means in our experiments. Finally, to appreciate the effectiveness of our proposal, we also performed a kind of semi-exhaustive trial and error evaluation of the Improved FPAC algorithm, which was executed (also ten times) by varying the value of l from 10 to 200 with increments of 10 and the best result is reported.

The results of the experiments are shown in detail in Tables 4-6. These tables are divided into separate blocks; each block corresponds to a corpus and has five rows; in the first row, the name of the corpus is found and in the remaining four rows, the quality of the clustering results obtained by Improved-FPAC are shown as follows: the second row shows, the results obtained by applying our method to determine the value of the parameter l; the third row shows the results obtained by using l=10; the fourth row shows the best result by varying the value of l from 10 to 200; and the fifth row shows the quality results obtained for Scalable K-Means. The first column displays the name of the clustering method used and the second column shows the number of centroids per cluster for the respective method. Columns three through fourteen present the average and standard deviation results for RI, Recall, Precision, F-Score, Purity and NMI. The last column of these tables shows the maximum number of iterations in all repetitions. In the results, the best outcome achieved for each method in each of the corpora is highlighted in bold-text as it can be seen in Tables 4-6, the standard deviation is very small in all cases. In Figure 4, we can see the summarized results for the three compared methods using the F-Score metric. The x-axis displays the corpora used in the experiments, while the y-axis shows the F-Score value obtained for each method and corpus.

Click to enlarge

In Figure 4, we can see the summarized results for the three compared methods using the F-Score metric; the x-axis displays the corpora used in the experiments, while the y-axis shows the F-Score value obtained for each method and corpus. From this figure, we can also see that using our proposal for calculating the number of centroids per cluster allows obtaining the best results in most cases. According to our experiments, in 16 of 20 corpora, the quality of the clustering obtained by the Improved-FPAC algorithm with the value of l calculated using our method yields better results than the value of l recommended in Bejos S, et al.^[17] These results are obtained regardless of the evaluation measure used; see the second and third rows in each block in Tables 4, 5 and 6. To validate these results, we applied the statistical Wilcoxon signed-rank test with p<0.01, which showed that our proposed method is statistically better (see entries marked with an asterisk in Tables 4-6) than the method proposed by Bejos S, et al,^[17] on these 16 datasets. Although the quality of the clustering obtained by the Improved-FPAC algorithm using the value of l calculated by our method did not coincide in all cases with the best clustering computed by Improved-FPAC varying l between 10 and 200, it was close to the best option. Our experiments show that Scalable K-means obtained the worst quality results in all the corpora.

CONCLUSION AND FUTURE WORK

This work introduces a method to compute the number of centroids per cluster (parameter l) for the Improved-FPAC algorithm. The proposed method considers the characteristics of the corpus (number of documents, vocabulary and number of classes) to determine the value for parameter l. To calculate the value of l, some corpora widely used in the literature were used to create an equation from a trend line obtained from the relationship between the best quality value obtained by varying the number of centroids from 10 to 200 and the characteristics of each corpus.

In our experiments, we confirmed a relationship between the characteristics of the corpus and the value of the parameter l that should be used in the Improved-FPAC algorithm to obtain better-quality results. In most of the evaluated corpora, the quality obtained with our method exceeds that obtained by using the fixed value suggested.^[17] Additionally, our proposal allows obtaining quality values close to the best quality found by varying l. However, using our method, it is not necessary to run the algorithm several times changing the number of centroids to find the option with the best quality result, which is not an option in practice.

In future work, we will modify Improved-FPAC to allow dynamic values of l. Starting from the value defined by our current proposal and dynamically increasing or decreasing it according to the number of documents and vocabulary size of each cluster and the quality results obtained in each iteration of the algorithm.

FPAC uses each cluster center as a query to retrieve a list of documents, assigned to that cluster without requiring distance calculation. However, as the number of centroids increases, in Improved-FPAC, the possibility of overlap and the number of distance calculations also increases. To avoid this, it is necessary to improve the query used in the cluster computation to remove those terms already included in a centroid, reducing overlap and potentially improving the algorithm’s performance.