Pairwise Exemplar Clustering

Exemplar-based clustering methods have been extensively shown to be effective in many clustering problems. They adaptively determine the number of clusters and hold the ap-pealing advantage of not requiring the estimation of latent pa-rameters, which is otherwise difficult in case of complicated parametric model and high dimensionality of the data. How-ever, modeling arbitrary underlying distribution of the data is still difficult for existing exemplar-based clustering methods. We present Pairwise Exemplar Clustering (PEC) to alleviate this problem by modeling the underlying cluster distributions more accurately with non-parametric kernel density estima-tion. Interpreting the clusters as classes from a supervised learning perspective, we search for an optimal partition of the data that balances two quantities: 1 the misclassification rate of the data partition for separating the clusters; 2 the sum of within-cluster dissimilarities for controlling the cluster size. The broadly used kernel form of cut turns out to be a special case of our formulation. Moreover, we optimize the corre-sponding objective function by a new efficient algorithm for message computation in a pairwise MRF. Experimental re-sults on synthetic and real data demonstrate the effectiveness of our method