江冰，谷飛洋，何增有

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

1 相關(guān)工作

對(duì)比序列模式挖掘主要包括基于閾值的對(duì)比序列模式挖掘和Top-k對(duì)比序列模式挖掘兩個(gè)研究方向。基于閾值的對(duì)比序列模式挖掘的目標(biāo)是找出所有滿(mǎn)足給定閾值的模式。最直接挖掘?qū)Ρ刃蛄心Ｊ降姆椒ㄊ敲杜e所有的序列模式，然后統(tǒng)計(jì)它們?cè)诿總€(gè)類(lèi)別上的頻率。很明顯這種方法的效率太低，不能滿(mǎn)足實(shí)際應(yīng)用的需求。Chan等[13]于2003年提出一種基于后綴樹(shù)的挖掘?qū)Ρ刃蛄心Ｊ降乃惴?emerging substrings mining，ESM)。與樸素的挖掘算法相比，ESM提高了一定的效率。Ji等[14]于2007年定義了MDS (minimal distinguishing subsequence) 的概念，并提出了相應(yīng)的挖掘算法，即ConSGapMiner (contrast sequences with gap miner)算法。ConSGapMiner是比較經(jīng)典的對(duì)比序列模式挖掘算法，它能以較快的效率挖掘出對(duì)比序列模式。但是MDS定義的對(duì)比序列模式在正例集中大于一個(gè)固定的閾值，在反例集中小于一個(gè)固定閾值，這種定義可能使一些有意義的模式?jīng)]有被挖掘出來(lái)。2010年Deng等[15]在Con-SGapMiner的基礎(chǔ)上利用F-ratio作為對(duì)比度；2011年Yu等[16]提出了TSEPsMiner算法；TSEPsMiner利用GrowthRate作為對(duì)比度，而且將這個(gè)對(duì)比度應(yīng)用在了挖掘?qū)Ρ刃蛄心Ｊ降乃惴ㄖ校?014年Wang等[17]提出用gd-DSPMiner算法來(lái)解決MDS定義中存在的問(wèn)題。在不明確數(shù)據(jù)的差異程度時(shí)，使用基于閾值的對(duì)比序列模式挖掘難以挖掘出預(yù)期的序列模式。在這種情況下，Top-k對(duì)比序列模式挖掘是一個(gè)可行的辦法。Top-k算法不用設(shè)定對(duì)比度的閾值，只需要設(shè)置想要挖掘模式的數(shù)目。楊皓等[7]于2015年提出了新的Top-k挖掘算法，即kDSP-Miner(Top-k distinguishing sequential patterns with gap constraint miner)算法。但是kDSP-Miner并沒(méi)有考慮冗余問(wèn)題，kDSPMiner挖掘出的序列模式可能會(huì)有大量的冗余。

2 問(wèn)題定義

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

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

定義3 (冗余對(duì)比序列模式) 對(duì)于兩個(gè)給定的對(duì)比序列模式和，如果滿(mǎn)足：

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

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

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

表4 符號(hào)及其含義Table 4 Symbols and their meaning

3 算法設(shè)計(jì)

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

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

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

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

6) 將隊(duì)列的第一個(gè)元素彈出。

7) 重復(fù) 4)～6)，直到隊(duì)列為空。

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

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

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

算法1 BFM (breadth-first miner)

/*初始化*/

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

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

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

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

7）重復(fù)步驟 5）、6），直到對(duì)列為空。

3.2 剪枝策略

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

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

算法2 PBFM(pruning breadth-first miner)

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

/*初始化*/

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

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

7）重復(fù)步驟 5）、6），直到隊(duì)列為空。

4 實(shí)驗(yàn)結(jié)果

4.1 實(shí)驗(yàn)環(huán)境

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

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

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

1) 實(shí)驗(yàn)1(去冗余前后Top-k集合對(duì)比實(shí)驗(yàn))

實(shí)驗(yàn)1的目標(biāo)是比較去冗余前后Top-k集合中序列模式的變化，來(lái)驗(yàn)證去冗余算法的有效性。在該實(shí)驗(yàn)中，使用了3組數(shù)據(jù)來(lái)對(duì)比去冗余前后Top-k結(jié)果集合的不同。每組數(shù)據(jù)分別找出了含有冗余序列的Top-k集合和不含冗余序列的Top-k集合，并比較其中序列的組成。在實(shí)驗(yàn)中，k值設(shè)置為5。實(shí)驗(yàn)結(jié)果如表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)

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

2) 實(shí)驗(yàn)2(加入剪枝策略前后的對(duì)比實(shí)驗(yàn))

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

表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)運(yùn)行的時(shí)間如圖2所示。從圖2中可以看出，隨著k值的增加，兩種算法的運(yùn)行時(shí)間都在增長(zhǎng)，但PBFM的運(yùn)行時(shí)間明顯少于BFM的運(yùn)行時(shí)間。在ADLs數(shù)據(jù)集中，隨著k值逐漸變大，這一區(qū)別越來(lái)越明顯。在Question 數(shù)據(jù)集中，當(dāng)k值較小時(shí)，這一區(qū)別較為明顯。隨著k值的增大，Top-k集合的最小對(duì)比度minTopkCR逐漸變小，當(dāng)時(shí)，PBFM算法中刪除的元素個(gè)數(shù)較少，但PBFM算法運(yùn)行的時(shí)間仍然少于BFM算法運(yùn)行的時(shí)間。

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

5 結(jié)束語(yǔ)

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

在BFM算法的基礎(chǔ)上,提出了性能更好的PBFM算法。與BFM算法相比，PBFM算法可以在更短的時(shí)間內(nèi)完成挖掘任務(wù)，并且不需要額外的操作。