Semi-Supervised Affinity Propagation with Soft Instance-Level Constraints.

Area of Science:

• Computer Science
• Machine Learning
• Data Mining

Background:

• Clustering algorithms like Affinity Propagation (AP) group data but often lack supervision.
• Existing semi-supervised methods may struggle with noisy constraints or labels.

Purpose of the Study:

• To introduce Soft-constraint Semi-Supervised Affinity Propagation (SCSSAP) for improved clustering.
• To enhance AP by incorporating adjustable constraints and penalties.

Main Methods:

• SCSSAP modifies the AP similarity matrix iteratively based on constraint violations.
• A penalty is added to the objective function for constraint violations.
• The algorithm incorporates metric learning for further performance enhancement.

Main Results:

• SCSSAP outperforms unsupervised AP with noiseless constraints.
• It matches or exceeds previous semi-supervised AP and constrained expectation maximization.
• SCSSAP demonstrates superior accuracy in clustering with noisy labels and constraints.

Conclusions:

• SCSSAP provides a robust semi-supervised clustering solution adaptable to noisy data.
• The tunable penalty parameter allows for flexible integration of confidence in constraints.
• Metric learning extension further boosts clustering performance.