基于索引树的带通配符序列模式挖掘算法

作     者：王乐 王水 刘胜蓝 王辉兵 WANG Le;WANG Shui;LIU Sheng-Lan;WANG Hui-Bing

作者机构：宁波财经学院信息工程学院浙江宁波315175 大连理工大学创新创业学院辽宁大连116024 

基　　金：国家自然科学基金项目(1120165702) 中国博士后面上基金项目(ZX20150629) 浙江省科技厅计划项目(2016C31128 2017C35014) 宁波市自然科学基金项目(2015A610135) 2015年度浙江省统计研究重点课题(201522)资助 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2019年第42卷第3期

页      码：554-565页

摘      要：随着有序时间序列数据的出现,序列模式挖掘成为数据挖掘领域的一个分支.其中带通配符的序列模式挖掘又是该领域中一个重要的研究问题,同时随着数据规模越来越大,算法的挖掘效率尤为重要.现有算法多采用树型结构来实现数据的压缩表示,树的结构和模式匹配方法对挖掘效率有决定性的影响.该文首先设计一个新的树结构索引树I-Tree(Index-Tree)来维护原始序列数据以及序列模式和模式索引信息;然后在索引树的基础上,提出一个新的带通配符的序列模式挖掘算法ITM(Index-Tree based sequential pattern Mining).算法ITM主要用4个策略提高算法的挖掘效率:(1)将原始序列中相同项压缩到一个节点上,该节点只记录项在原始序列中的索引;(2)采用迭代的方式,长度k+1的序列模式是用长度k(k>0)的候选序列模式产生;(3)采用前缀树的结构,逐层将k+1的候选序列模式压缩到索引树上,叶子节点上记录序列模式最后一项的索引;(4)整个挖掘过程,只用一棵索引树.算法ITM通过采用以上索引树压缩原始序列数据以及存储候选序列模式,有效地缩小搜索空间,从而算法效率得到显著提升.另一种提高挖掘效率的思路,是在挖掘过程中允许有小部分的模式丢失,来换取挖掘效率的大幅度提升,即所谓的近似模式挖掘.该文也给出了一个近似序列模式挖掘算法AITM(Approximate Index-Tree based sequential pattern Mining),该近似算法通过估计超序列模式的支持数,将非候选节点提前删掉,减少索引树上的节点个数,从而提高算法的时空效率;但是也因为估计的支持数可能会小于实际值,从而丢失了部分频繁的序列模式.该文实验中,提出的两个算法分别与算法MGCS、MAPB和MAPD进行了对比实验,采用3个典型数据序列进行测试,并设计了3组实验:(1)不同的最小支持度对算法的效率影响;(2)算法的扩展性;(3)通配符长度对算法效率的影响.实验结果验证了该文提出算法的有效性,时空效率得到一定的提高;针对不同的阈值,最小支持度越小、原始序列长度越长、通配符长度越长,算法的时间效率提高幅度越大;同时近似挖掘算法的精确度接近100%.

主 题 词：数据挖掘 序列模式 通配符 模式匹配 索引树 

学科分类：0810[工学-土木类] 12[管理学] 1201[管理学-管理科学与工程类] 0808[工学-自动化类] 0839[0839] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 

核心收录：

D　O　I：10.11897/SP.J.1016.2019.00554

馆 藏 号：203572366...