新數(shù)據(jù)挖掘課件-13.序列模式挖掘

十月26,2022DMKDSidesByMAO1第六章序列模式挖掘

內(nèi)容提要序列挖掘及其基本方法AprioriAll算法AprioriSome算法GSP算法十月26,2022DMKDSidesByMAO2序列挖掘序列挖掘或稱序列模式挖掘，是指從序列數(shù)據(jù)庫中發(fā)現(xiàn)蘊涵的序列模式。時間序列分析和序列模式挖掘有許多相似之處，在應用范疇、技術方法等方面也有很大的重合度。但是，序列挖掘一般是指相對時間或者其他順序出現(xiàn)的序列的高頻率子序列的發(fā)現(xiàn)，典型的應用還是限于離散型的序列。序列模式挖掘最早是由Agrawal等人提出的，它的最初動機是針對帶有交易時間屬性的交易數(shù)據(jù)庫中發(fā)現(xiàn)頻繁項目序列以發(fā)現(xiàn)某一時間段內(nèi)客戶的購買活動規(guī)律。近年來序列模式挖掘已經(jīng)成為數(shù)據(jù)挖掘的一個重要方面，其應用范圍也不局限于交易數(shù)據(jù)庫，在DNA分析等尖端科學研究領域、Web訪問等新型應用數(shù)據(jù)源等眾多方面得到針對性研究。十月26,2022DMKDSidesByMAO3序列挖掘—基本概念定義6-3一個序列（Sequence）是項集的有序表,記為α=α1→α2→?→αn，其中每個αi是一個項集（Itemset）。一個序列的長度（Length）是它所包含的項集。具有k長度的序列稱為k-序列。定義6-4

設序列α=α1→α2→?→αn，序列β=β1→β2→?→βm

。若存在整數(shù)i1<i2<?<in，使得，則稱序列α是序列β的子序列，或序列β包含序列α。在一組序列中,如果某序列α不包含其他任何序列中，則稱α是該組中最長序列(Maximalsequence)。定義6-5給定序列S，序列數(shù)據(jù)庫DT,序列S的支持度（Support）是指S在DT中相對于整個數(shù)據(jù)庫元組而言所包含S的元組出現(xiàn)的百分比。支持度大于最小支持度(min-sup)的k-序列,稱為DT上的頻繁k-序列。十月26,2022DMKDSidesByMAO4序列挖掘—數(shù)據(jù)源的形式表6-1帶交易時間的交易數(shù)據(jù)源示例客戶號（Cust_id）交易時間（Tran_time）物品（Item）11June25’99June30’993090222June10’99June15’99June20’9910，203040，60，703June25’9930，50，70444June25’99June30’99July25’993040，70905June12’9990表6-2顧客序列表示例客戶號（Cust_id）顧客序列（CustomerSequence）1<（30）（90）>2<（10，20）（30）（40，60，70）>3<（30，50，70）>4<（30）（40，70）（(90)>5<（90）>帶交易時間的交易數(shù)據(jù)庫的典型形式是包含客戶號（Customer-id）、交易時間（Transaction-Time）以及在交易中購買的項（Item）等的交易記錄表。表6-1給出了一個這樣數(shù)據(jù)表的示例。這樣的數(shù)據(jù)源需要進行形式化的整理，其中一個理想的預處理方法就是轉換成顧客序列，即將一個顧客的交易按交易時間排序成項目序列。例如表6-2給出了表6-1對應的所有顧客序列表。十月26,2022DMKDSidesByMAO5序列挖掘—數(shù)據(jù)源的形式(續(xù))表6-2顧客序列表示例

