Robust Clustering with Distance and Density

2. Related Work

AP is a distance-based algorithm for identifying exemplars in a dataset by imitating the message passing and feedback routine between the data objects (Dueck & Frey, 2007; Frey& Dueck, 2007). It enjoys lower error than traditional methods, which is computationally efficient in many applications (Dueck & Frey, 2007; Dueck et al., 2008). The measurements of the mutual similarity among objects are recorded in an input matrix of . The diagonal of the matrix, , is treated as the reference for the data object to become the cluster center. The responsibility that is sent from data object to the candidate clustering center , indicates how suitable an object can be used as a cluster center for the object . The availability that is sent from the candidate cluster center to the data object , reflects how likely the object chooses as its cluster center. The larger the value of and , the higher the probability that object is to become the cluster center. Consequently, increase the chance that an object belongs to a cluster with its center at object . During this iterative process, AP keeps updating and between the data objects until the predefined convergence criteria is met. The AP parameters adhere to what are used in its original settings, for example, a maximum of iterations is 1000, the upper limit of steady times is 100, and the damping coefficient is 0.9. The reference of clustering center is chosen to be the median value of similarity matrix.