基于同步頻繁樹的時間序列關聯規則分析

李海林，龍芳菊

（1. 華僑大學 信息管理系，福建 泉州 362021; 2. 華僑大學 現代應用統計與大數據研究中心，福建 廈門 361021）

時間序列數據是指一系列時間及其對應屬性值組成的序列集合，常見于醫學、金融、水文等領域[1]。通過分析這些數據，如疾病[2]、股票[3-4]和水文數據[5]等，研究者可以發現相關問題的潛在信息，進而為相關部門或企業的工作提供指導性建議。關聯規則是由Agrawal等[6]首次提出的，先找出頻繁項集，再通過項集的支持度和置信度等指標，分析被研究對象間的關聯關系。例如，購物籃分析案例就是關聯規則的一個經典應用。Apriori算法是由Agrawal等[7]提出的，在挖掘頻繁項集的過程中，該算法不僅要多次掃描數據庫，還會產生大量的候選頻繁項集，因而導致算法的挖掘效率低。為解決這一問題，很多學者從不同角度提出相應的方法。魏玲等[8]借鑒文獻[9]的MapReduce框架，提出了基于MapReduce的Apriori改進算法(MapReduce算法)，算法的基本思想是將頻繁K?1項集的前K?2項作為鍵，將最后一項作為值，并將具有相同鍵的頻繁K?1項集合并，以實現快速挖掘出候選頻繁K項集。此外，他們還提出性能更高的基于Bigtable與MapReduce的Apriori改進算法(BM_Apriori算法)，算法以事務集序號記錄每個項出現的位置，通過求頻繁K?1項集間的序號列表交集，即可快速獲取候選頻繁K項集。Zhang[10]基于概率論知識，通過參數a和b估算數據項集同時出現的概率，進而確定頻繁項集，最終實現對Apriori算法的改進，但是該算法存在頻繁項集缺失的可能性。Tran等[11]為了減少Apriori算法掃描數據庫的次數，將事務集轉化成事務矩陣，但是在矩陣運算過程中需要消耗較長時間。楊秋翔等[12]基于1和0表示數據項出現和未出現的數據集表示法創建權值向量矩陣，提出可以在數據挖掘過程中不斷縮減矩陣的算法(WV_Apriori算法)，以此達到提高挖掘頻繁K項集速率的目的，但是當數據量越來越大時，創建的矩陣也會隨之擴大，進而降低挖掘速率。Han等[13]提出能快速挖掘頻繁項集的FP-growth算法，該算法將原數據存儲到FP-tree中，從中挖掘頻繁項集，從而不會產生候選頻繁項集，但是該算法不能給出頻繁項集的支持度和置信度。此外，上述算法不能直接用于時間序列數據的關聯規則挖掘。Das等[14]于1998年首次提出挖掘時間序列數據的關聯規則，此后該研究成為數據挖掘領域的熱門方向。Velumani等[15]在數據預處理階段，先將時間序列數據轉為多個事務集，再用Apriori算法挖掘關聯規則。趙益[16]提出了Improved-Apriori算法，算法通過計算位置列表的方式可避免多次掃描數據庫。然而這2個算法均是基于Apriori，它們都會產生大量的候選頻繁項集，會導致其挖掘效率不高。針對時間序列數據，其他學者也做出了相應的努力。Das等[14]先將一條時間序列等分成多條子序列，再挖掘多個時間序列的項間關聯規則，但是他并沒有給出3支及以上股票的實驗結果。Chen等[17]所提的CEMiner算法基于區間數據，發現多個項間的閉合時態模式。Ruan等[18]提出一種可以在大規模區間型時態數據上并行和定量挖掘時間序列模式的算法。然而，這2種方法不能給出頻繁項集的支持度和置信度。由于樹形結構分支明確，直觀易懂，因而樹形存儲結構是一種較為常用的存儲形式，許多學者也將該存儲結構應用到數據挖掘中。Schlüter等[19]提出利用2種樹結構挖掘時間序列的關聯規則，Rashid等[20]基于樹結構，采用模式增長方法挖掘時態模式并給出關聯規則，Pankaj等[21]也用到了FP-tree結構。另外，馬慧等[22]利用FP-tree的優勢并考慮項間具有不同的有效時間，提出一種基于FP-tree挖掘時態關聯規則算法。

