去冗余Top-k對比序列模式挖掘

江冰，谷飛洋，何增有

至今已經(jīng)有很多種序列模式被提出，包括周期模式[1]、偏序模式[2]、閉合模式[3]、對比序列模式[4]、頻繁序列模式[5]等。對比序列模式挖掘作為數(shù)據(jù)挖掘中重要的一個問題，目前已經(jīng)積累了大量的研究成果[6-7]。對比序列模式是指在一類數(shù)據(jù)集中頻繁出現(xiàn)，而在另一類數(shù)據(jù)集中很少出現(xiàn)的序列模式。對比序列模式可以描述不同數(shù)據(jù)集之間的差異，在很多領域有廣泛應用。例如，對比序列模式可以用于納稅人行為分析[8]，患者的風險預測[9]等。在對比序列模式挖掘中，Top-k對比序列模式挖掘是一種重要的挖掘策略。 Topk方法是指在給定的標準下挖掘出差異最大的k個模式的方法。該方法被廣泛應用在關聯(lián)規(guī)則[10]、序列規(guī)則[11]、相關模式[12]和序列模式[7]等領域中。但是，在Top-k策略挖掘結果中依然存在冗余的問題。針對這一問題，本文提出了挖掘去冗余Top-k對比序列模式集合的方法。

1 相關工作

對比序列模式挖掘主要包括基于閾值的對比序列模式挖掘和Top-k對比序列模式挖掘兩個研究方向?；陂撝档膶Ρ刃蛄心Ｊ酵诰虻哪繕耸钦页鏊袧M足給定閾值的模式。最直接挖掘對比序列模式的方法是枚舉所有的序列模式，然后統(tǒng)計它們在每個類別上的頻率。很明顯這種方法的效率太低，不能滿足實際應用的需求。Chan等[13]于2003年提出一種基于后綴樹的挖掘對比序列模式的算法(emerging substrings mining，ESM)。與樸素的挖掘算法相比，ESM提高了一定的效率。Ji等[14]于2007年定義了MDS (minimal distinguishing subsequence) 的概念，并提出了相應的挖掘算法，即ConSGapMiner (contrast sequences with gap miner)算法。ConSGapMiner是比較經(jīng)典的對比序列模式挖掘算法，它能以較快的效率挖掘出對比序列模式。但是MDS定義的對比序列模式在正例集中大于一個固定的閾值，在反例集中小于一個固定閾值，這種定義可能使一些有意義的模式?jīng)]有被挖掘出來。2010年Deng等[15]在Con-SGapMiner的基礎上利用F-ratio作為對比度；2011年Yu等[16]提出了TSEPsMiner算法；TSEPsMiner利用GrowthRate作為對比度，而且將這個對比度應用在了挖掘對比序列模式的算法中；2014年Wang等[17]提出用gd-DSPMiner算法來解決MDS定義中存在的問題。在不明確數(shù)據(jù)的差異程度時，使用基于閾值的對比序列模式挖掘難以挖掘出預期的序列模式。在這種情況下，Top-k對比序列模式挖掘是一個可行的辦法。Top-k算法不用設定對比度的閾值，只需要設置想要挖掘模式的數(shù)目。楊皓等[7]于2015年提出了新的Top-k挖掘算法，即kDSP-Miner(Top-k distinguishing sequential patterns with gap constraint miner)算法。但是kDSP-Miner并沒有考慮冗余問題，kDSPMiner挖掘出的序列模式可能會有大量的冗余。

2 問題定義

表1 含有兩個類別的基因數(shù)據(jù)集Table 1 A gene data set with two classes

Top-k對比序列模式挖掘的目標是找出給定數(shù)據(jù)集中對比度最大的k個序列模式。

定義3 (冗余對比序列模式) 對于兩個給定的對比序列模式和，如果滿足：

表2 表1中基因數(shù)據(jù)集的Top-5對比序列模式Table 2 Top-five discriminative sequential patterns from gene data set in table 1

