Transitive Distance Clustering with K-Means Duality

Zhiding Yu, Chunjing Xu, Deyu Meng, Zhuo Hui, Fanyi Xiao, Wenbo Liu, Jianzhuang Liu; The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2014, pp. 987-994


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.

Related Material

author = {Yu, Zhiding and Xu, Chunjing and Meng, Deyu and Hui, Zhuo and Xiao, Fanyi and Liu, Wenbo and Liu, Jianzhuang},
title = {Transitive Distance Clustering with K-Means Duality},
booktitle = {The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
month = {June},
year = {2014}