多維序列模式挖掘算法

李廣原， 楊炳儒， 劉永彬， 劉英華

(1.北京科技大學(xué)信息工程學(xué)院，北京100083；2.廣西師范學(xué)院計(jì)算機(jī)與信息工程學(xué)院，廣西南寧530023)

0 引 言

序列模式挖掘是數(shù)據(jù)挖掘的一個(gè)重要方向，有著廣泛的應(yīng)用。人們已提出了不少的序列模式挖掘算法[1-7]，大多數(shù)現(xiàn)有的序列模式挖掘算法是針對(duì)一維數(shù)據(jù)來(lái)挖掘，并沒(méi)有考慮這些模式與多維數(shù)據(jù)的相關(guān)性，因而可能會(huì)遺漏一些重要信息的挖掘。而多維序列模式挖掘[8-11]考慮多維數(shù)據(jù)之間的相關(guān)性，因而能夠發(fā)現(xiàn)更多有關(guān)聯(lián)、有價(jià)值的模式。文獻(xiàn)[12]提出了一種基于數(shù)據(jù)特性的多維序列模式挖掘算法，它是以規(guī)則的形式給出多維序列模式的挖掘結(jié)果，該算法沒(méi)有設(shè)定屬性的支持度，得出大量的規(guī)則，而有些規(guī)則存在著冗余，可以進(jìn)行化簡(jiǎn)，因而不能完全反映屬性與序列項(xiàng)序列之間的關(guān)系，此外，如果所挖掘的最大頻繁模式數(shù)目以及在屬性較多的情況下，則挖掘過(guò)程十分耗時(shí)。本文給出一種新的多維序列模式挖掘算法，通過(guò)相關(guān)閾值的設(shè)置以及采用模式類與序列項(xiàng)比較的新方法挖掘?qū)傩耘c各序列項(xiàng)之間的關(guān)系，能夠有效地發(fā)現(xiàn)多屬性與序列模式間的關(guān)系，以挖掘潛在有意義的模式。事實(shí)證明，該算法是有效的，且具有較好的可擴(kuò)展性。

1 基本定義

設(shè)I是一個(gè)項(xiàng)的集合，集合X={1,2,…,}I稱為一個(gè)項(xiàng)集，由于它包含k個(gè)項(xiàng)，所以稱為k項(xiàng)集。建立在項(xiàng)集I上的事務(wù)T，記T=(tid,I)，其中tid是事務(wù)的標(biāo)識(shí)。項(xiàng)集X的支持度Support(X,D)是指在事務(wù)數(shù)據(jù)庫(kù)D中包含X的事務(wù)的個(gè)數(shù)，規(guī)則X Y的支持度是Support(X∪Y)，規(guī)則X Y的確信度是

定義1 設(shè)D是一個(gè)事務(wù)數(shù)據(jù)庫(kù)，I是項(xiàng)的集合，是最小支持度閾值，是最小確信度，D中的頻繁項(xiàng)集記作

定義2 設(shè)D是一個(gè)事務(wù)數(shù)據(jù)庫(kù)，I是項(xiàng)的集合，是最小支持度閾值，是最小確信度，則D中的滿足最小支持度和最小確信度的頻繁規(guī)則記作

定義3 設(shè)I是項(xiàng)的集合，序列s=<1,2,…,>定義為一個(gè)有序的項(xiàng)，其中 ∈I，i=1,2,…,n。這里，假設(shè) 僅由一個(gè)單項(xiàng)構(gòu)成。

定義4 序列數(shù)據(jù)庫(kù)是由一系列的元組構(gòu)成，每個(gè)元組格式為(TID,S,A1,A2,…An)，其中TID為元組的標(biāo)號(hào)，用來(lái)標(biāo)識(shí)元組；S為序列名稱；A1，A2，…An分別為屬性1至屬性n的名稱。

定義5 序列s=<1,2,…,>為序列t=<1,2,…,>的子序列，如果存在整數(shù) 1≤j1

定義6 設(shè)s是D中一序列，如果Support(s,D)≥ ，則s是一頻繁序列，是序列模式支持度閾值。

定義 7[12]設(shè)序列 s=，t=，n≥m，另設(shè)lcs(,)為兩序列的最大公共子序列，兩序列的相異度定義為Dissim(,)=n+m-2 lcs(,)。

定義8 給定一個(gè)相異度閾值 ∈Z，Z為整數(shù)，>0，如果Dissim(,)≤ ，則稱序列s，t為相似序列。

定義9 一個(gè)多維序列數(shù)據(jù)庫(kù)可以表示為(TID,S,A1,A2,…An)，其中TID為事務(wù)的關(guān)鍵字，S為序列項(xiàng)的名稱，s1,s2,…,sn為序列項(xiàng)序列，A1,A2,…,An為多維數(shù)據(jù)的屬性名，a1,a2,…,an分別是其屬性值，一個(gè)多維序列定義為(tid,s,a1,a2,…,an)，多維序列數(shù)據(jù)庫(kù)如表1所示。

表1 多維序列數(shù)據(jù)庫(kù)