鑒于上述文獻的理論研究及其所存在的問題，本文針對多條時間序列數據，通過數據降維并將符號化后的降維數據用趨勢項?位置表示，再利用樹結構找出頻繁K項集，該過程通過求樹的葉子節點與列表項間的信息交集，便可判斷該項是否與該樹枝中的所有結點構成頻繁K項集，無需產生大量的候選頻繁項集，此外，算法還能給出頻繁項集的支持度和置信度。由于在某些情況下需要考慮多條時間序列在同時區內的關聯關系，例如：在帶有時間屬性的零售商品銷售數據中，顧客常會同時購買A和B等商品，若僅知道商品A的需求變化趨勢但不知道商品B的變化趨勢，此時可以通過挖掘商品間的銷售量變化趨勢的關聯規則，進而預測商品B的需求變化趨勢。因此，在同時區內，本文提出一種基于同步頻繁樹的時序數據關聯規則算法(synchronize frequent tree, SFT)。

1 時間序列特征表示

挖掘多條時間序列數據間的頻繁項集，需要先對原數據進行特征表示。本文定義了2種表示法，即趨勢項?位置表示法和事務集表示法。經典算法Apriori、FP-growth以及近些年提出的MapReduce、BM_Apriori和WV_Apriori算法都是基于事務集表示的數據，而SFT算法則是基于趨勢項?位置表示的數據。

1.1 事務集表示法和趨勢項?位置表示法

Apriori、FP-growth、MapReduce、BM_Apriori和WV_Apriori等算法只能挖掘事務集數據的頻繁項集，對于時間序列數據，需要將其轉換為事務集才可以使用。本文將時間序列轉換為事務集的方法定義為事務集表示法，其轉換規則為：多條時間序列數據在同時區內的趨勢項組合表示一個事務。例如：TA=(a1,a2,a3)、TB=(b1,b2,b3)和TC=(c1,c2,c3) 是3條符號化后的時間序列，其轉換為事務集的結果為[(a1,b1,c1), (a2,b2,c2), (a3,b3,c3)]。

趨勢項?位置表示法是為了提出SFT算法而定義的一種時間序列轉換方法，其關鍵在于考慮到時間序列數據的時間屬性具有一維性的特點，表示規則為趨勢項+位置列表，其中趨勢項是由時間序列進行線性分段后的斜率確定，共分上升、平穩和下降3種，用q1、q2、q3表示，q表示時間序列名。例如：TA=(a2,a2,a1,a3,a1,a3,a1,a1) 是一條符號化后的時間序列數據，將其用趨勢項?位置表示為list_A=[{a1:(2,4,6,7)},{a2:(0,1)},{a3:(3,5)}]，其中，{a2:(0,1)}表示趨勢項a2在第0和第1個時區內出現。

1.2 性能比較與分析

顯然事務集表示法并沒有減少原數據量，而趨勢項?位置表示法只保留每個趨勢項，相同趨勢項則用位置索引代替。由于特征表示數據是各類算法挖掘工作的基礎，其對算法運行效率具有很大影響，因此有必要從轉換時效和轉換后數據的內存占用情況對上述2種表示法的性能進行比較和分析。實驗采用python程序將后文使用的3條股票時間序列數據分別進行事務集表示和趨勢項?位置表示，每條數據量為5 343，共16 029個數據。實驗結果如表1所示。

表1 2種表示法的性能比較Table 1 Performance comparison of two representations

從轉換時效方面，2種表示法處理的數據量相同，因而差異性不大；從內存占用方面，由趨勢項?位置表示的數據要遠低于事務集表示的數據，因為趨勢項?位置表示法以數值型(int)數據記錄趨勢項的變化趨勢，而事務集表示法則以字符型(str)數據記錄，由于int占用的內存要低于str占用的內存，因此用前者表示的數據，內存占用情況要優于后者。

