An Improved K-means Clustering Algorithm Based on Normal Matrix

It is well known that K-means algorithm is very sensitive to outliers, and often terminates at a local optimum. Therefore, the quality of the result is not satisfactory. Furthermore, it is usually designed as memory-resident algorithms, which limit the scalability. In this paper, we an improved K-means clustering algorithm - NK-means is developed. NK-means is based on spectral methods, namely uses Normal matrix that is used in spectral analysis approaches to normalize original datasets, and then finds clusters in the processed datasets by K-means algorithm. During the normalization, weighted adjacency matrix is constructed by the similarity between objects belonged in original datasets, and to generate Normal matrix. NK-means algorithm mainly uses the characteristic structure to process original datasets. In the processing, the data is transformed from a matrix into a vector, and the structures of the clusters are changed from three-dimensional sphere into two-dimensional circle. The experiment shows that NK-means algorithm significantly outperforms K-means in the efficiency and accuracy.