大数据环境下的高效分布式增量序列挖掘

南楠; 严英占

doi:10.13718/j.cnki.xsxb.2020.11.012

摘要: 本文提出一种基于MapReduce架构的高效分布式增量序列模式挖掘算法(Incremental Sequential Pattern Mining，IncSPM)，用于解决大数据环境中每当数据增加时就更新序列模式的问题.该算法利用后向挖掘算法来有效利用先前挖掘生成的序列模式，同时设计同现反转映射(Co-occurrence Reverse Map，CRMAP)数据结构来处理候选序列的组合爆炸问题，最后设计了新的候选生成和早期修剪机制以加快挖掘过程.用两种真实数据集对本文提出的算法进行了评估，实验表明与其他方法相比，本文算法在执行时间、内存消耗和扩展性方面均有实质性的提高.

Abstract: An efficient distributed incremental sequential pattern mining algorithm (Incremental Sequential Pattern Mining, IncSPM) based on MapReduce architecture is proposed to solve the problem of updating sequential patterns whenever data increases in big data environment. With this algorithm, the backward mining algorithm is used to utilize effectively the sequence patterns generated by previous mining, and simultaneously design a Co-occurrence Reverse Map (CRMAP) data structure to deal with the combined explosion problem of candidate sequences. Finally, new candidate generation and early pruning mechanism are designed to speed up the mining process. The proposed algorithm is evaluated on two real datasets, and experiments show that compared with other methods, the algorithm proposed in this paper has a substantial improvement in execution time, memory consumption and scalability.

Key words:

big data mining /
incremental sequential pattern /
backward mining /
co-occurrence reverse map data structure .

全文HTML

序列模式挖掘(Sequence Pattern Mining，SPM)是一个广泛应用的热门数据挖掘任务，用来挖掘频繁出现的有序事件或子序列^[1-2]，在挖掘Web使用模式、分析客户购买行为、挖掘DNA序列等方面有很大的应用价值.由于大数据具有大容量、多样性、高速度、低价值密度和准确性等特征^[3-4]，每当数据发生变化时，都必须重新运行序列模式挖掘算法，这是因为从旧数据获得的频繁项，在更新的数据中可能变为不频繁项，并且在更新的数据中可能会出现新的频繁项^[5].如果序列数据库的规模比较大，则有可能会产生大量的候选序列模式，故传统的SPM不可扩展^[6].传统的序列模式增量维护算法不能很好地适应大序列数据库，必须设计分布式挖掘算法来处理大数据^[7].

MapReduce是一种遵循分而治之的策略来处理大数据问题的分布式编程框架，它对程序员隐藏了数据划分和分配、任务调度、机器间通信和容错的内部细节，允许没有任何经验的程序员在分布式系统中有效地处理系统的资源^[8]. MapReduce模型不仅简化了分布式编程的任务，而且实现了对大数据集更好的处理^[9].后向挖掘算法用于高效序列模式的增量挖掘，该算法4个显著的优点：①提供一种简单的方法来检测稳定序列；②引入了唯一的稳定序列性质，即稳定序列的任何扩张也是稳定的；③稳定序列属性，通过跳过对稳定序列的支持计数来提高挖掘速度；④验证了序列新支持计数的过程很简单.

为了使增量挖掘算法可以很好地适应大序列数据库，已经有大量序列模式增量维护的算法研究.文献[10]提出了一种利用MapReduce框架从大数据集中挖掘频繁项集的位向量积算法，该算法运用位向量数据结构来维护压缩的事务，从给定的事务列表中有效地搜索频繁项集，其优点是只需扫描一次数据集.文献[11]提出了一种用于高效序列模式挖掘的纯数组结构(Array Structure for High-utility Sequential，AHUS)和并行策略，该算法运用高效用序列模式挖掘来发现序列数据库中效用值等于或大于给定最小效用阈值的所有序列模式的任务，运用AHUS并行挖掘来同时识别高效用序列模式(High-utility Sequential Pattem，HUSP)，具有较好的可扩展性.文献[12]提出了基于云均匀分布式词汇序列树算法的序列模式挖掘算法.该算法使用两阶段MapReduce框架发现序列模式，无需启动多轮MapReduce即可显著提高整体性能，并在云中的机器之间提供完美的负载平衡，实现了极高的可扩展性，并提供了比现有的云端算法更好的负载均衡.

