Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Learning Spectral Clustering

Francis R. Bach and Michael I. Jordan

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-03-1249
June 2003

http://www.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1249.pdf

Spectral clustering refers to a class of techniques which rely on the eigenstructure of a similarity matrix to partition points into disjoint clusters, with points in the same cluster having high similarity and points in different clusters having low similarity. In this paper, we derive a new cost function for spectral clustering based on a measure of error between a given partition and a solution of the spectral relaxation of a minimum normalized cut problem. Minimizing this cost function with respect to the partition leads to a new spectral clustering algorithm. Minimizing with respect to the similarity matrix leads to an algorithm for learning the similarity matrix. We develop a tractable approximation of our cost function that is based on the power method of computing eigenvectors.


BibTeX citation:

@techreport{Bach:CSD-03-1249,
    Author = {Bach, Francis R. and Jordan, Michael I.},
    Title = {Learning Spectral Clustering},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2003},
    Month = {Jun},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2003/5549.html},
    Number = {UCB/CSD-03-1249},
    Abstract = {Spectral clustering refers to a class of techniques which rely on the eigenstructure of a similarity matrix to partition points into disjoint clusters, with points in the same cluster having high similarity and points in different clusters having low similarity. In this paper, we derive a new cost function for spectral clustering based on a measure of error between a given partition and a solution of the spectral relaxation of a minimum normalized cut problem. Minimizing this cost function with respect to the partition leads to a new spectral clustering algorithm. Minimizing with respect to the similarity matrix leads to an algorithm for learning the similarity matrix. We develop a tractable approximation of our cost function that is based on the power method of computing eigenvectors.}
}

EndNote citation:

%0 Report
%A Bach, Francis R.
%A Jordan, Michael I.
%T Learning Spectral Clustering
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1249
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2003/5549.html
%F Bach:CSD-03-1249