序列模式挖掘算法

1、2022-3-41第4章 序列模式挖掘算法2022-3-42主要內(nèi)容n序列模式挖掘簡介n序列模式挖掘的應(yīng)用背景n序列模式挖掘算法概述nGSP算法nPrefixSpan算法nDisc-all算法n支持約束的序列模式挖掘2022-3-43一、序列模式挖掘簡介n序列模式的概念最早是由Agrawal和Srikant 提出的。n動(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ì)性的營銷措施。 2022-3-44 事務(wù)數(shù)據(jù)庫實(shí)例n例：一個(gè)事務(wù)數(shù)據(jù)庫，一個(gè)事務(wù)代

2、表一筆交易，一個(gè)單項(xiàng)代表交易的商品，單項(xiàng)屬性中的數(shù)字記錄的是商品ID2022-3-45 序列數(shù)據(jù)庫n一般為了方便處理，需要把數(shù)據(jù)庫轉(zhuǎn)化為序列數(shù)據(jù)庫。方法是把用戶ID相同的記錄合并，有時(shí)每個(gè)事務(wù)的發(fā)生時(shí)間可以忽略，僅保持事務(wù)間的偏序關(guān)系。2022-3-46 問題定義n項(xiàng)集(Itemset)是所有在序列數(shù)據(jù)庫出現(xiàn)過的單項(xiàng)組成的集合n例：對(duì)一個(gè)用戶購買記錄的序列數(shù)據(jù)庫來說，項(xiàng)集包含用戶購買的所有商品，一種商品就是一個(gè)單項(xiàng)。通常每個(gè)單項(xiàng)有一個(gè)唯一的ID，在數(shù)據(jù)庫中記錄的是單項(xiàng)的ID。2022-3-47 問題定義元素(Element)可表示為(x1x2xm)， xk(1 = k = m)為不同的單項(xiàng)。元

3、素內(nèi)的單項(xiàng)不考慮順序關(guān)系，一般默認(rèn)按照ID的字典序排列在用戶事務(wù)數(shù)據(jù)庫里，一個(gè)事務(wù)就是一個(gè)元素。2022-3-48 問題定義序列(Sequence)是不同元素(Element)的有序排列，序列s可以表示為s = ，sj(1 = j = l)為序列s的元素 一個(gè)序列包含的所有單項(xiàng)的個(gè)數(shù)稱為序列的長度。長度為l的序列記為l-序列2022-3-49 n例：一條序列有3個(gè)元素，分別是（10 20），30，（40 60 70 ）；n3個(gè)事務(wù)的發(fā)生時(shí)間是由前到后。這條 序列是一個(gè)6-序列。2022-3-410 問題定義設(shè)序列 = ，序列 = ，ai 和bi都是元素。如果存在整數(shù)1 = j1 j2 jn =

4、 m，使得a1 bj1，a2 bj2， an bjn，則稱序列為序列的子序列，又稱序列包含序列，記為 。2022-3-411 問題定義序列在序列數(shù)據(jù)庫S中的支持度為序列數(shù)據(jù)庫S中包含序列的序列個(gè)數(shù)，記為Support()給定支持度閾值，如果序列在序列數(shù)據(jù)庫中的支持?jǐn)?shù)不低于，則稱序列為序列模式長度為l的序列模式記為l-模式2022-3-412 n例子：設(shè)序列數(shù)據(jù)庫如下圖所示，并設(shè)用戶指定的最小支持度min-support = 2。SidSequence10203040l序列是序列的子序列l(wèi)序列是長度為3的序列模式2022-3-413序列模式 VS 關(guān)聯(lián)規(guī)則 問題序列模式挖掘 關(guān)聯(lián)規(guī)則挖掘數(shù)據(jù)集序

