序列模式挖掘算法

1、2024/3/23,1,第4章 序列模式挖掘算法,,2024/3/23,2,主要內(nèi)容,序列模式挖掘簡介序列模式挖掘的應(yīng)用背景序列模式挖掘算法概述GSP算法PrefixSpan算法Disc-all算法支持約束的序列模式挖掘,2024/3/23,3,一、序列模式挖掘簡介,序列模式的概念最早是由Agrawal和Srikant 提出的。動(dòng)機(jī)：大型連鎖超市的交易數(shù)據(jù)有一系列的用戶事務(wù)數(shù)據(jù)庫，每一條記錄包括用戶的ID，事務(wù)發(fā)生的時(shí)

2、間和事務(wù)涉及的項(xiàng)目。如果能在其中挖掘涉及事務(wù)間關(guān)聯(lián)關(guān)系的模式，即用戶幾次購買行為間的聯(lián)系，可以采取更有針對性的營銷措施。,2024/3/23,4,事務(wù)數(shù)據(jù)庫實(shí)例,例：一個(gè)事務(wù)數(shù)據(jù)庫，一個(gè)事務(wù)代表一筆交易，一個(gè)單項(xiàng)代表交易的商品，單項(xiàng)屬性中的數(shù)字記錄的是商品ID,2024/3/23,5,序列數(shù)據(jù)庫,一般為了方便處理，需要把數(shù)據(jù)庫轉(zhuǎn)化為序列數(shù)據(jù)庫。方法是把用戶ID相同的記錄合并，有時(shí)每個(gè)事務(wù)的發(fā)生時(shí)間可以忽略，僅保持事務(wù)間的偏序關(guān)系。,20

3、24/3/23,6,問題定義,項(xiàng)集(Itemset)是所有在序列數(shù)據(jù)庫出現(xiàn)過的單項(xiàng)組成的集合例：對一個(gè)用戶購買記錄的序列數(shù)據(jù)庫來說，項(xiàng)集包含用戶購買的所有商品，一種商品就是一個(gè)單項(xiàng)。通常每個(gè)單項(xiàng)有一個(gè)唯一的ID，在數(shù)據(jù)庫中記錄的是單項(xiàng)的ID。,2024/3/23,7,問題定義,元素(Element)可表示為(x1x2…xm)， xk(1 <= k <= m)為不同的單項(xiàng)。元素內(nèi)的單項(xiàng)不考慮順序關(guān)系，一般默認(rèn)按照ID的字典

4、序排列．在用戶事務(wù)數(shù)據(jù)庫里，一個(gè)事務(wù)就是一個(gè)元素。,2024/3/23,8,問題定義,序列(Sequence)是不同元素(Element)的有序排列，序列s可以表示為s = ，sj(1 <= j <= l)為序列s的元素 一個(gè)序列包含的所有單項(xiàng)的個(gè)數(shù)稱為序列的長度。長度為l的序列記為l-序列,2024/3/23,9,,例：一條序列有3個(gè)元素，分別是（10 20），30，（40 60 70 ）；3個(gè)事務(wù)的發(fā)

5、生時(shí)間是由前到后。這條 序列是一個(gè)6-序列。,2024/3/23,10,問題定義,設(shè)序列? = ，序列? = ，ai 和bi都是元素。如果存在整數(shù)1 <= j1 < j2 <…< jn <= m，使得a1 ? bj1，a2 ? bj2，…， an ? bjn，則稱序列?為序列?的子序列，又稱序列?包含序列?，記為? ? ?。,2024/3/23,11,問題定義,序列?在序列數(shù)據(jù)庫S中的支持度為序列數(shù)據(jù)庫

6、S中包含序列?的序列個(gè)數(shù)，記為Support(?)給定支持度閾值?，如果序列?在序列數(shù)據(jù)庫中的支持?jǐn)?shù)不低于?，則稱序列?為序列模式長度為l的序列模式記為l-模式,2024/3/23,12,,例子：設(shè)序列數(shù)據(jù)庫如下圖所示，并設(shè)用戶指定的最小支持度min-support = 2。,序列是序列的子序列序列是長度為3的序列模式,2024/3/23,13,序列模式 VS 關(guān)聯(lián)規(guī)則,2024/3/23,14,二、序列模式挖掘的應(yīng)用背景,應(yīng)

