條件對比序列模式挖掘算法研究.pdf

1、對比序列模式挖掘是數(shù)據(jù)挖掘中的重要課題之一，在實際應(yīng)用中具有非常高價值。對比序列模式挖掘旨在從具有類標(biāo)簽的序列數(shù)據(jù)中挖掘出具有明顯差別的序列模式。近年來各種各樣的對比序列模式挖掘算法相繼被提出，然而關(guān)于對比序列模式冗余問題的研究依舊匱乏。
　　對比序列模式挖掘主要分為兩大類，分別為指定閾值的對比序列模式挖掘和 top-k對比序列模式挖掘。現(xiàn)有方法挖掘出的序列模式都會存在一定的冗余，冗余是對比序列模式挖掘中一個急需解決的問題。導(dǎo)致對

2、比序列模式挖掘結(jié)果冗余的原因較多，其中一個重要誘因是差異顯著的子模式，即某個差異顯著的子模式可能導(dǎo)致其父模式也是差異顯著的。為了解決子模式產(chǎn)生的冗余影響，本文提出了條件對比度的概念，并針對這一概念提出了一個新的模式挖掘問題，即條件對比序列模式挖掘。本文將條件對比序列模式挖掘分為兩類：（1）指定閾值的條件對比序列模式挖掘問題；（2）top-k條件對比序列模式挖掘問題。針對這兩類模式挖掘問題，本文提出了CDSPM算法和TKCDS算法。其中C

3、DSPM算法是針對指定閾值的條件對比序列模式挖掘問題。在CDSPM算法中本文運(yùn)用Next跳轉(zhuǎn)指針及相關(guān)算法計算條件對比度。TKCDS算法是針對top-k條件對比序列模式挖掘問題。TKCDS算法通過構(gòu)造最小堆模式 hash tree來計算條件對比度。CDSPM和TKCDS均采用GSP構(gòu)造候選序列模式。
　　本文選用了一系列公開的數(shù)據(jù)集進(jìn)行了對比實驗。實驗表明條件對比度能很好地排除子序列模式的影響，在去除冗余問題上效果非常明顯。利用