连续时间区间内的频繁词序列挖掘算法

doi:10.19678/j.issn.1000-3428.0060269

摘要/Abstract

摘要： 查询文本中频繁出现的短语可快速掌握文本内容，然而传统频繁词序列挖掘算法面向挖掘任务时的时间复杂度较高，无法满足频繁更换查询条件及快速获得反馈的查询需求。利用基于频率树的快速频繁词序列挖掘算法（TS_Mining），在保持后缀树线性构造时间的情况下实现文本集合中频繁词序列的查询，并采用树型索引结构避免多次扫描文本集合，降低算法时间复杂度。针对连续时间区间内的频繁词序列查询问题，提出改进的剪枝挖掘算法（TS_Pruning），通过减少频率树的扫描范围进一步提高挖掘效率。实验结果表明，TS_Mining与TS_Pruning算法的运行时间相比经典Apriori挖掘算法约减少了2个数量级，具有更高的频繁词序列挖掘效率。

关键词: 频繁词序列, 后缀树, 数据挖掘, 频繁项集, 热点话题检测

Abstract: Mining frequent phrases in a text assists in the quick understanding of the content, but traditional algorithms for frequent word sequence mining usually have high time complexity in mining tasks, and fail to deal with frequently changing query criteria or respond to queries in real time.This paper gives an algorithm for rapidly mining frequent word sequences based on frequency tree, called TS_Mining.The algorithm can implement the query of the frequent word sequence in a text set while maintaining the linear construction time of the suffix tree.Through the tree index structure, repeated scanning of the text set can be avoided to reduce the algorithm complexity.In addition, in order to increase the efficiency of frequent word sequence mining in a continuous time interval, an improved pruning mining algorithm, called TS_Pruning is designed, which reduces the scanning range of the frequency tree.The experimental results show that compared with the Apriori mining algorithm, the TS_Mining algorithm and TS_Pruning algorithm reduces the running time by about 2 orders of magnitude, and displays a higher efficiency in frequent word sequence mining.

Key words: frequent word sequence, suffix tree, data mining, frequent itemset, hot topic detection

中图分类号:

TP391.4

王璐, 刘晓清, 何震瀛. 连续时间区间内的频繁词序列挖掘算法[J]. 计算机工程, 2022, 48(2): 79-85,91.

WANG Lu, LIU Xiaoqing, HE Zhenying. Frequent Word Sequence Mining Algorithm in Continuous Time Interval[J]. Computer Engineering, 2022, 48(2): 79-85,91.

http://www.ecice06.com/CN/Y2022/V48/I2/79

图/表 10

20220226124600

20220226124605

20220226124609

20220226124612

20220226124616

20220226124620

20220226124623

20220226124627

20220226124631

20220226124634

参考文献