操作系統(tǒng)及其系統(tǒng)進程調(diào)用是評價系統(tǒng)安全性的一個重要方面。通過對正常調(diào)用序列的學習可以預測隨后發(fā)生的系統(tǒng)調(diào)用序列、發(fā)現(xiàn)異常的調(diào)用。因此序列挖掘是從系統(tǒng)調(diào)用等操作系統(tǒng)審計數(shù)據(jù)中發(fā)現(xiàn)有用模式的一個理想的技術。表6-3給出了一個系統(tǒng)調(diào)用數(shù)據(jù)表示意，它是利用數(shù)據(jù)挖掘技術進行操作系統(tǒng)安全性審計的常用數(shù)據(jù)源。表6-3系統(tǒng)進程調(diào)用數(shù)據(jù)示例進程號（Pro_id）調(diào)用時間（Call_time）調(diào)用號（Call_id）74474410699106974410699-104：01：10：3004：01：10：3104：01：10：3204：01：10：3404：01：10：3504：01：10：3804：01：10：3904：01：10：4023144245816216表6-4系統(tǒng)調(diào)用序列數(shù)據(jù)表示例進程號（Pro_id）調(diào)用序列（Call_sequence）74410699<（23，14，81）><（14，24，16）><（4，5，62）>十月26,2022DMKDSidesByMAO6序列模式挖掘的一般步驟我們分五個具體階段來介紹基于上面概念發(fā)現(xiàn)序列模式的方法。這些步驟分別是排序階段、大項集階段、轉換階段、序列階段以及選最大階段。1.排序階段對數(shù)據(jù)庫進行排序（Sort），排序的結果將原始的數(shù)據(jù)庫轉換成序列數(shù)據(jù)庫（比較實際可能需要其他的預處理手段來輔助進行）。例如，上面介紹的交易數(shù)據(jù)庫，如果以客戶號（Cust_id）和交易時間（trans-time）進行排序，那么在通過對同一客戶的事務進行合并就可以得到對應的序列數(shù)據(jù)庫。2.大項集階段這個階段要找出所有頻繁的項集（即大項集）組成的集合L。實際上，也同步得到所有大1-序列組成的集合，即{<l>|l

L}。在上面表6-2給出的顧客序列數(shù)據(jù)庫中，假設支持數(shù)為2，則大項集分別是（30），（40），（70），（40，70）和（90）。實際操作中，經(jīng)常將大項集被映射成連續(xù)的整數(shù)。例如，上面得到的大項集映射成表6-6對應的整數(shù)。當然，這樣的映射純粹是為了處理的方便和高效。LargeItemsetsMappedTo（30）（40）（70）（40，70）（90）12345十月26,2022DMKDSidesByMAO7序列模式挖掘的一般步驟(續(xù))3.轉換階段在尋找序列模式的過程中，我們要不斷地進行檢測一個給定的大序列集合是否包含于一個客戶序列中。表6-7給出了表6-2數(shù)據(jù)庫經(jīng)過轉換后的數(shù)據(jù)庫。比如，在對ID號為2的客戶序列進行轉換的時候，交易（10，20）被剔除了，因為它并沒有包含任何大項集；交易（40，60，70）則被大項集的集合{（40），（70），（40，70）}代替。4.序列階段利用轉換后的數(shù)據(jù)庫尋找頻繁的序列，即大序列（LargeSequence）。5.選最大階段在大序列集中找出最長序列（MaximalSequences）。LargeItemsetsMappedTo（30）（40）（70）（40，70）（90）12345十月26,2022DMKDSidesByMAO8第六章時間序列和序列模式挖掘

內(nèi)容提要時間序列及其應用時間序列預測的常用方法基于ARMA模型的序列匹配方法基于離散傅立葉變換的時間序列相似性查找基于規(guī)范變換的查找方法序列挖掘及其基本方法AprioriAll算法AprioriSome算法GSP算法十月26,2022DMKDSidesByMAO9AprioriAll算法AprioriAll算法源于頻繁集算法Apriori，它把Apriori的基本思想擴展到序列挖掘中，也是一個多遍掃描數(shù)據(jù)庫的算法。在每一遍掃描中都利用前一遍的大序列來產(chǎn)生候選序列，然后在完成遍歷整個數(shù)據(jù)庫后測試它們的支持度。在第一遍掃描中，利用大項目集階段的輸出來初始化大1-序列的集合。在每次遍歷中，從一個由大序列組成的種子集開始，利用這個種子集，可以產(chǎn)生新的潛在的大序列。在第一次遍歷前，所有在大項集階段得到的大1-序列組成了種子集。十月26,2022DMKDSidesByMAO10AprioriAll算法表6-2顧客序列表示例

