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

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

2、時(shí)，每一個(gè)項(xiàng)（IID）攜帶了它在數(shù)據(jù)庫中出現(xiàn)的位置記錄集合（TID），使得以后的操作可以脫離數(shù)據(jù)庫。3.構(gòu)造k-項(xiàng)集時(shí)，新的項(xiàng)目集合（ IID ）由兩個(gè)k-1項(xiàng)集的項(xiàng)目集合求并集得到，記錄號(hào)集合（ TID ）由兩個(gè)k-1項(xiàng)集的記錄號(hào)集合求交集得到。n缺點(diǎn)：消耗大量的內(nèi)存大型數(shù)據(jù)庫操作時(shí)會(huì)受到處理器內(nèi)存容量的限制，數(shù)據(jù)可能無法一次裝入。多元股票時(shí)間序列的關(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多元股票時(shí)間序列的關(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í)間序列合并集多元時(shí)間序列合并集：設(shè)時(shí)間序列的集合S=s1, s2, su， Ti 是在時(shí)刻i對(duì)S的觀察觀察值值集合，Ti=s1(i),s2(i),su(i)(1in)，多元時(shí)間序列合并集D定義為

4、：D=T1,T2,Tn。D中每組觀察值作為一個(gè)事務(wù)，各分配一個(gè)識(shí)別號(hào)TID。s1s2s3多元股票時(shí)間序列的關(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測(cè)試集中國(guó)證券市場(chǎng)19972001共五年間近500只股票的收盤價(jià)時(shí)間序列集（以下同）多元股票時(shí)間序列的關(guān)聯(lián)規(guī)則（3）n測(cè)試結(jié)果 中紡機(jī)和二紡機(jī)屬于典型的紡織機(jī)電企業(yè)，而陜長(zhǎng)嶺屬于家電企業(yè)，他們之間為什么會(huì)出現(xiàn)相同的下跌走勢(shì)呢？而且，用肉眼觀察

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

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

7、多元時(shí)間序列的跨事務(wù)關(guān)聯(lián)規(guī)則是形如XY的蘊(yùn)涵式，并且滿足以下條件：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ī)則有 個(gè)。625646362616CCCCC跨事務(wù)關(guān)聯(lián)規(guī)則的算法ES-Apriori（3）在計(jì)算這2條規(guī)則的置信度時(shí)，只需要搜索由A0構(gòu)造的頻繁項(xiàng)集空間，并不需要搜索由B0構(gòu)造的頻繁項(xiàng)集空間（不考慮連接時(shí)產(chǎn)生的重復(fù)項(xiàng)集）。因?yàn)檫@個(gè)6-項(xiàng)集的符合時(shí)間序列的跨事務(wù)關(guān)聯(lián)規(guī)則條件的所有X

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

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

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

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

12、NY跨事務(wù)關(guān)聯(lián)規(guī)則的算法ES-Apriori:算法性能比較nES-Apriori與E-Apriori算法的性能對(duì)比 由圖中可知，當(dāng)項(xiàng)數(shù)小于20k時(shí)，E-Apriori和ES-Apriori的執(zhí)行效率都很高。但是隨著數(shù)據(jù)的增加，E-Apriori的內(nèi)存使用量將急速增加，導(dǎo)致運(yùn)算時(shí)間驟然變長(zhǎng)；而ES-Apriori無論在內(nèi)存上還是在時(shí)間上都呈現(xiàn)平穩(wěn)增加的態(tài)勢(shì)。在試驗(yàn)中，當(dāng)總的項(xiàng)數(shù)大于30k后，E-Apriori會(huì)耗盡計(jì)算機(jī)內(nèi)存而無法繼續(xù)運(yùn)行；而ES-Apriori卻可以順利運(yùn)行。試驗(yàn)結(jié)論證明，分析較大數(shù)據(jù)量的多元時(shí)間序列的跨事務(wù)關(guān)聯(lián)規(guī)則時(shí)，ES-Apriori算法在時(shí)間/空間性能上要優(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將沿著時(shí)間方向，把在同一時(shí)間窗口內(nèi)的數(shù)據(jù)投影到同一事務(wù)內(nèi)。假設(shè)時(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ī)則分析:實(shí)驗(yàn)結(jié)果n我們定義了兩個(gè)區(qū)間，分別代表不同的事件。其中，漲幅（收盤價(jià)昨收盤價(jià)）（昨收盤價(jià)）大于1%的數(shù)值定義為“漲”事件，漲幅小于-1%的數(shù)值定義為“跌”事件。 中國(guó)鳳凰跌(0),儀征化纖跌(1),金杯汽車跌(1)-金杯汽車漲(2)(1.7

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

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

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

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