Weighted bilateral K-means algorithm for fast co-clustering and fast spectral clustering

摘要

Bipartite spectral graph partition (BSGP) is a school of the most well-known algorithms designed for the bipartite graph partition problem. It is also a fundamental mathematical model widely used in the tasks of co-clustering and fast spectral clustering. In BSGP, the key is to find the minimal normalized cuts (Ncuts) of bipartite graph. However, the convolutional BSGP algorithms usually need to use the singular value decomposition (SVD) to find the minimal Ncuts, which is computational prohibitive. Under this circumstance, the application range of those methods would be limited when the volume of the dataset is huge or the dimension of features is high. To overcome this problem, this paper proposes a novel weighted bilateral k-means (WBKM) algorithm and applies it for co-clustering and fast spectral clustering. Specifically, WBKM is a relaxation of the problem of finding the minimal Ncuts of bipartite graph, so it can be seen as a new solution for the minimal-Ncuts problem in bipartite graph. Different from the conventional relaxation ways, WBKM relaxes the minimal-Ncuts problem to a Non-negative decomposition problem which can be solved by an efficient iterative method. Therefore, the running speed of the proposed method is much faster. Besides, as our model can directly output the clustering results without any help of post-procedures, its solution tends to be more close to the ideal solution of the minimal-Ncuts problem than that of the conventional BSGP algorithms. To demonstrate the effectiveness and efficiency of the proposed method, extensive experiments on various types of datasets are conducted. Compared with other state-of-the-art methods, the proposed WBKM not only has faster computational speed, but also achieves more promising clustering results.