鄒 妍,劉 燕
(赤峰學(xué)院 計(jì)算機(jī)與信息工程學(xué)院,內(nèi)蒙古 赤峰 024000)
多維序列模式挖掘算法分析
鄒 妍,劉 燕
(赤峰學(xué)院 計(jì)算機(jī)與信息工程學(xué)院,內(nèi)蒙古 赤峰 024000)
多維序列模式挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要分支.首先給出了多維序列模式挖掘的相關(guān)定義;其次對(duì)典型的多維序列模式挖掘算法進(jìn)行了總體歸納,并對(duì)在此基礎(chǔ)上發(fā)展起來(lái)的幾種多維序列模式挖掘算法的改良性能進(jìn)行了分析;最后展望其未來(lái)發(fā)展方向.
數(shù)據(jù)挖掘;多維序列模式;挖掘算法
數(shù)據(jù)挖掘作為知識(shí)發(fā)現(xiàn)的核心步驟,旨在從海量數(shù)據(jù)中提取有效的、潛在有用的、易于理解的知識(shí).序列模式挖掘是數(shù)據(jù)挖掘中非常重要的一個(gè)研究領(lǐng)域,最早是由R.Agrawal和R.Srikant在針對(duì)超市中購(gòu)物籃數(shù)據(jù)的分析提出來(lái)的[1].這類模式有著廣泛的應(yīng)用,如客戶購(gòu)買行為模式的分析、Web訪問模式的預(yù)測(cè)、疾病診斷、自然災(zāi)害預(yù)測(cè)、DNA序列分析等.多維序列模式挖掘是在序列模式挖掘基礎(chǔ)上考慮了其它一些維信息,像在顧客購(gòu)買行為分析中考慮到顧客的年齡、性別等信息,這樣的模式融合了更多的信息,應(yīng)用價(jià)值更高.經(jīng)過(guò)多年的發(fā)展,對(duì)多維序列模式的研究取得了比較大的進(jìn)步,研究者們提出了很多性能良好的算法.本文首先對(duì)三種經(jīng)典多維序列模式挖掘算法進(jìn)行總體歸納,接著對(duì)在這三種經(jīng)典算法基礎(chǔ)上發(fā)展起來(lái)的Seq-mdp算法、MSP算法及基于單基2維概念格的多維序列模式挖掘算法(不妨稱之為TDCL-SB)進(jìn)行了分析總結(jié).最后對(duì)未來(lái)的研究重點(diǎn)進(jìn)行了展望.
多維序列模式是從序列模式發(fā)展來(lái)的,是在序列模式一維挖掘的基礎(chǔ)上考慮了多維因素,使挖掘出的序列模式融合了更多的信息,具有更高的應(yīng)用價(jià)值[2].多維序列數(shù)據(jù)庫(kù)具有如下模式(RID,A1,…, Am,S),其中RID作為主鍵(Primary key).A1,…,Am是維,S是數(shù)據(jù)序列域.以*作為元符號(hào)(meta-symbol)表示不屬于維A1,…,Am域的值.一個(gè)多維序列可表示為p=(a1,…,am,s),其中ai∈(Ai∪{*})(1≤i≤m),s是一個(gè)序列.
表1 多維序列數(shù)據(jù)庫(kù)實(shí)例
定義1對(duì)于多維序列p=(a1,…,am,s)和數(shù)據(jù)庫(kù)元組t=(x1,…,xm,si),當(dāng)且僅當(dāng)ai=xi或ai=*(1≤i≤m),并且s?si時(shí),稱t包含p.在多維序列數(shù)據(jù)庫(kù)S中,包含p的元組個(gè)數(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個(gè)(n≤m)不是*,則稱M是一個(gè)n-維模式.設(shè)有i-維模式Mi=(a1,…,am)和j-維模式Mj=(b1,…,bm),其中,若對(duì)于所有不為*的ak(1≤k≤m)一定有ak=bk,則稱Mi是Mj的一個(gè)子模式(sub-pattern),而Mj是Mi的一個(gè)父模式(super-pattern).
多維序列模式挖掘的任務(wù)就是從多維序列模式數(shù)據(jù)庫(kù)中尋找出所有的滿足最小支持度的多維序列模式.一個(gè)多維序列數(shù)據(jù)庫(kù)實(shí)例如表1所示,它記錄了顧客的購(gòu)買歷史及相關(guān)屬性.Tid為序列號(hào),包含3個(gè)維,消費(fèi)群體、城市和年齡.假定A,B,…,H為顧客所購(gòu)買的項(xiàng)目.從表1可以看出,多維序列P=(*,赤峰,*,)被特集(1,商人,赤峰,中年,<(BD)CBA>),(2,自由職業(yè)者,赤峰,老年,<(BF) (CE)(FG)>)和(3,商人,赤峰,中年,<(AH)ABF>)所包含.P的支持度為3,如果給定的最小支持?jǐn)?shù)為2,則P是一個(gè)多維序列模式.
3.1 三種經(jīng)典多維序列模式挖掘算法
文獻(xiàn)[2]提出了三種經(jīng)典的多維序列模式挖掘算法:UniSeq,Seq-Dim和Dim-Seq.總體上,可以將多維序列模式挖掘算法劃分為兩類:一類是將多維分析方法和序列模式挖掘算法相結(jié)合的方法;另一類是先將多維信息集成到序列中,再對(duì)新集成的序列進(jìn)行挖掘.Seq-Dim和Dim-Seq屬于第一類,U-niSeq屬于后一類.
雖然,Seq-Dim和Dim-Seq屬于同一類算法,但是它們也有區(qū)別,關(guān)鍵在于處理步驟的順序不同.Seq-Dim算法的挖掘過(guò)程具有明確的目的性,先挖掘原始的序列模式,然后再利用BUC(Bottom-UP Computation)[3]算法挖掘序列投影數(shù)據(jù)庫(kù)的多維信息模式.由于在挖掘維度較高的多維模式時(shí),BUC算法的效率要高于PreFixSpan算法[4](該算法是Uniseq所采用的多維序列模式挖掘算法),因此,Seq-Dim算法在挖掘高維度的多維序列模式時(shí)更具優(yōu)勢(shì).
而Dim-Seq算法則是先挖掘多維信息模式,再生成相應(yīng)的多維模式投影數(shù)據(jù)庫(kù)來(lái)挖掘序列模式.其缺點(diǎn)是顯而易見的,首先,在第一個(gè)步驟中產(chǎn)生的多維信息模式并不能產(chǎn)生多維序列模式,這就造成了大量的浪費(fèi).其次,該算法沒有對(duì)序列模式進(jìn)行優(yōu)化,當(dāng)出現(xiàn)高維度的情況時(shí),該算法的執(zhí)行開銷會(huì)劇增.
UniSeq算法的基本思想是先把多維信息合并到序列數(shù)據(jù)庫(kù)中,再對(duì)新集成的序列數(shù)據(jù)庫(kù)進(jìn)行挖掘,最后利用經(jīng)典序列模式挖掘算法PreFixSpan對(duì)新的序列數(shù)據(jù)庫(kù)進(jìn)行挖掘.該算法的優(yōu)點(diǎn)是將所有的多維信息集成到序列數(shù)據(jù)庫(kù)中,容易實(shí)現(xiàn)和理解.且利用PreFixSpan算法,省去了在轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)過(guò)程及挖掘過(guò)程中的資源消耗.該算法適合于序列維度較低的情況.
3.2 Seq-mdp算法
從對(duì)三種經(jīng)典多維序列模式挖掘算法的分析中可以看出,Seq-Dim算法是較高效的一種算法.但該算法有缺點(diǎn),由于在挖掘多維模式時(shí)要多次掃描投影數(shù)據(jù)庫(kù),因此在維度高、數(shù)據(jù)量大時(shí),時(shí)間開銷也大.因此,研究者在文獻(xiàn)[5]中提出了一種基于連接的多維序列模式挖掘算法(以下稱之為Seq-mdp).
Seq-mdp算法與Seq-Dim算法的相似之處在于:也是先挖掘一般序列模式,再對(duì)每個(gè)序列模式生成該模式的維信息投影數(shù)據(jù)庫(kù),然后再在投影數(shù)據(jù)庫(kù)中挖掘多維模式,從而得到多維序列模式.
與Seq-Dim算法相比,改進(jìn)的地方在于:挖掘多維模式時(shí)采用一種以空間換取時(shí)間的策略,減少了挖掘多維模式的時(shí)間.但是,由于需要空間記錄頻繁項(xiàng)的相關(guān)信息用于后續(xù)的連接,因而在空間上開銷較大.
從Seq-mdp算法的描述可以看出,只需掃描一次投影數(shù)據(jù)庫(kù)即可得到所有的多維模式.該算法主要是通過(guò)記錄支持每個(gè)頻繁1-項(xiàng)集的元組及其屬性的方法,所記錄的這些內(nèi)容以備后續(xù)連接之用.在掃描投影數(shù)據(jù)庫(kù)時(shí),得到頻繁1-項(xiàng)集及上述相關(guān)信息,由頻繁(k-1)-項(xiàng)集(其中,k>1)做連接生成頻繁k-項(xiàng)集,再通過(guò)頻繁k-項(xiàng)集中的頻繁項(xiàng)就可以得到一個(gè)k-維模式,由此得到所有的k維模式.該算法減少了掃描投影數(shù)據(jù)庫(kù)的次數(shù),只對(duì)不斷減小的頻繁(k-1)-項(xiàng)集掃描,在時(shí)間復(fù)雜度方面明顯優(yōu)于Seq-Dim算法.
3.3 MSP算法
文獻(xiàn)[6]通過(guò)設(shè)置閾值及對(duì)比模式類與序列項(xiàng)的方法提出了多維序列模式挖掘算法MSP.
MSP算法給出了規(guī)則的支持度及規(guī)則的確信度、帶有最小支持度閾值的頻繁規(guī)則、序列模式支持度閾值、兩序列的相異度、相似序列、多維序列規(guī)則及模式類的相關(guān)定義.算法包括三個(gè)步驟:通過(guò)設(shè)置序列模式的支持度閾值、序列相異度閾值及屬性的支持度閾值,挖掘數(shù)據(jù)集中的最大頻繁模式,求出各模式類所包含的屬性,根據(jù)屬性的支持度閾值確定哪些屬性用于生成多維規(guī)則的前件;比較數(shù)據(jù)中各序列項(xiàng)序列與各模式類的包含與相似關(guān)系;按照一定的規(guī)則抽取與各模式類相關(guān)的屬性,進(jìn)而對(duì)規(guī)則進(jìn)行相應(yīng)的化簡(jiǎn),給出以屬性為前件、模式類為后件的多維序列規(guī)則為形式的多維序列模式挖掘結(jié)果.
通過(guò)與文獻(xiàn)[7]提出的基于數(shù)據(jù)特性的多維序列模式挖掘算法MSRC在特點(diǎn)及運(yùn)行時(shí)間上的比較,可以看出在規(guī)則冗余方面有了改進(jìn),化簡(jiǎn)的規(guī)則能更好的反映屬性與序列項(xiàng)序列之間的關(guān)系,能挖掘出更有意義的多維序列模式;另外,在時(shí)間復(fù)雜度上MSP算法更具優(yōu)勢(shì),該算法更有效.且該算法可以應(yīng)用到空間多維序列及多關(guān)系多維序列模式的挖掘上,具有較好的可擴(kuò)展性.
3.4 TDCL-SB
文獻(xiàn)[8]在多維概念格數(shù)據(jù)模型的基礎(chǔ)上,提出了多維序列模式的增量挖掘算法TDCL-SB.多維概念格是針對(duì)多維序列模式挖掘應(yīng)用而提出的新的數(shù)據(jù)結(jié)構(gòu),是對(duì)概念格和有序概念格的泛化.文獻(xiàn)[7]提出的TDCL-SB算法通過(guò)增量式構(gòu)建單基2維概念格來(lái)發(fā)現(xiàn)多維序列模式.有了多維格這種新的數(shù)據(jù)結(jié)構(gòu),使得整個(gè)挖掘過(guò)程變得高效,無(wú)論是有序信息維,還是無(wú)序信息維,其處理都是在多維格結(jié)構(gòu)上進(jìn)行的,而無(wú)需像傳統(tǒng)算法那樣針對(duì)不同的數(shù)據(jù)結(jié)構(gòu)采用不同的處理策略,另外,該算法僅需掃描一次數(shù)據(jù)庫(kù),并具有較好的增量特性.TDCL-SB算法在某銀行信用卡客戶的交易數(shù)據(jù)集上作了實(shí)際驗(yàn)證,實(shí)驗(yàn)結(jié)果表明,該算法具有以下優(yōu)點(diǎn):
(1)采用統(tǒng)一的數(shù)據(jù)模型實(shí)現(xiàn)一般序列模式與關(guān)聯(lián)模式的高效同步挖掘;
(2)算法具有增量特性,適用于數(shù)據(jù)集更新頻繁或用戶無(wú)法預(yù)先確定最小支持度約束范圍的應(yīng)用場(chǎng)合;
(3)算法生成的是具有實(shí)際應(yīng)用價(jià)值的最大頻繁序列模式.
自多維序列模式挖掘的概念及經(jīng)典算法提出以來(lái),經(jīng)過(guò)近些年的發(fā)展,多維序列模式挖掘研究取得了較大的進(jìn)展,但仍然存在一些問題,比如與相關(guān)領(lǐng)域知識(shí)的結(jié)合不夠,針對(duì)海量數(shù)據(jù)時(shí)間開銷大、算法效率不高等.這些都是下一步需要解決的問題.多維序列模式挖掘有著廣闊的應(yīng)用前景,如何進(jìn)一步提高算法的挖掘性能,以及如何加入一些時(shí)間和分類等約束,是有待于進(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〕肖仁財(cái).序列模式挖掘算法研究與實(shí)現(xiàn)[D].江蘇大學(xué),2007.17-30.
〔6〕李廣原,楊炳儒,等.多維序列模式挖掘算法[J].計(jì)算機(jī)工程與設(shè)計(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〕金陽(yáng),左萬(wàn)利.多維概念格與多維序列模式的增量挖掘[J].計(jì)算機(jī)研究與發(fā)展,2007,44(11):1818-1824.
TP311.13
A
1673-260X(2014)04-0034-03
內(nèi)蒙古自治區(qū)自然科學(xué)基金項(xiàng)目資助(2011MS0914)