荀亞玲，王林青，蔡江輝，2*，楊海峰

（1.太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024；2.中北大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030051）

0 引言

信息大爆炸的時(shí)代，帶時(shí)間標(biāo)簽的時(shí)序數(shù)據(jù)廣泛出現(xiàn)在各個(gè)行業(yè)，如：股票價(jià)格、網(wǎng)站點(diǎn)擊流、工業(yè)傳感器數(shù)據(jù)、車聯(lián)網(wǎng)等。時(shí)序數(shù)據(jù)就是在時(shí)間上分布的一系列數(shù)值，它具有如下特征［1］：1）所有交易記錄都按照它們發(fā)生的順序排序；2）連續(xù)的交易集之間可以存在時(shí)間間隔；3）多個(gè)交易集可以共用一個(gè)時(shí)間戳。這3 個(gè)屬性將時(shí)序數(shù)據(jù)庫與廣泛研究的事務(wù)性數(shù)據(jù)庫區(qū)分開。

近年來，高效地分析時(shí)序數(shù)據(jù)，使之產(chǎn)生業(yè)務(wù)價(jià)值成為一個(gè)熱門話題［2］。部分周期模式是時(shí)序數(shù)據(jù)庫中存在的一類重要的規(guī)則，與全模式周期相比，部分周期模式只描述時(shí)序數(shù)據(jù)中某些點(diǎn)的周期特征，是一種松散周期模式，在實(shí)際應(yīng)用中更具普遍性。在時(shí)序數(shù)據(jù)庫中發(fā)現(xiàn)部分周期模式在分析顧客消費(fèi)行為［3-5］、基因序列分析［6］等眾多領(lǐng)域具有重要意義。

時(shí)序數(shù)據(jù)因其產(chǎn)生頻率快、嚴(yán)重依賴于采集時(shí)間、測點(diǎn)多、信息量大等特性給探索動(dòng)態(tài)增長時(shí)序數(shù)據(jù)庫中的部分周期模式提出了挑戰(zhàn)。Tanbeer 等［5］給出了在事務(wù)數(shù)據(jù)庫中周期性頻繁模式（Periodic Frequent Pattern，PFP）的定義，并設(shè)計(jì)了一種稱為PF-Tree（Frequent Pattern-Tree）的模式增長算法來識(shí)別這種模式，指出如果間隔（連續(xù)出現(xiàn)之間的事務(wù)數(shù)）始終小于用戶定義的最大間隔周期閾值，則模式是周期性的，該定義已在多項(xiàng)研究［7-10］中得到使用。然而，這種定義過于嚴(yán)格，一些研究［1，11］對(duì)該定義做了改進(jìn)，將最小支持閾值和最大周期閾值與每個(gè)項(xiàng)目相關(guān)聯(lián)，更公平地衡量每個(gè)項(xiàng)目的周期性。然而，這將導(dǎo)致用戶需設(shè)置的參數(shù)數(shù)量變得非常大，雖然可以使用一個(gè)函數(shù)自動(dòng)設(shè)置所有閾值，但選擇適當(dāng)?shù)暮瘮?shù)為每個(gè)項(xiàng)目分配閾值并避免丟失感興趣的模式卻很困難。

模式組合爆炸的問題給發(fā)現(xiàn)有用的周期模式提出了挑戰(zhàn)。針對(duì)該問題，Likhitha 等［12］提出了一種可能存在于時(shí)間數(shù)據(jù)庫中的封閉周期性頻繁模式的新模型。封閉的周期頻繁模式［13］是一個(gè)簡潔的無損子集表示，唯一地保存了數(shù)據(jù)庫中所有周期頻繁模式的完整信息，同時(shí)一種高效的深度優(yōu)先搜索算法，即CPFP-Miner（Closed Periodic-Frequent Pattern Miner）被提出，用于查找數(shù)據(jù)庫中所有需要的模式。Fournier-Viger 等［8］提出了PFPM（Periodic Frequent Pattern Miner）算法，該算法允許用戶使用三種周期性度量（最小周期性、最大周期性和平均周期性）來發(fā)現(xiàn)周期性頻繁模式，為用戶提供了更多的靈活性，從而可以更精確地指定用戶感興趣的模式類型。PFPM 和許多其他研究一樣，均假設(shè)模式的周期性隨時(shí)間保持穩(wěn)定［14］，但在現(xiàn)實(shí)生活中，模式的周期性行為可能會(huì)隨著時(shí)間的推移而改變。因此，一些研究［15］試圖發(fā)現(xiàn)模式的頻率或效用可能發(fā)生變化的概念漂移點(diǎn)（變化點(diǎn)），但依賴于非常嚴(yán)格的最大周期模型。