5、列數(shù)據(jù)庫事務(wù)數(shù)據(jù)庫關(guān)注點(diǎn)單項(xiàng)間在同一事務(wù)內(nèi)以及事務(wù)間的關(guān)系單項(xiàng)間在同一事務(wù)內(nèi)的關(guān)系2022-3-414二、序列模式挖掘的應(yīng)用背景n應(yīng)用領(lǐng)域：客戶購買行為模式預(yù)測Web訪問模式預(yù)測疾病診斷自然災(zāi)害預(yù)測DNA序列分析2022-3-415nB2C電子商務(wù)網(wǎng)站可以根據(jù)客戶購買紀(jì)錄來分析客戶購買行為模式，從而進(jìn)行有針對(duì)性的營銷策略。IDUser transaction sequence1.23.4.圖書交易網(wǎng)站將用戶購物紀(jì)錄整合成用戶購物序列集合得到用戶購物行為序列模式相關(guān)商品推薦：如果用戶購買了書籍“UML語言”, 則推薦“Visio2003實(shí)用技巧”2022-3-416n大型網(wǎng)站的網(wǎng)站地圖(site

6、 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)站入口web1web22022-3-417n醫(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)行疾病診斷。2022-3-418n例: 通過分析大量曾患A類疾病的病人發(fā)病紀(jì)錄，發(fā)現(xiàn)以下

7、癥狀發(fā)生的序列模式：n如果病人具有以上癥狀，則有可能患A類疾病2022-3-419n查詢擴(kuò)展是搜索領(lǐng)域一個(gè)重要的問題。用戶提交的查詢往往不能完全反映其信息需求。一些研究工作嘗試用用戶的查詢序列模式來輔助原始查詢，其主要思想是：n1）挖掘用戶的查詢序列模式n2）用這些序列模式構(gòu)造查詢?cè)~關(guān)系圖n3）找到每個(gè)極大全連通圖作為一個(gè)”概念”n4) 對(duì)于一個(gè)查詢，和它同處于一個(gè)”概念”的查詢可以作為查詢擴(kuò)展的選項(xiàng)2022-3-420n給定一組查詢模式：, , 查詢關(guān)系圖如上圖：豐田雷諾寶馬汽車概念1：汽車品牌概念2：汽車2022-3-421三、序列模式挖掘算法概述nAgrawal和Srikant在提出這個(gè)

8、問題時(shí)提出了三個(gè)算法，AprioriAll ， AprioriSome 和DynamicSome， 它們都基于Apriori框架。構(gòu)成了序列模式挖掘問題的基石。隨后，這個(gè)領(lǐng)域 的研究工作取得了大量的成果。2022-3-422 序列模式挖掘算法概述n類Apriori算法n基于劃分的模式生長算法n基于序列比較的算法2022-3-423 類Apriori算法該類算法基于Apriori理論，即序列模式的任一子序列也是序列模式。算法首先自底向上的根據(jù)較短的序列模式生成較長的候選序列模式，然后計(jì)算候選序列模式的支持度。典型的代表有GSP算法, spade算法等。2022-3-424基于劃分的模式生長算法n

9、該類算法基于分治的思想，迭代的將原始數(shù)據(jù)集進(jìn)行劃分，減少數(shù)據(jù)規(guī)模，同時(shí)在劃分的過程中動(dòng)態(tài)的挖掘序列模式，并將新發(fā)現(xiàn)的序列模式作為新的劃分元。典型的代表有FreeSpan算法和prefixSpan算法。2022-3-425基于序列比較的算法n該類算法首先定義序列的大小度量，接著從小到大的枚舉原始序列數(shù)據(jù)庫中包含的所有k-序列，理論上所有的k-序列模式都能被找到。算法制定特定的規(guī)則加快這種枚舉過程。典型的代表為Disc-all算法。2022-3-426 四、GSP算法算法思想：類似于Apriori算法，采用冗余候選模式的剪除策略和特殊的數(shù)據(jù)結(jié)構(gòu)-哈希樹來實(shí)現(xiàn)候選模式的快速訪存。2022-3-427

10、 GSP算法描述n掃描序列數(shù)據(jù)庫，得到長度為1的序列模式L1，作為初始的種子集n根據(jù)長度為i 的種子集Li ，通過連接操作和修剪操作生成長度為i+1的候選序列模式Ci+1；然后掃描序列數(shù)據(jù)庫，計(jì)算每個(gè)候選序列模式的支持度，產(chǎn)生長度為i+1的序列模式Li+1，并將Li+1作為新的種子集n重復(fù)第二步，直到?jīng)]有新的序列模式或新的候選序列模式產(chǎn)生為止L1 C2 L2 C3 L3 C4 L4 2022-3-428 n產(chǎn)生候選序列模式主要分兩步：連接階段：如果去掉序列模式s1的第一個(gè)項(xiàng)目與去掉序列模式s2的最后一個(gè)項(xiàng)目所得到的序列相同，則可以將s1與s2進(jìn)行連接，即將s2的最后一個(gè)項(xiàng)目添加到s1中修切階段

