多维序列模式挖掘算法分析

邹 妍，刘 燕

（赤峰学院 计算机与信息工程学院，内蒙古 赤峰 024000）

多维序列模式挖掘算法分析

邹 妍，刘 燕

（赤峰学院 计算机与信息工程学院，内蒙古 赤峰 024000）

多维序列模式挖掘是数据挖掘领域的一个重要分支.首先给出了多维序列模式挖掘的相关定义；其次对典型的多维序列模式挖掘算法进行了总体归纳，并对在此基础上发展起来的几种多维序列模式挖掘算法的改良性能进行了分析；最后展望其未来发展方向.

数据挖掘；多维序列模式；挖掘算法

1 引言

数据挖掘作为知识发现的核心步骤，旨在从海量数据中提取有效的、潜在有用的、易于理解的知识.序列模式挖掘是数据挖掘中非常重要的一个研究领域，最早是由R.Agrawal和R.Srikant在针对超市中购物篮数据的分析提出来的[1].这类模式有着广泛的应用，如客户购买行为模式的分析、Web访问模式的预测、疾病诊断、自然灾害预测、DNA序列分析等.多维序列模式挖掘是在序列模式挖掘基础上考虑了其它一些维信息，像在顾客购买行为分析中考虑到顾客的年龄、性别等信息，这样的模式融合了更多的信息，应用价值更高.经过多年的发展，对多维序列模式的研究取得了比较大的进步，研究者们提出了很多性能良好的算法.本文首先对三种经典多维序列模式挖掘算法进行总体归纳，接着对在这三种经典算法基础上发展起来的Seq-mdp算法、MSP算法及基于单基2维概念格的多维序列模式挖掘算法（不妨称之为TDCL-SB）进行了分析总结.最后对未来的研究重点进行了展望.

2 多维序列模式挖掘相关定义

多维序列模式是从序列模式发展来的，是在序列模式一维挖掘的基础上考虑了多维因素，使挖掘出的序列模式融合了更多的信息，具有更高的应用价值[2].多维序列数据库具有如下模式（RID，A1，…, Am，S），其中RID作为主键（Primary key）.A1，…,Am是维，S是数据序列域.以*作为元符号（meta-symbol）表示不属于维A1，…,Am域的值.一个多维序列可表示为p=（a1，…，am，s），其中ai∈（Ai∪{*}）（1≤i≤m），s是一个序列.

表1 多维序列数据库实例

定义1对于多维序列p=（a1，…，am，s）和数据库元组t=（x1，…，xm，si），当且仅当ai=xi或ai=*（1≤i≤m），并且s⊆si时，称t包含p.在多维序列数据库S中，包含p的元组个数称为p的支持数，记为support（p）.给定最小支持度阈值minsup，如果support（p）≥minsup，则称p为多维序列模式.

定义2多维序列模式p=（a1，…，am，s）中的多维信息M=（a1，…，am）称为多维模式（multi-dimensional patterns或MD-patterns）.若a1，…，am中有n个（n≤m）不是*，则称M是一个n-维模式.设有i-维模式Mi=（a1，…，am）和j-维模式Mj=（b1，…，bm），其中，若对于所有不为*的ak（1≤k≤m）一定有ak=bk，则称Mi是Mj的一个子模式（sub-pattern），而Mj是Mi的一个父模式（super-pattern）.

多维序列模式挖掘的任务就是从多维序列模式数据库中寻找出所有的满足最小支持度的多维序列模式.一个多维序列数据库实例如表1所示，它记录了顾客的购买历史及相关属性.Tid为序列号，包含3个维，消费群体、城市和年龄.假定A,B,…,H为顾客所购买的项目.从表1可以看出，多维序列P=（*，赤峰，*，）被特集（1，商人，赤峰，中年，<(BD)CBA>），（2，自由职业者，赤峰，老年，<(BF) (CE)(FG)>）和（3，商人，赤峰，中年，<(AH)ABF>）所包含.P的支持度为3，如果给定的最小支持数为2，则P是一个多维序列模式.

