序列模式挖掘算法課件

第4章序列模式挖掘算法1/9/20231第4章序列模式挖掘算法1/7/20231主要內(nèi)容序列模式挖掘簡(jiǎn)介序列模式挖掘的應(yīng)用背景序列模式挖掘算法概述GSP算法PrefixSpan算法Disc-all算法支持約束的序列模式挖掘1/9/20232主要內(nèi)容序列模式挖掘簡(jiǎn)介1/7/20232一、序列模式挖掘簡(jiǎn)介序列模式的概念最早是由Agrawal和Srikant提出的。動(dòng)機(jī)：大型連鎖超市的交易數(shù)據(jù)有一系列的用戶事務(wù)數(shù)據(jù)庫(kù)，每一條記錄包括用戶的ID，事務(wù)發(fā)生的時(shí)間和事務(wù)涉及的項(xiàng)目。如果能在其中挖掘涉及事務(wù)間關(guān)聯(lián)關(guān)系的模式，即用戶幾次購(gòu)買行為間的聯(lián)系，可以采取更有針對(duì)性的營(yíng)銷措施。

1/9/20233一、序列模式挖掘簡(jiǎn)介序列模式的概念最早是由Agrawal和S事務(wù)數(shù)據(jù)庫(kù)實(shí)例例：一個(gè)事務(wù)數(shù)據(jù)庫(kù)，一個(gè)事務(wù)代表一筆交易，一個(gè)單項(xiàng)代表交易的商品，單項(xiàng)屬性中的數(shù)字記錄的是商品ID1/9/20234事務(wù)數(shù)據(jù)庫(kù)實(shí)例例：一個(gè)事務(wù)數(shù)據(jù)庫(kù)，一個(gè)事務(wù)代序列數(shù)據(jù)庫(kù)一般為了方便處理，需要把數(shù)據(jù)庫(kù)轉(zhuǎn)化為序列數(shù)據(jù)庫(kù)。方法是把用戶ID相同的記錄合并，有時(shí)每個(gè)事務(wù)的發(fā)生時(shí)間可以忽略，僅保持事務(wù)間的偏序關(guān)系。1/9/20235序列數(shù)據(jù)庫(kù)一般為了方便處理，需要把數(shù)問(wèn)題定義項(xiàng)集(Itemset)是所有在序列數(shù)據(jù)庫(kù)出現(xiàn)過(guò)的單項(xiàng)組成的集合例：對(duì)一個(gè)用戶購(gòu)買記錄的序列數(shù)據(jù)庫(kù)來(lái)說(shuō)，項(xiàng)集包含用戶購(gòu)買的所有商品，一種商品就是一個(gè)單項(xiàng)。通常每個(gè)單項(xiàng)有一個(gè)唯一的ID，在數(shù)據(jù)庫(kù)中記錄的是單項(xiàng)的ID。1/9/20236問(wèn)題定義1/7/20236問(wèn)題定義元素(Element)可表示為(x1x2…xm)，xk(1<=k<=m)為不同的單項(xiàng)。元素內(nèi)的單項(xiàng)不考慮順序關(guān)系，一般默認(rèn)按照ID的字典序排列．在用戶事務(wù)數(shù)據(jù)庫(kù)里，一個(gè)事務(wù)就是一個(gè)元素。1/9/20237問(wèn)題定義1/7/20237問(wèn)題定義序列(Sequence)是不同元素(Element)的有序排列，序列s可以表示為s=<s1s2…sl>，sj(1<=j<=l)為序列s的元素

一個(gè)序列包含的所有單項(xiàng)的個(gè)數(shù)稱為序列的長(zhǎng)度。長(zhǎng)度為l的序列記為l-序列1/9/20238問(wèn)題定義序列(Sequence)是不

例：一條序列<(10,20)30(40,60,70)>有3個(gè)元素，分別是（1020），30，（406070）；3個(gè)事務(wù)的發(fā)生時(shí)間是由前到后。這條序列是一個(gè)6-序列。1/9/202391/7/20239問(wèn)題定義設(shè)序列=<a1a2…an>，序列=<b1b2…bm>，ai和bi都是元素。如果存在整數(shù)1<=j1<j2<…<jn<=m，使得a1bj1，a2bj2，…，anbjn，則稱序列為序列的子序列，又稱序列包含序列，記為。1/9/202310問(wèn)題定義1/7/202310問(wèn)題定義序列在序列數(shù)據(jù)庫(kù)S中的支持度為序列數(shù)據(jù)庫(kù)S中包含序列的序列個(gè)數(shù)，記為Support()給定支持度閾值，如果序列在序列數(shù)據(jù)庫(kù)中的支持?jǐn)?shù)不低于，則稱序列為序列模式長(zhǎng)度為l的序列模式記為l-模式1/9/202311問(wèn)題定義序列在序列數(shù)據(jù)庫(kù)S中的支持度

例子：設(shè)序列數(shù)據(jù)庫(kù)如下圖所示，并設(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>是長(zhǎng)度為3的序列模式1/9/202312例子：設(shè)序列數(shù)據(jù)庫(kù)如下圖所示，并設(shè)用戶指定的最小支持度mi序列模式VS關(guān)聯(lián)規(guī)則問(wèn)題序列模式挖掘關(guān)聯(lián)規(guī)則挖掘數(shù)據(jù)集序列數(shù)據(jù)庫(kù)事務(wù)數(shù)據(jù)庫(kù)關(guān)注點(diǎn)單項(xiàng)間在同一事務(wù)內(nèi)以及事務(wù)間的關(guān)系單項(xiàng)間在同一事務(wù)內(nèi)的關(guān)系1/9/202313序列模式VS關(guān)聯(lián)規(guī)則問(wèn)題序列模式挖掘關(guān)二、序列模式挖掘的應(yīng)用背景應(yīng)用領(lǐng)域：客戶購(gòu)買行為模式預(yù)測(cè)Web訪問(wèn)模式預(yù)測(cè)疾病診斷自然災(zāi)害預(yù)測(cè)DNA序列分析1/9/202314二、序列模式挖掘的應(yīng)用背景應(yīng)用領(lǐng)域：1/7/202314應(yīng)用案例1：客戶購(gòu)買行為模式分析B2C電子商務(wù)網(wǎng)站可以根據(jù)客戶購(gòu)買紀(jì)錄來(lái)分析客戶購(gòu)買行為模式，從而進(jìn)行有針對(duì)性的營(yíng)銷策略。IDUsertransactionsequence1…………..2………………3……………………..4………………….圖書交易網(wǎng)站將用戶購(gòu)物紀(jì)錄整合成用戶購(gòu)物序列集合得到用戶購(gòu)物行為序列模式<(“UML語(yǔ)言”)(“Visio2003實(shí)用技巧”)>相關(guān)商品推薦：如果用戶購(gòu)買了書籍“UML語(yǔ)言”,則推薦“Visio2003實(shí)用技巧”1/9/202315應(yīng)用案例1：客戶購(gòu)買行為模式分析B2C電子商務(wù)網(wǎng)站可以根據(jù)客應(yīng)用案例2：Web訪問(wèn)模式分析大型網(wǎng)站的網(wǎng)站地圖(sitemap)往往具有復(fù)雜的拓?fù)浣Y(jié)構(gòu)。用戶訪問(wèn)序列模式的挖掘有助于改進(jìn)網(wǎng)站地圖的拓?fù)浣Y(jié)構(gòu)。比如用戶經(jīng)常訪問(wèn)網(wǎng)頁(yè)web1然后訪問(wèn)web2,而在網(wǎng)站地圖中二者距離較遠(yuǎn)，就有必要調(diào)整網(wǎng)站地圖，縮短它們的距離，甚至直接增加一條鏈接。Index網(wǎng)站入口web1web21/9/202316應(yīng)用案例2：Web訪問(wèn)模式分析大型網(wǎng)站的網(wǎng)站地圖(site應(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í)庫(kù)后，專家系統(tǒng)就可以依此來(lái)輔助人類專家進(jìn)行疾病診斷。1/9/202317應(yīng)用案例3：疾病診斷1/7/202317應(yīng)用案例3：疾病診斷例:通過(guò)分析大量曾患A類疾病的病人發(fā)病紀(jì)錄，發(fā)現(xiàn)以下癥狀發(fā)生的序列模式：<(眩暈)(兩天后低燒37-38度)>如果病人具有以上癥狀，則有可能患A類疾病1/9/202318應(yīng)用案例3：疾病診斷1/7/202318應(yīng)用案例4：查詢擴(kuò)展查詢擴(kuò)展是搜索領(lǐng)域一個(gè)重要的問(wèn)題。用戶提交的查詢往往不能完全反映其信息需求。一些研究工作嘗試用用戶的查詢序列模式來(lái)輔助原始查詢，其主要思想是：1）挖掘用戶的查詢序列模式2）用這些序列模式構(gòu)造查詢?cè)~關(guān)系圖3）找到每個(gè)極大全連通圖作為一個(gè)”概念”4)對(duì)于一個(gè)查詢，和它同處于一個(gè)”概念”的查詢可以作為查詢擴(kuò)展的選項(xiàng)1/9/202319應(yīng)用案例4：查詢擴(kuò)展查詢擴(kuò)展是搜索領(lǐng)域一個(gè)重要的問(wèn)題。用戶提應(yīng)用案例4：查詢擴(kuò)展給定一組查詢模式：<(豐田)(雷諾)>,<(寶馬)(豐田)>,<(豐田)(寶馬)>,<(寶馬)(雷諾)>,<(汽車)(豐田)>查詢關(guān)系圖如上圖：豐田雷諾寶馬汽車概念1：汽車品牌概念2：汽車1/9/202320應(yīng)用案例4：查詢擴(kuò)展豐田雷諾寶馬汽車概念1：汽車品牌概念2：三、序列模式挖掘算法概述Agrawal和Srikant在提出這個(gè)問(wèn)題時(shí)提出了三個(gè)算法，AprioriAll，AprioriSome和DynamicSome，它們都基于Apriori框架。構(gòu)成了序列模式挖掘問(wèn)題的基石。隨后，這個(gè)領(lǐng)域的研究工作取得了大量的成果。1/9/202321三、序列模式挖掘算法概述1/7/202321序列模式挖掘算法概述類Apriori算法基于劃分的模式生長(zhǎng)算法基于序列比較的算法1/9/202322序列模式挖掘算法概述1/7/202322