部分周期模式作為一種更為松散的周期模式，對(duì)它的研究更具普適意義。Kang 等［16］基于部分周期的概念，先后提出了類Apriori 和最大子模式命中的部分周期模式挖掘算法，其中最大子模式命中集將時(shí)間序列模式子集存入最大命中子模式樹中，在挖掘部分周期模式時(shí)只需要掃描兩次時(shí)序數(shù)據(jù)庫；同時(shí)，基于Apriori 特性和變通的時(shí)間序列部分周期模式挖掘算法還可以挖掘多周期的時(shí)間序列部分周期模式。Upadhyay 等［17］將頻繁部分周期模式應(yīng)用到發(fā)現(xiàn)物體的運(yùn)動(dòng)規(guī)律，使用部分周期模式樹來遞歸地尋找所有物體運(yùn)動(dòng)規(guī)律，但在跟蹤和定位物體的過程中會(huì)出現(xiàn)不確定性問題，因此，引入了一個(gè)時(shí)空概率來表示物體位置不確定性。Kiran等［7］發(fā)現(xiàn)確定項(xiàng)目集中每個(gè)候選模式的周期性使得部分周期頻繁模式挖掘成為一個(gè)計(jì)算代價(jià)很高的過程，因此，采用貪婪搜索來確定模式的周期性，通過消除次優(yōu)解的非周期模式來發(fā)現(xiàn)所有的部分周期頻繁模式。

上述傳統(tǒng)的部分周期模式挖掘方法有著很強(qiáng)的局限性：1）不具備可擴(kuò)展性；2）面對(duì)時(shí)序數(shù)據(jù)來源廣泛，且具有大體量、多源性、連續(xù)采樣、價(jià)值密度低、動(dòng)態(tài)性強(qiáng)等特點(diǎn)，導(dǎo)致目前的傳統(tǒng)挖掘方法在處理增量數(shù)據(jù)集時(shí)所耗時(shí)間巨大。一些研究［18-20］對(duì)動(dòng)態(tài)增長的模式挖掘進(jìn)行了研究，主要關(guān)注以下兩方面：1）避免對(duì)原始數(shù)據(jù)庫重新掃描；2）生成并調(diào)整大的樹結(jié)構(gòu)。因此，本文通過結(jié)合多尺度理論，提出一種新的適應(yīng)動(dòng)態(tài)增長時(shí)序數(shù)據(jù)部分周期模式挖掘算法（Multi-Scale Incremental Partial Periodic Frequent Pattern，MSIPPPGrowth）。在MSI-PPPGrowth 中，利用時(shí)序數(shù)據(jù)客觀存在多尺度特性，首先將數(shù)據(jù)集進(jìn)行更細(xì)粒度的劃分獲取到基準(zhǔn)尺度數(shù)據(jù)集，在基準(zhǔn)尺度數(shù)據(jù)集上利用PPPGrowth（Partial Periodic Pattern-Growth）算法挖掘相應(yīng)的部分周期模式；然后通過不同尺度數(shù)據(jù)間的相似度完成跨尺度推導(dǎo)，將單一尺度數(shù)據(jù)集上的關(guān)系通過尺度上推，轉(zhuǎn)化成目標(biāo)尺度上的關(guān)系，實(shí)現(xiàn)一次挖掘即可得到多層次的知識(shí)。其中，考慮時(shí)序周期性，基于克里金（Kriging）法［21］設(shè)計(jì)了一個(gè)新的函數(shù)Periodic-Jaccard 來有效解決尺度轉(zhuǎn)換過程中的缺失計(jì)數(shù)補(bǔ)全問題。

1 相關(guān)定義

