對比保序模式挖掘算法

孟玉飛，武優(yōu)西*，王珍，李艷

對比保序模式挖掘算法

孟玉飛1，武優(yōu)西1*，王珍1，李艷2

（1.河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院，天津 300401； 2.河北工業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院，天津 300401）（?通信作者電子郵箱wuc567@163.com）

針對現(xiàn)有的對比序列模式挖掘方法主要針對字符序列數(shù)據(jù)集且難以應(yīng)用于時(shí)間序列數(shù)據(jù)集的問題，提出一種對比保序模式挖掘（COPM）算法。首先，在候選模式生成階段，采用模式融合策略減少候選模式數(shù)；其次在模式支持度計(jì)算階段，利用子模式的匹配結(jié)果計(jì)算超模式的支持度；最后，設(shè)計(jì)了動(dòng)態(tài)最小支持度閾值的剪枝策略，以進(jìn)一步有效地剪枝候選模式。實(shí)驗(yàn)結(jié)果表明，在6個(gè)真實(shí)的時(shí)間序列數(shù)據(jù)集上，在內(nèi)存消耗方面，COPM算法至少比COPM-o（COPM-original）算法降低52.1%，比COPM-e（COPM-enumeration）算法低36.8%，比COPM-p（COPM-prune）算法降低63.6%；同時(shí)在運(yùn)行時(shí)間方面，COPM算法至少比COPM-o算法降低30.3%，比COPM-e算法降低8.8%，比COPM-p算法降低41.2%。因此，在算法性能方面，COPM算法優(yōu)于COPM-o、COPM-e和COPM-p算法。實(shí)驗(yàn)結(jié)果驗(yàn)證了COPM算法可以有效挖掘?qū)Ρ缺Ｐ蚰Ｊ?，發(fā)現(xiàn)不同類別的時(shí)間序列數(shù)據(jù)集間的差異。

模式挖掘；序列模式挖掘；時(shí)間序列；對比模式；保序模式

0 引言

隨著大數(shù)據(jù)時(shí)代的發(fā)展，時(shí)間序列數(shù)據(jù)廣泛存在于各領(lǐng)域，如股票每日收盤價(jià)［1］、每日的天氣溫度［2］、心/腦電數(shù)據(jù)［3］等。時(shí)間序列包含大量對用戶有用的信息，具有廣泛的應(yīng)用價(jià)值。人們迫切希望從時(shí)間序列數(shù)據(jù)中挖掘有用的模式。傳統(tǒng)的時(shí)間序列研究方法通常先采用分段聚合近似（Piecewise Aggregate Approximation， PAA）［4］和符號聚合近似（Symbolic Aggregate approXimation， SAX）［5］等方法將數(shù)值數(shù)據(jù)符號化，再研究挖掘字符序列的序列模式挖掘方法。然而時(shí)間序列的字符化在實(shí)現(xiàn)的過程中不僅會引入噪聲，還會忽略序列的原始趨勢特征，難以描述時(shí)間序列數(shù)據(jù)中的關(guān)鍵趨勢特征。

為了解決上述問題，Kim等［6］提出了保序模式的概念，直觀地表示時(shí)間序列中的波動(dòng)趨勢。近年來，保序模式匹配研究得到了較多學(xué)者的關(guān)注［7］，并提出了多種保序模式匹配算法，如高效的保序模式匹配算法［8］、近似保序模式匹配算法［9］等；但是這些方法需要用戶預(yù)先給定查詢模式［10-11］，從而在時(shí)間序列中尋找查詢模式的出現(xiàn)位置。為了有效地從時(shí)間序列中發(fā)現(xiàn)頻繁出現(xiàn)的相同趨勢，Wu等［12］首次提出保序模式挖掘問題。為了提高算法的挖掘效率，并進(jìn)一步提高保序模式的推薦準(zhǔn)確率，Wu等［13］提出了保序規(guī)則模式挖掘算法。

但是上述挖掘方法主要在時(shí)間序列上挖掘頻繁模式，在挖掘過程中未考慮不同類別的時(shí)間序列之間差異顯著時(shí)的對比模式。受符號序列的對比模式挖掘算法［14］的啟發(fā)，本文在時(shí)間序列數(shù)據(jù)上探索了對比保序模式挖掘（Contrast Order-preserving Pattern Mining， COPM），并提出一種高效的COPM算法，該算法可以有效地發(fā)現(xiàn)不同類別時(shí)間序列數(shù)據(jù)集的差異。

本文的主要工作如下：

1）在候選模式生成方面，采用模式融合策略，大幅減少了候選模式數(shù)。

2）在支持度計(jì)算（Support Calculation， SC）方面，COPM算法使用子模式匹配結(jié)果計(jì)算超模式的支持度，大幅縮短了運(yùn)行時(shí)間，降低了時(shí)間復(fù)雜度。

3）在對比保序模式判定方面，提出了一種動(dòng)態(tài)最小支持度閾值的剪枝策略，以縮短運(yùn)行時(shí)間。

4）在真實(shí)的時(shí)間序列數(shù)據(jù)集上進(jìn)行了對比實(shí)驗(yàn)，驗(yàn)證了COPM算法的有效性。

1 相關(guān)工作

