曾圣超， 張智恒， 閔 帆， 張紫茵

(1. 西南石油大學(xué) 計算機(jī)科學(xué)學(xué)院 四川 成都 610500； 2. 四川旅游學(xué)院 信息與工程學(xué)院 四川 成都 610100)

0 引言

作為決策粗糙集[1]的核心思想之一，三支決策理論近年來在各方面[2-11]均取得了長足的進(jìn)展。各種先進(jìn)的理論如形式三支粒計算、三支概念分析、三支認(rèn)知計算、三支模糊集方法、三支決策空間[2-7]等均受到三支決策的啟發(fā)。此外，在三支決策基礎(chǔ)上又實(shí)踐了多種機(jī)器學(xué)習(xí)技術(shù)，如三支推薦系統(tǒng)、三支主動學(xué)習(xí)、三支聚類[8]、三支鄰域覆蓋約簡[9]、三支垃圾郵件過濾[10]、項(xiàng)集三支增量挖掘[11]等。

增量算法利用已有的知識和增量數(shù)據(jù)得到最新的知識[11]，能夠極好地適應(yīng)大數(shù)據(jù)場景。對于模式發(fā)現(xiàn)問題，人們針對購物數(shù)據(jù)提出了頻繁項(xiàng)集的增量算法如三支決策更新模式方法(three-way decision update pattern，TDUP)[11]和快速更新算法(fast update，F(xiàn)UP)[12]。對于各種序列數(shù)據(jù)，如股價、文本、基因，設(shè)計了頻繁閉合序列挖掘算法(incremental bide，BideInc)[13]。對于最一般的時序交互數(shù)據(jù)[14]，如出行軌跡、購物清單、觀影評分[15]等，大量的增量算法如增量序列提取(incremental sequence extraction，ISE)[16]和增量更新序列(incrementally updating sequences，IUS)[17]被提出來獲得頻繁的事件/行為序列。多元時序數(shù)據(jù)(multivariant time series,MTS)如空氣質(zhì)量、工業(yè)設(shè)備、人體健康數(shù)據(jù)上的頻繁模式[18]挖掘同樣受到了廣泛關(guān)注[19-20]。然而，MTS上的頻繁模式增量挖掘算法還有待豐富。

本文提出了MTS數(shù)據(jù)上狀態(tài)轉(zhuǎn)移模式(state transition pattern，STAP)[20]的三支增量挖掘算法(three-way incremental updating method of state transition pattern，3IU-STAP)。該算法由4個階段組成。第一，增量更新頻繁狀態(tài)。它們是構(gòu)成STAP的基本分量元素，其集合可被視為構(gòu)成STAP的字母表。第二，構(gòu)造候選STAP以及增補(bǔ)數(shù)據(jù)db′。任意候選STAP均是由兩個更短的頻繁STAP鏈接而來。從原始數(shù)據(jù)DB截取的尾部長度是由候選序列的長度和通配符區(qū)間的上界來確定的。對于所有長度相同的候選STAP，所截取的尾部是一致的。因此，在最壞情況下，構(gòu)建增補(bǔ)數(shù)據(jù)的次數(shù)為MTS數(shù)據(jù)的長度；而在平均情況下，其構(gòu)建次數(shù)與最長頻繁STAP的長度一致。第三，通過判斷候選STAP在DB和db′上頻繁或不頻繁的表現(xiàn)，將所有候選模式劃分進(jìn)3個互不相交的集合中，即正域(positive region，POS)、負(fù)域(negative region，NEG)和邊界域(boundary region，BND)。當(dāng)一個候選STAP在DB和db′上均頻繁，則它一定是頻繁的，令其屬于正域。當(dāng)一個候選STAP在DB和db′上均不頻繁，則它一定是不頻繁的，令其屬于負(fù)域。否則，將其劃入邊界域，通過重新掃描DB或db′獲得準(zhǔn)確的支持度，并判斷該STAP是否頻繁。第四，算法依靠所獲得的頻繁模式來構(gòu)造更長的候選模式，直到生成候選模式集合為空時終止。

對環(huán)境工程、工業(yè)設(shè)備、石油工程等領(lǐng)域的4個真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，結(jié)果表明，增量算法與批量算法相比，時間性能提高了5.3～649倍，且增量越小，效率越高。

1 基礎(chǔ)知識

本章首先介紹MTS的數(shù)據(jù)模型。在此基礎(chǔ)上描述狀態(tài)、STAP及其支持度。

1.1 數(shù)據(jù)模型

在模式挖掘過程中，人們通常關(guān)注符號型的MTS數(shù)據(jù)。對于傳感器網(wǎng)絡(luò)采集的數(shù)值型數(shù)據(jù)，需要進(jìn)行離散化。

