Constructing affinity matrix in spectral clustering based on neighbor propagation

Ng-Jordan-Weiss (NJW) spectral clustering method partitions data using the largest K eigenvectors of the normalized affinity matrix derived from a dataset. but when the dataset is of complex structure, the affinity matrix constructed by traditional Gaussian function could not reflect the real similarity among data points, then the decision of clustering number and selection of K largest eigenvectors are not always effective. Constructing a good affinity matrix is very important to spectral clustering. A new affinity matrix generation method is proposed by using neighbor relation propagation principle and a neighbor relation propagation algorithm is also given. The affinity matrix generated can increase the similarity of point pairs that should be in same cluster and can well detect the structure of data. An improved multi-way spectral clustering algorithm is proposed then. We have performed experiments on dataset of complex structure, adopting Tian Xia and his partner's method for a baseline. The experiment result shows that our affinity matrix well reflects the real similarity among data points and selecting the largest K Eigenvectors gives the correct partition. We have also made comparison with NJW method on some common datasets, the results show that our method is more robust. (C) 2012 Elsevier B.V. All rights reserved.