定義4 (去冗余Top-k對比序列模式)集合L滿足Top-k對比序列模式集合的要求，同時對于每個序列，不存在；對于任意序列，，不是相對于的冗余對比序列模式。

表3 表1中基因數(shù)據(jù)集的Top-5去冗余對比序列模式Table 3 Top-five non-redundant distinguishing sequential patterns from gene data set in table 1

表4 符號及其含義Table 4 Symbols and their meaning

3 算法設計

為了挖掘去冗余Top-k對比序列模式的集合，用本文提出的BFM和PBFM算法，來解決挖掘出的結果集合的冗余問題。BFM和PBFM算法基于廣度優(yōu)先生成樹的原理來尋找Top-k序列的集合，樹的生成過程就是Top-k集合的更新過程。相比于使用深度優(yōu)先的方法來生成樹結構，使用廣度優(yōu)先的方法每次更新時不改變Top-k集合的大小，所以不會出現(xiàn)冗余的Top-k集合。

3.1 廣度優(yōu)先的生成樹算法

3) 創(chuàng)建一個隊列，將字母表中的每個元素放入隊列中。

4) 對于隊列的第一個元素，在其末尾分別與字母表中的每個元素連接，形成新的序列。

6) 將隊列的第一個元素彈出。

7) 重復 4)～6)，直到隊列為空。

例5 對表1的數(shù)據(jù)集進行去冗余Top-k對比序列模式挖掘, 令k =5。找出基因數(shù)據(jù)集的字母表為。將字母表的每個元素放入隊列中，生成的樹結構和隊列如圖1所示。

在Top-k對比序列模式挖掘中，去除冗余序列模式是提高挖掘結果質量的重要一步。但是在原有挖掘過程的基礎上，加入去冗余的步驟后，一個新的序列可能會替換Top-k集合中的多個序列，使Top-k集合中的序列模式數(shù)目小于k個。針對以上問題，本文提出基于廣度優(yōu)先的生成樹算法BFM (breadth-first miner)來去除冗余的序列模式。使用BFM算法可以在去除冗余序列模式的同時，保證Top-k集合的大小不發(fā)生變化。

圖1 生成樹和隊列的動態(tài)變化Fig. 1 The dynamic change of spanning tree and queue

算法1 BFM (breadth-first miner)

/*初始化*/

2）創(chuàng)建隊列，初始化隊列queue為空；

4）創(chuàng)建樹的根節(jié)點,建立由根節(jié)點分別指向字母表中每個元素的連接，令min TopkCR = get-MinTopkCR (L)；

如果 P′被找到且 P不是相對于P′的冗余序列模式，則把P加入集合L, 更新；

如果 P′被找到并且P是相對于P′的冗余序列，則用P替換集合L中對比度最小的序列更新，否則，用P替換集合L中對比度最小的序列更新；

7）重復步驟 5）、6），直到對列為空。

3.2 剪枝策略

為了提高算法的性能，本文中應用了一系列剪枝策略來輔助算法的運行[7]。運用這些剪枝策略，可以使程序運行的效率提高，更快地找出Top-k集合。

加入以上3條剪枝策略后，樹結構生成的速度會加快，可以在更短的時間內找到Top-k對比序列模式。對于某一類數(shù)據(jù)集，使用剪枝后，算法的效率會顯著提升。加入剪枝后的算法如算法2。

算法2 PBFM(pruning breadth-first miner)

輸出 包含Top-k對比序列模式的集合L。

/*初始化*/

2）創(chuàng)建隊列，初始化隊列queue為空；

4）創(chuàng)建樹的根節(jié)點，建立由根節(jié)點分別指向字母表中每個元素的指針，令min TopkCR = get-MinTopkCR (L)；

7）重復步驟 5）、6），直到隊列為空。

4 實驗結果

4.1 實驗環(huán)境