1.AprioriAll算法描述算法6-1AprioriAll算法輸入：大項集階段轉換后的序列數(shù)據(jù)庫DT輸出：所有最長序列（1）L1={large1-sequences}；//大項集階段得到的結果（2）FOR（k=2；Lk-1

；k++）DOBEGIN（3）Ck=aprioriALL_generate(Lk-1)；//Ck是從Lk-1中產(chǎn)生的新的候選者（4）FOReachcustomer-sequencecinDTDO//對于在數(shù)據(jù)庫中的每一個顧客序列c（5）SumthecountofallcandidatesinCkthatarecontainedinc；//被包含于c中Ck內(nèi)的所有候選者計數(shù)（6）Lk=CandidatesinCkwithminimumsupport//Lk＝Ck中滿足最小支持度的候選者（7）END；（8）Answer=MaximalSequencesin∪kLk；由于我們在關聯(lián)規(guī)則一章對Apriori算法進行了詳盡地介紹，因此上面給出的算法流程很容易理解。它的關鍵仍然是侯選集的產(chǎn)生，具體候選者的產(chǎn)生如下：十月26,2022DMKDSidesByMAO11AprioriAll算法舉例例子6-1對于如下所示的長度為3的序列集合。若將其作為函數(shù)aprioriALL_generate的輸入?yún)?shù)，在連接之后將如圖6-10(b)所示。再修剪掉子序列不在L3中的序列后，得到的序列如圖6-10(c)所示。在修剪的過程中，對于<1，2，4，3>，因為<2，4，3>不在L3大3序列中，所以<1，2，4，3>將被修剪掉。同理其他序列的修剪也是如此。此外，需要說明的是在產(chǎn)生候選4序列時不會產(chǎn)生長度大于4的序列，比如<1，2，4>和<1，3，5>連接時，程序在WHERE條件語句將終止此操作。十月26,2022DMKDSidesByMAO12AprioriAll算法舉例例子6-2給出一個客戶序列組成的數(shù)據(jù)庫如圖6-11（a）所示，在這里我們沒有給出源數(shù)據(jù)庫的形式，即客戶序列已經(jīng)以轉換的形式出現(xiàn)。假如最小支持度為40%（也就是至少兩個客戶序列）那么在大項集階段可以得到大1-序列，之后應用AprioriAll算法可以逐步演變成最終的大序列集。圖6-11給出了整個過程。十月26,2022DMKDSidesByMAO13AprioriAll算法舉例十月26,2022DMKDSidesByMAO14AprioriAll算法舉例至此，AprioriAll算法找到了所有的大-k序列集，即L1、L2、L3、L4，對于大-k序列集進行MaximalSequencesin∪kLk運算，最終得到最大的大序列。上例結果如下表所示：AprioriAll利用了Apriori算法的思想，但是在候選產(chǎn)生和生成頻繁序列方面需要考慮序列元素有序的特點進行相應地處理。表6-8只給出了最終的頻繁序列，實際上在候選產(chǎn)生過程中有大量序列產(chǎn)生。例如圖6-11中，在由L2產(chǎn)生C3過程中，諸如〈2，3，4〉和〈2，4，3〉都作為候選被測試，只不過因為〈2，4，3〉不滿足支持度要求而在演化L3過程中被裁減掉。Sequences

Support<1，2，3，4>2<1，3，5>2<4，5>2十月26,2022DMKDSidesByMAO15第六章時間序列和序列模式挖掘

內(nèi)容提要時間序列及其應用時間序列預測的常用方法基于ARMA模型的序列匹配方法基于離散傅立葉變換的時間序列相似性查找基于規(guī)范變換的查找方法序列挖掘及其基本方法AprioriAll算法AprioriSome算法GSP算法十月26,2022DMKDSidesByMAO16AprioriSome算法AprioriSome算法可以看作是AprioriAll算法的改進，具體過程分為兩個階段：前推階段：此階段用于找出指定長度的所有大序列?；厮蓦A段：此階段用于查找其他長度的所有大序列。算法6-3AprioriSome算法輸入：大項集階段轉換后的序列數(shù)據(jù)庫DT輸出：所有最長序列//ForwardPhase—前推階段；（1）L1={large1-sequences}；//大項目集階段的結果；（2）C1=L1；（3）last=1；//最后計數(shù)的Clast（4）FOR（k=2；Ck-1

