序列模式挖掘算法

1、2022-2-231第4章 序列模式挖掘算法2022-2-232主要內(nèi)容n序列模式挖掘簡介n序列模式挖掘的應用背景n序列模式挖掘算法概述nGSP算法nPrefixSpan算法nDisc-all算法n支持約束的序列模式挖掘2022-2-233一、序列模式挖掘簡介n序列模式的概念最早是由Agrawal和Srikant 提出的。n動機：大型連鎖超市的交易數(shù)據(jù)有一系列的用戶事務數(shù)據(jù)庫，每一條記錄包括用戶的ID，事務發(fā)生的時間和事務涉及的項目。如果能在其中挖掘涉及事務間關(guān)聯(lián)關(guān)系的模式，即用戶幾次購買行為間的聯(lián)系，可以采取更有針對性的營銷措施。 2022-2-234 事務數(shù)據(jù)庫實例n例：一個事務數(shù)據(jù)庫，一

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

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

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

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

6、16n大型網(wǎng)站的網(wǎng)站地圖(site map)往往具有復雜的拓撲結(jié)構(gòu)。用戶訪問序列模式的挖掘有助于改進網(wǎng)站地圖的拓撲結(jié)構(gòu)。比如用戶經(jīng)常訪問網(wǎng)頁web1然后訪問web2,而在網(wǎng)站地圖中二者距離較遠，就有必要調(diào)整網(wǎng)站地圖，縮短它們的距離，甚至直接增加一條鏈接。Index 網(wǎng)站入口web1web22022-2-2317n醫(yī)療領(lǐng)域的專家系統(tǒng)可以作為疾病診斷的輔助決策手段。對應特定的疾病，眾多該類病人的癥狀按時間順序被記錄。自動分析該紀錄可以發(fā)現(xiàn)對應此類疾病普適的癥狀模式。每種疾病和對應的一系列癥狀模式被加入到知識庫后，專家系統(tǒng)就可以依此來輔助人類專家進行疾病診斷。2022-2-2318n例: 通過分析大

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

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

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

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

11、與s2進行連接，即將s2的最后一個項目添加到s1中修切階段：若某候選序列模式的某個子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除L1 C2 L2 C3 L3 C4 L4 2022-2-2329 n候選序列模式的支持度計算：對于給定的候選序列模式集合C，掃描序列數(shù)據(jù)庫，對于其中的每一條序列s,找出集合C中被s所包含的所有候選序列模式，并增加其支持度計數(shù)L1 C2 L2 C3 L3 2022-2-2330哈希樹nGSP采用哈希樹存儲候選序列模式。哈希樹的節(jié)點分為三類： 1、根節(jié)點； 2、內(nèi)部節(jié)點； 3、葉子節(jié)點。 2022-2-2331 哈希樹n根節(jié)點和內(nèi)部節(jié)點中存

12、放的是一個哈希表，每個哈希表項指向其它的節(jié)點。而葉子節(jié)點內(nèi)存放的是一組候選序列模式。n例：2022-2-2332 添加候選序列模式n從根節(jié)點開始，用哈希函數(shù)對序列的第一個項目做映射來決定從哪個分支向下，依次在第n層對序列的第n個項目作映射來決定從哪個分支向下，直到到達一個葉子節(jié)點。將序列儲存在此葉子節(jié)點。n初始時所有節(jié)點都是葉子節(jié)點，當一個葉子節(jié)點所存放的序列數(shù)目達到一個閾值，它將轉(zhuǎn)化為一個內(nèi)部節(jié)點。 2022-2-2333 計算候選序列模式的支持度n給定一個序列s是序列數(shù)據(jù)庫的一個記錄： 1）對于根節(jié)點，用哈希函數(shù)對序列s的每一個單項做映射來并從相應的表項向下迭代的進行操作 2）。 2022

13、-2-2334 計算候選序列模式的支持度 2）對于內(nèi)部節(jié)點，如果s是通過對單項x做哈希映射來到此節(jié)點的，則對s中每一個和x在一個元素中的單項以及在x所在元素之后第一個元素的第一個單項做哈希映射，然后從相應的表項向下迭代做操作 2）或 3）。2022-2-2335 計算候選序列模式的支持度n（3）對一個葉子節(jié)點，檢查每個候選序列模式c是不是s的子序列.如果是相應的候選序列模式支持度加一。n這種計算候選序列的支持度的方法避免了大量無用的掃描，對于一條序列，僅檢驗那些最有可能成為它子序列的候選序列模式。掃描的時間復雜度由O(n*m)降為O(n*t),其中n表示序列數(shù)量，m表示候選序列模式的數(shù)量，t代