1.1 部分周期模式

時(shí)序數(shù)據(jù)庫中可能存在的部分周期模式的基本模型［1］如下：I={i1，i2，…，in}（n≥1）是出現(xiàn)在數(shù)據(jù)庫中的n個(gè)項(xiàng)目集合。項(xiàng)目X?I的集合稱為模式，一個(gè)模式包含k個(gè)項(xiàng)目稱為k模式，這個(gè)模式的長度為k。一個(gè)事務(wù)tr包含事務(wù)識(shí)別符、時(shí)間戳和一個(gè)模式，可以表示成tr=(tid，ts，Y)，tid代表著事務(wù)的識(shí)別符，ts∈R+代表事務(wù)的到達(dá)時(shí)間或時(shí)間戳，Y是一個(gè)模式。一個(gè)時(shí)序數(shù)據(jù)庫表示為TDB，TDB是有序事務(wù)集的集合TDB={tr1，tr2，…，trm}，m=|TDB|表示為時(shí)序數(shù)據(jù)庫的大?。ɑ蛘呤聞?wù)集的總個(gè)數(shù)）。令，是模式X出現(xiàn)在TDB中的事務(wù)的時(shí)間戳有序列表。

例1 考慮表1 所示的時(shí)序數(shù)據(jù)庫，項(xiàng)目集I={a，b，c，d，e，f，g，h}，這個(gè)時(shí)序數(shù)據(jù)庫包含12 個(gè)事務(wù)，因此這個(gè)數(shù)據(jù)庫的大小為|TDB|=12。在此時(shí)序數(shù)據(jù)庫中，每個(gè)事務(wù)都由事務(wù)的識(shí)別符、時(shí)間戳和一個(gè)模式組成。項(xiàng)目a 和b表示成{a，b}簡稱為ab，是一個(gè)模式并且這個(gè)模式包含兩個(gè)項(xiàng)目，稱為2 模式，模式ab 出現(xiàn)在第1 個(gè)事務(wù)里，因此第1 次出現(xiàn)的時(shí)間戳為=1，由此可得在表1 中所有包含模式ab的事務(wù)集所出現(xiàn)的時(shí)間戳的集合為TSab={1，3，4，5，9，11，12}。

表1 時(shí)序數(shù)據(jù)庫示例表Tab.1 Example of time series database

定義1模式X的周期出現(xiàn)。

定義2模式X的周期支持度。

定義3頻繁部分周期模式。

模式X是頻繁的部分周期模式，當(dāng)且僅當(dāng)PS(X) ≥minPS，minPS表示用戶指定的最小周期支持度。

1.2 多尺度理論

多尺度研究的本質(zhì)是根據(jù)概念分層將數(shù)據(jù)集分割成多個(gè)尺度，并且從一個(gè)尺度得出結(jié)論再轉(zhuǎn)變到其他尺度。尺度轉(zhuǎn)變包括尺度上推和尺度下推：尺度上推是將小尺度數(shù)據(jù)集結(jié)論轉(zhuǎn)變成大尺度數(shù)據(jù)集結(jié)論；反之則被稱為尺度下推。本文關(guān)注利用尺度上推實(shí)現(xiàn)頻繁周期模式的增量挖掘。

概念分層H是一個(gè)偏序關(guān)系集(H，?)，其中H為有限概念集，“?”表示H所包含概念之間的一種偏序關(guān)系，表示概念涉及范圍、粒度的相對(duì)大小或者時(shí)間幅度的相對(duì)長短，那么稱此概念分層(H，?)具有多尺度特性。以具備多尺度特性的概念分層為標(biāo)準(zhǔn)進(jìn)行數(shù)據(jù)集的劃分，便可以形成多尺度數(shù)據(jù)集。

