劉 錦，武優(yōu)西，王月華，李 艷

1(河北工業(yè)大學(xué) 人工智能學(xué)院，天津 300401) 2(河北工業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院，天津 300401)

1 引 言

序列模式挖掘[1]是數(shù)據(jù)挖掘[2]的一個(gè)熱門(mén)領(lǐng)域，在近年來(lái)獲得了信息產(chǎn)業(yè)的極大關(guān)注.隨著網(wǎng)絡(luò)信息技術(shù)[3]的飛速發(fā)展，序列模式挖掘在大數(shù)據(jù)時(shí)代的重要性和必要性日益凸顯，由于序列模式挖掘具有高效、可解釋性強(qiáng)的特性，目前已被廣泛應(yīng)用在生物信息學(xué)[4]、疾病檢測(cè)[5，6]、市場(chǎng)營(yíng)銷(xiāo)[7]、網(wǎng)絡(luò)安全[8，9]等領(lǐng)域.時(shí)間序列數(shù)據(jù)[10]作為一種常見(jiàn)而重要的數(shù)據(jù)，廣泛存在于人類(lèi)的生產(chǎn)生活中，與字符序列不同，時(shí)間序列數(shù)據(jù)是按照時(shí)間順序排列而成的數(shù)值序列，蘊(yùn)含著大量的規(guī)律信息，為了快速有效地獲得其中有價(jià)值的信息，研究者們提出了諸多時(shí)間序列分析方法，如序列模式挖掘方法[11]、離散短時(shí)傅里葉變換法[12]和邏輯回歸法[13]等.

然而在一些實(shí)際應(yīng)用中，有時(shí)元素值的變化趨勢(shì)要比元素值本身更有意義.例如在股票分析中，股票的變化趨勢(shì)要比股票的實(shí)際價(jià)格更值得研究；在氣溫預(yù)測(cè)方面，氣溫的變化顯然比氣溫?cái)?shù)值的大小更有意義，因此保序序列模式挖掘應(yīng)運(yùn)而生.保序序列模式挖掘是序列模式挖掘的一個(gè)新的分支，它適用于時(shí)間序列，關(guān)注的是元素值的變化趨勢(shì)而不是數(shù)值大小，所以它能挖掘出現(xiàn)頻率較高的趨勢(shì)圖.保序序列模式挖掘保證了時(shí)間序列的連續(xù)性，挖掘出的代表性趨勢(shì)使得人們可以更好地認(rèn)識(shí)事物的內(nèi)在變化規(guī)律.為了可以靈活地挖掘保序模式，本文提出基于(δ-γ)距離的近似保序序列模式挖掘算法(Approximate Order Preserving Pattern Mining，AOPM)，用來(lái)挖掘近似程度不同的保序模式.下面通過(guò)例1來(lái)說(shuō)明近似保序序列模式挖掘問(wèn)題.

例1.時(shí)間序列S=(19，16，21，18，20，13，8，22，5，11，18，15，19，12，6，11)，minsup=2.

若采用近似保序序列模式挖掘算法，可以挖掘出時(shí)間序列S中頻繁出現(xiàn)的趨勢(shì)圖(如圖1所示).如當(dāng)δ=0，γ=0時(shí)，可以挖掘出兩個(gè)子序列S1(18，20，13，8)和S2(15，19，12，6)，它們的保序模式完全相同，都為(3，4，2，1).當(dāng)δ=1，γ=2時(shí)，則可以挖掘出更長(zhǎng)的保序模式，如兩個(gè)子序列S3(16，21，18，20，13，8)和S4(11，18，15，19，12，6)，它們的保序模式分別為(3，6，4，5，2，1)和(2，5，4，6，3，1).S3和S4的保序模式雖然不完全相同，但與保序模式(3，5，4，6，2，1)具有很高的相似性，這是因?yàn)镾3和S4與它在每個(gè)位置的局部誤差都滿(mǎn)足≤δ=1，總誤差滿(mǎn)足≤γ=2，可以認(rèn)為保序模式(3，5，4，6，2，1)的相似趨勢(shì)在S中出現(xiàn)了兩次，滿(mǎn)足最小支持度閾值，因此(3，5，4，6，2，1)是一個(gè)頻繁的近似保序模式.

圖1 時(shí)間序列S的趨勢(shì)變化圖Fig.1 Trend graph of the time series S

本文的貢獻(xiàn)如下：

1)為了可以靈活地挖掘保序序列模式，提出了局部誤差不超過(guò)δ且整體誤差不超過(guò)γ的近似保序模式挖掘問(wèn)題.

