多元時間序列中關(guān)聯(lián)規(guī)則的發(fā)現(xiàn)(PPT-28)

1、多元時間序列中關(guān)聯(lián)規(guī)則的發(fā)現(xiàn) 史忠植 董澤坤中國科學(xué)院計算技術(shù)研究所2022-3-6多元時間序列的關(guān)聯(lián)規(guī)則分析n關(guān)聯(lián)規(guī)則：關(guān)聯(lián)規(guī)則：設(shè) 是項的集合。任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合，其中每個事務(wù)T是項的集合， 。每個事務(wù)有一個標(biāo)識符，稱為TID。設(shè)A是一個項集，事務(wù)T包含A當(dāng)且僅當(dāng) 。關(guān)聯(lián)規(guī)則是形如 的蘊含式，其中, ， ， 。,.,21nIIII IT TA IT IA BAIB 關(guān)聯(lián)規(guī)則的算法OptimizedApriorin優(yōu)點：只讀取一次數(shù)據(jù)庫1.OptimizedApriori是在ArioriTid的基礎(chǔ)上，將數(shù)據(jù)結(jié)構(gòu)由變換為，從而迅速減少了系統(tǒng)的I/O操作。2.在構(gòu)造候選1-項集

2、時，每一個項（IID）攜帶了它在數(shù)據(jù)庫中出現(xiàn)的位置記錄集合（TID），使得以后的操作可以脫離數(shù)據(jù)庫。3.構(gòu)造k-項集時，新的項目集合（ IID ）由兩個k-1項集的項目集合求并集得到，記錄號集合（ TID ）由兩個k-1項集的記錄號集合求交集得到。n缺點：消耗大量的內(nèi)存大型數(shù)據(jù)庫操作時會受到處理器內(nèi)存容量的限制，數(shù)據(jù)可能無法一次裝入。多元股票時間序列的關(guān)聯(lián)規(guī)則（1）n數(shù)據(jù)預(yù)處理1.數(shù)值離散化 s1=3,4,3,2,4,2,0,3,4,4s2=2,3,2,3,3,4,3,1,1,4 s3=0,3,4,1,0,1,3,3,3,40(深跌)1(跌)2(平)3(漲)4(大漲)0 1 2 3 4 5 6

3、 7 8 9股票S1 股票S2 股票S3多元股票時間序列的關(guān)聯(lián)規(guī)則（1）TIDITEMS0s1.3,s2.2,s3.01s1.4,s2.3,s3.32s1.3,s2.2,s3.43s1.2,s2.3,s3.14s1.4,s2.3,s3.05s1.2,s2.4,s3.16s1.0,s2.3,s3.37s1.3,s2.1,s3.38s1.4,s2.1,s3.39s1.4,s2.4,s3.42.序列合并多元時間序列合并集多元時間序列合并集：設(shè)時間序列的集合S=s1, s2, su， Ti 是在時刻i對S的觀察觀察值值集合，Ti=s1(i),s2(i),su(i)(1in)，多元時間序列合并集D定義為

4、：D=T1,T2,Tn。D中每組觀察值作為一個事務(wù)，各分配一個識別號TID。s1s2s3多元股票時間序列的關(guān)聯(lián)規(guī)則（2）n規(guī)則挖掘 設(shè)：最小支持度20，最小信任度50% 規(guī)則：s1.3 s2.2:股票1漲股票2平(20%,66.7%):s1.4 s2.3:股票1大漲 股票2漲(20%,50%);s2.1 s3.3:股票2跌 股票3漲(20%,100%);n測試集中國證券市場19972001共五年間近500只股票的收盤價時間序列集（以下同）多元股票時間序列的關(guān)聯(lián)規(guī)則（3）n測試結(jié)果 中紡機和二紡機屬于典型的紡織機電企業(yè)，而陜長嶺屬于家電企業(yè)，他們之間為什么會出現(xiàn)相同的下跌走勢呢？而且，用肉眼觀察

5、實際走勢圖，它們之間的形態(tài)也有很大差距，這個現(xiàn)象如何解釋？在經(jīng)過仔細(xì)分析后，我們發(fā)現(xiàn)：陜長嶺中很大的一項主營業(yè)務(wù)是生產(chǎn)紡織機電。這項業(yè)務(wù)和紡織企業(yè)有著密切的聯(lián)系，這幾年間國家對紡織機電的政策也有大的調(diào)整。所以，這幾只股票的下跌走勢比較相同是有內(nèi)在聯(lián)系的。這種關(guān)系很難從實際走勢圖中識別，但是關(guān)聯(lián)分析做到了這一點。 中紡機1，陜長嶺1 二紡機1 (21.6%,84.1%)多元時間序列的跨事務(wù)關(guān)聯(lián)規(guī)則分析（1）n“跨事務(wù)”特性的特點： 強調(diào)的是出現(xiàn)在不同事務(wù)中各項目之間的關(guān)聯(lián)關(guān)系，應(yīng)用到時間序列中就是不同時刻各序列的數(shù)據(jù)特征之間的關(guān)系，如： A公司的股票在第一天上漲，B公司的股票在第二天下跌，那么，

