序列模式挖掘

數據挖掘與商務智能

DataMining&BusinessIntelligence西安電子科技大學軟件學院主講人：黃健斌

第六章序列模式挖掘

內容提綱序列模式挖掘簡介序列模式挖掘的應用背景序列模式挖掘算法概述GSP算法SPADE算法PrefixSpan算法CloSpan算法利用SPSS軟件挖掘頻繁序列模式序列模式挖掘簡介序列模式的概念最早是由Agrawal和Srikant

提出的。動機：大型連鎖超市的交易數據有一系列的用戶事務數據庫，每一條記錄包括用戶的ID，事務發(fā)生的時間和事務涉及的項目。如果能在其中挖掘涉及事務間關聯關系的模式，即用戶幾次購買行為間的聯系，可以采取更有針對性的營銷措施。序列模式挖掘的應用背景應用領域：客戶購買行為模式預測Web訪問模式預測疾病診斷······應用案例1：客戶購買行為模式分析B2C電子商務網站可以根據客戶購買紀錄來分析客戶購買行為模式，從而進行有針對性的營銷策略。IDUsertransactionsequence1…………..2………………3……………………..4………………….圖書交易網站將用戶購物紀錄整合成用戶購物序列集合得到用戶購物行為序列模式<(“UML語言”)(“Visio2003實用技巧”)>相關商品推薦：如果用戶購買了書籍“UML語言”,則推薦“Visio2003實用技巧”應用案例2：Web訪問模式分析大型網站的網站地圖(sitemap)往往具有復雜的拓撲結構。用戶訪問序列模式的挖掘有助于改進網站地圖的拓撲結構。比如用戶經常訪問網頁web1然后訪問web2,而在網站地圖中二者距離較遠，就有必要調整網站地圖，縮短它們的距離，甚至直接增加一條鏈接。Index網站入口web1web2應用案例3：疾病診斷醫(yī)療領域的專家系統可以作為疾病診斷的輔助決策手段。對應特定的疾病，眾多該類病人的癥狀按時間順序被記錄。自動分析該紀錄可以發(fā)現對應此類疾病普適的癥狀模式。每種疾病和對應的一系列癥狀模式被加入到知識庫后，專家系統就可以依此來輔助人類專家進行疾病診斷。例:通過分析大量曾患A類疾病的病人發(fā)病紀錄，發(fā)現以下癥狀發(fā)生的序列模式：<(眩暈)(兩天后低燒37-38度)>如果病人具有以上癥狀，則有可能患A類疾病事務數據庫實例例：一個事務數據庫，一個事務代表一筆交易，一個單項代表交易的商品，單項屬性中的數字記錄的是商品ID序列數據庫一般為了方便處理，需要把事務數據庫轉化為序列數據庫。方法是把用戶ID相同的記錄合并，有時每個事務的發(fā)生時間可以忽略，僅保持事務間的順序關系?；靖拍铐椉?Itemset)是所有在序列數據庫出現過的單項組成的集合例：對一個用戶購買記錄的序列數據庫來說，項集包含用戶購買的所有商品，一種商品就是一個單項。通常每個單項有一個唯一的ID，在數據庫中記錄的是單項的ID?；靖拍钤?Element)可表示為(x1x2…xm)，xk(1<=k<=m)為不同的單項。元素內的單項不考慮順序關系，一般默認按照ID的字典序排列．在用戶事務數據庫里，一個事務就是一個元素基本概念序列(Sequence)是不同元素(Element)的有序排列，序列s可以表示為s=<s1s2…sl>，sj(1<=j<=l)為序列s的元素

