基于位置信息的序列模式挖掘算法

(西北工業(yè)大學(xué) 計算機(jī)學(xué)院， 西安 710072)



摘 要：PrefixSpan算法在產(chǎn)生頻繁序列模式時會產(chǎn)生大量的投影數(shù)據(jù)庫，其中很多投影數(shù)據(jù)庫是相同的。提出了基于位置信息的序列模式挖掘算法——PVS，該方法通過記錄每個已產(chǎn)生投影數(shù)據(jù)庫的位置信息，避免了重復(fù)產(chǎn)生相同的投影數(shù)據(jù)庫，從而提高了算法的運(yùn)行效率。通過實(shí)驗證明，該算法在處理相似度很高的序列數(shù)據(jù)時比PrefixSpan算法有效。

關(guān)鍵詞：前綴；序列模式；投影數(shù)據(jù)庫；位置信息

中圖分類號：TP311 文獻(xiàn)標(biāo)志碼：A

文章編號：10013695(2009)02052903



Position valuebased sequential pattern mining algorithm



ZHANG Lijun， LI Zhanhuai， WANG Miao

(School of Computer， Northwestern Polytechnical University， Xi’an 710072， China)

Abstract:More project databases are produced when PrefixSpan mines frequent sequential patterns.This paper developed the position valuebased sequential pattern mining approach， PVS， which could produce all the sequential patterns without candidate set. And it also recorded the position value of each produced project database， escape of producing the same project database. The experiment shows PVS is more feasible and efficient than PrefixSpan when dealing similar sequential database.Key words:prefix; sequential pattern; project database; position value



0 引言

序列模式挖掘是數(shù)據(jù)挖掘中的重要組成部分，它是從序列數(shù)據(jù)庫中挖掘出滿足用戶要求的子序列作為頻繁模式，這些子序列具有時序性的特點(diǎn)。近幾年序列模式挖掘研究發(fā)展迅速，并廣泛應(yīng)用于多個領(lǐng)域，如顧客購買行為的分析、網(wǎng)絡(luò)訪問模式分析、科學(xué)實(shí)驗數(shù)據(jù)的分析、DNA序列的破譯、蛋白質(zhì)功能預(yù)測等方面。

序列模式首先是由R. Agrawal等人[1]提出的，隨后所提出的算法都是基于Apriori原理的改進(jìn)算法。Zaki[2]提出了基于垂直數(shù)據(jù)表示的SPADE算法。Han等人[3]提出了不產(chǎn)生候選集的基于模式增長的FPgrowth算法，接著他們又研究出了基于投影數(shù)據(jù)庫的FreeSpan[4]和PrefixSpan[5]算法。但是，上述算法所產(chǎn)生的頻繁模式眾多，其中有很多冗余模式存在。因此，在某些場合下不需要挖掘出完全的頻繁模式集，而是去挖掘出具有相同表達(dá)能力、卻有更加簡潔形式和較小數(shù)量的閉合頻繁模式集。Pasquier等人[6]首先提出了頻繁閉合模式的概念。一個頻繁模式是閉合頻繁模式，當(dāng)且僅當(dāng)沒有與其具有相同支持度的超集存在。隨后，Pei等人[7]提出了基于FPgrowth的CLOSET算法；Wang等人[8]在CLOSET的基礎(chǔ)上提出了CLOSET+算法。Burdick 等人[9]提出的深度優(yōu)先搜索算法MAFIA采用垂直二進(jìn)制位圖表示模式支持集。Yan等人[10]在投影數(shù)據(jù)庫方法的基礎(chǔ)上提出了CloSpan算法。Zaki等人[11]采用垂直數(shù)據(jù)表示的方法提出了CHARM算法。

從上述序列模式挖掘算法的發(fā)展過程可以看到，傳統(tǒng)的Apriori類算法由于受到其自身不可避免的缺點(diǎn)限制，已經(jīng)被以PrefixSpan算法為代表的基于模式增長的方法所替代。但是，PrefixSpan算法也有其缺點(diǎn)，即在產(chǎn)生頻繁模式的同時，可能會產(chǎn)生出大量的重復(fù)投影數(shù)據(jù)庫，對算法的性能有所影響。如果能夠避免產(chǎn)生重復(fù)的投影數(shù)據(jù)庫，則可以在一定程度上提高算法的效率。為此，本文提出了基于位置信息的序列模式挖掘算法——PVS（position valuebased sequential pattern mining），該方法能有效地避免重復(fù)投影數(shù)據(jù)庫的產(chǎn)生，從而提高算法的效率。尤其對相似度很高的序列數(shù)據(jù)進(jìn)行頻繁模式挖掘，PVS的效率遠(yuǎn)比PrefixSpan高，產(chǎn)生的投影數(shù)據(jù)庫數(shù)量也遠(yuǎn)遠(yuǎn)小于PrefixSpan算法。

