Automatic determination of intrinsic cluster number family in spectral clustering using random walk on graph

In spectral clustering algorithms, selecting the cluster number and determining the parameter of affinity function are two generally unsolved problems. In this paper we analyze in detail the influence of these two parameters on clustering results and show their close relationship. We further extend one of them, the cluster number, to intrinsic cluster number family, which is designed to achieve stable clustering hierarchy. Specifically, we use random walk on graph and eigengap to discover the intrinsic structure of the data. We proposed an algorithm to simultaneously determination the cluster number family and the parameter of affinity function. The experimental results on both simulated data clustering and natural image segmentation show that our proposed algorithm has many advantages.