2 同步頻繁樹

鑒于經典算法Apriori和FP-growth不能直接對時間序列數據進行關聯規則挖掘，提出了一種可以解決上述問題的新算法，即SFT算法。新算法通過求葉子節點與列表項間的信息交集，便可判斷該項是否與該樹枝中的所有節點構成頻繁項集。算法總體思路：先將時間序列用趨勢項?位置表示，并去除非頻繁項，再用首條時間序列構建一棵基礎樹，通過求葉子節點與列表項間的信息交集，便可以在樹的生長過程中不斷挖掘出頻繁K項集。通過給出頻繁K項集所有前綴項的信息量，便可以計算出頻繁K項集的支持度與置信度。新方法除了適用于多條數時間序列數據外，在小數據和大數據中，其都能取得較優的時間效率，此外還能給出頻繁項集的支持度和置信度。

X表示葉子節點所在的列表，x為樹的葉子節點，也是列表的部分項，即X中的項需要滿足某些條件后才能成為樹的葉子節點。yi表示列表Y的項。loc_list表示葉子節點信息表與列表項位置表的信息交集，其信息量用loc_count表示，data表示僅包含頻繁項的數據集，min_supc表示最小支持度計數。

算法 SFT算法

輸入 data，min_supc；

輸出 頻繁K項集。

1)以Root為根，首條時間序列的所有項為xt，構建一棵基礎樹；

2)讓所有葉子結點xt與時間序列X后的所有Y序列進行匹配計算；

3)對xt與yi求loc_list，并判斷loc_count是否不小于min_supc：

①是，將loc_list作為yi的節點信息表，yi作為葉子節點，即xi。xi所在的樹枝節點構成頻繁項集，頻繁項數即為xi所在的樹層，項集個數即為loc_count。判斷Y是否為最后一條時間序列：

是，輸出頻繁K項集；

否，輸出頻繁K項集，重復2)、3)；

② 否，yi不是葉子節點，舍棄。

3 實例分析

設最小支持度計數min_supc為2，用趨勢項?位置表示的時間序列數據集data=[[{a1: (0, 2, 3, 5,7, 9),a2: (4, 6, 8),a3: (1)}],[{b1: (2, 3),b2: (0, 4, 5, 6, 8,9),b3: (1,7)}],[{c1: (3, 4, 6),c2: (2, 7),c3: (0, 1, 5, 8, 9)}]], data可視化結果如圖1所示，{b1: (2, 3)}表示趨勢項b1在第2和第3個時區內出現過。在構建同步頻繁樹前，需要先去除data中的非頻繁項。

圖1 實例數據可視化Fig.1 Visualization of an instance data

在data中，由于a3的數量僅為1，小于2，因此去掉此非頻繁項。根據SFT算法的挖掘步驟，利用首條時間序列[{a1: (0, 2, 3, 5, 7, 9),a2: (4, 6, 8) }]中的a1和a2項構建一棵基礎樹，如圖2所示。

圖2 基礎樹Fig.2 Base tree

葉子節點a1、a2分別與時間序列B和C中的項進行匹配計算，即[{b1: (2, 3),b2: (0, 4, 5, 6, 8, 9),b3: (1,7) }]和[{c1: (3, 4, 6),c2: (2, 7),c3: (0, 1, 5, 8,9) }]，結果如圖3所示。例如a1與b2的loc_list為(0,5,9)，即loc_count為3，因而b2成為葉子節點，其信息表為(0,5,9)，信息量為3，由于b2位于第2層樹，則a1b2是頻繁2項集，項集個數為3。而a1與b3的loc_list為(7)，即loc_count小于2，因此b3不是葉子節點。

圖3 同步頻繁樹的生長Fig.3 Growth process of synchronize frequent tree

