Marrying k-means with evidence accumulation in clustering analysis

Text clustering is becoming increasingly important to text mining and to the development of commercial applications. Previous research mainly focused on single clustering on documents. Compared with cluster ensembles, segmentations obtained from single clustering runs are less convincing in terms of accuracy and consistency. In this paper, we propose an approach based on evidence accumulation clustering (EAC) with k-means for text clustering problems. Our goal is to obtain a consistent, stable, and credible clustering scheme. First, we ran the k-means algorithm multiple times while the number of clusters ranges in an optimum area. Then, we constructed a matrix called co-association matrix by integrating all the derived clustering partitions. Finally, we obtained consistent clusters by performing hierarchical cluster algorithm on the co-association matrix. The linkage criterion used was a single link. The above process is equivalent to the process of finding a minimum spanning tree (MST) for a completed graph determined by a co-association matrix. The algorithm was tested on four text data sets. Experimental results showed that our method improves the accuracy of the final results.