對比模式挖掘研究進展

◆魏芹雙

（河北工業大學計算機科學與軟件學院 天津 300401）

對比模式挖掘研究進展

◆魏芹雙

（河北工業大學計算機科學與軟件學院 天津 300401）

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

對比模式; 序列模式挖掘

0 前言

近年來，序列模式挖掘在眾多領域的研究中發揮著重要作用，越來越多的研究者加入到序列模式挖掘問題的研究行列。對比模式能夠描述兩類或多類樣本中的對比信息，識別不同類別樣本集合的特征，在商品推薦、用戶行為分析和電力供應預測等領域有著廣泛的應用。

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

本文對上述幾個經典算法的進行簡單介紹并且對它們進行評述。

1 對比模式挖掘算法

1.1 ConSGapMiner算法

對比數據可以應用于生物醫學、分類器的創建等諸多領域，Ji等人[1]提出了可以挖掘出滿足間隙約束的最小的對比模式挖掘算法ConSGapMiner算法。所謂的最小就是挖掘出對比模式的超模式均不是滿足間隙約束的對比模式。

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

現代計算機體系結構有對對二進制數進行移位操作和邏輯操作有非常高的效率，因此ConSGapMiner算法利用比特值集合的運算可以很快的得到模式在序列中的支持數。ConSGapMiner算法的提出為之后的研究起到了重要的引導作用。但它也存在一些不足:利用深度優先挖掘的辦法時，一些最小的對比模式不能及時發現，這樣剪枝策略得不到充分的發揮，會造成空間與時間上的浪費，從而影響挖掘的效率。

1.2 gd-DSPMiner算法

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

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

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

1.3 kDSP-Miner算法

上文提到的ConSGapMiner算法和gd-DSPMiner算法雖然可以快速的得到滿足要求的對比模式，但設置不恰當的支持度閾值可能會造成對比模式的丟失，往往需要經過多次實驗才可以得到合適的正例支持度閾值和負例支持度閾值。Yang等人[3]提出了帶間隔約束的top-k對比序列模式挖掘算法kDSP-Miner算法。用戶在挖掘對比最顯著的k個對比模式時，不需要手動輸入支持度閾值，避免了由于支持度閾值設置不合理而影響挖掘效果的問題。這里提到的top-k是指帶間隔約束的對比度，即模式在正例序列庫中的支持度與負例序列庫中的支持度之差。

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

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

2 總結

本文對對比模式挖掘產生的背景進行了分析，指出提出對比模式挖掘的意義所在。重點對近幾年來提出的經典算法進行簡單的介紹對它們的優缺點進行分析。目前已有的對比模式挖掘算法均是在周期性間隙約束的條件下進行的，如何在非周期性間隙約束條件下進行對比模式的挖掘值得我們進一步探索。

[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對序列模式挖掘[J].軟件學報，2015.