2015 AdaptiveMessageUpdateforFastAff

• (Fujiwara et al., 2015) ⇒ Yasuhiro Fujiwara, Makoto Nakatsuji, Hiroaki Shiokawa, Yasutoshi Ida, and Machiko Toyoda. (2015). “Adaptive Message Update for Fast Affinity Propagation.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783280

Subject Headings: Affinity Propagation.

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Adaptive+Message+Update+for+Fast+Affinity+Propagation
• http://dl.acm.org/citation.cfm?id=2783258.2783280&preflayout=flat#citedby

Quotes

Author Keywords

• Affinity propagation; clustering; data mining; efficient

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.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 AdaptiveMessageUpdateforFastAff	Yasuhiro Fujiwara Makoto Nakatsuji Hiroaki Shiokawa Yasutoshi Ida Machiko Toyoda			Adaptive Message Update for Fast Affinity Propagation				10.1145/2783258.2783280		2015