類Apriori算法該類算法基于Apriori理論，即序列模式的任一子序列也是序列模式。算法首先自底向上的根據(jù)較短的序列模式生成較長(zhǎng)的候選序列模式，然后計(jì)算候選序列模式的支持度。典型的代表有GSP算法,spade算法等。1/9/202323類Apriori算法1/7/202323 基于劃分的模式生長(zhǎng)算法該類算法基于分治的思想，迭代的將原始數(shù)據(jù)集進(jìn)行劃分，減少數(shù)據(jù)規(guī)模，同時(shí)在劃分的過(guò)程中動(dòng)態(tài)的挖掘序列模式，并將新發(fā)現(xiàn)的序列模式作為新的劃分元。典型的代表有FreeSpan算法和prefixSpan算法。1/9/202324 基于劃分的模式生長(zhǎng)算法1/7/202324 基于序列比較的算法該類算法首先定義序列的大小度量，接著從小到大的枚舉原始序列數(shù)據(jù)庫(kù)中包含的所有k-序列，理論上所有的k-序列模式都能被找到。算法制定特定的規(guī)則加快這種枚舉過(guò)程。典型的代表為Disc-all算法。1/9/202325 基于序列比較的算法1/7/202325四、GSP算法算法思想：類似于Apriori算法，采用冗余候選模式的剪除策略和特殊的數(shù)據(jù)結(jié)構(gòu)-----哈希樹來(lái)實(shí)現(xiàn)候選模式的快速訪存。1/9/202326四、GSP算法1/7/202326

GSP算法描述掃描序列數(shù)據(jù)庫(kù)，得到長(zhǎng)度為1的序列模式L1，作為初始的種子集根據(jù)長(zhǎng)度為i的種子集Li

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

C2

L2

C3

L3

C4

L4

……1/9/202327GSP算法描述掃描序列數(shù)據(jù)庫(kù)，得到長(zhǎng)度

產(chǎn)生候選序列模式主要分兩步：連接階段：如果去掉序列模式s1的第一個(gè)項(xiàng)目與去掉序列模式s2的最后一個(gè)項(xiàng)目所得到的序列相同，則可以將s1與s2進(jìn)行連接，即將s2的最后一個(gè)項(xiàng)目添加到s1中修切階段：若某候選序列模式的某個(gè)子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除L1

C2

L2

C3

L3

C4

L4

……1/9/202328產(chǎn)生候選序列模式主要分兩步：L1C2L2C

候選序列模式的支持度計(jì)算：對(duì)于給定的候選序列模式集合C，掃描序列數(shù)據(jù)庫(kù)，對(duì)于其中的每一條序列s,找出集合C中被s所包含的所有候選序列模式，并增加其支持度計(jì)數(shù)L1

C2

L2

C3

L3

……1/9/202329候選序列模式的支持度計(jì)算：對(duì)于給定的候選序列模式集合C，掃 哈希樹GSP采用哈希樹存儲(chǔ)候選序列模式。哈希樹的節(jié)點(diǎn)分為三類：1、根節(jié)點(diǎn)；2、內(nèi)部節(jié)點(diǎn)；3、葉子節(jié)點(diǎn)。

1/9/202330 哈希樹GSP采用哈希樹存儲(chǔ)候選序列模式。哈希樹的節(jié)點(diǎn)分哈希樹根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)中存放的是一個(gè)哈希表，每個(gè)哈希表項(xiàng)指向其它的節(jié)點(diǎn)。而葉子節(jié)點(diǎn)內(nèi)存放的是一組候選序列模式。例：1/9/202331哈希樹根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)中存放

添加候選序列模式從根節(jié)點(diǎn)開始，用哈希函數(shù)對(duì)序列的第一個(gè)項(xiàng)目做映射來(lái)決定從哪個(gè)分支向下，依次在第n層對(duì)序列的第n個(gè)項(xiàng)目作映射來(lái)決定從哪個(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)。

1/9/202332添加候選序列模式1/7/202332

計(jì)算候選序列模式的支持度給定一個(gè)序列s是序列數(shù)據(jù)庫(kù)的一個(gè)記錄：

1）對(duì)于根節(jié)點(diǎn)，用哈希函數(shù)對(duì)序列s的每一個(gè)單項(xiàng)做映射來(lái)并從相應(yīng)的表項(xiàng)向下迭代的進(jìn)行操作2）。

1/9/202333計(jì)算候選序列模式的支持度1/7/202333計(jì)算候選序列模式的支持度

2）對(duì)于內(nèi)部節(jié)點(diǎn)，如果s是通過(guò)對(duì)單項(xiàng)x做哈希映射來(lái)到此節(jié)點(diǎn)的，則對(duì)s中每一個(gè)和x在一個(gè)元素中的單項(xiàng)以及在x所在元素之后第一個(gè)元素的第一個(gè)單項(xiàng)做哈希映射，然后從相應(yīng)的表項(xiàng)向下迭代做操作2）或3）。1/9/202334計(jì)算候選序列模式的支持度1/7/202334計(jì)算候選序列模式的支持度（3）對(duì)一個(gè)葉子節(jié)點(diǎn)，檢查每個(gè)候選序列模式c是不是s的子序列.如果是相應(yīng)的候選序列模式支持度加一。這種計(jì)算候選序列的支持度的方法避免了大量無(wú)用的掃描，對(duì)于一條序列，僅檢驗(yàn)?zāi)切┳钣锌赡艹蔀樗有蛄械暮蜻x序列模式。掃描的時(shí)間復(fù)雜度由O(n*m)降為O(n*t),其中n表示序列數(shù)量，m表示候選序列模式的數(shù)量，t代表哈希樹葉子節(jié)點(diǎn)的最大容量1/9/202335計(jì)算候選序列模式的支持度（3）對(duì)一個(gè)葉子節(jié)點(diǎn)，檢查每個(gè)候

