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

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

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

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