可并行中文同主题词聚类新算法

doi:10.13190/jbupt.200904.122.shenxy

北京邮电大学学报 ›› 2009, Vol. 32 ›› Issue (4): 122-127.doi: 10.13190/jbupt.200904.122.shenxy

可并行中文同主题词聚类新算法

沈筱彦陈俊亮孟祥武张玉洁

北京邮电大学网络与交换技术国家重点实验室北京邮电大学网络与交换技术国家重点实验室北京邮电大学网络与交换技术国家重点实验室

收稿日期:2008-11-20 修回日期:2009-06-01 出版日期:2009-08-28 发布日期:2009-08-28
通讯作者: 沈筱彦

A Parallable Algorithm for Chinese CoTopic Words Clustering

Jun-Liang Chen Xiang-Wu Meng

Received:2008-11-20 Revised:2009-06-01 Online:2009-08-28 Published:2009-08-28

摘要/Abstract

摘要：

提出了一种高效的自动按照主题对中文词进行聚类的算法.该算法利用顿号(、)切分抽取语料库句子中的并列中文词，并以抽取出的中文词为节点构建一个共引用图; 然后对每个中文词节点产生若干个locality sensitive Hashing (LSH)签名组合; 最后将至少有1个相同LSH签名组合的任意2个中文词标记为同一个主题类.实验表明,该算法运算速度快，且易并行实现,在海量语料库的支持下,执行效率高,聚类效果较好.

关键词: 中文词聚类, 共引用图, LSH签名, 连通分支, 并行化

Abstract:

A simple but powerful algorithm for automatically clustering Chinese cotopic words is presented. The method first uses punctuation ‘、’ to split and extract paratactic Chinese words within sentences from a corpus and constructs a cocitation graph by treating Chinese words as nodes. Second, the method generates several locality sensitive Hashing (LSH) signature combinations for each node in the cocitation graph. Those nodes shared at least one LSH signature combination, are grouped together and most of them may belong to the same topic. The main advantages of the algorithm are the fast speed of calculation and high convenience of implementation in parallel. Experimental results indicate the high efficiency and good clustering effect.

Key words: Chinese word clustering, co-citation graph, connected component, LSH signature, parallable

沈筱彦陈俊亮孟祥武张玉洁. 可并行中文同主题词聚类新算法[J]. 北京邮电大学学报, 2009, 32(4): 122-127.

Jun-Liang Chen Xiang-Wu Meng. A Parallable Algorithm for Chinese CoTopic Words Clustering[J]. JOURNAL OF BEIJING UNIVERSITY OF POSTS AND TELECOM, 2009, 32(4): 122-127.

参考文献

[1] 胡和平, 曾庆锐, 路松峰. 中文词聚类研究[J]. 计算机工程与科学, 2006, 28(1): 122-124. Hu Heping, Zeng Qingrui, Lu Songfeng. Research on Chinese word clustering[J]. Computer Engineering and Science, 2006, 28(1): 122-124.
[2] Wu Fazhou, Su Hao, Zhou Ming, et al. Use web to extend synonym for new Chinese words//NDBC 2006. Guang Zhou: , 2006.
[3] 梅翔, 孟祥武, 陈俊亮, 等. 一种基于语义关联的查询优化方法[J]. 北京邮电大学学报, 2006, 29(6): 107-110. Mei Xiang, Meng Xiangwu, Chen Junliang, et al. A query refinement scheme based on semantic association ranking[J]. Beijing University of Posts and Telecommunications, 2006, 29(6): 107-110.
[4] Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Physical Review E-Statistical, Nonlinear, and Soft Matter Physics, 2004, 70(62): 066-111.
[5] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(22): 026-113.
[6] Du N, Wang B, Wu B. Community detection in complex networks[J]. Journal of Computer Science and Technology, 2008, 23(4): 672-683.
[7] Gibson D, Kumar R, Tomkins A. Discovering large dense subgraphs in massive graphs//The 31st International Conference on Very Large Data Bases. New York: , 2005.
[8] Broder A Z, Charikar M, Frieze A M, et al. Min-wise independent permutations//The Annual ACM Symposium on Theory of Computing. New York: ACM, 1998: 327-336.
[9] Broder A Z, Steven C G, Mark S M, et al. Syntactic clustering of the web[J]. Computer Networks and ISDN Systems Archive, 1997, 29(8): 1157-1166.
[10] Indyk P R, Motvani. Approximate nearest neighbors: towards removing the curse of dimensionality//STOC' 98. Dollas: ACM, 1998: 604-613.
[11] Dean J, Ghemawat J. Map reduce simplified data processing on large clusters//The 6th Symposium on Operating Systems Design and Implementation. San Francisco: ACM, 2004: 10-20.
[12] Aggarwal G, Datar M, Rajagopalan S, et al. On the streaming model augmented with a sorting primitive//Annual IEEE Symposium on Foundations of Computer Science. Los Alamitos: IEEE, 2004: 540-549.

可并行中文同主题词聚类新算法

A Parallable Algorithm for Chinese CoTopic Words Clustering

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价