一種保序序列快速挖掘算法：RSMM

趙曉倩，武優(yōu)西，王月華，李 艷

(1.河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院 天津 300401； 2.河北工業(yè)大學(xué) 經(jīng)濟(jì)管理學(xué)院 天津 300401)

0 引言

在如今的大數(shù)據(jù)時(shí)代，分析隱藏在數(shù)據(jù)背后的信息、規(guī)律成為一個(gè)重要的挑戰(zhàn)，眾多學(xué)者從多角度對(duì)大數(shù)據(jù)進(jìn)行研究，產(chǎn)生了一系列的分析方法，其中最為經(jīng)典的方法就是數(shù)據(jù)挖掘[1]。序列模式挖掘[2-3]作為數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)重要課題，主要目的是從序列數(shù)據(jù)集中挖掘出用戶感興趣的子序列，通過分析潛在的模式幫助人們理解數(shù)據(jù)并進(jìn)行決策。目前已經(jīng)應(yīng)用到多個(gè)領(lǐng)域，例如生物醫(yī)學(xué)[4]、疾病檢測(cè)[5]、物聯(lián)網(wǎng)網(wǎng)絡(luò)安全防范[6]和網(wǎng)絡(luò)點(diǎn)擊流分析[7-8]等。為了解決不同的問題，序列模式挖掘衍生出多種挖掘方法：為避免頻繁但存在缺失項(xiàng)的模式丟失，Dong等[9]提出了負(fù)序列模式挖掘；為了更加靈活地挖掘滿足特定要求的模式，Wang等[10]提出基于周期約束的序列模式挖掘方法；為了避免參數(shù)設(shè)置不合理，Wu等[11]提出了自適應(yīng)間隙的序列模式挖掘。

然而現(xiàn)有的序列模式挖掘方法大多針對(duì)字符序列，由于時(shí)間序列具有高維性和連續(xù)性的特點(diǎn)[12-13]，很難直接應(yīng)用到時(shí)間序列分析中，因此，研究人員提出了新的研究方法。比如，在最初的研究中，通常會(huì)把原始的時(shí)間序列轉(zhuǎn)化為其他域的數(shù)據(jù)來(lái)進(jìn)行降維。最常用的方法有分段化表示法[14]、符號(hào)化表示法[15]等，但這些方法需要人為設(shè)定參數(shù)，過程中容易丟失重要的信息，并在一定程度上破壞了時(shí)間序列的連續(xù)性。同時(shí)，對(duì)于時(shí)間序列數(shù)據(jù)，如果過度關(guān)注元素?cái)?shù)據(jù)的大小，很容易忽視序列的形態(tài)變化，難以發(fā)現(xiàn)有價(jià)值的信息。Wu等[16]提出了保序序列模式挖掘(OPP-Miner)算法挖掘序列中頻繁出現(xiàn)的趨勢(shì)變化。該方法使用模式的相對(duì)順序表示其形狀特征，稱為保序模式，采用模式匹配[17]的方法計(jì)算支持度，需要多遍掃描原序列，從而在計(jì)算效率方面有待進(jìn)一步提高，尋求高效的挖掘算法解決時(shí)間序列問題成為當(dāng)前的挑戰(zhàn)之一。

1 相關(guān)工作

序列模式挖掘是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)重要的分支，有廣闊的應(yīng)用前景。傳統(tǒng)的序列模式挖掘問題是從序列數(shù)據(jù)庫(kù)中找出頻繁出現(xiàn)的模式[18]，為了應(yīng)對(duì)場(chǎng)景的需要，研究人員采取了在此基礎(chǔ)上增加條件的方法，如Wu等[19]提出了高平均效用的序列模式挖掘；Wang等[20]提出了對(duì)比序列模式挖掘來(lái)提高分類的精度；武優(yōu)西等[21]提出基于周期性一般間隙約束的序列模式挖掘方法。

盡管上述研究取得了良好的挖掘效果，但這些研究主要是針對(duì)符號(hào)化的序列或字符序列進(jìn)行挖掘。上述方法難以應(yīng)用到有序的連續(xù)數(shù)值構(gòu)成的時(shí)間序列上進(jìn)行挖掘，需要通過一系列轉(zhuǎn)換，將原始的數(shù)值型數(shù)據(jù)轉(zhuǎn)換成為其他域的數(shù)據(jù)，然后再進(jìn)行挖掘。常見的方法有基于分段的表示和基于符號(hào)的表示，如Lin等[22]采用PAA方法將時(shí)間序列進(jìn)行分段并每段求平均值，然后再挖掘其中的頻繁模式；Tan等[23]根據(jù)數(shù)據(jù)波動(dòng)將數(shù)字時(shí)間序列轉(zhuǎn)換為字符型序列，并運(yùn)用在具有弱通配符間隙的模式挖掘中。

