唐 雁，吳紹春

（上海大學 計算機工程與科學學院， 上海 200072）

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

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

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

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

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

1.1 前驅(qū)和后繼

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

1.2 索引

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

1.3 后繼表達式

設序列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每一個后繼，建立形如aiai1+1的后繼項，對ai的所有后繼項根據(jù)不同的后繼字符（假定為ak、a1、…、az）進行合并，形成ai的后繼表達式ai((ak,k1,k2,…,km),(a1,l1,l2,…,ln),…,(az,z1,z2,…,zt))。

1.4 多元索引后繼樹

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

圖1中多元索引后繼樹的根節(jié)點為ai，第一個葉節(jié)點(ak,k1,k2,…,km)表示ai的一個后繼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é)束標記）中共有k個不同的字符，則k個字符對應于k棵不同的多元索引后繼樹。由于一個序列包含多個字符，每個字符有多個不同的后繼，每個不同的后繼用一個葉節(jié)點表示多個索引的集合，將一個序列對應的所有多元索引后繼樹的森林定義為序列的多元索引后繼樹（Mul t i-Index Successive Tree），記為MIST，它是序列的一種等價的描述模型，即對任意的一序列都能構(gòu)造其MIST，同時對于MIST也能還原其對應的原始序列。

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

圖2 MIST示例

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

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

1.6 基礎頻繁項集

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

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

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

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

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

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

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

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

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

輸入：基礎頻繁項集L2，k-1項頻繁序列Lk-1，最小支持度Supoor t

輸出：k項頻繁序列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;//計數(shù)

Char ch= the root of Lk-1.item;//基礎頻繁項集的根

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”是否為頻繁項，查找頻繁項集{a(b,c,1,2,7,8)}，可以發(fā)現(xiàn)有2個匹配項（1,2）和（7,8），滿足最小支持度條件，因此字符串”abc”是頻繁項。

3 實驗與結(jié)果分析

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

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

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

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

圖 4 MIST與Pref ixSpan時間性能比較

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

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

4 結(jié)束語

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

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

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

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

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

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

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