DocumentCode :
3403835
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
fYear :
2010
fDate :
13-18 June 2010
Firstpage :
2109
Lastpage :
2116
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on
Conference_Location :
San Francisco, CA
ISSN :
1063-6919
Print_ISBN :
978-1-4244-6984-0
Type :
conf
DOI :
10.1109/CVPR.2010.5539889
Filename :
5539889
Link To Document :
بازگشت