1 問題描述

設(shè)I={i1，i2，…，im}是項集，ik(1≤k≤m)是一個項。序列S記為S=〈s1s2…sn〉，其中sj(1≤j≤n)為項集，稱為序列S的元素。序列包含的項的個數(shù)稱為序列的長度，長度為k的序列記為k序列。設(shè)α=〈a1a2…an〉，β=〈b1b2…bn〉，如果存在整數(shù)1≤j1＜j2＜…＜jn≤m，使得a1bj1，a2bj2，…，anbjn，則稱序列α為β的子序列，又稱序列β包含α，記為αβ。序列α在序列數(shù)據(jù)庫S中的支持度為序列數(shù)據(jù)庫S中包含序列α的序列個數(shù)，記為support(α)。給定閾值min_support，如果序列α在序列數(shù)據(jù)庫中的支持度不低于min_support，則稱序列α為頻繁序列模式，長度為k的頻繁序列模式記為k-模式。

定義1 前綴（prefix）。設(shè)序列每個元素中的所有項都按照字典序排列。給定序列，α=〈e1e2…en〉，β=〈e′1e′2…e′m〉（m≤n），如果e′i=ei(i≤m-1)，e′mem，并且(em-e′m)中的項目均在e′m項目的后面，則稱β是α的前綴。

例如表1的序列數(shù)據(jù)庫中，序列s1中，子序列aba就是子序列abacd的前綴，而ba就不是其前綴。



表1 一個例子序列數(shù)據(jù)庫

IDsequence

s1abacd

s2abdca

s3daacd

定義2 后綴（suffix）。給定序列α=〈e1e2…en〉，設(shè)序列β=〈e1e2…em-1e′m〉（m≤n）為α的前綴，則稱序列γ=〈e″mem+1…en〉為序列α關(guān)于β的后綴，其中e″m=(em-e′m)。

例如對于表1的序列數(shù)據(jù)庫，序列s1中，子序列acd就是子序列abacd的后綴，而ac就不是其后綴。

定義3 投影（project）。給定序列α和β，如果β是α的子序列，則α關(guān)于β的投影α′必須滿足：β是α′的前綴，α′是α的滿足上述條件的最大子序列。

例如在表1中，序列s1關(guān)于ab的投影為acd。

定義4 投影數(shù)據(jù)庫(project database)。設(shè)α為序列數(shù)據(jù)庫S的一個序列模式，則S關(guān)于α的投影數(shù)據(jù)庫為S中所有序列關(guān)于α的后綴構(gòu)成的數(shù)據(jù)庫。

例如，表1中子序列ab為S的一個序列模式，S關(guān)于ab的投影數(shù)據(jù)庫由acd，dca兩條序列構(gòu)成。

定義5 一個序列數(shù)據(jù)庫的所有頻繁序列模式是指所有符合約束條件，即滿足最小支持度和最小長度的所有子序列。

定義6 一個子序列在數(shù)據(jù)庫S中的位置信息為數(shù)據(jù)庫S中各個序列關(guān)于該模式的后綴位置，記為((s1，v1)，(s2，v2)，…，(sn，vn))。其中：si表示S中包含該模式序列的序號；vi表示對應(yīng)的序列關(guān)于該模式的后綴位置。

例如，對于表1中的數(shù)據(jù)庫，設(shè)最小支持度為2，則子序列ab是一個頻繁模式，它的位置記為((1，2)，(2，2))。其中(1，2)表示S中第一條序列關(guān)于模式ab的后綴位置為2；(2，2)表示S中第二條序列關(guān)于模式ab的后綴位置為2。

定理1 對于序列α和β，設(shè)β是α的后綴，并且α和β在數(shù)據(jù)庫S中的位置相同。β的投影數(shù)據(jù)庫已經(jīng)建立，即已經(jīng)產(chǎn)生了以β為前綴的所有頻繁子序列，α的投影數(shù)據(jù)庫建立晚于β，此時α不需要建立投影數(shù)據(jù)庫，α可以利用β的投影數(shù)據(jù)庫，從而產(chǎn)生出以α為前綴的子序列。