11、：若某候選序列模式的某個(gè)子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除L1 C2 L2 C3 L3 C4 L4 2022-3-429 n候選序列模式的支持度計(jì)算：對(duì)于給定的候選序列模式集合C，掃描序列數(shù)據(jù)庫，對(duì)于其中的每一條序列s,找出集合C中被s所包含的所有候選序列模式，并增加其支持度計(jì)數(shù)L1 C2 L2 C3 L3 2022-3-430哈希樹nGSP采用哈希樹存儲(chǔ)候選序列模式。哈希樹的節(jié)點(diǎn)分為三類： 1、根節(jié)點(diǎn)； 2、內(nèi)部節(jié)點(diǎn)； 3、葉子節(jié)點(diǎn)。 2022-3-431 哈希樹n根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)中存放的是一個(gè)哈希表，每個(gè)哈希表項(xiàng)指向其它的節(jié)點(diǎn)。而葉子節(jié)點(diǎn)內(nèi)存放的

12、是一組候選序列模式。n例：2022-3-432 添加候選序列模式n從根節(jié)點(diǎn)開始，用哈希函數(shù)對(duì)序列的第一個(gè)項(xiàng)目做映射來決定從哪個(gè)分支向下，依次在第n層對(duì)序列的第n個(gè)項(xiàng)目作映射來決定從哪個(gè)分支向下，直到到達(dá)一個(gè)葉子節(jié)點(diǎn)。將序列儲(chǔ)存在此葉子節(jié)點(diǎn)。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)。 2022-3-433 計(jì)算候選序列模式的支持度n給定一個(gè)序列s是序列數(shù)據(jù)庫的一個(gè)記錄： 1）對(duì)于根節(jié)點(diǎn)，用哈希函數(shù)對(duì)序列s的每一個(gè)單項(xiàng)做映射來并從相應(yīng)的表項(xiàng)向下迭代的進(jìn)行操作 2）。 2022-3-434 計(jì)算候選序列模式的支持度 2）對(duì)于內(nèi)部節(jié)點(diǎn)，如果s是通

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

14、度為3的序列模式產(chǎn)生長度為4的候選序列模式Sequential patternsWith length 3Candidate 4-SequencesAfter JoinAfter Pruning2022-3-437 GSP算法存在的主要問題如果序列數(shù)據(jù)庫的規(guī)模比較大，則有可能會(huì)產(chǎn)生大量的候選序列模式需要對(duì)序列數(shù)據(jù)庫進(jìn)行循環(huán)掃描對(duì)于序列模式的長度比較長的情況，由于其對(duì)應(yīng)的短的序列模式規(guī)模太大，本算法很難處理2022-3-438五、PrefixSpan算法算法思想：采用分治的思想，不斷產(chǎn)生序列數(shù)據(jù)庫的多個(gè)更小的投影數(shù)據(jù)庫，然后在各個(gè)投影數(shù)據(jù)庫上進(jìn)行序列模式挖掘2022-3-439 相關(guān)定義前綴：設(shè)

15、每個(gè)元素中的所有項(xiàng)目按照字典序排列。給定序列 = ， = (m n) ，如果ei = ei (i m - 1)， em em，并且(em - em)中的項(xiàng)目均在em中項(xiàng)目的后面， 則稱是的前綴例：序列 是序列 的一個(gè)前綴；序列則不是 。2022-3-440相關(guān)定義投影：給定序列和 ，如果是的子序列，則關(guān)于的投影必須滿足： 是的前綴，是的滿足上述條件的最大子序列例：對(duì)于 序列 =， 其子序列 = 的投影是 = ; 的投影是原序列。2022-3-441相關(guān)定義后綴： 序列關(guān)于子序列 = 的投影為 = (n = m)，則序列關(guān)于子序列的后綴為， 其中em” = (em - em)n例：對(duì)于 序列，其