序列模式挖掘作為數(shù)據(jù)挖掘的一個(gè)重要分支［15-17］，在諸如差分隱私保護(hù)［18］等領(lǐng)域得到了廣泛的應(yīng)用。由于傳統(tǒng)的序列模式挖掘方法在現(xiàn)實(shí)生活中存在諸多問題和局限性，因此研究者們針對用戶的不同需求提出了多種擴(kuò)展方法，如間隙約束序列模式挖掘［19-21］、閉合序列模式挖掘［22］、共生序列模式挖掘［23-25］、高效用序列模式挖掘［26-28］、負(fù)序列模式挖掘［29-30］和面向用戶興趣的三支序列模式挖掘［31］；但是，當(dāng)前序列模式挖掘方法只關(guān)注模式在序列中的出現(xiàn)數(shù)，并未考慮序列的類別信息，導(dǎo)致一些重要模式的丟失。針對此問題，研究者們提出了一些新的模式和挖掘方法，如對比模式挖掘［32-36］的方法旨在找到在一些類別中頻繁出現(xiàn)，但在其他類別中不頻繁出現(xiàn)的序列模式，可被應(yīng)用在序列數(shù)據(jù)集中分析用戶行為。

目前大多數(shù)經(jīng)典的序列模式挖掘算法主要關(guān)注離散字符序列，不能直接應(yīng)用于時(shí)間序列數(shù)據(jù)。由于時(shí)間序列具有高維、海量等結(jié)構(gòu)特征，使用傳統(tǒng)的挖掘方法不僅會降低算法性能，還會影響最終模式挖掘結(jié)果的準(zhǔn)確性和有效性。近些年，時(shí)間序列挖掘成為數(shù)據(jù)挖掘的熱點(diǎn)，各種模式匹配或模式挖掘方法被提出。例如，三支序列模式挖掘?qū)r(shí)間序列的波動(dòng)趨勢分為強(qiáng)、中和弱，而用戶通常比較關(guān)心的是由強(qiáng)和中趨勢組成的模式［31］。為了避免查詢模式與時(shí)間序列之間存在較大偏差，Li等［9］提出了近似序列模式挖掘方法，在進(jìn)行模式匹配和挖掘前，通常使用離散化方法（如分段線性表示方法和符號表示方法）降維處理時(shí)間序列的數(shù)據(jù)。以上方法都采用了一些符號方法將時(shí)間序列轉(zhuǎn)換為符號。

雖然符號化表示方法能夠?qū)r(shí)間序列離散化成字符后進(jìn)行挖掘，但是符號化方法容易引入噪聲，并且符號化方法過于關(guān)注時(shí)間序列中的數(shù)值，忽略了時(shí)間序列上的趨勢變化。近期，研究人員提出了保序模式匹配方法［6］，該方法無需進(jìn)行數(shù)學(xué)變換和符號化，直接使用數(shù)值的相對順序表示時(shí)間序列中元素的秩，能夠直觀地表示時(shí)間序列中的波動(dòng)趨勢。受保序模式匹配的啟發(fā)，武優(yōu)西等［37］提出了一種新的時(shí)間序列模式挖掘方法——保序序列模式挖掘，它重點(diǎn)關(guān)注時(shí)間序列上的波動(dòng)趨勢，能夠找出給定時(shí)間序列中的所有的頻繁保序模式；但該方法在計(jì)算模式支持度的過程中，需要多次掃描數(shù)據(jù)庫，算法效率低。為了進(jìn)一步提高算法的效率，武優(yōu)西等［38］提出了一種保序序列規(guī)則挖掘方法，在挖掘過程中利用子模式的匹配結(jié)果計(jì)算超模式的支持度，提高了挖掘效率。這兩種挖掘方法只是挖掘最精確的保序序列模式，為了滿足不同場景的需要，武優(yōu)西等［39］又提出了一種近似保序序列模式挖掘方法，以挖掘近似程度不同的保序模式。

然而，在上述研究中，保序模式挖掘、保序序列規(guī)則挖掘方法和近似保序序列模式挖掘都只在單類別時(shí)間序列數(shù)據(jù)集上挖掘，忽略了不同類別數(shù)據(jù)間的差異性，為了有效地發(fā)現(xiàn)不同類別時(shí)間序列數(shù)據(jù)集的差異，本文提出了一種COPM算法。

2 問題定義

時(shí)間序列數(shù)據(jù)庫是由多條時(shí)間序列組成的大型時(shí)間序列數(shù)據(jù)集，可以表示為＝｛1，2，…，T，…，T｝，其中T是由一組數(shù)字元素組成的序列。

定義2 秩次。一組中某個(gè)值的秩次是它在組中的排列順序，記作（p）。

定義3 保序模式。一組由秩次表示的模式稱為保序序列模式，簡稱保序模式，記作（）=（（1），（2），…，（p））。

例1 給定時(shí)間序列=｛15，10，18，12，19，14｝，它的子序列是一個(gè)模式，即=（15，10，18，12）。

其中元素15在中是第三小的，那么（15）=3；同理，（10）=1，（18）=4，（12）=2，因而，（）=（3，1，4，2）。

定義6 支持率。如果（，）大于給定的密度閾值，那么，計(jì)數(shù)為1；否則，計(jì)數(shù)為0。模式在時(shí)間分類序列庫中的支持率是所有時(shí)間序列的計(jì)數(shù)和與時(shí)間序列數(shù)之比，記作（，）。

