A Graph Partition-Based Soft Clustering Algorithm

Cluster analysis is one of the basic tools for discovering structure in data sets. Soft clustering enables the user to have a good overall view of the information contained in the data set that he has. However, existing soft algorithms suffer from various aspects. We propose GPSC (graph partition-based soft clustering), an efficient soft clustering algorithm based on a given graph model. This algorithm projected data set to a graph firstly, applied graph partition method to get an initial clustering result. Secondly, the core vertices and verge vertices have been defined to measure the membership for each vertex to clusters and relationships of neighbor clusters. Then the membership matrix and relationship matrix have been induced. From these two matrixes, we can find more fuzzy relations and latent clusters. Our experiments show that GPSC algorithm is able to discover clusters that cannot be detected by non-fuzzy algorithms, while maintaining a high degree of efficiency. Comparison with existing hard clustering algorithms like K-means and its variants shows that GPSC is both effective and efficient.