Agglomerative clustering via maximum incremental path integral
Publication in refereed journal

Times Cited
Web of Science47WOS source URL (as at 26/10/2020) Click here for the latest count
Altmetrics Information

Other information
AbstractAgglomerative clustering, which iteratively merges small clusters, is commonly used for clustering because it is conceptually simple and produces a hierarchy of clusters. In this paper, we propose a novel graph-structural agglomerative clustering algorithm, where the graph encodes local structures of data. The idea is to define a structural descriptor of clusters on the graph and to assume that two clusters have large affinity if their structural descriptors undergo substantial change when merging them into one cluster. A key insight of this paper to treat a cluster as a dynamical system and its samples as states. Based on that, Path Integral, which has been introduced in statistical mechanics and quantum mechanics, is utilized to measure the stability of a dynamical system. It is proposed as the structural descriptor, and the affinity between two clusters is defined as Incremental Path Integral, which can be computed in a closed-form exact solution, with linear time complexity with respect to the maximum size of clusters. A probabilistic justification of the algorithm based on absorbing random walk is provided. Experimental comparison on toy data and imagery data shows that it achieves considerable improvement over the state-of-the-art clustering algorithms. (C) 2013 Elsevier Ltd. All rights reserved.
All Author(s) ListZhang W, Zhao DL, Wang XG
Journal namePattern Recognition
Volume Number46
Issue Number11
Pages3056 - 3065
LanguagesEnglish-United Kingdom
KeywordsAgglomerative clustering; Graph algorithms; Path integral; Random walk
Web of Science Subject CategoriesComputer Science; Computer Science, Artificial Intelligence; COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE; Engineering; Engineering, Electrical & Electronic; ENGINEERING, ELECTRICAL & ELECTRONIC

Last updated on 2020-27-10 at 00:41