2)為了完備地解決這個(gè)問(wèn)題，我們提出了AOPM算法.在生成候選模式方面，采用了前后綴拼接的模式融合策略，不會(huì)生成無(wú)意義的候選模式，減少了候選模式的范圍.在模式支持度計(jì)算方面，首選獲取候選模式的全部候選序列，然后在進(jìn)行模式匹配.

3)在真實(shí)的時(shí)間序列數(shù)據(jù)集上進(jìn)行了對(duì)比實(shí)驗(yàn)，驗(yàn)證了AOPM算法的完備性和高效性.

本文剩余部分安排如下：第2節(jié)總結(jié)相關(guān)工作；第3節(jié)給出了AOPM問(wèn)題的相關(guān)定義；第4節(jié)提出AOPM算法，并分析算法的時(shí)空復(fù)雜度；第5節(jié)驗(yàn)證AOPM算法的性能；第6節(jié)得出了本文結(jié)論.

2 相關(guān)工作

序列模式挖掘作為當(dāng)前的研究熱點(diǎn)之一旨在快速找出滿(mǎn)足用戶(hù)特定需求的模式，針對(duì)不同問(wèn)題，已經(jīng)衍生出多種形式的挖掘方法，如間隙約束挖掘方法[14，15]、負(fù)序列挖掘方法[16]、高效用挖掘方法[17]、序列規(guī)則挖掘方法[18]等.序列模式挖掘方法可以采用多種形式進(jìn)行劃分，如模式支持度計(jì)算方式的不同和挖掘數(shù)據(jù)性質(zhì)的不同等角度進(jìn)行劃分.

根據(jù)模式支持度計(jì)算方式的不同，可以將序列模式挖掘分為精確序列模式挖掘和近似序列模式挖掘.Lin等人采用PAA方法將時(shí)間序列進(jìn)行分段并對(duì)求每段的平均值，然后再挖掘其中的頻繁模式；Min等人根據(jù)數(shù)據(jù)波動(dòng)將數(shù)字時(shí)間序列轉(zhuǎn)換為字符型序列，并運(yùn)用在具有弱通配符間隙的模式挖掘中，這些研究都屬于精確序列模式挖掘.而B(niǎo)ae等人利用效用容忍因子計(jì)算模式的可信效用，進(jìn)而從噪聲數(shù)據(jù)庫(kù)中提取魯棒的高效用模式則屬于近似序列模式挖掘.

根據(jù)挖掘數(shù)據(jù)性質(zhì)的不同，又可以將序列模式挖掘分為字符序列模式挖掘[19]和時(shí)間序列挖掘[20].字符序列模式挖掘主要針對(duì)DNA序列和基因序列等由字符構(gòu)成的字符型序列，挖掘字符序列通常是為了解決生物信息學(xué)中的問(wèn)題.時(shí)間序列挖掘的對(duì)象則是由連續(xù)變化的數(shù)值構(gòu)成的數(shù)值型序列，通常首先采用SAX算法將時(shí)間序列符號(hào)化[21，22]，然后在使用不同的方法進(jìn)行挖掘，如計(jì)算時(shí)間序列的先驗(yàn)移動(dòng)平均的方法、線(xiàn)性回歸的方法等.保序模式挖掘的對(duì)象就是時(shí)間序列，通過(guò)挖掘其中頻繁出現(xiàn)的趨勢(shì)圖，可以幫助人們進(jìn)行分析和預(yù)測(cè)，如股票市場(chǎng)的股價(jià)波動(dòng)分析，某個(gè)地點(diǎn)的氣溫變化分析以及用戶(hù)行為分析[23]等.