14、表哈希樹葉子節(jié)點的最大容量2022-2-2336 n例：下圖演示了如何從長度為3的序列模式產(chǎn)生長度為4的候選序列模式Sequential patternsWith length 3Candidate 4-SequencesAfter JoinAfter Pruning2022-2-2337 GSP算法存在的主要問題如果序列數(shù)據(jù)庫的規(guī)模比較大，則有可能會產(chǎn)生大量的候選序列模式需要對序列數(shù)據(jù)庫進行循環(huán)掃描對于序列模式的長度比較長的情況，由于其對應的短的序列模式規(guī)模太大，本算法很難處理2022-2-2338五、PrefixSpan算法算法思想：采用分治的思想，不斷產(chǎn)生序列數(shù)據(jù)庫的多個更小的投影數(shù)據(jù)庫

15、，然后在各個投影數(shù)據(jù)庫上進行序列模式挖掘2022-2-2339 相關(guān)定義前綴：設每個元素中的所有項目按照字典序排列。給定序列 = ， = (m n) ，如果ei = ei (i m - 1)， em em，并且(em - em)中的項目均在em中項目的后面， 則稱是的前綴例：序列 是序列 的一個前綴；序列則不是 。2022-2-2340相關(guān)定義投影：給定序列和 ，如果是的子序列，則關(guān)于的投影必須滿足： 是的前綴，是的滿足上述條件的最大子序列例：對于 序列 =， 其子序列 = 的投影是 = ; 的投影是原序列。2022-2-2341相關(guān)定義 后綴： 序列關(guān)于子序列 = 的投影為 = (n = m

16、)，則序列關(guān)于子序列的后綴為， 其中em” = (em - em)n例：對于 序列，其子序列的投影是，則對于的后綴為。2022-2-2342 n例： a(ab)a(abc)2022-2-2343相關(guān)定義n投影數(shù)據(jù)庫：設為序列數(shù)據(jù)庫S中的一個序列模式，則的投影數(shù)據(jù)庫為S中所有以為前綴的序列相對于的后綴，記為S|n投影數(shù)據(jù)庫中的支持度：設為序列數(shù)據(jù)庫S中的一個序列，序列以為前綴，則在的投影數(shù)據(jù)庫S|中的支持度為S|中滿足條件 .的序列的個數(shù)2022-2-2344算法描述n掃描序列數(shù)據(jù)庫，生成所有長度為1的序列模式n根據(jù)長度為1的序列模式，生成相應的投影數(shù)據(jù)庫n在相應的投影數(shù)據(jù)庫上重復上述步驟，直到

17、在相應的投影數(shù)據(jù)庫上不能產(chǎn)生長度為1的序列模式為止n分別對不同的投影數(shù)據(jù)庫重復上述過程，直到?jīng)]有新的長度為1的序列模式產(chǎn)生為止SS1SmS11 S1n Sm1 Smp 2022-2-2345 n例：對于如下的序列數(shù)據(jù)庫生成一系列的投影數(shù)據(jù)庫SidSequence102030402022-2-2346 n掃描序列數(shù)據(jù)庫S，產(chǎn)生長度為1的序列模式有： : 4, :4, : 4, : 3, : 3, : 3n序列模式的全集必然可以分為分別以，和為前綴的序列模式的集合，構(gòu)造不同前綴所對應的投影數(shù)據(jù)庫，結(jié)果如下頁圖所示2022-2-2347 PrefixProject Database 2022-2-2

18、348算法偽碼nPrefixSpan算法輸入：序列數(shù)據(jù)庫S及最小支持度閾值min_sup輸出：所有的序列模式方法：去除所有非頻繁的項目，然后調(diào)用子程序PrefixSpan(, 0, S)2022-2-2349 算法偽碼n子程序PrefixSpan(, L, S|) 參數(shù)： . 一個序列模式 L. 序列模式的長度 S| . 如果為空，則為S，否則為的投影數(shù)據(jù)庫掃描S|，找到滿足下述要求的長度為1的序列模式b： b可以添加到的最后一個元素中并為序列模式 可以作為的最后一個元素并為序列模式對每個生成的序列模式b，將b添加到形成序列模式，并輸出對每個,構(gòu)造的投影數(shù)據(jù)庫S| ,并調(diào)用子程序PrefixS

19、pan(, L + 1, S|)2022-2-2350 Sid sequence 1 2 3 4 給定如下的序列數(shù)據(jù)庫：2022-2-2351 n找出頻繁單項：1，3，7，8；然后除去非頻繁的單項：Sid sequence 1 2 3 4 2022-2-2352 n為頻繁1序列（頻繁單項）生成投影數(shù)據(jù)庫：SidSuffix for prefix 13SidSuffix for prefix 1232022-2-2353 SidSuffix for prefix 23SidSuffix for prefix 342022-2-2354 n在上面的投影數(shù)據(jù)庫中，前綴的投影數(shù)據(jù)庫中還有頻繁單項_3，