6、C公司的股票會在第三天上漲。（s%,c%） 這種規(guī)則包含了時間特性，規(guī)則的前件可以用來作為后件的預(yù)測條件，它們的實際使用價值是很明顯的。多元時間序列的跨事務(wù)關(guān)聯(lián)規(guī)則分析（2）n多元時間序列的跨事務(wù)關(guān)聯(lián)規(guī)則多元時間序列的跨事務(wù)關(guān)聯(lián)規(guī)則： 設(shè)= e1(0),e1(w-1),e2(0), e2(w- 1) , ,eu(0), eu(w-1) 是事件的集合，這些事件是多元時間序列合并集D中各序列觀察值的屬性，w是D的滑動時間窗口滑動時間窗口。以時刻s (1sn-w+1)為D的參考時間基準(zhǔn)點，如果時刻s+x (0 xw-1)此事件出現(xiàn)，則標(biāo)記ei(x) 屬于Ts。每一個 ei(x)分配一個識別號IID。

7、多元時間序列的跨事務(wù)關(guān)聯(lián)規(guī)則是形如XY的蘊涵式，并且滿足以下條件：1.X,Y;2.ei(0)X, 1iu;3.ej(q)X, 1ju,(i=j)(1qw-1)(ij)(0qw-1);4.ei(p)Y, 1iu, max(q) A1,A2, B1,B2;A0, A1,B0, B1-A2, B2。而傳統(tǒng)關(guān)聯(lián)規(guī)則可能產(chǎn)生的規(guī)則有 個。625646362616CCCCC跨事務(wù)關(guān)聯(lián)規(guī)則的算法ES-Apriori（3）在計算這2條規(guī)則的置信度時，只需要搜索由A0構(gòu)造的頻繁項集空間，并不需要搜索由B0構(gòu)造的頻繁項集空間（不考慮連接時產(chǎn)生的重復(fù)項集）。因為這個6-項集的符合時間序列的跨事務(wù)關(guān)聯(lián)規(guī)則條件的所有X

8、子集只有A0, B0、A0, A1,B0, B1，這兩項都是在A0的基礎(chǔ)上構(gòu)造產(chǎn)生的。同理 ， 5 項 集 B 0 , A1,A2,B1, B2的X子集B0、B0, A1, B1只須搜索由B0構(gòu)造的頻繁項集空間?？缡聞?wù)關(guān)聯(lián)規(guī)則的算法ES-Apriori（4）n從上面的分析得出，挖掘所有規(guī)則可以分成u步運行：每步只構(gòu)造包含ei(0)|( 1iu)的頻繁項集，挖掘相應(yīng)的的關(guān)聯(lián)規(guī)則。這樣，一次調(diào)入內(nèi)存的數(shù)據(jù)可降低為全部調(diào)入的1/u，當(dāng)有大量數(shù)據(jù)項參與運算時，此方法也能順利運行。nES-Apriori算法分割了頻繁項集空間，降低了一次調(diào)入內(nèi)存的數(shù)據(jù)量，從而緩解了因數(shù)據(jù)爆炸而耗盡內(nèi)存的問題。n為能夠快速

9、便捷的讀取跨事務(wù)關(guān)聯(lián)規(guī)則X子集的支持度計數(shù)值，我們設(shè)計了一顆動態(tài)樹來保存頻繁項集。用每一個節(jié)點表示一個項ei(x)，由樹的根節(jié)點出發(fā)所形成的數(shù)枝上所有的節(jié)點就代表一個頻繁k-項集，而樹枝的終點記載了這個頻繁項集的支持度計數(shù)值。 跨事務(wù)關(guān)聯(lián)規(guī)則的算法ES-Apriori（5）:構(gòu)造動態(tài)樹以基本項A和B，滑動時間窗口為3的數(shù)據(jù)庫為例，構(gòu)造一顆6層（最長的關(guān)聯(lián)規(guī)則包括6項）共有32個節(jié)點的動態(tài)樹。 首先，建立節(jié)點1（A0），作為第一層節(jié)點；第二項A0A1有兩項，需要新建第二層鏈表，作為子節(jié)點直接添加到節(jié)點2；因為第三項A0A2與A0A1同屬于第二層，作為A0A1的兄弟節(jié)點，加入到第二層鏈表中；同理，

