序列模式挖掘

數(shù)據(jù)挖掘與商務(wù)智能

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

第六章序列模式挖掘

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

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

一個(gè)序列包含的所有單項(xiàng)的個(gè)數(shù)稱為序列的長度。長度為l的序列記為l-序列舉例例：一條序列<(10,20)30(40,60,70)>有3個(gè)元素，分別是（1020），30，（406070）；3個(gè)事務(wù)的發(fā)生時(shí)間是由前到后。這條序列是一個(gè)6-序列?；靖拍钤O(shè)序列=<a1a2…an>，序列=<b1b2…bm>，ai和bi都是元素。如果存在整數(shù)1<=j1<j2<…<jn<=m，使得a1bj1，a2bj2，…，anbjn，則稱序列為序列的子序列，又稱序列包含序列，記為。序列在序列數(shù)據(jù)庫S中的支持度為序列數(shù)據(jù)庫S中包含序列的序列個(gè)數(shù)，記為Support()給定支持度閾值，如果序列在序列數(shù)據(jù)庫中的支持度不低于，則稱序列為序列模式長度為l的序列模式記為l-模式例子例子：設(shè)序列數(shù)據(jù)庫如下圖所示，并設(shè)用戶指定的最小支持度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的序列模式序列模式先驗(yàn)特性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ān)聯(lián)規(guī)則問題序列模式挖掘關(guān)聯(lián)規(guī)則挖掘數(shù)據(jù)集序列數(shù)據(jù)庫事務(wù)數(shù)據(jù)庫關(guān)注點(diǎn)單項(xiàng)間在同一事務(wù)內(nèi)以及事務(wù)間的關(guān)系單項(xiàng)間在同一事務(wù)內(nèi)的關(guān)系序列模式挖掘算法概述類Apriori算法

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

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

置信度：事務(wù)X出現(xiàn)時(shí)Y出現(xiàn)的頻繁程度頻繁項(xiàng)集：滿足最小支持的項(xiàng)集

知識(shí)回顧定理 先驗(yàn)原理：如果一個(gè)項(xiàng)集是頻繁的，那它的所有子集一定都是 頻繁的

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

Ck+1=candidatesgeneratedfromFk;

foreachtransactiontindatabasedoincrementthecountofallcandidatesinCk+1thatarecontainedint

Fk+1=candidatesinCk+1withmin_support

endreturn

k

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

，通過連接操作和修剪操作生成長度為i+1的候選序列模式Ci+1；掃描序列數(shù)據(jù)庫，計(jì)算每個(gè)候選序列模式的支持度，產(chǎn)生長度為i+1的序列模式Fi+1，并將Fi+1作為新的種子集重復(fù)第二步，直到?jīng)]有新的序列模式或新的候選序列模式產(chǎn)生為止F1

C2

F2

C3

F3

C4

F4

……GSP算法偽代碼輸入：大項(xiàng)集階段轉(zhuǎn)換后的序列數(shù)據(jù)庫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算法產(chǎn)生候選序列模式主要分兩步：連接階段：如果去掉序列模式s1的第一個(gè)元素與去掉序列模式s2的最后一個(gè)元素所得到的序列相同，則可以將s1與s2進(jìn)行連接，即將s2的最后一個(gè)元素添加到s1中剪枝階段：若某候選序列模式的某個(gè)子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除L1

C2

L2

C3

L3

C4

L4

……GSP算法序列合并過程

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

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

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

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

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

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

=<e1e2…en>，

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

=ei(i

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

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

=<(b)>的投影是’=<(b)(acd)>;<(ab)>的投影是原序列<(ab)(acd)>。基本概念后綴：序列關(guān)于子序列

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

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

L:序列模式的長度;

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

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

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

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

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

4<(8)>

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

sequence1<(1)(1,3)>

2<(3)(7)>

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

4<(8)>

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

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