Pairwise clustering by minimizing the error of unsupervised Nearest Neighbor classification

Yingzhen Yang, Xinqi Chu, Thomas S. Huang

Research output: Contribution to conferencePaper

Abstract

Pair wise clustering methods, including the popular graph cut based approaches such as normalized cut, partition the data space into clusters by the pair wise affinity between data points. The success of pair wise clustering largely depends on the pair wise affinity function defined over data points coming from different clusters. Interpreting the pair wise affinity in a probabilistic framework, we build the relationship between pair wise clustering and unsupervised classification by learning the soft Nearest Neighbor (NN) classifier from unlabeled data, and search for the optimal partition of the data points by minimizing the generalization error of the learned classifier associated with the data partitions. Modeling the underlying distribution of the data by non-parametric kernel density estimation, the asymptotic generalization error of the unsupervised soft NN classification involves only the pair wise affinity between data points. Moreover, such error rate reduces to the well-known kernel form of graph cut in case of uniform data distribution, which provides another understanding of the kernel similarity used in Laplacian Eigenmaps which also assumes uniform distribution. By minimizing the generalization error bound, we propose a new clustering algorithm. Our algorithm efficiently partition the data by inference in a pair wise MRF model. Experimental results demonstrate the effectiveness of our method.

Original languageEnglish (US)
Pages182-187
Number of pages6
DOIs
StatePublished - Jan 1 2013
Event2013 12th International Conference on Machine Learning and Applications, ICMLA 2013 - Miami, FL, United States
Duration: Dec 4 2013Dec 7 2013

Other

Other2013 12th International Conference on Machine Learning and Applications, ICMLA 2013
CountryUnited States
CityMiami, FL
Period12/4/1312/7/13

    Fingerprint

Keywords

  • Kernel Density Estimation
  • Nearest Neighbor Classifier
  • Pairwise Clustering

ASJC Scopus subject areas

  • Computer Science Applications
  • Human-Computer Interaction

Cite this

Yang, Y., Chu, X., & Huang, T. S. (2013). Pairwise clustering by minimizing the error of unsupervised Nearest Neighbor classification. 182-187. Paper presented at 2013 12th International Conference on Machine Learning and Applications, ICMLA 2013, Miami, FL, United States. https://doi.org/10.1109/ICMLA.2013.188