由于C是最后一條時間序列，因此輸出圖3中的所有頻繁2項集：a1c2、a1c3、a2c1，其項集個數分別為2、3、2，但B并非最后一條時間序列，先輸出頻繁2項集a1b1、a1b2、a2c1、a2b2，再以同樣的思路將葉子節點b1、b2、b1與時間序列C中的項進行匹配計算，結果如圖4所示，由于葉子結點是最后一條時間序列中的項，因此一棵完整的同步頻繁樹構建完成，并輸出所有的頻繁3項集，即a1b2c3、a2b2c1。

圖4 完整的同步頻繁樹Fig.4 Complete synchronized frequent tree

4 數值實驗

為了驗證SFT算法具有普適性，使用零售商品數據和股票數據分別進行實驗。分別與基于時間序列事務集的Apriori[7]、FP-growth[14]、MapReduce[9-10]、BM_Apriori[9]以及WV_Apriori[13]算法的挖掘結果進行比較和分析，以檢驗SFT算法的有效性和性能。

4.1 數據介紹

零售商品數據是從UCI 網站下載的Online_Retail_II，取其中代號為20 725、20 727和20 728的銷售量。每條數據的時間在2010年12月2日?2011年12月9日，共225天，675個數據量。股票數據是從預測者網中獲取，冠城大通股票(600067)、中船科技股票(600072)和上汽集團股票(600104)的日收盤價，每支股票的時間在1997年12月25日?2021年3月4日，共5 343個工作日，16 029個數據量。為了獲取多條時間序列間的變化趨勢規則，需要先將每條時間序列分割成多個趨勢項，然后再借鑒文獻[23]的對齊思想將多條時間序列的趨勢項對齊。例如，在時區[0, 3]內，時間序列A的趨勢項是a1，而時間序列B在[0,1]和[1, 3]區間內的趨勢項為b1和b2，為了與B對齊，序列A的[0, 3]時區被分成[0,1]和[1, 3]，對應的趨勢項是a1、a1。本文使用的分割策略為基于滑動窗口的線性回歸，分割所得線段可以保留原數據的局部變化趨勢。以上汽集團股票數據為例，圖5是它的原始變化趨勢，圖6展示的是時間在2020年8月14日?2020年9月24日該支股票的數據分割過程，藍色表示原始時間序列，紅色表示分割后的局部擬合線段，表2則給出部分具體的原始數據。

表2 原始數據(上汽集團股票)Table 2 Raw data(Shangqi group)

圖5 上汽集團歷年的股票數據Fig.5 Stock data of Shangqi group over the years

圖6 時間序列線性分段(上汽集團股票)Fig.6 Linear segmentation of time series(Shangqi group)

4.2 時序數據關聯分析

本次實驗共分為2組，第1組使用商品銷售數據集，第2組使用股票數據集。實驗采用SFT算法，除了與經典算法Apriori和FP-growth進行比較外，實驗還給出了近年來提出并且具有較好性能的MapReduce、BM_Apriori和WV_Apriori算法的挖掘結果進行比較。由于近年來從時間序列角度研究商品銷售關聯性成為熱門方向[24-25]，因此本文將給出詳細的商品銷售數據挖掘結果，并用股票數據的部分結果說明新方法具有普適性。第1組實驗結果如圖7所示，圖7中展示了基于不同的min_supc，實驗算法和對比算法的頻繁2、3項集的個數。實驗表明，無論min_supc取什么值，這些算法的挖掘結果都是相同的，進而說明SFT方法能夠取得同樣精度的效果。

圖7 頻繁項集個數對比(商品數據)Fig.7 Comparison of frequent itemsets(commodity data)

為說明實驗結果的真實可靠性，圖8給出了當min_supc =12時，頻繁2項集的詳細數據。其中，陰影部分的數字表示滿足min_supc的頻繁項集個數，例如頻繁項集a1b1共有38個，非陰影部分的數字表示不滿足min_supc的項集個數，‘—’則表示該頻繁項集不存在，因為本文挖掘的是不同時間序列間的關聯關系，所以a1a2等不是要找的頻繁2項集。