例：下圖演示了如何從長(zhǎng)度為3的序列模式產(chǎn)生長(zhǎng)度為4的候選序列模式SequentialpatternsWithlength3Candidate4-SequencesAfterJoinAfterPruning<(1,2)3><(1,2)(3,4)><(1,2)(3,4)><(1,2)4><(1,2)35><1(3,4)><(1,3)5><2(3,4)><235>1/9/202336例：下圖演示了如何從長(zhǎng)度為3的序列模式產(chǎn)生長(zhǎng)度為4的候選序

GSP算法存在的主要問(wèn)題如果序列數(shù)據(jù)庫(kù)的規(guī)模比較大，則有可能會(huì)產(chǎn)生大量的候選序列模式需要對(duì)序列數(shù)據(jù)庫(kù)進(jìn)行循環(huán)掃描對(duì)于序列模式的長(zhǎng)度比較長(zhǎng)的情況，由于其對(duì)應(yīng)的短的序列模式規(guī)模太大，本算法很難處理1/9/202337GSP算法存在的主要問(wèn)題1/7/202337五、PrefixSpan算法算法思想：采用分治的思想，不斷產(chǎn)生序列數(shù)據(jù)庫(kù)的多個(gè)更小的投影數(shù)據(jù)庫(kù)，然后在各個(gè)投影數(shù)據(jù)庫(kù)上進(jìn)行序列模式挖掘1/9/202338五、PrefixSpan算法算法思想：1/7/202338

相關(guān)定義前綴：設(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)>則不是。1/9/202339

相關(guān)定義1/7/ 相關(guān)定義投影：給定序列和，如果是的子序列，則關(guān)于的投影’必須滿足：是’的前綴，’是的滿足上述條件的最大子序列

例：對(duì)于序列=<(ab)(acd)>，其子序列=<(b)>的投影是’=<(b)(acd)>;<(ab)>的投影是原序列<(ab)(acd)>。1/9/202340 相關(guān)定義投影：給定序列和，如果是的子序列，則 相關(guān)定義后綴：序列關(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)>。1/9/202341 相關(guān)定義后綴：序列關(guān)于子序列=<e1e2…e

例：<a(abc)(ac)d(cf)><a><aa>a(ab)a(abc)<(abc)(ac)d(cf)><(_bc)(ac)d(cf)><ab><(_c)(ac)d(cf)>1/9/202342例：<a(abc)(ac)d(cf)><a><aa>a( 相關(guān)定義投影數(shù)據(jù)庫(kù)：設(shè)為序列數(shù)據(jù)庫(kù)S中的一個(gè)序列模式，則的投影數(shù)據(jù)庫(kù)為S中所有以為前綴的序列相對(duì)于的后綴，記為S|投影數(shù)據(jù)庫(kù)中的支持度：設(shè)為序列數(shù)據(jù)庫(kù)S中的一個(gè)序列，序列以為前綴，則在的投影數(shù)據(jù)庫(kù)S|中的支持度為S|中滿足條件.的序列的個(gè)數(shù)1/9/202343 相關(guān)定義投影數(shù)據(jù)庫(kù)：設(shè)為序列數(shù)據(jù)庫(kù)S中的一個(gè)序列模式，

算法描述掃描序列數(shù)據(jù)庫(kù)，生成所有長(zhǎng)度為1的序列模式根據(jù)長(zhǎng)度為1的序列模式，生成相應(yīng)的投影數(shù)據(jù)庫(kù)在相應(yīng)的投影數(shù)據(jù)庫(kù)上重復(fù)上述步驟，直到在相應(yīng)的投影數(shù)據(jù)庫(kù)上不能產(chǎn)生長(zhǎng)度為1的序列模式為止分別對(duì)不同的投影數(shù)據(jù)庫(kù)重復(fù)上述過(guò)程，直到?jīng)]有新的長(zhǎng)度為1的序列模式產(chǎn)生為止SS1…SmS11………S1n……Sm1………Smp……1/9/202344 算法描述SS1SmS11……S1n……Sm

例：對(duì)于如下的序列數(shù)據(jù)庫(kù)生成一系列的投影數(shù)據(jù)庫(kù)SidSequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<(af)cbc>1/9/202345例：對(duì)于如下的序列數(shù)據(jù)庫(kù)生成一系列的投影數(shù)據(jù)庫(kù)SidSeq

掃描序列數(shù)據(jù)庫(kù)S，產(chǎn)生長(zhǎng)度為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ù)庫(kù)，結(jié)果如下頁(yè)圖所示1/9/202346掃描序列數(shù)據(jù)庫(kù)S，產(chǎn)生長(zhǎng)度為1的序列模式有：<a>:4

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>1/9/202347PrefixProjectDatabase<a><(ab 算法偽碼PrefixSpan算法輸入：序列數(shù)據(jù)庫(kù)S及最小支持度閾值min_sup輸出：所有的序列模式方法：去除所有非頻繁的項(xiàng)目，然后調(diào)用子程序PrefixSpan(<>,0,S)1/9/202348 算法偽碼PrefixSpan算法1/7/202348

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

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

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

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

4<(8)>

給定如下的序列數(shù)據(jù)庫(kù)：1/9/202350Sidsequence1<(1,

找出頻繁單項(xiàng)：1，3，7，8；然后除去非頻繁的單項(xiàng)：Sidsequence1<(1)(1,3)>

2<(3)(7)>

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

4<(8)>

1/9/202351找出頻繁單項(xiàng)：1，3，7，8；然后除去非頻繁的單項(xiàng)：Sid

為頻繁1序列（頻繁單項(xiàng)）生成投影數(shù)據(jù)庫(kù)：SidSuffixforprefix<(1)>1<(1,3)>3<(_3)(8)(7)>SidSuffixforprefix<(3)>1<>2<(7)>3<(8)(7)>1/9/202352為頻繁1序列（頻繁單項(xiàng)）生成投影數(shù)據(jù)庫(kù)：SidSuffix

SidSuffixforprefix<(7)>2<>3<>SidSuffixforprefix<(8)>3<(7)>4<>1/9/202353SidSuffixforprefix<(7)>2<>

在上面的投影數(shù)據(jù)庫(kù)中，前綴<(1)>的投影數(shù)據(jù)庫(kù)中還有頻繁單項(xiàng)_3，前綴<(3)>的投影數(shù)據(jù)庫(kù)中還有頻繁單項(xiàng)7.生成頻繁2序列<(1,3)>，<(3)(7)>,然后為其生成投影數(shù)據(jù)庫(kù).其中沒有頻繁項(xiàng)目，算法終止。SidSuffixforprefix<(1,3)>1<>3<(8)(7)>SidSuffixforprefix<(3)(7)>2<>3<>1/9/202354在上面的投影數(shù)據(jù)庫(kù)中，前綴<(1)>的投影數(shù)據(jù)庫(kù)中還有頻繁PrefixSpan算法分析PrefixSpan算法不需要產(chǎn)生候選序列模式，從而大大縮減了檢索空間相對(duì)于原始的序列數(shù)據(jù)庫(kù)而言，投影數(shù)據(jù)庫(kù)的規(guī)模不斷減小PrefixSpan算法的主要開銷在于投影數(shù)據(jù)庫(kù)的構(gòu)造1/9/202355PrefixSpan算法分析PrefixSpan算法不PrefixSpan算法的主要改進(jìn)隔層投影：使用隔層投影代替逐層投影，從而可以有效減小投影數(shù)據(jù)庫(kù)的個(gè)數(shù)偽投影：當(dāng)序列數(shù)據(jù)庫(kù)可以直接放入內(nèi)存時(shí)，可以使用偽投影操作代替實(shí)際的投影數(shù)據(jù)庫(kù)，從而可以有效減少構(gòu)造投影數(shù)據(jù)庫(kù)的開銷1/9/202356PrefixSpan算法的主要改進(jìn)隔層投影：使用隔層投影代替 隔層投影掃描序列數(shù)據(jù)庫(kù)，產(chǎn)生所有長(zhǎng)度為1的序列模式再次掃描序列數(shù)據(jù)庫(kù)，構(gòu)造如下圖所示的下三角矩陣，得到所有長(zhǎng)度為2的序列模式構(gòu)造長(zhǎng)度為2的序列模式所對(duì)應(yīng)的掃描數(shù)據(jù)庫(kù)，然后對(duì)每個(gè)投影數(shù)據(jù)庫(kù)，重復(fù)上面的操作，直到?jīng)]有新的序列模式產(chǎn)生為止SidSequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<(af)cbc>1/9/202357 隔層投影SidSequence10<a(abc)(ac)