時(shí)序數(shù)據(jù)庫TDB以概念分層(H，?)中的概念hi為數(shù)據(jù)尺度，按照數(shù)據(jù)尺度劃分后的結(jié)果，所有子數(shù)據(jù)集為時(shí)序數(shù)據(jù)庫TDB在數(shù)據(jù)尺度hi下的元尺度數(shù)據(jù)集。若其他尺度數(shù)據(jù)集可以由該元尺度數(shù)據(jù)集合并或分解得到，那么該元尺度數(shù)據(jù)集稱為基準(zhǔn)尺度數(shù)據(jù)集BS，相應(yīng)地通過概念hi劃分的上層尺度數(shù)據(jù)集稱為目標(biāo)尺度數(shù)據(jù)集TS。尺度上推轉(zhuǎn)換，即通過基準(zhǔn)尺度集結(jié)果推導(dǎo)出目標(biāo)尺度數(shù)據(jù)集對(duì)應(yīng)的近似結(jié)果，而不對(duì)目標(biāo)尺度數(shù)據(jù)集TS進(jìn)行直接挖掘，達(dá)到快速更新頻繁的部分周期模式目的。

PFIi和PFIj分別代表著基準(zhǔn)尺度數(shù)據(jù)集BSi和BSj的頻繁部分周期模式。在兄弟尺度間和尺度上推的過程中都常有項(xiàng)目周期支持度計(jì)數(shù)缺失的情況，因此，基于克里金法［21］提出一個(gè)估計(jì)缺失周期支持度計(jì)數(shù)模型。

克里金法是一種基于最小二乘法的隨機(jī)插值技術(shù)，用方差矩陣作為權(quán)重函數(shù)，可應(yīng)用于通過其他點(diǎn)數(shù)據(jù)來估算地表上任意點(diǎn)，估算公式如式（1）所示。克里金法中隨機(jī)場（如圖1 所示）中隨機(jī)場所對(duì)應(yīng)的指數(shù)集通常為地理坐標(biāo)，而隨機(jī)場內(nèi)每一個(gè)點(diǎn)的測度都是一個(gè)隨機(jī)變量，服從特定的概率分布。

圖1 克里金模型Fig.1 Model of Kriging

式中：s0為未知點(diǎn)，{s1，s2，…，sn}為隨機(jī)場的樣本點(diǎn)；a為克里金權(quán)重，由樣本點(diǎn)與未知點(diǎn)間的協(xié)方差矩陣確定；μ為隨機(jī)過程{Y(t)}的期望；(s0)是Y在未知點(diǎn)s0處的估計(jì)；ε為任意常數(shù)，用于估計(jì)值的誤差修正。

MSI-PPPGrowth 將空間場降維到平面場，如圖2 所示，需要通過1、2、3、4 這4 個(gè)已知點(diǎn)來推測待估值點(diǎn)5。

圖2 平面場模型Fig.2 Model of plane field

考慮到周期性和時(shí)間維度，設(shè)計(jì)了一個(gè)估計(jì)缺失計(jì)數(shù)的模型PJK-EstimateCount。式（2）給定了一個(gè)權(quán)重系數(shù)（wc），反映了在tsmin到tsmax時(shí)間段內(nèi)，有效周期支持度計(jì)數(shù)比：

其中：minPS為最小周期支持度，maxPer為最大周期間隔，tsmin、tsmax表示尺度數(shù)據(jù)集中最小時(shí)間和最大時(shí)間。

缺失項(xiàng)集計(jì)數(shù)利用式（3）進(jìn)行估算：

其中：est_percounti是用來估計(jì)在基準(zhǔn)尺度數(shù)據(jù)集BSi中未知項(xiàng)目計(jì)數(shù)，percountj是基準(zhǔn)尺度數(shù)據(jù)集BSj中項(xiàng)目的精確周期支持度計(jì)數(shù)，Sij代表著基準(zhǔn)尺度數(shù)據(jù)集BSi和BSj間的相似度，m表示每個(gè)基準(zhǔn)尺度數(shù)據(jù)集BS中非零精確支持度的個(gè)數(shù)。值得注意的是當(dāng)時(shí)est_percounti的值應(yīng)該設(shè)置為minPS。因?yàn)樵诨鶞?zhǔn)尺度數(shù)據(jù)集BS中項(xiàng)目的周期計(jì)數(shù)為0 代表著它并不是一個(gè)頻繁部分周期模式，因此它的周期支持度計(jì)數(shù)不能超過minPS。

2 時(shí)序數(shù)據(jù)的多尺度部分周期模式增量挖掘算法