由于時(shí)間序列具有高維性、連續(xù)性等特點(diǎn)，直接對(duì)其進(jìn)行挖掘是非常困難的，需要通過(guò)一系列轉(zhuǎn)換將原始的數(shù)值型數(shù)據(jù)轉(zhuǎn)換為其它域的數(shù)據(jù)再進(jìn)行挖掘，轉(zhuǎn)換的實(shí)質(zhì)就是對(duì)時(shí)間序列模式來(lái)進(jìn)行重新表示.保序模式匹配問(wèn)題就與時(shí)間序列的次序關(guān)系表示緊密相關(guān)，基于次序關(guān)系的表示與數(shù)值型表示并不相同，數(shù)值型表示是原始的時(shí)間序列數(shù)據(jù)，而次序關(guān)系則是用元素在序列中的秩次進(jìn)行表示的，所以有相對(duì)順序的概念.Kim等人[22]首先將元素之間的次序關(guān)系定義為二元關(guān)系(<，>)，并提出了相對(duì)順序的前綴表示和最近鄰表示，但沒(méi)有考慮元素間數(shù)值相等的情況.然而兩個(gè)數(shù)值之間的次序關(guān)系實(shí)際上是三元(<，=，>)的，因此Cho等人[23]對(duì)其進(jìn)行了擴(kuò)展，將二元關(guān)系擴(kuò)展為三元關(guān)系，并設(shè)計(jì)了一種即使存在元素相等的情況，也能判斷兩個(gè)字符串是否順序同構(gòu)的算法.它要求模式與子序列的相對(duì)順序完全相同，能快速定位與已知模式趨勢(shì)變化完全相同的子序列，為此，Wu等人[24]提出了保序模式挖掘算法OPP-Miner，用來(lái)發(fā)現(xiàn)時(shí)間序列中的隱藏規(guī)律.上述研究屬于精確匹配的研究.而在一定數(shù)據(jù)噪音存在的場(chǎng)景下，需要研究近似模式匹配，如Wu等人允許模式和匹配子序列之間存在數(shù)據(jù)噪聲，提出了一種帶長(zhǎng)度約束的(δ-γ)近似預(yù)測(cè)方法，用來(lái)找到更加有價(jià)值的模式.又如Paw等人[25]提出基于Hamming距離度量相似度的匹配的精確度，若兩個(gè)字符串在相同位置刪除最多k個(gè)元素后具有相同的相對(duì)順序則匹配成功，但該問(wèn)題的匹配結(jié)果存在偏差，因?yàn)闊o(wú)法度量子序列與模式之間的局部近似度.Juan等人[26]提出基于(δ-γ)距離的相似度度量方法改善了此問(wèn)題，采用局部-整體約束，提高了匹配的精確度.表1給出了相關(guān)研究工作對(duì)比.

表1 相關(guān)研究工作對(duì)比Table 1 Comparison of related research work

從表1可以看出：文獻(xiàn)[24]與本文的研究最為相近，不同之處在于文獻(xiàn)[24]是精確的保序模式挖掘，而本文是保序模式的近似挖掘.文獻(xiàn)[26]是基于(δ-γ)距離的保序模式匹配，而本文研究的是保序模式挖掘.文獻(xiàn)[25]是基于Hamming距離的保序模式匹配，而本文是(δ-γ)距離近似.本文將(δ-γ)保序匹配引入到保序模式挖掘中來(lái)，挖掘不同約束條件下的頻繁趨勢(shì)圖，適應(yīng)了更多的應(yīng)用領(lǐng)域，更好地幫助人們進(jìn)行分析和預(yù)測(cè).

3 相關(guān)定義

定義1.時(shí)間序列：由n個(gè)有序的連續(xù)數(shù)值構(gòu)成的時(shí)間序列可以表示為S=s1s2…si…sn(1≤i≤n)，其中si可以稱(chēng)為元素.

定義2.秩次：元素pi在長(zhǎng)度為m的模式P=p1p2…pi…pm(1≤i≤m)中的秩次記作rankp(pi)=1+|{x|px

定義3.相對(duì)順序和保序模式：長(zhǎng)度為m的模式P的相對(duì)順序?yàn)閞ankp(p1)rankp(p2)rankpp(p3)…rankp(pm)，由相對(duì)順序所表示的模式就是保序模式.

例2.給定模式P=(19，16，21，18)，由于元素19在模式P中第3小，因此其秩次rankp(19)=3；類(lèi)似的，元素16在模式P中最小，因此rankp(16)=1.進(jìn)而其保序模式r(P)=(3，1，4，2).

定義5.(δ-γ)保序出現(xiàn)：對(duì)于一個(gè)長(zhǎng)度為m的保序模式P，若在時(shí)間序列S中能找到一個(gè)長(zhǎng)度也為m的子序列T，使得P與T的保序模式r(T)滿(mǎn)足(δ-γ)距離約束，則稱(chēng)T是保序模式P在時(shí)間序列S中的一次(δ-γ)保序出現(xiàn)，其中δ和γ是兩個(gè)給定的非負(fù)整數(shù).

定義6.頻繁保序模式：如果保序模式P在時(shí)間序列S中的(δ-γ)保序出現(xiàn)數(shù)不小于用戶(hù)給定的最小支持度閾值(minsup)，則稱(chēng)P為一個(gè)頻繁的(δ-γ)保序模式.