20、前綴的投影數(shù)據(jù)庫中還有頻繁單項7. 生成頻繁2序列，, 然后為其生成投影數(shù)據(jù)庫.其中沒有頻繁項目，算法終止。SidSuffix for prefix 13SidSuffix for prefix 232022-2-2355 PrefixSpan算法分析nPrefixSpan算法不需要產(chǎn)生候選序列模式，從而大大縮減了檢索空間n相對于原始的序列數(shù)據(jù)庫而言，投影數(shù)據(jù)庫的規(guī)模不斷減小nPrefixSpan算法的主要開銷在于投影數(shù)據(jù)庫的構(gòu)造2022-2-2356PrefixSpan算法的主要改進 隔層投影：使用隔層投影代替逐層投影，從而可以有效減小投影數(shù)據(jù)庫的個數(shù) 偽投影：當序列數(shù)據(jù)庫可以直接放入內(nèi)存時

21、，可以使用偽投影操作代替實際的投影數(shù)據(jù)庫，從而可以有效減少構(gòu)造投影數(shù)據(jù)庫的開銷2022-2-2357隔層投影n掃描序列數(shù)據(jù)庫，產(chǎn)生所有長度為1的序列模式n再次掃描序列數(shù)據(jù)庫，構(gòu)造如下圖所示的下三角矩陣，得到所有長度為2的序列模式n構(gòu)造長度為2的序列模式所對應的掃描數(shù)據(jù)庫，然后對每個投影數(shù)據(jù)庫，重復上面的操作，直到?jīng)]有新的序列模式產(chǎn)生為止SidSequence102030402022-2-2358a2b(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

22、)(1,1,1)(2,0,1)1abcdef2022-2-2359偽投影n當數(shù)據(jù)庫可以直接放入內(nèi)存時，并不需要構(gòu)造所有的序列模式對應的投影數(shù)據(jù)庫，我們可以使用指向數(shù)據(jù)庫中序列的指針及其偏移量作為偽投影n例子：假設上述序列數(shù)據(jù)庫可以放入內(nèi)存，在構(gòu)造a投影數(shù)據(jù)庫時，序列 S1 = 所對應的偽投影為：一個指向S1的指針，指針偏移設定為2。同樣的，序列S1的投影數(shù)據(jù)庫對應的偽投影為：一個指向S1的指針，指針偏移設定為42022-2-2360n算法思想：nDisc-all算法采用了Disc（Direct sequence comparing)策略。其核心思想是對于給定的k和所有k-1序列模式，通過枚舉所

23、有合適的k序列發(fā)現(xiàn)k-序列模式。通過引入適當?shù)拿杜e策略保證算法效率。2022-2-2361相關(guān)定義n給定兩條l-序列和 , 如果 ，那么下列條件必滿足其一：1） , 的第m項 的第m項且與 在其第m項 之前的部分完全相同 2） , 的第m項 = 的第m項但 的第m項和第m-1項不在同一元素中而 的第m項則相反，并且與 在其第m項 之前的部分完全相同lmm1 ,lmm1 ,2022-2-2362 n例： 小于 因為條件1), 小于 因為條件2).n定義序列的大小關(guān)系只是為了給序列排序，這種大小度量是相對的，沒有真正的物理意義2022-2-2363相關(guān)定義n一條l-序列序列所有長度為k的子序列（1

24、 k l)中最小的一條叫做這條序列的k-最小序列.n給定k-序列c為條件序列，一條l-序列序列所有大于c的長度為k的子序列（1 k l)中最小的一條叫做這條序列的k-條件最小序列.2022-2-2364 Disc-all算法概述n該算法首先劃分數(shù)據(jù)庫，然后在劃分數(shù)據(jù)庫上執(zhí)行迭代的執(zhí)行Disc策略，即基于序列比較的序列模式枚舉過程：首先通過適當?shù)拿杜e找到所有的k-序列模式，然后根據(jù)k-序列模式找到所有的k+1序列模式。2022-2-2365 數(shù)據(jù)庫劃分nDisc-all算法對原始序列數(shù)據(jù)庫進行兩層劃分：n一層劃分：首先找到所有的頻繁單項并刪除所有的非頻繁單項，然后進行一級劃分，即對于每個頻繁單項

25、i，找到所有包含它的序列組成i劃分。n二層劃分：找到所有的2-序列模式并刪除所有的非頻繁2-序列，然后進行二級劃分，即對于每個2-序列模式，找到所有包含它的序列。2022-2-2366 SidSequence10203040例：對如下數(shù)據(jù)庫進行兩層劃分，給定最小支持度2，首先找到所有的頻繁單項：a,b,c,d,e,f2022-2-2367 生成一層劃分數(shù)據(jù)庫n下面給出了每個頻繁單項的一層劃分數(shù)據(jù)庫：頻繁單項劃分數(shù)據(jù)庫a b c d e f 2022-2-2368 n在a-劃分數(shù)據(jù)庫里找到所有第一項為a的2-序列模式：，并刪除非頻繁的以a開頭的2-序列。刪除規(guī)則為：n1）如果單項i和a在同一元素