由于時(shí)序數(shù)據(jù)庫中允許連續(xù)的事務(wù)之間存在時(shí)間間隔和存在公共時(shí)間戳的事務(wù)，因此在衡量周期性時(shí)不能只考慮項(xiàng)目的頻率，還需要考慮它在數(shù)據(jù)庫中到達(dá)的時(shí)間，以便準(zhǔn)確地確定項(xiàng)目集的周期性?；趥鹘y(tǒng)樹結(jié)構(gòu)的挖掘方法因其未考慮到時(shí)間參數(shù)的影響而且只考慮單個(gè)項(xiàng)目頻率，并不能直接應(yīng)用于部分周期模式挖掘。PPPGrowth［1］通過在樹結(jié)構(gòu)中添加時(shí)間和周期頻率兩個(gè)屬性（被稱為PPP-Tree）可有效度量項(xiàng)目的周期性；但PPP-Growth 需要頻繁遍歷樹結(jié)構(gòu)，在挖掘時(shí)序數(shù)據(jù)的部分周期模式過程中造成的時(shí)間消耗令人難以接受。因此，MSI-PPPGrowth 將多尺度理論引入PPPGrowth 算法，避免了頻繁遍歷樹結(jié)構(gòu)的嚴(yán)重開銷。

圖3 展示了PPPGrowth 算法基于表2 所示數(shù)據(jù)集對(duì)應(yīng)的樹結(jié)構(gòu)構(gòu)造過程，圖中pf 為部分周期支持度，每個(gè)樹節(jié)點(diǎn)包含部分周期頻繁項(xiàng)目本身及其在事物集中出現(xiàn)的時(shí)間戳，以方便計(jì)算周期間隔。PPPGrowth 的挖掘過程如下：從每個(gè)部分周期項(xiàng)（作為初始后綴項(xiàng)集）開始，構(gòu)造條件模式庫（一個(gè)子數(shù)據(jù)庫，由與后綴項(xiàng)集共現(xiàn)的PPP 樹中的前綴路徑的集合組成），然后構(gòu)造條件PPP 樹，并在樹上遞歸地執(zhí)行挖掘。通過將后綴項(xiàng)集與從條件PPP 樹生成的部分周期項(xiàng)集連接來實(shí)現(xiàn)模式增長。

圖3 構(gòu)建PPP-TreeFig.3 Construction of PPP-Tree

算法1 描述了在基準(zhǔn)尺度數(shù)據(jù)集BS中挖掘頻繁部分周期模式，并利用函數(shù)來補(bǔ)全缺失的部分后期支持度計(jì)數(shù)的過程。

算法1 基準(zhǔn)尺度數(shù)據(jù)集挖掘。

輸入 基準(zhǔn)尺度數(shù)據(jù)集BS，最小周期支持度minPS，最大周期間隔maxPer；

輸出 所有頻繁部分周期模式（D1）。

算法2 描述了在增量數(shù)據(jù)集TS中挖掘頻繁的部分周期模式，通過三種情況來將BS與TS的結(jié)果更新，獲取時(shí)序數(shù)據(jù)更新后的最終部分周期模式。

算法2 增量數(shù)據(jù)集挖掘。

輸入 增量數(shù)據(jù)集TS，最小周期支持度minPS，最大周期間隔maxPer；

輸出 更新后的頻繁項(xiàng)目集。

以下將結(jié)合具體的實(shí)例來描述MSI-PPPGrowth 算法的挖掘過程。

算法1 的第1）步將公司一年的銷售數(shù)據(jù)按照對(duì)應(yīng)于尺度“季”的屬性劃分為dseason1、dseason2、dseason3、dseason4四個(gè)尺度。從概念層次來看，可以看到“年”是4個(gè)季節(jié)的上層尺度TS，4個(gè)季節(jié)是“年”的基準(zhǔn)尺度BS，也就是說dyear=dseason1?dseason2?dseason3?dseason4。4個(gè)尺度的數(shù)據(jù)集如表2～5所示。

表2 dseason1尺度數(shù)據(jù)集Tab.2 Scale dataset of dseason1

表3 dseason2尺度數(shù)據(jù)集Tab.3 Scale dataset of dseason2