a2b(4,2,2)1c(4,2,1)(3,3,2)3d(2,1,1)(2,2,0)(1,3,0)0e(1,2,1)(1,2,0)(1,2,0)(1,1,0)0f(2,1,1)(2,2,0)(1,2,1)(1,1,1)(2,0,1)1abcdef1/9/202358a2b(4,2,2)1c(4,2,1)(3,3,2)3d(

偽投影當(dāng)數(shù)據(jù)庫(kù)可以直接放入內(nèi)存時(shí)，并不需要構(gòu)造所有的序列模式對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)，我們可以使用指向數(shù)據(jù)庫(kù)中序列的指針及其偏移量作為偽投影例子：假設(shè)上述序列數(shù)據(jù)庫(kù)可以放入內(nèi)存，在構(gòu)造a投影數(shù)據(jù)庫(kù)時(shí)，序列S1=<a(abc)(ac)d(cf)>所對(duì)應(yīng)的偽投影為：一個(gè)指向S1的指針，指針偏移設(shè)定為2。同樣的，序列S1的<ab>投影數(shù)據(jù)庫(kù)對(duì)應(yīng)的偽投影為：一個(gè)指向S1的指針，指針偏移設(shè)定為41/9/202359 偽投影當(dāng)數(shù)據(jù)庫(kù)可以直接放入內(nèi)存時(shí)，并不需要構(gòu)造所有的序六、Disc-all算法算法思想：Disc-all算法采用了Disc（Directsequencecomparing)策略。其核心思想是對(duì)于給定的k和所有k-1序列模式，通過(guò)枚舉所有合適的k序列發(fā)現(xiàn)k-序列模式。通過(guò)引入適當(dāng)?shù)拿杜e策略保證算法效率。1/9/202360六、Disc-all算法算法思想：1/7/202360 相關(guān)定義給定兩條l-序列和,如果>

，那么下列條件必滿足其一： 1）,的第m項(xiàng)>的第m項(xiàng)且與在其第m項(xiàng)之前的部分完全相同2）,的第m項(xiàng)=的第m項(xiàng)但的第m項(xiàng)和第m-1項(xiàng)不在同一元素中而的第m項(xiàng)則相反，并且與在其第m項(xiàng)之前的部分完全相同1/9/202361 相關(guān)定義給定兩條l-序列和,如果>，那么

例：<(a,b)c>小于<acb>因?yàn)闂l件1),<(a,b)c>小于<abb>

因?yàn)闂l件2).定義序列的大小關(guān)系只是為了給序列排序，這種大小度量是相對(duì)的，沒有真正的物理意義1/9/2023621/7/202362 相關(guān)定義一條l-序列序列所有長(zhǎng)度為k的子序列（1kl)中最小的一條叫做這條序列的k-最小序列.給定k-序列c為條件序列，一條l-序列序列所有大于c的長(zhǎng)度為k的子序列（1kl)中最小的一條叫做這條序列的k-條件最小序列.1/9/202363 相關(guān)定義一條l-序列序列所有長(zhǎng)度為k的子序列（1kDisc-all算法概述該算法首先劃分?jǐn)?shù)據(jù)庫(kù)，然后在劃分?jǐn)?shù)據(jù)庫(kù)上執(zhí)行迭代的執(zhí)行Disc策略，即基于序列比較的序列模式枚舉過(guò)程：首先通過(guò)適當(dāng)?shù)拿杜e找到所有的k-序列模式，然后根據(jù)k-序列模式找到所有的k+1序列模式。1/9/202364Disc-all算法概述1/7/202364數(shù)據(jù)庫(kù)劃分Disc-all算法對(duì)原始序列數(shù)據(jù)庫(kù)進(jìn)行兩層劃分：一層劃分：首先找到所有的頻繁單項(xiàng)并刪除所有的非頻繁單項(xiàng)，然后進(jìn)行一級(jí)劃分，即對(duì)于每個(gè)頻繁單項(xiàng)i，找到所有包含它的序列組成i劃分。二層劃分：找到所有的2-序列模式并刪除所有的非頻繁2-序列，然后進(jìn)行二級(jí)劃分，即對(duì)于每個(gè)2-序列模式，找到所有包含它的序列。1/9/202365數(shù)據(jù)庫(kù)劃分Disc-all算法對(duì)原始序

SidSequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<(af)cbc>例：對(duì)如下數(shù)據(jù)庫(kù)進(jìn)行兩層劃分，給定最小支持度2，首先找到所有的頻繁單項(xiàng)：a,b,c,d,e,f1/9/202366SidSequence10<a(abc)(ac)d(cf)生成一層劃分?jǐn)?shù)據(jù)庫(kù)下面給出了每個(gè)頻繁單項(xiàng)的一層劃分?jǐn)?shù)據(jù)庫(kù)：頻繁單項(xiàng)劃分?jǐn)?shù)據(jù)庫(kù)a<a(abc)(ac)d(cf)><(ad)c(bc)(ae)><(ef)(ab)(df)cb><(af)cbc>b<a(abc)(ac)d(cf)><(ad)c(bc)(ae)><(ef)(ab)(df)cb><(af)cbc>c<a(abc)(ac)d(cf)><(ad)c(bc)(ae)><(ef)(ab)(df)cb><(af)cbc>d<a(abc)(ac)d(cf)><(ad)c(bc)(ae)><(ef)(ab)(df)cb>e<(ad)c(bc)(ae)><(ef)(ab)(df)cb>f<a(abc)(ac)d(cf)><(ef)(ab)(df)cb><(af)cbc>1/9/202367生成一層劃分?jǐn)?shù)據(jù)庫(kù)下面給出了每個(gè)頻繁單項(xiàng)的一層劃

在a-劃分?jǐn)?shù)據(jù)庫(kù)里找到所有第一項(xiàng)為a的2-序列模式：<aa><(ab)><ab><ac><ad><af>，并刪除非頻繁的以a開頭的2-序列。刪除規(guī)則為：1）如果單項(xiàng)i和a在同一元素內(nèi)且<(ai)>是2-序列模式;2）如果單項(xiàng)i和a不在同一元素內(nèi)且<ai>是2-序列模式;當(dāng)條件1),2)全都不滿足時(shí)刪除i.1/9/202368在a-劃分?jǐn)?shù)據(jù)庫(kù)里找到所有第一項(xiàng)為a的2-序列模式：<aa生成二層劃分?jǐn)?shù)據(jù)庫(kù)下面只給出根據(jù)a-劃分找到的2-序列模式及其二層劃分?jǐn)?shù)據(jù)庫(kù)，注意所有的非頻繁2-序列已經(jīng)被刪除。頻繁單項(xiàng)劃分?jǐn)?shù)據(jù)庫(kù)<aa><a(abc)(ac)d(cf)><ac(bc)a><(ab)><a(abc)(ac)d(cf)><(ab)(df)cb><ab><a(abc)(ac)d(cf)><ac(bc)a><(ab)(df)cb><acbc><ac><a(abc)(ac)d(cf)><ac(bc)a><(ab)(df)cb><acbc><ad><a(abc)(ac)d(cf)><(ab)(df)cb><af><a(abc)(ac)d(cf)><(ab)(df)cb>1/9/202369生成二層劃分?jǐn)?shù)據(jù)庫(kù)下面只給出根據(jù)a-劃分找到的Disc策略對(duì)于每一個(gè)劃分?jǐn)?shù)據(jù)庫(kù)，給定一組k-序列模式集合S，Disc策略通過(guò)枚舉找到所有的k+1-序列模式。枚舉過(guò)程如下：1)對(duì)于每個(gè)序列s,找到s的最小的k+1-子序列s’,且s’的k前綴S，將s’加入k+1序列集，記錄s’的源序列s1/9/202370Disc策略對(duì)于每一個(gè)劃分?jǐn)?shù)據(jù)庫(kù) Disc策略2)對(duì)k+1序列集排序，設(shè)最小支持度為δ，排序后第δ個(gè)序列稱為條件序列。3)如果第一個(gè)序列和條件序列相等，則輸出條件序列為一個(gè)k+1-序列模式，并且將所有k+1序列替換為它們?cè)葱蛄械臈l件最小k+1-序列。否則盡可能將所有k+1序列替換為條件序列，對(duì)于源序列中不含條件序列的k+1序列則替換為條件最小k+1-序列1/9/202371 Disc策略2)對(duì)k+1序列集排序，設(shè)最小支持度為Disc策略4）重復(fù)上述步驟直到k+1序列集包含的序列數(shù)目小于δ。Disc策略迭代的根據(jù)k-序列模式集找到k+1-序列模式集，然后遞增k.直到?jīng)]有k+1-序列模式集為空，算法終止。Disc-all算法從從k=2時(shí)開始采用Disc策略。1/9/202372Disc策略1/7/202372Disc策略由于Disc-all算法是在劃分?jǐn)?shù)據(jù)庫(kù)上采用Disc策略，對(duì)于一個(gè)<i1i2>的劃分，Disc策略只尋找所有以<i1i2>為前綴的序列模式?；貞浿坝懻摰膒refixSpan算法，可以發(fā)現(xiàn)在這一點(diǎn)上二者非常相似。都是基于前綴生長(zhǎng)的思想。不同的是prefixSpan采用遞歸而Disc-all算法采用迭代。1/9/202373Disc策略由于Disc-all