例3.給定δ=1，γ=2，P=(3，2，4，1)，S=(19，16，21，18，20，13，8，22，5，11，18，15，19，12，6，11).在時(shí)間序列S中可以找到子序列S1=(19，16，21，18)，將S1轉(zhuǎn)化為保序模式后得r(S1)=(3，1，4，2)，P與r(S1)進(jìn)行(δ-γ)保序匹配：|3-3|=0≤δ，|2-1|=1≤δ，|4-4|=0≤δ，|1-2|=1≤δ；0+1+0+1=2≤γ，因此，P和S1滿(mǎn)足(δ-γ)距離約束，S1為P在時(shí)間序列S中的一次(δ-γ)保序出現(xiàn).同理，P在時(shí)間序列S中的另外3個(gè)(δ-γ)保序出現(xiàn)分別為S2=(21，18，20，13)，S3=(13，8，22，5)，S4=(18，15，19，12).

定義7.近似保序模式挖掘：用戶(hù)通過(guò)自定義參數(shù)值，在給定的時(shí)間序列S中找到所有滿(mǎn)足最小支持度閾值的頻繁保序模式.

例4.時(shí)間序列S=(19，16，21，18，20，13，8，22，5，11，18，15，19，12，6，11)，δ=1，γ=2，minsup=4，挖掘出所有的頻繁(δ-γ)保序模式.

在時(shí)間序列S中挖掘得到的頻繁近似保序模式集F={(1，2)，(2，1)，(1，2，3)，(1，3，2)，(2，1，3)，(2，3，1)，(3，1，2)，(3，2，1)(3，2，4，1)，(3，4，1，2)，(4，3，2，1)}.

當(dāng)δ=γ=0時(shí)，近似保序序列模式挖掘轉(zhuǎn)化為精確保序序列模式挖掘，因此本文研究是更具一般性研究.

4 AOPM

對(duì)于近似保序模式挖掘，關(guān)鍵的兩個(gè)步驟是候選模式的生成和(δ-γ)保序模式支持度的計(jì)算.4.1節(jié)介紹了候選模式生成策略；4.2節(jié)介紹了候選模式支持度計(jì)算策略；4.3節(jié)介紹了AOPM算法；4.4節(jié)對(duì)AOPM算法及其對(duì)比算法進(jìn)行了時(shí)空復(fù)雜度分析.

4.1 候選模式生成

4.1.1 枚舉策略

枚舉策略是一一列出所有可能出現(xiàn)的情況的策略，假設(shè)一個(gè)長(zhǎng)度為m(1

例5.長(zhǎng)度為3的頻繁模式集合Fre3={(1，3，2)，(2，1，3)}，采用枚舉策略生成長(zhǎng)度為4的候選模式集C4，結(jié)果如下表2所示.

表2 基于枚舉策略生成候選模式集C4Table 2 Generate candidate pattern set C4 based on enumeration strategy

以模式(1，3，2)為例，生成長(zhǎng)度為4的候選模式有以下4種情形：1)新增加的元素小于原始的3個(gè)元素時(shí)則生成候選模式(2，4，3，1)；2)新增加的元素的數(shù)值只比第一個(gè)大則生成候選模式(1，4，3，2)；3)新增加的元素比最小的兩個(gè)元素?cái)?shù)值都大則生成候選模式(1，4，2，3)；4)新增加的元素大于原始的3個(gè)元素時(shí)則生成候選模式(1，3，2，4).由于每個(gè)模式可以生成4個(gè)候選模式，那么2個(gè)頻繁模式就可以產(chǎn)生出2×4=8個(gè)候選模式.

顯然候選模式數(shù)量越多，挖掘速度越慢.下一小節(jié)中，本文將提出更加高效的模式融合策略減少候選模式的生成.

4.1.2 模式融合策略

定義8.前綴子模式和保序前綴子模式、后綴子模式和保序后綴子模式：給定序列模式P=(p1p2…pm)，除去最后一個(gè)元素pm后剩余的子模式Q=(p1p2…pm-1)就是模式P的前綴子模式，保序前綴子模式就是前綴子模式的保序模式，記做prefixorder(P)；除去第一個(gè)元素p1后剩余的子模式H=(p2p3…pm)就是模式P的后綴子模式，保序后綴子模式就是后綴子模式的模式，記做suffixorder(P).

定義9.模式融合：假設(shè)有兩個(gè)長(zhǎng)度都為m的模式P=(p1p2…pm)和Q=(q1q2…qm)，當(dāng)模式P的后綴子模式的保序模式與模式Q的前綴子模式的保序模式一致時(shí)，即suffixorder(P)=prefixorder(Q)，則P和Q就可以拼接生成長(zhǎng)度為m+1的超模式；這里存在3種情況：

情況1.p1>qm.此時(shí)產(chǎn)生一個(gè)超模式T，其中t1=p1+1，然后將qj(1≤j≤m)與p1進(jìn)行比較，若qj>p1，那么tj+1=qj+1，否則，tj+1=qj.

