您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 2016, Vol. 51 ›› Issue (9): 106-112.doi: 10.6040/j.issn.1671-9352.1.2015.057

• • 上一篇    下一篇

K-Canopy:一种面向话题发现的快速数据切分算法

陈强1,2,杜攀1,陈海强3,包秀国4,刘悦1,程学旗1*   

  1. 1. 中国科学院网络数据科学与技术重点实验室, 中国科学院计算技术研究所, 北京 100190;2. 中国科学院大学, 北京 100190;3.中国信息安全测评中心, 北京 100085;4. 国家计算机网络与信息安全管理中心, 北京 100029
  • 收稿日期:2015-09-25 出版日期:2016-09-20 发布日期:2016-09-23
  • 通讯作者: 程学旗(1971— ),男,博士,研究员,博士生导师,CCF 高级会员,主要研究领域为网络科学、网络与信息安全、互联网搜索与服务.E-mail: cxq@ict.ac.cn E-mail:chenqiang@software.ict.ac.cn
  • 作者简介:陈强(1989— ),男,硕士研究生,主要研究方向为网络数据挖掘、文本挖掘.E-mail:chenqiang@software.ict.ac.cn
  • 基金资助:
    国家重点基础研究发展计划(973计划)项目(2012CB316303,2013CB329602);国家高技术研究发展计划(863计划)项目(2014AA15204);国家自然科学基金青年项目(61303156);国家自然科学基金重点项目(61232010);欧盟FP7-PIRSES-GA-2012-318939;中国科学院重点部署项目(KGZD-EW-T03-2)

K-Canopy:a fast data segmentation algorithm for the topic detection

CHEN Qiang1,2, DU Pan1, CHEN Hai-qiang3, BAO Xiu-guo4, LIU Yue1, CHENG Xue-qi1*   

  1. 1.CAS Key Lab of Network Data Science and Technology, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China;
    2. University of Chinese Academy of Sciences, Beijing 100190, China;
    3. China Information Technology Security Evaluation Center, Beijing 100085, China;
    4. National Computer Network and Information Security Management Center, Beijing 100029, China
  • Received:2015-09-25 Online:2016-09-20 Published:2016-09-23

PDF (PC)

722

摘要： 针对海量数据上的话题发现任务,提出了一种均匀快速的数据预切分算法。在保证一定精度情况下,通过该算法可以按照数据的语义关联强度快速有效地将数据集切分成大小均匀的子数据集,以支持后续的话题发现算法的并行执行。实验表明,所提出的方法能够快速切分海量数据,保持块内数据的语义关联,大大提升话题发现的效率与质量。

关键词: 话题发现, 平衡能力, 数据切分, 海量数据

Abstract: This paper presented a pre-clustering algorithm for tasks of topic detection on big data. To support the parallelization of the successive topic detection task,the proposed algorithm was designed to segment the dataset according to the semantic association among data points as evenly and efficiently as possible. The experimental result shows that our proposed algorithm is effective at segmenting dataset while preserving semantic association inside data blocks, and is helpful for improving the efficiency and effectiveness of topic detection.

Key words: topic detection, balance, big data, data segmentation

中图分类号: 

  • TP391