andLlast

；k++）DOBEGIN（5）IF（Lk-1know）THENCk=NewcandidatesgeneratedfromLk-1；//Ck＝產(chǎn)生于Lk-1新的候選集（6）ELSECk=NewcandidatesgeneratedfromCk-1；//Ck＝產(chǎn)生于Ck-1新的候選集（7）IF（k=next（last））THENBEGIN（9）FOReachcustomer-sequencecinthedatabaseDO//對于在數(shù)據(jù)庫中的每一個客戶序列c（10）SumthecountofallcandidatesinCkthatarecontainedinc；//求包含在c中的Ck的候選者的數(shù)目之和（11）Lk=CandidatesinCkwithminimumsupport；//Lk＝在Ck中滿足最小支持度的候選者（12）last=k；（13）END；（14）END；十月26,2022DMKDSidesByMAO17AprioriSome算法(續(xù))表6-2顧客序列表示例//BackwardPhase—回溯階段；（15）FOR（k--；k>=1；k--）DO（16）IF（Lknotfoundinforwardphase）THENBEGIN//Lk在前推階段沒有確定的情況（17）DeleteallsequencesinCkcontainedinSomeLi，i>k；//刪除所有在Ck中包含在Lk中的序列，i>k（18）FOReachcustomer-sequencecinDTDO//對于在DT中的每一個客戶序列c（19）SumthecountofallcandidatesinCkthatarecontainedinc；//對在Ck中包含在c中的所有的候選這的計數(shù)（20）Lk=CandidatesinCkwithminimumsupport//Lk=在Ck中滿足最小支持度的候選者（21）END；（22）ELSEDeleteallsequencesinLkcontainedinSomeLi，i>k；//Lk

已知（23）Answer=∪kLk；//從k到m求Lk的并集在前推階段（forwardphase）中，我們只對特定長度的序列進行計數(shù)。比如，前推階段我們對長度為1、2、4和6的序列計數(shù)（計算支持度），而長度為3和5的序列則在回溯階段中計數(shù)。next函數(shù)以上次遍歷的序列長度作為輸入，返回下次遍歷中需要計數(shù)的序列長度。算法6-4next（k:integer）IF（hitk<0.666）THENreturnk+1；ELSEIF（hitk<0.75）THENreturnk+2；ELSEIF（hitk<0.80）THENreturnk+3；ELSEIF（hitk<0.85）THENreturnk+4；ELSETHENreturnk+5；hitk被定義為大k-序列（largek-sequence）和候選k-序列（candidatek-sequence）的比率，即|Lk|/|Ck|。這個函數(shù)的功能是確定對哪些序列進行計數(shù)，在對非最大序列計數(shù)時間的浪費和計算擴展小候選序列之間作出權衡。十月26,2022DMKDSidesByMAO18AprioriSome算法例子6-3我們?nèi)匀徊捎肁prioriAll算法用過的圖6-11（a）數(shù)據(jù)庫例子來說明AprioriSome算法。在大項集階段可以找出L1（和圖6-9（b）的L1相同）。假設next（k）=2k，則通過計算C2可以得到L2（和圖6-11（d）中的L2相同）。第三次遍歷后，apriori_generate函數(shù)以L2作為輸入?yún)?shù)來產(chǎn)生C3。圖6-12（e）給出了C3中的候選序列。我們不計算C3，因此也不產(chǎn)生L3。下一步apriori_generate函數(shù)以C3來產(chǎn)生C4，在經(jīng)過剪枝后，得到的結果和圖6-9（i）所示的C4相同。在以C4計算L4（圖6-12（i））之后，我們試圖產(chǎn)生C5，這時的結果為空。前推階段的具體運行見下圖6-12所示。十月26,2022DMKDSidesByMAO19AprioriSome算法十月26,2022DMKDSidesByMAO20AprioriSome算法回溯階段的具體運行見下圖6-13所示。十月26,2022DMKDSidesByMAO21AprioriAll和AprioriSome比較AprioriAll和AprioriSome比較AprioriAll用Lk-1去算出所有的候選Ck，而AprioriSome會直接用Ck-1去算出所有的候選Ck.，因為Ck-1包含Lk-1，所以AprioriSome會產(chǎn)生比較多的候選。雖然AprioriSome跳躍式計算候選，但因為它所產(chǎn)生的候選比較多，可能在回溯階段前就占滿內(nèi)存。如果內(nèi)存滿了，AprioriSome就會被強迫去計算最后一組的候選，（即使原本是要跳過此項）。這樣，會影響并減少已算好的兩個候選間的跳躍距離，而使得AprioriSome會變的跟AprioriAll一樣。對于較低的支持度，有較長的大序列，也因此有較多的非最大序列，所以AprioriSome比較好。十月26,2022DMKDSidesByMAO22第六章時間序列和序列模式挖掘

