Header menu link for other important links
X
Automatic Scale Parameters in Affinity Matrix Construction for Improved Spectral Clustering
S. Mohanavalli, , C. Aravindan
Published in World Scientific Publishing Co. Pte Ltd
2016
Volume: 30
   
Issue: 10
Abstract
Spectral clustering partitions data into similar groups in the eigenspace of the affinity matrix. The accuracy of the spectral clustering algorithm is affected by the affine equivariance realized in the translation of distance to similarity relationship. The similarity value computed as a Gaussian of the distance between data objects is sensitive to the scale factor σ. The value of σ, a control parameter of drop in affinity value, is generally a fixed constant or determined by manual tuning. In this research work, σ is determined automatically from the distance values i.e.The similarity relationship that exists in the real data space. The affinity value of a data pair is determined as a location estimate of the spread of distance values of the data points with the other points. The scale factor σi corresponding to a data point xi is computed as the trimean of its distance vector and used in fixing the scale to compute the affinity matrix. Our proposed automatic scale parameter for spectral clustering resulted in a robust similarity matrix which is affine equivariant with the distance distribution and also eliminates the overhead of manual tuning to find the best σ value. The performance of spectral clustering using such affinity matrices was analyzed using UCI data sets and image databases. The obtained scores for NMI, ARI, Purity and F-score were observed to be equivalent to those of existing works and better for most of the data sets. The proposed scale factor was used in various state-of-The-Art spectral clustering algorithms and it proves to perform well irrespective of the normalization operations applied in the algorithms. A comparison of clustering error rates obtained for various data sets across the algorithms shows that the proposed automatic scale factor is successful in clustering the data sets equivalent to that obtained using manually tuned best σ value. Thus the automatic scale factor proposed in this research work eliminates the need for exhaustive grid search for the best scale parameter that results in best clustering performance. © 2016 World Scientific Publishing Company.
About the journal
JournalInternational Journal of Pattern Recognition and Artificial Intelligence
PublisherWorld Scientific Publishing Co. Pte Ltd
ISSN02180014