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

鄒 妍，劉 燕

（赤峰學(xué)院 計算機與信息工程學(xué)院，內(nèi)蒙古 赤峰 024000）

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

鄒 妍，劉 燕

（赤峰學(xué)院 計算機與信息工程學(xué)院，內(nèi)蒙古 赤峰 024000）

多維序列模式挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個重要分支.首先給出了多維序列模式挖掘的相關(guān)定義；其次對典型的多維序列模式挖掘算法進(jìn)行了總體歸納，并對在此基礎(chǔ)上發(fā)展起來的幾種多維序列模式挖掘算法的改良性能進(jìn)行了分析；最后展望其未來發(fā)展方向.

數(shù)據(jù)挖掘；多維序列模式；挖掘算法

1 引言

數(shù)據(jù)挖掘作為知識發(fā)現(xiàn)的核心步驟，旨在從海量數(shù)據(jù)中提取有效的、潛在有用的、易于理解的知識.序列模式挖掘是數(shù)據(jù)挖掘中非常重要的一個研究領(lǐng)域，最早是由R.Agrawal和R.Srikant在針對超市中購物籃數(shù)據(jù)的分析提出來的[1].這類模式有著廣泛的應(yīng)用，如客戶購買行為模式的分析、Web訪問模式的預(yù)測、疾病診斷、自然災(zāi)害預(yù)測、DNA序列分析等.多維序列模式挖掘是在序列模式挖掘基礎(chǔ)上考慮了其它一些維信息，像在顧客購買行為分析中考慮到顧客的年齡、性別等信息，這樣的模式融合了更多的信息，應(yīng)用價值更高.經(jīng)過多年的發(fā)展，對多維序列模式的研究取得了比較大的進(jìn)步，研究者們提出了很多性能良好的算法.本文首先對三種經(jīng)典多維序列模式挖掘算法進(jìn)行總體歸納，接著對在這三種經(jīng)典算法基礎(chǔ)上發(fā)展起來的Seq-mdp算法、MSP算法及基于單基2維概念格的多維序列模式挖掘算法（不妨稱之為TDCL-SB）進(jìn)行了分析總結(jié).最后對未來的研究重點進(jìn)行了展望.

2 多維序列模式挖掘相關(guān)定義

多維序列模式是從序列模式發(fā)展來的，是在序列模式一維挖掘的基礎(chǔ)上考慮了多維因素，使挖掘出的序列模式融合了更多的信息，具有更高的應(yīng)用價值[2].多維序列數(shù)據(jù)庫具有如下模式（RID，A1，…, Am，S），其中RID作為主鍵（Primary key）.A1，…,Am是維，S是數(shù)據(jù)序列域.以*作為元符號（meta-symbol）表示不屬于維A1，…,Am域的值.一個多維序列可表示為p=（a1，…，am，s），其中ai∈（Ai∪{*}）（1≤i≤m），s是一個序列.

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

定義1對于多維序列p=（a1，…，am，s）和數(shù)據(jù)庫元組t=（x1，…，xm，si），當(dāng)且僅當(dāng)ai=xi或ai=*（1≤i≤m），并且s?si時，稱t包含p.在多維序列數(shù)據(jù)庫S中，包含p的元組個數(shù)稱為p的支持?jǐn)?shù)，記為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-維模式.設(shè)有i-維模式Mi=（a1，…，am）和j-維模式Mj=（b1，…，bm），其中，若對于所有不為*的ak（1≤k≤m）一定有ak=bk，則稱Mi是Mj的一個子模式（sub-pattern），而Mj是Mi的一個父模式（super-pattern）.

多維序列模式挖掘的任務(wù)就是從多維序列模式數(shù)據(jù)庫中尋找出所有的滿足最小支持度的多維序列模式.一個多維序列數(shù)據(jù)庫實例如表1所示，它記錄了顧客的購買歷史及相關(guān)屬性.Tid為序列號，包含3個維，消費群體、城市和年齡.假定A,B,…,H為顧客所購買的項目.從表1可以看出，多維序列P=（*，赤峰，*，）被特集（1，商人，赤峰，中年，<(BD)CBA>），（2，自由職業(yè)者，赤峰，老年，<(BF) (CE)(FG)>）和（3，商人，赤峰，中年，<(AH)ABF>）所包含.P的支持度為3，如果給定的最小支持?jǐn)?shù)為2，則P是一個多維序列模式.

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

