Spectral clustering with physical intuition on spring-mass dynamics

Abstract

In this paper, we provide a new insight into clustering with a spring-mass dynamics, and propose a resulting hierarchical clustering algorithm. To realize the spectral graph partitioning as clustering, we model a weighted graph of a data set as a mass-spring dynamical system, where we regard a cluster as an oscillating single entity of a data set with similar properties. And then, we describe how oscillation modes are related with eigenvectors of a graph Laplacian matrix of the dataset. In each step of the clustering, we select a group of clusters, which has the biggest number of constituent clusters. This group is divided into sub-clusters by examining an eigenvector minimizing a cost function, which is formed in such a way that subdivided clusters will be balanced with large size. To find k clusters out of non-spherical or complex data, we first transform the data into spherical clusters located on the unit sphere positioned in the (k - 1)- dimensional space. In the sequel, we use the previous procedure to these transformed data. The computational experiments demonstrate that the proposed method works quite well on a variety of data sets, although its performance degrades with the degree of overlapping of datasets. (C) 2014 The Franklin Institute. Published by Elsevier Ltd. All rights reserved.