證明 因為子序列α和β在數(shù)據(jù)庫S中的位置相同，同時β是α的后綴，那么α和β具有相同的投影數(shù)據(jù)庫。按照相同投影數(shù)據(jù)庫所產(chǎn)生的頻繁子序列相同，所以當(dāng)β已經(jīng)建立了投影數(shù)據(jù)庫后，α無須再建立投影數(shù)據(jù)庫，而是利用β的投影數(shù)據(jù)庫產(chǎn)生前綴為α的頻繁子序列。

例如當(dāng)挖掘前綴為b的子頻繁模式時，b的投影數(shù)據(jù)庫為{acd，dca}，因此根據(jù)該投影數(shù)據(jù)庫可以產(chǎn)生出頻繁子序列a，c，d，從而得到頻繁模式ba，bc，bd。此時，當(dāng)挖掘前綴為ab的子頻繁模式時，由于ab和b在S中的位置相同，具有相同的投影數(shù)據(jù)庫{acd，dca}，可以不用產(chǎn)生ab的投影數(shù)據(jù)庫，根據(jù)b的投影數(shù)據(jù)庫可直接得到子頻繁模式aba，abc，abd。

2 算法描述

PVS的運(yùn)行過程類似于PrefixSpan算法，遞歸產(chǎn)生頻繁子序列的投影數(shù)據(jù)庫，從而以有利于模式增長的方法產(chǎn)生出所有的頻繁子序列。在產(chǎn)生投影數(shù)據(jù)庫的過程中，記錄產(chǎn)生投影數(shù)據(jù)庫的子序列，從而由定理1可知，可以避免多次產(chǎn)生相同的投影數(shù)據(jù)庫。

2.1 算法介紹及舉例說明

PVS由以下部分組成：a)對原始序列進(jìn)行掃描，產(chǎn)生出頻繁1項集，將原始序列數(shù)據(jù)庫投影產(chǎn)生出若干個不相交的子投影數(shù)據(jù)庫，同時記錄產(chǎn)生投影數(shù)據(jù)庫序列的位置信息。b)按照深度優(yōu)先的方法分別掃描這些投影數(shù)據(jù)庫，產(chǎn)生出相鄰的頻繁2項集，判斷所產(chǎn)生的2項集的投影數(shù)據(jù)庫是否建立。如果已經(jīng)存在，則直接產(chǎn)生出其頻繁模式；否則產(chǎn)生其相應(yīng)的投影數(shù)據(jù)庫，并記錄產(chǎn)生投影數(shù)據(jù)庫的位置信息，同時產(chǎn)生出滿足約束條件的子頻繁模式。c)依此類推，遞歸產(chǎn)生出頻繁N項集，直到?jīng)]有新的投影數(shù)據(jù)庫產(chǎn)生為止。

應(yīng)用上述算法產(chǎn)生表1的序列數(shù)據(jù)庫的所有頻繁模式，設(shè)模式最小支持度min_support=2，最小長度min_len=2。

a）掃描一次原始序列數(shù)據(jù)庫，可以得到頻繁1項集：a(3)，b(2)，c(3)，d(3)。其中括號里面的數(shù)字代表其支持度。同時，記錄這些頻繁項集所產(chǎn)生的序列位置，如a的位置信息為（（1，1），（2，1），（3，2））。首先產(chǎn)生a的投影數(shù)據(jù)庫：bacd，dbca，acd；然后掃描該投影數(shù)據(jù)庫，得到頻繁2項集：ab(2)，ac(3)，ad(3)。同時記錄它們的位置信息，如ab的位置為（（1，2），（2，2）），按照深度優(yōu)先的策略，產(chǎn)生ab的投影數(shù)據(jù)庫acd，dca。再掃描該投影數(shù)據(jù)庫，得到頻繁3項集：aba(2)，abc(2)，abd(2)。依此類推，直到所有以a為前綴的頻繁模式產(chǎn)生為止。

b）接下來產(chǎn)生以b為前綴的頻繁模式，首先得到b的位置為（（1，2），（2，2）），根據(jù)a）的記錄，發(fā)現(xiàn)在該位置已經(jīng)產(chǎn)生了投影數(shù)據(jù)庫，并且該投影數(shù)據(jù)庫的頻繁項集也已經(jīng)產(chǎn)生。因此對于b，不用重新產(chǎn)生投影數(shù)據(jù)庫，并在該投影數(shù)據(jù)庫上掃描，利用前面的結(jié)果可以直接得到ba(2)，bc(2)，bd(2)。

