An efficient k-means algorithm integrated with Jaccard distance measure for document clustering

Document Clustering is a widely studied problem in Text Categorization. It is the process of partitioning or grouping a given set of documents into disjoint clusters where documents in the same cluster are similar. K-means, one of the simplest unsupervised learning algorithms, solves the well known clustering problem following a simple and easy way to classify a given data set through a certain number of clusters (assume k clusters) fixed a priori. The main idea is to define k centroids, one for each cluster. This clustering algorithm uses an iterative procedure which converges to one of numerous local minima. We have found that these iterative techniques are especially sensitive to initial starting conditions of the centroid of each cluster and the more the distance among the cluster centroid the better the clustering performance. In simple K-means algorithm the way to initialize the centroid is not specified and one popular way to start is to randomly choose k points of the samples as k centroids but this process does not guarantee to choose the maximum dissimilar documents as the centroid point for k-cluster. In this paper we proposed a modified k-means algorithm which uses Jaccard distance measure for computing the most dissimilar k documents as centroids for k clusters. Our experimental results demonstrate that our proposed K-means algorithm with Jaccard distance measure for computing the centroid improves the clustering performance of the simple K-means algorithm.