一個序列包含的所有單項的個數稱為序列的長度。長度為l的序列記為l-序列舉例例：一條序列<(10,20)30(40,60,70)>有3個元素，分別是（1020），30，（406070）；3個事務的發(fā)生時間是由前到后。這條序列是一個6-序列?；靖拍钤O序列=<a1a2…an>，序列=<b1b2…bm>，ai和bi都是元素。如果存在整數1<=j1<j2<…<jn<=m，使得a1bj1，a2bj2，…，anbjn，則稱序列為序列的子序列，又稱序列包含序列，記為。序列在序列數據庫S中的支持度為序列數據庫S中包含序列的序列個數，記為Support()給定支持度閾值，如果序列在序列數據庫中的支持度不低于，則稱序列為序列模式長度為l的序列模式記為l-模式例子例子：設序列數據庫如下圖所示，并設用戶指定的最小支持度min-support=2。SidSequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<(af)cbc>序列<a(bc)df>是序列<a(abc)(ac)d(cf)>的子序列序列<(ab)c>是長度為3的序列模式序列模式先驗特性Apriori(Agrawal&Sirkant’94)特性如果序列s是非頻繁序列，則s的所有超集序列都是非頻繁的<a(bd)bcb(ade)>50<(be)(ce)d>40<(ah)(bf)abf>30<(bf)(ce)b(fg)>20<(bd)cb(ac)>10SequenceSeq.IDmin_sup=2<hb>非頻繁則：<hab>非頻繁<(ah)b>非頻繁序列模式VS關聯規(guī)則問題序列模式挖掘關聯規(guī)則挖掘數據集序列數據庫事務數據庫關注點單項間在同一事務內以及事務間的關系單項間在同一事務內的關系序列模式挖掘算法概述類Apriori算法

該類算法基于Apriori理論，即序列模式的任一子序列也是序列模式。算法首先自底向上的根據較短的序列模式生成較長的候選序列模式，然后計算候選序列模式的支持度。典型的代表有GSP算法,spade算法等基于劃分的模式生長算法

該類算法基于分治的思想，迭代的將原始數據集進行劃分，減少數據規(guī)模，同時在劃分的過程中動態(tài)的挖掘序列模式，并將新發(fā)現的序列模式作為新的劃分元。典型的代表有FreeSpan算法和prefixSpan算法知識回顧基本概念支持度計數：包含特定項集的事務的個數:關聯規(guī)則：形如的蘊涵表達式支持度：同時包含X,Y的事務在所有事務中所占的比例

置信度：事務X出現時Y出現的頻繁程度頻繁項集：滿足最小支持的項集

知識回顧定理 先驗原理：如果一個項集是頻繁的，那它的所有子集一定都是 頻繁的

定理1：如果規(guī)則不滿足置信度閾值，則形如 的規(guī)則一定也不滿足置信度閾值，其中X'是X的子集關聯規(guī)則挖掘的任務劃分：頻繁項集的產生（候選(產生)，剪枝（基于先驗原理））規(guī)則的產生(逐層方法來產生關聯規(guī)則,定理1剪枝)知識回顧Ck:CandidateitemsetofsizekFk:frequentitemsetofsizekF1={frequentitems};for(k=1;Fk!=;k++)dobegin

Ck+1=candidatesgeneratedfromFk;

foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedint

Fk+1=candidatesinCk+1withmin_support

endreturn

k

Fk;Apriori算法偽代碼：知識回顧支持度度量滿足單調性(X'為X的子集)置信度一般不滿足單調性(X'為X的子集)如果關聯規(guī)則產生自同一項集，則置信度滿足單調性知識回顧Prunedsupersets基于支持度的候選項集剪枝知識回顧PrunedRulesLowConfidenceRule基于置信度的候選規(guī)則剪枝GSP算法算法思想(候選產生測試法)：類似于Apriori算法，采用冗余候選模式的剪除策略和特殊的數據結構-----哈希樹來實現候選模式的快速訪存。GSP算法描述掃描序列數據庫，得到長度為1的序列模式F1，作為初始的種子集根據長度為i的種子集Fi

，通過連接操作和修剪操作生成長度為i+1的候選序列模式Ci+1；掃描序列數據庫，計算每個候選序列模式的支持度，產生長度為i+1的序列模式Fi+1，并將Fi+1作為新的種子集重復第二步，直到沒有新的序列模式或新的候選序列模式產生為止F1

C2

F2

C3

F3

C4

F4