3.1 三種經(jīng)典多維序列模式挖掘算法

文獻(xiàn)[2]提出了三種經(jīng)典的多維序列模式挖掘算法：UniSeq，Seq-Dim和Dim-Seq.總體上，可以將多維序列模式挖掘算法劃分為兩類：一類是將多維分析方法和序列模式挖掘算法相結(jié)合的方法；另一類是先將多維信息集成到序列中，再對新集成的序列進(jìn)行挖掘.Seq-Dim和Dim-Seq屬于第一類，U-niSeq屬于后一類.

雖然，Seq-Dim和Dim-Seq屬于同一類算法，但是它們也有區(qū)別，關(guān)鍵在于處理步驟的順序不同.Seq-Dim算法的挖掘過程具有明確的目的性，先挖掘原始的序列模式，然后再利用BUC（Bottom-UP Computation）[3]算法挖掘序列投影數(shù)據(jù)庫的多維信息模式.由于在挖掘維度較高的多維模式時，BUC算法的效率要高于PreFixSpan算法[4]（該算法是Uniseq所采用的多維序列模式挖掘算法），因此，Seq-Dim算法在挖掘高維度的多維序列模式時更具優(yōu)勢.

而Dim-Seq算法則是先挖掘多維信息模式，再生成相應(yīng)的多維模式投影數(shù)據(jù)庫來挖掘序列模式.其缺點是顯而易見的，首先，在第一個步驟中產(chǎn)生的多維信息模式并不能產(chǎn)生多維序列模式，這就造成了大量的浪費.其次，該算法沒有對序列模式進(jìn)行優(yōu)化，當(dāng)出現(xiàn)高維度的情況時，該算法的執(zhí)行開銷會劇增.

UniSeq算法的基本思想是先把多維信息合并到序列數(shù)據(jù)庫中，再對新集成的序列數(shù)據(jù)庫進(jìn)行挖掘，最后利用經(jīng)典序列模式挖掘算法PreFixSpan對新的序列數(shù)據(jù)庫進(jìn)行挖掘.該算法的優(yōu)點是將所有的多維信息集成到序列數(shù)據(jù)庫中，容易實現(xiàn)和理解.且利用PreFixSpan算法，省去了在轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)過程及挖掘過程中的資源消耗.該算法適合于序列維度較低的情況.

3.2 Seq-mdp算法

從對三種經(jīng)典多維序列模式挖掘算法的分析中可以看出，Seq-Dim算法是較高效的一種算法.但該算法有缺點，由于在挖掘多維模式時要多次掃描投影數(shù)據(jù)庫，因此在維度高、數(shù)據(jù)量大時，時間開銷也大.因此，研究者在文獻(xiàn)[5]中提出了一種基于連接的多維序列模式挖掘算法（以下稱之為Seq-mdp）.

Seq-mdp算法與Seq-Dim算法的相似之處在于：也是先挖掘一般序列模式，再對每個序列模式生成該模式的維信息投影數(shù)據(jù)庫，然后再在投影數(shù)據(jù)庫中挖掘多維模式，從而得到多維序列模式.

與Seq-Dim算法相比，改進(jìn)的地方在于：挖掘多維模式時采用一種以空間換取時間的策略，減少了挖掘多維模式的時間.但是，由于需要空間記錄頻繁項的相關(guān)信息用于后續(xù)的連接，因而在空間上開銷較大.

從Seq-mdp算法的描述可以看出，只需掃描一次投影數(shù)據(jù)庫即可得到所有的多維模式.該算法主要是通過記錄支持每個頻繁1-項集的元組及其屬性的方法，所記錄的這些內(nèi)容以備后續(xù)連接之用.在掃描投影數(shù)據(jù)庫時，得到頻繁1-項集及上述相關(guān)信息，由頻繁（k-1）-項集（其中，k>1）做連接生成頻繁k-項集，再通過頻繁k-項集中的頻繁項就可以得到一個k-維模式，由此得到所有的k維模式.該算法減少了掃描投影數(shù)據(jù)庫的次數(shù)，只對不斷減小的頻繁（k-1）-項集掃描，在時間復(fù)雜度方面明顯優(yōu)于Seq-Dim算法.

3.3 MSP算法