雖然上述方法可以處理時(shí)間序列數(shù)據(jù)，但忽略了序列的原始特征，不易發(fā)現(xiàn)數(shù)據(jù)的變化趨勢(shì)。為此，提出了基于次序關(guān)系的表示方法，如Kim等[24]提出KMP算法，尋找序列中出現(xiàn)趨勢(shì)相同的子序列。在一些允許一定數(shù)據(jù)噪聲存在的場(chǎng)景下，保序模式的近似匹配也相繼被提出，如文獻(xiàn)[25]提出的基于(δ,γ)距離的相似度度量方法，采用局部-整體約束，提高了匹配的精確度。隨著研究的深入，保序模式匹配已經(jīng)不能滿足需要，Wu等[16]提出的OPP-Miner采用模式匹配的方式計(jì)算支持度。本文提出的RSMM利用子模式的結(jié)果得到超模式的支持度，避免了多次讀取原序列，提高了挖掘效率。

2 相關(guān)定義

定義1(時(shí)間序列) 時(shí)間序列是指將同一統(tǒng)計(jì)指標(biāo)的數(shù)值按照其發(fā)生的時(shí)間先后順序排列而成的數(shù)列，可以表示為T=(t1,…,ti,…,tn)(1≤i≤n)，其中n表示的是序列T的長(zhǎng)度。

定義2(秩) 元素pj在長(zhǎng)度為m的模式P=(p1,…,pj,…pm)(1≤j≤m)中的秩記作rank(pj)，表示的是pj在該模式中的相對(duì)大小。

定義3(保序模式) 由元素的相對(duì)順序表示的模式稱為保序模式，記作rn(P)=(rank(p1),rank(p2),…,rank(pm))，模式中元素的個(gè)數(shù)即為模式的長(zhǎng)度。

例1給定溫度模式(24.2, 30.5, 27.1, 32.2)，由于元素24.2是子序列中最小的，因此rank(24.2)=1。同理可知，rank(30.5)=3。進(jìn)而，其保序模式為(1,3,2,4)，其對(duì)應(yīng)的趨勢(shì)如圖1所示。

圖1 模式(1,3,2,4)Figure 1 Pattern (1,3,2,4)

定義4(出現(xiàn)和支持度) 給定模式P=(p1,p2,…,pm)，時(shí)間序列T=(t1,t2,…,tn)，若存在子序列T′=(ti,ti+1,…,ti+m-1)，1≤i，(i+m-1)≤n且rank(T′)=rank(P)，則T′是模式P在序列T中的一次出現(xiàn)，記作〈ti+m-1〉。模式P在序列T中出現(xiàn)的總次數(shù)就是模式P在序列T中的支持度，記作sup(P)。

定義5(頻繁保序模式) 給定最小支持度閾值minsup，如果模式P在序列T中的支持度不小于給定的最小值支持度閾值minsup，則模式P稱為頻繁保序模式。

定義6(保序模式挖掘) 給定時(shí)間序列T=(t1,t2,…,tn)，最小支持度閾值minsup，挖掘出滿足最小支持度閾值的所有頻繁保序模式稱為保序模式挖掘。

3 保序模式挖掘算法

3.1 候選模式生成

傳統(tǒng)的候選模式生成多采用枚舉法，但該方法會(huì)產(chǎn)生大量冗余候選，為減少候選模式生成，采用模式融合方式。下面進(jìn)行詳細(xì)說明。

P和Q是長(zhǎng)度為m的子模式，R和H是長(zhǎng)度為m+1的超模式，LX是模式X在序列T中的匹配集合，其中元素lxi是X在序列中的一次出現(xiàn)。

定義7(前綴、后綴保序模式、子模式和超模式) 給定模式P，子序列E=rn(p1,p2,…,pm-1)稱為模式P的前綴保序模式，記作E=prefix(P)；子序列K=rn(p2,p3,…,pm)稱為模式P的后綴保序模式，記作K=suffix(P)，其中：E和K是P的子模式；P是E和K的超模式。

定義8(模式融合) 兩個(gè)m長(zhǎng)度的保序模式P、Q，若rn(suffix(P))=rn(prefix(Q))，那么模式P和Q可以生成(m+1)長(zhǎng)度的超模式。這里存在兩種情況。

情況1若p1qm，那么模式P和Q可以生成一個(gè)(m+1)長(zhǎng)度的模式R，即R=P⊕Q。

①p1