表4 dseason3尺度數(shù)據(jù)集Tab.4 Scale dataset of dseason3

表5 dseason4尺度數(shù)據(jù)集Tab.5 Scale dataset of dseason4

表6 這部分的數(shù)據(jù)集被當(dāng)作增量數(shù)據(jù)集對(duì)待，記為dIncremental。最小周期支持度minPS設(shè)為2，最大周期間隔maxPer設(shè)為2。

表6 dIncremental尺度數(shù)據(jù)表Tab.6 Scale dataset of dIncremental

利用PPP-Tree 根據(jù)算法1 中第2）、第3）和第5）步，按最小支持度閾值挖掘基準(zhǔn)尺度數(shù)據(jù)集BS來獲得周期頻繁項(xiàng)目，并且存儲(chǔ)所有的頻繁周期項(xiàng)目和他們所對(duì)應(yīng)的支持度計(jì)數(shù)到候選集項(xiàng)目信息表Can_info，如表7 所示。

相似矩陣M是在基準(zhǔn)數(shù)據(jù)集BS間利用Jaccard 相似性計(jì)算所得，具體見算法1 第6）步。根據(jù)上述Can_info，相似矩陣計(jì)算結(jié)果如下：

算法1 的7）～19）用以估計(jì)項(xiàng)目及未知的周期支持度計(jì)數(shù)，例如，對(duì)表7season1 中的”a“項(xiàng)缺失值進(jìn)行估計(jì)，根據(jù)式（2）所計(jì)算的結(jié)果為est_percounta==1.631 7，est_percounta≤minPS=2，所以est_percounta的最終結(jié)果為1.631 7。

表7 候選項(xiàng)目集信息Tab.7 Candidate itemset information

頻繁項(xiàng)集的更新僅通過挖掘新的尺度數(shù)據(jù)集和尺度變換來實(shí)現(xiàn)。對(duì)于不同的基準(zhǔn)尺度數(shù)據(jù)集更新時(shí)，采用算法2來具體實(shí)現(xiàn)。首先，根據(jù)算法2 的第1）步得到所對(duì)應(yīng)的部分周期頻繁項(xiàng)目集｛a，b，c，d，e，ab，ad，bd，cd，de，abd｝（如表7所示）；再通過測量原始BS數(shù)據(jù)集的頻繁項(xiàng)集與新添加數(shù)據(jù)集的頻繁項(xiàng)集之間的相似性，從而更新相似性矩陣M。

當(dāng)新的頻繁項(xiàng)集與原始數(shù)據(jù)集的周期頻繁項(xiàng)進(jìn)行比較時(shí)，將發(fā)生以下三種情況，對(duì)應(yīng)的處理過程見算法2 中4）～28）行：情況一，在兩個(gè)數(shù)據(jù)集中都是頻繁的部分周期模式，比如項(xiàng)目ab、ad、bd、abd，只需要通過添加項(xiàng)集的原始計(jì)數(shù)和新計(jì)數(shù)來更新每個(gè)頻繁項(xiàng)集的支持計(jì)數(shù)。情況二，項(xiàng)目集在原始數(shù)據(jù)集中是頻繁的，但在新添加的數(shù)據(jù)中并不頻繁，如bc。新數(shù)據(jù)中那些不頻繁的項(xiàng)集的計(jì)數(shù)需要根據(jù)新數(shù)據(jù)與每個(gè)BS數(shù)據(jù)集之間的相似性，來估計(jì)缺失的周期支持度計(jì)數(shù)。為了提高估計(jì)精度，以所有BS數(shù)據(jù)集的估計(jì)值的平均值作為最終估計(jì)結(jié)果。情況三，項(xiàng)目集在原始數(shù)據(jù)集BS中不是頻繁項(xiàng)集，但在增量數(shù)據(jù)集TS中卻是頻繁的，如de。Can_info包含了每個(gè)BS數(shù)據(jù)集中頻繁項(xiàng)集候選信息，因此首先在Can_info中搜索該項(xiàng)集：如果Can_info中存在這個(gè)項(xiàng)集，則直接讀取其計(jì)數(shù)；否則必須估計(jì)每個(gè)項(xiàng)集的周期支持度計(jì)數(shù)基于相似性的BS數(shù)據(jù)集。將每個(gè)BS數(shù)據(jù)集中的計(jì)數(shù)添加到新數(shù)據(jù)中的計(jì)數(shù)中，估計(jì)完后周期支持度計(jì)數(shù)總和為更新后的項(xiàng)集的最終結(jié)果。

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

