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 条

[11] Fast Monte-Carlo algorithms for finding low-rank approximations [J].

Frieze, A ;

Kannan, R ;

Vempala, S .

39TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 1998, :370-378

[12]

Indyk P., 1999, 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), P154, DOI 10.1109/SFFCS.1999.814587

[13] Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation [J].

Jain, K ;

Vazirani, VV .

JOURNAL OF THE ACM, 2001, 48 (02) :274-296

[14] Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms [J].

Leighton, T ;

Rao, S .

JOURNAL OF THE ACM, 1999, 46 (06) :787-832

[15] Latent semantic indexing: A probabilistic analysis [J].

Papadimitriou, CH ;

Raghavan, P ;

Tamaki, H ;

Vempala, S .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2000, 61 (02) :217-235

[16] Normalized cuts and image segmentation [J].

Shi, JB ;

Malik, J .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2000, 22 (08) :888-905

[17] APPROXIMATE COUNTING, UNIFORM GENERATION AND RAPIDLY MIXING MARKOV-CHAINS [J].

SINCLAIR, A ;

JERRUM, M .

INFORMATION AND COMPUTATION, 1989, 82 (01) :93-133

[18] ERROR AND PERTURBATION BOUNDS FOR SUBSPACES ASSOCIATED WITH CERTAIN EIGENVALUE PROBLEMS [J].

STEWART, GW .

SIAM REVIEW, 1973, 15 (04) :727-764

[19]

Weiss Y., 1999, Proceedings of the Seventh IEEE International Conference on Computer Vision, P975, DOI 10.1109/ICCV.1999.790354

← 1 2 →