②p1>qm：其中r1=p1+1，若qi≤p1，則ri+1=qi；若qi>p1，則ri+1=qi+1，1≤i≤m。

情況2若p1=qm，那么模式P和Q可以生成兩個(gè)(m+1)長(zhǎng)度的模式R、H，即R，H=P⊕Q。

其中：r1=hm+1=p1，rm+1=h1=p1+1，若qip1，則ri+1=qi+1，1≤i≤m-1。

例2給定3長(zhǎng)度的模式P=(2,1,3)，Q=(1,3,2)，可以生成4長(zhǎng)度的候選模式。表1給出了采用枚舉法和模式融合生成的候選模式集。若采用枚舉法，則每個(gè)模式都存在4種情況，以(2,1,3)為例，將1、2、3、4分別插在尾部，同時(shí)還要保持模式(2,1,3)的相對(duì)順序，得到的候選模式如表1所示。模式融合以(2,1,3)與(1,3,2)為例，因?yàn)閜1=q3=2，滿足情況2，進(jìn)而可以產(chǎn)生2個(gè)候選模式(3,1,4,2)、(2,1,4,3)。從表1可以看出，采用模式融合可以減少候選模式數(shù)量。

表1 候選模式集Table 1 Candidate pattern sets

算法1模式融合(pattern fusion，PF)

輸入： 子模式P,Q

輸出： 超模式R,H

1．E←rn(prefix(P))

2．K←rn(suffix(Q))

3． IFK==E

4． IFP[0]==Q[m-1]

5．R∪H←Fm[i]⊕Fm[j]

6． ELSE

7．R←Fm[i]⊕Fm[j]

8． END IF

9． END IF

10． RETURNR,H

3.2 支持度計(jì)算

依據(jù)3.1可以看出，P⊕Q生成超模式有兩種情況，下面分別介紹。

P和Q為m長(zhǎng)度的模式，P為前綴保序模式，其對(duì)應(yīng)的匹配集合為L(zhǎng)P，Q為后綴保序模式，其對(duì)應(yīng)的匹配集合為L(zhǎng)Q?！磍pi〉為P的一次出現(xiàn)，即lpi∈LP；〈lqj〉為Q的一次出現(xiàn)，即lqj∈LQ。

方法1R=P⊕Q：當(dāng)且僅當(dāng)lqj=lpi+1，〈lqj〉為R的一次出現(xiàn)，即lqj∈LR。

方法2R、H=P⊕Q：當(dāng)且僅當(dāng)lqj=lpi+1時(shí)，〈lqj〉可能為R或H的一次出現(xiàn)，需要判斷序列T中ta和tb的大小(a=lqj-m，b=lqj)。若tatb，〈lqj〉為H的一次出現(xiàn)，即lqj∈LH；若ta=tb，〈lqj〉既不是R又不是H的出現(xiàn)。

最終集合LR、LH中元素的個(gè)數(shù)為超模式R、H的支持度，即sup(R)=|LR|，sup(H)=|LH|。

例3圖2表示的是某地16天內(nèi)的平均溫度變化情況，2長(zhǎng)度模式P=(1,2)和Q=(2,1)的匹配集合分別為L(zhǎng)P={2,4,8,10,12,14,16}和LQ={3,5,6,7,9,11,13,15}。

圖2 某地16天平均溫度變化情況圖Figure 2 The average temperature in 16 days

P⊕Q生成兩個(gè)超模式R=(1,3,2)和H=(2,3,1)，P和Q分別為前綴保序模式和后綴保序模式。由于2∈LP且(2+1=3)∈LQ，根據(jù)方法2知，〈3〉可能為R或H的一次出現(xiàn)，可得a=3-2=1，b=3，由于t1

算法2支持度計(jì)算算法(support calculation，SC)

輸入： 模式P和Q分別作為前綴模式和后綴模式的匹配集合LP，LQ

輸出： 超模式的支持度

1．LR={};LH={}

2． IFP[0]==Q[m-1]

3． 根據(jù)方法2得到匹配集合LR和LH

4． ELSE

5． 根據(jù)方法1得到匹配集合LR

6． END IF

7． RETURNLR.size,LH.size

3.3 保序快速挖掘算法

本節(jié)提出了一種保序快速挖掘算法，即讀取子模式匹配結(jié)果挖掘(read sub-pattern matching for mining，RSMM)算法，具體步驟如下所示。

步驟1 掃描序列T，分別記錄模式(1,2)，(2,1)的匹配集合，計(jì)算模式的支持度，若為頻繁模式，將該模式加入頻繁集F2中；

步驟2 根據(jù)PF由頻繁集Fm生成(m+1)長(zhǎng)度的候選模式；