定義7 對比保序模式。為了反映兩類時(shí)間序列的差異，對正類設(shè)定最小支持率閾值；并對負(fù)類設(shè)定最大支持率閾值，如果模式同時(shí)滿足以下兩個(gè)條件，則稱模式是一個(gè)對比保序模式。

3 本文算法

3.1　候選模式生成

候選模式生成的策略主要有枚舉策略和模式融合策略兩種。本節(jié)采用模式融合策略生成候選模式。文獻(xiàn)［12］中的模式融合策略可以有效地減少候選模式數(shù)，相關(guān)定義如下。

定義8 前綴保序模式、后綴保序模式、保序子模式和保序超模式。給定模式=（1，2，…，p），子模式=（（1，2，…，p-1））稱為模式的前綴保序模式，記作=（）；子模式=（（2，3，…，p））稱為模式的后綴保序模式，記作=（）。同時(shí)，和成為的保序子模式，稱為模式和的保序超模式。

定義9 模式融合。給定兩個(gè)長度的保序模式、，若（）=（），那么模式和可以生成長度為+1的超模式。存在兩種情況：

例2介紹生成候選模式的策略。

例2 給定模式=（1，3，2），=（2，1，3），可以生成長度為4的候選模式。

如果將作為前綴模式，作為后綴模式，候選模式生成規(guī)則如下：以（1，3，2）⊕（2，1，3）為例，（）=（）=（2，1），且1≠3，滿足情況1，可以生成1個(gè)長度為4的候選模式=⊕。由于1<3，因此1=1，4=3+1=4；由于2<4，因此2=2=3；由于3<4，因此3=3=2?？梢缘弥?，=（1，3，2，4）。

如果將作為前綴模式，作為后綴模式，候選模式生成規(guī)則如下：以（2，1，3）⊕（1，3，2）為例，（）=（）=（1，2），且1=3，滿足情況2，可以生成2個(gè)長度為4的候選模式，=⊕。由融合規(guī)則可得，=（2，1，4，3），=（3，1，4，2）。

另外一種生成候選模式的策略是枚舉策略，每個(gè)長度為的模式可以生成+1個(gè)候選模式。若對例2采用枚舉法，則每個(gè)模式都可以生成4個(gè)候選模式，以為例，得到的候選模式為（2，4，3，1）、（1，4，3，2）、（1，4，2，3）和（1，3，2，4），則模式（1，3，2）和（2，1，3）將生成8個(gè)候選模式；然而，模式（1，3，2）和（2，1，3）采用模式融合策略僅生成3個(gè)候選模式，因此模式融合策略可以有效地減少候選模式數(shù)。

3.2　支持度計(jì)算

為了避免冗余計(jì)算，支持度計(jì)算的策略主要是利用子模式的匹配結(jié)果計(jì)算超模式的支持度，以縮短運(yùn)行時(shí)間。下面將給出具體的計(jì)算規(guī)則。

挖掘保序模式從長度為2的模式開始，因?yàn)殚L度為1的模式只是一個(gè)點(diǎn)，沒有趨勢波動(dòng)，長度為2的模式只有兩個(gè)點(diǎn)（1，2）和（2，1）。掃描一遍時(shí)間序列，如果子序列的相對順序?yàn)椋?，2），則將它的位置索引存入（1，2）；否則，存入（2，1）。

當(dāng)模式長度大于2時(shí)，采用3.1節(jié)的模式融合策略生成候選模式，由于⊕生成候選模式時(shí)有兩種情況，因此，計(jì)算模式支持度也對應(yīng)兩種情況。

作為前綴保序子模式、作為后綴保序子模式時(shí)，對應(yīng)的匹配集合分別為L，T和L，T。生成的候選超模式對應(yīng)的匹配集合則為L，T和L，T。

情況1=⊕。

情況2，=⊕。

下面通過例3介紹上述模式支持度計(jì)算規(guī)則。

例3 給定時(shí)間序列1=｛15，10，18，12，19，14｝，以及長度為2的保序模式=（1，2）和=（2，1）。

子序列（10，18）和（12，19）對應(yīng)的保序模式為（1，2），因此將它的位置索引（3，5）存入（1，2）；子序列（15，10）、（18，12）和（19，14）對應(yīng)的保序模式為（2，1），因此將它的位置索引（2，4，6）存入（2，1）。最終通過計(jì)算可知，和在時(shí)間序列1上的匹配集合分別為L，T1=｛3，5｝和L，T1=｛2，4，6｝。

算法1 支持度計(jì)算（SC）算法。

輸入 前綴保序子模式，后綴保序子模式，以及它們對應(yīng)的匹配集合L，T和L，T；

輸出 超模式的支持度。

3） 根據(jù)情況2得到匹配集合L，T和L，T

4） ELSE

5） 根據(jù)情況1得到匹配集合L，T

6） END IF

7） RETURN（G，T）.，（K，T）.

3.3　COPM算法

為了更高效地挖掘?qū)Ρ缺Ｐ蚰Ｊ剑竟?jié)設(shè)計(jì)一個(gè)剪枝策略剪枝候選模式，并提出COPM算法。

動(dòng)態(tài)最小支持度閾值的剪枝策略為：若（，+）<，則將模式以及它的超模式剪枝。

COPM算法的具體步驟如下：

步驟1 掃描一次時(shí)間序列數(shù)據(jù)庫。

步驟2 得到（1，2）和（2，1）模式的匹配集合（（1，2），D）和（（2，1），D），并將（1，2）和（2，1）加入候選模式集C（=2）。