考慮前面的序列數(shù)據(jù)庫(kù)，對(duì)于右側(cè)的一個(gè)基于<ab>二層劃分，仍然給定最小支持度為2，下面的例子展示了Disc策略是如何找到以3-序列模式的

SidSequence10<a(abc)(ac)d(cf)>20<ac(bc)a>30<(ab)(df)cb>40<acbc>1/9/202374考慮前面的序列數(shù)據(jù)庫(kù)，對(duì)于右側(cè)的一個(gè)基于<ab>二層劃分，初始化3-序列集Sid3-Sequence10<abc>40<abc>20<acb>可以看出<a(bc)>是一條3序列模式。Sid為30的序列沒有產(chǎn)生初始3-序列因?yàn)槠洳话?lt;ab>為前綴的3-子序列Sid3-Sequence10<a(bc)>20<a(bc)>40<abc><a(bc)>為條件序列，將所有3-序列替換為源序列的條件3-最小序列并重新排序，又發(fā)現(xiàn)一條3-序列模式<abc>1/9/202375初始化3-序列集Sid3-Sequen

Sid3-Sequence40<acb>20<acb>10<acd>用新的條件最小3-序列替換各3-序列并排序，3-序列數(shù)據(jù)集如右側(cè)所示。這一次沒有新的3-序列模式被發(fā)現(xiàn)。Sid3-Sequence10<abd>40<acb>20<acb>用新的條件序列<acb>替換各3-序列并排序，3-序列數(shù)據(jù)集如右側(cè)所示。發(fā)現(xiàn)新的3-序列模式<acb>.注意Sid為10的序列不含<acb>,所以用條件最小3-序列<acd>替換。1/9/202376Sid3-Sequence40<acb>20<acb>10

重復(fù)上面的步驟，可以發(fā)現(xiàn)新的3-序列模式<acc>.這時(shí)只有Sid為10的序列含有比<acc>更大的3-序列，所以算法停止。Sid3-Sequence40<acc>20<acc>10<acd>1/9/202377Sid3-Sequence40<acc>20<acc>10 Disc-all算法分析Disc-all算法同樣不生成候選序列模式，減少了計(jì)算開銷。同時(shí)采用劃分技術(shù),減少了搜索空間。應(yīng)用Disc策略，解決了劃分效率隨劃分層次增加而下降的問(wèn)題。Disc-all采用的劃分技術(shù)不如prefixSpan高效，而且Disc策略較為復(fù)雜耗時(shí)，算法效率往往不及prefixSpan，但在處理長(zhǎng)序列數(shù)據(jù)集時(shí)，因?yàn)镈isc策略沒有迭代開銷同時(shí)投影技術(shù)效率有所下降，Disc-all表現(xiàn)反而更好。1/9/202378 Disc-all算法分析Disc-all算法同樣不生成候選Disc-all和prefixSpan的性能比較平均序列長(zhǎng)度為20時(shí)，Disc-all和prefixSpan的性能比較1/9/202379Disc-all和prefixSpan的性能比較平均序列Disc-all和prefixSpan的性能比較平均序列長(zhǎng)度為80時(shí)，Disc-all和prefixSpan的性能比較1/9/202380Disc-all和prefixSpan的性能比較平均序列長(zhǎng)度

用戶需要的往往是滿足特定條件的序列模式，而傳統(tǒng)的序列模式挖掘沒有考慮用戶的特殊要求，做了大量無(wú)效的挖掘。比如對(duì)于購(gòu)買記錄的事務(wù)數(shù)據(jù)庫(kù)，用戶希望得到的序列模式事務(wù)之間的時(shí)間差不能太大。

七、支持約束的序列模式挖掘

1/9/2023811/7/202381

解決辦法引入約束的概念。在約束條件下做符合用戶要求的序列模式挖掘。一方面利用特定約束本身的性質(zhì)節(jié)省了挖掘的時(shí)間和空間，另一方面避免用戶陷入大量的無(wú)用信息。1/9/202382 解決辦法1/7/202382

約束的分類單調(diào)約束：如果一個(gè)序列滿足，那么這個(gè)序列的所有超序列也滿足的約束；反單調(diào)約束：如果一個(gè)序列滿足，那么這個(gè)序列的任意子序列也滿足的約束；簡(jiǎn)潔約束：用特定規(guī)則挖掘的約束；還有一些無(wú)法歸為以上三類的約束，一般被稱為強(qiáng)約束（toughconstraints.）比如時(shí)間性約束。1/9/202383 約束的分類1/7/202383一些常用的約束約束分類描述單項(xiàng)蘊(yùn)含約束單調(diào)約束目標(biāo)序列模式必須包含某些單項(xiàng)持續(xù)時(shí)間約束反單調(diào)約束目標(biāo)序列模式的第一個(gè)元素和最后一個(gè)元素間的時(shí)間間隔不大于某個(gè)閾值間隔約束強(qiáng)約束目標(biāo)序列模式的任意連續(xù)兩個(gè)元素間的時(shí)間間隔不大于某個(gè)閾值均值約束強(qiáng)約束如果每個(gè)單項(xiàng)被賦予一個(gè)表示重要性的權(quán)值，目標(biāo)序列模式的平均值大于某個(gè)閾值1/9/202384一些常用的約束約束分類描述單項(xiàng)蘊(yùn)含約束單調(diào)約支持約束的序列模式挖掘算法在支持約束的模式序列挖掘領(lǐng)域內(nèi)產(chǎn)生了大量的成果。主要有兩類，一類是針對(duì)特定的約束，如針對(duì)單調(diào)性約束的ExAnte,針對(duì)Gap約束的CCSM,另一類是提出一個(gè)通用的框架，可以針對(duì)不同的約束采用不同的策略，如PrefixGrowth.1/9/202385支持約束的序列模式挖掘算法1/7/202385ExAnte算法ExAnte實(shí)際上是一種數(shù)據(jù)預(yù)處理方法，它首先刪除所有不滿足約束條件的序列，然后刪除所有在新的序列數(shù)據(jù)庫(kù)中非頻繁的單項(xiàng)。處理后的數(shù)據(jù)集可以應(yīng)用任何序列模式挖掘方法。1/9/202386ExAnte算法1/7/202386

例：給定最小支持度2和約束

Sum(P)>4，（目標(biāo)序列模式的總值大于4），考慮右側(cè)的序列數(shù)據(jù)庫(kù),單項(xiàng)后的數(shù)字代表權(quán)值。SidSequence10<c.1(a.1,b.2,c.1)(d.2,c.1)>20<(a.1,d.2)c.1>30<c.1,b.2,d.2>40<(a.1,c.1)c.1>1/9/202387例：給定最小支持度2和約束Sum(P)>4，（目標(biāo)序列模

