一种基于m元树结构的序列模式挖掘

郑金彬

（龙岩学院 数学与计算机科学学院，福建 龙岩 3 6 4 0 1 2）

一种基于m元树结构的序列模式挖掘

郑金彬

（龙岩学院 数学与计算机科学学院，福建 龙岩 3 6 4 0 1 2）

提出一种基于m元树结构序列挖掘模式挖掘算法，该算法通过构造m元树结构，利用滑动窗口不断对数据集新旧项目的增删以确保数据库内容的更新.实验与理论分析表明，即使算法输入参数的不同，比如兴趣度、最小支持度等，该算法都是非常有效的.

数据挖掘；渐进序列模式；滑动窗口；m元树

1 引言

数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程.序列模式挖掘是数据挖掘技术中一个非常重要的研究课题和领域,旨在从有序事件的数据集中发现有规律的序列模式[1].序列模式挖掘中首次引入了：“给定一个序列数据库，每个序列由一组有序项目组成，包含不同的项目集列表和一个用户定义的最小支持度阈值，序列模式挖掘便是找出所有发生频率不低于序列阈值的子序列”[2].

定义1 令X={x1,x2,…,xn}是不同的项目集，元素 e记为 (xixj)，xi,xj为不同的单项（1≤i≤n,1≤j≤n），元素内的单项不考虑顺序关系，一般默认按照序列I D的字典序排列，在用户事务数据库里，一个事务就是一个元素；序列 s记为〈e1,e2,…,em〉，是一组有序元素列表，序列数据库D B则是一序列的集合，其中|D B|表示序列元素个数，即序列长度.在序列数据库 D B中，设序列 α=〈a1,a2,…,an〉和 β=〈b1,b2,…,bm〉，如果存在整数 1≤i1

序列模式挖掘可应用于数据中的数据不随时间而改变的静态数据库.然而在许多实际应用领域中，数据库中数据的内容是会不断更新变化的.正因为在数据库数据更新过程中，原先数据库中的非频繁数据序列也会变成频繁数据序列，为了找出所有的序列模式，所以挖掘算法不论数据库数据更新与否都必须一直要执行[4].为此，需采用序列模式挖掘中的增量式更新算法来解决这种超过数据库数据的挖掘过程.

针对序列数据集和增量数据集来挖掘频繁项均有广泛的研究案例了.然而采用渐进序列模式挖掘来发现序列模式是一个新的研究领域，不过渐进序列模式挖掘也面临新的挑战，就是如何发现数据项内在的特征以便将新的数据项添加到现有的数据库中和从数据库中删除废弃的数据项[3].

2 渐近序列模式挖掘概述

根据数据库相应的管理规则，为此我们提出了序列模式挖掘的一般模型，称之为“渐近序列模式挖掘”[2]，主要就是如何实现将新的数据项添加到现有的数据库中和从数据库中删除废弃的数据项，并因此不受废弃数据项的影响能找到最新序列模式.

2.1 问题描述

先前有许多关于渐近数据库的讨论研究，但提出的方法难以从数据库中提取重要的隐含信息，比如介于数据库之外的支持项.本文提出的m元树结构方法却有效地解决了这一问题，当然，这方法除了修改项目的标签、序列I D号和时间戳，还得添加每个项目的支持分支数.

2.2 相关研究

2.2.1 序列模式挖掘

序列模式的概念最早是由A g r a w a l和S r i k a n t提出的[5].一般序列模式挖掘算法可归纳为以下典型的三类：（1）类A p r i o r i算法，该类算法基于A p r i-o r i理论，即序列模式的任一子序列也是序列模式.算法首先自底向上的根据较短的序列模式生成较长的候选序列模式，然后计算候选序列模式的支持度.典型的代表有G S P算法，S P A D E算法等.（2）基于划分的模式生长算法，该类算法基于分治的思想，迭代的将原始数据集进行划分，减少数据规模，同时在划分的过程中动态地挖掘序列模式，并将新发现的序列模式作为新的划分元.典型的代表有F r e e S p a n算法和P r e f i x S p a n算法.（3）基于序列比较的算法，该类算法首先定义序列的大小度量，接着从小到大地枚举原始序列数据库中包含的所有k-序列，理论上所有的k-序列模式都能被找到，典型的代表为D i s c-a l l算法[6,7].其实基于以上三种思想的传统算法有很多，比如闭序列模式挖掘，最大频繁序列模式挖掘和约束序列模式挖掘等.

2.2.2 渐进序列模式挖掘

渐序列模式挖掘是一种普遍适用的找出最新频繁序列模式的模式挖掘方法.该算法在静态和动态变化的数据库中均可高效执行，且不受废弃数据的影响，该算法利用滑动窗口逐步更新数据库中的序列，随着时间的推移不断积累频繁候选序列模式.所谓滑动窗口就是在一个长为n的原始序列上从头到尾滑动长为w的窗口[6].

定义2 兴趣期（P O I）是一个滑动窗口.P O I长度是由用户自行定义的时间间隔.那么若序列元素的时间戳属于P O I的时间范围内，则将该元素归入长度为|D B|的序列模式，也就是说，若序列元素的时间戳不属于P O I的时间范围内，则应立即将其从序列数据库中枝剪出，并从此不再并入长度为|D B|的序列[6].

3 渐近序列模式挖掘的改进策略

其实可以通过修改渐近序列树结构来解决渐近序列模式的挖掘问题，方法就是归并包容相同支持度的项目以获得新的支持模式，本文则通过构建m元树的数据结构来实现这种策略.

3.1 数据结构

m元树结构用来存储数据库的项目的细节特征，该树的结点总体上分为根结点和叶结点两种.根结点用于链接所有叶结点的头结点，每个叶结点则包含每个项目的项目名称、序列I D号、时间戳.

