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

• 作者: 刘胜蓝 王乐 王水 王辉兵
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 数据挖掘 序列模式 通配符 模式匹配 索引树
• 年，卷（期）: 2019,（3）
• 所属期刊栏目: 人工智能
• 页码范围: 554-565
• 页数: 12页
• 分类号: TP18
• 字数: 8590字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2019.00554

摘要

随着有序时间序列数据的出现,序列模式挖掘成为数据挖掘领域的一个分支.其中带通配符的序列模式挖掘又是该领域中一个重要的研究问题,同时随着数据规模越来越大,算法的挖掘效率尤为重要.现有算法多采用树型结构来实现数据的压缩表示,树的结构和模式匹配方法对挖掘效率有决定性的影响.该文首先设计一个新的树结构索引树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％.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王乐	宁波财经学院信息工程学院	17	151	9.0	12.0
3	刘胜蓝	大连理工大学创新创业学院	15	129	7.0	11.0
6	王水	宁波财经学院信息工程学院	1	1	1.0	1.0
7	王辉兵	大连理工大学创新创业学院	5	32	3.0	5.0