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 language | English (US) |
---|---|
Pages | 182-187 |
Number of pages | 6 |
DOIs | |
State | Published - 2013 |
Externally published | Yes |
Event | 2013 12th International Conference on Machine Learning and Applications, ICMLA 2013 - Miami, FL, United States Duration: Dec 4 2013 → Dec 7 2013 |
Other
Other | 2013 12th International Conference on Machine Learning and Applications, ICMLA 2013 |
---|---|
Country/Territory | United States |
City | Miami, FL |
Period | 12/4/13 → 12/7/13 |
Keywords
- Kernel Density Estimation
- Nearest Neighbor Classifier
- Pairwise Clustering
ASJC Scopus subject areas
- Computer Science Applications
- Human-Computer Interaction