7、用領(lǐng)域：客戶購買行為模式預(yù)測Web訪問模式預(yù)測疾病診斷自然災(zāi)害預(yù)測DNA序列分析,2024/3/23,15,應(yīng)用案例1：客戶購買行為模式分析,B2C電子商務(wù)網(wǎng)站可以根據(jù)客戶購買紀(jì)錄來分析客戶購買行為模式，從而進(jìn)行有針對性的營銷策略。,,圖書交易網(wǎng)站將用戶購物紀(jì)錄整合成用戶購物序列集合,得到用戶購物行為序列模式,,,相關(guān)商品推薦：如果用戶購買了書籍“UML語言”, 則推薦“Visio2003實(shí)用技巧”,2024/3/23,16,

8、應(yīng)用案例2：Web訪問模式分析,大型網(wǎng)站的網(wǎng)站地圖(site map)往往具有復(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)站入口,,,,,,,,,,,,,web1,web2,2024/3/23,17,應(yīng)用案例3：疾病診斷,醫(yī)療領(lǐng)域的專家系統(tǒng)可以作為疾病診斷的輔助決

9、策手段。對應(yīng)特定的疾病，眾多該類病人的癥狀按時(shí)間順序被記錄。自動(dòng)分析該紀(jì)錄可以發(fā)現(xiàn)對應(yīng)此類疾病普適的癥狀模式。每種疾病和對應(yīng)的一系列癥狀模式被加入到知識(shí)庫后，專家系統(tǒng)就可以依此來輔助人類專家進(jìn)行疾病診斷。,2024/3/23,18,應(yīng)用案例3：疾病診斷,例: 通過分析大量曾患A類疾病的病人發(fā)病紀(jì)錄，發(fā)現(xiàn)以下癥狀發(fā)生的序列模式：如果病人具有以上癥狀，則有可能患A類疾病,2024/3/23,19,應(yīng)用案例4：查詢擴(kuò)展,查詢擴(kuò)展是搜索領(lǐng)域

10、一個(gè)重要的問題。用戶提交的查詢往往不能完全反映其信息需求。一些研究工作嘗試用用戶的查詢序列模式來輔助原始查詢，其主要思想是：1）挖掘用戶的查詢序列模式2）用這些序列模式構(gòu)造查詢詞關(guān)系圖3）找到每個(gè)極大全連通圖作為一個(gè)”概念”4) 對于一個(gè)查詢，和它同處于一個(gè)”概念”的查詢可以作為查詢擴(kuò)展的選項(xiàng),2024/3/23,20,應(yīng)用案例4：查詢擴(kuò)展,給定一組查詢模式：, ,,, 查詢關(guān)系圖如上圖：,概念1：汽車品牌,概念2：汽車,202

11、4/3/23,21,三、序列模式挖掘算法概述,Agrawal和Srikant在提出這個(gè)問題時(shí)提出了三個(gè)算法，AprioriAll ， AprioriSome 和DynamicSome， 它們都基于Apriori框架。構(gòu)成了序列模式挖掘問題的基石。隨后，這個(gè)領(lǐng)域 的研究工作取得了大量的成果。,2024/3/23,22,序列模式挖掘算法概述,類Apriori算法基于劃分的模式生長算法基于序列比較的算法,2024/3/23,2

12、3,類Apriori算法,該類算法基于Apriori理論，即序列模式的任一子序列也是序列模式。算法首先自底向上的根據(jù)較短的序列模式生成較長的候選序列模式，然后計(jì)算候選序列模式的支持度。典型的代表有GSP算法, spade算法等。,2024/3/23,24,基于劃分的模式生長算法,該類算法基于分治的思想，迭代的將原始數(shù)據(jù)集進(jìn)行劃分，減少數(shù)據(jù)規(guī)模，同時(shí)在劃分的過程中動(dòng)態(tài)的挖掘序列模式，并將新發(fā)現(xiàn)的序列模式作為新的劃分元。典型的代表有Free