基于文献[12]的研究，通过设计新的CRMAP数据结构和后向挖掘算法，提出了基于MapReduce的高效分布式增量序列模式挖掘(IncSPM)算法，用来解决大数据环境中序列模式挖掘的增量维护问题.文献[12]是一种广度优先搜索算法，它们组合较小的序列产生候选序列，生成可能不会出现在数据库中的候选序列.本文算法通过后向挖掘算法来有效利用先前挖掘生成的序列模式，引入一种高效的CRMAP数据结构来生成出现在输入数据库中有希望的候选对象，以减小搜索空间.基于CRMAP数据结构，设计候选生成规则和早期修剪机制以避免输入数据库中生成错误的候选序列，从而使本文算法具有良好的线性可扩展性.实验结果显示，本文IncSPM在处理时间、内存消耗和可扩展性方面的有实质性的提高.

1. 后向挖掘和同现反转映射

1.1. 后向挖掘

以往的序列模式挖掘MapReduce算法没有处理增量维护问题，不能利用以前挖掘生成的序列模式，每当数据增加时，它们都会在更新的数据集上重新运行算法.在大数据环境中，通过扫描整个数据集来重新挖掘所有序列模式是不可接受的，本文采用后向挖掘来进行序列模式的高效增量挖掘.序列s的更新数据集(Updated Dataset，UD)中输入序列集合称为s的投影pj_s，序列s最后一个项目集中的项集称为序列s的结尾end_s，输入序列s的相应属于增量数据集(Increment Sequence Dataset，IncSD)中项目集称为序列s的增量inc_s，更新数据集UD中所有输入序列的inc_s并集称为UD的增量并集，其增量inc_s包含末端输入序列的集合被称为序列s的末端投影endpj_s，属于pj_s而不属于endpj_s的输入序列的集合称为序列s的SD投影.

在后向挖掘中，长度为k的序列在向后方向上被扩展到长度k+1，具有项j的序列〈a_ka_k－1…a₂a₁〉的项集扩展表示为〈{j∪a_k}a_k－1…a₂a₁〉，同样具有项目j的序列〈a_ka_k－1…a₂a₁〉的序列扩展被表示为〈ja_ka_k－1…a₂a₁〉.在生成新的序列s之后，如果该序列的末端投影为空，则表明任何输入序列的增量不包含s，并且s是稳定的.因此，UD中稳定序列的支持数与原始数据集SD中的支持数相同.

1.2. 同现反转映射数据结构

同现反转映射(Co-occurrence Reverse Map，CRMAP)数据结构用来解决大多数序列模式挖掘算法的性能瓶颈-评估数据库中不存在的模式所花费的时间，可以处理候选序列的组合爆炸问题.

CRMAP是将每个项目j映射到序列中位于其前面的一组项目的数据结构.本文定义了两个CRMAP结构，即CRMAP_i和CRMAP_s. CRMAP_i以不少于最小支持数(Minimum support，min_sup)序列将每个项目j映射相对于项集扩展在其之前的一组项目，CRMAP_s以不少于min_sup序列将每个项目j映射到相对于序列扩展在其之前的一组项目.

引理1 当且仅当x∈CRMAP_i(y)时，相对于项集扩展〈(x，y)〉的长度为2的向后扩展序列被认为是频繁的.

证明：根据CRMAP_i的定义，如果项目x没有映射到CRMAP_i(y)，则相对于少于min_sup序列的项集扩展而言，x出现在y之前，故〈(x，y)〉不频繁.

引理2 当且仅当x∈CRMAP_s(y)时，相对于序列扩展〈(x，y)〉的长度为2的向后扩展序列被认为是频繁的.

证明：根据CRMAP_s的定义，如果项目x没有映射到CRMAP_s(y)，则相对于少于min_sup序列的序列扩展而言，x出现在y之前，故〈(x，y)〉不频繁.

4. 结语

