多元時(shí)間序列中-智能科學(xué)與人工智能網(wǎng)站ppt課件

1、多元時(shí)間序列中關(guān)聯(lián)規(guī)那么的發(fā)現(xiàn) 史忠植 董澤坤中國(guó)科學(xué)院計(jì)算技術(shù)研討所2022/3/13多元時(shí)間序列的關(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)含式，其中, ， ， 。關(guān)聯(lián)規(guī)那么的算法OptimizedApriori優(yōu)點(diǎn)：只讀取一次數(shù)據(jù)庫OptimizedApriori是在ArioriTid的根底上，將數(shù)據(jù)構(gòu)造由變換為，從而迅速減少了系統(tǒng)的I/O操作。在構(gòu)造候選1-項(xiàng)集時(shí)，每一個(gè)項(xiàng)IID攜帶了它在數(shù)據(jù)庫中出現(xiàn)的位置記錄集合TID，使得

2、以后的操作可以脫離數(shù)據(jù)庫。構(gòu)造k-項(xiàng)集時(shí)，新的工程集合 IID 由兩個(gè)k-1項(xiàng)集的工程集合求并集得到，記錄號(hào)集合 TID 由兩個(gè)k-1項(xiàng)集的記錄號(hào)集合求交集得到。缺陷：耗費(fèi)大量的內(nèi)存大型數(shù)據(jù)庫操作時(shí)會(huì)受四處置器內(nèi)存容量的限制，數(shù)據(jù)能夠無法一次裝入。多元股票時(shí)間序列的關(guān)聯(lián)規(guī)那么1數(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 7 8 9股票S1 股票S2 股票S3多元股票時(shí)間序列的關(guān)聯(lián)規(guī)那么1TIDITEMS0s1

3、.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í)間序列的集合S=s1, s2, su， Ti 是在時(shí)辰i對(duì)S的察看值集合，Ti=s1(i),s2(i),su(i)(1in)，多元時(shí)間序列合并集D定義為：D=T1,T2,Tn。D中每組察看值作為一個(gè)事務(wù)，各分配一個(gè)識(shí)別號(hào)TID。s1s2s3多元股票時(shí)間序列的關(guān)聯(lián)規(guī)那么2

4、規(guī)那么發(fā)掘 設(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%);測(cè)試集中國(guó)證券市場(chǎng)19972001共五年間近500只股票的收盤價(jià)時(shí)間序列集以下同多元股票時(shí)間序列的關(guān)聯(lián)規(guī)那么3測(cè)試結(jié)果 中紡機(jī)和二紡機(jī)屬于典型的紡織機(jī)電企業(yè)，而陜長(zhǎng)嶺屬于家電企業(yè)，他們之間為什么會(huì)出現(xiàn)一樣的下跌走勢(shì)呢？而且，用肉眼察看實(shí)踐走勢(shì)圖，它們之間的形狀也有很大差距，這個(gè)景象如何解釋？在經(jīng)過仔細(xì)分析后，我們發(fā)現(xiàn)：陜長(zhǎng)嶺中很大的一項(xiàng)主營(yíng)業(yè)務(wù)是消費(fèi)紡織機(jī)電。