13、Span算法和prefixSpan算法。,2024/3/23,25,基于序列比較的算法,該類算法首先定義序列的大小度量，接著從小到大的枚舉原始序列數(shù)據(jù)庫中包含的所有k-序列，理論上所有的k-序列模式都能被找到。算法制定特定的規(guī)則加快這種枚舉過程。典型的代表為Disc-all算法。,2024/3/23,26,四、GSP算法,算法思想：類似于Apriori算法，采用冗余候選模式的剪除策略和特殊的數(shù)據(jù)結(jié)構(gòu)-----哈希樹來實(shí)現(xiàn)候選模式的快

14、速訪存。,2024/3/23,27,GSP算法描述,掃描序列數(shù)據(jù)庫，得到長度為1的序列模式L1，作為初始的種子集根據(jù)長度為i 的種子集Li ，通過連接操作和修剪操作生成長度為i+1的候選序列模式Ci+1；然后掃描序列數(shù)據(jù)庫，計(jì)算每個(gè)候選序列模式的支持度，產(chǎn)生長度為i+1的序列模式Li+1，并將Li+1作為新的種子集重復(fù)第二步，直到?jīng)]有新的序列模式或新的候選序列模式產(chǎn)生為止,L1? C2 ? L2 ? C3 ? L3 ? C4 ?

15、 L4 ? ……,2024/3/23,28,,產(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 ? ……,,,,2024/3/

16、23,29,,候選序列模式的支持度計(jì)算：對于給定的候選序列模式集合C，掃描序列數(shù)據(jù)庫，對于其中的每一條序列s,找出集合C中被s所包含的所有候選序列模式，并增加其支持度計(jì)數(shù),L1? C2 ? L2 ? C3 ? L3 ? ……,,,2024/3/23,30,哈希樹,GSP采用哈希樹存儲(chǔ)候選序列模式。哈希樹的節(jié)點(diǎn)分為三類： 1、根節(jié)點(diǎn)； 2、內(nèi)部節(jié)點(diǎn)； 3、葉子節(jié)點(diǎn)。,2024/3/23,31,哈希樹,根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)中存放的

17、是一個(gè)哈希表，每個(gè)哈希表項(xiàng)指向其它的節(jié)點(diǎn)。而葉子節(jié)點(diǎn)內(nèi)存放的是一組候選序列模式。例：,2024/3/23,32,添加候選序列模式,從根節(jié)點(diǎn)開始，用哈希函數(shù)對序列的第一個(gè)項(xiàng)目做映射來決定從哪個(gè)分支向下，依次在第n層對序列的第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)。,2024/3/23,33,計(jì)算候

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

19、,計(jì)算候選序列模式的支持度,（3）對一個(gè)葉子節(jié)點(diǎn)，檢查每個(gè)候選序列模式c是不是s的子序列.如果是相應(yīng)的候選序列模式支持度加一。這種計(jì)算候選序列的支持度的方法避免了大量無用的掃描，對于一條序列，僅檢驗(yàn)?zāi)切┳钣锌赡艹蔀樗有蛄械暮蜻x序列模式。掃描的時(shí)間復(fù)雜度由O(n*m)降為O(n*t),其中n表示序列數(shù)量，m表示候選序列模式的數(shù)量，t代表哈希樹葉子節(jié)點(diǎn)的最大容量,2024/3/23,36,,例：下圖演示了如何從長度為3的序列模式產(chǎn)生長

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

21、39,相關(guān)定義,前綴：設(shè)每個(gè)元素中的所有項(xiàng)目按照字典序排列。給定序列? = ，? = (m ? n) ，如果ei’ = ei (i ? m - 1)， em’ ? em，并且(em - em’)中的項(xiàng)目均在em’中項(xiàng)目的后面， 則稱?是?的前綴例：序列 是序列 的一個(gè)前綴；序列則不是 。,2024/3/23,40,相關(guān)定義,投影：給定序列?和? ，如果?是?的子序列，則?關(guān)于?的投影?’必須滿足： ?是?’的前綴，?’是?的滿足上