從表中可以看出，Sid為20，40的序列不滿足給定的約束，可以被刪除。刪除后頻繁單項(xiàng)為c,b,d.a被刪除。得到如下的數(shù)據(jù)集：同原數(shù)據(jù)集相比，數(shù)據(jù)規(guī)模大大減少SidSequence10<c.1(b.2,c.1)(d.2,c.1)>30<c.1,b.2,d.2>1/9/202388從表中可以看出，Sid為20，40的序列不滿足給定的約束， PrefixGrowth算法PrefixGrowth算法以prefixSpan算法為框架，將約束處理機(jī)制整合到前綴增長(zhǎng)的過(guò)程中。在為前綴構(gòu)造投影數(shù)據(jù)庫(kù)之前，首先啟用相應(yīng)的約束機(jī)制檢查前綴是否有可能擴(kuò)展為滿足約束條件的序列模式。1/9/202389 PrefixGrowth算法1/7/202389 處理單調(diào)約束對(duì)于單調(diào)約束，PrefixGrowth算法對(duì)于每一個(gè)前綴找到其最長(zhǎng)的投影，如果該投影滿足單調(diào)約束，則為此前綴構(gòu)造投影數(shù)據(jù)庫(kù)，否則直接刪除此前綴。1/9/202390 處理單調(diào)約束1/7/202390處理強(qiáng)約束對(duì)于強(qiáng)約束，PrefixGrowth沒有提供統(tǒng)一的處理策略，只是討論了兩種常見的強(qiáng)約束：均值約束和總值約束的處理。這是因?yàn)閺?qiáng)約束本身不具有內(nèi)在的統(tǒng)一性，只是一些難于處理約束的別稱。1/9/202391處理強(qiáng)約束1/7/202391

Thanks!1/9/2023921/第4章序列模式挖掘算法1/9/202393第4章序列模式挖掘算法1/7/20231主要內(nèi)容序列模式挖掘簡(jiǎn)介序列模式挖掘的應(yīng)用背景序列模式挖掘算法概述GSP算法PrefixSpan算法Disc-all算法支持約束的序列模式挖掘1/9/202394主要內(nèi)容序列模式挖掘簡(jiǎn)介1/7/20232一、序列模式挖掘簡(jiǎn)介序列模式的概念最早是由Agrawal和Srikant提出的。動(dòng)機(jī)：大型連鎖超市的交易數(shù)據(jù)有一系列的用戶事務(wù)數(shù)據(jù)庫(kù)，每一條記錄包括用戶的ID，事務(wù)發(fā)生的時(shí)間和事務(wù)涉及的項(xiàng)目。如果能在其中挖掘涉及事務(wù)間關(guān)聯(lián)關(guān)系的模式，即用戶幾次購(gòu)買行為間的聯(lián)系，可以采取更有針對(duì)性的營(yíng)銷措施。

1/9/202395一、序列模式挖掘簡(jiǎn)介序列模式的概念最早是由Agrawal和S事務(wù)數(shù)據(jù)庫(kù)實(shí)例例：一個(gè)事務(wù)數(shù)據(jù)庫(kù)，一個(gè)事務(wù)代表一筆交易，一個(gè)單項(xiàng)代表交易的商品，單項(xiàng)屬性中的數(shù)字記錄的是商品ID1/9/202396事務(wù)數(shù)據(jù)庫(kù)實(shí)例例：一個(gè)事務(wù)數(shù)據(jù)庫(kù)，一個(gè)事務(wù)代序列數(shù)據(jù)庫(kù)一般為了方便處理，需要把數(shù)據(jù)庫(kù)轉(zhuǎn)化為序列數(shù)據(jù)庫(kù)。方法是把用戶ID相同的記錄合并，有時(shí)每個(gè)事務(wù)的發(fā)生時(shí)間可以忽略，僅保持事務(wù)間的偏序關(guān)系。1/9/202397序列數(shù)據(jù)庫(kù)一般為了方便處理，需要把數(shù)問(wèn)題定義項(xiàng)集(Itemset)是所有在序列數(shù)據(jù)庫(kù)出現(xiàn)過(guò)的單項(xiàng)組成的集合例：對(duì)一個(gè)用戶購(gòu)買記錄的序列數(shù)據(jù)庫(kù)來(lái)說(shuō)，項(xiàng)集包含用戶購(gòu)買的所有商品，一種商品就是一個(gè)單項(xiàng)。通常每個(gè)單項(xiàng)有一個(gè)唯一的ID，在數(shù)據(jù)庫(kù)中記錄的是單項(xiàng)的ID。1/9/202398問(wèn)題定義1/7/20236問(wèn)題定義元素(Element)可表示為(x1x2…xm)，xk(1<=k<=m)為不同的單項(xiàng)。元素內(nèi)的單項(xiàng)不考慮順序關(guān)系，一般默認(rèn)按照ID的字典序排列．在用戶事務(wù)數(shù)據(jù)庫(kù)里，一個(gè)事務(wù)就是一個(gè)元素。1/9/202399問(wèn)題定義1/7/20237問(wèn)題定義序列(Sequence)是不同元素(Element)的有序排列，序列s可以表示為s=<s1s2…sl>，sj(1<=j<=l)為序列s的元素

一個(gè)序列包含的所有單項(xiàng)的個(gè)數(shù)稱為序列的長(zhǎng)度。長(zhǎng)度為l的序列記為l-序列1/9/2023100問(wèn)題定義序列(Sequence)是不

例：一條序列<(10,20)30(40,60,70)>有3個(gè)元素，分別是（1020），30，（406070）；3個(gè)事務(wù)的發(fā)生時(shí)間是由前到后。這條序列是一個(gè)6-序列。1/9/20231011/7/20239問(wèn)題定義設(shè)序列=<a1a2…an>，序列=<b1b2…bm>，ai和bi都是元素。如果存在整數(shù)1<=j1<j2<…<jn<=m，使得a1bj1，a2bj2，…，anbjn，則稱序列為序列的子序列，又稱序列包含序列，記為。1/9/2023102問(wèn)題定義1/7/202310問(wèn)題定義序列在序列數(shù)據(jù)庫(kù)S中的支持度為序列數(shù)據(jù)庫(kù)S中包含序列的序列個(gè)數(shù)，記為Support()給定支持度閾值，如果序列在序列數(shù)據(jù)庫(kù)中的支持?jǐn)?shù)不低于，則稱序列為序列模式長(zhǎng)度為l的序列模式記為l-模式1/9/2023103問(wèn)題定義序列在序列數(shù)據(jù)庫(kù)S中的支持度

