On Spectral Clustering: Analysis and an algorithm

On Spectral Clustering: Analysis and an algorithm. Ng, A. Y, Jordan, M. I, & Weiss, Y. In Advances in Neural Information Processing Systems 14, volume 14, pages 849–856, 2001.

Paper abstract bibtex

Despite many empirical successes of spectral clustering methods\textbar algorithms that cluster points using eigenvectors of matrices derived from the distances between the points\textbarthere are several unresolved issues. First, there is a wide variety of algorithms that use the eigenvectors in slightly dierent ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems. 1

@inproceedings{Ng:2001:NIPS,
	title = {On {Spectral} {Clustering}: {Analysis} and an algorithm},
	volume = {14},
	url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.8100},
	abstract = {Despite many empirical successes of spectral clustering methods{\textbar} algorithms that cluster points using eigenvectors of matrices derived from the distances between the points{\textbar}there are several unresolved issues. First, there is a wide variety of algorithms that use the eigenvectors in slightly dierent ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems. 1},
	booktitle = {Advances in {Neural} {Information} {Processing} {Systems} 14},
	author = {Ng, Andrew Y and Jordan, Michael I and Weiss, Yair},
	year = {2001},
	keywords = {clustering, spectral},
	pages = {849--856},
}

Downloads: 0

{"_id":"iGHSoKFHmy7766pxd","bibbaseid":"ng-jordan-weiss-onspectralclusteringanalysisandanalgorithm-2001","downloads":0,"creationDate":"2018-01-22T16:01:07.099Z","title":"On Spectral Clustering: Analysis and an algorithm","author_short":["Ng, A. Y","Jordan, M. I","Weiss, Y."],"year":2001,"bibtype":"inproceedings","biburl":"https://bibbase.org/zotero/girdhar","bibdata":{"bibtype":"inproceedings","type":"inproceedings","title":"On Spectral Clustering: Analysis and an algorithm","volume":"14","url":"http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.8100","abstract":"Despite many empirical successes of spectral clustering methods\\textbar algorithms that cluster points using eigenvectors of matrices derived from the distances between the points\\textbarthere are several unresolved issues. First, there is a wide variety of algorithms that use the eigenvectors in slightly dierent ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems. 1","booktitle":"Advances in Neural Information Processing Systems 14","author":[{"propositions":[],"lastnames":["Ng"],"firstnames":["Andrew","Y"],"suffixes":[]},{"propositions":[],"lastnames":["Jordan"],"firstnames":["Michael","I"],"suffixes":[]},{"propositions":[],"lastnames":["Weiss"],"firstnames":["Yair"],"suffixes":[]}],"year":"2001","keywords":"clustering, spectral","pages":"849–856","bibtex":"@inproceedings{Ng:2001:NIPS,\n\ttitle = {On {Spectral} {Clustering}: {Analysis} and an algorithm},\n\tvolume = {14},\n\turl = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.8100},\n\tabstract = {Despite many empirical successes of spectral clustering methods{\\textbar} algorithms that cluster points using eigenvectors of matrices derived from the distances between the points{\\textbar}there are several unresolved issues. First, there is a wide variety of algorithms that use the eigenvectors in slightly dierent ways. Second, many of these algorithms have no proof that they will actually compute a reasonable clustering. In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation theory, we analyze the algorithm, and give conditions under which it can be expected to do well. We also show surprisingly good experimental results on a number of challenging clustering problems. 1},\n\tbooktitle = {Advances in {Neural} {Information} {Processing} {Systems} 14},\n\tauthor = {Ng, Andrew Y and Jordan, Michael I and Weiss, Yair},\n\tyear = {2001},\n\tkeywords = {clustering, spectral},\n\tpages = {849--856},\n}\n\n","author_short":["Ng, A. Y","Jordan, M. I","Weiss, Y."],"key":"Ng:2001:NIPS","id":"Ng:2001:NIPS","bibbaseid":"ng-jordan-weiss-onspectralclusteringanalysisandanalgorithm-2001","role":"author","urls":{"Paper":"http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.8100"},"keyword":["clustering","spectral"],"metadata":{"authorlinks":{}},"html":""},"search_terms":["spectral","clustering","analysis","algorithm","ng","jordan","weiss"],"keywords":["clustering","spectral"],"authorIDs":[],"dataSources":["C5FtkvWWggFfMJTFX","XFrKPG99s5t3W7xuW"]}