Towards effective document clustering:: A constrained K-means based approach

被引:49
作者
Hu, Guobiao [1 ,2 ]
Zhou, Shuigeng [1 ,2 ]
Guan, Jihong [3 ]
Hu, Xiaohua [4 ]
机构
[1] Fudan Univ, Dept Comp Sci & Engn, Shanghai 200433, Peoples R China
[2] Fudan Univ, Shanghai Key Lab Intelligent Informat Proc, Shanghai 200433, Peoples R China
[3] Tongji Univ, Dept Comp Sci & Technol, Shanghai 200092, Peoples R China
[4] Drexel Univ, Coll Informat Sci & Technol, Philadelphia, PA 19104 USA
基金
中国国家自然科学基金;
关键词
document clustering; semi-supervised learning; spectral relaxation; clustering with prior knowledge;
D O I
10.1016/j.ipm.2008.03.001
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 [计算机科学与技术];
摘要
Document clustering is an important tool for document collection organization and browsing. In real applications, some limited knowledge about cluster membership of a small number of documents is often available, such as some pairs of documents belonging to the same cluster. This kind of prior knowledge can be served as constraints for the clustering process. We integrate the constraints into the trace formulation of the sum of square Euclidean distance function of K-means. Then,the combined criterion function is transformed into trace maximization, which is further optimized by eigen-decomposition. Our experimental evaluation shows that the proposed semi-supervised clustering method can achieve better performance, compared to three existing methods. (C) 2008 Elsevier Ltd. All rights reserved.
引用
收藏
页码:1397 / 1409
页数:13
相关论文
共 34 条
[1]
Allan J, 2002, TOPIC DETECTION TRAC
[2]
[Anonymous], 1999, MATRICHNYE VYCHISLEN
[3]
[Anonymous], 2001, ICML, DOI DOI 10.1109/TPAMI.2002.1017616
[4]
[Anonymous], P 10 EUR C PRINC PRA
[5]
[Anonymous], 2002, J. Mach. Learn. Res
[6]
[Anonymous], INT C KNOWL DISC DAT, DOI DOI 10.1145/1014052.1014062
[7]
Basu S, 2004, SIAM PROC S, P333
[8]
Basu S., 2002, P 19 INT C MACHINE L, P19, DOI [10.5555/645531.656012, DOI 10.5555/645531.656012]
[9]
Principal direction divisive partitioning [J].
Boley, D .
DATA MINING AND KNOWLEDGE DISCOVERY, 1998, 2 (04) :325-344
[10]
SPECTRAL K-WAY RATIO-CUT PARTITIONING AND CLUSTERING [J].
CHAN, PK ;
SCHLAG, MDF ;
ZIEN, JY .
IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1994, 13 (09) :1088-1096