例子：設(shè)序列數(shù)據(jù)庫(kù)如下圖所示，并設(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>是長(zhǎng)度為3的序列模式1/9/2023104例子：設(shè)序列數(shù)據(jù)庫(kù)如下圖所示，并設(shè)用戶指定的最小支持度mi序列模式VS關(guān)聯(lián)規(guī)則問(wèn)題序列模式挖掘關(guān)聯(lián)規(guī)則挖掘數(shù)據(jù)集序列數(shù)據(jù)庫(kù)事務(wù)數(shù)據(jù)庫(kù)關(guān)注點(diǎn)單項(xiàng)間在同一事務(wù)內(nèi)以及事務(wù)間的關(guān)系單項(xiàng)間在同一事務(wù)內(nèi)的關(guān)系1/9/2023105序列模式VS關(guān)聯(lián)規(guī)則問(wèn)題序列模式挖掘關(guān)二、序列模式挖掘的應(yīng)用背景應(yīng)用領(lǐng)域：客戶購(gòu)買行為模式預(yù)測(cè)Web訪問(wèn)模式預(yù)測(cè)疾病診斷自然災(zāi)害預(yù)測(cè)DNA序列分析1/9/2023106二、序列模式挖掘的應(yīng)用背景應(yīng)用領(lǐng)域：1/7/202314應(yīng)用案例1：客戶購(gòu)買行為模式分析B2C電子商務(wù)網(wǎng)站可以根據(jù)客戶購(gòu)買紀(jì)錄來(lái)分析客戶購(gòu)買行為模式，從而進(jìn)行有針對(duì)性的營(yíng)銷策略。IDUsertransactionsequence1…………..2………………3……………………..4………………….圖書交易網(wǎng)站將用戶購(gòu)物紀(jì)錄整合成用戶購(gòu)物序列集合得到用戶購(gòu)物行為序列模式<(“UML語(yǔ)言”)(“Visio2003實(shí)用技巧”)>相關(guān)商品推薦：如果用戶購(gòu)買了書籍“UML語(yǔ)言”,則推薦“Visio2003實(shí)用技巧”1/9/2023107應(yīng)用案例1：客戶購(gòu)買行為模式分析B2C電子商務(wù)網(wǎng)站可以根據(jù)客應(yīng)用案例2：Web訪問(wèn)模式分析大型網(wǎng)站的網(wǎng)站地圖(sitemap)往往具有復(fù)雜的拓?fù)浣Y(jié)構(gòu)。用戶訪問(wèn)序列模式的挖掘有助于改進(jìn)網(wǎng)站地圖的拓?fù)浣Y(jié)構(gòu)。比如用戶經(jīng)常訪問(wèn)網(wǎng)頁(yè)web1然后訪問(wèn)web2,而在網(wǎng)站地圖中二者距離較遠(yuǎn)，就有必要調(diào)整網(wǎng)站地圖，縮短它們的距離，甚至直接增加一條鏈接。Index網(wǎng)站入口web1web21/9/2023108應(yīng)用案例2：Web訪問(wèn)模式分析大型網(wǎng)站的網(wǎng)站地圖(site應(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í)庫(kù)后，專家系統(tǒng)就可以依此來(lái)輔助人類專家進(jìn)行疾病診斷。1/9/2023109應(yīng)用案例3：疾病診斷1/7/202317應(yīng)用案例3：疾病診斷例:通過(guò)分析大量曾患A類疾病的病人發(fā)病紀(jì)錄，發(fā)現(xiàn)以下癥狀發(fā)生的序列模式：<(眩暈)(兩天后低燒37-38度)>如果病人具有以上癥狀，則有可能患A類疾病1/9/2023110應(yīng)用案例3：疾病診斷1/7/202318應(yīng)用案例4：查詢擴(kuò)展查詢擴(kuò)展是搜索領(lǐng)域一個(gè)重要的問(wèn)題。用戶提交的查詢往往不能完全反映其信息需求。一些研究工作嘗試用用戶的查詢序列模式來(lái)輔助原始查詢，其主要思想是：1）挖掘用戶的查詢序列模式2）用這些序列模式構(gòu)造查詢?cè)~關(guān)系圖3）找到每個(gè)極大全連通圖作為一個(gè)”概念”4)對(duì)于一個(gè)查詢，和它同處于一個(gè)”概念”的查詢可以作為查詢擴(kuò)展的選項(xiàng)1/9/2023111應(yīng)用案例4：查詢擴(kuò)展查詢擴(kuò)展是搜索領(lǐng)域一個(gè)重要的問(wèn)題。用戶提應(yīng)用案例4：查詢擴(kuò)展給定一組查詢模式：<(豐田)(雷諾)>,<(寶馬)(豐田)>,<(豐田)(寶馬)>,<(寶馬)(雷諾)>,<(汽車)(豐田)>查詢關(guān)系圖如上圖：豐田雷諾寶馬汽車概念1：汽車品牌概念2：汽車1/9/2023112應(yīng)用案例4：查詢擴(kuò)展豐田雷諾寶馬汽車概念1：汽車品牌概念2：三、序列模式挖掘算法概述Agrawal和Srikant在提出這個(gè)問(wèn)題時(shí)提出了三個(gè)算法，AprioriAll，AprioriSome和DynamicSome，它們都基于Apriori框架。構(gòu)成了序列模式挖掘問(wèn)題的基石。隨后，這個(gè)領(lǐng)域的研究工作取得了大量的成果。1/9/2023113三、序列模式挖掘算法概述1/7/202321序列模式挖掘算法概述類Apriori算法基于劃分的模式生長(zhǎng)算法基于序列比較的算法1/9/2023114序列模式挖掘算法概述1/7/202322

類Apriori算法該類算法基于Apriori理論，即序列模式的任一子序列也是序列模式。算法首先自底向上的根據(jù)較短的序列模式生成較長(zhǎng)的候選序列模式，然后計(jì)算候選序列模式的支持度。典型的代表有GSP算法,spade算法等。1/9/2023115類Apriori算法1/7/202323 基于劃分的模式生長(zhǎng)算法該類算法基于分治的思想，迭代的將原始數(shù)據(jù)集進(jìn)行劃分，減少數(shù)據(jù)規(guī)模，同時(shí)在劃分的過(guò)程中動(dòng)態(tài)的挖掘序列模式，并將新發(fā)現(xiàn)的序列模式作為新的劃分元。典型的代表有FreeSpan算法和prefixSpan算法。1/9/2023116 基于劃分的模式生長(zhǎng)算法1/7/202324 基于序列比較的算法該類算法首先定義序列的大小度量，接著從小到大的枚舉原始序列數(shù)據(jù)庫(kù)中包含的所有k-序列，理論上所有的k-序列模式都能被找到。算法制定特定的規(guī)則加快這種枚舉過(guò)程。典型的代表為Disc-all算法。1/9/2023117 基于序列比較的算法1/7/202325四、GSP算法算法思想：類似于Apriori算法，采用冗余候選模式的剪除策略和特殊的數(shù)據(jù)結(jié)構(gòu)-----哈希樹來(lái)實(shí)現(xiàn)候選模式的快速訪存。1/9/2023118四、GSP算法1/7/202326

GSP算法描述掃描序列數(shù)據(jù)庫(kù)，得到長(zhǎng)度為1的序列模式L1，作為初始的種子集根據(jù)長(zhǎng)度為i的種子集Li

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

C2

L2

C3

L3

C4

L4

……1/9/2023119GSP算法描述掃描序列數(shù)據(jù)庫(kù)，得到長(zhǎng)度

產(chǎn)生候選序列模式主要分兩步：連接階段：如果去掉序列模式s1的第一個(gè)項(xiàng)目與去掉序列模式s2的最后一個(gè)項(xiàng)目所得到的序列相同，則可以將s1與s2進(jìn)行連接，即將s2的最后一個(gè)項(xiàng)目添加到s1中修切階段：若某候選序列模式的某個(gè)子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除L1

C2

L2

C3

L3

C4

L4

……1/9/2023120產(chǎn)生候選序列模式主要分兩步：L1C2L2C

候選序列模式的支持度計(jì)算：對(duì)于給定的候選序列模式集合C，掃描序列數(shù)據(jù)庫(kù)，對(duì)于其中的每一條序列s,找出集合C中被s所包含的所有候選序列模式，并增加其支持度計(jì)數(shù)L1

C2

L2

C3

L3

……1/9/2023121候選序列模式的支持度計(jì)算：對(duì)于給定的候選序列模式集合C，掃 哈希樹GSP采用哈希樹存儲(chǔ)候選序列模式。哈希樹的節(jié)點(diǎn)分為三類：1、根節(jié)點(diǎn)；2、內(nèi)部節(jié)點(diǎn)；3、葉子節(jié)點(diǎn)。

1/9/2023122 哈希樹GSP采用哈希樹存儲(chǔ)候選序列模式。哈希樹的節(jié)點(diǎn)分哈希樹根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)中存放的是一個(gè)哈希表，每個(gè)哈希表項(xiàng)指向其它的節(jié)點(diǎn)。而葉子節(jié)點(diǎn)內(nèi)存放的是一組候選序列模式。例：1/9/2023123哈希樹根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)中存放

添加候選序列模式從根節(jié)點(diǎn)開始，用哈希函數(shù)對(duì)序列的第一個(gè)項(xiàng)目做映射來(lái)決定從哪個(gè)分支向下，依次在第n層對(duì)序列的第n個(gè)項(xiàng)目作映射來(lái)決定從哪個(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)。

1/9/2023124添加候選序列模式1/7/202332

計(jì)算候選序列模式的支持度給定一個(gè)序列s是序列數(shù)據(jù)庫(kù)的一個(gè)記錄：