5、這項(xiàng)業(yè)務(wù)和紡織企業(yè)有著親密的聯(lián)絡(luò)，這幾年間國(guó)家對(duì)紡織機(jī)電的政策也有大的調(diào)整。所以，這幾只股票的下跌走勢(shì)比較一樣是有內(nèi)在聯(lián)絡(luò)的。這種關(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“跨事務(wù)特性的特點(diǎn)： 強(qiáng)調(diào)的是出如今不同事務(wù)中各工程之間的關(guān)聯(lián)關(guān)系，運(yùn)用到時(shí)間序列中就是不同時(shí)辰各序列的數(shù)據(jù)特征之間的關(guān)系，如： A公司的股票在第一天上漲，B公司的股票在第二天下跌，那么，C公司的股票會(huì)在第三天上漲。s%,c% 這種規(guī)那么包含了時(shí)間特性，規(guī)那么的前件可以用來作為后件的預(yù)測(cè)條件，它們的實(shí)踐運(yùn)用價(jià)值是很明顯的

6、。多元時(shí)間序列的跨事務(wù)關(guān)聯(lián)規(guī)那么分析2多元時(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í)間窗口。以時(shí)辰s (1sn-w+1)為D的參考時(shí)間基準(zhǔn)點(diǎn)，假設(shè)時(shí)辰s+x (0 xw-1)此事件出現(xiàn)，那么標(biāo)志ei(x) 屬于Ts。每一個(gè) ei(x)分配一個(gè)識(shí)別號(hào)IID。多元時(shí)間序列的跨事務(wù)關(guān)聯(lián)規(guī)那么是形如XY的蘊(yùn)涵式，并且滿足以下條件：X,Y;ei(0)X, 1iu;ej(q)X, 1ju,(i=j)(1qw-1)(ij)(0qw-1);e

7、i(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è)?？缡聞?wù)關(guān)聯(lián)規(guī)那么的算法ES-Apriori3在計(jì)算這2條規(guī)那么的置信度時(shí)，只需求搜索由A0構(gòu)造的頻繁項(xiàng)集空間，并不需求搜索由B0構(gòu)造的頻繁項(xiàng)集空間不思索銜接時(shí)產(chǎn)生的反復(fù)項(xiàng)集。由于這個(gè)6-項(xiàng)集的符合時(shí)間序列的跨事務(wù)關(guān)聯(lián)規(guī)那么條件的一切X子集只需A0, B0、A0, A1,B0, B1，這兩項(xiàng)都是在A0的根底上構(gòu)造產(chǎn)生的。同理，5項(xiàng)集B0, A1,A2,B1, B2的X子集B0、B0, A1, B1只須搜索由B0構(gòu)造的頻繁項(xiàng)集空間?？缡聞?wù)關(guān)聯(lián)規(guī)那么的算法

8、ES-Apriori4從上面的分析得出，發(fā)掘一切規(guī)那么可以分成u步運(yùn)轉(zhuǎn)：每步只構(gòu)造包含ei(0)|( 1iu)的頻繁項(xiàng)集，發(fā)掘相應(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)轉(zhuǎn)。ES-Apriori算法分割了頻繁項(xiàng)集空間，降低了一次調(diào)入內(nèi)存的數(shù)據(jù)量，從而緩解了因數(shù)據(jù)爆炸而耗盡內(nèi)存的問題。為可以快速便利的讀取跨事務(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ā)所構(gòu)成的數(shù)枝上一切的節(jié)點(diǎn)就代表一個(gè)頻繁k-項(xiàng)集，而樹枝的終點(diǎn)記載了這個(gè)頻繁項(xiàng)集的支持度計(jì)數(shù)值。 跨事務(wù)關(guān)

9、聯(lián)規(guī)那么的算法ES-Apriori5:構(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)1A0，作為第一層節(jié)點(diǎn)；第二項(xiàng)A0A1有兩項(xiàng)，需求新建第二層鏈表，作為子節(jié)點(diǎn)直接添加到節(jié)點(diǎn)2；由于第三項(xiàng)A0A2與A0A1同屬于第二層，作為A0A1的兄弟節(jié)點(diǎn)，參與到第二層鏈表中；同理，A0B0、A0B1、A0B2都屬于第二層，都參與到第二層鏈表中。由于第二層節(jié)點(diǎn)的父節(jié)點(diǎn)只需節(jié)點(diǎn)1，所以第二層只需求一個(gè)鏈表。從第三層開場(chǎng)，每一個(gè)新節(jié)點(diǎn)能夠?qū)儆诓煌母腹?jié)點(diǎn)，所以他們會(huì)被添加到不同的各自父節(jié)點(diǎn)的子節(jié)點(diǎn)鏈表中。例如，節(jié)點(diǎn)11代表頻繁