步驟3 根據(jù)模式融合策略，由C生成長度為+1的候選超模式。

步驟4 利用SC算法計(jì)算模式的支持度，繼而根據(jù)剪枝策略進(jìn)行剪枝；若不被剪枝，則將它加入候選模式集C。最終若為對比保序模式，則將該模式加入結(jié)果集。

步驟5 重復(fù)執(zhí)行步驟3～4，直到?jīng)]有新的候選模式生成。

步驟6 最終得到所有符合條件的對比保序模式結(jié)果集。

例4 給定時(shí)間序列數(shù)據(jù)庫，如表1所示。序號為1～3的時(shí)間序列為一組，即某一類時(shí)間序列庫，類別標(biāo)簽用+表示；序號為4～6的時(shí)間序列為另一組，即另一類時(shí)間序列庫，類別標(biāo)簽用-表示。設(shè)置最小密度閾值=0.1，正類最小支持率閾值=0.5，負(fù)類最大支持率閾值=0.1，挖掘中所有的對比保序模式。

表1時(shí)間序列數(shù)據(jù)庫示例

Tab.1　Example of time series database D

注：序號1～6代表有6條時(shí)間序列。

根據(jù)步驟1，掃描時(shí)間序列數(shù)據(jù)庫。

根據(jù)步驟2，可以得到（（1，2），D）和（（2，1），D），并得到2=｛（1，2），（2，1）｝。

根據(jù)步驟3，由長度為2的模式（1，2）和（2，1）可以生成長度為3的候選模式（1，2，3）、（1，3，2）、（2，3，1）、（2，1，3）、（3，1，2）和（3，2，1）。

根據(jù)步驟4，利用SC算法計(jì)算支持度。以模式=（1，3，2）為例，通過SC算法計(jì)算可知模式在1、2、3、4、5和6中的支持度分別為2、2、2、0、0和0。再根據(jù)定義5，可以計(jì)算得出模式在1、2、3、4、5和6中的密度值分別為0.33、0.4、0.4、0、0和0。最后根據(jù)定義6計(jì)算可知，（，+）=3/3=1，（，-）=0/3=0。由于1>，則不會被剪枝，將模式加入候選模式集3；且0<，則模式符合對比保序模式定義。因此，模式是一個(gè)對比保序模式，將模式（1，3，2）加入結(jié)果集。

根據(jù)步驟5，重復(fù)執(zhí)行步驟3和4，直到?jīng)]有新的候選模式生成，最終得到所有符合條件的對比保序模式集為=｛（1，3，2），（2，1，3），（1，3，2，4），（3，1，4，2），（1，4，2，5，3）｝。

算法2 COPM算法。

輸入 時(shí)間序列數(shù)據(jù)庫，最小密度閾值，正類最小支持率閾值，負(fù)類最大支持率閾值；

輸出 對比保序模式結(jié)果集。

1） 掃描一次時(shí)間序列數(shù)據(jù)庫，得到（（1，2），D）和（（2，1），D），并得到2=｛（1，2），（2，1）｝

2）←2

3） WHILEC！= null DO

4） FOR eachinCDO

5） FOR eachinCDO

6） IFcan fuse withTHEN

7） 根據(jù)模式融合策略生成超模式

8） 利用SC算法計(jì)算超模式的支持度，再根據(jù)定義5、6得到超模式支持率（，+）

9） IF（，+）≥THEN

10） 將模式加入候選模式集C+1，再計(jì)算（，-）

11） IF（，-）≤THEN

12） 將模式加入結(jié)果集

13） END IF

14） END IF

15） END IF

16） END FOR

17） END FOR

18）←+1；

19） END WHILE

20） RETURN

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

4.1　實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證COPM算法的性能，本文采用真實(shí)的時(shí)間序列數(shù)據(jù)集作為測試數(shù)據(jù)集，數(shù)據(jù)集中的數(shù)據(jù)分為兩類。所有的數(shù)據(jù)集都可以在http：//www.timeseriesclassification.com/dataset.php網(wǎng)站下載。表2給出了每個(gè)數(shù)據(jù)集的具體描述。

表2實(shí)驗(yàn)數(shù)據(jù)集

Tab.2　Experimental datasets

實(shí)驗(yàn)運(yùn)行的環(huán)境為：Inter Core i5-3230U處理器，主頻1.60 GHz，內(nèi)存8 GB，Windows 10，64位操作系統(tǒng)，程序的開發(fā)環(huán)境為Eclipse。

4.2　對比算法

1）COPM-o（COPM-original）。為了分析COPM算法計(jì)算支持率的效率，提出了COPM-o算法，該算法采用Wu等［12］提出的保序模式匹配方法計(jì)算候選模式支持率。

2）COPM-e（COPM-enumeration）。為了分析模式融合策略的性能，提出了COPM-e算法，該算法采用枚舉策略生成候選模式。

3）COPM-p（COPM-prune）。為了驗(yàn)證2.3節(jié)中的剪枝策略的效果，提出了COPM-p算法，該算法未采用該剪枝策略。

4.3　COPM算法的挖掘效果

