李广原， 杨炳儒， 刘永彬， 刘英华

(1.北京科技大学信息工程学院，北京100083；2.广西师范学院计算机与信息工程学院，广西南宁530023)

0 引 言

序列模式挖掘是数据挖掘的一个重要方向，有着广泛的应用。人们已提出了不少的序列模式挖掘算法[1-7]，大多数现有的序列模式挖掘算法是针对一维数据来挖掘，并没有考虑这些模式与多维数据的相关性，因而可能会遗漏一些重要信息的挖掘。而多维序列模式挖掘[8-11]考虑多维数据之间的相关性，因而能够发现更多有关联、有价值的模式。文献[12]提出了一种基于数据特性的多维序列模式挖掘算法，它是以规则的形式给出多维序列模式的挖掘结果，该算法没有设定属性的支持度，得出大量的规则，而有些规则存在着冗余，可以进行化简，因而不能完全反映属性与序列项序列之间的关系，此外，如果所挖掘的最大频繁模式数目以及在属性较多的情况下，则挖掘过程十分耗时。本文给出一种新的多维序列模式挖掘算法，通过相关阈值的设置以及采用模式类与序列项比较的新方法挖掘属性与各序列项之间的关系，能够有效地发现多属性与序列模式间的关系，以挖掘潜在有意义的模式。事实证明，该算法是有效的，且具有较好的可扩展性。

1 基本定义

设I是一个项的集合，集合X={1,2,…,}I称为一个项集，由于它包含k个项，所以称为k项集。建立在项集I上的事务T，记T=(tid,I)，其中tid是事务的标识。项集X的支持度Support(X,D)是指在事务数据库D中包含X的事务的个数，规则X Y的支持度是Support(X∪Y)，规则X Y的确信度是

定义1 设D是一个事务数据库，I是项的集合，是最小支持度阈值，是最小确信度，D中的频繁项集记作

定义2 设D是一个事务数据库，I是项的集合，是最小支持度阈值，是最小确信度，则D中的满足最小支持度和最小确信度的频繁规则记作

定义3 设I是项的集合，序列s=<1,2,…,>定义为一个有序的项，其中 ∈I，i=1,2,…,n。这里，假设 仅由一个单项构成。

定义4 序列数据库是由一系列的元组构成，每个元组格式为(TID,S,A1,A2,…An)，其中TID为元组的标号，用来标识元组；S为序列名称；A1，A2，…An分别为属性1至属性n的名称。

定义5 序列s=<1,2,…,>为序列t=<1,2,…,>的子序列，如果存在整数 1≤j1

定义6 设s是D中一序列，如果Support(s,D)≥ ，则s是一频繁序列，是序列模式支持度阈值。

定义 7[12]设序列 s=，t=，n≥m，另设lcs(,)为两序列的最大公共子序列，两序列的相异度定义为Dissim(,)=n+m-2 lcs(,)。

定义8 给定一个相异度阈值 ∈Z，Z为整数，>0，如果Dissim(,)≤ ，则称序列s，t为相似序列。

定义9 一个多维序列数据库可以表示为(TID,S,A1,A2,…An)，其中TID为事务的关键字，S为序列项的名称，s1,s2,…,sn为序列项序列，A1,A2,…,An为多维数据的属性名，a1,a2,…,an分别是其属性值，一个多维序列定义为(tid,s,a1,a2,…,an)，多维序列数据库如表1所示。

表1 多维序列数据库

定义10 多维序列规则是形如(a1,a2,…,an)(s1,s2,…,sm)的关联规则，其中(a1,a2,…,an)代表多维数据的属性值，(s1,s2,…,sm)代表序列模式。

定义11 设se为数据库DB的一个子集，Supportse(propi(v))为第i个属性的值为v在se中的支持度，定义为

Suppportse(propi(v))=cardse(propi(v))/card(se)用于描述多维序列规则的属性，其支持度大于或等于给定的阈值 。

定义12 设Sc为某些序列模式SPc的模式类，定义多维序列规则为

2 MSP算法

为挖掘多维序列规则，提出了基于序列聚类与属性描述相结合的多维序列模式挖掘算法MSP，算法包括以下3个步骤：

(1)挖掘序列项中的最大频繁序列。每个最大频繁序列即构成一个模式类，一个模式类就是一条多维序列规则的后件。