步驟3 利用SC計(jì)算候選模式的支持度，判斷是否是頻繁模式，若為頻繁模式，將該模式加入頻繁集Fm+1中；

步驟4 重復(fù)步驟2、3直到?jīng)]有(m+1)長(zhǎng)度的候選模式生成；

步驟5 依據(jù)Fm+1重復(fù)步驟2～4，直到?jīng)]有候選模式生成。最終，集合F中的模式即為頻繁保序模式。

例4對(duì)于例3采用該算法挖掘頻繁保序模式，首先掃描時(shí)間序列，得到模式P1=(1,2)和P2=(2,1)的匹配集合LP1={2,4,8,10,12,14,16}，LP2={3,5,6,7,9,11,13,15}，因此sup(P1)=7，sup(P2)=8，由于minsup=3，可知F2={(1,2),(2,1)}。依據(jù)模式融合，(1,2)⊕(2,1)可以生成R=(1,3,2)和H=(2,3,1)，根據(jù)計(jì)算支持度的方法可知sup(R)=5，sup(H)=1。得到3長(zhǎng)度的頻繁模式集F3={(1,3,2),(2,1,3),(3,1,2)}。以此類推，依據(jù)F3可以計(jì)算出4長(zhǎng)度的頻繁模式。最終，得到頻繁模式集F={(1,2),(2,1),(1,3,2),(2,1,3),(3,1,2),(1,3,2,4)}。

采用RSMM算法只在計(jì)算2長(zhǎng)度模式時(shí)遍歷時(shí)間序列，相比OPP-Miner減少了遍歷序列的次數(shù)，提高了挖掘的效率。

算法3RSMM

輸入： 序列數(shù)據(jù)集T,最小支持度閾值minsup

輸出： 頻繁模式集合F

1． 掃描序列T,將模式(1,2)、(2,1)的匹配結(jié)果分別放入集合LP、LQ,計(jì)算模式的支持度,將頻繁模式放入F2

2．m←2

3． WHILEFm!=null DO

4． FOR eachPinFmDO

5． FOR eachQinFmDO

6． 根據(jù)PF生成超模式

7． 采用SC計(jì)算超模式的支持度sup

8． IFsup≥minsupTHEN

9. 將模式加入到頻繁模式集Fm+1中

10. END IF

11. END FOR

12. END FOR

13.m←m+1;

14. END WHILE

15. RETURNF

定理1采用RSMM計(jì)算模式支持度的方法是完備的。

證明(反證法)存在子序列T′=(ti,ti+1,…,ti+m)，若R=P⊕Q且rn(T′)=R，假設(shè)(i+m)?LR。由于rn(suffix(T′))=P，rn(prefix(T′))=Q，則(i+m-1)∈LP，(i+m)∈LQ，依據(jù)定理1可得(i+m)∈LR，與假設(shè)矛盾。因此，該算法計(jì)算模式支持度得到的結(jié)果是完備的。

定理2RSMM滿足Apriori性質(zhì)。

證明給定序列T，若R=P⊕Q且R為頻繁模式，即sup(R)≥minsup，依據(jù)定理1可知|LP|≥|LR|，即sup(P)≥sup(R)，所以sup(P)≥minsup，同理，sup(Q)≥minsup。因此，該算法中頻繁超模式的非空子模式也是頻繁模式，即該算法滿足Apriori性質(zhì)。

定理3保序快速挖掘算法的空間復(fù)雜度為O(L×(m+n))，時(shí)間復(fù)雜度為O(L×(L+n))。其中m、n、L分別為最長(zhǎng)模式長(zhǎng)度、序列長(zhǎng)度和生成超模式的個(gè)數(shù)。

證明該算法的空間復(fù)雜度由兩部分組成：存儲(chǔ)頻繁模式空間和模式末位索引空間。由于頻繁模式的個(gè)數(shù)為L(zhǎng)，因此存儲(chǔ)頻繁模式空間復(fù)雜度為O(L×m)；對(duì)于一個(gè)模式，產(chǎn)生的匹配集合空間為O(n)，L個(gè)頻繁模式，模式匹配集合空間復(fù)雜度為O(L×n)。因此，該算法空間復(fù)雜度為O(L×(m+n))。在生成超模式時(shí)所需要的時(shí)間復(fù)雜度為O(L×L)，在計(jì)算支持度階段所需要的時(shí)間復(fù)雜度為O(n×L)。因此，該算法的時(shí)間復(fù)雜度為O(L×(L+n))。

4 實(shí)驗(yàn)部分

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