10、項(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-Apriori6:查詢動(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)A0A2B0B1B2中X子集A0B0B1的支持度計(jì)數(shù)值，只需求循著節(jié)點(diǎn)1A0轉(zhuǎn)到第二層鏈表，由節(jié)點(diǎn)2開場(chǎng)順序搜索節(jié)點(diǎn)找到節(jié)點(diǎn)4B0，轉(zhuǎn)入節(jié)點(diǎn)4的子節(jié)點(diǎn)鏈表，找到節(jié)點(diǎn)14B1，讀出它的支持度計(jì)數(shù)值。在整個(gè)搜索過程中，只需求經(jīng)過5個(gè)節(jié)點(diǎn)，這樣的速度要比搜索鏈表高

11、出假設(shè)干倍，也要比Hash表技術(shù)快。在設(shè)計(jì)中，將曾經(jīng)計(jì)算過信任度的頻繁項(xiàng)集節(jié)點(diǎn)直接銷毀，可以減少訪問空間，進(jìn)一步加快搜索速度。 ES-Apriori算法流程圖項(xiàng)稱號(hào)映射,買賣號(hào)映射開場(chǎng)載入數(shù)據(jù)數(shù)據(jù)全部載入?N掃描數(shù)據(jù)庫，獲得1-項(xiàng)集L1L1項(xiàng)的滑動(dòng)窗口值能否為0？構(gòu)造2-項(xiàng)集構(gòu)造k-項(xiàng)集構(gòu)造動(dòng)態(tài)樹輸出規(guī)那么能否還有L1？終了YNNY跨事務(wù)關(guān)聯(lián)規(guī)那么的算法ES-Apriori:算法性能比較ES-Apriori與E-Apriori算法的性能對(duì)比 由圖中可知，當(dāng)項(xiàng)數(shù)小于20k時(shí)，E-Apriori和ES-Apriori的執(zhí)行效率都很高。但是隨著數(shù)據(jù)的添加，E-Apriori的內(nèi)存運(yùn)用量將急速添加，導(dǎo)

12、致運(yùn)算時(shí)間驟然變長(zhǎng)；而ES-Apriori無論在內(nèi)存上還是在時(shí)間上都呈現(xiàn)平穩(wěn)添加的態(tài)勢(shì)。在實(shí)驗(yàn)中，當(dāng)總的項(xiàng)數(shù)大于30k后，E-Apriori會(huì)耗盡計(jì)算機(jī)內(nèi)存而無法繼續(xù)運(yùn)轉(zhuǎn)；而ES-Apriori卻可以順利運(yùn)轉(zhuǎn)。實(shí)驗(yàn)結(jié)論證明，分析較大數(shù)據(jù)量的多元時(shí)間序列的跨事務(wù)關(guān)聯(lián)規(guī)那么時(shí)，ES-Apriori算法在時(shí)間/空間性能上要優(yōu)于E-Apriori算法。多元股票序列的跨事務(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í)

13、間窗口內(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 股票S3TIDITEMS0s1.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

14、,s2.1,s3.39s1.4,s2.4,s3.4s1s2s3多元股票序列的跨事務(wù)關(guān)聯(lián)規(guī)那么分析:實(shí)驗(yàn)結(jié)果我們定義了兩個(gè)區(qū)間，分別代表不同的事件。其中，漲幅收盤價(jià)昨收盤價(jià)昨收盤價(jià)大于1%的數(shù)值定義為“漲事件，漲幅小于-1%的數(shù)值定義為“跌事件。 中國(guó)鳳凰跌(0),儀征化纖跌(1),金杯汽車跌(1)-金杯汽車漲(2)(1.7%,83%)多元時(shí)間序列的頻繁片斷方式關(guān)聯(lián)規(guī)那么分析分析多元時(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ù)爆炸。另一

15、種抑制數(shù)據(jù)多值性的方法是，將時(shí)間序列的片段映射為一個(gè)與其類似的片段，將這些數(shù)值數(shù)據(jù)轉(zhuǎn)化為“方式，并用一個(gè)有代表性的片段替代序列中與其類似的片段。這樣，數(shù)值數(shù)據(jù)的空間就可以降低到關(guān)聯(lián)規(guī)那么分析可以接受的范圍。我們將運(yùn)用聚類的方法搜索時(shí)間序列中的頻繁“方式，并用這些方式替代時(shí)間序列中與其類似的片段，近而在經(jīng)過方式匹配的多元時(shí)間序列中發(fā)掘關(guān)聯(lián)規(guī)那么。時(shí)間序列的類似性度量DTW間隔DTW：Dynamic Time Warping 動(dòng)態(tài)時(shí)間歸整或動(dòng)態(tài)時(shí)間彎折，這項(xiàng)技術(shù)曾經(jīng)在語音識(shí)別上運(yùn)用了很多年，在1994年，由Berndt和Clifford首先運(yùn)用到數(shù)據(jù)發(fā)掘中。不同序列的類似性可以經(jīng)過計(jì)算它們之間的歐

16、幾里得間隔來衡量，但是這種方法對(duì)序列在時(shí)間軸上相近數(shù)值的提早或推后出現(xiàn)會(huì)產(chǎn)生較大的誤差。在用歐幾里得間隔和DTW間隔分別計(jì)算四個(gè)序列的類似度，然后再對(duì)它們聚類，結(jié)果如下： 四個(gè)時(shí)間序列的聚類：歐幾里得間隔 DTW間隔動(dòng)態(tài)時(shí)間規(guī)整DTW (1)假設(shè)我們有兩個(gè)時(shí)間序列Q和C,長(zhǎng)度分別是n和m，為了用DTW陳列這兩個(gè)序列，我們構(gòu)造一個(gè)n,m的矩陣，第(i,j)單元記錄兩個(gè)點(diǎn)qi和ci之間的歐幾里得間隔。一條彎折的途徑W，是由假設(shè)干個(gè)彼此相連的矩陣單元構(gòu)成，這條路經(jīng)描畫了Q和C之間的一種映射。設(shè)第k個(gè)單元定義為wk=(i,j)k, 那么這條彎折的途徑服從許多限制：1. 邊境條件 且這條途徑必需由第一個(gè)

17、單元經(jīng)過矩陣到達(dá)最后一個(gè)單元。2. 延續(xù)性 設(shè) ，那么， 。這個(gè)條件限制了允許的每一個(gè)彎折步必需彼此相鄰。包括對(duì)角線單元3. 單調(diào)性 設(shè) ，那么， 。 這個(gè)條件限制了W中的點(diǎn)在時(shí)間上的不能回退。 動(dòng)態(tài)時(shí)間規(guī)整DTW (2)滿足上述條件的途徑數(shù)的是指數(shù)級(jí)的，然而，我們只關(guān)懷整個(gè)途徑中最短的、消費(fèi)最少的一條路經(jīng)圖中的兩個(gè)序列之間的DTW間隔，可以經(jīng)過動(dòng)態(tài)規(guī)劃的方法找到一條最短的路經(jīng)。這里，每個(gè)序列采12個(gè)點(diǎn)，點(diǎn)點(diǎn)間隔構(gòu)成12,12的矩陣。首先初始化矩陣的每一個(gè)單元的部分間隔 ，經(jīng)過下面的循環(huán)，累計(jì)間隔 就等于當(dāng)前單元的部分間隔 和相鄰單元中的最短累計(jì)間隔相加。這樣，計(jì)算到最后一個(gè)點(diǎn)的時(shí)侯，一條最短

18、途徑就得了出來。 頻繁片段方式關(guān)聯(lián)規(guī)那么分析：發(fā)掘頻繁片段方式為了可以對(duì)時(shí)間序列中不同片段的方式進(jìn)展關(guān)聯(lián)規(guī)那么分析，需求對(duì)時(shí)間序列中相近的片段序列子序列分類。在這里我們不采用由相關(guān)領(lǐng)域?qū)＜姨峁┑男蛄心０遄鳛榉诸愐?guī)范，而是直接從序列中“提煉。這一過程需求用到有關(guān)聚類clustering的方法。在時(shí)間序列中，定義一個(gè)滑動(dòng)時(shí)間窗口，窗口的大小w等于方式的長(zhǎng)度pattern_length。將滑動(dòng)時(shí)間窗口運(yùn)用到序列s中，沿著時(shí)間的方向，每個(gè)窗口內(nèi)的子序列定義一個(gè)標(biāo)識(shí)，然后對(duì)于一切的n-w+1個(gè)子序列聚類。在這里，我們只需求搜集頻繁出現(xiàn)的子序列或片段，而個(gè)別景象將不再討論關(guān)聯(lián)分析只關(guān)懷頻繁項(xiàng)之間的規(guī)那么，這樣可以降低