定義10 多維序列規(guī)則是形如(a1,a2,…,an)(s1,s2,…,sm)的關(guān)聯(lián)規(guī)則，其中(a1,a2,…,an)代表多維數(shù)據(jù)的屬性值，(s1,s2,…,sm)代表序列模式。

定義11 設(shè)se為數(shù)據(jù)庫(kù)DB的一個(gè)子集，Supportse(propi(v))為第i個(gè)屬性的值為v在se中的支持度，定義為

Suppportse(propi(v))=cardse(propi(v))/card(se)用于描述多維序列規(guī)則的屬性，其支持度大于或等于給定的閾值 。

定義12 設(shè)Sc為某些序列模式SPc的模式類，定義多維序列規(guī)則為

2 MSP算法

為挖掘多維序列規(guī)則，提出了基于序列聚類與屬性描述相結(jié)合的多維序列模式挖掘算法MSP，算法包括以下3個(gè)步驟：

(1)挖掘序列項(xiàng)中的最大頻繁序列。每個(gè)最大頻繁序列即構(gòu)成一個(gè)模式類，一個(gè)模式類就是一條多維序列規(guī)則的后件。

(2)根據(jù)序列的包含與相似度計(jì)算式，對(duì)數(shù)據(jù)庫(kù)中的每一序列項(xiàng)序列與上述各模式類進(jìn)行比較，為每個(gè)模式類記下序列項(xiàng)序列所在事務(wù)的標(biāo)號(hào)，為下一步處理相關(guān)屬性做準(zhǔn)備。

(3)經(jīng)過(guò)步驟(2)處理后，對(duì)應(yīng)于每一模式類，根據(jù)其包含的所有事務(wù)標(biāo)號(hào)，取所有對(duì)應(yīng)的事務(wù)屬性進(jìn)行相應(yīng)的屬性支持度計(jì)算，取支持度大于給定閾值的屬性作為描述多維序列規(guī)則的屬性，產(chǎn)生多維序列規(guī)則并進(jìn)行化簡(jiǎn)。

2.1 挖掘最大頻繁序列

目前已提出了不少的挖掘最大頻繁序列算法，常用的算法有：GSP算法、PrefixSpan算法、SPADE算法等。對(duì)于長(zhǎng)序列模式挖掘，可以采用文獻(xiàn)[7]介紹的算法，該算法具有較好的擴(kuò)展性能，且只需掃描一次數(shù)據(jù)庫(kù)，采用有效的數(shù)據(jù)結(jié)構(gòu)能夠快速提高挖掘速度和節(jié)省存儲(chǔ)開(kāi)銷。

2.2 相異度計(jì)算

序列相似度計(jì)算在生物信息學(xué)中有著重要的應(yīng)用，DNA和蛋白質(zhì)序列是基本生物學(xué)數(shù)據(jù)，通過(guò)開(kāi)發(fā)有效的方法來(lái)比較和比對(duì)生物序列并發(fā)現(xiàn)生物序物模式非常重要，為了比對(duì)DNA序列的相似性，人們提出了一些有效的算法，如BLAST[13]、FASTA[14]、LCSS[15]。我們采用LCSS算法來(lái)對(duì)序列進(jìn)行比較，它通過(guò)計(jì)算把序列s1轉(zhuǎn)換成序列s2所需要的最小的刪除、插入相關(guān)的項(xiàng)數(shù)。采用定義7計(jì)算公式，比如，設(shè)有兩個(gè)序列：s1=，s2=，其最大子序列為：，(這里不考慮它們之間的項(xiàng)，只考慮它們的出現(xiàn)次序)則它們的相異度為4，相異度越小，說(shuō)明兩序列越相似。

2.3 支持類的事務(wù)選擇

在挖掘最大頻繁序列后，即生成了多維序列規(guī)則中后件每個(gè)最大頻繁序列可作為模式的一類，數(shù)據(jù)庫(kù)中的每一個(gè)序列項(xiàng)中的序列分別和這些模式類相比較，對(duì)于某一序列項(xiàng)序列，如果它包含某個(gè)模式類，則它屬于支持該模式類，如果它同時(shí)包含多個(gè)模式類，則它同時(shí)支持多個(gè)模式類，如果它不包含任何模式類，則利用定義7、8和各個(gè)模式類進(jìn)行相異度計(jì)算，支持所有滿足相異度閾值模式類。上述操作，一旦某個(gè)序列項(xiàng)序列支持某個(gè)模式類后，便記下它所在事務(wù)的標(biāo)號(hào)。

2.4 屬性選擇

當(dāng)每個(gè)模式類所支持的事務(wù)確定后，便需要選擇哪些屬性來(lái)對(duì)多維序列規(guī)則進(jìn)行描述，這里涉及到兩個(gè)問(wèn)題：一是屬性的選擇，二是屬性值的取值，第一個(gè)問(wèn)題可以根據(jù)定義11來(lái)確定，也就是選擇支持度要大于給定閾值的屬性，第二個(gè)問(wèn)題，對(duì)于二元屬性和數(shù)值屬性，直接取值即可，而對(duì)于區(qū)間值屬性，可以取它們區(qū)間相交值作為確定的值。

