基于多元索引后繼樹的序列模式挖掘方法

唐 雁，吳紹春

（上海大學(xué) 計(jì)算機(jī)工程與科學(xué)學(xué)院， 上海 200072）

隨著科學(xué)技術(shù)的飛速發(fā)展，在各個(gè)領(lǐng)域產(chǎn)生了大量的歷史數(shù)據(jù)，如何有效地管理和利用這些海量數(shù)據(jù)序列，發(fā)現(xiàn)和理解這些數(shù)據(jù)序列背后隱含的規(guī)律和知識，已經(jīng)受到越來越多數(shù)據(jù)挖掘研究者的廣泛關(guān)注。序列模式挖掘由此應(yīng)運(yùn)而生，并已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域中一個(gè)重要研究方向。

目前的序列模式挖掘方法主要分為2類：（1）基于Apr iori的算法，其基本思想是頻繁模式的子模式也一定是頻繁模式，如Apr ior iALL、GSP算法；（2）基于模式增長方法，采用分而治之的原理,反復(fù)把數(shù)據(jù)庫投影到比它小的數(shù)據(jù)集里，在較小的數(shù)據(jù)集上進(jìn)行模式擴(kuò)展的序列挖掘，如Freespan、Pref ixSpan算法。

本文提出一種新型的序列挖掘模型—多元索引后繼樹，具有創(chuàng)建速度快， 檢索速度快，空間效率高等特點(diǎn)。該模型使用索引方法通過一遍掃描創(chuàng)建描述一個(gè)序列的多元索引后繼樹，可以完全拋棄原始序列，然后使用模式增長的方式生成頻繁模式，無需生成候選模式，同時(shí)也可以通過索引快速生成原始序列。本文通過試驗(yàn)分析證明多元索引后繼樹模型多方面性能均優(yōu)于其他的序列挖掘模型。

1 多元索引后繼樹（MIST）模型

使用多元索引后繼樹模型的前提是需要對序列進(jìn)行符號化等相關(guān)的預(yù)處理，將序列轉(zhuǎn)換成用符號表示的字符串序列。

1.1 前驅(qū)和后繼

對任意序列T中的任意字符串a(chǎn)1a2，a1稱為a2的前驅(qū)；a2稱為a1的后繼，序列T最后一個(gè)字符的后繼（假定為#）為序列結(jié)束符。

1.2 索引

在一序列中，每一個(gè)字符在序列中出現(xiàn)的位置就定義為該字符在序列中的索引。

1.3 后繼表達(dá)式

設(shè)序列T是由一字符串a(chǎn)0，a1，…，an組成的，其索引分別為0，1，…，n。若其中ai1、ai2、…、aim為一組相同的字符，這里統(tǒng)一記為ai，則ai1+1、ai2+1、…、aim+1都是ai的后繼，而ai1+1、ai2+1、…、aim+1的索引分別為i1+1、i2+1、…、im+1。對ai每一個(gè)后繼，建立形如aiai1+1的后繼項(xiàng)，對ai的所有后繼項(xiàng)根據(jù)不同的后繼字符（假定為ak、a1、…、az）進(jìn)行合并，形成ai的后繼表達(dá)式ai((ak,k1,k2,…,km),(a1,l1,l2,…,ln),…,(az,z1,z2,…,zt))。

1.4 多元索引后繼樹

序列T中，任一ai的后繼表達(dá)式可以用一棵2級多叉樹來表示，如圖1。我們定義為多元索引后繼樹，它是一顆深度為2的樹。

圖1中多元索引后繼樹的根節(jié)點(diǎn)為ai，第一個(gè)葉節(jié)點(diǎn)(ak,k1,k2,…,km)表示ai的一個(gè)后繼ak，后繼ak在序列中出現(xiàn)次數(shù)（即字符串a(chǎn)iak出現(xiàn)的次數(shù)）為m，k1、k2、…、km為aiak在序列中ak出現(xiàn)的索引位置。

圖1 多元索引后繼樹結(jié)構(gòu)

1.5 多元索引后繼樹模型

若全文a0，a1，…，an（以#為結(jié)束標(biāo)記）中共有k個(gè)不同的字符，則k個(gè)字符對應(yīng)于k棵不同的多元索引后繼樹。由于一個(gè)序列包含多個(gè)字符，每個(gè)字符有多個(gè)不同的后繼，每個(gè)不同的后繼用一個(gè)葉節(jié)點(diǎn)表示多個(gè)索引的集合，將一個(gè)序列對應(yīng)的所有多元索引后繼樹的森林定義為序列的多元索引后繼樹（Mul t i-Index Successive Tree），記為MIST，它是序列的一種等價(jià)的描述模型，即對任意的一序列都能構(gòu)造其MIST，同時(shí)對于MIST也能還原其對應(yīng)的原始序列。