本文采用真實(shí)數(shù)據(jù)集作為測(cè)試序列，股票和石油數(shù)據(jù)集來(lái)自https:∥www.yahoo.com/；天氣數(shù)據(jù)集來(lái)自https:∥archive.ics.uci.edu/ml/datasets.php。其中T3～T5是截取T6的部分?jǐn)?shù)據(jù)。具體數(shù)據(jù)集描述如表2所示。

表2 時(shí)間序列數(shù)據(jù)集Table 2 Time series data sets

實(shí)驗(yàn)運(yùn)行的環(huán)境為Inter(R)Core(TM)i5-8265U處理器，主頻1.60 GHz，內(nèi)存8 GB，Windows 10，64位操作系統(tǒng)的計(jì)算機(jī)，程序的開發(fā)環(huán)境為Visual Studio 2019。

4.2 基線方法

1) OPP-Miner：為了分析RSMM的效率，采用OPP-Miner作為對(duì)比算法；

2) RSMM-e：為了分析模式融合在生成超模式時(shí)的效果，提出了采用枚舉策略的RSMM-e。

4.3 RSMM挖掘效果

為了驗(yàn)證RSMM的效率，在T1、T2和T6上進(jìn)行實(shí)驗(yàn)，設(shè)置minsup=12。挖掘出的頻繁模式數(shù)量如表3所示。

表3 頻繁模式數(shù)量Table 3 Number of frequent patterns

從表3可以看出，在不同的數(shù)據(jù)集上，三種算法挖掘出的頻繁模式個(gè)數(shù)是相同的，如在T1中，三種算法均挖掘出了160個(gè)頻繁模式；在T6中，三種算法均挖掘出1 023個(gè)頻繁模式。

接著，從運(yùn)行時(shí)間和生成候選模式數(shù)量分析RSMM的挖掘效果。結(jié)果如表4～5所示。

表4 運(yùn)行時(shí)間Table 4 Running time 單位：ms

表5 候選模式數(shù)量Table 5 The number of candidate patterns

從表4～5可以得到如下結(jié)論。

1) 采用RSMM可以提高挖掘的性能。在T6上，OPP-Miner需要1 594 ms而RSMM需要1 036 ms，運(yùn)行時(shí)間縮短了558 ms。

2) 采用模式融合可以提高挖掘的性能。在T2上，RSMM-e生成5 738個(gè)候選模式，而RSMM采用模式融合生成了2 371個(gè)候選模式，減少了冗余模式的生成，從而將運(yùn)行時(shí)間從18 156 ms減少到500 ms。

4.4 數(shù)據(jù)集長(zhǎng)度對(duì)算法性能的影響

為了驗(yàn)證數(shù)據(jù)集長(zhǎng)度對(duì)挖掘效果的影響，我們?cè)诓煌L(zhǎng)度的數(shù)據(jù)集T3～T6上進(jìn)行實(shí)驗(yàn)，從運(yùn)行時(shí)間上分析算法的性能。minsup=100，實(shí)驗(yàn)結(jié)果如表6所示。

無(wú)論在長(zhǎng)數(shù)據(jù)集還是短數(shù)據(jù)集上，RSMM的挖掘效果都是最好的，而對(duì)于長(zhǎng)數(shù)據(jù)集，RSMM的挖掘效果更明顯。從表6可以看出，T3上，OPP-Miner需要16 ms，而RSMM需要15 ms；T6上，OPP-Miner需要250 ms，而RSMM需要125 ms，時(shí)間縮短了50%。可以看出，RSMM對(duì)長(zhǎng)數(shù)據(jù)集有更優(yōu)的效果。這是由于挖掘長(zhǎng)數(shù)據(jù)集時(shí)，會(huì)產(chǎn)生更多的候選模式，OPP-Miner會(huì)多次掃描時(shí)間序列，浪費(fèi)了不必要的時(shí)間，而采用RSMM可以避免多次掃描序列。因此，對(duì)于數(shù)據(jù)集效果更明顯。

表6 運(yùn)行時(shí)間Table 6 Running time 單位：ms

5 結(jié)論

我們提出的RSMM算法在計(jì)算支持度時(shí)，通過子模式匹配結(jié)果計(jì)算超模式的支持度，避免了多次讀取原序列。在時(shí)間序列數(shù)據(jù)集上的挖掘?qū)嶒?yàn)表明RSMM具有高效性，可以在更短的時(shí)間內(nèi)挖掘到所有頻繁出現(xiàn)的趨勢(shì)，與OPP-Miner相比，在運(yùn)行時(shí)間上平均減少了26%。并且對(duì)于長(zhǎng)序列，RSMM的挖掘效果更明顯，運(yùn)行時(shí)間減少了50%。