22、述條件的最大子序列　例：對于 序列? =， 其子序列? = 的投影是?’ = ; 的投影是原序列。,2024/3/23,41,相關(guān)定義,后綴： 序列?關(guān)于子序列? = 的投影為?’ = (n >= m)，則序列?關(guān)于子序列?的后綴為， 其中em” = (em - em’)　　例：對于 序列，其子序列的投影是，則對于的后綴為。,2024/3/23,42,,例： ,,,,,,,a(ab),a(abc),,,,,,,,202

23、4/3/23,43,相關(guān)定義,投影數(shù)據(jù)庫：設(shè)?為序列數(shù)據(jù)庫S中的一個(gè)序列模式，則?的投影數(shù)據(jù)庫為S中所有以?為前綴的序列相對于?的后綴，記為S|?投影數(shù)據(jù)庫中的支持度：設(shè)?為序列數(shù)據(jù)庫S中的一個(gè)序列，序列?以?為前綴，則?在?的投影數(shù)據(jù)庫S|?中的支持度為S|?中滿足條件? ? ?.?的序列?的個(gè)數(shù),2024/3/23,44,算法描述,掃描序列數(shù)據(jù)庫，生成所有長度為1的序列模式根據(jù)長度為1的序列模式，生成相應(yīng)的投影數(shù)據(jù)庫在相應(yīng)的

24、投影數(shù)據(jù)庫上重復(fù)上述步驟，直到在相應(yīng)的投影數(shù)據(jù)庫上不能產(chǎn)生長度為1的序列模式為止分別對不同的投影數(shù)據(jù)庫重復(fù)上述過程，直到?jīng)]有新的長度為1的序列模式產(chǎn)生為止,S,,,S1…,Sm,,,S11 ………,S1n ……,,,Sm1 ………,Smp ……,2024/3/23,45,,例：對于如下的序列數(shù)據(jù)庫生成一系列的投影數(shù)據(jù)庫,2024/3/23,46,,掃描序列數(shù)據(jù)庫S，產(chǎn)生長度為1的序列模式有： : 4, :4,

25、 : 4, : 3, : 3, : 3序列模式的全集必然可以分為分別以，，，，和為前綴的序列模式的集合，構(gòu)造不同前綴所對應(yīng)的投影數(shù)據(jù)庫，結(jié)果如下頁圖所示,2024/3/23,47,,2024/3/23,48,算法偽碼,PrefixSpan算法輸入：序列數(shù)據(jù)庫S及最小支持度閾值min_sup輸出：所有的序列模式方法：去除所有非頻繁的項(xiàng)目，然后調(diào)用子程序PrefixSpan(, 0, S),2024/3/23,49,算法偽

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

27、fixSpan(?’, L + 1, S|?’),2024/3/23,50,,給定如下的序列數(shù)據(jù)庫：,2024/3/23,51,,找出頻繁單項(xiàng)：1，3，7，8；然后除去非頻繁的單項(xiàng)：,2024/3/23,52,,為頻繁1序列（頻繁單項(xiàng)）生成投影數(shù)據(jù)庫：,2024/3/23,53,,2024/3/23,54,,在上面的投影數(shù)據(jù)庫中，前綴的投影數(shù)據(jù)庫中還有頻繁單項(xiàng)_3，前綴的投影數(shù)據(jù)庫中還有頻繁單項(xiàng)7. 生成頻繁2序列，, 然后為其生成投影

28、數(shù)據(jù)庫.其中沒有頻繁項(xiàng)目，算法終止。,2024/3/23,55,PrefixSpan算法分析,PrefixSpan算法不需要產(chǎn)生候選序列模式，從而大大縮減了檢索空間相對于原始的序列數(shù)據(jù)庫而言，投影數(shù)據(jù)庫的規(guī)模不斷減小PrefixSpan算法的主要開銷在于投影數(shù)據(jù)庫的構(gòu)造,2024/3/23,56,PrefixSpan算法的主要改進(jìn),隔層投影：使用隔層投影代替逐層投影，從而可以有效減小投影數(shù)據(jù)庫的個(gè)數(shù)偽投影：當(dāng)序列數(shù)據(jù)庫可以直

