Transitive Distance Clustering with K-Means Duality

Zhiding Yu, Chunjing Xu, Deyu Meng, Zhuo Hui, Fanyi Xiao, Wenbo Liu, Jianzhuang Liu

CVPR 2014

doi:10.1109/CVPR.2014.131 /cvpr/2014/yu2014cvpr-transitive/

Abstract

We propose a very intuitive and simple approximation for the conventional spectral clustering methods. It effectively alleviates the computational burden of spectral clustering - reducing the time complexity from O(n^3) to O(n^2) - while capable of gaining better performance in our experiments. Specifically, by involving a more realistic and effective distance and the "k-means duality" property, our algorithm can handle datasets with complex cluster shapes, multi-scale clusters and noise. We also show its superiority in a series of its real applications on tasks including digit clustering as well as image segmentation.

PDF CVPR Semantic Scholar

Cite

Text

Yu et al. "Transitive Distance Clustering with K-Means Duality." Conference on Computer Vision and Pattern Recognition, 2014. doi:10.1109/CVPR.2014.131

Markdown

[Yu et al. "Transitive Distance Clustering with K-Means Duality." Conference on Computer Vision and Pattern Recognition, 2014.](https://mlanthology.org/cvpr/2014/yu2014cvpr-transitive/) doi:10.1109/CVPR.2014.131

BibTeX

@inproceedings{yu2014cvpr-transitive,
  title     = {{Transitive Distance Clustering with K-Means Duality}},
  author    = {Yu, Zhiding and Xu, Chunjing and Meng, Deyu and Hui, Zhuo and Xiao, Fanyi and Liu, Wenbo and Liu, Jianzhuang},
  booktitle = {Conference on Computer Vision and Pattern Recognition},
  year      = {2014},
  doi       = {10.1109/CVPR.2014.131},
  url       = {https://mlanthology.org/cvpr/2014/yu2014cvpr-transitive/}
}