為驗(yàn)證本文算法的有效性，所有實(shí)驗(yàn)均在電腦配置為CPU：Intel Core i7-4850HQ CPU @ 2.30 GHz，內(nèi)存16 GB，操作系統(tǒng)為macOS 11.6.1上基于Python 3.8.2實(shí)現(xiàn)。實(shí)驗(yàn)使用的數(shù)據(jù)集如表8所示，其中T10I4D100K是稀疏數(shù)據(jù)集而T15I1KD300K、accident 和Bible 為稠密數(shù)據(jù)集。對(duì)比算法選擇了未考慮時(shí)間尺度特性的PPPGrowth算法［1］與PPF-DFS算法［22］。

表8 數(shù)據(jù)集參數(shù)Tab.8 Parameters of datasets

為了驗(yàn)證本文所提算法的有效性，將各數(shù)據(jù)集劃分成11 份，前10 份作為基準(zhǔn)尺度數(shù)據(jù)集，第11 份作為增量尺度數(shù)據(jù)集。

3.1 參數(shù)對(duì)算法效率的影響

3.1.1 最大周期間隔maxPer對(duì)算法性能的影響

該組實(shí)驗(yàn)分別在稀疏和稠密數(shù)據(jù)上驗(yàn)證了maxPer對(duì)算法性能的影響（最小周期支持度minPS=100，maxPer變化范圍為10～320），實(shí)驗(yàn)結(jié)果見圖4。

圖4 maxPer對(duì)運(yùn)行時(shí)間的影響Fig.4 Influence of maxPer on running time

從圖4 可以看出，隨著maxPer的增大運(yùn)行時(shí)間也隨之增加，這是由于maxPer越大，滿足條件的部分周期頻繁模式也將越多，導(dǎo)致需要頻繁調(diào)用補(bǔ)全缺失周期支持度計(jì)數(shù)函數(shù)，而在稀疏數(shù)據(jù)集上，這種調(diào)用會(huì)更頻繁，因此在稀疏數(shù)據(jù)集上的增長趨勢相比稠密數(shù)據(jù)集更為明顯。在稠密數(shù)據(jù)集上的運(yùn)行時(shí)間要高于在稀疏數(shù)據(jù)集的運(yùn)行時(shí)間，因?yàn)槌砻軘?shù)據(jù)集對(duì)應(yīng)的PPP-Tree 構(gòu)建和頻繁樹結(jié)構(gòu)調(diào)整代價(jià)更高?？傮w而言，所設(shè)計(jì)的增量挖掘算法在所耗時(shí)間上明顯少于PPPGrowth 與PPF-DFS 算法。MSI-PPPGrowth 較上述兩種對(duì)比算法在稀疏集T10I4D100K中的提升效率分別為7.4%與5.5%，在稠密集T15I1KD300K、accident 和Bible 中提升效率分別為10.9%與6.3%，9.7%與4.3%和7.5%與5.8%。

3.1.2 最小周期支持度minPS對(duì)算法性能的影響

該組實(shí)驗(yàn)分別在稀疏和稠密數(shù)據(jù)上驗(yàn)證了minPS對(duì)算法性能的影響（maxPer=80，minPS從50～150），實(shí)驗(yàn)結(jié)果見圖5。圖5 展示了隨著minPS的增加，滿足條件的部分周期模式越少，因此計(jì)算缺失計(jì)數(shù)過程和調(diào)整樹結(jié)構(gòu)代價(jià)明顯減小，從而使得運(yùn)行時(shí)間減少。在稀疏數(shù)據(jù)集T10I4D100K 和稠密數(shù)據(jù)集T15I1KD300K、accidents、Bible 上，所提算法的挖掘時(shí)間均少于PPPGrowth 算法與PPF-DFS 算法，效率分別提升約為7%與12%、11.3%與8%、3.2%與5.9%和5.6%與5.2%。其主要原因在于，數(shù)據(jù)集更新后，MSI-PPPGrowth 算法不需要重新掃描數(shù)據(jù)集或頻繁調(diào)整樹結(jié)構(gòu)，只需要根據(jù)所設(shè)計(jì)的相關(guān)函數(shù)來估計(jì)所缺失的周期支持度?？梢姡琈SI-PPPGrowth能夠很好地應(yīng)對(duì)各種類型的數(shù)據(jù)集，具有廣泛的適用性。