29、接放入內(nèi)存時(shí)，可以使用偽投影操作代替實(shí)際的投影數(shù)據(jù)庫，從而可以有效減少構(gòu)造投影數(shù)據(jù)庫的開銷,2024/3/23,57,隔層投影,掃描序列數(shù)據(jù)庫，產(chǎn)生所有長度為1的序列模式再次掃描序列數(shù)據(jù)庫，構(gòu)造如下圖所示的下三角矩陣，得到所有長度為2的序列模式構(gòu)造長度為2的序列模式所對應(yīng)的掃描數(shù)據(jù)庫，然后對每個(gè)投影數(shù)據(jù)庫，重復(fù)上面的操作，直到?jīng)]有新的序列模式產(chǎn)生為止,2024/3/23,58,,2024/3/23,59,偽投影,當(dāng)數(shù)據(jù)庫可以直接放入

30、內(nèi)存時(shí)，并不需要構(gòu)造所有的序列模式對應(yīng)的投影數(shù)據(jù)庫，我們可以使用指向數(shù)據(jù)庫中序列的指針及其偏移量作為偽投影例子：假設(shè)上述序列數(shù)據(jù)庫可以放入內(nèi)存，在構(gòu)造a投影數(shù)據(jù)庫時(shí)，序列 S1 = 所對應(yīng)的偽投影為：一個(gè)指向S1的指針，指針偏移設(shè)定為2。同樣的，序列S1的投影數(shù)據(jù)庫對應(yīng)的偽投影為：一個(gè)指向S1的指針，指針偏移設(shè)定為4,2024/3/23,60,六、Disc-all算法,算法思想：Disc-all算法采用了Disc（Direct

31、sequence comparing)策略。其核心思想是對于給定的k和所有k-1序列模式，通過枚舉所有合適的k序列發(fā)現(xiàn)k-序列模式。通過引入適當(dāng)?shù)拿杜e策略保證算法效率。,2024/3/23,61,相關(guān)定義,給定兩條l-序列?和? , 如果? > ?，那么下列條件必滿足其一：1） , ? 的第m項(xiàng) > ? 的第m項(xiàng)且?與? 在其第m項(xiàng) 之前的部分完全相同 2

32、） , ? 的第m項(xiàng) = ? 的第m項(xiàng)但? 的第m項(xiàng)和第m-1項(xiàng)不在同一元素中而? 的第m項(xiàng)則相反，并且?與? 在其第m項(xiàng) 之前的部分完全相同,2024/3/23,62,,例： 小于 因?yàn)闂l件1), 小于 因?yàn)闂l件2).定義序列的大小關(guān)系只是為了給序列排序，這種大小度量是相對的，沒有真正的物理意義,2024/3/23,63,相關(guān)定義,一條l-序列序列所有長度為k的子序列（1

33、 k l)中最小的一條叫做這條序列的k-最小序列.給定k-序列c為條件序列，一條l-序列序列所有大于c的長度為k的子序列（1 k l)中最小的一條叫做這條序列的k-條件最小序列.,2024/3/23,64,Disc-all算法概述,該算法首先劃分?jǐn)?shù)據(jù)庫，然后在劃分?jǐn)?shù)據(jù)庫上執(zhí)行迭代的執(zhí)行Disc策略，即基于序列比較的序列模式枚舉過程：首先通過適當(dāng)?shù)拿杜e找到所有的k-序列模式，然后根據(jù)k-序列模式找到所有的k+1序列模式。,202

34、4/3/23,65,數(shù)據(jù)庫劃分,Disc-all算法對原始序列數(shù)據(jù)庫進(jìn)行兩層劃分：一層劃分：首先找到所有的頻繁單項(xiàng)并刪除所有的非頻繁單項(xiàng)，然后進(jìn)行一級劃分，即對于每個(gè)頻繁單項(xiàng)i，找到所有包含它的序列組成i劃分。二層劃分：找到所有的2-序列模式并刪除所有的非頻繁2-序列，然后進(jìn)行二級劃分，即對于每個(gè)2-序列模式，找到所有包含它的序列。,2024/3/23,66,,例：對如下數(shù)據(jù)庫進(jìn)行兩層劃分，給定最小支持度2，首先找到所有的頻繁單項(xiàng)

