Novel text clustering approach based on R-Grams

doi:10.11772/j.issn.1001-9081.2015.11.3130

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (11): 3130-3134.DOI: 10.11772/j.issn.1001-9081.2015.11.3130

• DPCS 2015 Paper • Previous Articles Next Articles

Novel text clustering approach based on R-Grams

WANG Xianming^1,2, GU Qiong^3,4, HU Zhiwen⁵

1. Oujiang College, Wenzhou University, Wenzhou Zhejiang 325035, China;
2. Network Research Institute of Wenzhou, Wenzhou Zhejiang 325035, China;
3. School of Mathematics and Computer Science, Hubei University of Arts and Science, Xiangyang Hubei 441053, China;
4. Institute of Logic and Intelligence, Southwest University, Chongqing 400715, China;
5. College of New Media, Zhejiang University of Media and Communications, Hangzhou Zhejiang 310018, China

Received:2015-06-17 Revised:2015-07-15 Published:2015-11-13

基于R-Grams的文本聚类方法

王贤明^1,2, 谷琼^3,4, 胡智文⁵

1. 温州大学瓯江学院, 浙江温州 325035;
2. 温州信息化研究中心, 浙江温州 325035;
3. 湖北文理学院数学与计算机科学学院, 湖北襄阳 441053;
4. 西南大学逻辑与智能研究中心, 重庆 400715;
5. 浙江传媒学院新媒体学院, 杭州 310018

通讯作者: 谷琼(1973-),女,湖北荆门人,副教授,博士, CCF会员,主要研究方向:Web数据挖掘、网络舆情.
作者简介:王贤明(1979-),男,湖北黄冈人,讲师,硕士,主要研究方向:Web数据挖掘、网络舆情; 胡智文(1975-),男,湖北黄冈人,副教授,博士,主要研究方向:新媒体、网络数据挖掘.
基金资助:
浙江省自然科学基金资助项目(LY13F010005); 教育部人文社会科学研究项目(15YJAZH015); 湖北省科技支撑计划软科学项目(2015BDH109); 温州市科技计划项目(R20130021).

Abstract

Abstract: Focusing on the issue that the clustering accuracy rate and recall rate are difficult to balance in traditional text clustering algorithms, a clustering approach based on the R-Grams text similarity computing algorithm was proposed. Firstly, the clustered documents were sorted in descending order; secondly, the symbolic documents were identified and then initial clustering results were achieved by using an R-Grams-based similarity computing algorithm; finally, the final clustering results were completed by combining the initial clustering. The experimental results show that the proposed approach can flexibly regulate the clustering results by adjusting the clustering threshold parameter to satisfy different demands and the optimal parameter is about 15. With the increasing of the clustering threshold, the clustering accuracies increase, and the recalls increase at first, then decrease. In addition, the approach is free from time-consuming processing procedures such as word segmentation and feature extraction and can be easily implemented.

Key words: text, clustering, random, R-Grams

摘要： 针对传统文本聚类中存在着聚类准确率和召回率难以平衡等问题,提出了一种基于R-Grams文本相似度计算方法的文本聚类方法.该方法首先通过将待聚类文档降序排列,其次采用R-Grams文本相似度算法计算文本之间的相似度并根据相似度实现各聚类标志文档的确定并完成初始聚类,最后通过对初始聚类结果进行聚类合并完成最终聚类.实验结果表明:聚类结果可以通过聚类阈值灵活调整以适应不同的需求,最佳聚类阈值为15左右.随着聚类阈值的增大,各聚类准确率增大,召回率呈现先增后降的趋势.此外,该聚类方法避免了大量的分词、特征提取等繁琐处理,实现简单.

关键词: 文本, 聚类, 随机, R-Grams

CLC Number:

TP391

WANG Xianming, GU Qiong, HU Zhiwen. Novel text clustering approach based on R-Grams[J]. Journal of Computer Applications, 2015, 35(11): 3130-3134.

王贤明, 谷琼, 胡智文. 基于R-Grams的文本聚类方法[J]. 计算机应用, 2015, 35(11): 3130-3134.

References

