### Francis R. Bach and Michael I. Jordan

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-03-1249

June 2003

### http://www2.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://www2.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://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5549.html %F Bach:CSD-03-1249