[1] 黄波.基于向量空间模型和LDA模型相结合的微博客话题发现算法研究[M].成都:西南交通大学出版社,2012. HUANG Bo. Microblog topic detection algorithm based on combination of vector space model and LDA [D]. Chengdu: Southwest Jiaotong University Press, 2012.
[2] 魏明川,朱俊杰,张瑾,等.基于吸收马尔可夫链的子话题发现方法[J]. 中文信息学报,2014,28(1):41-46. WEI Mingchuan, ZHU Junjie, ZHANG Jin, et al. Sub-topic detection method based on absorbing markov chain [J].Journal of Chinese Information Processing, 2014, 28(1):41-46.
[3] 袁继鹏.网络舆情话题演化及话题重要度分析[D].北京:中国科学院计算技术研究所,2012. YUAN Jipeng. Public opinion evolvement and topical importance analysis on web[D]. Beijing: Institute of Computing Technology, CAS, 2012.
[4] MACQUEEN J. Some methods for classification and analysis of multivariate observations[C] //Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability.[S.l.] :[s.n.] , 1967:281-297.
[5] 黄康平.个性化话题推荐[D].北京:中国科学院计算技术研究所,2013. HUANG Kangping. Personalized topic recommendation[D]. Beijing: Institute of Computing Technology, CAS, 2013.
[6] CHAN P K, SCHLAG D F, ZIEN J Y. Spectral K-way ratio-cut partitioning and clustering [J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1994, 13(9):1088-1096.
[7] SHI J, MALIK J. Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(8):888-905.
[8] DING C H Q, HE X, ZHA H, et al. A min-max cut algorithm for graph partitioning and data clustering[C] // Proceedings of the IEEE International Conference on Data Mining. New York: IEEE, 2001.
[9] PAPKA R, ALLAN J. On-line new event detection using single pass clustering TITLE2[R]. Amherst, MA: University of Massachusetts, 1998.
[10] MCCALLUM A, NIGAM K, UNGAR L H. Efficient clustering of high-dimensional data sets with application to reference matching[C] //Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data mining. New York: ACM, 2000:169-178.
[11] MANKU G S, JAIN A, SARMA A D. Detecting near-duplicates for web crawling[C] //Proceedings of the 16th International Conference on World Wide Web. New York: ACM, 2007:141-150.
[1] 龚双双,陈钰枫,徐金安,张玉洁. 基于网络文本的汉语多词表达抽取方法[J]. 山东大学学报（理学版）, 2018, 53(9): 40-48.
[2] 余传明,左宇恒,郭亚静,安璐. 基于复合主题演化模型的作者研究兴趣动态发现[J]. 山东大学学报（理学版）, 2018, 53(9): 23-34.
[3] 严倩,王礼敏,李寿山,周国栋. 结合新闻和评论文本的读者情绪分类方法[J]. 山东大学学报（理学版）, 2018, 53(9): 35-39.
[4] 原伟,唐亮,易绵竹. 基于本体的俄文新闻话题检测设计与实现[J]. 山东大学学报（理学版）, 2018, 53(9): 49-54.
[5] 廖祥文,张凌鹰,魏晶晶,桂林,程学旗,陈国龙. 融合时间特征的社交媒介用户影响力分析[J]. 山东大学学报（理学版）, 2018, 53(3): 1-12.
[6] 余传明,冯博琳,田鑫,安璐. 基于深度表示学习的多语言文本情感分析[J]. 山东大学学报（理学版）, 2018, 53(3): 13-23.
[7] 张军,李竞飞,张瑞,阮兴茂,张烁. 基于网络有效阻抗的社区发现算法[J]. 山东大学学报（理学版）, 2018, 53(3): 24-29.
[8] 庞博,刘远超. 融合pointwise及深度学习方法的篇章排序[J]. 山东大学学报（理学版）, 2018, 53(3): 30-35.
[9] 陈鑫,薛云,卢昕,李万理,赵洪雅,胡晓晖. 基于保序子矩阵和频繁序列模式挖掘的文本情感特征提取方法[J]. 山东大学学报（理学版）, 2018, 53(3): 36-45.
[10] 王彤,马延周,易绵竹. 基于DTW的俄语短指令语音识别[J]. 山东大学学报（理学版）, 2017, 52(11): 29-36.
[11] 张晓东,董唯光,汤旻安,郭俊锋,梁金平. 压缩感知中基于广义Jaccard系数的gOMP重构算法[J]. 山东大学学报（理学版）, 2017, 52(11): 23-28.
[12] 孙建东,顾秀森,李彦,徐蔚然. 基于COAE2016数据集的中文实体关系抽取算法研究[J]. 山东大学学报（理学版）, 2017, 52(9): 7-12.
[13] 王凯,洪宇,邱盈盈,王剑,姚建民,周国栋. 一种查询意图边界检测方法研究[J]. 山东大学学报（理学版）, 2017, 52(9): 13-18.
[14] 张帆,罗成,刘奕群,张敏,马少平. 异质搜索环境下的用户偏好性预测方法研究[J]. 山东大学学报（理学版）, 2017, 52(9): 26-34.
[15] 杨艳,徐冰,杨沐昀,赵晶晶. 一种基于联合深度学习模型的情感分类方法[J]. 山东大学学报（理学版）, 2017, 52(9): 19-25.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发