26、內(nèi)且是2-序列模式;n2）如果單項i和a不在同一元素內(nèi)且是2-序列模式; 當條件1), 2)全都不滿足時刪除i. 2022-2-2369 生成二層劃分數(shù)據(jù)庫n下面只給出根據(jù)a-劃分找到的2-序列模式及其二層劃分數(shù)據(jù)庫，注意所有的非頻繁2-序列已經(jīng)被刪除。頻繁單項劃分數(shù)據(jù)庫 2022-2-2370 Disc策略n對于每一個劃分數(shù)據(jù)庫，給定一組k-序列模式集合S，Disc策略通過枚舉找到所有的k+1-序列模式。枚舉過程如下：n1) 對于每個序列s,找到s的最小的k+1-子序列s,且s的k前綴 S，將s加入k+1序列集，記錄s的源序列s2022-2-2371 Disc策略n2) 對k+1序列集排序，

27、設最小支持度為，排序后第個序列稱為條件序列。n3) 如果第一個序列和條件序列相等，則輸出條件序列為一個k+1-序列模式，并且將所有k+1序列替換為它們源序列的條件最小k+1-序列。否則盡可能將所有k+1序列替換為條件序列，對于源序列中不含條件序列的k+1序列則替換為條件最小k+1-序列2022-2-2372 Disc策略n4）重復上述步驟直到k+1序列集包含的序列數(shù)目小于。nDisc策略迭代的根據(jù)k-序列模式集找到k+1-序列模式集，然后遞增k. 直到?jīng)]有k+1-序列模式集為空，算法終止。Disc-all算法從從k=2時開始采用Disc策略。2022-2-2373 Disc策略n由于Disc-

28、all算法是在劃分數(shù)據(jù)庫上采用Disc策略，對于一個的劃分，Disc策略只尋找所有以為前綴的序列模式。n回憶之前討論的prefixSpan算法，可以發(fā)現(xiàn)在這一點上二者非常相似。都是基于前綴生長的思想。不同的是prefixSpan采用遞歸而Disc-all算法采用迭代。2022-2-2374 n考慮前面的序列數(shù)據(jù)庫，對于右側(cè)的一個基于二層劃分，仍然給定最小支持度為2，下面的例子展示了Disc策略是如何找到以3-序列模式的nSidSequence102030402022-2-2375 初始化3-序列集Sid3-Sequence104020n可以看出是一條3序列模式。Sid為30的序列沒有產(chǎn)生初始3

29、-序列因為其不包含以為前綴的3-子序列Sid3-Sequence102040n為條件序列，將所有3-序列替換為源序列的條件3-最小序列并重新排序，又發(fā)現(xiàn)一條3-序列模式2022-2-2376 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-2-2377 n重復上面的步驟，可以發(fā)現(xiàn)新的3-序列模式. 這時只有Sid

30、為10的序列含有比更大的3-序列，所以算法停止。Sid3-Sequence4020102022-2-2378Disc-all算法分析nDisc-all算法同樣不生成候選序列模式，減少了計算開銷。同時采用劃分技術(shù), 減少了搜索空間。應用Disc策略，解決了劃分效率隨劃分層次增加而下降的問題。nDisc-all采用的劃分技術(shù)不如prefixSpan高效，而且Disc策略較為復雜耗時，算法效率往往不及prefixSpan，但在處理長序列數(shù)據(jù)集時，因為Disc策略沒有迭代開銷同時投影技術(shù)效率有所下降， Disc-all表現(xiàn)反而更好。2022-2-2379 Disc-all和prefixSpan的性能比

31、較平均序列長度為20時，Disc-all和prefixSpan的性能比較2022-2-2380Disc-all和prefixSpan的性能比較平均序列長度為80時，Disc-all和prefixSpan的性能比較2022-2-2381 n用戶需要的往往是滿足特定條件的序列模式，而傳統(tǒng)的序列模式挖掘沒有考慮用戶的特殊要求，做了大量無效的挖掘。比如對于購買記錄的事務數(shù)據(jù)庫，用戶希望得到的序列模式事務之間的時間差不能太大。 2022-2-2382解決辦法引入約束的概念。在約束條件下做符合用戶要求的序列模式挖掘。一方面利用特定約束本身的性質(zhì)節(jié)省了挖掘的時間和空間，另一方面避免用戶陷入大量的無用信息。2022-2-2383約束的分類n單調(diào)約束：如果一個序列滿足，那么這個序列的所有超序列也滿足的約束；n反單調(diào)約束：如果一個序列滿足，那么這個