情況2.p1=qm.此時(shí)產(chǎn)生兩個(gè)超模式T和K，在拼接為模式T=(t1t2…tmtm+1)時(shí)，首先令t1=p1+1，然后將qj(1≤j≤m)與p1進(jìn)行比較，若qj>p1，那么ti+1=qj+1，否則，ti+1=qj；在拼接為模式k=(k1k2…kmkm+1)時(shí)，km+1=qm+1，然后將pi(1≤i≤m)與qm進(jìn)行比較，若pi>qm，那么ki=pi+1，否則，ki=pi.

情況3.p1qm，那么ti=pi+1，否則，ti=pi.

例6.給定保序模式P=(2，3，1)，其分別與模式Q=(3，2，1)和模式R=(3，1，2)進(jìn)行拼接.

首先求出模式P的后綴、模式Q和R的前綴模式分別為：suffix(P)=(3，1)和prefix(Q)=(3，2)，prefix(R)=(3，1).他們的保序模式分別為：suffixorder(P)=(2，1)，prefixorder(Q)=(2，1)，prefixorder(R)=(2，1).因?yàn)閟uffixorder(P)=prefixorder(Q)=(2，1)，且1<2，滿(mǎn)足情況1，故P和Q可拼接為一個(gè)長(zhǎng)度為4的模式T，因?yàn)閜1>q3，所以令t1=p1+1=3，然后將q1、q2和q3別與q3進(jìn)行比較，因?yàn)閝2和q3都不大于p1，q1大于p1，所以(t2t3t4)=(4，2，1)，綜上T=(3，4，2，1).

又因?yàn)閟uffixorder(P)=prefixorder(R)且2=2，滿(mǎn)足情況2，故P和R拼接可生成兩個(gè)長(zhǎng)度為4的模式T和K.在生成T時(shí)，令x1=p1+1，因?yàn)閞3≤p1，所以令x4=r4，因?yàn)閞1>p1，所以x2=r2+1，因?yàn)閞2、r3≤p1，所以x3=r2、x4=r3、最終得到X=(3，4，1，2)；在生成K時(shí)，令k4=r4+1，因?yàn)閝1、q3≤r3，所以k1=q1、k3=q3，因?yàn)閝2>r4所以k2=q2+1，最終可得到K=(2，4，1，3).

例7.本文使用與例5相同的頻繁模式集Fre3，通過(guò)模式融合策略來(lái)生成4長(zhǎng)度候選模C4.

3長(zhǎng)度的頻繁模式F3的第一個(gè)模式是(1，3，2)，(1，3，2)的后綴模式為(3，2)，它的相對(duì)順序是(2，1)，然后開(kāi)始從上到下順序遍歷F3中的模式，當(dāng)找到一個(gè)前綴的相對(duì)順序也為(1，2)的模式時(shí)，就將這兩個(gè)模式進(jìn)行模式拼接，經(jīng)過(guò)一次循環(huán)之后，能夠在模式(1，3，2)的基礎(chǔ)上生成(1，3，2，4)這個(gè)4長(zhǎng)度的候選模式，再次對(duì)F3的第二個(gè)模式(2，1，3)進(jìn)行同樣的操作，不停地循環(huán)上述步驟，直到長(zhǎng)度為3的頻繁模式集合中的最后一個(gè)模式被處理完，這樣就找到了全部的長(zhǎng)度為4的候選模式，拼接結(jié)果如表3所示.

表3 基于模式融合策略生成候選模式集C4Table 3 Candidate pattern set C4 generated based on pattern fusion strategy

通過(guò)對(duì)比表2和表3可以看到，如果采用枚舉策略會(huì)生成8個(gè)長(zhǎng)度為4的候選模式，而當(dāng)采用基于前后綴拼接的模式融合策略生成候選模式時(shí)，只生成了3個(gè)長(zhǎng)度為4的候選模式.因此，模式融合策略可以有效地減少候選模式的數(shù)量，從而提高算法的挖掘效率.

算法1.Generate算法：

輸入：長(zhǎng)度為m的頻繁模式Fm

輸出：下一長(zhǎng)度的候選模式數(shù)組C

1.fori=1 toFm.size do

2. forj=1 toFm.size do

3. q←suffixorder(Fm[i])

4. r←prefixorder(Fm[j])

5. if q=r then

6. if(Fm[i][1]=Fm[j][m])then

7. c1∪c2←Fm[i]?Fm[j]

8.C←c1

9.C←c2

10. else

11. c←Fm[i]?Fm

12.C←c

13. end if

