Hits:

Indexed by:期刊论文

Date of Publication:2017-04-17

Journal:计算机学报

Included Journals:EI、CSCD、Scopus

Volume:40

Issue:6

Page Number:1338-1352

ISSN No.:0254-4164

Key Words:序列模式挖掘;一般间隙;频繁模式;模式匹配;Apriori性质;人工智能

Abstract:序列模式挖掘是从给定序列中发现出现频率高的模式的一种方法,目前已在诸多领域被广泛应用.假定子模式pi和pj(i＜j)可以分别匹配事件A和事件B,传统的序列模式挖掘方法能够对事件B在事件A之后的序列进行检测,而不能对事件B发生在事件A之前的序列进行识别.为了解决此问题,文中提出了周期性一般间隙约束的序列模式挖掘问题,该问题具有如下5个特点:间隙约束的最小值可为负值的一般间隙约束;每个间隙约束都相同的周期性模式;在支持数统计方面无特殊约束,即允许序列中事件多次使用;该挖掘问题满足Apriori性质;挖掘支持率大于给定的频繁度阈值的频繁模式.为了进行有效地挖掘,采用深度优先的方式建立模式树.文中采用模式匹配技术,在一遍扫描序列数据库的情况下,建立其所有超模式的不完整网树森林(不完整网树是网树的最后一层结点,可以存储在一个数组中,可以有效地表示一个模式在一个序列中的支持数),并对这些超模式的支持率进行有效地计算,进而挖掘出所有频繁模式,有效地提高了序列模式挖掘速度.实验结果验证了文中算法的可行性和有效性.