K-MEAP: Multiple Exemplars Affinity Propagation With Specified $K$ Clusters.

Area of Science:

• Computer Science
• Machine Learning
• Data Mining

Background:

• The single exemplar-based Affinity Propagation (AP) clustering approach has been extended to Multi-Exemplar Affinity Propagation (MEAP).
• MEAP can identify multiple exemplars per cluster but cannot directly utilize user-specified cluster numbers (K).
• Rerunning MEAP to achieve a specific K is computationally intensive.

Purpose of the Study:

• To propose a novel clustering algorithm, Multiple Exemplars Affinity Propagation with Specified K Clusters (K-MEAP).
• To enable direct generation of a user-defined number of clusters (K) while retaining MEAP's advantages.
• To improve the efficiency and accuracy of clustering when K is known.

Main Methods:

• Introduction of two novel message types within the K-MEAP algorithm.
• These messages control the number of clusters during the message-passing process.
• Detailed problem formulation, message derivation, and in-depth analysis are provided.

Main Results:

• K-MEAP successfully generates a specified number of K clusters directly and efficiently.
• The algorithm avoids the need for time-consuming parameter tuning.
• Experimental studies on 11 real-world datasets show K-MEAP outperforms related approaches in clustering accuracy.

Conclusions:

• K-MEAP offers a significant advancement in clustering by directly incorporating user-defined cluster numbers.
• The method is efficient and accurate, outperforming existing algorithms.
• K-MEAP provides a practical solution for scenarios where the desired number of clusters is known beforehand.