10、A0B0、A0B1、A0B2都屬于第二層，都加入到第二層鏈表中。由于第二層節(jié)點的父節(jié)點只有節(jié)點1，所以第二層只需要一個鏈表。從第三層開始，每一個新節(jié)點可能屬于不同的父節(jié)點，所以他們會被添加到不同的各自父節(jié)點的子節(jié)點鏈表中。例如，節(jié)點11（代表頻繁項集A0A2B0）的父節(jié)點是節(jié)點3（代表頻繁項集A0A2），所以被加入到節(jié)點3的子節(jié)點鏈表中。以此類推，所有的節(jié)點都被添加到動態(tài)樹中。 跨事務(wù)關(guān)聯(lián)規(guī)則的算法ES-Apriori（6）:查詢動態(tài)樹 當(dāng)分解頻繁項集為X子集和Y子集時，需要讀取X子集的支持度計數(shù)值，從而計算X Y的支持度。這一搜索過程可以在構(gòu)造的動態(tài)樹中快速實現(xiàn)。例如，我們需要得到頻繁項A0

11、A2B0B1B2中X子集A0B0B1的支持度計數(shù)值，只需要循著節(jié)點1（A0）轉(zhuǎn)到第二層鏈表，由節(jié)點2開始順序搜索節(jié)點找到節(jié)點4（B0B0），轉(zhuǎn)入節(jié)點4的子節(jié)點鏈表，找到節(jié)點14（B1），讀出它的支持度計數(shù)值。在整個搜索過程中，只需要經(jīng)過5個節(jié)點，這樣的速度要比搜索鏈表高出若干倍，也要比Hash表技術(shù)快。在設(shè)計中，將已經(jīng)計算過信任度的頻繁項集節(jié)點直接銷毀，能夠減少訪問空間，進一步加快搜索速度。 ES-Apriori算法流程圖項名稱映射,交易號映射開始載入數(shù)據(jù)數(shù)據(jù)全部載入?N掃描數(shù)據(jù)庫，獲得1-項集（L1）L1項的滑動窗口值是否為0？構(gòu)造2-項集構(gòu)造k-項集構(gòu)造動態(tài)樹輸出規(guī)則是否還有L1？結(jié)束YN

12、NY跨事務(wù)關(guān)聯(lián)規(guī)則的算法ES-Apriori:算法性能比較nES-Apriori與E-Apriori算法的性能對比 由圖中可知，當(dāng)項數(shù)小于20k時，E-Apriori和ES-Apriori的執(zhí)行效率都很高。但是隨著數(shù)據(jù)的增加，E-Apriori的內(nèi)存使用量將急速增加，導(dǎo)致運算時間驟然變長；而ES-Apriori無論在內(nèi)存上還是在時間上都呈現(xiàn)平穩(wěn)增加的態(tài)勢。在試驗中，當(dāng)總的項數(shù)大于30k后，E-Apriori會耗盡計算機內(nèi)存而無法繼續(xù)運行；而ES-Apriori卻可以順利運行。試驗結(jié)論證明，分析較大數(shù)據(jù)量的多元時間序列的跨事務(wù)關(guān)聯(lián)規(guī)則時，ES-Apriori算法在時間/空間性能上要優(yōu)于E-Apr

13、iori算法。多元股票序列的跨事務(wù)關(guān)聯(lián)規(guī)則分析:數(shù)據(jù)預(yù)處理1.離散化： 2.序列合并s1=3,4,3,2,4,2,0,3,4,4s2=2,3,2,3,3,4,3,1,1,4 s3=0,3,4,1,0,1,3,3,3,43.數(shù)據(jù)投影 合并集D將沿著時間方向，把在同一時間窗口內(nèi)的數(shù)據(jù)投影到同一事務(wù)內(nèi)。假設(shè)時間窗口值為3，則TID=0的事務(wù)為： T=s1.3(0),s2.2(0),s3.0(0),s1.4(1),s2.3(1),s3.3(1),s1.3(2),s2.2(2),s3.4(2)0(深跌)1(跌)2(平)3(漲)4(大漲)0 1 2 3 4 5 6 7 8 9股票S1 股票S2 股票S3T

