時間序列和序列模式挖掘-Read課件

第六章時間序列和序列模式挖掘信息與計算科學系2009年4月第六章時間序列和序列模式挖掘1概述時間序列：將某一指標在不同時間上的不同數值，按照時間的先后順序排列而成的數列時間序列挖掘通過研究信息的時間特性，深入洞悉事務進化的機制，成為獲得知識的有效途徑序列挖掘挖掘從序列數據庫中發(fā)現相對時間或其它順序所出現的高頻率子序列概述時間序列：26.1時間序列及其應用時間序列挖掘就是從大量的時間序列數據中提取人民事先不知道的、但又是潛在有用的與時間屬性相關的信息和知識，并用于短期、中期或長期預測，指導人們的社會、經濟、軍事和生活等行為時間序列的研究必須依據合適的理論和技術進行，相應的建模方法也不同：一元時間序列：可以通過單變量隨機過程的觀察獲得規(guī)律性信息；多元時間序列：通過多變量描述變化規(guī)律離散型時間序列：序列中的每一個序列值所對應的時間參數為間斷點連續(xù)型時間序列：序列中的每個序列值所對應的時間參數為連續(xù)函數序列的分布規(guī)律：序列的統(tǒng)計特征可表現平穩(wěn)或有規(guī)律震蕩，從而為序列分析提供理論根據6.1時間序列及其應用時間序列挖掘就是從大量的時間序列數據36.2時間序列預測的常用方法確定性時間序列預測方法對于平穩(wěn)變化特征的時間序列，其未來行為與現在的行為有關，利用屬性現在的值預測將來的值是可行的一種更科學的評價方法：將數據的變動看成是長期趨勢、季節(jié)變動和隨機型變動共同作用的結果長期變動：歲時間變化的、按照某種規(guī)則穩(wěn)步增長、下降或保持在某一水平上的規(guī)律；季節(jié)變動：在一定時間內的周期性變化規(guī)律隨機型變動：不可控的偶然因素等時間序列分析就是設法消除隨機型波動、分解季節(jié)性變化、擬合確定型趨勢確定性時間序列預測技術可以控制時間序列變動的基本樣式6.2時間序列預測的常用方法確定性時間序列預測方法46.3基于ARMA模型的序列匹配方法基本概念ARMA模型對于平穩(wěn)、正態(tài)、零均值的時序X={xt|t=0,1,…,n-1}，若X在t時刻的取值不僅與其前n步的各個值xt-1,xt-2,…,xt-n有關，且還與前m步的各個干擾at-1,at-2,…,at-m有關，則按多元線性回歸的思想，得到最一般的ARMA(n,m)模型：6.3基于ARMA模型的序列匹配方法基本概念56.3基于ARMA模型的序列匹配方法(cont.)AR模型(自回歸模型)MA模型(m階滑動平均模型)6.3基于ARMA模型的序列匹配方法(cont.)AR模型6利用基本概念建立模型對于AR模型，有可用以下線性方程組表示：或寫為參數矩陣可用最小二乘法計算利用基本概念建立模型對于AR模型，有76.6序列挖掘基本概念定義6-3一個序列是項集的有序表，記為a=a1a2…an,其中每個ai是一個項集。一個序列的長度是它所包含的項集。具有k長度的序列稱為k-序列定義6-4設序列a=a1a2…an,序列β=β1