(2)根据序列的包含与相似度计算式，对数据库中的每一序列项序列与上述各模式类进行比较，为每个模式类记下序列项序列所在事务的标号，为下一步处理相关属性做准备。

(3)经过步骤(2)处理后，对应于每一模式类，根据其包含的所有事务标号，取所有对应的事务属性进行相应的属性支持度计算，取支持度大于给定阈值的属性作为描述多维序列规则的属性，产生多维序列规则并进行化简。

2.1 挖掘最大频繁序列

目前已提出了不少的挖掘最大频繁序列算法，常用的算法有：GSP算法、PrefixSpan算法、SPADE算法等。对于长序列模式挖掘，可以采用文献[7]介绍的算法，该算法具有较好的扩展性能，且只需扫描一次数据库，采用有效的数据结构能够快速提高挖掘速度和节省存储开销。

2.2 相异度计算

序列相似度计算在生物信息学中有着重要的应用，DNA和蛋白质序列是基本生物学数据，通过开发有效的方法来比较和比对生物序列并发现生物序物模式非常重要，为了比对DNA序列的相似性，人们提出了一些有效的算法，如BLAST[13]、FASTA[14]、LCSS[15]。我们采用LCSS算法来对序列进行比较，它通过计算把序列s1转换成序列s2所需要的最小的删除、插入相关的项数。采用定义7计算公式，比如，设有两个序列：s1=，s2=，其最大子序列为：，(这里不考虑它们之间的项，只考虑它们的出现次序)则它们的相异度为4，相异度越小，说明两序列越相似。

2.3 支持类的事务选择

在挖掘最大频繁序列后，即生成了多维序列规则中后件每个最大频繁序列可作为模式的一类，数据库中的每一个序列项中的序列分别和这些模式类相比较，对于某一序列项序列，如果它包含某个模式类，则它属于支持该模式类，如果它同时包含多个模式类，则它同时支持多个模式类，如果它不包含任何模式类，则利用定义7、8和各个模式类进行相异度计算，支持所有满足相异度阈值模式类。上述操作，一旦某个序列项序列支持某个模式类后，便记下它所在事务的标号。

2.4 属性选择

当每个模式类所支持的事务确定后，便需要选择哪些属性来对多维序列规则进行描述，这里涉及到两个问题：一是属性的选择，二是属性值的取值，第一个问题可以根据定义11来确定，也就是选择支持度要大于给定阈值的属性，第二个问题，对于二元属性和数值属性，直接取值即可，而对于区间值属性，可以取它们区间相交值作为确定的值。

2.5 规则化简

