Three-way k-means: integrating k-means and three-way decision

The traditional k-means, which unambiguously assigns an object precisely to a single cluster with crisp boundary, does not adequately show the fact that a cluster may not have a well-defined cluster boundary. This paper presents a three-way k-means clustering algorithm based on three-way strategy. In the proposed method, an overlap clustering is used to obtain the supports (unions of the core regions and the fringe regions) of the clusters and perturbation analysis is applied to separate the core regions from the supports. The difference between the support and the core region is regarded as the fringe region of the specific cluster. Therefore, a three-way explanation of the cluster is naturally formed. Davies-Bouldin index (DB), Average Silhouette index (AS) and Accuracy (ACC) are computed by using core region to evaluate the structure of threeway k-means result. The experimental results on UCI data sets and USPS data sets show that such strategy is effective in improving the structure of clustering results.