On clusterings: Good, bad and spectral

被引：435

作者：

Kannan, R ^{[1
]}

Vempala, S

Vetta, A

机构：

[1] Yale Univ, Dept Comp Sci, New Haven, CT 06511 USA

[2] MIT, Dept Math, Cambridge, MA 02139 USA

来源：

JOURNAL OF THE ACM | 2004年 / 51卷 / 03期

关键词：

algorithms; theory; clustering; graph algorithms; spectral methods;

D O I：

10.1145/990308.990313

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We motivate and develop a natural bicriteria measure for assessing the quality of a clustering that avoids the drawbacks of existing measures. A simple recursive heuristic is shown to have poly-logarithmic worst-case guarantees under the new measure. The main result of the article is the analysis of a popular spectral algorithm. One variant of spectral clustering turns out to have effective worst-case guarantees; another finds a "good" clustering, if one exists.

引用

页码：497 / 515

页数：19

共 19 条

[1] Spectral partitioning with multiple eigenvectors [J].

Alpert, CJ ;

Kahng, AB ;

Yao, SZ .

DISCRETE APPLIED MATHEMATICS, 1999, 90 (1-3) :3-26

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[3]

[Anonymous], MITLCSTR906

[4]

Azar Y., 2001, P 33 ANN ACM S THEOR, P619, DOI [10.1145/380752.380859, DOI 10.1145/380752.380859]

[5]

Benczur A. A., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P47, DOI 10.1145/237814.237827

[6]

Charikar M., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P1, DOI 10.1145/301250.301257

[7]

CHARIKAR M, 1997, P 29 ANN ACM S THEOR, P626, DOI DOI 10.1145/258533.258657

[8]

DHILLON I, 2001, P 7 ACM C KNOWL DISC

[9]

Drineas P, 1999, PROCEEDINGS OF THE TENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P291

[10] A SIMPLE HEURISTIC FOR THE P-CENTER PROBLEM [J].

DYER, ME ;

FRIEZE, AM .

OPERATIONS RESEARCH LETTERS, 1985, 3 (06) :285-288

← 1 2 →