為了驗(yàn)證COPM算法的有效性，本文采用COPM-o、COPM-e和COPM-p這3個(gè)對比算法。在D1～D6這6個(gè)數(shù)據(jù)集上實(shí)驗(yàn)，設(shè)置=0.01，=0.25，=0.1。表3分別給出在數(shù)據(jù)集D1～D6上的內(nèi)存消耗、運(yùn)行時(shí)間和候選模式數(shù)的對比。在D1～D6數(shù)據(jù)集上，在內(nèi)存消耗方面，COPM算法至少比COPM-o算法降低52.1%，比COPM-e算法降低36.8%，比COPM-p算法降低63.6%；同時(shí)在運(yùn)行時(shí)間方面，COPM算法至少比COPM-o算法降低30.3%，比COPM-e算法降低8.8%，比COPM-p算法降低41.2%。通過觀察表3可以得到如下結(jié)論：

1）COPM算法優(yōu)于COPM-o算法，因?yàn)镃OPM算法不僅比COPM-o算法消耗更少的內(nèi)存，而且運(yùn)行時(shí)間更短，這表明COPM算法采用了比COPM-o算法更有效的策略計(jì)算支持率，即本文的支持度計(jì)算方法能夠縮短運(yùn)行時(shí)間。例如，從表3可以看出，在D1上，兩種算法都生成了161個(gè)候選模式，在D1上，COPM算法消耗內(nèi)存16.284 MB，花費(fèi)了0.165 s；而COPM-o算法消耗內(nèi)存為67.451 MB，花費(fèi)了0.607 s。在其他數(shù)據(jù)集上也可以發(fā)現(xiàn)同樣結(jié)果。原因如下：COPM-o算法采用的模式匹配的策略不能很好地利用子模式的計(jì)算結(jié)果，必須重復(fù)掃描數(shù)據(jù)庫，導(dǎo)致計(jì)算效率低；相反，COPM算法只需掃描一次數(shù)據(jù)庫，并且利用子模式的計(jì)算結(jié)果計(jì)算超模式的支持度，避免了許多冗余的計(jì)算，從而縮短運(yùn)行時(shí)間。因此，COPM算法優(yōu)于COPM-o算法。

2）COPM算法優(yōu)于COPM-e算法，這表明模式融合策略可以有效地剪枝候選模式。從表3可以看出，COPM算法比COPM-e算法消耗更少的內(nèi)存，且COPM算法比COPM-e算法運(yùn)行時(shí)間更短。例如，在D1上，COPM算法消耗內(nèi)存16.284 MB，花費(fèi)時(shí)間為0.165 s。而COPM-e算法消耗內(nèi)存29.905 MB，花費(fèi)時(shí)間為0.221 s。其他數(shù)據(jù)集上也是同樣的效果。原因如下：模式融合策略可以有效地剪枝候選模式。例如，從表3可以看出，在D1上，COPM算法生成了161個(gè)候選模式，而COPM-e算法生成了235個(gè)候選模式，與COPM算法相比，COPM-e算法生成的候選模式數(shù)多了45.9%。候選模式數(shù)越少，算法運(yùn)行越快，算法消耗的內(nèi)存越少；因此，COPM算法優(yōu)于COPM-e算法。

3）COPM算法優(yōu)于COPM-p算法，這表明剪枝策略能進(jìn)一步縮短運(yùn)行時(shí)間。從表3可以看出，在所有數(shù)據(jù)集上COPM算法均比COPM-p算法消耗更少的內(nèi)存，并且花費(fèi)更少的運(yùn)行時(shí)間。例如，在D1上，COPM算法消耗內(nèi)存為16.284 MB，花費(fèi)時(shí)間為0.165 s；而COPM-p算法消耗內(nèi)存為189.285 MB，花費(fèi)時(shí)間為336.734 s。這是因?yàn)榧糁Σ呗钥梢杂行У販p少候選模式數(shù)。在D1上，COPM-p算法生成的候選模式數(shù)為29 925，而COPM算法生成的候選模式數(shù)僅為161，與COPM算法相比，COPM-p算法生成的候選模式數(shù)量多了99.5%，因此，COPM算法優(yōu)于COPM-p算法。

表3不同算法在數(shù)據(jù)集D1～D6上不同指標(biāo)對比

Tab.3　Comparison of different algorithms with different indicators on dataset D1 to D6

4.4　可擴(kuò)展性

為了驗(yàn)證COPM算法的可擴(kuò)展性，本文采用COPM-o、COPM-e和COPM-p算法作為對比算法；此外，選擇D6數(shù)據(jù)集作為實(shí)驗(yàn)基礎(chǔ)數(shù)據(jù)集，并且創(chuàng)建了D6_1，D6_2，D6_3，D6_4，D6_5和D6_6實(shí)驗(yàn)數(shù)據(jù)集，它們分別是D6數(shù)據(jù)集大小的1、2、3、4、5和6倍。參數(shù)設(shè)置為=0.01，=0.25，=0.1。內(nèi)存消耗和運(yùn)行時(shí)間的結(jié)果對比分別如表4所示。

表4不同數(shù)據(jù)集大小下的內(nèi)存消耗和運(yùn)行時(shí)間對比

Tab.4　Comparison of memory consumption and running time with different dataset sizes