3.1.1 添加新项目

在时间t时往m元树中插入新的元素，作为时间t+1的更新树.该算法在时间t采用后序策略遍历m元树，直到在渐近数据库查找到新的数据时中止运行，每当在一序列中存在有一系列元素，就用序列模式各自元素相应的序列号从根结点开始创建一条新的路径，以作为候选模式.如果这条路径已经存在，则以各自的信息来更新结点的相关区域.

3.1.2 删除废弃项目

应当将废弃的元素（比如属于兴趣期之外的元素），或者在序列列表中没有序列号的结点分别从结点序列表中和m元树中删除.

3.2 从渐进数据库中挖掘频繁模式

序列模式挖掘的主要思想就是利用了m元树存储介于不同兴趣期的所有序列.当时间刻t+1到来时，该算法便采用后序策略遍历原先的m元树，从中删除废弃项目并插入新项目以确保渐近序列数据库内容的更新.其算法如下所述：

3.3 算法实例

3.3.1 频繁序列模式的最小频率

如图1为一实例数据库，其中S01,S02,…,Sn表示不同I D号的序列，A，B，C，D表示在数据库中的不同项目，t1,t2,…,tk表示时间戳.随着时间的推移，会有越来越多的元素添加到渐近数据库中，比如序列S01在时间 t1,t2,t4,t5分别包含元素 A，B，C和（A D），而D bp,q则表示包含从时间戳p到时间戳q所有元素的数据库子集.假设最小支持度阀值m i n_s u p=0.5，|D bp,q|=5，那么该实例数据库频繁序列模式的最小频率为：|D b1,5|*m i n_s u p=5*0.5=2.5.

3.3.2 t0-t5的m元树结构构造实例

假设实例数据库如3.3.1所述，最小支持度阀值m i n_s u p=0.5，|D bp,q|=5，每一结点信息包含：结点标签、序列I D号和时间戳，则m元树在时间段t1-t5的构造过程为：在开始时刻t0m元树只有根结点；在时刻t1到来时，序列S01,S02,S03分别包含元素：A，(A D)和A，因三个序列均包含有元素A，所以元素A的序列I D号分别标上0 1，0 2，0 3，同样，元素D、（A D）的序列I D号分别标上0 2，它们的时间戳均为：1；在时刻t2到来时，序列S01,S02,S03,S04分别包含元素：B，B，(B C)和 D，根据 m-a r y算法的后序遍历，比如在序列S01,S02,S03的结点A，分别在序列表查找是否有新的元素到来，查找结果表明有B，C和（B C）三个新的元素，于是便在结点A后产生三个叶结点B，C和（B C），限于篇幅，其他时间戳所有结点的构造在这就不再说述了，t0-t5m元树结构构造结果如图2所示.

4 实验结果与算法性能分析

实验结果表明，基于3.3.1数据库的测试数据之上，该算法能非常有效的执行并完成序列模式的挖掘.以下对测试数据集依据不同的输入参数分析算法的特性，比如，兴趣期（P O I）、遍历时间等.

4.1 P O I对算法执行时间的影响

这里的执行时间是指该算法的执行所有指令所需的时间.实验结果如图3（a）所示，P O I与遍历模式时间是一种成正比的关系，原因就是：随着P O I的推进，不断遍历m元树时增加了候选模式，对此需扩展其相应的数据结构用于存储这些候选式，这必然造成所需时间的递增.

4.2 P O I及最小支持度对遍历模式数的影响

实验结果如图3（b）表明，遍历模式数量与P O I和最小支持度有着一定的依赖关系.也就是说，当P O I不断推进时，模式数量也跟着递增，若需处理的项目数越多，则产生的模式数就越多；同时，随着最小支持度的增加，模式数量却跟着递减，原因在于：当该项目的支持度小于最小支持度时，支持度较低的模式不会再频繁出现，也就是说发生的频繁很小.

5 结论

随着时间的不断推进，基于数据库测试数据所产生的序列模式也会不断发生更新，对于不断增加的候选集，通过构造m元树用于存储和管理，为此，设计出了相应的m元树的遍历算法来查找出所有的最新序列模式，同时删除了原有的废弃数据和模式.实验结果表明：该渐近序列模式挖掘算法不会受到输入参数的大幅度影响，且当所设置的最小支持阀值很小时，这算法就越显得高效了，此外，该算法在现实数据集上具有良好的可扩展性.

〔1〕Y.Hirate and h.Yamana, (2006) “Sequential Pattern Mining with Time Interval,”In:10th Pacific– AsiaConf.KnowledgeDiscovery and Data mining(PAKDD’06).

〔2〕C.Luo and S.M.Chung,(2005) “ Efficient Mining of Maxmal Sequential Patterns using Multiple Samples,” In:.5th SIAM Int’l Conf.Data Mining(SDM).

〔3〕S.Cong,J.han and D.Pandu,(2005) “Parallel Mining of Closed sequential Patterns,”In:11 ACM SIGKDD Int’l Conf.Knowledge Discovery and Data Mining(KDD’05).

〔4〕Jiawei Han,Micheline Kamber.数据挖掘:概念与技术(影印版)[M].高等教育出版社,2006.

〔5〕王虎,丁世飞.序列模式挖掘研究与发展[J].计算机科学,2009(12).

〔6〕蔡建山,迟呈英,战学刚,王丫.基于滑动窗口的动态摘要算法[J].计算机工程,2007(3).

〔7〕陈卓,杨炳儒,宋威,宋泽锋.序列模式挖掘综述[J].计算机应用研究,2008(7).

T P 3 0 1.6

A

1673-260X（2010）10-0031-04

福建省教育厅基金资助项目（JA08229）