[1] MACQUEEN J B. Some methods for classification and analysis of multivariate observations[C]// Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley: University of California Press, 1967:281-297.
[2] ZHANG T, RAMAKRISHNAN R, LIVNY M. BIRCH: an efficient data clustering method for very large databases[J]. Data Mining and Knowledge Discovery, 1997,1(2):141-182.
[3] ESTER M, KRIEGEL H P, SANDER J, et al. A density-based algorithm for discovering clusters in large spatial databases with noise [C]// Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Menlo Park: AAAI Press,1996:226-231.
[4] ANKERST M, BREUNIG M, KRIEGEL H P, et al. OPTICS: ordering points to identify the clustering structure[C]// Proceedings of the ACM SIGMOD 1999 International Conference on Management of Data. New York: ACM, 1999: 49-60.
[5] ZENG Y, XU H, BAI S. OPTICS-plus for text clustering[J]. Journal of Chinese Information Processing, 2008,22(1):51-55,60. (曾依灵,许洪波,白硕.改进的OPTICS算法及其在文本聚类中的应用[J].中文信息学报,2008,22(1):51-55,60.)
[6] HYOTYNIEMI H. Text document classification with self-organizing maps[C]// Proceedings of Finnish Artificial Intelligence Conference Genes, Nets and Symbols. Vaasa: the Finnish Artificial Intelligence Society and University of Vaasa, 1996:64-72.
[7] LIU Y, WU C, LIU M. Research of fast SOM clustering for text information[J]. Knowledge-Based Systems,2011,38(8): 9325-9333.
[8] HE T, DAI W, JIAO C. Research of text clustering based on hybrid parallel genetic algorithm[J].Journal of Chinese Information Processing, 2007,21(4):55-60. (何婷婷,戴文华,焦翠珍.基于混合并行遗传算法的文本聚类研究[J].中文信息学报,2007,21(4):55-60.)
[9] JAMAL A N, IRAKLIS V, ASIM K, et al. Semantic smoothing for text clustering[J]. Knowledge-Based Systems,2013,54(4): 216-229.
[10] PENG J, YANG D, TANG S,et al. A novel text clustering algorithm based on inner product space model of semantic[J]. Chinese Journal of Computers,2007,30(8):1354-1363.(彭京,杨冬青,唐世渭,等.一种基于语义内积空间模型的文本聚类算法[J].计算机学报,2007,30(8):1354-1363.)
[11] LUO N, ZUO W, YUAN F, et al.Using ontology semantics to improve text documents clustering[J].Journal of Southeast University: English Edition,2006,22(3):370-374.
[12] ZHU H, ZUO W, HE F,et al. A novel text clustering method based on Ontology[J]. Journal of Jilin University: Science Edition,2010, 48(2):277-283.(朱会峰,左万利,赫枫龄,等.一种基于本体的文本聚类方法[J].吉林大学学报:理学版,2010,48(2):277-283.)
[13] YAN Y, CHEN L, TJHI W C. Fuzzy semi-supervised co-clustering for text documents[J].Fuzzy Sets and Systems,2013,215(3): 74-89.
[14] WEI S, JIU Z, SOON C P. Fuzzy control GA with a novel hybrid semantic similarity strategy for text clustering[J]. Information Sciences,2014,273(3): 156-170.
[15] XU S, LU Z, GU G. Spectral clustering algorithms for document cluster ensemble problem[J]. Journal on Communications, 2010, 31(6):58-66. (徐森,卢志茂,顾国昌.使用谱聚类算法解决文本聚类集成问题[J].通信学报,2010,31(6):58-66.)
[16] ZOU Z, TIAN S, YU L, et al. An improved Uyghur Web text clustering based on suffix tree[J].Journal of Chinese Information Processing,2013,27(2):118-126.(邹志华,田生伟,禹龙,等.改进的维吾尔语Web文本后缀树聚类[J].中文信息学报,2013,27(2):118-126.)
[17] YAO M, PI D, CONG X. Chinese text clustering algorithm based k-means[J]. Physics Procedia,2012, 33: 301-307.
[18] WANG M, FU J, LUO Y, et al. Two-stage text clustering based on collaborative clustering[J]. Pattern Recognition and Artificial Intelligence, 2009, 22(6):848-853.(王明文,付剑波,罗远胜,等.基于协同聚类的两阶段文本聚类方法[J].模式识别与人工智能,2009,22(6):848-853.)
[19] BHARTI K K, SINGH P K. A three-stage unsupervised dimension reduction method for text clustering[J]. Journal of Computational Science,2014,5(2):156-169.
[20] GONG L, ZENG J, ZHANG S. Text stream clustering algorithm based on adaptive feature selection[J].Expert Systems with Applications,2011,38(3):1393-1399.
[21] WANG X, HU Z, GU Q. A novel approach for text similarity computing based on random n-Grams [J]. Journal of the China Society for Scientific and Technical Information,2013,32(7): 716-723.(王贤明,胡智文,谷琼.一种基于随机n-Grams的文本相似度计算方法[J].情报学报,2013,32(7): 716-723.)
[22] FUNG B C M,WANG K, ESTER M. Hierarchical document clustering using frequent itemsets[C]// Proceedings of the 3rd SIAM International Conference on Data Mining. Piscataway: IEEE,2003: 59-70.
[23] ZHANG W, YOSHIDA T, TANG X,et al. Text clustering using frequent itemsets[J]. Knowledge-Based Systems,2010,23(5):379-388.