例1：對于序列abcabaabc#，其中#為結(jié)束符，共有3個(gè)不同的字符a、b、c，a的后繼表達(dá)式為：{（b,1,4,7）,(a,6)},b的后繼表達(dá)式為：{(c,2,8),(5,6)},c的后繼表達(dá)式為：{（a,3）,(#,9)}。該序列對應(yīng)的多元索引后繼樹如圖2。

圖2 MIST示例

從圖2的第一棵樹a（索引為0）開始遍歷，查找到索引為1的葉節(jié)點(diǎn)b，按照葉節(jié)點(diǎn)的后繼符b開始，遍歷后繼樹b，找到索引為2的葉節(jié)點(diǎn)c，以此類推，將遍歷整個(gè)MIST，那么遍歷路徑上的根項(xiàng)所組成的字符便可以還原初始的序列。

例2：在例1中，如果查詢字符串”abc”，從a的分支查找后繼符b，發(fā)現(xiàn)b存在于原文1、4、7位置處，再根據(jù)b的分支查找后繼符c，發(fā)現(xiàn)存在于2、8位置處，并且abc有2個(gè)匹配（1,2）和（7,8）；則查詢字符串”abc”是在索引庫存在2個(gè)匹配。

1.6 基礎(chǔ)頻繁項(xiàng)集

后繼樹中每一個(gè)葉節(jié)點(diǎn)的計(jì)數(shù)定義為此葉節(jié)點(diǎn)上的后繼字符在序列中作為后繼出現(xiàn)的次數(shù)。假設(shè)最小支持度為Suppor t，則計(jì)數(shù)滿足最小支持度要求即為頻繁項(xiàng)，由此產(chǎn)生的頻繁項(xiàng)集合就稱為基礎(chǔ)頻繁項(xiàng)集，它是頻繁2項(xiàng)集。

例3：在例1中，a的后繼表達(dá)式a(b，1,4,7)表示a的后繼符b出現(xiàn)在原序列中1、4、7索引位置，即頻繁項(xiàng)ab在序列中出現(xiàn)過3次，其頻繁項(xiàng)計(jì)數(shù)為3；同理a(b,c,1,2,7,8)可看做a的后繼bc分別在索引1、2，7、8位置，即頻繁項(xiàng)abc在序列出現(xiàn)2次，其頻繁項(xiàng)計(jì)數(shù)為2。

例4：對于序列abcabaabc#，假設(shè)支持度Suppor t=2，多元索引后繼樹a的第一個(gè)葉節(jié)點(diǎn)（b,1,4,7）的支持度為3，滿足要求；第二個(gè)葉節(jié)點(diǎn)（a,6）的支持度為1，因?yàn)椴粷M足支持度要求不做考慮，從而多元索引后繼樹a滿足支持度要求的葉節(jié)點(diǎn)為（b,1,4,7）；因此，基礎(chǔ)頻繁項(xiàng)集為{a(b,1,4,7,b(c,2,8)}。

2 基于MIST的頻繁序列模式挖掘

采用MIST發(fā)現(xiàn)頻繁序列模式主要有2個(gè)步驟完成：（1）生成基礎(chǔ)頻繁項(xiàng)集；（2）生成所有頻繁序列模式。

生成基礎(chǔ)頻繁項(xiàng)的具體過程是從每一顆索引后繼樹的根出發(fā)，遍歷它的葉節(jié)點(diǎn)，判斷此葉節(jié)點(diǎn)是否滿足最小支持度要求，滿足則保留，否則舍去。

生成所有頻繁序列模式的具體過程包括：訪問滿足最小支持度要求的葉節(jié)點(diǎn)，根據(jù)此葉節(jié)點(diǎn)的后繼符訪問相應(yīng)基礎(chǔ)頻繁項(xiàng)集中的索引后繼樹，查找樹中是否存在距離為1的葉節(jié)點(diǎn)，如存在，并且同時(shí)滿足最小支持度要求，則加入到被訪問的葉節(jié)點(diǎn)中，對不滿足要求的索引則舍去。以此類推，直至生成最大頻繁序列。

例5：對于序列abcabaabc#，假設(shè)支持度Suppor t=2，則滿足要求的節(jié)點(diǎn)集合為{a(b,1,4,7),b(c,2,8)}。從多元索引后繼樹a中最后一個(gè)后繼符b開始訪問基礎(chǔ)頻繁項(xiàng)集中對應(yīng)的多元索引后繼樹b(c,2,8)，得到滿足要求的頻繁項(xiàng)集{a(b,c,1,2,7,8)}，即abc為最大頻繁序列，其支持度為2。

下面給出獲取滿足支持度Suppor t的k項(xiàng)頻繁序列的算法：

輸入：基礎(chǔ)頻繁項(xiàng)集L2，k-1項(xiàng)頻繁序列Lk-1，最小支持度Supoor t

輸出：k項(xiàng)頻繁序列Lk

算法：

Foreach(each item in Lk-1)

