序列模式挖掘

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

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

第六章序列模式挖掘

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

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

一個序列包含的所有單項的個數(shù)稱為序列的長度。長度為l的序列記為l-序列舉例例：一條序列<(10,20)30(40,60,70)>有3個元素，分別是（1020），30，（406070）；3個事務(wù)的發(fā)生時間是由前到后。這條序列是一個6-序列。基本概念設(shè)序列=<a1a2…an>，序列=<b1b2…bm>，ai和bi都是元素。如果存在整數(shù)1<=j1<j2<…<jn<=m，使得a1bj1，a2bj2，…，anbjn，則稱序列為序列的子序列，又稱序列包含序列，記為。序列在序列數(shù)據(jù)庫S中的支持度為序列數(shù)據(jù)庫S中包含序列的序列個數(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的序列模式序列模式先驗特性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)注點單項間在同一事務(wù)內(nèi)以及事務(wù)間的關(guān)系單項間在同一事務(wù)內(nèi)的關(guān)系序列模式挖掘算法概述類Apriori算法

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

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

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

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

定理1：如果規(guī)則不滿足置信度閾值，則形如 的規(guī)則一定也不滿足置信度閾值，其中X'是X的子集關(guān)聯(lián)規(guī)則挖掘的任務(wù)劃分：頻繁項集的產(chǎn)生（候選(產(chǎn)生)，剪枝（基于先驗原理））規(guī)則的產(chǎn)生(逐層方法來產(chǎn)生關(guān)聯(lián)規(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算法偽代碼：知識回顧支持度度量滿足單調(diào)性(X'為X的子集)置信度一般不滿足單調(diào)性(X'為X的子集)如果關(guān)聯(lián)規(guī)則產(chǎn)生自同一項集，則置信度滿足單調(diào)性知識回顧Prunedsupersets基于支持度的候選項集剪枝知識回顧PrunedRulesLowConfidenceRule基于置信度的候選規(guī)則剪枝GSP算法算法思想(候選產(chǎn)生測試法)：類似于Apriori算法，采用冗余候選模式的剪除策略和特殊的數(shù)據(jù)結(jié)構(gòu)-----哈希樹來實現(xiàn)候選模式的快速訪存。GSP算法描述掃描序列數(shù)據(jù)庫，得到長度為1的序列模式F1，作為初始的種子集根據(jù)長度為i的種子集Fi

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

C2

F2

C3

F3

C4

F4

……GSP算法偽代碼輸入：大項集階段轉(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的第一個元素與去掉序列模式s2的最后一個元素所得到的序列相同，則可以將s1與s2進(jìn)行連接，即將s2的最后一個元素添加到s1中剪枝階段：若某候選序列模式的某個子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除L1

C2

L2

C3

L3

C4

L4

……GSP算法序列合并過程

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

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

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

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

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

Pei,etal.@ICDE’01采用分治的思想，不斷產(chǎn)生序列數(shù)據(jù)庫的多個更小的投影數(shù)據(jù)庫，然后在各個投影數(shù)據(jù)庫上進(jìn)行序列模式挖掘知識回顧FP-Growth算法通過逐個讀入事務(wù)，并把每一個事務(wù)映射到FP樹中的一條路徑的方法構(gòu)造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基本概念前綴：設(shè)每個元素中的所有單項按照字典序排列。給定序列

=<e1e2…en>，

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

=ei(i

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

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

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

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

例：對于序列<(ab)(acd)>，其子序列<(b)>的投影是<(b)(acd)>，則<(ab)(acd)>對于<(b)>的后綴為<(acd)>。※總結(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中的一個序列模式，則的投影數(shù)據(jù)庫為S中所有以為前綴的序列相對于的后綴，記為S|投影數(shù)據(jù)庫中的支持度：設(shè)為序列數(shù)據(jù)庫S中的一個序列，序列以為前綴，則在的投影數(shù)據(jù)庫S|中的支持度為S|中滿足條件.的序列的個數(shù)舉例例：對于如下的序列數(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)造不同前綴所對應(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的序列模式為止分別對不同的投影數(shù)據(jù)庫重復(fù)上述過程，直到?jīng)]有新的長度為1的序列模式產(chǎn)生為止SS1…SmS11………S1n……Sm1………Smp……算法偽碼PrefixSpan算法輸入：序列數(shù)據(jù)庫S及最小支持度閾值min_sup輸出：所有的序列模式方法：去除所有非頻繁的項目，然后調(diào)用子程序PrefixSpan(<>,0,S)算法偽碼子程序PrefixSpan(,L,S|)參數(shù)：:一個序列模式;

L:序列模式的長度;

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

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

sequence1<(1)(1,3)>

2<(3)(7)>

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

4<(8)>

舉例為頻繁1序列（頻繁單項）生成投影數(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序列（頻繁單項）生成投影數(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ù)庫中還有頻繁單項_3，前綴<(3)>的投影數(shù)據(jù)庫中還有頻繁單項7.生成頻繁2序列<(1,3)>，<(3)(7)>,然后為其生成投影數(shù)據(jù)庫.其中沒有頻繁項目，算法終止。SidSuffixforprefix<(1,3)>1<>3<(8)(7)>SidSuffixforprefix<(3)(7)>2<>3<>PrefixSpan算法分析PrefixSpan算法不需要產(chǎn)生候選序列模式，從而大大縮減了檢索空間相對于原始的序列數(shù)據(jù)庫而言，投影數(shù)據(jù)庫的規(guī)模不斷減小PrefixSpan算法的主要開銷在于投影數(shù)據(jù)庫的構(gòu)造?？梢酝ㄟ^偽投影技術(shù)進(jìn)行效率提升。偽投影當(dāng)數(shù)據(jù)庫可以直接放入內(nèi)存時，并不需要構(gòu)造所有的序列模式對應(yīng)的投影數(shù)據(jù)庫，我們可以使用指向數(shù)據(jù)庫中序列的指針及其偏移量作為偽投影例子：假設(shè)上述序列數(shù)據(jù)庫可以放入內(nèi)存，在構(gòu)造a投影數(shù)據(jù)庫時，序列S1=<a(abc)(ac)d(cf)>所對應(yīng)的偽投影為：一個指向S1的指針，指針偏移設(shè)定為2。同樣的，序列S1的<ab>投影數(shù)據(jù)庫對應(yīng)的偽投影為：一個指向S1的指針，指針偏移設(shè)定為4偽投影與物理投影對比偽投影避免了物理投影拷貝后綴的過程當(dāng)數(shù)據(jù)庫可以存放入主內(nèi)存中，偽投影在時間和空間上都是很高效的但是當(dāng)數(shù)據(jù)庫不可以放入內(nèi)存中時，偽投影技術(shù)是非常低效的硬盤隨機訪問時很低效的建議策略:集成偽投影和物理投影技術(shù)當(dāng)數(shù)據(jù)集可以放入內(nèi)存時候，使用偽投影技術(shù)算法效率比較偽投影與物理投影比較閉序列模式挖掘閉序列模式：如果不存在序列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'之間的序列關(guān)系都有s<s'；(項集擴展小于序列擴展)如果s=a?ip，s'=a?ip'，p<p'則有s<s'；(同種擴展與后綴大小相關(guān))如果s=a?sp，同時s'=a?sp'，p<p'則s<s'；舉例：<(ab)><<(ab)(a)>,<(ab)><<(a)(b)>字典序序列樹構(gòu)造字典序序列樹構(gòu)造示例示例PrefixSpan算法PrefixSpan算法特點：在前綴搜索樹上搜索所有的頻繁項集終止條件：序列s的投影數(shù)據(jù)庫中序列的個數(shù)小于min_sup優(yōu)化策略引理1：給定一個子序列s和它的投影數(shù)據(jù)庫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)>的序列都不可能是閉序列。因此我們不需要構(gòu)造序列s?e優(yōu)化策略引理2：給定一個序列s和它的投影數(shù)據(jù)庫Ds.如果存在a，對Ds中所有序列項a總是出現(xiàn)在項b之前（無論他們是在同一個元素中還是不同元素中），那么Ds?a?b=Ds?b。因此對于任意的r，s?b?r不可能是閉序列。則不需要搜索分支s?b優(yōu)化策略投影數(shù)據(jù)庫等價性優(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的一個向后子模式舉例：對于如下序列數(shù)據(jù)庫有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的一個向后超模式舉例：對于如下序列數(shù)據(jù)庫有L(D<(b)>)=L(D<(e)(b)>)，則可以得出D<(b)>=D<(e)(b)>.即：不需要增長序列<(e)(b)>,因為<(e)(b)>的投影數(shù)據(jù)庫與<(b)>的投影數(shù)據(jù)