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

江冰，谷飛洋，何增有

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

1 相關工作

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

2 問題定義

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

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

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

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

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

表3 表1中基因數據集的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算法基于廣度優先生成樹的原理來尋找Top-k序列的集合，樹的生成過程就是Top-k集合的更新過程。相比于使用深度優先的方法來生成樹結構，使用廣度優先的方法每次更新時不改變Top-k集合的大小，所以不會出現冗余的Top-k集合。

3.1 廣度優先的生成樹算法

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

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

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

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

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

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

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

算法1 BFM (breadth-first miner)

/*初始化*/

2）創建隊列，初始化隊列queue為空；

4）創建樹的根節點,建立由根節點分別指向字母表中每個元素的連接，令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對比序列模式。對于某一類數據集，使用剪枝后，算法的效率會顯著提升。加入剪枝后的算法如算法2。

算法2 PBFM(pruning breadth-first miner)

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

/*初始化*/

2）創建隊列，初始化隊列queue為空；

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

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

4 實驗結果

4.1 實驗環境

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

表5 數據集的特征Table 5 The characteristics of the data sets

4.2 實驗結果分析

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

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

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

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

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

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

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

表8 去冗余前后Top-k序列模式集合的變化(UJI數據集)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數據集中，隨著k值逐漸變大，這一區別越來越明顯。在Question 數據集中，當k值較小時，這一區別較為明顯。隨著k值的增大，Top-k集合的最小對比度minTopkCR逐漸變小，當時，PBFM算法中刪除的元素個數較少，但PBFM算法運行的時間仍然少于BFM算法運行的時間。

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

5 結束語

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

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