Extended Affinity Propagation: Global Discovery and Local Insights
This is an incremental improvement for clustering analysts, addressing specific shortcomings in an existing algorithm.
The authors tackled the problem of Affinity Propagation's lack of global structure discovery by proposing Extended Affinity Propagation, which preserves desirable features like exemplars and no need to specify cluster numbers while overcoming this limitation and providing additional insights such as refined confidence values and local cluster strengths, achieving this goal as illustrated on synthetic and real-world datasets.
We propose a new clustering algorithm, Extended Affinity Propagation, based on pairwise similarities. Extended Affinity Propagation is developed by modifying Affinity Propagation such that the desirable features of Affinity Propagation, e.g., exemplars, reasonable computational complexity and no need to specify number of clusters, are preserved while the shortcomings, e.g., the lack of global structure discovery, that limit the applicability of Affinity Propagation are overcome. Extended Affinity Propagation succeeds not only in achieving this goal but can also provide various additional insights into the internal structure of the individual clusters, e.g., refined confidence values, relative cluster densities and local cluster strength in different regions of a cluster, which are valuable for an analyst. We briefly discuss how these insights can help in easily tuning the hyperparameters. We also illustrate these desirable features and the performance of Extended Affinity Propagation on various synthetic and real world datasets.