Doubly Stochastic Distance Clustering

In doubly stochastic (DS) clustering, it is common to initialize the DS matrix with a similarity matrix and use the eigen-decomposition of the DS-scaled similarity matrix to obtain the optimal cluster indicators. The selection of a proper initial similarity measure, however, is a difficult problem and the eigen-decomposition is time-consuming, with time complexity of O(n(3)) where n is the data size. In this paper, we propose to replace the DS similarity matrix with the DS Euclidean distance matrix for clustering. We show that the optimal cluster indicators minimize the k-medoids error of data with DS Euclidean distance. We propose a fast method to obtain data with DS distance for clustering. Compared with DS similarity clustering, DS distance clustering is kernel-free and of low time complexity, typically O(nd(2)+d(3)) where d is the input dimension. Experimental results on real-world datasets and the image segmentation task verify the superiority of our DS distance clustering over several competing methods.