Source-linked AI summary
Adaptive Affinity Propagation Clustering
Kaijun Wang, Junying Zhang, Dan Li, Xinna Zhang, Tao Guo
TL;DR
AP makes it difficult to choose a preference yielding an optimal clustering and does not automatically eliminate oscillations. Adaptive AP scans preferences, adjusts damping, and escapes oscillations when needed; experiments show it can outperform or equal AP in clustering quality and oscillation elimination.
Problem
AP lacks an automatic way to select a preference that yields an optimal clustering solution and to eliminate oscillations during convergence.
Method
Adaptive AP scans preference values, adaptively adjusts damping to eliminate oscillations, and decreases preference values to escape oscillations when damping fails.
Results
Adaptive AP can outperform or equal AP in clustering quality and oscillation elimination.
Takeaways & Limitations
Adaptive AP provides an automatic approach to searching for suitable clusterings and handling oscillations instead of relying on manual parameter adjustment.
Takeaways & Limitations
The chosen preference-scanning scope and stopping settings constrain the search, with the paper noting that validity methods for complex overlapping clusters require further research.
Abstract
from arXiv · showhide
Affinity propagation clustering (AP) has two limitations: it is hard to know what value of parameter 'preference' can yield an optimal clustering solution, and oscillations cannot be eliminated automatically if occur. The adaptive AP method is proposed to overcome these limitations, including adaptive scanning of preferences to search space of the number of clusters for finding the optimal clustering solution, adaptive adjustment of damping factors to eliminate oscillations, and adaptive escaping from oscillations when the damping adjustment technique fails. Experimental results on simulated and real data sets show that the adaptive AP is effective and can outperform AP in quality of clustering results.
1 Introduction
AP is a fast, general clustering algorithm that uses pairwise similarities and candidate exemplars, but its preference and damping settings create unresolved practical problems. Adaptive AP addresses these problems through preference scanning and automatic oscillation handling.
- AP clusters data from pairwise similarities while treating every data point as a potential exemplar.It iteratively accumulates responsibility and availability evidence to identify stable exemplars and corresponding clusters.
- The preference p influences which points become exemplars and how many clusters are produced, but the usual median similarity preference may not yield an optimal solution.Larger preference values increase a point’s likelihood of becoming a final cluster center.
- AP’s damping factor controls iterative updates and may need manual increases when oscillations prevent convergence.Using damping close to 1 can suppress oscillations but makes AP run very slowly.
- Adaptive AP combines preference scanning, adaptive damping, and adaptive escape to address preference selection and oscillation problems.The method searches preference values, adjusts damping automatically, and decreases preference when damping fails.
2 Adaptive Affinity Propagation
Adaptive AP searches preference values for clustering solutions with different cluster counts, validates them, and adaptively handles oscillations during iterative updates. Its mechanisms adjust damping, escape by decreasing preference, and vary scanning steps to balance speed and search resolution.
- Adaptive damping and escape: Adaptive damping detects oscillations through a monitoring window and gradually increases lam until a preset stopping condition is met.Oscillations are identified when non-oscillation features occur in fewer than two thirds of the window.
- Adaptive damping and escape: When lam reaches at least 0.85 without suppressing oscillations, adaptive escape gradually decreases p to move away from the problematic preference.This escape mechanism operates alongside adaptive preference scanning.
- Adaptive preference scanning: Adaptive p-scanning decreases preference values during the iterative process to generate clustering solutions with different numbers of clusters.The method checks exemplar convergence and additional iterations before each preference reduction, while reusing current responsibility and availability values.
- Adaptive preference scanning: The adaptive decreasing step sets ps=0.01pm/q, making preference steps smaller for larger exemplar counts and larger for smaller counts.This design addresses the differing sensitivity of large and small cluster counts while balancing runtime against missed cluster structures.
- Adaptive preference scanning: The scan starts at p=pm/2 and reduces preference until K=2, with maxits=50000 preventing an iteration limit from blocking the search.The preference domain corresponds to cluster counts from 1 through n, while the square of n is treated as a reasonable upper limit for optimal cluster count.
- Cluster validation: Silhouette index selects the optimal solution by choosing the clustering with the largest overall average silhouette across the scanned cluster counts.The index reflects cluster compactness and separation.
3 Experimental Results
Experiments compare adaptive AP with AP across simulated and real data sets using clustering accuracy, quality, oscillation handling, and runtime-related evaluation criteria. Adaptive AP generally identifies cluster counts and produces higher-quality solutions, while preserving identical results on two application tasks.
- Data sets: Experiments use twelve simulated and real data sets, including varied cluster structures and gene-expression data.The first four data sets are simulated; the remaining data sets are real, with Yeast and NCI60 as gene-expression data.
- Evaluation: Table 4 reports adAP error, oscillation elimination, running time, and Fowlkes-Mallows index, with FM measuring agreement against true labels.The last four data sets lack true class labels, so they have no error-rate or FM values.
- Clustering results: For all but the last four data sets, adAP finds the correct number of clusters in every case while AP fails in every case.This comparison is reported directly from Table 4 results.
- Clustering results: FM values are higher for adAP than AP, indicating better clustering quality, while oscillations produce poor AP solutions for 22k10far and Ionosphere.FM measures agreement with true class labels, with larger values indicating better agreement.
- Application tasks: Both methods find the same four representative sentences for Document data and the same seven airport hubs for Travelroute data.These application tasks yield identical cluster-center selections for adAP and AP.
- Application tasks: For Exons, adAP has a higher exon identification rate, while for overlapping FaceImage clusters it produces 102 clusters versus AP's less suitable result.FaceImage contains overlapping clusters among 900 images from 100 persons, limiting separability.
4 Conclusion
The conclusion presents adaptive AP as a method that addresses preference selection and oscillation handling in AP. It combines preference scanning, adaptive damping, adaptive escape, and cluster validation, and is reported to outperform or equal AP in clustering quality and oscillation elimination.
- Adaptive preference scanning: Adaptive AP scans preference values and uses cluster validation to find a data-set-suitable clustering solution.The scanning searches the number-of-clusters space rather than requiring a fixed preference value.
- Oscillation handling: Adaptive damping automatically eliminates oscillations, while adaptive escape decreases preference when damping fails.These techniques replace manual damping adjustment and provide a fallback for unresolved oscillations.
- Conclusion: Adaptive AP can outperform or equal AP in clustering quality and oscillation elimination.The conclusion reports this comparison across the evaluated settings.
- Open issue: Further research is needed to determine which validity method best suits data sets with complex structures such as overlapping clusters.The conclusion identifies validity-method selection as an open issue for complex cluster structures.