14. end for

15.end for

16.returnC

4.2 支持度計(jì)算

4.2.1 候選序列查找

對(duì)每一個(gè)候選模式，在進(jìn)行(δ-γ)保序匹配之前首先要從頭到尾掃描時(shí)間序列S來(lái)找到它的所有候選序列，下面通過(guò)例8來(lái)具體介紹.

例8.給定S=(19，16，21，18，20，13，8，22，5，11，18，15，19，12，6，11)，在minsup=4，δ=1，γ=2的情況下找到候選模式(4，3，5，1，2)的候選序列.

對(duì)每一個(gè)候選模式，我們通過(guò)從頭到尾掃描數(shù)據(jù)庫(kù)的方法來(lái)找到所有的候選序列，找的第1個(gè)候選序列是(19，16，21，18，20)，第2個(gè)候選序列是(16，21，18，20，13)，以此類(lèi)推，直至到S的結(jié)尾.候選模式(4，3，5，1，2)的全部候選序列結(jié)果集C={(19，16，21，18，20)，(16，21，18，20，13)，(21，18，20，13，8)，(18，20，13，8，22)，(20，13，8，22，5)，(13，8，22，5，11)，(8，22，5，11，18)，(22，5，11，18，15)，(5，11，18，15，19)，(11，18，15，19，12)，(18，15，19，12，6)，(15，19，12，6，11)}.

4.2.2 支持度的計(jì)算

為快速計(jì)算支持度，對(duì)每個(gè)候選模式，將它的候選序列通過(guò)排序算法都轉(zhuǎn)化為保序模式，然后將該候選模式與它的所有候選序列進(jìn)行(δ-γ)保序匹配，如果匹配成功，則該模式的支持度加一.將所有的候選序列匹配完成后，如果該候選模式的支持度大于等于給定的支持度閾值，則該模式就是一個(gè)頻繁的(δ-γ)保序模式，將其存儲(chǔ)到最終的頻繁模式數(shù)組中.如此循環(huán)，直到找到該長(zhǎng)度的所有頻繁(δ-γ)保序模式.

算法2.Match算法：

輸入：候選模式數(shù)組C

輸出：滿(mǎn)足最小支持度閾值的(δ-γ)保序模式

1.fori=1 toC.size do

2. c←C[i]

3. forj=1 toS.size do

4. Scan the time seriesSto generate the candidate sequences of c

5. The candidate c is matched with its candidate sequences to get the supportnumber

6. ifnumber≥minsupthen

7.Fm←c

8. end if

9. end for

10.end for

11.returnFm

4.3 AOPM算法

例9.時(shí)間序列S=(19，16，21，18，20，13，8，22，5，11，18，15，19，12，6，11)，δ=1，γ=2，minsup=4，挖掘出所有的近似保序模式.

長(zhǎng)度為1的模式是一個(gè)點(diǎn)，不代表趨勢(shì)變化，因此從2長(zhǎng)度的模式開(kāi)始挖掘.2長(zhǎng)度的保序模式只有上升(1，2)和下降(2，1)兩種趨勢(shì)，即C2={(1，2)，(2，1)}，分別計(jì)算它們的支持度，它們的支持度都不小于給定的最小支持度，所以2長(zhǎng)度的頻繁模式F2={(1，2)，(2，1)}；然后用這兩個(gè)2長(zhǎng)度的頻繁模式生成3長(zhǎng)度的候選模C3={(1，2，3)，(2，3，1)，(1，3，2)，(3，1，2)，(2，1，3)，(3，2，1)}，分別計(jì)算它們的支持度，得到3長(zhǎng)度的頻繁模式F3={(1，2，3)，(2，3，1)，(1，3，2)，(3，1，2)，(2，1，3)，(3，2，1)}，迭代上述過(guò)程得到4長(zhǎng)度的頻繁模式F4={(3，2，4，1)，(3，4，1，2)，(4，3，2，1)}，F(xiàn)5={}.最終挖掘得到的近似保序模式F={(1，2)，(2，1)，(1，2，3)，(2，3，1)，(1，3，2)，(3，1，2)，(2，1，3)，(3，2，1)，(3，2，4，1)，(3，4，1，2)，(4，3，2，1)}.

算法3.AOPM算法：

輸入：序列數(shù)據(jù)集S，局部約束δ，全局約束γ，最小支持度閾值minsup

輸出：頻繁(δ-γ)保序模式集合F

1.Scan time sequenceS，calculate the support of each pattern in the candidate pattern set {(1，2)，(2，1)} of length 2，and put the frequent pattern intoF2

2.m←2

3.C←Generate(F2)