16、子序列的投影是，則對(duì)于的后綴為。2022-3-442 n例： a(ab)a(abc)2022-3-443相關(guān)定義n投影數(shù)據(jù)庫：設(shè)為序列數(shù)據(jù)庫S中的一個(gè)序列模式，則的投影數(shù)據(jù)庫為S中所有以為前綴的序列相對(duì)于的后綴，記為S|n投影數(shù)據(jù)庫中的支持度：設(shè)為序列數(shù)據(jù)庫S中的一個(gè)序列，序列以為前綴，則在的投影數(shù)據(jù)庫S|中的支持度為S|中滿足條件 .的序列的個(gè)數(shù)2022-3-444算法描述n掃描序列數(shù)據(jù)庫，生成所有長度為1的序列模式n根據(jù)長度為1的序列模式，生成相應(yīng)的投影數(shù)據(jù)庫n在相應(yīng)的投影數(shù)據(jù)庫上重復(fù)上述步驟，直到在相應(yīng)的投影數(shù)據(jù)庫上不能產(chǎn)生長度為1的序列模式為止n分別對(duì)不同的投影數(shù)據(jù)庫重復(fù)上述過程，直到

17、沒有新的長度為1的序列模式產(chǎn)生為止SS1SmS11 S1n Sm1 Smp 2022-3-445 n例：對(duì)于如下的序列數(shù)據(jù)庫生成一系列的投影數(shù)據(jù)庫SidSequence102030402022-3-446 n掃描序列數(shù)據(jù)庫S，產(chǎn)生長度為1的序列模式有： : 4, :4, : 4, : 3, : 3, : 3n序列模式的全集必然可以分為分別以，和為前綴的序列模式的集合，構(gòu)造不同前綴所對(duì)應(yīng)的投影數(shù)據(jù)庫，結(jié)果如下頁圖所示2022-3-447 PrefixProject Database 2022-3-448算法偽碼nPrefixSpan算法輸入：序列數(shù)據(jù)庫S及最小支持度閾值min_sup輸出：所有的

18、序列模式方法：去除所有非頻繁的項(xiàng)目，然后調(diào)用子程序PrefixSpan(, 0, S)2022-3-449 算法偽碼n子程序PrefixSpan(, L, S|)參數(shù)： . 一個(gè)序列模式 L. 序列模式的長度 S| . 如果為空，則為S，否則為的投影數(shù)據(jù)庫掃描S|，找到滿足下述要求的長度為1的序列模式b：b可以添加到的最后一個(gè)元素中并為序列模式可以作為的最后一個(gè)元素并為序列模式對(duì)每個(gè)生成的序列模式b，將b添加到形成序列模式，并輸出對(duì)每個(gè),構(gòu)造的投影數(shù)據(jù)庫S| ,并調(diào)用子程序PrefixSpan(, L + 1, S|)2022-3-450 Sid sequence 1 2 3 4 給定如下的序

19、列數(shù)據(jù)庫：2022-3-451 n找出頻繁單項(xiàng)：1，3，7，8；然后除去非頻繁的單項(xiàng)：Sid sequence 1 2 3 4 2022-3-452 n為頻繁1序列（頻繁單項(xiàng)）生成投影數(shù)據(jù)庫：SidSuffix for prefix 13SidSuffix for prefix 1232022-3-453 SidSuffix for prefix 23SidSuffix for prefix 342022-3-454 n在上面的投影數(shù)據(jù)庫中，前綴的投影數(shù)據(jù)庫中還有頻繁單項(xiàng)_3，前綴的投影數(shù)據(jù)庫中還有頻繁單項(xiàng)7. 生成頻繁2序列，, 然后為其生成投影數(shù)據(jù)庫.其中沒有頻繁項(xiàng)目，算法終止。SidSu

20、ffix for prefix 13SidSuffix for prefix 232022-3-455 PrefixSpan算法分析nPrefixSpan算法不需要產(chǎn)生候選序列模式，從而大大縮減了檢索空間n相對(duì)于原始的序列數(shù)據(jù)庫而言，投影數(shù)據(jù)庫的規(guī)模不斷減小nPrefixSpan算法的主要開銷在于投影數(shù)據(jù)庫的構(gòu)造2022-3-456PrefixSpan算法的主要改進(jìn)隔層投影：使用隔層投影代替逐層投影，從而可以有效減小投影數(shù)據(jù)庫的個(gè)數(shù)偽投影：當(dāng)序列數(shù)據(jù)庫可以直接放入內(nèi)存時(shí)，可以使用偽投影操作代替實(shí)際的投影數(shù)據(jù)庫，從而可以有效減少構(gòu)造投影數(shù)據(jù)庫的開銷2022-3-457隔層投影n掃描序列數(shù)據(jù)庫，產(chǎn)