3 多维序列模式挖掘算法分析

3.1 三种经典多维序列模式挖掘算法

文献[2]提出了三种经典的多维序列模式挖掘算法：UniSeq，Seq-Dim和Dim-Seq.总体上，可以将多维序列模式挖掘算法划分为两类：一类是将多维分析方法和序列模式挖掘算法相结合的方法；另一类是先将多维信息集成到序列中，再对新集成的序列进行挖掘.Seq-Dim和Dim-Seq属于第一类，U-niSeq属于后一类.

虽然，Seq-Dim和Dim-Seq属于同一类算法，但是它们也有区别，关键在于处理步骤的顺序不同.Seq-Dim算法的挖掘过程具有明确的目的性，先挖掘原始的序列模式，然后再利用BUC（Bottom-UP Computation）[3]算法挖掘序列投影数据库的多维信息模式.由于在挖掘维度较高的多维模式时，BUC算法的效率要高于PreFixSpan算法[4]（该算法是Uniseq所采用的多维序列模式挖掘算法），因此，Seq-Dim算法在挖掘高维度的多维序列模式时更具优势.

而Dim-Seq算法则是先挖掘多维信息模式，再生成相应的多维模式投影数据库来挖掘序列模式.其缺点是显而易见的，首先，在第一个步骤中产生的多维信息模式并不能产生多维序列模式，这就造成了大量的浪费.其次，该算法没有对序列模式进行优化，当出现高维度的情况时，该算法的执行开销会剧增.

UniSeq算法的基本思想是先把多维信息合并到序列数据库中，再对新集成的序列数据库进行挖掘，最后利用经典序列模式挖掘算法PreFixSpan对新的序列数据库进行挖掘.该算法的优点是将所有的多维信息集成到序列数据库中，容易实现和理解.且利用PreFixSpan算法，省去了在转换数据结构过程及挖掘过程中的资源消耗.该算法适合于序列维度较低的情况.

3.2 Seq-mdp算法

从对三种经典多维序列模式挖掘算法的分析中可以看出，Seq-Dim算法是较高效的一种算法.但该算法有缺点，由于在挖掘多维模式时要多次扫描投影数据库，因此在维度高、数据量大时，时间开销也大.因此，研究者在文献[5]中提出了一种基于连接的多维序列模式挖掘算法（以下称之为Seq-mdp）.

Seq-mdp算法与Seq-Dim算法的相似之处在于：也是先挖掘一般序列模式，再对每个序列模式生成该模式的维信息投影数据库，然后再在投影数据库中挖掘多维模式，从而得到多维序列模式.

与Seq-Dim算法相比，改进的地方在于：挖掘多维模式时采用一种以空间换取时间的策略，减少了挖掘多维模式的时间.但是，由于需要空间记录频繁项的相关信息用于后续的连接，因而在空间上开销较大.

从Seq-mdp算法的描述可以看出，只需扫描一次投影数据库即可得到所有的多维模式.该算法主要是通过记录支持每个频繁1-项集的元组及其属性的方法，所记录的这些内容以备后续连接之用.在扫描投影数据库时，得到频繁1-项集及上述相关信息，由频繁（k-1）-项集（其中，k>1）做连接生成频繁k-项集，再通过频繁k-项集中的频繁项就可以得到一个k-维模式，由此得到所有的k维模式.该算法减少了扫描投影数据库的次数，只对不断减小的频繁（k-1）-项集扫描，在时间复杂度方面明显优于Seq-Dim算法.

3.3 MSP算法

文献[6]通过设置阈值及对比模式类与序列项的方法提出了多维序列模式挖掘算法MSP.

