基于同步頻繁樹的時間序列關(guān)聯(lián)規(guī)則分析

李海林，龍芳菊

（1. 華僑大學(xué) 信息管理系，福建 泉州 362021; 2. 華僑大學(xué) 現(xiàn)代應(yīng)用統(tǒng)計(jì)與大數(shù)據(jù)研究中心，福建 廈門 361021）

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

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

1 時間序列特征表示

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

1.1 事務(wù)集表示法和趨勢項(xiàng)?位置表示法

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

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

1.2 性能比較與分析

顯然事務(wù)集表示法并沒有減少原數(shù)據(jù)量，而趨勢項(xiàng)?位置表示法只保留每個趨勢項(xiàng)，相同趨勢項(xiàng)則用位置索引代替。由于特征表示數(shù)據(jù)是各類算法挖掘工作的基礎(chǔ)，其對算法運(yùn)行效率具有很大影響，因此有必要從轉(zhuǎn)換時效和轉(zhuǎn)換后數(shù)據(jù)的內(nèi)存占用情況對上述2種表示法的性能進(jìn)行比較和分析。實(shí)驗(yàn)采用python程序?qū)⒑笪氖褂玫?條股票時間序列數(shù)據(jù)分別進(jìn)行事務(wù)集表示和趨勢項(xiàng)?位置表示，每條數(shù)據(jù)量為5 343，共16 029個數(shù)據(jù)。實(shí)驗(yàn)結(jié)果如表1所示。

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

從轉(zhuǎn)換時效方面，2種表示法處理的數(shù)據(jù)量相同，因而差異性不大；從內(nèi)存占用方面，由趨勢項(xiàng)?位置表示的數(shù)據(jù)要遠(yuǎn)低于事務(wù)集表示的數(shù)據(jù)，因?yàn)橼厔蓓?xiàng)?位置表示法以數(shù)值型(int)數(shù)據(jù)記錄趨勢項(xiàng)的變化趨勢，而事務(wù)集表示法則以字符型(str)數(shù)據(jù)記錄，由于int占用的內(nèi)存要低于str占用的內(nèi)存，因此用前者表示的數(shù)據(jù)，內(nèi)存占用情況要優(yōu)于后者。

2 同步頻繁樹

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

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

算法 SFT算法

輸入 data，min_supc；

輸出 頻繁K項(xiàng)集。

1)以Root為根，首條時間序列的所有項(xiàng)為xt，構(gòu)建一棵基礎(chǔ)樹；

2)讓所有葉子結(jié)點(diǎn)xt與時間序列X后的所有Y序列進(jìn)行匹配計(jì)算；

3)對xt與yi求loc_list，并判斷l(xiāng)oc_count是否不小于min_supc：

①是，將loc_list作為yi的節(jié)點(diǎn)信息表，yi作為葉子節(jié)點(diǎn)，即xi。xi所在的樹枝節(jié)點(diǎn)構(gòu)成頻繁項(xiàng)集，頻繁項(xiàng)數(shù)即為xi所在的樹層，項(xiàng)集個數(shù)即為loc_count。判斷Y是否為最后一條時間序列：

是，輸出頻繁K項(xiàng)集；

否，輸出頻繁K項(xiàng)集，重復(fù)2)、3)；

② 否，yi不是葉子節(jié)點(diǎn)，舍棄。

3 實(shí)例分析

設(shè)最小支持度計(jì)數(shù)min_supc為2，用趨勢項(xiàng)?位置表示的時間序列數(shù)據(jù)集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可視化結(jié)果如圖1所示，{b1: (2, 3)}表示趨勢項(xiàng)b1在第2和第3個時區(qū)內(nèi)出現(xiàn)過。在構(gòu)建同步頻繁樹前，需要先去除data中的非頻繁項(xiàng)。

圖1 實(shí)例數(shù)據(jù)可視化Fig.1 Visualization of an instance data

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

圖2 基礎(chǔ)樹Fig.2 Base tree

葉子節(jié)點(diǎn)a1、a2分別與時間序列B和C中的項(xiàng)進(jìn)行匹配計(jì)算，即[{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) }]，結(jié)果如圖3所示。例如a1與b2的loc_list為(0,5,9)，即loc_count為3，因而b2成為葉子節(jié)點(diǎn)，其信息表為(0,5,9)，信息量為3，由于b2位于第2層樹，則a1b2是頻繁2項(xiàng)集，項(xiàng)集個數(shù)為3。而a1與b3的loc_list為(7)，即loc_count小于2，因此b3不是葉子節(jié)點(diǎn)。

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

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

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

4 數(shù)值實(shí)驗(yàn)

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

4.1 數(shù)據(jù)介紹

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

表2 原始數(shù)據(jù)(上汽集團(tuán)股票)Table 2 Raw data(Shangqi group)

圖5 上汽集團(tuán)歷年的股票數(shù)據(jù)Fig.5 Stock data of Shangqi group over the years

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

4.2 時序數(shù)據(jù)關(guān)聯(lián)分析

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

圖7 頻繁項(xiàng)集個數(shù)對比(商品數(shù)據(jù))Fig.7 Comparison of frequent itemsets(commodity data)

為說明實(shí)驗(yàn)結(jié)果的真實(shí)可靠性，圖8給出了當(dāng)min_supc =12時，頻繁2項(xiàng)集的詳細(xì)數(shù)據(jù)。其中，陰影部分的數(shù)字表示滿足min_supc的頻繁項(xiàng)集個數(shù)，例如頻繁項(xiàng)集a1b1共有38個，非陰影部分的數(shù)字表示不滿足min_supc的項(xiàng)集個數(shù)，‘—’則表示該頻繁項(xiàng)集不存在，因?yàn)楸疚耐诰虻氖遣煌瑫r間序列間的關(guān)聯(lián)關(guān)系，所以a1a2等不是要找的頻繁2項(xiàng)集。

圖8 頻繁2項(xiàng)集及其個數(shù)Fig.8 Frequent 2 itemsets and their number

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

表3 SFT與Apriori算法挖掘關(guān)聯(lián)規(guī)則Table 3 Association rules mined by SFT and Apriori

為了說明SFT算法具有普適性，第2組實(shí)驗(yàn)使用股票數(shù)據(jù)。由于挖掘步驟與第1組實(shí)驗(yàn)相同，因此圖9直接給出挖掘結(jié)果，其表明6種算法的挖掘結(jié)果相同，因而說明SFT算法具有較強(qiáng)的普適性。

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

4.3 時間效率分析

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

SFT算法具有較高較優(yōu)的時間性能，使其有較強(qiáng)的普適性。然而，SFT算法只考慮到同時區(qū)內(nèi)不同時間序列間的關(guān)聯(lián)關(guān)系，挖掘在不同時區(qū)內(nèi)不同時間序列間的關(guān)聯(lián)關(guān)系，將是進(jìn)一步需要研究的工作。