35、：a,b,c,d,e,f,2024/3/23,67,生成一層劃分?jǐn)?shù)據(jù)庫,下面給出了每個(gè)頻繁單項(xiàng)的一層劃分?jǐn)?shù)據(jù)庫：,2024/3/23,68,,在a-劃分?jǐn)?shù)據(jù)庫里找到所有第一項(xiàng)為a的2-序列模式：，并刪除非頻繁的以a開頭的2-序列。刪除規(guī)則為：1）如果單項(xiàng)i和a在同一元素內(nèi)且是2-序列模式;2）如果單項(xiàng)i和a不在同一元素內(nèi)且是2-序列模式; 當(dāng)條件1), 2)全都不滿足時(shí)刪除i.,2024/3/23,69,生成二層劃分?jǐn)?shù)據(jù)庫

36、,下面只給出根據(jù)a-劃分找到的2-序列模式及其二層劃分?jǐn)?shù)據(jù)庫，注意所有的非頻繁2-序列已經(jīng)被刪除。,2024/3/23,70,Disc策略,對于每一個(gè)劃分?jǐn)?shù)據(jù)庫，給定一組k-序列模式集合S，Disc策略通過枚舉找到所有的k+1-序列模式。枚舉過程如下：1) 對于每個(gè)序列s,找到s的最小的k+1-子序列s’,且s’的k前綴 S，將s’加入k+1序列集，記錄s’的源序列s,2024/3/23,71,Disc策略,2) 對k+1序列集排

37、序，設(shè)最小支持度為δ，排序后第δ個(gè)序列稱為條件序列。3) 如果第一個(gè)序列和條件序列相等，則輸出條件序列為一個(gè)k+1-序列模式，并且將所有k+1序列替換為它們源序列的條件最小k+1-序列。否則盡可能將所有k+1序列替換為條件序列，對于源序列中不含條件序列的k+1序列則替換為條件最小k+1-序列,2024/3/23,72,Disc策略,4）重復(fù)上述步驟直到k+1序列集包含的序列數(shù)目小于δ。Disc策略迭代的根據(jù)k-序列模式集找到k+

38、1-序列模式集，然后遞增k. 直到?jīng)]有k+1-序列模式集為空，算法終止。Disc-all算法從從k=2時(shí)開始采用Disc策略。,2024/3/23,73,Disc策略,由于Disc-all算法是在劃分?jǐn)?shù)據(jù)庫上采用Disc策略，對于一個(gè)的劃分，Disc策略只尋找所有以為前綴的序列模式?；貞浿坝懻摰膒refixSpan算法，可以發(fā)現(xiàn)在這一點(diǎn)上二者非常相似。都是基于前綴生長的思想。不同的是prefixSpan采用遞歸而Disc-all算

39、法采用迭代。,2024/3/23,74,,考慮前面的序列數(shù)據(jù)庫，對于右側(cè)的一個(gè)基于二層劃分，仍然給定最小支持度為2，下面的例子展示了Disc策略是如何找到以3-序列模式的,2024/3/23,75,初始化3-序列集,可以看出是一條3序列模式。Sid為30的序列沒有產(chǎn)生初始3-序列因?yàn)槠洳话詾榍熬Y的3-子序列,為條件序列，將所有3-序列替換為源序列的條件3-最小序列并重新排序，又發(fā)現(xiàn)一條3-序列模式,2024/3/23,76,,用新的

40、條件最小3-序列替換各3-序列并排序，3-序列數(shù)據(jù)集如右側(cè)所示。這一次沒有新的3-序列模式被發(fā)現(xiàn)。,,用新的條件序列替換各3-序列并排序，3-序列數(shù)據(jù)集如右側(cè)所示。發(fā)現(xiàn)新的3-序列模式.注意Sid為10的序列不含,所以用條件最小3-序列替換。,2024/3/23,77,,重復(fù)上面的步驟，可以發(fā)現(xiàn)新的3-序列模式. 這時(shí)只有Sid為10的序列含有比更大的3-序列，所以算法停止。,2024/3/23,78,Disc-all算法分析,Disc