Novel text clustering approach based on R-Grams

基于R-Grams的文本聚类方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	LIU Xiaoguang, JIN Shaokang, WEI Zihui, LIANG Tie, WANG Hongrui, LIU Xiuling. Real-time fall detection method based on threshold and extremely randomized tree [J]. Journal of Computer Applications, 2021, 41(9): 2761-2766.
[2]	XU Jianglang, LI Linyan, WAN Xinjun, HU Fuyuan. Indoor scene recognition method combined with object detection [J]. Journal of Computer Applications, 2021, 41(9): 2720-2725.
[3]	CHEN Hengheng, NI Zhiwei, ZHU Xuhui, JIN Yuanyuan, CHEN Qian. Differential privacy high-dimensional data publishing method via clustering analysis [J]. Journal of Computer Applications, 2021, 41(9): 2578-2585.
[4]	TANG Andi, HAN Tong, XU Dengwu, XIE lei. Chaotic elite Harris hawks optimization algorithm [J]. Journal of Computer Applications, 2021, 41(8): 2265-2272.
[5]	ZHU Cheng, ZHAO Xiaoqi, ZHAO Liping, JIAO Yuhong, ZHU Yafei, CHENG Jianying, ZHOU Wei, TAN Ying. Classification of functional magnetic resonance imaging data based on semi-supervised feature selection by spectral clustering [J]. Journal of Computer Applications, 2021, 41(8): 2288-2293.
[6]	YANG Rui, QIAN Xiaojun, SUN Zhenqiang, XU Zhen. Hybrid aerial image segmentation algorithm based on multi-region feature fusion for natural scene [J]. Journal of Computer Applications, 2021, 41(8): 2445-2452.
[7]	ZENG Xiangyin, ZHENG Bochuan, LIU Dan. Detection of left and right railway tracks based on deep convolutional neural network and clustering [J]. Journal of Computer Applications, 2021, 41(8): 2324-2329.
[8]	LI Hui, WU Chuansheng, LIU Jun, LIU Wen. Image smoothing method based on gradient surface area and sparsity constraints [J]. Journal of Computer Applications, 2021, 41(7): 2039-2047.
[9]	LU Guoqing, SUN Hao. Two-dimensional mapping of swarm robot based on random walk [J]. Journal of Computer Applications, 2021, 41(7): 2121-2127.
[10]	ZHANG Yang, JIANG Minghu. Authorship identification of text based on attention mechanism [J]. Journal of Computer Applications, 2021, 41(7): 1897-1901.
[11]	HUANG Shaowei, HUANG Wanlin, LEI Runlong, MAO Xuesong. Simultaneous measurement of range and speed based on pulse position and amplitude modulation [J]. Journal of Computer Applications, 2021, 41(7): 2145-2149.
[12]	YU Dunhui, ZHANG Luyi, ZHANG Xiaoxiao, MAO Liang. User recommendation method of cross-platform based on knowledge graph and restart random walk [J]. Journal of Computer Applications, 2021, 41(7): 1871-1877.
[13]	LI Xiang, WANG Weibing, SHANG Xueda. Application of Transformer optimized by pointer generator network and coverage loss in field of abstractive text summarization [J]. Journal of Computer Applications, 2021, 41(6): 1647-1651.
[14]	XIE Yu, JIANG Yu, LONG Chaoqi. Extended isolation forest algorithm based on random subspace [J]. Journal of Computer Applications, 2021, 41(6): 1679-1685.
[15]	ZHANG Yang, DONG Shicheng. Intelligent recommendation method for lock mechanism in concurrent program [J]. Journal of Computer Applications, 2021, 41(6): 1597-1603.