1）對(duì)于根節(jié)點(diǎn)，用哈希函數(shù)對(duì)序列s的每一個(gè)單項(xiàng)做映射來(lái)并從相應(yīng)的表項(xiàng)向下迭代的進(jìn)行操作2）。

1/9/2023125計(jì)算候選序列模式的支持度1/7/202333計(jì)算候選序列模式的支持度

2）對(duì)于內(nèi)部節(jié)點(diǎn)，如果s是通過(guò)對(duì)單項(xiàng)x做哈希映射來(lái)到此節(jié)點(diǎn)的，則對(duì)s中每一個(gè)和x在一個(gè)元素中的單項(xiàng)以及在x所在元素之后第一個(gè)元素的第一個(gè)單項(xiàng)做哈希映射，然后從相應(yīng)的表項(xiàng)向下迭代做操作2）或3）。1/9/2023126計(jì)算候選序列模式的支持度1/7/202334計(jì)算候選序列模式的支持度（3）對(duì)一個(gè)葉子節(jié)點(diǎn)，檢查每個(gè)候選序列模式c是不是s的子序列.如果是相應(yīng)的候選序列模式支持度加一。這種計(jì)算候選序列的支持度的方法避免了大量無(wú)用的掃描，對(duì)于一條序列，僅檢驗(yàn)?zāi)切┳钣锌赡艹蔀樗有蛄械暮蜻x序列模式。掃描的時(shí)間復(fù)雜度由O(n*m)降為O(n*t),其中n表示序列數(shù)量，m表示候選序列模式的數(shù)量，t代表哈希樹葉子節(jié)點(diǎn)的最大容量1/9/2023127計(jì)算候選序列模式的支持度（3）對(duì)一個(gè)葉子節(jié)點(diǎn)，檢查每個(gè)候

例：下圖演示了如何從長(zhǎng)度為3的序列模式產(chǎn)生長(zhǎng)度為4的候選序列模式SequentialpatternsWithlength3Candidate4-SequencesAfterJoinAfterPruning<(1,2)3><(1,2)(3,4)><(1,2)(3,4)><(1,2)4><(1,2)35><1(3,4)><(1,3)5><2(3,4)><235>1/9/2023128例：下圖演示了如何從長(zhǎng)度為3的序列模式產(chǎn)生長(zhǎng)度為4的候選序

GSP算法存在的主要問(wèn)題如果序列數(shù)據(jù)庫(kù)的規(guī)模比較大，則有可能會(huì)產(chǎn)生大量的候選序列模式需要對(duì)序列數(shù)據(jù)庫(kù)進(jìn)行循環(huán)掃描對(duì)于序列模式的長(zhǎng)度比較長(zhǎng)的情況，由于其對(duì)應(yīng)的短的序列模式規(guī)模太大，本算法很難處理1/9/2023129GSP算法存在的主要問(wèn)題1/7/202337五、PrefixSpan算法算法思想：采用分治的思想，不斷產(chǎn)生序列數(shù)據(jù)庫(kù)的多個(gè)更小的投影數(shù)據(jù)庫(kù)，然后在各個(gè)投影數(shù)據(jù)庫(kù)上進(jìn)行序列模式挖掘1/9/2023130五、PrefixSpan算法算法思想：1/7/202338

相關(guān)定義前綴：設(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)>則不是。1/9/2023131

相關(guān)定義1/7/ 相關(guān)定義投影：給定序列和，如果是的子序列，則關(guān)于的投影’必須滿足：是’的前綴，’是的滿足上述條件的最大子序列

例：對(duì)于序列=<(ab)(acd)>，其子序列=<(b)>的投影是’=<(b)(acd)>;<(ab)>的投影是原序列<(ab)(acd)>。1/9/2023132 相關(guān)定義投影：給定序列和，如果是的子序列，則 相關(guān)定義后綴：序列關(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)>。1/9/2023133 相關(guān)定義后綴：序列關(guān)于子序列=<e1e2…e

例：<a(abc)(ac)d(cf)><a><aa>a(ab)a(abc)<(abc)(ac)d(cf)><(_bc)(ac)d(cf)><ab><(_c)(ac)d(cf)>1/9/2023134例：<a(abc)(ac)d(cf)><a><aa>a( 相關(guān)定義投影數(shù)據(jù)庫(kù)：設(shè)為序列數(shù)據(jù)庫(kù)S中的一個(gè)序列模式，則的投影數(shù)據(jù)庫(kù)為S中所有以為前綴的序列相對(duì)于的后綴，記為S|投影數(shù)據(jù)庫(kù)中的支持度：設(shè)為序列數(shù)據(jù)庫(kù)S中的一個(gè)序列，序列以為前綴，則在的投影數(shù)據(jù)庫(kù)S|中的支持度為S|中滿足條件.的序列的個(gè)數(shù)1/9/2023135 相關(guān)定義投影數(shù)據(jù)庫(kù)：設(shè)為序列數(shù)據(jù)庫(kù)S中的一個(gè)序列模式，

算法描述掃描序列數(shù)據(jù)庫(kù)，生成所有長(zhǎng)度為1的序列模式根據(jù)長(zhǎng)度為1的序列模式，生成相應(yīng)的投影數(shù)據(jù)庫(kù)在相應(yīng)的投影數(shù)據(jù)庫(kù)上重復(fù)上述步驟，直到在相應(yīng)的投影數(shù)據(jù)庫(kù)上不能產(chǎn)生長(zhǎng)度為1的序列模式為止分別對(duì)不同的投影數(shù)據(jù)庫(kù)重復(fù)上述過(guò)程，直到?jīng)]有新的長(zhǎng)度為1的序列模式產(chǎn)生為止SS1…SmS11………S1n……Sm1………Smp……1/9/2023136 算法描述SS1SmS11……S1n……Sm

例：對(duì)于如下的序列數(shù)據(jù)庫(kù)生成一系列的投影數(shù)據(jù)庫(kù)SidSequence10<a(abc)(ac)d(cf)>20<(ad)c(bc)(ae)>30<(ef)(ab)(df)cb>40<(af)cbc>1/9/2023137例：對(duì)于如下的序列數(shù)據(jù)庫(kù)生成一系列的投影數(shù)據(jù)庫(kù)SidSeq

掃描序列數(shù)據(jù)庫(kù)S，產(chǎn)生長(zhǎng)度為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ù)庫(kù)，結(jié)果如下頁(yè)圖所示1/9/2023138掃描序列數(shù)據(jù)庫(kù)S，產(chǎn)生長(zhǎng)度為1的序列模式有：<a>:4

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>1/9/2023139PrefixProjectDatabase<a><(ab 算法偽碼PrefixSpan算法輸入：序列數(shù)據(jù)庫(kù)S及最小支持度閾值min_sup輸出：所有的序列模式方法：去除所有非頻繁的項(xiàng)目，然后調(diào)用子程序PrefixSpan(<>,0,S)1/9/2023140 算法偽碼PrefixSpan算法1/7/202348

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

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

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

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

4<(8)>

給定如下的序列數(shù)據(jù)庫(kù)：1/9/2023142Sidsequence1<(1,

找出頻繁單項(xiàng)：1，3，7，8；然后除去非頻繁的單項(xiàng)：Sidsequence1<(1)(1,3)>

2<(3)(7)>

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

4<(8)>

1/9/2023143找出頻繁單項(xiàng)：1，3，7，8；然后除去非頻繁的單項(xiàng)：Sid

為頻繁1序列（頻繁單項(xiàng)）生成投影數(shù)據(jù)庫(kù)：SidSuffixforprefix<(1)>1<(1,3)>3<(_3)(8)(7)>SidSuffixforprefix<(3)>1<>2<(7)>3<(8)(7)>1/9/2023144為頻繁1序列（頻繁單項(xiàng)）生成投影數(shù)據(jù)庫(kù)：SidSuffix

SidSuffixforprefix<(7)>2<>3<>SidSuffixforprefix<(8)>3<(7)>4<>1/9/2023145SidSuffixforprefix<(7)>2<>

在上面的投影數(shù)據(jù)庫(kù)中，前綴<(1)>的投影數(shù)據(jù)庫(kù)中