內(nèi)容提要時間序列及其應用時間序列預測的常用方法基于ARMA模型的序列匹配方法基于離散傅立葉變換的時間序列相似性查找基于規(guī)范變換的查找方法序列挖掘及其基本方法AprioriAll算法AprioriSome算法GSP算法十月26,2022DMKDSidesByMAO23GSP算法GSP算法主要包括三個步驟：①掃描序列數(shù)據(jù)庫，得到長度為1的序列模式L1，作為初始的種子集；②根據(jù)長度為i的種子集Li

通過連接操作和剪切操作生成長度為i+1的候選序列模式Ci+1；然后掃描序列數(shù)據(jù)庫，計算每個候選序列模式的支持數(shù)，產(chǎn)生長度為i+1的序列模式Li+1，并將Li+1作為新的種子集；③重復第二步，直到?jīng)]有新的序列模式或新的候選序列模式產(chǎn)生為止。其中，產(chǎn)生候選序列模式主要分兩步：連接階段：如果去掉序列模式S1的第一個項目與去掉序列模式S2的最后一個項目所得到的序列相同，則可以將S1于S2進行連接，即將S2的最后一個項目添加到S1中。剪切階段：若某候選序列模式的某個子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除。候選序列模式的支持度計算按照如下方法進行：對于給定的候選序列模式集合C，掃描序列數(shù)據(jù)庫DT，對于其中的每一條序列d，找出集合C中被d所包含的所有候選序列模式，并增加其支持度計數(shù)。十月26,2022DMKDSidesByMAO24GSP算法算法6-5GSP算法輸入：大項集階段轉換后的序列數(shù)據(jù)庫DT。輸出：最大序列（1）L1={large1-sequences}；//大項集階段得到的結果（2）FOR（k=2；Lk-1

；k++）DOBEGIN（3）Ck=GSPgenerate(Lk-1)；（4）FOReachcustomer-sequencecinthedatabase

DTDO（5）IncrementthecountofallcandidatesinCkthatarecontainedinc；（6）Lk=CandidatesinCkwithminimumsupport；（7）END；（8）Answer=MaximalSequencesin∪kLk；十月26,2022DMKDSidesByMAO25GSP算法部分例子例子6-5

表6-9演示了從長度為3的序列模式產(chǎn)生長度為4的候選序列模式的過程。演示了從長度為3的序列模式產(chǎn)生長度為4的候選序列模式的過程。在連接階段:

序列<（1，2），3>可以與<2，（3，4）>連接，因為<（*，2），3>與<2，（3，*）>是相同的，兩序列連接后為<（1，2），（3，4）><（1，2），3>與<2，3，5>連接，得到<（1，2），3，5>。剩下的序列是不能連接的，比如<（1，2），4>不能與任何長度為3的序列連接，這是因為其他序列沒有<（2），（4，*）>或者<（2），（4），（*）>的形式。表6-9GSP算法舉例在修剪階段<（1，2），3，5>將被剪掉，這是因為<1，3，5>并不在L3中，而<（1，2），（3，4）>的長度為3的子序列都在L3因而被保留下來。SequentialpatternsWithLength3Candidate4-Sequences

