Clustering with Transitive Distance and K-Means Duality
| dc.creator | Xu, Chunjing | |
| dc.creator | Liu, Jianzhuang | |
| dc.creator | Tang, Xiaoou | |
| dc.date | 2007-11-22 | |
| dc.date.accessioned | 2026-07-07T08:44:34Z | |
| dc.date.available | 2026-07-07T08:44:34Z | |
| dc.description | Recent spectral clustering methods are a propular and powerful technique for data clustering. These methods need to solve the eigenproblem whose computational complexity is $O(n^3)$, where $n$ is the number of data samples. In this paper, a non-eigenproblem based clustering method is proposed to deal with the clustering problem. Its performance is comparable to the spectral clustering algorithms but it is more efficient with computational complexity $O(n^2)$. We show that with a transitive distance and an observed property, called K-means duality, our algorithm can be used to handle data sets with complex cluster shapes, multi-scale clusters, and noise. Moreover, no parameters except the number of clusters need to be set in our algorithm. | |
| dc.description | 13 pages, 6 figures | |
| dc.identifier | https://arxiv.org/abs/0711.3594 | |
| dc.identifier | http://arxiv.org/abs/0711.3594 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/142701 | |
| dc.subject | Machine Learning | |
| dc.title | Clustering with Transitive Distance and K-Means Duality | |
| dc.type | text |