c）同理，分別建立c、d的投影數(shù)據(jù)庫，按照深度優(yōu)先的方法產(chǎn)生以各自為前綴的頻繁模式。產(chǎn)生的所有頻繁模式如表2所示。

表2 PVS投影數(shù)據(jù)庫和頻繁模式

前綴投影數(shù)據(jù)庫頻繁模式

abacd，bdca，acdab(2)，aba(2)，abc(2)，abd(2)，aa(3)，aac(2)，aacd(2)，aad(2)，ac(3)，acd(2)，ad(3)

bacd，dcaba(2)，bc(2)，bd(2)

cd，a，dcd (2)

dca，aacddc(2)，da(2)

2.2 算法分析

通過2.1節(jié)的算法描述可以看到，本文提出的算法采用PrefixSpan算法建立投影數(shù)據(jù)庫的方法來產(chǎn)生頻繁模式。使用該方法生成頻繁項集有以下優(yōu)點(diǎn)：a）不需要產(chǎn)生候選集，大量節(jié)約了存儲空間；b）隨著投影數(shù)據(jù)庫的逐漸產(chǎn)生，數(shù)據(jù)庫的大小遞減，縮小了頻繁項的搜索范圍。原始PrefixSpan算法有其致命的缺點(diǎn)：產(chǎn)生大量的重復(fù)投影數(shù)據(jù)庫，并在這些投影數(shù)據(jù)庫上重復(fù)掃描導(dǎo)致效率不高。PVS記錄每個投影數(shù)據(jù)庫產(chǎn)生的位置信息，避免重復(fù)產(chǎn)生相同的投影數(shù)據(jù)庫，相同的投影數(shù)據(jù)庫只需產(chǎn)生一次，并掃描一次，從而提高了算法的效率；特別是對相似度較高的序列數(shù)據(jù)進(jìn)行挖掘時，算法的執(zhí)行效率會有很大提高。

3 實(shí)驗分析

本文通過對一個人工特殊序列數(shù)據(jù)庫的處理，分析了PrefixSpan算法處理相似序列時產(chǎn)生大量投影數(shù)據(jù)庫的弊端，并與本文提出的算法在產(chǎn)生投影數(shù)據(jù)庫的數(shù)量上進(jìn)行了對比；同時使用本文提出的算法對該序列數(shù)據(jù)庫進(jìn)行了頻繁模式挖掘，給出了算法的運(yùn)行效果。

本文實(shí)驗的軟硬件環(huán)境是臺式電腦Pentium 4 2.6 GHz處理器，512 MB內(nèi)存，微軟Windows XP SP2 操作系統(tǒng)，算法開發(fā)環(huán)境為Microsoft Visual C++ 6.0 SP6。

3.1 與PrefixSpan算法對比

PrefixSpan算法有兩個主要特點(diǎn)：a）不產(chǎn)生候選集，節(jié)約內(nèi)存空間；b)產(chǎn)生的投影數(shù)據(jù)庫隨著頻繁模式長度的增加而遞減，大大提高了挖掘效率。但是它有一個很突出的缺點(diǎn)，即可能會產(chǎn)生大量重復(fù)的投影數(shù)據(jù)庫，在處理這些投影數(shù)據(jù)庫的過程中浪費(fèi)了大量的資源，同時也影響了算法執(zhí)行的效率。

通過實(shí)驗發(fā)現(xiàn)，PrefixSpan算法在處理相似度較高的序列時效率很低，一種特例就是處理完全相同的序列。為了測試PrefixSpan算法處理相似序列的效率，使用一個人工序列數(shù)據(jù)庫。該數(shù)據(jù)庫由三條序列組成，每條序列的長度為16，并且這三條序列完全相同，如表3所示。

表3 一個人工序列數(shù)據(jù)庫

IDsequence

S1ABCDEFGHIJKLMNOP

S2ABCDEFGHIJKLMNOP

S3ABCDEFGHIJKLMNOP