圖8 頻繁2項集及其個數Fig.8 Frequent 2 itemsets and their number

鑒于FP-growth算法不能給出頻繁項集的支持度和置信度，而MapReduce、BM_Apriori和WV_Apriori是為挖掘頻繁項集而提出的算法，故本文僅給出SFT和Apriori算法所挖掘頻繁項集的支持度和置信度。當min_supc=12時，2個算法均給出如表3所示的結果，其中Rule表示規則，Sup表示支持度，Conf 表示置信度。以a1b1?c1為例，其表明增加購買20 725商品、20 727商品和20 728商品的規則數占總規則數的0.09；當都增加購買20 725和20 727時，20 728的購買量會增加的概率為0.57。

表3 SFT與Apriori算法挖掘關聯規則Table 3 Association rules mined by SFT and Apriori

為了說明SFT算法具有普適性，第2組實驗使用股票數據。由于挖掘步驟與第1組實驗相同，因此圖9直接給出挖掘結果，其表明6種算法的挖掘結果相同，因而說明SFT算法具有較強的普適性。

圖9 頻繁項集個數對比（股票數據）Fig.9 Comparison of frequent itemsets (stock data)

4.3 時間效率分析

時間效率是衡量算法好壞的重要指標之一。由于挖掘頻繁項集所耗時間占整個挖掘過程的多數時間，因此圖10給出6種算法在挖掘商品數據和股票數據頻繁項集時所消耗的時間可視化圖，表4是具體的數值結果。實驗表明，無論在數據量為675的商品數據，還是在數據量為16 029的股票數據，SFT算法的時間效率在不同最小支持計數的取值下都要優于其他算法，因而說明SFT算法具有較強的穩健性。

圖10 時間復雜度對比Fig.10 Comparison of time complexity-commodity data

表4 6種算法挖掘頻繁項集的時耗Table 4 Time consumption of six algorithms for mining frequent itemsets s

由圖10和表4的定量結果分析可知，SFT算法要優于其他5種對比算法，因而有必要從定性角度進一步分析實驗結果。本文認為影響SFT算法取得較好性能的主要因素有：1) 在生成頻繁K項集的過程中，SFT算法不會產生候選頻繁項集；2) SFT算法只需要對葉子節點和列表趨勢項求一次信息交集，即可快速判斷出頻繁K項集；3) 由1.2節分析得出，由趨勢項?位置表示的數據，其所占內存要遠低于事務集表示的數據，因而導致在程序運行過程中，SFT算法的處理速度要快于其他算法。

限于篇幅有限并且考慮到各類因素對不同算法的影響程度不同，因而對于每個對比算法，僅給出必要的分析和解釋：1) WV_Apriori算法在數據量較少的商品數據中，具有較好的時間效率，而在數據量較大的股票數據中，其時間效率明顯降低，表現出很差的穩健性。導致這種結果的原因：①在創建0-1矩陣的過程中，每項表示一列，每個事務表示一行，當數據量越來越大時，其創建的矩陣會越來越大，因而將會消耗更多的時間；②由于頻繁項集的挖掘是基于0-1矩陣，當矩陣很大時，除了遍歷矩陣需要較多的時間外，矩陣占用較多內存也會影響程序的運行速率；③ 由于WV_Apriori算法只需要遍歷一次數據庫，并且在挖掘更高的頻繁項集時，不斷縮小矩陣，因此當數據量較小時，其效率要高于Apriori、FPgrowth和MapReduce算法，正因為該算法需要遍歷完整個矩陣后才能判斷項間是否構成頻繁項集，因此其運行速率不及BM_Apriori和SFT算法。2) 由于BM_Apriori算法直接求2個頻繁K?1項之間的序號列表交集，即可快速找出它們之間的所有項集個數，但是該算法的基礎數據用事務集表示，因而在數據量較少的商品數據中，其時間效率要優于除了SFT算法以外的其他算法，然而在數據量較大的股票數據中，該算法會產生候選頻繁K項集，因而其時間效率略低于FP-growth算法。3) MapReduce算法通過合并具有相同鍵的頻繁K?1項集，即可快速產生候選頻繁K項集，因而其挖掘速率要快于Apriori算法，但是正因它還會產生較多的候選項集，因此導致其運行效率不及余下的其他算法。4) FPgrowth算法只需要掃描2次數據庫，并通過頭指針可以快速找到其他樹枝上的相同項，因而在數據量較大的股票數據中，其挖掘速率要優于除了SFT以外的其他算法，但是由于其挖掘的基礎數據用事務集表示，此外，在重新對事務集進行排序、構建FP-tree、提取條件模式基以及構建條件FP-tree過程中，消耗了較多時間，因此導致其運行速率不及SFT算法。5) 當最大頻繁項集是K時，Apriori算法需要掃描K次數據庫，并從大量候選頻繁項集中挖掘出頻繁K項集，因而導致其具有較低的挖掘速率。