{

For(i=k-1;i

{

Char c= Lk-1.item(i);// Lk-1中需要匹配的字符

Foreach(each item in L2)

{

int count=0;//計(jì)數(shù)

Char ch= the root of Lk-1.item;//基礎(chǔ)頻繁項(xiàng)集的根

If(c==ch)

For( j=0;j< L2.count;j++)

{

If(L2.item(j)-Lk-1.item(i)==1)

Count++;

}

If(Count≥Support) insert L2.item into Lk-1;

}

i+=k-1;

}

}

Lk= Lk-1;

Return Lk;

例6：如果查詢字符串“abc”是否為頻繁項(xiàng)，查找頻繁項(xiàng)集{a(b,c,1,2,7,8)}，可以發(fā)現(xiàn)有2個(gè)匹配項(xiàng)（1,2）和（7,8），滿足最小支持度條件，因此字符串”abc”是頻繁項(xiàng)。

3 實(shí)驗(yàn)與結(jié)果分析

為了對上述算法效果進(jìn)行考察，本文采用從2002年1月1日到2010年1月1日的崇明地電數(shù)據(jù)進(jìn)行模擬試驗(yàn)，如圖3。

圖 3 地電數(shù)據(jù)模擬生成的部分原始序列

對崇明地電數(shù)據(jù)進(jìn)行分段符號化處理生成字符串序列，采用機(jī)器CPU主頻為1.66Hz×2，內(nèi)存為1 G，操作系統(tǒng)為Windows XP的實(shí)驗(yàn)環(huán)境進(jìn)行實(shí)驗(yàn)分析。

本文分別考察了MIST和Pref ixSpan，并對2種算法的挖掘效果進(jìn)行了對比分析。圖4是在不同的支持度閾值下，2種方法所花費(fèi)的時(shí)間消耗。從圖中可以看出，MIST有明顯的性能優(yōu)勢。其主要原因是：由于此時(shí)Pref ixSpan在重復(fù)投影和重復(fù)掃描過程中花費(fèi)的了較多的時(shí)間，而MIST使用索引創(chuàng)建樹和生成頻繁模式，同時(shí)將相同的后繼字符合并，有效地提高了算法效率。

圖 4 MIST與Pref ixSpan時(shí)間性能比較

把MIST與Pref ixSpan算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較表明，MIST在空間性能方面也占優(yōu)勢。這是由于MIST算法避免了重復(fù)投影數(shù)據(jù)庫的構(gòu)建，放棄了對非頻繁項(xiàng)的存儲，從而使得MIST算法占據(jù)的內(nèi)存空間小于Pref ixSpan算法，如圖5。

圖 5 MIST與Pref ixSpan空間性能比較

4 結(jié)束語

本文提出一種新的序列挖掘模型—多元索引后繼樹，與其他方法相比，MIST的優(yōu)點(diǎn)體現(xiàn)在：（1）無需生成候選模式，節(jié)省存儲空間，提高時(shí)間效率。（2）直接使用字符在原始序列的索引位置，使得頻繁項(xiàng)生成過程中速度更快。不管是創(chuàng)建還是生成都很方便快捷。（3）查詢和匹配時(shí)無需進(jìn)行字符串分解，因此可以查詢和匹配任意長度的字符串。（4）在發(fā)現(xiàn)頻繁項(xiàng)過程中，使用基礎(chǔ)頻繁項(xiàng)，不需要使用字符串匹配和頻繁計(jì)數(shù)，從而生成過程簡化，速度更快。

多元索引后繼樹作為一種被初步證明有效的數(shù)據(jù)挖掘模型，在理論上還需作進(jìn)一步發(fā)展，給出完整體系；在實(shí)踐上，對本文提出的多元索引后繼樹的數(shù)據(jù)結(jié)構(gòu)和頻繁模式挖掘算法，還應(yīng)擴(kuò)大其實(shí)驗(yàn)范圍，增加不同條件和狀態(tài)的實(shí)驗(yàn)數(shù)據(jù)，以準(zhǔn)確、全面地評估其有效性，認(rèn)識其特征，探索更多實(shí)際應(yīng)用領(lǐng)域。

[1]金 燦，朱紹文. 序列模式的增量式挖掘算法研究[D]. 武漢：華中師范大學(xué)碩士論文，2004.

[2]王 虎，丁世飛. 序列模式挖掘研究與發(fā)展[J].計(jì)算機(jī)科學(xué)，2009.

[3]呂 鋒，張煒瑋. 4種序列模式挖掘算法的特性研究[J]. 武漢理工大學(xué)學(xué)報(bào)，2006，2.

[4]張圓圓，胡學(xué)剛. 序列模式發(fā)現(xiàn)模型的研究[D]. 合肥：合肥工業(yè)大學(xué)碩士論文，2007.

[5]馮文超，吳紹春，王 煒. 基于IRST的并行時(shí)序模式挖掘算法[J]. 計(jì)算機(jī)工程應(yīng)用研究，2007.