◆魏芹雙

（河北工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院 天津 300401）

對(duì)比模式挖掘研究進(jìn)展

◆魏芹雙

（河北工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院 天津 300401）

對(duì)比模式能夠描述兩類或多類樣本中的對(duì)比信息，識(shí)別不同類別樣本集合的特征，在商品推薦、用戶行為分析和電力供應(yīng)預(yù)測(cè)等領(lǐng)域有著廣泛的應(yīng)用。傳統(tǒng)的序列模式挖掘不能描述多類樣本中的對(duì)比信息，因此越來(lái)越多的研究者投入到對(duì)比模式挖掘的研究行列。本文總結(jié)近幾年來(lái)對(duì)比模式挖掘取得的重大成果和進(jìn)展，特別地分析研究了其中幾個(gè)經(jīng)典算法，最后對(duì)對(duì)比模式挖掘發(fā)展趨勢(shì)進(jìn)行了展望，以便對(duì)帶有間隙約束的對(duì)比模式挖掘做進(jìn)一步的研究。

對(duì)比模式; 序列模式挖掘

0 前言

近年來(lái)，序列模式挖掘在眾多領(lǐng)域的研究中發(fā)揮著重要作用，越來(lái)越多的研究者加入到序列模式挖掘問(wèn)題的研究行列。對(duì)比模式能夠描述兩類或多類樣本中的對(duì)比信息，識(shí)別不同類別樣本集合的特征，在商品推薦、用戶行為分析和電力供應(yīng)預(yù)測(cè)等領(lǐng)域有著廣泛的應(yīng)用。

對(duì)比序列模式的概念最早是由Ji等人[1]在2007年提出的，它是序列模式挖掘的一個(gè)重要研究方向。對(duì)比模式是指模式在正例序列庫(kù)中是頻繁的并且在負(fù)例序列庫(kù)中是非頻繁的，Ji等人[1]設(shè)計(jì)了滿足間隙約束的最小對(duì)比模式挖掘算法ConSGapMiner算法。經(jīng)過(guò)多年的發(fā)展，對(duì)比序列模式挖掘的研究取得了較大的進(jìn)步，研究者們提出了很多性能良好的算法。Shah等人建立了一個(gè)以對(duì)比模式作為特征的分類器，應(yīng)用在多肽折疊預(yù)測(cè)問(wèn)題上; Wang等人[2]首次提出將密度的概念融入到對(duì)比模式挖掘中，并設(shè)計(jì)了滿足密度約束和間隙約束的對(duì)比模式挖掘算法gd-DSPMiner算法; Duan等人對(duì)基于顯露模式的對(duì)比挖掘進(jìn)行了詳盡的研究; Yang等人[3]為解決由于用戶設(shè)置不恰當(dāng)?shù)闹С侄乳撝刀斐深l繁模式丟失的問(wèn)題提出了帶間隔約束的top-k對(duì)比模式挖掘算法kDSP-Miner算法; Wang等人設(shè)計(jì)了帶緊湊間隔約束的最小對(duì)比序列模式挖掘算法MDSP-CGC算法，該算法可以不需要提前設(shè)置間隔約束，可以直接對(duì)候選模式進(jìn)行分析自動(dòng)計(jì)算最適合的間隔約束; Yang等人將基于單元素序列的最小對(duì)比序列模式挖掘擴(kuò)展為基于元素集合序列的最小比模式挖掘。

本文對(duì)上述幾個(gè)經(jīng)典算法的進(jìn)行簡(jiǎn)單介紹并且對(duì)它們進(jìn)行評(píng)述。

1 對(duì)比模式挖掘算法

1.1 ConSGapMiner算法

對(duì)比數(shù)據(jù)可以應(yīng)用于生物醫(yī)學(xué)、分類器的創(chuàng)建等諸多領(lǐng)域，Ji等人[1]提出了可以挖掘出滿足間隙約束的最小的對(duì)比模式挖掘算法ConSGapMiner算法。所謂的最小就是挖掘出對(duì)比模式的超模式均不是滿足間隙約束的對(duì)比模式。

該算法的思想是:首先掃描序列庫(kù)中的所有序列，生成字符集∑并建立字典樹; 利用深度優(yōu)先遍歷字典樹的方法對(duì)長(zhǎng)度為l（l〉0）的候選模式集C’l中的模式生成長(zhǎng)度為l+1的待挖掘模式集Cl+1; 利用比特集合（Bitset）數(shù)組計(jì)算得到長(zhǎng)度為l+1的待挖掘模式在各個(gè)序列中的支持?jǐn)?shù)，從而計(jì)算該模式在正例序列庫(kù)D+和負(fù)例序列庫(kù)D-中支持度; 如果在模式在正例序列庫(kù)D+中的支持度大于等于正例支持度閾值并且在負(fù)例序列庫(kù)D-中的支持度小于等于負(fù)例支持度閾值，將這個(gè)模式加入最小對(duì)比模式集中，否則將模式加入到候選模式集C’l+1，用于生成長(zhǎng)度為l+2的待挖掘模式集Cl+2。迭代上述過(guò)程直到候選模式集為空。

現(xiàn)代計(jì)算機(jī)體系結(jié)構(gòu)有對(duì)對(duì)二進(jìn)制數(shù)進(jìn)行移位操作和邏輯操作有非常高的效率，因此ConSGapMiner算法利用比特值集合的運(yùn)算可以很快的得到模式在序列中的支持?jǐn)?shù)。ConSGapMiner算法的提出為之后的研究起到了重要的引導(dǎo)作用。但它也存在一些不足:利用深度優(yōu)先挖掘的辦法時(shí)，一些最小的對(duì)比模式不能及時(shí)發(fā)現(xiàn)，這樣剪枝策略得不到充分的發(fā)揮，會(huì)造成空間與時(shí)間上的浪費(fèi)，從而影響挖掘的效率。