β2…βn。若存在整數i1<i2<…<in,使得,j=1,…,n，則稱序列a是序列β的子序列。在一組序列中，若某序列a不包含在其他任何序列中，則稱a是該組中最長序列例：<(3)(4,5)(8)>是<(7)(3,8)(9)(4,5,6)(8)>的子序列，但<(3)(5)>不是<(3,5)>的子序列，同樣，<(3,5)>也不是<(3)(5)>的子序列定義6-5給定序列S，序列數據庫DT，序列S的支持度是指S在DT中相對于整個數據庫元組而言所包含S的元組出現的百分比。支持度大于最小支持度的k-序列，稱為DT上的頻繁k-序列6.6序列挖掘基本概念8數據源的形式1、帶交易時間的交易數據庫交易記錄包含客戶號、交易時間及交易中購買的項客戶號交易時間物品1June25’99301June30’99902June10’9910,202June15’99302June20’9940,60,703June25’9930,50,704June25’99304June30’9940,704July25’99905June12’9990數據源的形式客戶號交易時間物品1June25’99301J9數據源的形式(cont.)數據源進行形式化整理,將一個顧客的交易按交易時間排序成項目集客戶號物品1<(30)>2<(10,20)(30)(40,60,70>3<(30,50,70)>4<(30)(40,70)(90)>5<(90)>數據源的形式(cont.)客戶號物品1<(30)>2<(1010數據源的形式(cont.)2、系統(tǒng)調用日志操作系統(tǒng)及其系統(tǒng)進程調用時評價系統(tǒng)安全性的一個重要方面。通過對正常調用序列的學習，可預測隨后發(fā)生的系統(tǒng)調用序列，發(fā)現異常的調用進程號調用時間調用號74404:01:10:302374404:01:10:3214106904:01:10:354904:01:10:3624106904:01:10:37574404:01:10:3881106904:01:10:3962904:01:10:4016-1數據源的形式(cont.)進程號調用時間調用號74404:011數據源的形式(cont.)3、Web日志Web服務器中的日志文件記錄了用戶訪問信息，包括IP地址、訪問時間、URL以及訪問方式等?？疾煊脩舻恼{用順序并從中發(fā)現規(guī)律，可為改善站點設計和提高系統(tǒng)安全性提供重要依據IP地址URL調用序列192.168.120.10<(a)(b,c)(d)>192.168.120.20<(b)(c)(d,e)>192.168.120.30<(a,b)(d)>數據源的形式(cont.)IP地址URL調用序列192.1612序列挖掘的一般步驟一般步驟包括：排序階段將原始的數據庫經排序后轉換成序列數據庫大項集階段找出所有頻繁的項集組成的集合轉換階段在尋找序列模式的過程中，不斷地檢測一個給定的大序列集合是否包含于一個客戶序列中序列階段利用轉換后的數據庫尋找頻繁的序列，即大序列選最大階段在大序列集中找出最長序列序列挖掘的一般步驟一般步驟包括：136.7AprioriAll算法算法思想：將Apriori擴展到序列挖掘中，在每一遍掃描中都利用前以便的大序列來產生候選序列，然后再完成對這個數據庫的遍歷后測試它們的支持度6.7AprioriAll算法算法思想：146.7AprioriAll算法(Cont.)算法描述：輸入：大項集階段轉換后的序列數據庫D輸出：所有最長序列處理：L1={large1-sequence};For(k=2;Lk-1≠Φ;k++)BEGINCk=AprioriAll-generate(Lk-1);foreachcustomer-sequencecinDDOsumthecountofallcandidatesinCkwhichcontainedinc;Lk=candidatesinCkwithminimumsupport;ENDAnswer=MaximalSequenceinUkLk;6.7AprioriAll算法(Cont.)算法描述：15AprioriALL-generate輸入：所有的大(k-1)序列的集合Lk-1輸出：候選Ck處理(1)鏈接運算，得到CkSelectp.itemset1,p.itemset2,…,p.itemsetk-1,q.itemsetk-1FromLk-1p,Lk-1qWherep≠qandp.itemset1=q.itemset1,…p.itemsetk-2=q.itemsetk-2(2)刪除Ck的那些(k-1)序列不在Lk-1中的元素For所有c∈Ck的序列DOFOR所有的c的(k-1)序列sDOIF(s不屬于Lk-1)THENDelete來自于Ck的c；AprioriALL-generate16例：給出一個源數據庫如下表所示，對其進行序列挖掘。設最小支持度為40%?？蛻籼柦灰讜r間物品1June25’99301June30’99902June10’9910,202June15’99302June20’9940,60,703June25’9930,50,704June25’99304June30’9940,704July25’99905June12’9990例：客戶號交易時間物品1June25’99301June17數據源進行形式化整理與轉換客戶號原始顧客序列物品AfterMapping1<(30)><90><{(30)}{(90)}><{1}{5}>2<(10,20)(30)(40,60,70><{(30)}{(40),(70),(40,70)}><{1}{2,3,4}>3<(30,50,70)><{(30,70)}><{1,3}>4<(30)(40,70)(90)><{(30)}{(40),(70),(40,70)}{(90)}><{1}{2,3,4}{5}>5<(90)><{(90)}><{5}>數據源進行形式化整理與轉換客戶號原始顧客序列物品After18例：原序列數據庫：<(1,5)(2)(3)(4)><(1)(3)(4)(3,5)><(1)(2)(3)(4)><(1)(3)(5)><(4)(5)>例：191-sequencessupporseqsupport2-seqsupport1,222,421,343,431,433,521,5324,522,32<1,2><2,1><3,1><4,1><5,1><1,3><2,3><3,2><4,2><5,2><1,4><2,4><3,4><4,3><5,3><1,5><2,5><3,5><4,5><5,4><1,2,3><1,3,2><1,4,2><1,5,2><2,3,4><2,4,3><3,4,5><3,5,4><1,2,4><1,3,4><1,4,3><1,5,3><1,2,5><1,3,5><1,4,5><1,5,4>1-sequencessuppor201-sequencessupport1,2,321,2,421,3,431,3,522,3,42<1,2,3><1,3,4><1,4,5><2,3,4><3,4,5><1,2,4><1,3,5><1,2,3,4><1,2,4,3><1,3,4,5><1,3,5,4><1,2,3,4>1-sequencessupport1,2,3,42最大序列為：<1,2,3,4><1,3,5><4,5>1-sequencessupport1,2,321,2,4221算法性能缺陷：缺少時間限制用戶可能需要指定序列模式的相鄰元素之間的時間間隔；事務的定義過于嚴格一個事務中包含在客戶的一次購買行為中所購買的所有物品?？赡苄枰付ㄒ粋€滑動時間窗口，客戶在滑動時間窗口的時間段內的所有購買行為均作為一個事務缺少分類層次只能在項目的原始級別上進行挖掘算法性能缺陷：226.8AprioriSome算法AprioriSome算法分為兩個階段：前推階段：用于找出指定長度的所有大序列回溯階段：用于查找其他長度的所有大序列6.8AprioriSome算法AprioriSome算法23AprioriSome算法描述輸入：大項集階段轉換后的序列數據庫D；輸出：所有最長序列處理：前推階段：L1={large1-sequences};C1=L1;Last=1;For(k=2;Ck-1≠ΦandLlast≠Φ;k++)DOBEGINIf(Lk-1know)THENCk=NewcandidatesfromLk-1;ELSECk=NewcandidatesfromCk-1; If(k=next(last)THENBEGINFOReachcinDDO計算Ck各項的支持度; Lk=Ck中滿足最小支持度的候選項 last=k; ENDENDAprioriSome算法描述24回溯階段：For(k--;k>=1;k--;)if(Lknotfoundin前推階段)then begindeleteallsequencesinCkcontainedinSomeLi,i>k; foreachcinDDOCk中包含在c中的所有候選者計數 Lk=滿足最小支持度的Ck項endelsedeleteallsequencesinLkcontainedinsomeLi,i>k;Answer=∪Lk回溯階段：25算法next(k:integer)If(hitk<0.666)THENreturnk+1;Elseif(hitk<0.75)THENreturnk+2;Elseif(hitk<0.8)THENreturnk+3;Elseif(hitk<0.85)THENreturnk+4;Elsereturnk+5;Hitk=|Lk|/|Ck|確定對哪些序列進行計數，在對非最大序列計數時間的浪費和擴展小候選序列之間做出權衡算法next(k:integer)26算法示例：使用下表中的數據庫信息，對于next(k)=2k,利用AprioriSome算法進行大序列求解原序列數據庫：<(1,5)(2)(3)(4)><(1)(3)(4)(3,5)><(1)(2)(3)(4)><(1)(3)(5)><(4)(5)>算法示例：27AprioriAllVsAprioriSomeAprioriSome會產生比較多的候選AprioriSome跳躍式計算，可能在回溯階段前就占滿內存；對于較低的支持度，有較長的大序列，因此有較多的非最大序列，在一定條件下，AprioriSome會比較好AprioriAllVsAprioriSomeAprio286.9GSP算法算法描述：1、掃描序列數據庫，得到長度為1的序列模式L1，作為初始的種子集；2、根據長度為i的種子集Li通過連接操作和剪切操作生成長度為i+1的候選序列模式Ci+1；然后掃描序列數據庫，計算每個序列模式的支持數，產生長度為i+1的序列模式Li+1，并將Li+1作為新的種子集；3、重復第2步，直到沒有新的序列模式或新的候選序列模式產生為止6.9GSP算法算法描述：296.9GSP算法(cont.)連接階段：如果去掉序列模式S1的第一個項目與去掉序列模式S2的最后一個項目所得到的序列相同，則可以將S1與S2進行連接，即將S2的最后一個項目添加到S1中剪切階段：若某候選序列模式的某個子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式