表5分別從6個層面，概括總結6種算法的區別與聯系：除了SFT算法外，其他算法都是基于用事務集表示的數據；SFT和BM_Apriori算法分別用項的位置和事務的序號代替原數據，而其他算法僅僅是通過不同的方法表示保留原數據；SFT算法與FP-growth和WV_Apriori算法一樣不會產生候選頻繁項集；僅有SFT算法和BM_Apriori算法可以直接判斷頻繁K項集，而其他算法則需要遍歷完整個數據庫才能判斷；SFT和Apriori算法能給出頻繁項集的支持度與置信度，而其他算法不能；SFT算法與FP-growth、Mapreduce和BM_Apriori算法都能應用于大數據中。

表5 6種算法對比Table 5 Comparison of six algorithms

顯然，無論在定量分析還是定性分析中，SFT算法都要優于其他算法。

5 結束語

針對經典算法Apriori和FP-growth不適用于時間序列數據，提出了一種挖掘時間序列數據關聯規則的新方法，即SFT算法，并給出了近些年來提出的，且具有較好性能的MapReduce、BM_Apriori和WV_Apriori算法挖掘結果作對比。SFT算法的總體思路是先將時間序列數據用趨勢項?位置表示，再通過求葉子節點與列表項間的信息交集，進而可以快速挖掘出頻繁K項集。

本文具的創新點：1) 新定義的事務集表示法可以將多條時間序列數據轉換成事務集，該轉換法讓僅適用于挖掘無序數據的關聯規則算法也可以挖掘時間序列數據，此外還定義了趨勢項?位置表示法，用該方法表示的數據，其內存占用要低于原數據所占的內存，而內存占用情況會影響算法運行速率；2) SFT算法可以挖掘多條時間序列數據間的關聯規則，彌補了Apriori、FPgrowth等算法不適用于時間序列數據的缺點；3)通過計算樹葉子節點與列表項間的信息交集，便可快速判斷頻繁K項集，并且不會產生候選頻繁項集，因而提高了算法的挖掘速率；4) SFT算法充分利用時間序列具有一維性特點，并采用了直觀易懂的樹型結構，這為時間序列數據關聯分析的研究提供了一種新的研究思路和視角。實驗表明：1) 基于趨勢項?位置表示法表示的時間序列數據，其內存占用要遠低于用事務集表示的時間序列數據；2) 利用SFT算法挖掘出的頻繁項集與經典算法Apriori、FP-growth以及近些年來所提的，并且具有較好性能的MapReduce、BM_Apriori和WV_Apriori算法的挖掘結果相同；3) 無論在大數據還是小數據中，SFT算法的時間效率都要優于對比算法；4) 對于關聯規則，SFT算法給出的結果與Apriori的結果相同。

SFT算法具有較高較優的時間性能，使其有較強的普適性。然而，SFT算法只考慮到同時區內不同時間序列間的關聯關系，挖掘在不同時區內不同時間序列間的關聯關系，將是進一步需要研究的工作。