[1] LIU J, SHANG J, WANG C, et al.Mining quality phrases from massive text corpora[C]//Proceedings of the 36th ACM SIGMOD International Conference on Management of Data.New York, USA:ACM Press, 2015:1729-1744.
[2] 王永恒, 贾焰, 杨树强.海量短语信息文本聚类技术研究[J].计算机工程, 2007, 33(14):38-40. WANG Y H, JIA Y, YANG S Q.Study on massive short documents clustering technology[J].Computer Engineering, 2007, 33(14):38-40.(in Chinese)
[3] 张仰森, 段宇翔, 黄改娟, 等.社交媒体话题检测与追踪技术研究综述[J].中文信息学报, 2019, 33(7):1-10, 30. ZHANG Y S, DUAN Y X, HUANG G J, et al.A survey on topic detection and tracking methods in social media[J].Journal of Chinese Information Processing, 2019, 33(7):1-10, 30.(in Chinese)
[4] EL-KISHKY A, SONG Y L, WANG C, et al.Scalable topical phrase mining from text corpora[J].Proceedings of the VLDB Endowment, 2014, 8(3):305-316.
[5] BEIL F, ESTER M, XU X W.Frequent term-based text clustering[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA:ACM Press, 2002:436-442.
[6] MA H F.Hot topic extraction using time window[C]//Proceedings of 2011 International Conference on Machine Learning and Cybernetics.Washington D.C., USA:IEEE Press, 2011:56-60.
[7] WANG X, ZHANG Y, ZHANG W J, et al.Skype:top-k spatial-keyword publish/subscribe over sliding window[J].Proceedings of the VLDB Endowment, 2016, 9(7):588-599.
[8] VAN LE H, TAKASU A.Parallelizing top-k frequent spatiotemporal terms computation on key-value stores[C]//Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.New York, USA:ACM Press, 2018:476-479.
[9] 刘一宁, 申彦明.基于终身机器学习的主题挖掘与评分预测联合模型[J].计算机工程, 2019, 45(6):237-241, 248. LIU Y N, SHEN Y M.Topic mining and ratings prediction joint model based on lifelong machine learning[J]. Computer Engineering, 2019, 45(6):237-241, 248.(in Chinese)
[10] 路畅, 何震瀛, 荆一楠, 等.热点词汇的最长时间区间查询算法[J].计算机应用与软件, 2019, 36(8):249-254, 305. LU C, HE Z Y, JING Y N, et al.A hot terms maximal time range query algorithm[J].Computer Applications and Software, 2019, 36(8):249-254, 305.(in Chinese)
[11] CHEN L S, SHANG S, JENSEN C S, et al.Top-k term publish/subscribe for geo-textual data streams[J].The VLDB Journal, 2020, 29(5):1101-1128.
[12] CHEN L S, SHANG S.Approximate spatio-temporal top-k publish/subscribe[J].World Wide Web, 2019, 22(5):2153-2175.
[13] 赵志洲, 路畅, 何震瀛, 等.一种高效的文本区间热词查询算法[J].计算机工程, 2018, 44(2):17-23, 30. ZHAO Z Z, LU C, HE Z Y, et al.An efficient text interval hot word query algorithm[J].Computer Engineering, 2018, 44(2):17-23, 30.(in Chinese)
[14] HAN J W, KAMBER M.Data mining:concepts and techniques[M].San Fancisco, USA:Morgan Kaufmann Publishers, Inc., 2012.
[15] AGRAWAL R, IMIELIŃSKI T, SWAMI A.Mining association rules between sets of items in large databases[C]//Proceedings of 1993 ACM SIGMOD International Conference on Management of Data.New York, USA:ACM Press, 1993:207-216.
[16] AGRAWAL R, SRIKANT R.Fast algorithms for mining association rules in large databases[C]//Proceedings of the 20th International Conference on Very Large Data Bases.New York, USA:ACM Press, 1994:487-499.
[17] HAN J W, PEI J, YIN Y W, et al.Mining frequent patterns without candidate generation:a frequent-pattern tree approach[J].Data Mining and Knowledge Discovery, 2004, 8(1):53-87.
[18] 刘昱彤, 吴斌, 谢韬, 等.基于古汉语语料的新词发现方法[J].中文信息学报, 2019, 33(1):46-55. LIU Y T, WU B, XIE T, et al.New word detection in ancient Chinese corpus[J].Journal of Chinese Information Processing, 2019, 33(1):46-55.(in Chinese)
[19] 柯文俊, 高金华, 沈华伟, 等.基于改进Apriori算法的问题模板无监督抽取方法[J].中文信息学报, 2020, 34(10):76-84. KE W J, GAO J H, SHEN H W, et al.Unsupervised question template extraction based on improved Apriori algorithm[J].Journal of Chinese Information Processing, 2020, 34(10):76-84.(in Chinese)
[20] WEINER P.Linear pattern matching algorithms[C]//Proceedings of the 14th Annual Symposium on Switching and Automata Theory.Washington D.C., USA:IEEE Press, 1973:1-11.
[21] MCCREIGHT E M.A space-economical suffix tree construction algorithm[J].Journal of the ACM, 1976, 23(2):262-272.
[22] UKKONEN E.On-line construction of suffix trees[J].Algorithmica, 1995, 14(3):249-260.
[23] SCHLER J, KOPPEL M, ARGAMON S, et al.Effects of age and gender on blogging[C]//Proceedings of 2006 AAAI Symposium on Computational Approaches for Analyzing Weblogs.Palo Alto, USA:AAAI Press, 2006:1-10.

选择文件类型/文献管理软件名称

选择包含的内容