……GSP算法偽代碼輸入：大項集階段轉換后的序列數據庫DT。輸出：最大序列（1）L1={large1-sequences}；（2）FOR（k

=2；Lk-1

；k++）DOBEGIN（3）Ck=GSPgenerate(Lk-1)；（4）FOReachcustomer-sequencecinthedatabaseDTDO（5）IncrementthecountofallcandidatesinCkthatarecontainedinc；（6）Lk=CandidatesinCkwithminimumsupport；（7）END；（8）Answer=MaximalSequencesin∪kLk；GSP算法產生候選序列模式主要分兩步：連接階段：如果去掉序列模式s1的第一個元素與去掉序列模式s2的最后一個元素所得到的序列相同，則可以將s1與s2進行連接，即將s2的最后一個元素添加到s1中剪枝階段：若某候選序列模式的某個子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除L1

C2

L2

C3

L3

C4

L4

……GSP算法序列合并過程

序列s1與另一個序列s2合并，s2的最后一個單項可以作為最后一個單項合并到s1的最后一個元素中，也可以作為一個單獨的元素。取決于以下條件：如果s2的最后兩個單項屬于相同的元素，則s2的最后一個單項在合并后的序列中是s1的最后一個元素的一部分。如果s2的最后兩個單項屬于不同的元素，則s2的最后一個單項在合并后的序列中成為連接到s1尾部的元素。GSP算法候選序列模式的支持度計算：對于給定的候選序列模式集合C，掃描序列數據庫，對于其中的每一條序列s,找出集合C中被s所包含的所有候選序列模式，并增加其支持度計數舉例哈希樹GSP采用哈希樹存儲候選序列模式。哈希樹的節(jié)點分為三類：根節(jié)點內部節(jié)點葉子節(jié)點

哈希樹根節(jié)點和內部節(jié)點中存放的是一個哈希表，每個哈希表項指向其它的節(jié)點。而葉子節(jié)點內存放的是一組候選序列模式。例：添加候選序列模式從根節(jié)點開始，用哈希函數對序列的第一個元素做映射來決定從哪個分支向下，依次在第n層對序列的第n個單項作映射來決定從哪個分支向下，直到到達一個葉子節(jié)點。將序列儲存在此葉子節(jié)點。初始時所有節(jié)點都是葉子節(jié)點，當一個葉子節(jié)點所存放的序列數目達到一個閾值，它將轉化為一個內部節(jié)點。

計算候選序列模式的支持度給定一個序列s是序列數據庫的一個記錄：對于根節(jié)點，用哈希函數對序列s的每一個單項做映射來并從相應的表項向下迭代的進行操作2）。對于內部節(jié)點，如果s是通過對單項x做哈希映射來到此節(jié)點的，則對s中每一個和x在一個元素中的單項以及在x所在元素之后第一個元素的第一個單項做哈希映射，然后從相應的表項向下迭代做操作2）或3）。對一個葉子節(jié)點，檢查每個候選序列模式c是不是s的子序列.如果是相應的候選序列模式支持度加一。

計算候選序列模式的支持度hash樹存儲的優(yōu)點這種計算候選序列的支持度的方法避免了大量無用的掃描，對于一條序列，僅檢驗那些最有可能成為它子序列的候選序列模式。掃描的時間復雜度由O(n*m)降為O(n*t),其中n表示序列數量，m表示候選序列模式的數量，t代表哈希樹葉子節(jié)點的最大容量GSP算法存在的主要問題如果序列數據庫的規(guī)模比較大，則有可能會產生大量的候選序列模式需要對序列數據庫進行循環(huán)掃描對于序列模式的長度比較長的情況，由于其對應的短的序列模式規(guī)模太大，本算法很難處理SPADE算法SPADE(SequentialPAtternDiscoveryusingEquivalentClass)developedbyZaki2001基于Apriori的垂直數據格式的序列模式挖掘算法通過簡單的連接K序列任意長度為(k-1)子序列的ID_list，可以確定任意K序列的支持度。ID_list的長度等于K序列的支持度，即可確定是否是序列模式。數據庫表示形式：<itemset:(sequence_ID,event_ID)>SPADE算法minsup=2SPADE算法總結優(yōu)點：垂直數據格式的使用連同ID_list的創(chuàng)建，可以減少對序列數據庫的掃描。ID_list攜帶了計算候選序列支持度的必要信息，隨著頻繁序列長度的增加，導致連接速度加快。缺點：同GSP，使用寬度優(yōu)先和先驗剪枝產生很大的候選集。序列模式挖掘算法概述基于劃分的模式生長算法