由表4可知，COPM算法的內(nèi)存消耗和運(yùn)行時(shí)間都隨數(shù)據(jù)集大小的增加呈線性增長。例如，與D6_1相比，D6_6的長度增加了500%，COPM算法在D6_1上內(nèi)存消耗為21.973 MB，而在D6_6上內(nèi)存消耗為94.395 MB，與D6_1相比，COPM算法在D6_6上的內(nèi)存消耗增長了329.6%，在D6_1上運(yùn)行時(shí)間為0.217 s，而在D6_6上運(yùn)行時(shí)間為0.923 s，與D6_1相比，COPM算法在D6_6上的運(yùn)行時(shí)間增加了325.4%。因此，內(nèi)存消耗和運(yùn)行時(shí)間的增加明顯慢于數(shù)據(jù)集大小的增長。這些結(jié)果表明，COPM算法的時(shí)間和空間復(fù)雜度與數(shù)據(jù)集大小呈正相關(guān)。在其他數(shù)據(jù)集也有相同的規(guī)律。更重要地，在所有數(shù)據(jù)集上，COPM算法的挖掘性能比其他對比算法更優(yōu)，COPM算法的內(nèi)存消耗明顯少于其他對比算法，并且運(yùn)行時(shí)間比其他對比算法都更短。因此，根據(jù)COPM算法的挖掘性能不會隨著數(shù)據(jù)集大小的增加而降低，進(jìn)而可以得出結(jié)論，COPM算法具有很強(qiáng)的可擴(kuò)展性。

4.5　不同密度閾值對算法性能的影響

從圖1、2可以看出，一般情況下，隨著密度閾值的增大，COPM算法生成的候選模式數(shù)更少，運(yùn)行時(shí)間更短。例如，在D3上，當(dāng)=0.01和=0.025時(shí)，運(yùn)行時(shí)間分別是0.271 s和0.170 s；生成的候選模式數(shù)分別為275和118。產(chǎn)生這一現(xiàn)象的原因如下：隨著值的增加，密度值大于最小密度閾值的候選模式數(shù)顯著減少，使算法運(yùn)行時(shí)間更短。

圖1　D1～D6上不同den值下的運(yùn)行時(shí)間對比

圖2　D1～D6上不同den值下的候選模式數(shù)對比

5 結(jié)語

本文提出了一種基于時(shí)間序列數(shù)據(jù)庫的COPM算法，可以發(fā)現(xiàn)不同類別時(shí)間序列數(shù)據(jù)集間的差異性。該算法主要分為候選模式生成和支持度計(jì)算兩個(gè)步驟：在候選模式生成階段，本文采用模式融合策略，大幅減少了候選模式數(shù)；在支持度計(jì)算階段，本文利用子模式的匹配結(jié)果計(jì)算超模式的支持度，避免了重復(fù)掃描數(shù)據(jù)庫，大幅縮短了算法的運(yùn)行時(shí)間。為了進(jìn)一步有效地挖掘?qū)Ρ缺Ｐ蚰Ｊ?，提出了?dòng)態(tài)最小支持率閾值的剪枝策略進(jìn)一步減少候選模式數(shù)，以減少算法的運(yùn)行時(shí)間。通過與3個(gè)對比算法對比實(shí)驗(yàn)，得出了COPM算法在內(nèi)存消耗、運(yùn)行時(shí)間和候選模式生成方面的性能均優(yōu)于其他算法，驗(yàn)證了COPM算法具有較強(qiáng)的可擴(kuò)展性。本文還驗(yàn)證了不同密度閾值對算法性能的影響。綜上所述，本文的實(shí)驗(yàn)結(jié)果均驗(yàn)證了COPM算法的有效性。

多分類問題可以通過一對多的方式或者樹形多級的方式轉(zhuǎn)換為多個(gè)二分類問題，因此，針對多類數(shù)據(jù)集挖掘問題，可以采用多次二分類的方式進(jìn)行對比模式挖掘；但是該挖掘方式過于復(fù)雜，未來將進(jìn)一步研究如何直接在多分類數(shù)據(jù)集上進(jìn)行對比模式挖掘；此外，我們還將繼續(xù)研究如何有效地應(yīng)用挖掘結(jié)果指導(dǎo)分類。

[1] LIN Y， LIN Z X， LIAO Y， et al. Forecasting the realized volatility of stock price index： a hybrid model integrating CEEMDAN and LSTM ［J］. Expert Systems with Applications， 2022， 206： 117736.

[2] MAN J， DONG H H， GAO J Y， et al. GA-GRGAT： a novel deep learning model for high-speed train axle temperature long term forecasting ［J］. Expert Systems with Applications， 2022， 202： 117033.

[3] DAI C L， WU J， PI D C， et al. Brain EEG time-series clustering using maximum-weight clique ［J］. IEEE Transactions on Cybernetics， 2022， 52（1）： 357-371.

[4] CHAKRABARTI K， KEOGH E， MEHROTRA S， et al. Locally adaptive dimensionality reduction for indexing large time series databases ［J］. ACM Transactions on Database Systems， 2002， 27（2）： 188-228.

[5] LIN J， KEOGH E， WEI L， et al. Experiencing SAX： a novel symbolic representation of time series ［J］. Data Mining and Knowledge Discovery. 2007， 15（2）： 107-144.

[6] KIM J， EADES P， FLEISCHER R， et al. Order-preserving matching ［J］. Theoretical Computer Science， 2014， 525（13）： 68-79.

[7] 武優(yōu)西，劉茜，閆文杰，等. 無重疊條件嚴(yán)格模式匹配的高效求解算法［J］. 軟件學(xué)報(bào)， 2021， 32（11）： 3331-3350.（WU Y X， LIU X， YAN W J， et al. Efficient algorithm for solving strict pattern matching under nonoverlapping condition ［J］. Journal of Software， 2021， 32（11）： 3331-3350.）