21、生所有長度為1的序列模式n再次掃描序列數(shù)據(jù)庫，構(gòu)造如下圖所示的下三角矩陣，得到所有長度為2的序列模式n構(gòu)造長度為2的序列模式所對(duì)應(yīng)的掃描數(shù)據(jù)庫，然后對(duì)每個(gè)投影數(shù)據(jù)庫，重復(fù)上面的操作，直到?jīng)]有新的序列模式產(chǎn)生為止SidSequence102030402022-3-458a2b(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)1abcdef2022-3-459偽投影n當(dāng)數(shù)據(jù)庫可以直接放入內(nèi)存時(shí)，并不需要構(gòu)造所有的序列模式對(duì)應(yīng)

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

23、下列條件必滿足其一：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) 之前的部分完全相同lmm1 ,lmm1 ,2022-3-462 n例： 小于 因?yàn)闂l件1), 小于 因?yàn)闂l件2).n定義序列的大小關(guān)系只是為了給序列排序，這種大小度量是相對(duì)的，沒有真正的物理意義2022-3-463相關(guān)定義n一條l-序列序列所有長度為k的子序列（1 k l)中最小的一條叫做這條序列的k-最小序列.n給定k-序列c為條件序列，一條l-序列序列所有大于c的長度為k的子序列（1 k l)中最

24、小的一條叫做這條序列的k-條件最小序列.2022-3-464 Disc-all算法概述n該算法首先劃分?jǐn)?shù)據(jù)庫，然后在劃分?jǐn)?shù)據(jù)庫上執(zhí)行迭代的執(zhí)行Disc策略，即基于序列比較的序列模式枚舉過程：首先通過適當(dāng)?shù)拿杜e找到所有的k-序列模式，然后根據(jù)k-序列模式找到所有的k+1序列模式。2022-3-465 數(shù)據(jù)庫劃分nDisc-all算法對(duì)原始序列數(shù)據(jù)庫進(jìn)行兩層劃分：n一層劃分：首先找到所有的頻繁單項(xiàng)并刪除所有的非頻繁單項(xiàng)，然后進(jìn)行一級(jí)劃分，即對(duì)于每個(gè)頻繁單項(xiàng)i，找到所有包含它的序列組成i劃分。n二層劃分：找到所有的2-序列模式并刪除所有的非頻繁2-序列，然后進(jìn)行二級(jí)劃分，即對(duì)于每個(gè)2-序列模式，找到

25、所有包含它的序列。2022-3-466 SidSequence10203040例：對(duì)如下數(shù)據(jù)庫進(jìn)行兩層劃分，給定最小支持度2，首先找到所有的頻繁單項(xiàng)：a,b,c,d,e,f2022-3-467 生成一層劃分?jǐn)?shù)據(jù)庫n下面給出了每個(gè)頻繁單項(xiàng)的一層劃分?jǐn)?shù)據(jù)庫：頻繁單項(xiàng)劃分?jǐn)?shù)據(jù)庫a b c d e f 2022-3-468 n在a-劃分?jǐn)?shù)據(jù)庫里找到所有第一項(xiàng)為a的2-序列模式：，并刪除非頻繁的以a開頭的2-序列。刪除規(guī)則為：n1）如果單項(xiàng)i和a在同一元素內(nèi)且是2-序列模式;n2）如果單項(xiàng)i和a不在同一元素內(nèi)且是2-序列模式; 當(dāng)條件1), 2)全都不滿足時(shí)刪除i. 2022-3-469 生成二層劃分?jǐn)?shù)

26、據(jù)庫n下面只給出根據(jù)a-劃分找到的2-序列模式及其二層劃分?jǐn)?shù)據(jù)庫，注意所有的非頻繁2-序列已經(jīng)被刪除。頻繁單項(xiàng)劃分?jǐn)?shù)據(jù)庫 2022-3-470 Disc策略n對(duì)于每一個(gè)劃分?jǐn)?shù)據(jù)庫，給定一組k-序列模式集合S，Disc策略通過枚舉找到所有的k+1-序列模式。枚舉過程如下：n1) 對(duì)于每個(gè)序列s,找到s的最小的k+1-子序列s,且s的k前綴 S，將s加入k+1序列集，記錄s的源序列s2022-3-471 Disc策略n2) 對(duì)k+1序列集排序，設(shè)最小支持度為，排序后第個(gè)序列稱為條件序列。n3) 如果第一個(gè)序列和條件序列相等，則輸出條件序列為一個(gè)k+1-序列模式，并且將所有k+1序列替換為它們?cè)葱蛄?/p>