为了使增量挖掘算法能够很好地适应大序列数据库，本文利用MapReduce分布式平台，提出了一种高效的增量序列模式挖掘(IncSPM)算法，用来处理大数据环境中的序列模式增量维护问题.该算法通过结合候选序列的后向挖掘来避免挖掘更新数据库中支持度不变的序列，同时引入高效的CRMAP数据结构来生成出现在输入数据库中有希望的候选对象，以减小搜索空间.基于CRMAP设计高效的候选生成规则和早期剪枝属性以避免输入数据库中生成错误的候选序列，加快挖掘过程.实验表明，本文算法在执行时间、内存和可扩展性方面均有明显的提高.未来的工作是解决在数据被删除和修改时更新序列模式的问题，并尝试在其他大数据处理框架(如Apache Spark)上实现所提出的算法.

参考文献 (12)

姓名
	姓名不能为空！
邮箱
	邮箱不能为空！非法的邮箱地址。
手机号码
	电话不能为空！请输入有效手机号!
标题
	标题不能为空！
留言内容
	内容不能为空！
验证码
	验证码不能为空！验证码错误！

[1]	doi: http://arxiv.org/abs/1805.10515 GAN W S, LIN J C W, FOURNIER-VIGER P, et al. A Survey of Parallel Sequential Pattern Mining [J]. ACM Transactions on Knowledge Discovery from Data, 2019, 13(3): 1-34.
[2]	doi: http://www.researchgate.net/publication/313476858_A_Survey_of_Sequential_Pattern_Mining FOURNIER-VIGER P, LIN J C W, KIRAN R U, et al. A survey of sequential pattern mining[J]. Data Science and Pattern Recognition, 2017, 1(1): 54-77.
[3]	doi: http://www.sciencedirect.com/science/article/pii/S0378720617303129 WANG Y C, KUNG L, WANG W Y C, et al. An Integrated Big Data Analytics-enabled Transformation Model: Application to Health Care [J]. Information & Management, 2018, 55(1): 64-79.
[4]	O'HALLORAN K L, TAN S, PHAM D S, et al. A Digital Mixed Methods Research Design: Integrating Multimodal Analysis with Data Mining and Information Visualization for Big Data Analytics [J]. Journal of Mixed Methods Research, 2018, 12(1): 11-30. doi: 10.1177/1558689816651015
[5]	TARUS J K, NIU Z D, KALUI D. A Hybrid Recommender System for E-learning Based on Context Awareness and Sequential Pattern Mining [J]. Soft Computing, 2018, 22(8): 2449-2461. doi: 10.1007/s00500-017-2720-6
[6]	邵梁, 何星舟, 尚俊娜.基于Spark框架的FP-Growth大数据频繁项集挖掘算法[J].计算机应用研究, 2018, 35(10): 2932-2935. doi: http://d.old.wanfangdata.com.cn/Periodical/jsjyyyj201810012
[7]	SALETI S, SUBRAMANYAM R B V. A Novel Mapreduce Algorithm for Distributed Mining of Sequential Patterns Using Co-occurrence Information [J]. Applied Intelligence, 2019, 49(1): 150-171. doi: 10.1007/s10489-018-1259-2
[8]	doi: http://dl.acm.org/doi/10.1145/3178114 WANG J Z, HUANG J L. On Incremental High Utility Sequential Pattern Mining [J]. ACM Transactions on Intelligent Systems and Technology, 2018, 9(5): 1-26.
[9]	GAUTAM J V, PRAJAPATI H B, DABHI V K, et al. Empirical Study of Job Scheduling Algorithms in Hadoop MapReduce [J]. Cybernetics and Information Technologies, 2017, 17(1): 146-163. doi: 10.1515/cait-2017-0012
[10]	SALETI S, SUBRAMANYAM R B V. A Novel Bit Vector Product Algorithm for Mining Frequent Itemsets from Large Datasets Using MapReduce Framework [J]. Cluster Computing, 2018, 21(2): 1365-1380. doi: 10.1007/s10586-017-1249-x
[11]	DINH D T, LE B, FOURNIER-VIGER P, et al. An Efficient Algorithm for Mining Periodic High-utility Sequential Patterns [J]. Applied Intelligence, 2018, 48(12): 4694-4714. doi: 10.1007/s10489-018-1227-x
[12]	CHEN C C, SHUAI H H, CHEN M S. Distributed and Scalable Sequential Pattern Mining through Stream Processing [J]. Knowledge and Information Systems, 2017, 53(2): 365-390. doi: 10.1007/s10115-017-1037-1

留言板