Affinity propagation seems to outperform methods that randomly resample potential centers, especially for non-trivial numbers of clusters. Why?
Finding k clusters within n data points involves a search space of size n choose k, or [n(n-1)(n-2)…(n-k+1)]/[k(k-1)(k-2)…(2)], which is polynomial in n if k is within a fixed distance of 1 or n, but exponential in n if k grows linearly with n. Algorithms dependent on random initialization (e.g. k-centers clustering) will perform better with smaller search spaces because the initialization will be more likely to be sampled from a region near the optimal solution. So, those methods work well when k is close to 1 or n. Affinity does not rely on random sampling, but instead exchanges soft information between data points while considering all of them to be potential exemplars. It works better in the large-search-space situation, where k is not close to 1 or n.
Related Questions
- Is there a connection between affinity propagation and other methods, like hierarchical agglomerative clustering and spectral clustering (normalized cuts)?
- Affinity propagation seems to outperform methods that randomly resample potential centers, especially for non-trivial numbers of clusters. Why?
- Can affinity propagation be viewed as just a good way to initialize standard methods, such as k-centers clustering?