4.whileC!=null do

5.Fm←Match(C)

6.m←m+1；C←Generate(Fm)

7.end while

8.returnF

4.4 算法時(shí)間和空間復(fù)雜度

AOPM算法與其對(duì)比算法(將會(huì)在下節(jié)中介紹)的時(shí)空復(fù)雜度對(duì)比如表4所示，其中，m，n，N分別表示模式長(zhǎng)度、序列長(zhǎng)度和候選模式個(gè)數(shù).

表4 相關(guān)算法時(shí)空復(fù)雜度比較Table 4 Comparison of time and space complexity of related algorithms

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

5.1節(jié)對(duì)本文的實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)數(shù)據(jù)進(jìn)行了說(shuō)明；5.2節(jié)介紹了本文所使用的對(duì)比算法；5.3節(jié)驗(yàn)證了AOPM算法的完備性和高效性.

5.1 數(shù)據(jù)集

實(shí)驗(yàn)運(yùn)行的環(huán)境為：Intel(R)Core(TM)i7-6560U處理器，主頻2.20GHz，內(nèi)存容量16GB，Windows 10，64位操作系統(tǒng)的計(jì)算機(jī)，程序開(kāi)發(fā)環(huán)境為VS2017.對(duì)比實(shí)驗(yàn)數(shù)據(jù)集分別為黃金、石油、羅素2000指數(shù)和納斯達(dá)克指數(shù)的收盤(pán)價(jià)格.數(shù)據(jù)集的具體描述如表5所示.

表5 實(shí)驗(yàn)數(shù)據(jù)集Table 5 Experimental data sets

5.2 對(duì)比算法

1)segtreeBA：為了驗(yàn)證AOPM算法中(δ-γ)保序匹配算法的高效性，將AOPM算法中(δ-γ)保序匹配算法替換為segtreeBA算法來(lái)進(jìn)行對(duì)比.segtreeBA算法是文獻(xiàn)” New algorithms for δγ-order preserving matching ”中使用的(δ-γ)保序匹配算法，該算法建立了一個(gè)樹(shù)形結(jié)構(gòu)即segment tree，并給segment tree建立了3個(gè)標(biāo)準(zhǔn)操作函數(shù)分別為：buildSegTree()函數(shù)、updateSegTree()函數(shù)和querySegTree()函數(shù).

2)enum：為了驗(yàn)證AOPM算法中候選模式生成策略的高效性，將其與enum算法進(jìn)行對(duì)比，enum算法使用了枚舉的候選模式生成策略.

3)segtreeBA-enum：segtreeBA-enum采用了segtreeBA算法的模式匹配策略和枚舉的候選模式生成策略來(lái)與AOPM算法進(jìn)行整體運(yùn)行效率上的對(duì)比.

5.3 挖掘?qū)嵗?/h3>

5.3.1 近似挖掘

本文在δ=2，γ=4的條件下來(lái)進(jìn)行近似挖掘，minsup則根據(jù)數(shù)據(jù)集的長(zhǎng)度不同而采取不同的值.實(shí)驗(yàn)結(jié)果如圖2和圖3所示.

圖2 SDB1-SDB4數(shù)據(jù)集中產(chǎn)生的候選模式數(shù)量對(duì)比Fig.2 Comparison of the number of candidate patterns generated in the SDB1-SDB4 data sets

圖3 SDB1-SDB4數(shù)據(jù)集中4種算法運(yùn)行時(shí)間對(duì)比Fig.3 Comparison of the running time of the four algorithms in the SDB1-SDB4 data sets

通過(guò)實(shí)驗(yàn)，可以得出以下結(jié)論：

1)因?yàn)檫@4種算法在每個(gè)數(shù)據(jù)集上都使用了相同的挖掘條件，所以這4種算法在SDB1-SDB4數(shù)據(jù)集上都挖掘出了相同數(shù)量的頻繁保序模式.

2)由圖2的挖掘結(jié)果可知：AOPM算法、segtreeBA算法生成了相同數(shù)量的候選模式，因?yàn)樗鼈兌疾扇×四Ｊ饺诤系暮蜻x模式生成策略；enum算法、segtreeBA-enum算法也生成了相同數(shù)量的候選模式，它們都采取了枚舉的候選模式生成策略.因?yàn)槟Ｊ饺诤喜呗圆粫?huì)生成無(wú)意義的候選模式，即會(huì)篩選掉一些不可能是頻繁模式的候選模式，所以使用模式融合策略的算法要比使用枚舉策略的算法生成的候選模式少.