圖5 minPS對(duì)運(yùn)行時(shí)間的影響Fig.5 Influence of minPS on running time

3.2 尺度劃分對(duì)精度的影響

從第2 章的增量挖掘算法處理過程中可以看出，由于采用估值函數(shù)來補(bǔ)全項(xiàng)目集未知的周期支持度計(jì)數(shù)，MSIPPPGrowth 算法可能會(huì)產(chǎn)生兩種錯(cuò)誤：1）假正項(xiàng)集（不常見的項(xiàng)目由于估計(jì)誤差，導(dǎo)致在目標(biāo)尺度數(shù)據(jù)集中被推斷為頻繁的項(xiàng)集）；2）假負(fù)項(xiàng)集（目標(biāo)尺度數(shù)據(jù)集中頻繁出現(xiàn)但在增量數(shù)據(jù)集中數(shù)據(jù)缺失）。因此，使用精度（precision）來衡量提出的算法的準(zhǔn)確性（如式（4）所示）。精度反映了假正項(xiàng)集和假負(fù)項(xiàng)集對(duì)實(shí)驗(yàn)結(jié)果準(zhǔn)確性的影響。

在這組實(shí)驗(yàn)中，將評(píng)估稀疏數(shù)據(jù)集T10I4D100K 和稠密數(shù)據(jù)集T15I1KD300K、accidents、Bible 下的尺度劃分（如表9所示）對(duì)MSI-PPPGrowth 算法精度的影響。

表9 數(shù)據(jù)集尺度劃分Tab.9 Size division of datasets

從圖6 觀察到，尺度的劃分對(duì)算法性能有著重要的影響，但無論在密集型數(shù)據(jù)集還是稀疏性數(shù)據(jù)集上，MSIPPPGrowth 算法的精度均保持在80%以上。具體而言，稠密數(shù)據(jù)集由于其更平滑的數(shù)據(jù)分布使其效果更優(yōu)于稀疏數(shù)據(jù)集，且尺度劃分得越細(xì)，根據(jù)估值函數(shù)所得到的周期支持度越能接近真實(shí)值，從圖6 可以看出，當(dāng)尺度大小為SIZE4 時(shí)，算法的精度都達(dá)到91.5%以上?？傮w而言，MSI-PPPGrowth算法雖然在精度上存在著一定的誤差，但這種誤差和換取的效率提升是值得的，尤其對(duì)于大型密集數(shù)據(jù)集而言，整體的效率最高提高了12%。因此，通過一定精度的損失來抵消挖掘過程中所消耗的時(shí)間是可行且有效的。

圖6 不同尺度劃分造成的精度影響Fig.6 Influence of different scale divisions on accuracy

4 結(jié)語

本文提出了一種結(jié)合多尺度理論的時(shí)間序列部分周期模式挖掘算法（MSI-PPPGrowth），充分利用了時(shí)序數(shù)據(jù)的多尺度特性，大幅降低了傳統(tǒng)動(dòng)態(tài)時(shí)序數(shù)據(jù)在部分周期模式挖掘過程中頻繁數(shù)據(jù)庫掃描和調(diào)整樹結(jié)構(gòu)的開銷。實(shí)驗(yàn)結(jié)果表明本文算法具有廣泛的適應(yīng)性和高效性，在稀疏數(shù)據(jù)集和稠密數(shù)據(jù)集上運(yùn)行效率分別提升了近7%和12%。本文算法尤其適應(yīng)于大規(guī)模數(shù)據(jù)集，因此，以期對(duì)大規(guī)模動(dòng)態(tài)數(shù)據(jù)的并行挖掘做進(jìn)一步的研究。