AfterJoin

AfterPruning<（1，2），3><（1，2），4><1，（3，4）><（1，3），5><2，（3，4）><2，3，5>

<（1，2），（3，4）><（1，2），3，5>

<（1，2），（3，4）>十月26,2022DMKDSidesByMAO26十月26,2022DMKDSidesByMAO26GSP算法舉例十月26,2022DMKDSidesByMAO26GSP算法舉例例：基于表中的數(shù)據(jù)D，利用GSP算法進行序列模式挖掘，最小支持數(shù)為2（最小支持度為50%）。注:為了節(jié)省篇幅,在不引起誤解的情況下表中省略了逗號和括號.GSP算法完整舉例序列數(shù)據(jù)庫D用戶訪問序列10<a(abc)(ab)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<eg(af)cbc>十月26,2022DMKDSidesByMAO27十月26,2022DMKDSidesByMAO27GSP算法舉例十月26,2022DMKDSidesByMAO27GSP算法舉例1）對原始數(shù)據(jù)庫D進行掃描，查找長度為1的頻繁序列，構造種子集S1掃描發(fā)現(xiàn)頻繁序列及其支持度<a>:4；<b>:4；<c>:4；<d>:3；<e>:3；<f>:3，從而得到種子集S1

={<a>,<b>,<c>,<d>,<e>,<g>,<h>}；由種子集S1構造長度為2的候選集C2可以直接連接S1無需判斷，也無需進行剪枝。2）S2生成過程。<(aa)>,<aa>,<(ab)>,<ab>,<ba>,<(ac)>,<ac>,<ca>,<(ad)>,<ad>,<da>,<(ae)>,<ae>,<ea>,<(af)>,<af>,<fa>,<(bb)>,<bb>,<(bc)>,<bc>,<cb>,<(bd)>,<bd>,<db>,<(be)>,<be>,<eb>,<(bf)>,<bf>,<fb>,<(cc)>,<cc>,<(cd)>,<cd>,<dc>,<(ce)>,<ce>,<ec>,<(cf)>,<cf>,<fc>,<(dd)>,<dd>,<(de)>,<de>,<ed>,<(df)>,<df>,<fd>,<(ee)>,<ee>,<(ef)>,<ef>,<fe>,<(ff)>,<ff>因為1項序列都頻繁，所以無需剪枝，可以直接保留連接后的序列。2的種子集：S2={<aa>，<(a,b)>，<ab>，<ba>，<ac>，<ca>，<ad>，<ea>，<af>，<bb>，<(b,c)>，<bc>，<cb>，<bd>，<db>，<bf>，<cc>，<dc>，<ec>，<cf>，<fc>，<ef>，<ff>}。GSP算法完整舉例例1：基于表4-1中的數(shù)據(jù)D，利用GSP算法進行序列模式挖掘，最小支持數(shù)為2（最小支持度為50%）。表4-2：序列數(shù)據(jù)庫D示例十月26,2022DMKDSidesByMAO28十月26,2022DMKDSidesByMAO28GSP算法舉例十月26,2022DMKDSidesByMAO28GSP算法舉例3）由種子集S2構造長度為3的候選集C3由于S2的序列太多，僅以S2中的三個序列<aa>,<(ab)>,<ab>來演示連接和剪枝的原理：3-1）連接階段<aa>序列去掉第一個元素a后得到序列<a>，<(a,b)>序列去掉最后一個元素b后也得到序列<a>，所以<aa>與<(a,b)>這兩個序列是可以連接的，將<(a,b)>的最后一個元素b連接到<aa>序列的最后，由于元素b在原序列屬于最后一個集合中，因此要將b與a合并形成集合（a,b），所以連接后得到的序列為<a(a,b)>。同理，發(fā)現(xiàn)<aa>與<ab