1.2 gd-DSPMiner算法

帶有密度約束的序列模式更有助于生物學(xué)家研究發(fā)現(xiàn)生物序列中的一些特殊因子的分布情況，更有利于發(fā)現(xiàn)新的突變因子等。因此Wang等人[2]提出密度的概念，并且將密度與滿足間隙約束的對(duì)比模式相融合提出了滿足密度約束和間隙約束的對(duì)比模式的挖掘算法gd-DSPMiner算法。

該算法利用匹配三元組進(jìn)行模式在序列中出現(xiàn)數(shù)的計(jì)算。在對(duì)比模式挖掘的過(guò)程中，將長(zhǎng)度為l（l〉0）的待挖掘模式Cl分為四個(gè)不相交的集合:所有長(zhǎng)度小于等于l的gd-DSP（滿足密度約束和間隙約束的對(duì)比模式）的模式集合Pl，不可能是gd-DSP的模式集合Ul，子模式是gd-DSP的模式集合Ml和超模式可能是gd-DSP的模式集合Rl。通過(guò)連接集合Rl中的任意兩個(gè)長(zhǎng)度為l的候選模式，得到長(zhǎng)度為l+1的待挖掘模式，從而得到所有的待挖掘模式集Cl+1; 根據(jù)gd-DSP的定義，只有Cl+1中的模式有可能產(chǎn)生滿足要求的對(duì)比模式，因此僅僅對(duì)Cl+1中的模式進(jìn)行挖掘，大大提高了挖掘的效率。

gd-DSPMiner算法的提出解決了ConSGapMiner算法采用深度優(yōu)先遍歷字典樹生成候選模式而造成的重復(fù)挖掘的問(wèn)題，但在計(jì)算模式在序列中的支持?jǐn)?shù)時(shí)采用了匹配三元組的方法，該方法中不管模式在序列的某位置是否產(chǎn)生出現(xiàn)都會(huì)為該位置建立匹配三元組，因此造成了空間上的浪費(fèi)。在設(shè)置參數(shù)方面必須進(jìn)行多次實(shí)驗(yàn)，才可以得到合適的密度、支持度閾值以及間隙約束。

1.3 kDSP-Miner算法

上文提到的ConSGapMiner算法和gd-DSPMiner算法雖然可以快速的得到滿足要求的對(duì)比模式，但設(shè)置不恰當(dāng)?shù)闹С侄乳撝悼赡軙?huì)造成對(duì)比模式的丟失，往往需要經(jīng)過(guò)多次實(shí)驗(yàn)才可以得到合適的正例支持度閾值和負(fù)例支持度閾值。Yang等人[3]提出了帶間隔約束的top-k對(duì)比序列模式挖掘算法kDSP-Miner算法。用戶在挖掘?qū)Ρ茸铒@著的k個(gè)對(duì)比模式時(shí)，不需要手動(dòng)輸入支持度閾值，避免了由于支持度閾值設(shè)置不合理而影響挖掘效果的問(wèn)題。這里提到的top-k是指帶間隔約束的對(duì)比度，即模式在正例序列庫(kù)中的支持度與負(fù)例序列庫(kù)中的支持度之差。

該算法通過(guò)掃描數(shù)據(jù)集，生成字母表∑并生成集合枚舉樹;利用深度優(yōu)先遍歷基于∑的集合枚舉樹方法逐一產(chǎn)生候選對(duì)比序列模式; 分別對(duì)每一個(gè)候選模式進(jìn)行挖掘，如果對(duì)比度大于已有的top-k中的對(duì)比度最小的模式就將該模式替換為當(dāng)前模式。迭代上述過(guò)程，直到完成對(duì)集合枚舉樹的遍歷。

該算法采用三個(gè)裁剪策略和一個(gè)加速策略提高了算法的挖掘效率。為了提高該算法對(duì)高維序列進(jìn)行處理的能力，同時(shí)進(jìn)一步設(shè)計(jì)了kDSP-Miner的多線程版。Wang等人同樣針對(duì)設(shè)置不合理的參數(shù)而造成頻繁模式的丟失問(wèn)題提出了MDSP-CGC算法，原理與kDSP-Miner算法類似，在此不再贅述。

2 總結(jié)

本文對(duì)對(duì)比模式挖掘產(chǎn)生的背景進(jìn)行了分析，指出提出對(duì)比模式挖掘的意義所在。重點(diǎn)對(duì)近幾年來(lái)提出的經(jīng)典算法進(jìn)行簡(jiǎn)單的介紹對(duì)它們的優(yōu)缺點(diǎn)進(jìn)行分析。目前已有的對(duì)比模式挖掘算法均是在周期性間隙約束的條件下進(jìn)行的，如何在非周期性間隙約束條件下進(jìn)行對(duì)比模式的挖掘值得我們進(jìn)一步探索。

[1]Ji Xiaonan，James Bailey，Dong Guozhu.Mining minimal distinguishing subsequence patterns with gap constraints [J].Knowledge Information Systems，2007.

[2]Wang Xianming，Duan Lei，Dong Guozhu，et al.Efficient mining of density-aware distinguishing sequential patterns with gap constraints [M].In:Proceedings of the 19th International Conference of Database Systems for Advanced Applications，2014.

[3]楊皓，段磊，胡斌等.帶間隔約束的Top-k對(duì)序列模式挖掘[J].軟件學(xué)報(bào)，2015.