A Fuzzy Clustering Algorithm for the Mode-Seeking Framework

In this paper, we propose a new fuzzy clustering algorithm based on the modeseekingframework. Given a dataset in Rd, we define regions of high density thatwe call cluster cores. We then consider a random walk on a neighborhood graphbuilt on top of our data points which is designed to be attracted by high densityregions. The strength of this attraction is controlled by a temperature parameterbeta > 0. The membership of a point to a given cluster is then the probability for therandom walk to hit the corresponding cluster core before any other. While manyproperties of random walks (such as hitting times, commute distances, etc. . . ) havebeen shown to enventually encode purely local information when the number ofdata points grows, we show that the regularization introduced by the use of clustercores solves this issue. Empirically, we show how the choice of beta influences thebehavior of our algorithm: for small values of beta the result is close to hard modeseekingwhereas when beta is close to 1 the result is similar to the output of a (fuzzy)spectral clustering. Finally, we demonstrate the scalability of our approach by providingthe fuzzy clustering of a protein configuration dataset containing a milliondata points in 30 dimensions.