MSP算法给出了规则的支持度及规则的确信度、带有最小支持度阈值的频繁规则、序列模式支持度阈值、两序列的相异度、相似序列、多维序列规则及模式类的相关定义.算法包括三个步骤：通过设置序列模式的支持度阈值、序列相异度阈值及属性的支持度阈值，挖掘数据集中的最大频繁模式，求出各模式类所包含的属性，根据属性的支持度阈值确定哪些属性用于生成多维规则的前件；比较数据中各序列项序列与各模式类的包含与相似关系；按照一定的规则抽取与各模式类相关的属性，进而对规则进行相应的化简，给出以属性为前件、模式类为后件的多维序列规则为形式的多维序列模式挖掘结果.

通过与文献[7]提出的基于数据特性的多维序列模式挖掘算法MSRC在特点及运行时间上的比较，可以看出在规则冗余方面有了改进，化简的规则能更好的反映属性与序列项序列之间的关系，能挖掘出更有意义的多维序列模式；另外，在时间复杂度上MSP算法更具优势，该算法更有效.且该算法可以应用到空间多维序列及多关系多维序列模式的挖掘上，具有较好的可扩展性.

3.4 TDCL-SB

文献[8]在多维概念格数据模型的基础上，提出了多维序列模式的增量挖掘算法TDCL-SB.多维概念格是针对多维序列模式挖掘应用而提出的新的数据结构，是对概念格和有序概念格的泛化.文献[7]提出的TDCL-SB算法通过增量式构建单基2维概念格来发现多维序列模式.有了多维格这种新的数据结构，使得整个挖掘过程变得高效，无论是有序信息维，还是无序信息维，其处理都是在多维格结构上进行的，而无需像传统算法那样针对不同的数据结构采用不同的处理策略，另外，该算法仅需扫描一次数据库，并具有较好的增量特性.TDCL-SB算法在某银行信用卡客户的交易数据集上作了实际验证，实验结果表明，该算法具有以下优点：

（1）采用统一的数据模型实现一般序列模式与关联模式的高效同步挖掘；

（2）算法具有增量特性，适用于数据集更新频繁或用户无法预先确定最小支持度约束范围的应用场合；

（3）算法生成的是具有实际应用价值的最大频繁序列模式.

4 总结

自多维序列模式挖掘的概念及经典算法提出以来，经过近些年的发展，多维序列模式挖掘研究取得了较大的进展，但仍然存在一些问题，比如与相关领域知识的结合不够，针对海量数据时间开销大、算法效率不高等.这些都是下一步需要解决的问题.多维序列模式挖掘有着广阔的应用前景，如何进一步提高算法的挖掘性能，以及如何加入一些时间和分类等约束，是有待于进一步研究的问题.

〔1〕R.Agrawal,R.Srikant.M ining Sequential Patterns [C].In: Proceeding of the list International Conference on Data Engineering.TaiPei,1995: 3-14.

〔2〕Pinto H,Han J,Pei J,et al.M ulti-dimensional sequential pattern m ining[C]//Proc.of athe 10th International Conference on Information and Know ledge M anagement.Atlanta,New York:ACM Press,2001:81-88.

〔3〕K.Beyer,R.Ramakrishnan.Botton-up computation of sparse and iceberg cubes[C].In:Proc. 1999ACM-SIGMODInt.Conf.Management of Data(SIGMOD’99),Philadelphia,PA,1999:359-370.

〔4〕Jian Pei,Jiawei Han,Behzad M ortazavi-Asi,HelenPinto.PrefixSpan:M ining Sequential Patterns Efficiently by Prefix-Projected Pattern[C]. IEEE，2001.

〔5〕肖仁财.序列模式挖掘算法研究与实现[D].江苏大学,2007.17-30.

〔6〕李广原,杨炳儒，等.多维序列模式挖掘算法[J].计算机工程与设计,2011,32(7):2378-2379.

〔7〕Lionel Savary,Karine Zeitouni.M ining multidimensional sequential rules:a characterization based approach[C].IEEE MCD05,2005:99-102.

〔8〕金阳,左万利.多维概念格与多维序列模式的增量挖掘[J].计算机研究与发展,2007,44(11):1818-1824.

TP311.13

A

1673-260X（2014）04-0034-03

内蒙古自治区自然科学基金项目资助（2011MS0914）