27、的條件最小k+1-序列。否則盡可能將所有k+1序列替換為條件序列，對(duì)于源序列中不含條件序列的k+1序列則替換為條件最小k+1-序列2022-3-472 Disc策略n4）重復(fù)上述步驟直到k+1序列集包含的序列數(shù)目小于。nDisc策略迭代的根據(jù)k-序列模式集找到k+1-序列模式集，然后遞增k. 直到?jīng)]有k+1-序列模式集為空，算法終止。Disc-all算法從從k=2時(shí)開始采用Disc策略。2022-3-473 Disc策略n由于Disc-all算法是在劃分?jǐn)?shù)據(jù)庫上采用Disc策略，對(duì)于一個(gè)的劃分，Disc策略只尋找所有以為前綴的序列模式。n回憶之前討論的prefixSpan算法，可以發(fā)現(xiàn)在這一點(diǎn)

28、上二者非常相似。都是基于前綴生長的思想。不同的是prefixSpan采用遞歸而Disc-all算法采用迭代。2022-3-474 n考慮前面的序列數(shù)據(jù)庫，對(duì)于右側(cè)的一個(gè)基于二層劃分，仍然給定最小支持度為2，下面的例子展示了Disc策略是如何找到以3-序列模式的nSidSequence102030402022-3-475 初始化3-序列集Sid3-Sequence104020n可以看出是一條3序列模式。Sid為30的序列沒有產(chǎn)生初始3-序列因?yàn)槠洳话詾榍熬Y的3-子序列Sid3-Sequence102040n為條件序列，將所有3-序列替換為源序列的條件3-最小序列并重新排序，又發(fā)現(xiàn)一條3-序列

29、模式2022-3-476 Sid3-Sequence402010n用新的條件最小3-序列替換各3-序列并排序，3-序列數(shù)據(jù)集如右側(cè)所示。這一次沒有新的3-序列模式被發(fā)現(xiàn)。Sid3-Sequence104020n用新的條件序列替換各3-序列并排序，3-序列數(shù)據(jù)集如右側(cè)所示。發(fā)現(xiàn)新的3-序列模式.注意Sid為10的序列不含,所以用條件最小3-序列替換。2022-3-477 n重復(fù)上面的步驟，可以發(fā)現(xiàn)新的3-序列模式. 這時(shí)只有Sid為10的序列含有比更大的3-序列，所以算法停止。Sid3-Sequence4020102022-3-478Disc-all算法分析nDisc-all算法同樣不生成候選序

30、列模式，減少了計(jì)算開銷。同時(shí)采用劃分技術(shù), 減少了搜索空間。應(yīng)用Disc策略，解決了劃分效率隨劃分層次增加而下降的問題。nDisc-all采用的劃分技術(shù)不如prefixSpan高效，而且Disc策略較為復(fù)雜耗時(shí)，算法效率往往不及prefixSpan，但在處理長序列數(shù)據(jù)集時(shí)，因?yàn)镈isc策略沒有迭代開銷同時(shí)投影技術(shù)效率有所下降， Disc-all表現(xiàn)反而更好。2022-3-479 Disc-all和prefixSpan的性能比較平均序列長度為20時(shí)，Disc-all和prefixSpan的性能比較2022-3-480Disc-all和prefixSpan的性能比較平均序列長度為80時(shí)，Disc-all和prefixSpan的性能比較2022-3-481 n用戶需要的往往是滿足特定條件的序列模式，而傳統(tǒng)的序列模式挖掘沒有考慮用戶的特殊要求，做了大量無效的挖掘。比如對(duì)于購買記錄的事務(wù)數(shù)據(jù)庫，用戶希望得到的序列模式事務(wù)之間的時(shí)間差不能太大。 2022-3-482解決辦法引入約束的概念。在約束條件下做符合用戶要求的序列模式挖掘。一方面利用特定約束本身的性質(zhì)節(jié)省了挖掘的時(shí)間和空間，另一方面避免用戶陷入大量的無用信息。2022-3-483約束的分類n單調(diào)約束：如果一個(gè)序列滿足，那么這個(gè)序列的所有超序列也滿足的約束；n反單調(diào)約束：如果一個(gè)序列滿足，那么這個(gè)序