周期性一般间隙约束的序列模式挖掘

发布时间：2018-04-20 10:29

本文选题：序列模式挖掘 + 一般间隙　；参考：《计算机学报》2017年06期

【摘要】：序列模式挖掘是从给定序列中发现出现频率高的模式的一种方法,目前已在诸多领域被广泛应用.假定子模式p_i和p_j(ij)可以分别匹配事件A和事件B,传统的序列模式挖掘方法能够对事件B在事件A之后的序列进行检测,而不能对事件B发生在事件A之前的序列进行识别.为了解决此问题,文中提出了周期性一般间隙约束的序列模式挖掘问题,该问题具有如下5个特点:间隙约束的最小值可为负值的一般间隙约束;每个间隙约束都相同的周期性模式;在支持数统计方面无特殊约束,即允许序列中事件多次使用;该挖掘问题满足Apriori性质;挖掘支持率大于给定的频繁度阈值的频繁模式.为了进行有效地挖掘,采用深度优先的方式建立模式树.文中采用模式匹配技术,在一遍扫描序列数据库的情况下,建立其所有超模式的不完整网树森林(不完整网树是网树的最后一层结点,可以存储在一个数组中,可以有效地表示一个模式在一个序列中的支持数),并对这些超模式的支持率进行有效地计算,进而挖掘出所有频繁模式,有效地提高了序列模式挖掘速度.实验结果验证了文中算法的可行性和有效性.
[Abstract]:Sequential pattern mining is a method to discover patterns with high frequency from a given sequence, which has been widely used in many fields. It is assumed that the subpatterns pi and pstack _ jj _ ijj) can match event A and event B, respectively. The traditional sequential pattern mining method can detect the sequence of event B after event A, but can not identify the sequence of event B that occurred before event A. In order to solve this problem, a sequential pattern mining problem with periodic general gap constraints is proposed. The problem has the following five characteristics: the minimum value of gap constraints can be negative general gap constraints; Every gap constraint has the same periodic pattern; there are no special constraints in supporting statistics, that is, the events in the sequence are allowed to be used multiple times; the mining problem satisfies the Apriori property; and the mining support rate is greater than the given frequency threshold. In order to excavate effectively, the pattern tree is built in depth first. In this paper, the pattern matching technique is used to set up all the incomplete net tree forests of its superpattern (incomplete net tree is the last layer node of the net tree, which can be stored in an array) under the condition of scanning the sequence database once. It can effectively represent the support number of a pattern in a sequence, calculate the support rate of these superpatterns effectively, and then mine all frequent patterns, thus effectively improving the speed of sequential pattern mining. Experimental results show that the proposed algorithm is feasible and effective.
【作者单位】：河北工业大学计算机科学与软件学院;大连理工大学软件学院;合肥工业大学计算机科学与信息工程学院;佛蒙特大学计算机系;
【基金】：国家自然科学基金(61229301) 教育部创新团队项目(IRT13059) 河北省自然科学基金(F2013202138) 河北省教育厅重点项目(ZD2014009);河北省教育厅青年基金(QN2014192)资助~~
【分类号】：TP311.13

【参考文献】