经过前面几步后，可得到形如(a1,a2,…,an)(s1,s2,…,sm)的多维序列规则，在这里，(s1,s2,…,sm)是最大频繁模式，如果所生成的模式比较多，这时可根据属性间的关联(如果有)进行适当的化简，特别是当多维属性个数比较多的情况下。如果属性集{A{B}，{}，{{a1,a2,…,an}，则多维序列规则(a1,a2,{A},…{B},…,an)(s1,s2,…,sm)可化简为(a1,a2,{A},…,an)(s1,s2,…,sm)。

2.6 MSP算法描述

//主程序

//为序列模式的支持度阈值；为序列相异度阈值；为属性的支持度阈值。

3 MSP性能分析

为评价MSP算法的性能，我们选用文献[12]给出的算法(不妨称为MSRC)作为比较的对象，因为MSRC算法已成功地在一个真实数据集上进行测试，并且MSP和MSRC输出结果的形式都是多维序列规则。

3.1 MSP算法的特点

MSP有如下特点：①可以根据用户指定的条件控制输出规则的数目，这是由于设置了属性的支持度阈值。②MSP算法生成的规则，MSRC算法不能全部生成，这是因为在算法MSP中，数据库中每个序列项序列并不是唯一归于某一模式类，而是根据包含或相异度阈值来确定，它们可同时属于多个模式类，而算法MSRC只规定每个序列项序列仅属于与其最相似的模式类，每个模式类包含的序列项直接影响规则前件的构成。③MSP算法根据属性之间存在着的关联，可以对规则进行相应的化简。

3.2 MSP与MSRC运行时间的比较

MSP算法和MSRC算法主要的运行时间开销体现在对序列项序列求最大频繁模式以及对序列项序列与模式类进行比较这两个过程上。设：

TMSP：MSP 执行的总时间

TMSRC：MSRC执行的总时间

T0-MSP：MSP求最大频繁模式所花的时间

T0-MSRC：MSRC求最大频繁模式所花的时间

T1-MSP：MSP对序列项序列与模式类进行比较所花的时间

T1-MSRC：MSRC对序列项序列与模式类进行比较所花的时间

T0(X，Y)：逐个判断X个序列中的每个序列是否包含Y个序列中的每个序列所花的时间

T1(X，Y)：逐个求出X个序列中的每个序列与Y个序列中的每个序列存在的最大公子串所花的时间，则

又假设数据库共有N个事务数，一个序列项，序列项序列中存在M个最大频繁模式，即M个模式类，则

由于求两个序列是否存在包含关系所需的时间比求两个序列的最大公共子串所花的时间要小得多，即T1(X,Y)>T0(X,Y)。

由此

因而

根据式(1)～式(7)得

4 结束语

本文给出一种基于最大频繁模式挖掘、模式相似与属性描述相结合的多维序列模式挖掘算法MSP。通过相关阈值的设置以及采用模式类与序列项比较的新方法挖掘属性与各序列项之间的关系，以挖掘有意义的多维序列模式。对算法进行分析表明，MSP算法是有效的，且具有较好的可扩展性。该算法可以应用到挖掘诸如空间多维序列以及多关系多维序列模式上，进一步提高算法的挖掘性能是下一步要研究的方向。

[1]Liu H,Han J,Xin D,et al.Mining frequent patterns on very high dimensional data:a topdownrow enumeration approach[C].Bethesda:Proceeding of the SIAMInternational Conferenceon Data Mining,2006:280-291.

[2]Hye-Chung,Kum Joong,Hyuk Chang,et al.Sequential pattern mining in multi-databases via multiple alignment[J].Data Mining and Knowledge Discovery,2006,12(2-3):151-180.

[3]Luo C,Chung S.Efficient mining of maximal sequential patterns using multiple samples[C].Proceeding of the SIAM International Conference on Data Mining,2005:415-426.

[4]Pei J,Han J,Mortazavi-AslB,et al.Mining sequential patterns by pattern-growth:the prefixspan approach[J].IEEE Transactions on Knowledge and Data Engineering,2004,16(11):1424-1440.

[5]Kum H C,Paulsen S.Comparative study of sequential pattern mining models[J].Data Mining and Knowledge Discovery,2005,6:45-71.

[6]Xin D,Shen X,Mei Q,et al.Discovering interesting patterns through user's interactive feedback[C].Proceeding of the ACM SIGKDD International Conference on Knowledge Discovery in Databases,2006:773-778.

[7]Savary L,Zeitouni K.Indexed bit map for mining frequent sequences[C].9th European Conference on Principles and Practice of Knowledge Discovery in Databases,2005:51-76.

[8]Karine Zeitouni.From sequence mining to multidimensional sequence mining[R].http://www.prism.uvsq.fr/～karima/papers.

[9]Pinto H,Han J,Pei J,et al.Multidimensionnal sequential pattern mining[C].CIKM ACM,2001:81-88.

[10]纪兆辉,李存华.挖掘闭合多维序列模式的可行方法[J].计算机工程与设计,2009,30(22):5065-5067.

[11]XIAORen-cai,XUEAn-rong.Efficient algorithmofminingmulti-dimensionalsequential patterns[J].Computer Engineering and Applications,2008,44(6):187-190.

[12]Lionel Savary,Karine Zeitouni.Mining multidimensional sequential rules:a characterization based approach[C].IEEE MCD05,2005:99-102.

[13]Scott McGinnis,Thomas L.Madden BLAST:at the core of a powerful and diverse set of sequence analysis tools[J].Nucleic Acids Research,2004,32:20-25.

[14]Freschi V,Bogliolo A.Longuest common subsequence between run-length-encodedstrings:anewalgorithm withimproved parallelism[J].Elsevier Information Processing Letters,2004,90(4):167-173.

[15]Hyrum D Carroll.Biologically relevant multiple sequence alignment[D].Department of Computer Science,Brigham Young University,2008.