設(shè)定最小支持度min_support=3，最小長度min_len=16，也就是說需要產(chǎn)生的頻繁序列為ABCDEFGHIJKLMNOP。通過對上述序列數(shù)據(jù)庫進(jìn)行實(shí)驗，得出的數(shù)據(jù)為：PrefixSpan算法所產(chǎn)生的投影數(shù)據(jù)庫總數(shù)高達(dá)65 535個；用PVS算法所產(chǎn)生的投影數(shù)據(jù)庫數(shù)量僅為16個。另外對表1中的數(shù)據(jù)進(jìn)行挖掘，PrefixSpan算法共產(chǎn)生21個投影數(shù)據(jù)庫；PVS算法產(chǎn)生13個投影數(shù)據(jù)庫。由此可見，PVS能夠有效地降低投影數(shù)據(jù)庫產(chǎn)生的數(shù)量，從而提高挖掘效率。

3.2 算法運(yùn)行效果

圖1是表3在最小長度min_len分別為2、3、4時，最小支持度min_support為3時算法PVS與PrefixSpan產(chǎn)生頻繁項集的運(yùn)行時間對比圖（時間單位為ms）。通過圖中數(shù)據(jù)可以看到，PVS的運(yùn)行效率要高于PrefixSpan算法，并且在相同支持度時，隨著最小長度的減小，運(yùn)行時間也隨之遞增。

4 結(jié)束語

PrefixSpan算法在產(chǎn)生頻繁模式時會產(chǎn)生大量的投影數(shù)據(jù)庫，其中很多投影數(shù)據(jù)庫是相同的，如果能避免相同投影數(shù)據(jù)庫的產(chǎn)生，則可在一定程度上提高算法的效率。本文提出了基于位置信息的序列模式挖掘算法——PVS，該方法通過記錄已產(chǎn)生的投影數(shù)據(jù)庫的位置信息來避免相同投影數(shù)據(jù)庫的產(chǎn)生，從而提高算法的運(yùn)行效率。通過實(shí)驗證明，該算法是可行有效的，但是，由于需要記錄模式的位置信息，消耗了一定的內(nèi)存空間。如何提高算法的存儲性能是筆者今后的研究方向。

參考文獻(xiàn)：

［1］

AGRAWAL R， SRIKANT R. Mining sequential patterns:generalizations and performance improvements[C]//Proc of the 5th Int’l Conference on Extending Database Technology(EDBT).London:Sprin-gerVerlag，1996:317.

[2]ZAKI M.SPADE:an efficient algorithm for mining frequent sequences[J].Machine Learning，2001，42(12):3160.

[3]HAN Jiawei，PEI Jian，YIN Yiwen.Mining frequent patterns without candidate generation[C]//Proc of ACMSIGMOD Int’1 Conference on Management of Data. New York:ACM Press， 2000:112.

[4]HAN Jiawei， PEI Jian， MORTAZAVIASL B，et al.FreeSpan:frequent patternprojected sequential pattern mining[C]//Proc of ACM SIGKDD Int’l Conference on Knowledge Discovery in Databases.New York: ACM Press，2000:355359.

[5]PEI Jian， HAN Jiawei.Mining sequential patterns by patterngrowth:the PrefixSpan approach[J].IEEE Trans on Knowledge and Data Engineering，2004，6(10):117.

[6]PASQUIER N，BASTIDE Y，TAOUIL R，et al.Discovering frequent closed itemsets for association rules[C]//Proc of the 7th Int’l Conference on Database Theory.London:SpringerVerlag， 1999:398416.

[7]PEI Jian，HAN Jiawei，MAO Ruiying.CLOSET:an efficient algorithm for mining frequent closed itemsets[C]//Proc ofACM SIGMOD Int’l Workshop on Data Mining and Knowledge Discovery.New York:ACM Press，2000:2130.

[8]WANG Jianyong，HAN Jiawei，PEI Jian.CLOSET+:scalable and spacesaving closed itemset mining[J].Knowledge Discovery，2003，4(2):29.

[9] BURDICK D， CALIMLIM M， GEHRKE J. MAFIA:a maximal frequent itemset algorithm for transactional databases[C]//Proc of the 17th Int’l Conference on Data Engineering.Los Alamitos:IEEE Computer Society Press，2001:443452.

[10]YAN Xifeng，HAN Jiawei，AFSHAR R.CloSpan: mining closed sequential patterns in large datasets[J].Data Mining，2003，16(5):4045.

[11]ZAKI M， HSIAO C.CHARM:an efficient algorithm for closed itemset mining[C]//Proc of the 2nd SIAM Int’l Conference on Data Mining.Arlington: SIAM， 2002:1228.