Clustering based on the In-tree Graph Structure and Affinity Propagation

Clustering analysis aims to discover the underlying clusters in the data points according to their similarities. It has wide applications ranging from bioinformatics to astronomy. Here, we proposed a Generalized Affinity Propagation (G-AP) clustering algorithm. Data points are first organized in a sparsely connected in-tree (IT) structure by a physically inspired strategy. Then, additional edges are added to the IT structure for those reachable nodes. This expanded structure is subsequently trimmed by affinity propagation method. Consequently, the underlying cluster structure, with separate clusters, emerges. In contrast to other IT-based methods, G-AP is fully automatic and takes as input the pairs of similarities between data points only. Unlike affinity propagation, G-AP is capable of discovering nonspherical clusters.

cs.LG cs.CV stat.ML Computer Science Physics Mathematics

View graph Source

Paper

References (7)

01IEEE Trans. Comput1971 · IEEE Trans. Comput

02ACM Trans. Knowl. Discovery Data2007 · ACM Trans. Knowl. Discovery Data

03Pattern Recognit2008 · Pattern Recognit

04The idea behind this process is to first use a simple rule which allows the emergence of error and then repair the error by a repair mechanism so as to obtain a reliable outputThe idea behind this process is to first use a simple rule which allows the emergence of error and then repair the error by a repair mechanism so as to obtain a reliable output

05The IT structure contains N – 1 directed edges (N is the number of the nodes), even sparserThe IT structure contains N – 1 directed edges (N is the number of the nodes), even sparser

06Supplementary Material: fig. S1~S5

07even sparser than the K (= 1) nearest neighbor graph (containing N undirected edges)The IT structure contains N -1 directed edges (N is the number of the nodes)