Automatic Determination of Intrinsic Cluster Number Sequence in Spectral Clustering Using Random Walk on Graph (WP-P8)

Author(s) : Xin Zheng (Institute of HCI and Media Integration, Tsinghua University, China) Xueyin Lin (Institute of HCI and Media Integration, Tsinghua University, China)

Abstract : Spectral clustering has been one of the most promising clustering methods in the last few years. But most of the literature ignored the predetermination of two sensitive factors: the cluster number and the parameter of affinity function. In this paper we analyze in detail their influence on clustering results and show that the two factors are closely correlated when producing stable clustering results. We then introduce the concept of intrinsic cluster number family, an extension of cluster number, which is designed to achieve stable clustering hierarchy. In order to determine this family automatically, we introduce into spectral clustering the technique of random walk on graph, which provides another dimension showing intrinsic structure of data. Although random walk is expensive on computation, we find a trick to significantly reduce the computational complexity. One major difference between our method and traditional hierarchical clustering(HC) is that we use operable clustering stability to select reasonable cluster numbers. Successful results of the method applied on both simulated data clustering and natural image segmentation are presented.

Menu