Automatic Scale Parameters in Affinity Matrix Construction for Improved Spectral Clustering

摘要

Spectral clustering partitions data into similar groups in the eigenspace of the affinity matrix. The accuracy of the spectral clustering algorithm is a r ected 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 sigma. The value of sigma, a control parameter of drop in affinity value, is generally a fixed constant or determined by manual tuning. In this research work, ffiis 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 sigma(i) corresponding to a data point x(i) 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 sigma 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 sigma 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.