[8] CHO S， NA J C， PARK K， et al. A fast algorithm for order-preserving pattern matching ［J］. Information Processing Letters， 2015， 115（2）： 397-402.

[9] LI Y， YU L， LIU J， et al. NetDPO：（delta， gamma）-approximate pattern matching with gap constraints under one-off condition ［J］. Applied Intelligence， 2022， 52（11）： 12155-12174.

[10] CHHABRA T， TARHIO J. A filtration method for order-preserving matching ［J］. Information Processing Letters， 2016， 116（2）： 71-74.

[11] KIM Y， KANG M， NA J C， et al. Order-preserving pattern matching with scaling ［J］. Information Processing Letters， 2023， 180： 106333.

[12] WU Y X， HU Q， LI Y， et al. OPP-Miner： order-preserving sequential pattern mining for time series ［EB/OL］. ［2022-02-09］. https：//arxiv.org/pdf/2202.03140.pdf.

[13] WU Y X， ZHAO X Q， LI Y， et al. OPR-Miner： order-preserving rule mining for time series ［EB/OL］. ［2022-12-04］. https：//arxiv.org/pdf/2209.08932.pdf.

[14] WU Y X， WANG Y H， LI Y， et al. Top-self-adaptive contrast sequential pattern mining ［J］. IEEE Transactions on Cybernetics， 2022， 52（11）： 11819-11833.

[15] GAN W S， LIN J C， FOURNIER-VIGER P， et al. A survey of parallel sequential pattern mining ［J］. ACM Transactions on Knowledge Discovery from Data， 2019， 13（3）： 1-34.

[16] OKOLICA J S， PETERSON G L， MILLS R F， et al. Sequence pattern mining with variables ［J］. IEEE Transactions on Knowledge and Data Engineering， 2020， 32（1）： 177-187.

[17] SAMARIYA D， MA J. A new dimensionality-unbiased score for efficient and effective outlying aspect mining［J］. Data Science and Engineering， 2022， 7（2）： 120-135.

[18] 李艷輝，劉浩，袁野，等. 基于差分隱私的頻繁序列模式挖掘算法［J］. 計(jì)算機(jī)應(yīng)用， 2017， 37（2）： 316-321.（LI Y H， LIU H， YUAN Y， et al. Frequent sequence pattern mining with differential privacy ［J］. Journal of Computer Applications， 2017， 37（2）： 316-321.）

[19] WU Y X， TONG Y， ZHU X Q， et al. NOSEP： nonoverlapping sequence pattern mining with gap constraints ［J］. IEEE Transactions on Cybernetics， 2018， 48（10）： 2809-2822.

[20] 武優(yōu)西，周坤，劉靖宇，等. 周期性一般間隙約束的序列模式挖掘［J］. 計(jì)算機(jī)學(xué)報(bào)， 2017， 40（6）： 1338-1352.（WU Y X， ZHOU K， LIU J Y， et al. Mining sequential patterns with periodic general gap constraints ［J］. Chinese Journal of Computers， 2017， 40（6）： 1338-1352.）

[21] LI Y， ZHANG S， GUO L， et al. NetNMSP： nonoverlapping maximal sequential pattern mining ［J］. Applied Intelligence. 2022， 52（9）： 9861-9884.

[22] WU Y X， ZHU C R， LI Y， et al. NetNCSP： nonoverlapping closed sequential pattern mining ［J］. Knowledge-Based Systems， 2020， 196： 105812.

[23] WANG L Z， BAO X G， ZHOU L H. Redundancy reduction for prevalent co-location patterns ［J］. IEEE Transactions on Knowledge and Data Engineering， 2018， 30（1）： 142-155.

[24] 王曉璇，王麗珍，陳紅梅，等. 基于特征效用參與率的空間高效用co-location模式挖掘方法［J］. 計(jì)算機(jī)學(xué)報(bào)， 2019， 42（8）： 1721-1738.（WANG X X， WANG L Z， CHEN H M， et al. Mining spatial high utility co-location patterns based on feature utility ratio ［J］. Chinese Journal of Computers， 2019， 42（8）： 1721-1738.）

[25] 馬董，陳紅梅，王麗珍，等. 空間亞頻繁co-location模式的主導(dǎo)特征挖掘［J］. 計(jì)算機(jī)應(yīng)用， 2020， 40（2）： 465-472.（MA D， CHEN H M， WANG L Z， et al. Dominant feature mining of spatial sub-prevalent co-location patterns ［J］. Journal of Computer Applications， 2020， 40（2）： 465-472.）

[26] LIU C H， GUO C H. Mining top-N high-utility operation patterns for taxi drivers ［J］. Expert Systems with Applications， 2021， 170： 114546.

[27] WU Y X， GENG M， LI Y， et al. HANP-Miner： high average utility nonoverlapping sequential pattern mining ［J］. Knowledge-Based Systems， 2021， 229： 107361.

[28] GAN W S， LIN J C， FOURNIER-VIGER P， et al. HUOPM： high-utility occupancy pattern mining ［J］. IEEE Transactions on Cybernetics， 2020， 50（3）： 1195-1208.