3)AOPM算法與segtreeBA算法相比，采取了相同的候選模式生成策略但采取了不同的模式匹配策略.與AOPM算法相比，segtreeBA算法每進(jìn)行一次(δ-γ)保序匹配都要使用querySegTree()和updateSegTree()函數(shù)來(lái)對(duì)segment tree進(jìn)行更改恢復(fù)操作，這就增加了(δ-γ)保序匹配時(shí)的時(shí)間復(fù)雜度，而AOPM算法則無(wú)需更改原時(shí)間序列.由圖3可知，在SDB1～SDB4數(shù)據(jù)集上segtreeBA算法的運(yùn)行時(shí)間要比AOPM算法的運(yùn)行時(shí)間長(zhǎng).

4)AOPM算法與enum算法相比，采取了相同的模式匹配策略而采取了不同的候選模式生成策略.enum算法使用了枚舉的候選模式生成策略，生成候選模式的時(shí)間復(fù)雜度為O(mN)，隨著挖掘的進(jìn)行候選模式m的長(zhǎng)度會(huì)越來(lái)越大，所以與AOPM算法相比，enum算法會(huì)生成更多的候選模式進(jìn)而增加了時(shí)間復(fù)雜度.由圖3可知，enum算法的運(yùn)行時(shí)間要比AOPM算法的運(yùn)行時(shí)間長(zhǎng).

5)segtree-enum算法無(wú)論是模式匹配還是候選模式生成都采取了與AOPM算法不同的策略，所以segtree-enum算法的運(yùn)行時(shí)間相當(dāng)長(zhǎng)，在圖3的4個(gè)數(shù)據(jù)集上segtreeBA-enum算法所需的運(yùn)行時(shí)間都是AOPM算法的幾倍乃至十幾倍，由此可知AOPM算法所使用的模式匹配策略和候選模式生成策略配合使用是非常高效的.綜上所述可以得出：AOPM算法是一個(gè)完備性和高效性的算法.

5.3.2 精確挖掘

本文在在δ=0，γ=0的條件下來(lái)進(jìn)行精確挖掘，minsup根據(jù)數(shù)據(jù)集的長(zhǎng)度不同而采取不同的值.實(shí)驗(yàn)結(jié)果如圖4和圖5所示.

圖4 SDB1-SDB4數(shù)據(jù)集中產(chǎn)生的候選模式數(shù)量對(duì)比Fig.4 Comparison of the number of candidate patterns generated in the SDB1-SDB4 data sets

圖5 SDB1-SDB4數(shù)據(jù)集中4種算法運(yùn)行時(shí)間對(duì)比Fig.5 Comparison of the running time of the four algorithms in the SDB1-SDB4 data sets

在相同的挖掘條件下，4種挖掘算法挖掘出了相同數(shù)量的頻繁保序模式.由圖4可知，當(dāng)挖掘的頻繁模式個(gè)數(shù)相同時(shí)，AOPM算法和segtreeBA算法生成了相同數(shù)量的候選模式，因?yàn)樗鼈兌疾扇×四Ｊ饺诤系暮蜻x模式生成策略；enum算法和segtreeBA-enum算法也生成了相同數(shù)量的候選模式，它們都采取了枚舉的候選模式生成策略.在運(yùn)行速度方面，由圖5可知，與近似保序挖掘一樣，因?yàn)锳OPM算法所用策略使得挖掘過(guò)程更加簡(jiǎn)便，所以要比其它對(duì)比算法運(yùn)行速度快，從而驗(yàn)證了AOPM算法在精確挖掘條件下也是一個(gè)挖掘效率較高的保序模式挖掘算法.

6 結(jié) 論

為了在時(shí)間序列中挖掘有價(jià)值的信息，本文提出了近似保序序列模式挖掘，并提出了近似保序序列模式挖掘算法：AOPM算法.該算法能夠在時(shí)間序列中挖掘近似程度不同的保序模式，更好地幫助人們進(jìn)行分析和預(yù)測(cè).在候選模式生成方面，AOPM算法使用了模式融合策略.該策略在不遺漏任何有效解的情況下，顯著減少了候選模式的數(shù)量.在計(jì)算模式支持度時(shí)，AOPM算法首選獲取候選模式的全部候選序列，然后在進(jìn)行模式匹配.但AOPM算法仍需重復(fù)掃描數(shù)據(jù)庫(kù)來(lái)計(jì)算模式支持度，后期的研究可以著重于如何避免重復(fù)掃描數(shù)據(jù)庫(kù)來(lái)提高挖掘效率.本文通過(guò)在真實(shí)時(shí)間序列數(shù)據(jù)集上的進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明AOPM算法是一個(gè)完備性和高效性的保序模式挖掘算法.