本文設計了一系列實驗來評估算法的有效性。算法用C++語言來實現(xiàn)。實驗中所用到的數(shù)據(jù)集為4組真實數(shù)據(jù)。這4組數(shù)據(jù)分別是：E.Coli數(shù)據(jù)集,記錄了兩個不同類型的DNA序列。在E.Coli數(shù)據(jù)集中，每個DNA序列前面都用“+”和“–”標記出了序列所屬的類別。UJI數(shù)據(jù)集，記錄了超過11 000個獨立的手寫數(shù)字。ADLs數(shù)據(jù)集，記錄了一段時間內不同的人在自己家中的活動情況。Question數(shù)據(jù)集，記錄了各種不同的問題，可以將每個問題看作由不同單詞組成的序列。前3個數(shù)據(jù)集來自UCI的機器學習數(shù)據(jù)集。最后一個數(shù)據(jù)集是Question的訓練數(shù)據(jù)集。實驗運行的環(huán)境是：Core i3的處理器，Windows 7操作系統(tǒng)，2GB RAM 的計算機上完成。表5中列出了實驗中用到的數(shù)據(jù)集的特征。

表5 數(shù)據(jù)集的特征Table 5 The characteristics of the data sets

4.2 實驗結果分析

1) 實驗1(去冗余前后Top-k集合對比實驗)

實驗1的目標是比較去冗余前后Top-k集合中序列模式的變化，來驗證去冗余算法的有效性。在該實驗中，使用了3組數(shù)據(jù)來對比去冗余前后Top-k結果集合的不同。每組數(shù)據(jù)分別找出了含有冗余序列的Top-k集合和不含冗余序列的Top-k集合，并比較其中序列的組成。在實驗中，k值設置為5。實驗結果如表6～8所示。

表6 去冗余前后Top-k序列模式集合的變化(ADLs數(shù)據(jù)集)Table 6 The set of Top-k sequential patterns before and after eliminating redundancy(ADLs data set)

通過實驗結果可以發(fā)現(xiàn)，去冗余Top-k集合中出現(xiàn)了冗余Top-k集合中沒有出現(xiàn)的序列模式。同時，去冗余Top-k集合中刪去了冗余的序列模式。因此，本文的算法能夠有成效地去除冗余對比序列模式。

2) 實驗2(加入剪枝策略前后的對比實驗)

實驗2的目標是比較算法1與加入剪枝策略后算法效率的變化。分別在ADLs數(shù)據(jù)集和Question數(shù)據(jù)集上進行對比實驗，比較算法1和算法2運行的時間，來衡量算法的效率。

表7 去冗余前后Top-k序列模式集合的變化(E.Coli數(shù)據(jù)集)Table 7 The set of Top-k sequential patterns before and after eliminating redundancy(E.Coli data set)

表8 去冗余前后Top-k序列模式集合的變化(UJI數(shù)據(jù)集)Table 8 The set of Top-k sequential patterns before and after eliminating redundancy(UJI data set)

將k的值分別從1取到20，比較算法1(BFM)和算法2(PBFM)運行的時間如圖2所示。從圖2中可以看出，隨著k值的增加，兩種算法的運行時間都在增長，但PBFM的運行時間明顯少于BFM的運行時間。在ADLs數(shù)據(jù)集中，隨著k值逐漸變大，這一區(qū)別越來越明顯。在Question 數(shù)據(jù)集中，當k值較小時，這一區(qū)別較為明顯。隨著k值的增大，Top-k集合的最小對比度minTopkCR逐漸變小，當時，PBFM算法中刪除的元素個數(shù)較少，但PBFM算法運行的時間仍然少于BFM算法運行的時間。

圖2 BFM和PBFM的效率對比Fig. 2 Comparison of BFM and PBFM efficiencies

5 結束語

本文首先提出了一種挖掘去冗余Top-k對比序列模式的算法BFM,這是一種基于廣度優(yōu)先生成樹的算法。通過不斷的比較子序列和超序列的對比度，Top-k集合不斷地更新，直到樹結構的生成過程結束。相比之前的Top-k對比序列模式挖掘算法，BFM算法可以得到去冗余的Top-k集合，并且不需要其他集合的輔助。

在BFM算法的基礎上,提出了性能更好的PBFM算法。與BFM算法相比，PBFM算法可以在更短的時間內完成挖掘任務，并且不需要額外的操作。