Large Scale Spectral Clustering Using Approximate Commute Time Embedding

Details Large Scale Spectral Clustering Using Approximate Commute Time Embedding Large Scale Spectral Clustering Using Approximate Commute Time Embedding

2011-11-19

arxiv.org/abs/1111.4541v2

Computer Science

Learning

Scientific paper

Spectral clustering is a novel clustering method which can detect complex shapes of data clusters. However, it requires the eigen decomposition of the graph Laplacian matrix, which is proportion to $O(n^3)$ and thus is not suitable for large scale systems. Recently, many methods have been proposed to accelerate the computational time of spectral clustering. These approximate methods usually involve sampling techniques by which a lot information of the original data may be lost. In this work, we propose a fast and accurate spectral clustering approach using an approximate commute time embedding, which is similar to the spectral embedding. The method does not require using any sampling technique and computing any eigenvector at all. Instead it uses random projection and a linear time solver to find the approximate embedding. The experiments in several synthetic and real datasets show that the proposed approach has better clustering quality and is faster than the state-of-the-art approximate spectral clustering methods.

Affiliated with

Also associated with

No associations

Rating

Large Scale Spectral Clustering Using Approximate Commute Time Embedding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Large Scale Spectral Clustering Using Approximate Commute Time Embedding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large Scale Spectral Clustering Using Approximate Commute Time Embedding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-514601