1.2 狀態(tài)轉(zhuǎn)移模式

定義3[20]給定兩個狀態(tài)轉(zhuǎn)移模式P=s1Δs2…si，P′=s′1Δs′2…s′j，i,j≥1，它的增長操作是P?P′=s1Δs2…siΔs1′Δs2′…sj′。

其中|EP|表示模式P在DB上出現(xiàn)的次數(shù)。因此，P在DB上的支持度是

sup(P,DB)=(|EP|/|E|)∈[0,1]。

當(dāng)時間序列DB給定時，可以簡寫成sup(P)。由此可給出頻繁STAP的定義。

定義7[20]給定閾值ρd，頻繁STAP的集合為

F={?P∈F|sup(P)≥ρd}。

2 本文算法

本節(jié)首先提出STAP的增量挖掘問題并分析其時間復(fù)雜度。其次，提出了解決該問題的三支增量模型。然后，基于模型提出了3IU-STAP算法設(shè)計與實(shí)現(xiàn)。

2.1 問題描述

問題： 增量挖掘頻繁STAP。

輸出：FDB∪db={P|sup(s∈P,DB∪db)≥ρw,sup(P,DB∪db)≥ρd}。FDB∪db是在更新后的數(shù)據(jù)集上所有滿足閾值ρw和ρd的頻繁STAP的集合。

雖然問題的時間復(fù)雜度是指數(shù)級的，但可通過引理1描述的向下封閉性質(zhì)來大大減少實(shí)際運(yùn)行時間。

引理1假設(shè)ρd是STAP的序列閾值。如果P?P′，則sup(P′)≤sup(P)。

2.2 3IU-STAP算法

2.2.1三支增量模型 對于任意給定的候選模式P(由定義3可得)以及支持度，根據(jù)它在原始數(shù)據(jù)DB和增補(bǔ)數(shù)據(jù)db′上是否頻繁，提出了判斷候選模式是否頻繁的三支劃分模型，如式(1)所示，

(1)

圖1給出了針對這3個區(qū)域的處理技術(shù)。正域中的候選模式P一定是頻繁的，直接接受并存儲。負(fù)域中的候選模式P一定是不頻繁的，直接拒絕并拋棄。邊界域中的模式P需要延遲決策，即掃描數(shù)據(jù)集計算最新的支持度。當(dāng)一個候選STAP在DB上頻繁，而在db′上不頻繁，即sup(P,DB)≥ρd且sup(P,db′)<ρd，掃描db′；當(dāng)該模式在DB上不頻繁，而在db′上頻繁，即sup(P,DB)<ρd且sup(P,db′)≥ρd，掃描DB。

最后，基于式(1)與圖1所示模型導(dǎo)出引理2和引理3，以有效降低算法對數(shù)據(jù)集的掃描。

圖1 STAP增量挖掘三分而治示意圖Figure 1 Tri-partition and actions

圖2 構(gòu)造增補(bǔ)數(shù)據(jù)Figure 2 Construct supplementary data

引理2若P是存在于正域中的候選模式，則模式P在DB∪db上頻繁。

證明

(2)

由于|EDB|>0且|Edb|>0,則有

(3)

(4)

不等式同號可相加，由式(3)+式(4)得

(5)

則可得到

因此P在DB∪db上頻繁。

引理3若P是存在于負(fù)域中的候選模式，則模式P在DB∪db上不頻繁。

證明與引理2同理。

2.2.2算法描述 算法1給出了頻繁狀態(tài)轉(zhuǎn)移模式三支增量挖掘算法的偽代碼實(shí)現(xiàn)。其輸入由7部分組成，即原始數(shù)據(jù)DB及其頻繁狀態(tài)集W和頻繁STAP集FDB、增量數(shù)據(jù)db、通配符區(qū)間Δ、以及兩種閾值ρw和ρd，ρw被用于判斷一個狀態(tài)是否頻繁，ρd被用于判斷一個STAP是否頻繁。其輸出為更新后的數(shù)據(jù)集DB∪db上的頻繁STAP集合FDB∪db。

算法1狀態(tài)轉(zhuǎn)移模式三支增量挖掘。

輸入：DB，db，ρd，ρw，Δ，F(xiàn)DB，W;

輸出：FDB∪db。 ∥最新的頻繁STAP

方法名：3IU-STAP

1. 根據(jù)W, DB, db以及ρw增量更新頻繁狀態(tài)集，記為W*;

2. 初始化1-FDB∪db←{s|sup(s)≥ρd≥ρw}?W*, k←2, FDB∪db←?;

3. while ((k-1)-FDB∪db≠?) do

4. k-FDB∪db←?;∥正域中所有長度為k的STAP集合