14、IDITEMS0s1.3,s2.2,s3.01s1.4,s2.3,s3.32s1.3,s2.2,s3.43s1.2,s2.3,s3.14s1.4,s2.3,s3.05s1.2,s2.4,s3.16s1.0,s2.3,s3.37s1.3,s2.1,s3.38s1.4,s2.1,s3.39s1.4,s2.4,s3.4s1s2s3多元股票序列的跨事務(wù)關(guān)聯(lián)規(guī)則分析:實驗結(jié)果n我們定義了兩個區(qū)間，分別代表不同的事件。其中，漲幅（收盤價昨收盤價）（昨收盤價）大于1%的數(shù)值定義為“漲”事件，漲幅小于-1%的數(shù)值定義為“跌”事件。 中國鳳凰跌(0),儀征化纖跌(1),金杯汽車跌(1)-金杯汽車漲(2)(1.7

15、%,83%)多元時間序列的頻繁片斷模式關(guān)聯(lián)規(guī)則分析n分析多元時間序列中采樣值之間的關(guān)聯(lián)規(guī)則，必須預(yù)先將這些數(shù)值映射到一定的區(qū)間，以降低數(shù)據(jù)之間的差異程度。這樣才能在一個較小的空間，分析有限的事件之間的關(guān)聯(lián)規(guī)則。否則，數(shù)據(jù)的多值性將導(dǎo)致產(chǎn)生太多的候選項而引發(fā)數(shù)據(jù)爆炸。n另一種克服數(shù)據(jù)多值性的方法是，將時間序列的片段映射為一個與其相似的片段，將這些數(shù)值數(shù)據(jù)轉(zhuǎn)化為“模式”，并用一個有代表性的片段代替序列中與其相似的片段。這樣，數(shù)值數(shù)據(jù)的空間就可以降低到關(guān)聯(lián)規(guī)則分析可以接受的范圍。n我們將使用聚類的方法搜索時間序列中的頻繁“模式”，并用這些模式代替時間序列中與其相似的片段，近而在經(jīng)過模式匹配的多元時間

16、序列中挖掘關(guān)聯(lián)規(guī)則。時間序列的相似性度量DTW距離nDTW：Dynamic Time Warping 動態(tài)時間歸整（或動態(tài)時間彎折），這項技術(shù)已經(jīng)在語音識別上使用了很多年，在1994年，由Berndt和Clifford首先應(yīng)用到數(shù)據(jù)挖掘中。n不同序列的相似性可以通過計算它們之間的歐幾里得距離來衡量，但是這種方法對序列在時間軸上相近數(shù)值的提前或推后出現(xiàn)會產(chǎn)生較大的誤差。在用歐幾里得距離和DTW距離分別計算四個序列的相似度，然后再對它們聚類，結(jié)果如下： 四個時間序列的聚類：歐幾里得距離 DTW距離動態(tài)時間規(guī)整DTW (1)n假設(shè)我們有兩個時間序列Q和C,長度分別是n和m，n為了用DTW排列這兩個序

17、列，我們構(gòu)造一個（n,m）的矩陣，第(i,j)單元記錄兩個點qi和ci之間的歐幾里得距離。一條彎折的路徑W，是由若干個彼此相連的矩陣單元構(gòu)成，這條路經(jīng)描述了Q和C之間的一種映射。設(shè)第k個單元定義為wk=(i,j)k, 則n這條彎折的路徑服從許多限制：1. 邊界條件 且這條路徑必須由第一個單元經(jīng)過矩陣到達最后一個單元。2. 連續(xù)性 設(shè) ，那么， 。這個條件限制了允許的每一個彎折步必須彼此相鄰。（包括對角線單元）3. 單調(diào)性 設(shè) ，那么， 。 這個條件限制了W中的點在時間上的不能回退。 Kkwwwww,.,.,21nmKnm),max() 1 , 1 (1w),(mnwK),(),(1bawbaw

18、kk1, 1bbaa),(),(1bawbawkk0, 0bbaa動態(tài)時間規(guī)整DTW (2)n滿足上述條件的路徑數(shù)的是指數(shù)級的，然而，我們只關(guān)心整個路徑中最短的、消費最少的一條路經(jīng)KwCQDTWkkk1min),(圖中的兩個序列之間的DTW距離，可以通過動態(tài)規(guī)劃的方法找到一條最短的路經(jīng)。這里，每個序列采12個點，點點距離構(gòu)成（12,12）的矩陣。首先初始化矩陣的每一個單元的局部距離 ，通過下面的循環(huán)，累計距離 就等于當(dāng)前單元的局部距離 和相鄰單元中的最短累計距離相加。這樣，計算到最后一個點的時侯，一條最短路徑就得了出來。 jicqjid),(),(ji),(jid)1,(), 1(),1, 1(min),(),(jijijijidji頻繁片段模式關(guān)聯(lián)規(guī)則分析：挖掘頻繁片段模式n為了能夠?qū)r間序列中不同片段的模式進行關(guān)聯(lián)規(guī)則分析，需要對時間序列中相近的片段序列（子序列）分類。在這里我們不采用由相關(guān)領(lǐng)域?qū)＜姨峁┑男蛄心０遄鳛榉诸悩?biāo)準(zhǔn)，而是直接從序列中“提煉”。這一過程需要用到有關(guān)聚類（clustering）的方法。n在時間序列中，定義一個滑動時間窗口，窗口的大小w等于模式的長度pattern_length。將滑動時間窗口應(yīng)用到序列s中，沿著時間的方向，每個窗口內(nèi)的子序列定義一個標(biāo)識，然后對于所有的n-w+1個子序列聚類。在這里，我們只需要搜集頻繁出現(xiàn)的子序列（或片段），而