Title :
Isoperimetric cut on a directed graph
Author :
Chen, Mo ; Liu, Ming ; Liu, Jianzhuang ; Tang, Xiaoou
Author_Institution :
Dept. of Inf. Eng., Chinese Univ. of Hong Kong, Hong Kong, China
Abstract :
In this paper, we propose a novel probabilistic view of the spectral clustering algorithm. In our framework, the spectral clustering algorithm can be viewed as assigning class labels to samples to minimize the Bayes classification error rate by using a kernel density estimator (KDE). From this perspective, we propose to construct directed graphs using variable bandwidth KDEs. Such a variable bandwidth KDE based directed graph has the advantage that it encodes the local density information of the data in the graph edge weights. In order to cluster vertices of the directed graph, we develop a directed graph partitioning algorithm which optimizes a random walk isoperimetric ratio. The partitioning result can be obtained efficiently by solving a system of linear equations. We have applied our algorithm to several benchmark data sets and obtained promising results.
Keywords :
Bayes methods; directed graphs; image classification; pattern clustering; Bayes classification error rate; KDE; directed graph; graph edge weights; kernel density estimator; local density information; spectral clustering algorithm; variable bandwidth KDE; Art; Bandwidth; Clustering algorithms; Clustering methods; Distributed computing; Equations; Error analysis; Kernel; Partitioning algorithms; Shape;
Conference_Titel :
Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on
Conference_Location :
San Francisco, CA
Print_ISBN :
978-1-4244-6984-0
DOI :
10.1109/CVPR.2010.5539889