Research On Spectral Clustering With Identifying Clustering Number Based On Eigengap

Spectral clustering is an important branch of clustering. Spectral clustering algorithm does not care about the shape of the data set, and is easy to implement, so it’s very suitable for handling large datasets and being applied to distributed systems. Furthermore, spectral clustering can achieve a global optimal solution to improve the clustering effect. However, one of the difficulties in spectral clustering is to detect the number of clusters. The number is usually required to be sepcified in advance in most clustering algorithms, and an improper value of cluster number can lead to an poor clustering performance. Another research hotspot in spectral clustering area is decentralized spectral clustering. Notice that the centralized spectral clustering algorithms can not be directly applied to distributed applications. Thus, improvements have been made on the following points:First, we propose an approach to identifying the clustering number based on eigengap(ICNE). By constructing the adjacency matrix based on the graph Laplacians matrix, the ICNE algorithm computes eigenvalues and the corresponding eigenvectors of normalized graph Laplacians sequentially. Furthermore, the number of cluster k can be identified by detecting the gaps between the adjacent eigenvalues. Finally, the data can be clustered by applying the first k eigenvectors to the k-means algorithm.Secondly, a decentralized spectral clustering method(DSC-ICNE) method is proposed to implement the ICNE method in a decentralized way, which can identify the number of clusters and perform the cluster analysis in a distributed way to improve the scalability.Finally, an algorithm named Spectral Clustering with Identifying Clustering Number based on Eigengap(SC-ICNE) is proposed to detect the number of clusters using the ICNE method and cluster the dadaset with the first k eigenvectors. The simulation of SC-ICNE is also made on the UCI database, and the simulation result shows that the SC-ICNE algorithm can perform the cluster anlysis quickly and efficiently, and achieve better clustering results for non-spherical data sets compared to the k-means method.