41、-all算法同樣不生成候選序列模式，減少了計(jì)算開銷。同時(shí)采用劃分技術(shù), 減少了搜索空間。應(yīng)用Disc策略，解決了劃分效率隨劃分層次增加而下降的問題。Disc-all采用的劃分技術(shù)不如prefixSpan高效，而且Disc策略較為復(fù)雜耗時(shí)，算法效率往往不及prefixSpan，但在處理長序列數(shù)據(jù)集時(shí)，因?yàn)镈isc策略沒有迭代開銷同時(shí)投影技術(shù)效率有所下降， Disc-all表現(xiàn)反而更好。,2024/3/23,79,Disc-all和pr

42、efixSpan的性能比較,平均序列長度為20時(shí)，Disc-all和prefixSpan的性能比較,2024/3/23,80,Disc-all和prefixSpan的性能比較,平均序列長度為80時(shí)，Disc-all和prefixSpan的性能比較,2024/3/23,81,,用戶需要的往往是滿足特定條件的序列模式，而傳統(tǒng)的序列模式挖掘沒有考慮用戶的特殊要求，做了大量無效的挖掘。比如對于購買記錄的事務(wù)數(shù)據(jù)庫，用戶希望得到的序列模式事務(wù)之間

43、的時(shí)間差不能太大。,七、支持約束的序列模式挖掘,2024/3/23,82,解決辦法,引入約束的概念。在約束條件下做符合用戶要求的序列模式挖掘。一方面利用特定約束本身的性質(zhì)節(jié)省了挖掘的時(shí)間和空間，另一方面避免用戶陷入大量的無用信息。,2024/3/23,83,約束的分類,單調(diào)約束：如果一個(gè)序列滿足，那么這個(gè)序列的所有超序列也滿足的約束；反單調(diào)約束：如果一個(gè)序列滿足，那么這個(gè)序列 的任意子序列也滿足的約束；簡潔約束：用特定規(guī)

44、則挖掘的約束；　還有一些無法歸為以上三類的約束，一般被稱為強(qiáng)約束（tough constraints.）比如時(shí)間性約束。,2024/3/23,84,一些常用的約束,2024/3/23,85,支持約束的序列模式挖掘算法,在支持約束的模式序列挖掘領(lǐng)域內(nèi)產(chǎn)生了大量的成果。主要有兩類，一類是針對特定的約束，如針對單調(diào)性約束的ExAnte,針對Gap約束的CCSM,另一類是提出一個(gè)通用的框架，可以針對不同的約束采用不同的策略，如PrefixG

45、rowth.,2024/3/23,86,ExAnte算法,ExAnte實(shí)際上是一種數(shù)據(jù)預(yù)處理方法，它首先刪除所有不滿足約束條件的序列，然后刪除所有在新的序列數(shù)據(jù)庫中非頻繁的單項(xiàng)。處理后的數(shù)據(jù)集可以應(yīng)用任何序列模式挖掘方法。,2024/3/23,87,,例：給定最小支持度2和約束 Sum(P)>4，（目標(biāo)序列模式的總值大于4），考慮右側(cè)的序列數(shù)據(jù)庫,單項(xiàng)后的數(shù)字代表權(quán)值。,2024/3/23,88,,從表中可以看出，Sid為20，4

46、0的序列不滿足給定的約束，可以被刪除。刪除后頻繁單項(xiàng)為c,b,d.a被刪除。得到如下的數(shù)據(jù)集：同原數(shù)據(jù)集相比，數(shù)據(jù)規(guī)模大大減少,2024/3/23,89,PrefixGrowth算法,PrefixGrowth算法以prefixSpan算法為框架，將約束處理機(jī)制整合到前綴增長的過程中。在為前綴構(gòu)造投影數(shù)據(jù)庫之前，首先啟用相應(yīng)的約束機(jī)制檢查前綴是否有可能擴(kuò)展為滿足約束條件的序列模式。,2024/3/23,90,處理單調(diào)約束,對于