Abstract | ||
---|---|---|
Affinity Propagation is a clustering algorithm used in many applications. It iteratively updates messages between data points until convergence. The message updating process enables Affinity Propagation to have higher clustering quality compared with other approaches. However, its computation cost is high; it is quadratic in the number of data points. This is because it updates the messages of all data point pairs. This paper proposes an efficient algorithm that guarantees the same clustering results as the original algorithm. Our approach, F-AP, is based on two ideas: (1) it computes upper and lower estimates to limit the messages to be updated in each iteration, and (2) it dynamically detects converged messages to efficiently skip unneeded updates. Experiments show that F-AP is much faster than previous approaches with no loss in clustering performance. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1145/2783258.2783280 | ACM Knowledge Discovery and Data Mining |
Keywords | Field | DocType |
Affinity Propagation,efficient,clustering | Convergence (routing),Data point,Data mining,Canopy clustering algorithm,CURE data clustering algorithm,Data stream clustering,Affinity propagation,Correlation clustering,Computer science,Theoretical computer science,Cluster analysis | Conference |
Citations | PageRank | References |
6 | 0.59 | 18 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Yasuhiro Fujiwara | 1 | 292 | 25.43 |
Makoto Nakatsuji | 2 | 225 | 13.16 |
Hiroaki Shiokawa | 3 | 153 | 12.82 |
Yasutoshi Ida | 4 | 17 | 6.58 |
Machiko Toyoda | 5 | 35 | 2.57 |