文獻(xiàn)[6]通過設(shè)置閾值及對比模式類與序列項的方法提出了多維序列模式挖掘算法MSP.

MSP算法給出了規(guī)則的支持度及規(guī)則的確信度、帶有最小支持度閾值的頻繁規(guī)則、序列模式支持度閾值、兩序列的相異度、相似序列、多維序列規(guī)則及模式類的相關(guān)定義.算法包括三個步驟：通過設(shè)置序列模式的支持度閾值、序列相異度閾值及屬性的支持度閾值，挖掘數(shù)據(jù)集中的最大頻繁模式，求出各模式類所包含的屬性，根據(jù)屬性的支持度閾值確定哪些屬性用于生成多維規(guī)則的前件；比較數(shù)據(jù)中各序列項序列與各模式類的包含與相似關(guān)系；按照一定的規(guī)則抽取與各模式類相關(guān)的屬性，進(jìn)而對規(guī)則進(jìn)行相應(yīng)的化簡，給出以屬性為前件、模式類為后件的多維序列規(guī)則為形式的多維序列模式挖掘結(jié)果.

通過與文獻(xiàn)[7]提出的基于數(shù)據(jù)特性的多維序列模式挖掘算法MSRC在特點及運行時間上的比較，可以看出在規(guī)則冗余方面有了改進(jìn)，化簡的規(guī)則能更好的反映屬性與序列項序列之間的關(guān)系，能挖掘出更有意義的多維序列模式；另外，在時間復(fù)雜度上MSP算法更具優(yōu)勢，該算法更有效.且該算法可以應(yīng)用到空間多維序列及多關(guān)系多維序列模式的挖掘上，具有較好的可擴展性.

3.4 TDCL-SB

文獻(xiàn)[8]在多維概念格數(shù)據(jù)模型的基礎(chǔ)上，提出了多維序列模式的增量挖掘算法TDCL-SB.多維概念格是針對多維序列模式挖掘應(yīng)用而提出的新的數(shù)據(jù)結(jié)構(gòu)，是對概念格和有序概念格的泛化.文獻(xiàn)[7]提出的TDCL-SB算法通過增量式構(gòu)建單基2維概念格來發(fā)現(xiàn)多維序列模式.有了多維格這種新的數(shù)據(jù)結(jié)構(gòu)，使得整個挖掘過程變得高效，無論是有序信息維，還是無序信息維，其處理都是在多維格結(jié)構(gòu)上進(jìn)行的，而無需像傳統(tǒng)算法那樣針對不同的數(shù)據(jù)結(jié)構(gòu)采用不同的處理策略，另外，該算法僅需掃描一次數(shù)據(jù)庫，并具有較好的增量特性.TDCL-SB算法在某銀行信用卡客戶的交易數(shù)據(jù)集上作了實際驗證，實驗結(jié)果表明，該算法具有以下優(yōu)點：

（1）采用統(tǒng)一的數(shù)據(jù)模型實現(xiàn)一般序列模式與關(guān)聯(lián)模式的高效同步挖掘；

（2）算法具有增量特性，適用于數(shù)據(jù)集更新頻繁或用戶無法預(yù)先確定最小支持度約束范圍的應(yīng)用場合；

（3）算法生成的是具有實際應(yīng)用價值的最大頻繁序列模式.

4 總結(jié)

自多維序列模式挖掘的概念及經(jīng)典算法提出以來，經(jīng)過近些年的發(fā)展，多維序列模式挖掘研究取得了較大的進(jìn)展，但仍然存在一些問題，比如與相關(guān)領(lǐng)域知識的結(jié)合不夠，針對海量數(shù)據(jù)時間開銷大、算法效率不高等.這些都是下一步需要解決的問題.多維序列模式挖掘有著廣闊的應(yīng)用前景，如何進(jìn)一步提高算法的挖掘性能，以及如何加入一些時間和分類等約束，是有待于進(jìn)一步研究的問題.

〔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〕肖仁財.序列模式挖掘算法研究與實現(xiàn)[D].江蘇大學(xué),2007.17-30.

〔6〕李廣原,楊炳儒，等.多維序列模式挖掘算法[J].計算機工程與設(shè)計,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].計算機研究與發(fā)展,2007,44(11):1818-1824.

TP311.13

A

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

內(nèi)蒙古自治區(qū)自然科學(xué)基金項目資助（2011MS0914）