基于多尺度的時序數據部分周期模式增量挖掘

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

（1.太原科技大學 計算機科學與技術學院，太原 030024；2.中北大學 計算機科學與技術學院，太原 030051）

0 引言

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

近年來，高效地分析時序數據，使之產生業務價值成為一個熱門話題［2］。部分周期模式是時序數據庫中存在的一類重要的規則，與全模式周期相比，部分周期模式只描述時序數據中某些點的周期特征，是一種松散周期模式，在實際應用中更具普遍性。在時序數據庫中發現部分周期模式在分析顧客消費行為［3-5］、基因序列分析［6］等眾多領域具有重要意義。

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

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

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

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

1 相關定義

1.1 部分周期模式

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

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

表1 時序數據庫示例表Tab.1 Example of time series database

定義1模式X的周期出現。

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

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

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

1.2 多尺度理論

多尺度研究的本質是根據概念分層將數據集分割成多個尺度，并且從一個尺度得出結論再轉變到其他尺度。尺度轉變包括尺度上推和尺度下推：尺度上推是將小尺度數據集結論轉變成大尺度數據集結論；反之則被稱為尺度下推。本文關注利用尺度上推實現頻繁周期模式的增量挖掘。

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

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

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

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

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

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

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

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

考慮到周期性和時間維度，設計了一個估計缺失計數的模型PJK-EstimateCount。式（2）給定了一個權重系數（wc），反映了在tsmin到tsmax時間段內，有效周期支持度計數比：

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

缺失項集計數利用式（3）進行估算：

其中：est_percounti是用來估計在基準尺度數據集BSi中未知項目計數，percountj是基準尺度數據集BSj中項目的精確周期支持度計數，Sij代表著基準尺度數據集BSi和BSj間的相似度，m表示每個基準尺度數據集BS中非零精確支持度的個數。值得注意的是當時est_percounti的值應該設置為minPS。因為在基準尺度數據集BS中項目的周期計數為0 代表著它并不是一個頻繁部分周期模式，因此它的周期支持度計數不能超過minPS。

2 時序數據的多尺度部分周期模式增量挖掘算法

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

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

圖3 構建PPP-TreeFig.3 Construction of PPP-Tree

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

算法1 基準尺度數據集挖掘。

輸入 基準尺度數據集BS，最小周期支持度minPS，最大周期間隔maxPer；

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

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

算法2 增量數據集挖掘。

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

輸出 更新后的頻繁項目集。

以下將結合具體的實例來描述MSI-PPPGrowth 算法的挖掘過程。

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

表2 dseason1尺度數據集Tab.2 Scale dataset of dseason1

表3 dseason2尺度數據集Tab.3 Scale dataset of dseason2

表4 dseason3尺度數據集Tab.4 Scale dataset of dseason3

表5 dseason4尺度數據集Tab.5 Scale dataset of dseason4

表6 這部分的數據集被當作增量數據集對待，記為dIncremental。最小周期支持度minPS設為2，最大周期間隔maxPer設為2。

表6 dIncremental尺度數據表Tab.6 Scale dataset of dIncremental

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

相似矩陣M是在基準數據集BS間利用Jaccard 相似性計算所得，具體見算法1 第6）步。根據上述Can_info，相似矩陣計算結果如下：

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

表7 候選項目集信息Tab.7 Candidate itemset information

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

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

3 實驗與結果分析

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

表8 數據集參數Tab.8 Parameters of datasets

為了驗證本文所提算法的有效性，將各數據集劃分成11 份，前10 份作為基準尺度數據集，第11 份作為增量尺度數據集。

3.1 參數對算法效率的影響

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

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

圖4 maxPer對運行時間的影響Fig.4 Influence of maxPer on running time

從圖4 可以看出，隨著maxPer的增大運行時間也隨之增加，這是由于maxPer越大，滿足條件的部分周期頻繁模式也將越多，導致需要頻繁調用補全缺失周期支持度計數函數，而在稀疏數據集上，這種調用會更頻繁，因此在稀疏數據集上的增長趨勢相比稠密數據集更為明顯。在稠密數據集上的運行時間要高于在稀疏數據集的運行時間，因為稠密數據集對應的PPP-Tree 構建和頻繁樹結構調整代價更高。總體而言，所設計的增量挖掘算法在所耗時間上明顯少于PPPGrowth 與PPF-DFS 算法。MSI-PPPGrowth 較上述兩種對比算法在稀疏集T10I4D100K中的提升效率分別為7.4%與5.5%，在稠密集T15I1KD300K、accident 和Bible 中提升效率分別為10.9%與6.3%，9.7%與4.3%和7.5%與5.8%。

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

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

圖5 minPS對運行時間的影響Fig.5 Influence of minPS on running time

3.2 尺度劃分對精度的影響

從第2 章的增量挖掘算法處理過程中可以看出，由于采用估值函數來補全項目集未知的周期支持度計數，MSIPPPGrowth 算法可能會產生兩種錯誤：1）假正項集（不常見的項目由于估計誤差，導致在目標尺度數據集中被推斷為頻繁的項集）；2）假負項集（目標尺度數據集中頻繁出現但在增量數據集中數據缺失）。因此，使用精度（precision）來衡量提出的算法的準確性（如式（4）所示）。精度反映了假正項集和假負項集對實驗結果準確性的影響。

在這組實驗中，將評估稀疏數據集T10I4D100K 和稠密數據集T15I1KD300K、accidents、Bible 下的尺度劃分（如表9所示）對MSI-PPPGrowth 算法精度的影響。

表9 數據集尺度劃分Tab.9 Size division of datasets

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

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

4 結語

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