該類算法基于分治的思想，迭代的將原始數據集進行劃分，減少數據規(guī)模，同時在劃分的過程中動態(tài)的挖掘序列模式，并將新發(fā)現的序列模式作為新的劃分元。典型的代表有FreeSpan算法和PrefixSpan算法PrefixSpan算法算法思想：基于FP-Growth算法

Pei,etal.@ICDE’01采用分治的思想，不斷產生序列數據庫的多個更小的投影數據庫，然后在各個投影數據庫上進行序列模式挖掘知識回顧FP-Growth算法通過逐個讀入事務，并把每一個事務映射到FP樹中的一條路徑的方法構造FP-Tree。在FP-Tree上利用遞歸分治的方法挖掘頻繁項集知識回顧nullA:1B:1nullA:1B:1B:1C:1D:1AfterreadingTID=1:AfterreadingTID=2:知識回顧nullA:7B:5B:3C:3D:1C:1D:1C:3D:1D:1E:1E:1PointersareusedtoassistfrequentitemsetgenerationD:1E:1TransactionDatabaseHeadertable基本概念前綴：設每個元素中的所有單項按照字典序排列。給定序列

=<e1e2…en>，

=<e1’e2’…em’>(mn)，如果ei’

=ei(i

m-1)，em’em，并且(em-em’)中的單項均在em’中單項的后面，則稱是的前綴例：序列<(ab)>是序列<(abd)(acd)>的一個前綴；序列<(ad)>則不是?；靖拍钔队埃航o定序列和，如果是的子序列，則關于的投影’必須滿足：是’的前綴，’是的滿足上述條件的最大子序列例：對于序列

=<(ab)(acd)>，其子序列

=<(b)>的投影是’=<(b)(acd)>;<(ab)>的投影是原序列<(ab)(acd)>?；靖拍詈缶Y：序列關于子序列

=<e1e2…em-1em’>的投影為’=<e1e2…en>(n>=m)，則序列關于子序列的后綴為<em”em+1…en>，其中em”=(em-em’)

例：對于序列<(ab)(acd)>，其子序列<(b)>的投影是<(b)(acd)>，則<(ab)(acd)>對于<(b)>的后綴為<(acd)>?！偨Y：后綴即是投影去掉它自身；舉例例：<a(abc)(ac)d(cf)><a><aa><a(ab)><a(abc)><(abc)(ac)d(cf)><(_bc)(ac)d(cf)><ab><(_c)(ac)d(cf)>基本概念投影數據庫：設為序列數據庫S中的一個序列模式，則的投影數據庫為S中所有以為前綴的序列相對于的后綴，記為S|投影數據庫中的支持度：設為序列數據庫S中的一個序列，序列以為前綴，則在的投影數據庫S|中的支持度為S|中滿足條件.的序列的個數舉例例：對于如下的序列數據庫生成一系列的投影數據庫SidSequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<(af)cbc>舉例掃描序列數據庫S，產生長度為1的序列模式有：<a>:4,<b>:4,<c>:4,<d>:3,<e>:3,<f>:3序列模式的全集必然可以分為分別以<a>，<b>，<c>，<d>，<e>和<f>為前綴的序列模式的集合，構造不同前綴所對應的投影數據庫，結果如下頁圖所示舉例PrefixProjectDatabase<a><(abc)(ac)d(cf)><(_d)c(bc)(ae)><(_b)(df)cb><(_f)cbc><b><(_c)(ac)d(cf)><(_c)(ae)><(df)cb><c><c><(ac)d(cf)><(bc)(ae)><b><bc><d><(cf)><c(bc)(ae)><(_f)cb><e><(_f)(ab)(df)cb><(af)cbc><f><(ab)(df)cb><cbc>Prefix-Span算法描述掃描序列數據庫，生成所有長度為1的序列模式根據長度為1的序列模式，生成相應的投影數據庫在相應的投影數據庫上重復上述步驟，直到在相應的投影數據庫上不能產生長度為1的序列模式為止分別對不同的投影數據庫重復上述過程，直到沒有新的長度為1的序列模式產生為止SS1…SmS11………S1n……Sm1………Smp……算法偽碼PrefixSpan算法輸入：序列數據庫S及最小支持度閾值min_sup輸出：所有的序列模式方法：去除所有非頻繁的項目，然后調用子程序PrefixSpan(<>,0,S)算法偽碼子程序PrefixSpan(,L,S|)參數：:一個序列模式;