5. 根據(jù)tail和db構(gòu)造增補(bǔ)數(shù)據(jù)db′; ∥將tail作為db的頭部

6. 構(gòu)建候選模式集k-O=(k-1)-FDB∪db?1-FDB∪db; ∥笛卡爾積

7. for each P∈k-O do

8. if sup(P，db′)≥ρdthen

9. if P∈FDBthen k-FDB∪db=k-FDB∪db∪{P}; ∥將頻繁模式P存入正域

10. else isFrequent=delayDecision(DB, P,ρd,Δ); ∥掃描DB，返回布爾值

11. if isFrequent then k-FDB∪db=k-FDB∪db∪{P};

12. else ∥在db′上不頻繁

13. if P∈FDBthen isFrequent=delayDecision(db′, P,ρd,Δ); ∥掃描db′，返回布爾值

14. if isFrequent then k-FDB∪db=k-FDB∪db∪{P};

15. else continue; ∥此時P屬于負(fù)域，一定不頻繁，直接拋棄

16. return FDB∪db。

第6行描述了兩個頻繁STAP集合的笛卡爾積。對任意模式P∈(k-1)-FDB∪db以及P′∈1-FDB∪db，長度為k的候選模式通過P?P′獲得。第8～9行組成的條件對應(yīng)了式(1)中正域判定條件，其候選STAP屬于正域可直接存儲。第12、15行對應(yīng)了式(1)中負(fù)域劃分條件直接拋棄。第10～11行及13～14行分別描述了兩種延遲決策技術(shù)。

算法2實(shí)現(xiàn)了delayDecision方法以重新掃描DB并獲得新的支持度信息。如果這個新支持度不小于指定閾值ρd，則再將其劃入正域，否則拋棄。

算法2掃描數(shù)據(jù)集以更新支持度。

輸出：TRUE or FALSE。

方法名：delayDecision

1. occ=0;

2. for i=1;i<|T|-k;i++ do

5. else return FALSE。

算法3實(shí)現(xiàn)了方法count。其中α表示匹配到了DB中第α個時間點(diǎn)，β表示匹配到了模式P中第β個狀態(tài)。

算法3統(tǒng)計以ti開頭的所有匹配次數(shù)。

輸出：occ。

方法名：count

1. if β等于k then return 1; ∥P中所有的狀態(tài)都完成了一次匹配

2. occ=0;

5. return occ。

3 實(shí)驗(yàn)

本章節(jié)通過實(shí)驗(yàn)對兩方面展開了討論：1) 3IU-STAP性能與頻繁閾值ρd的關(guān)系；2) 3IU-STAP性能與增量大小的關(guān)系。

3.1 數(shù)據(jù)集與預(yù)處理

實(shí)驗(yàn)環(huán)境為CPU：i5-7500 3.40 GHz；內(nèi)存6 GB；操作系統(tǒng)：Windows 10；IDE：Eclipse，Java。

表1展示了數(shù)據(jù)集的基本信息。依次來自UCI、全國數(shù)學(xué)建模比賽(半開放)、中國海洋石油公司(油井維護(hù)數(shù)據(jù))。采用的離散化方案參見文獻(xiàn)[20]。

3.2 結(jié)果分析

如圖3所示，在各數(shù)據(jù)集中，增量算法分別比批量算法快7.7倍、12倍、649倍、5.3倍。其中，Δ=[3, 6]，增量劃分比例為10%，Apriori-STAP是批量算法。

表1 數(shù)據(jù)集的基本信息Table 1 Basic information of data set

圖3 批量算法與3IU-STAP算法時間性能Figure 3 Batch algorithm and 3IU-STAP algorithm time performance

圖4為基于不同增量數(shù)據(jù)劃分比例(r)的算法性能表現(xiàn)。當(dāng)劃分比例較小時，運(yùn)行時間少。隨著r的增加，運(yùn)行時間增加。因?yàn)樵隽吭酱?，邊界域所耗費(fèi)的時間越大。

圖4 增量大小對時間性能的影響Figure 4 The effect of incremental size on time performance

4 結(jié)論

本文基于三支決策理論，提出了一種多元時序數(shù)據(jù)上狀態(tài)轉(zhuǎn)移模式的三支增量模型與挖掘算法3IU-STAP。在插入增量數(shù)據(jù)時，通過三支劃分模型將大量的候選模式劃分為正域和負(fù)域，從而減少掃描數(shù)據(jù)集的次數(shù)。通過構(gòu)造增補(bǔ)數(shù)據(jù)集來確保掃描結(jié)果的完備性。理論分析與大量實(shí)驗(yàn)結(jié)果表明，3IU-STAP能準(zhǔn)確高效地獲得結(jié)果。