基于AC-Trie的在线社交网络文本流热点要素抽取

doi:10.3969/j.issn.0372-2112.2016.10.026

电子学报 ›› 2016, Vol. 44 ›› Issue (10): 2466-2470.DOI: 10.3969/j.issn.0372-2112.2016.10.026

基于AC-Trie的在线社交网络文本流热点要素抽取

黄九鸣, 吴泉源, 张圣栋, 贾焰, 刘东, 周斌

国防科学技术大学计算机学院, 湖南长沙 410073

收稿日期:2015-02-15 修回日期:2015-08-14 出版日期:2016-10-25
- 作者简介:
- 黄九鸣,男,1981年生于福建安溪.博士、中国人民解放军国防科学技术大学助理研究员.研究方向为Web挖掘、大数据、分布式计算和社交网络分析.E-mail:jiuming.huang@qq.com;吴泉源,男,1942年生于上海.中国人民解放军国防科学技术大学教授、博士生导师.研究方向为人工智能和分布式计算.
- 基金资助:
- 国家973重点基础研究发展计划 (No.2013CB329601）; 国家自然科学基金 (No.61502517）

Mining Hot Phrases on Social Network Text Streams Based on AC-Trie

HUANG Jiu-ming, WU Quan-yuan, ZHANG Sheng-dong, JIA Yan, LIU Dong, ZHOU Bin

School of Computer, National University of Defense Technology, Changsha, Hunan 410073, China

Received:2015-02-15 Revised:2015-08-14 Online:2016-10-25 Published:2016-10-25
- Supported by:
- National Program on Key Basic Research Project of China (973 Program) (No.2013CB329601); National Natural Science Foundation of China (No.61502517)

摘要/Abstract

摘要：

在线社交网络文本流中的热点短语能反映文本流中隐含的热点话题和突发事件.本文提出了一种无需分词并能支持多种热度度量函数的热点短语挖掘技术.首先用文本流的某个典型时段采样得到候选短语，构建AC-Trie前缀树.然后，基于该前缀树，单遍扫描后续的文本流，将候选短语的历史出现频率记录在Trie相应节点上，从而支持多种基于历史频率的热度计算方法.此外，为及时发现新的热点短语并减少AC-Trie的构建次数，本文通过分析Trie树各节点上的遗漏短语频率，动态确定候选短语的更新时机.新浪微博数据集上的实验验证了本文方法的有效性（准确率达89%）和高效性（时空开销仅为基准算法的2%）.

关键词: 文本流, 热点短语, AC-Trie, 文本挖掘, 在线社交网络

Abstract:

The hot phrases in the social network text streams can reflect the hidden hot topics and sudden events.This paper proposes a hot phrase mining technology which can support various hot degree measures without word segmentation.We first construct an AC-Trie using the candidate phrases gathered from text streams.Based on such AC-Trie,we record the historical occurrence frequency of phrases on the Trie by scanning the following streams in single-pass.Furthermore,the AC-Trie needs to be reconstructed using the new samples in the text stream because of the evolution of hot phrases.Thus,we start the reconstruction dynamically according to estimating the occurrence frequency of the missed phrases.The experiments on the Sina micro-blog show that our approach is effective (precision of 89%) and efficient (overhead is 2% of naïve approach).

Key words: text stream, hot phrase, AC-Trie, text mining, micro-blog

中图分类号:

TP391

黄九鸣, 吴泉源, 张圣栋, 等. 基于AC-Trie的在线社交网络文本流热点要素抽取[J]. 电子学报, 2016, 44(10): 2466-2470.

HUANG Jiu-ming, WU Quan-yuan, ZHANG Sheng-dong, et al. Mining Hot Phrases on Social Network Text Streams Based on AC-Trie[J]. Acta Electronica Sinica, 2016, 44(10): 2466-2470.

参考文献

[1] Calders T,Dexters N,Goethals B.Mining frequent itemsets in a stream[A].Seventh IEEE International Conference on Data Mining[C].Omaha,Nebraska:IEEE,2007.83-92.
[2] Yuan Z,Jia Y,Yang S.Online burst detection over high speed short text streams[A].Computational Science-ICCS 2007[C].Heidelberg,Berlin:Springer,2007.717-725.
[3] Fujiki T,Nanno T,Suzuki Y,Okumura M.Identification of bursts in a document stream[A].First International Workshop on Knowledge Discovery in Data Streams (in conjunction with ECML/PKDD 2004)[C].Pisa,Italy,2004.55-64.
[4] Kleinberg J.Bursty and hierarchical structure in streams[J].Data Mining and Knowledge Discovery,2003,7(4):373-397.
[5] Ahonen-Myka H.Discovery of frequent word sequences in text[A].Pattern Detection and Discovery[M].Berlin Heidelberg:Springer,2002.180-189.
[6] Han J,Pei J,Yin Y.Mining frequent patterns without candidate generation[A].ACM SIGMOD Record[C].Dallas,Texas:ACM,2000.29(2):1-12.
[7] Wong R C W,Fu A W C.Mining top-K frequent itemsets from data streams[J].Data Mining and Knowledge Discovery,2006,13(2):193-217.
[8] Lee D,Lee W.Finding maximal frequent itemsets over online data streams adaptively[A].Fifth IEEE International Conference on Data Mining[C].Houston,Texas:IEEE,2005.8.
[9] Yu J X,Chong Z,Lu H,et al.False positive or false negative:mining frequent itemsets from high speed transactional data streams[A].Proceedings of the Thirtieth International Conference on Very Large Data Bases (VLDB Endowment)[C].Toronto,2004.Volume 30:204-215.
[10] Thanh Lam H,Calders T.Mining top-k frequent items in a data stream with flexible sliding windows[A].Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Washington,DC:ACM,2010.283-292.
[11] Zhou G,Zou H C,Xiong X B,et al.MB-singlepass:microblog topic detection based on combined similarity[J].Computer Science,2012,39(10):198-202.
[12] Liu G,Xu X,Zhu Y,et al.An improved latent dirichlet allocation model for hot topic extraction[A].IEEE Fourth International Conference on Big Data and Cloud Computing (BdCloud)[C].Sydney:IEEE,2014.470-476.

基于AC-Trie的在线社交网络文本流热点要素抽取

Mining Hot Phrases on Social Network Text Streams Based on AC-Trie

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

[1]	皮德常, 吴致远, 曹建军. 基于知识图谱表示学习的谣言早期检测方法[J]. 电子学报, 2023, 51(2): 385-395.
[2]	黄名选. 关联模式挖掘与词向量学习融合的伪相关反馈查询扩展[J]. 电子学报, 2021, 49(7): 1305-1313.
[3]	黄名选, 蒋曹清. 基于项权值排序挖掘的跨语言查询扩展[J]. 电子学报, 2020, 48(3): 568-576.
[4]	马慧芳, 刘文, 李志欣, 蔺想红. 融合耦合距离区分度和强类别特征的短文本相似度计算方法[J]. 电子学报, 2019, 47(6): 1331-1336.
[5]	黄名选, 蒋曹清. 基于完全加权正负关联模式挖掘的越-英跨语言查询译后扩展[J]. 电子学报, 2018, 46(12): 3029-3036.
[6]	许文文, 时鹏, 于留宝, 胡长军. 一种在线社交网络的自适应观点引导模型及实现[J]. 电子学报, 2016, 44(7): 1714-1720.