L:序列模式的長度;

S|:如果為空，則為S，否則為的投影數據庫掃描S|，找到滿足下述要求的長度為1的序列模式b：b可以添加到的最后一個元素中并為序列模式<b>可以作為的最后一個元素并為序列模式對每個生成的序列模式b，將b添加到形成序列模式’，并輸出’對每個’,構造’的投影數據庫S|’,并調用子程序PrefixSpan(’,L+1,S|’)PrefixSpan算法序列合并過程

序列s1與另一個序列s2合并，s2的最后一個單項可以作為最后一個單項合并到s1的最后一個單項中，也可以作為一個單獨的單項。取決于以下條件：如果s2的最后兩個單項屬于相同的元素，則s2的最后一個單項在合并后的序列中是s1的最后一個元素的一部分。如果s2的最后兩個單項屬于不同的元素，則s2的最后一個單項在合并后的序列中成為連接到s1尾部的元素。舉例Sid

sequence1<(1,2)(1,3)>

2<(3,4)(5,6,7)>

3<(1,3)(8)(7)>

4<(8)>

給定如下的序列數據庫：minsup=2舉例找出頻繁單項：1，3，7，8；然后除去非頻繁的單項：Sid

sequence1<(1)(1,3)>

2<(3)(7)>

3<(1,3)(8)(7)>

4<(8)>

舉例為頻繁1序列（頻繁單項）生成投影數據庫：SidSuffixforprefix<(1)>1<(1,3)>3<(_3)(8)(7)>Sid

sequence1<(1)(1,3)>

2<(3)(7)>

3<(1,3)(8)(7)>

4<(8)>

舉例為頻繁1序列（頻繁單項）生成投影數據庫：SidSuffixforprefix<(3)>1<>2<(7)>3<(8)(7)>Sid

sequence1<(1)(1,3)>

2<(3)(7)>

3<(1,3)(8)(7)>

4<(8)>

舉例SidSuffixforprefix<(7)>2<>3<>SidSuffixforprefix<(8)>3<(7)>4<>舉例在上面的投影數據庫中，前綴<(1)>的投影數據庫中還有頻繁單項_3，前綴<(3)>的投影數據庫中還有頻繁單項7.生成頻繁2序列<(1,3)>，<(3)(7)>,然后為其生成投影數據庫.其中沒有頻繁項目，算法終止。SidSuffixforprefix<(1,3)>1<>3<(8)(7)>SidSuffixforprefix<(3)(7)>2<>3<>PrefixSpan算法分析PrefixSpan算法不需要產生候選序列模式，從而大大縮減了檢索空間相對于原始的序列數據庫而言，投影數據庫的規(guī)模不斷減小PrefixSpan算法的主要開銷在于投影數據庫的構造?？梢酝ㄟ^偽投影技術進行效率提升。偽投影當數據庫可以直接放入內存時，并不需要構造所有的序列模式對應的投影數據庫，我們可以使用指向數據庫中序列的指針及其偏移量作為偽投影例子：假設上述序列數據庫可以放入內存，在構造a投影數據庫時，序列S1=<a(abc)(ac)d(cf)>所對應的偽投影為：一個指向S1的指針，指針偏移設定為2。同樣的，序列S1的<ab>投影數據庫對應的偽投影為：一個指向S1的指針，指針偏移設定為4偽投影與物理投影對比偽投影避免了物理投影拷貝后綴的過程當數據庫可以存放入主內存中，偽投影在時間和空間上都是很高效的但是當數據庫不可以放入內存中時，偽投影技術是非常低效的硬盤隨機訪問時很低效的建議策略:集成偽投影和物理投影技術當數據集可以放入內存時候，使用偽投影技術算法效率比較偽投影與物理投影比較閉序列模式挖掘閉序列模式：如果不存在序列s'，其中s'是s的真超序列，并且s'與s具有相同的支持度，那么稱s為閉序列模式例子：以下序列哪一個為閉序列模式? <abc>:20,<abcd>:20,<abcde>:15CloSpan:MiningClosedSequentialPatternsinLargeDatasetsXifengYan.JiaweiHan序列擴展項集擴展：，同時

