多維序列模式挖掘算法

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

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

0 引 言

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

1 基本定義

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

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

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

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

定義4 序列數(shù)據(jù)庫是由一系列的元組構(gòu)成，每個元組格式為(TID,S,A1,A2,…An)，其中TID為元組的標(biāo)號，用來標(biāo)識元組；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 給定一個相異度閾值 ∈Z，Z為整數(shù)，>0，如果Dissim(,)≤ ，則稱序列s，t為相似序列。

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

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

定義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ù)庫DB的一個子集，Supportse(propi(v))為第i個屬性的值為v在se中的支持度，定義為

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

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

2 MSP算法

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

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

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

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

2.1 挖掘最大頻繁序列

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

2.2 相異度計算

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

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

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

2.4 屬性選擇

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

2.5 規(guī)則化簡

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

2.6 MSP算法描述

//主程序

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

3 MSP性能分析

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

3.1 MSP算法的特點

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

3.2 MSP與MSRC運行時間的比較

MSP算法和MSRC算法主要的運行時間開銷體現(xiàn)在對序列項序列求最大頻繁模式以及對序列項序列與模式類進行比較這兩個過程上。設(shè)：

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

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

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

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

T1-MSP：MSP對序列項序列與模式類進行比較所花的時間

T1-MSRC：MSRC對序列項序列與模式類進行比較所花的時間

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

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

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

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

由此

因而

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

4 結(jié)束語

本文給出一種基于最大頻繁模式挖掘、模式相似與屬性描述相結(jié)合的多維序列模式挖掘算法MSP。通過相關(guān)閾值的設(shè)置以及采用模式類與序列項比較的新方法挖掘?qū)傩耘c各序列項之間的關(guān)系，以挖掘有意義的多維序列模式。對算法進行分析表明，MSP算法是有效的，且具有較好的可擴展性。該算法可以應(yīng)用到挖掘諸如空間多維序列以及多關(guā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].計算機工程與設(shè)計,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.