2.5 規(guī)則化簡(jiǎn)

經(jīng)過(guò)前面幾步后，可得到形如(a1,a2,…,an)(s1,s2,…,sm)的多維序列規(guī)則，在這里，(s1,s2,…,sm)是最大頻繁模式，如果所生成的模式比較多，這時(shí)可根據(jù)屬性間的關(guān)聯(lián)(如果有)進(jìn)行適當(dāng)?shù)幕?jiǎn)，特別是當(dāng)多維屬性個(gè)數(shù)比較多的情況下。如果屬性集{A{B}，{}，{{a1,a2,…,an}，則多維序列規(guī)則(a1,a2,{A},…{B},…,an)(s1,s2,…,sm)可化簡(jiǎn)為(a1,a2,{A},…,an)(s1,s2,…,sm)。

2.6 MSP算法描述

//主程序

//為序列模式的支持度閾值；為序列相異度閾值；為屬性的支持度閾值。

3 MSP性能分析

為評(píng)價(jià)MSP算法的性能，我們選用文獻(xiàn)[12]給出的算法(不妨稱為MSRC)作為比較的對(duì)象，因?yàn)镸SRC算法已成功地在一個(gè)真實(shí)數(shù)據(jù)集上進(jìn)行測(cè)試，并且MSP和MSRC輸出結(jié)果的形式都是多維序列規(guī)則。

3.1 MSP算法的特點(diǎn)

MSP有如下特點(diǎn)：①可以根據(jù)用戶指定的條件控制輸出規(guī)則的數(shù)目，這是由于設(shè)置了屬性的支持度閾值。②MSP算法生成的規(guī)則，MSRC算法不能全部生成，這是因?yàn)樵谒惴∕SP中，數(shù)據(jù)庫(kù)中每個(gè)序列項(xiàng)序列并不是唯一歸于某一模式類，而是根據(jù)包含或相異度閾值來(lái)確定，它們可同時(shí)屬于多個(gè)模式類，而算法MSRC只規(guī)定每個(gè)序列項(xiàng)序列僅屬于與其最相似的模式類，每個(gè)模式類包含的序列項(xiàng)直接影響規(guī)則前件的構(gòu)成。③MSP算法根據(jù)屬性之間存在著的關(guān)聯(lián)，可以對(duì)規(guī)則進(jìn)行相應(yīng)的化簡(jiǎn)。

3.2 MSP與MSRC運(yùn)行時(shí)間的比較

MSP算法和MSRC算法主要的運(yùn)行時(shí)間開(kāi)銷體現(xiàn)在對(duì)序列項(xiàng)序列求最大頻繁模式以及對(duì)序列項(xiàng)序列與模式類進(jìn)行比較這兩個(gè)過(guò)程上。設(shè)：

TMSP：MSP 執(zhí)行的總時(shí)間

TMSRC：MSRC執(zhí)行的總時(shí)間

T0-MSP：MSP求最大頻繁模式所花的時(shí)間

T0-MSRC：MSRC求最大頻繁模式所花的時(shí)間

T1-MSP：MSP對(duì)序列項(xiàng)序列與模式類進(jìn)行比較所花的時(shí)間

T1-MSRC：MSRC對(duì)序列項(xiàng)序列與模式類進(jìn)行比較所花的時(shí)間

T0(X，Y)：逐個(gè)判斷X個(gè)序列中的每個(gè)序列是否包含Y個(gè)序列中的每個(gè)序列所花的時(shí)間

T1(X，Y)：逐個(gè)求出X個(gè)序列中的每個(gè)序列與Y個(gè)序列中的每個(gè)序列存在的最大公子串所花的時(shí)間，則

又假設(shè)數(shù)據(jù)庫(kù)共有N個(gè)事務(wù)數(shù)，一個(gè)序列項(xiàng)，序列項(xiàng)序列中存在M個(gè)最大頻繁模式，即M個(gè)模式類，則

由于求兩個(gè)序列是否存在包含關(guān)系所需的時(shí)間比求兩個(gè)序列的最大公共子串所花的時(shí)間要小得多，即T1(X,Y)>T0(X,Y)。

由此

因而

根據(jù)式(1)～式(7)得

4 結(jié)束語(yǔ)

本文給出一種基于最大頻繁模式挖掘、模式相似與屬性描述相結(jié)合的多維序列模式挖掘算法MSP。通過(guò)相關(guān)閾值的設(shè)置以及采用模式類與序列項(xiàng)比較的新方法挖掘?qū)傩耘c各序列項(xiàng)之間的關(guān)系，以挖掘有意義的多維序列模式。對(duì)算法進(jìn)行分析表明，MSP算法是有效的，且具有較好的可擴(kuò)展性。該算法可以應(yīng)用到挖掘諸如空間多維序列以及多關(guān)系多維序列模式上，進(jìn)一步提高算法的挖掘性能是下一步要研究的方向。

[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ì)兆輝,李存華.挖掘閉合多維序列模式的可行方法[J].計(jì)算機(jī)工程與設(shè)計(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.