Refining Spherical K-Means for Clustering Documents

Spherical k-means is a popular algorithm for document clustering. However, it may still yield poor performance in some circumstances. In this paper, we consider a discrete optimization model for spherical k-means. By using the convexity of objective function and specific structure of constraint set, we first reformulate the discrete problem as an equivalent convex maximization problem with linear constraints. Then we characterize the local optimality of relaxed problem. Based on the characteristics, we refine the spherical k-means algorithm by alternatively performing spherical k-means and switching data points between clusters. This strategy guarantees that the refined algorithm can always attain a local optimal solution.