[29] WU Y X， CHEN M J， LI Y， et al. ONP-Miner： one-off negative sequential pattern mining ［EB/OL］. ［2022-07-25］. https：//arxiv.org/pdf/2207.11950.pdf.

[30] DONG X J， GONG Y S， CAO L B. e-RNSP： an efficient method for mining repetition negative sequential patterns ［J］. IEEE Transactions on Cybernetics， 2020， 50（5）： 2084-2096.

[31] WU Y X， LUO L F， LI Y， et al. NTP-Miner： nonoverlapping three-way sequential pattern mining ［J］. ACM Transaction on Knowledge Discovery from Data， 2022， 16（3）： 51.

[32] JI X N， BAILEY J， DONG G Z. Mining minimal distinguishing subsequence patterns with gap constraints ［J］. Knowledge and Information Systems， 2007， 11（3）： 259-286.

[33] WANG X M， DUAN L， DONG G Z， et al. Efficient mining of density-aware distinguishing sequential patterns with gap constraints ［J］. Database Systems for Advanced Applications， 2014， 8421： 372-387.

[34] 段磊，唐常杰，楊寧，等. 基于顯露模式的對比挖掘研究及應(yīng)用進(jìn)展［J］. 計(jì)算機(jī)應(yīng)用， 2012， 32（2）：304-308.（DUAN L， TANG C J， YANG N， et al. Survey on emerging pattern based contrast mining and applications ［J］. Journal of Computer Applications， 2012， 32（2）： 304-308.）

[35] WU Y X， WANG Y H， LIU J Y， et al. Mining distinguishing subsequence patterns with nonoverlapping condition ［J］. Cluster Computing， 2019， 22： 5905-5907.

[36] HE Z Y， ZHANG S M， GU F Y， et al. Mining conditional discriminative sequential patterns ［J］. Information Sciences， 2019， 478： 524-539.

[37] 武優(yōu)西，戶倩，郭媛，等.保序序列模式挖掘方法： CN202010544303.5 ［P］. 2020-06-15.（WU Y X， H Q， GUO Y， et al. Order-preserving sequential pattern mining algorithm： CN202010544303.5 ［P］. 2020-06-15.）

[38] 武優(yōu)西，趙曉倩，李艷，等.保序序列規(guī)則挖掘方法： CN202210294476.5 ［P］. 2022-03-23.（WU Y X， ZHAO X Q， LI Y， et al. Order-preserving sequential rule mining algorithm： CN202210294476.5 ［P］. 2022-03-23.）

[39] 武優(yōu)西，劉錦，耿萌，等.近似保序序列模式挖掘方法： CN202210295950.6 ［P］. 2022-03-23.（WU Y X， LIU J， GENG M， et al. Approximate order-preserving sequential pattern mining algorithm： CN202210295950.6 ［P］. 2022-03-23.）

Contrast order-preserving pattern mining algorithm

MENG Yufei1， WU Youxi1*， WANG Zhen1， LI Yan2

（1，，300401，；2，，300401，）

Aiming at the problem that the existing contrast sequential pattern mining methods mainly focus on character sequence datasets and are difficult to be applied to time series datasets， a new Contrast Order-preserving Pattern Mining （COPM） algorithm was proposed. Firstly， in the candidate pattern generation stage， a pattern fusion strategy was used to reduce the number of candidate patterns. Then， in the pattern support calculation stage， the support of super-pattern was calculated by using the matching results of sub-patterns. Finally， a dynamic pruning strategy of minimum support threshold was designed to further effectively prune the candidate patterns. Experimental results show that on six real time series datasets， the memory consumption of COPM algorithm is at least 52.1% lower than that of COPM-o （COPM-original） algorithm， 36.8% lower than that of COPM-e （COPM-enumeration） algorithm， and 63.6% lower than that of COPM-p （COPM-prune） algorithm. At the same time， the running time of COPM algorithm is at least 30.3% lower than that of COPM-o algorithm， 8.8% lower than that of COPM-e algorithm and 41.2% lower than that of COPM-p algorithm. Therefore， in terms of algorithm performance， COPM algorithm is superior to COPM-o， COPM-e and COPM-p algorithms. The experimental results verify that COPM algorithm can effectively mine the contrast order-preserving patterns to find the differences between different classes of time series datasets.

pattern mining; sequential pattern mining; time series; contrast pattern; order-preserving pattern

This work is partially supported by Natural Science Foundation of Hebei Province （F20202013）.

MENG Yufei， born in 1995， M. S. candidate. Her research interests include data mining.

WU Youxi， born in 1974， Ph. D.， professor. His research interests include data mining， machine learning.

WANG Zhen， born in 1997， M. S. candidate. Her research interests include data mining.

LI Yan， born in 1975， Ph. D.， associate professor. Her research interests include data mining， supply chain management.

TP311.13

A

1001-9081（2023）12-3740-07

10.11772/j.issn.1001-9081.2022121828

2022?12?09；

2023?02?24；

2023?02?28。

河北省自然科學(xué)基金資助項(xiàng)目（F2020202013）。

孟玉飛（1995—），女，河北石家莊人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘；武優(yōu)西（1974—），男，天津人，教授，博士，CCF杰出會員，主要研究方向：數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)；王珍（1997—），女，河南周口人，碩士研究生，主要研究方向：數(shù)據(jù)挖掘；李艷（1975—），女，天津人，副教授，博士，主要研究方向：數(shù)據(jù)挖掘、供應(yīng)鏈管理。