序列擴展：字典序樹字典序：,同時，如果滿足下列條件之一，則t<t'舉例：(a,f)<(b,f),(a,b)<(a,b,c)字典序樹字典序序列如果s'=s?p,則s<s'；(序列大于它的前綴序列)如果s=a?ip，同時s'=a?sp',無論p與p'之間的序列關系都有s<s'；(項集擴展小于序列擴展)如果s=a?ip，s'=a?ip'，p<p'則有s<s'；(同種擴展與后綴大小相關)如果s=a?sp，同時s'=a?sp'，p<p'則s<s'；舉例：<(ab)><<(ab)(a)>,<(ab)><<(a)(b)>字典序序列樹構造字典序序列樹構造示例示例PrefixSpan算法PrefixSpan算法特點：在前綴搜索樹上搜索所有的頻繁項集終止條件：序列s的投影數據庫中序列的個數小于min_sup優(yōu)化策略引理1：給定一個子序列s和它的投影數據庫Ds.如果存在a，a是Ds中所有具有相同擴展類型序列的公共前綴。那么對于任意的b，如果s?b是閉的，a肯定是b的前綴。即我們只需要搜索分支s?a，而不用搜索分支s?b。舉例：Ds={<(d)(e)(af)>,<(d)(e)(fg)>}，因為<(d)(e)>是Ds中的所有序列的公共前綴，因此D中以s為前綴但不包含序列<(d)(e)>的序列都不可能是閉序列。因此我們不需要構造序列s?e優(yōu)化策略引理2：給定一個序列s和它的投影數據庫Ds.如果存在a，對Ds中所有序列項a總是出現在項b之前（無論他們是在同一個元素中還是不同元素中），那么Ds?a?b=Ds?b。因此對于任意的r，s?b?r不可能是閉序列。則不需要搜索分支s?b優(yōu)化策略投影數據庫等價性優(yōu)化策略引理3：給定兩個序列s和s'，同時s是s'的子序列，且L(Ds)=L(Ds')，那么對于任意的r，support(s?r)=supprot(s'?r)優(yōu)化策略推論1：如果一個序列s<s'并且.如果有L(Ds)=L(Ds')，那么就不需要在繼續(xù)搜索s'在前綴搜索樹上的分支。稱s'是s的一個向后子模式舉例：對于如下序列數據庫有L(D<(f)>)=L(D<(af)>)，則可以得出D<(f)>=D<(af)>.即：不需要一一比較D<(f)>和D<(af)>z中的所有序列是否相等，而只需要比較這兩個集合的大小即可優(yōu)化策略推論2：如果一個序列s<s'并且.如果有L(Ds)=L(Ds')，那么就可以利用s分支代替搜索s'在前綴搜索樹上的分支。稱s'是s的一個向后超模式舉例：對于如下序列數據庫有L(D<(b)>)=L(D<(e)(b)>)，則可以得出D<(b)>=D<(e)(b)>.即：不需要增長序列<(e)(b)>,因為<(e)(b)>的投影數據庫與<(b)>的投影數據