數(shù)據(jù)挖掘基本算法ppt課件-資料下載頁
2025-04-30 18:14本頁面
【正文】 列： itemset(T1), itemset(T2),…, itemset(Tn) 。73 挖掘序列模式? 如果一個序列 s包含于一個客戶序列中，則我們稱該客戶支持（ support）序列 s。? 一個具體序列的支持（ support）定義為那一部分支持該序列的客戶總數(shù)。? 給定一個客戶交易組成的數(shù)據(jù)庫 D，挖掘序列模式的問題就是在那些具有客戶指定最小支持度（ minimum support）的序列中找出最大序列。而每個這樣的最大序列就代表了一個序列模式（ sequence pattern）。74 挖掘序列模式? 實現(xiàn)算法可以分五個具體階段來找出所有的序列模式，分別是排序階段、大項集階段、轉(zhuǎn)換階段、序列階段以及最大值階段。? 序列模式分析規(guī)則挖掘的重點在于分析數(shù)據(jù)間的前后（因果）關(guān)系，可以發(fā)現(xiàn)客戶潛在的購物模式，規(guī)則是 “先購買了商品 X的顧客后購買產(chǎn)品 Y”，置信度和支持度由決策者輸入。? 序列模式挖掘是基于時間或者其他序列的經(jīng)常發(fā)生的模式。? 應(yīng)用領(lǐng)域：客戶購買行為模式預(yù)測、 Web訪問模式預(yù)測、疾病診斷、自然災(zāi)害診斷、 DNA序列分析。75 挖掘序列模式? 序列模式挖掘的很多參數(shù)對挖掘的結(jié)果有很大影響。1）時間序列 T的持續(xù)時間，即這個時間序列的有效時間或者是用戶選擇的一個時間段。2）時間折疊窗口 W。在一段時間內(nèi)發(fā)生的幾件事件可以被看作是同時發(fā)生的。3）時間間隔 int，這個參數(shù)表示發(fā)現(xiàn)的模式的時間間隔。? int=0? min_inervalintmax_interval? int=c76 挖掘序列模式（ 2）序列模式挖掘的主要算法GSP算法： 類似于 Apriori算法。PrefixSpan算法： 采用分而治之的思想，不斷產(chǎn)生序列數(shù)據(jù)庫的多個更小的投影數(shù)據(jù)庫，然后在各個投影數(shù)據(jù)庫上進(jìn)行序列模式挖掘。77 挖掘序列模式? 上述算法存在的主要問題：167。 缺少時間限制 ：用戶可能需要指定序列模式的相鄰元素之間的時間間隔。例如，一個序列模式可能會發(fā)現(xiàn)客戶在購買了物品 A后的第三年購買物品 B。我們需要的卻是給定時間間隔內(nèi)用戶的購買意向。167。 事務(wù)的定義過于嚴(yán)格 ：一個事務(wù)中包含在客戶的一次購買行為中所購買的所有物品。可能需要指定一個滑動時間窗口，客戶在滑動時間窗口的時間段內(nèi)的所有的購買行為均作為一個事務(wù)。167。 缺少分類層次 ：只能在項目的原始級別上進(jìn)行挖掘。78 挖掘序列模式（ 2）序列模式挖掘的主要算法1） GSP算法? 掃描序列數(shù)據(jù)庫，得到長度為 l的序列模式 L1，作為初始的種子集。? 掃描長度為 i的種子集 Li ，通過連接操作和剪切操作生成長度為 i+1的候選序列模式 Ci+1；然后掃描序列數(shù)據(jù)庫，計算每個候選序列模式的支持?jǐn)?shù)，產(chǎn)生長度為 i+1的序列模式Li+1，并將 Li+1作為新的種子集。? 重復(fù)第二步，直到?jīng)]有新的序列模式或新的候選序列模式產(chǎn)生為止。L1? C2 ? L2 ? C3 ? L3 ? C4 ? L4 ? ……79 挖掘序列模式? 產(chǎn)生候選序列模式主要分為兩步：? 連接階段：如果去掉序列模式 s1的第一個項目與去掉序列模式 s2的最后一個項目所得到的序列相同，則可以將 s1與 s2進(jìn)行連接，即將 s2的最后一個項目添加到 s1中。? 剪切階段：若某候選序列模式的某個子序列不是序列模式，則此候選序列模式不可能是序列模式，將它從候選序列模式中刪除。80 挖掘序列模式? 例：下圖演示了如何從長度為 3的序列模式產(chǎn)生長度為 4的候選序列模式。Sequential patternsWith length 3Candidate 4SequencesAfter Join After Pruning(1,2) 3 (1,2) (3,4) (1,2) (3,4)(1,2) 4 (1,2) 3 51 (3,4)(1,3) 52 (3,4)2 3 581 挖掘序列模式? 候選序列模式的支持度計算：對于給定的候選序列模式集合 C，掃描序列數(shù)據(jù)庫，對于其中的每一條序列 d，找出集合 C中被 d所包含的所有候選序列模式，并增加其支持度計數(shù)。? GSP算法存在的主要問題：? 1）如果序列數(shù)據(jù)庫的規(guī)模較大，則有可能會產(chǎn)生大量的候選序列模式；? 2）需要對序列數(shù)據(jù)庫進(jìn)行循環(huán)掃描；? 3）對于序列模式的長度比較長的情況，由于其對應(yīng)的短的序列模式規(guī)模太大，本算法很難處理。82 挖掘序列模式2） PrefixSpan算法（基于前綴投影的序列模式挖掘算法）? 相關(guān)定義如下：? 前綴。設(shè)每個元素中的所有項目按照字典序排列。給定序列 ? =(a1,a2,…,a n) ， ? (m≤n)，如果則稱 ?是 ?的前綴。83 挖掘序列模式? 投影。給定序列 ?和 ?，如果 ?是 ?的子序列，則 ?關(guān)于 ?的投影 ?’必需滿足： ?是 ?’的前綴， ?’是 ?的滿足上述條件的最大子序列。? 后綴。序列 ?關(guān)于子序列 ?的投影 ?’(n≥m)，則序列 ?關(guān)于子序列 ?的后綴為84 挖掘序列模式? 算法描述：? 掃描序列數(shù)據(jù)庫，生成所有長度為 l的序列模式。? 根據(jù)長度 l的序列模式，生成相應(yīng)的投影數(shù)據(jù)庫。? 在相應(yīng)的投影數(shù)據(jù)庫上重復(fù)上述步驟，直到在相應(yīng)的投影數(shù)據(jù)庫上不能產(chǎn)生長度為 l的序列模式為止。? 投影數(shù)據(jù)庫：設(shè) ?為序列數(shù)據(jù)庫 S中的一個序列模式，則 ?的投影數(shù)據(jù)庫為 S中所有以 ?為前綴的序列相對于 ?的后綴，記為 S| ? 。? 投影數(shù)據(jù)庫中的支持?jǐn)?shù)：設(shè) ?為序列數(shù)據(jù)庫 S中的一個序列模式，序列 ?以 ?為前綴，則 ?在 ?投影數(shù)據(jù)庫 S中支持?jǐn)?shù)為S| ?滿足條件 ? ? ?.?的序列 ?的個數(shù)。85 挖掘序列模式? PrefixSpan算法167。 輸入：序列數(shù)據(jù)庫 S及最小支持度閾值 min_sup167。 輸出：所有的序列模式167。 方法：調(diào)用子程序 PrefixSpan(() 0, S)86 挖掘序列模式? 子程序 PrefixSpan(?, L, S|?)167。 參數(shù)： ? 為一個序列模式 ； L為序列模式 ?的長度； S|?如果 ?為空，則為 S，否則為 ?的投影數(shù)據(jù)庫。216。掃描 S|?，找到滿足下述要求的長度為 1的序列模式 b：?b可以添加到 ?的最后一個元素中并為序列模式?b可以作為 ?的最后一個元素并為序列模式216。對每個生成的序列模式 b，將 b添加到 ?形成序列模式 ?’，并輸出 ?’216。對每個 ?’,構(gòu)造 ?’的投影數(shù)據(jù)庫 S|?’ ,并調(diào)用子程序PrefixSpan(?’, L + 1, S|?’)87 挖掘序列模式? PrefixSpan算法分析：167。 PrefixSpan算法不需要產(chǎn)生候選序列模式，從而大大縮減了檢索空間167。 相對于原始的序列數(shù)據(jù)庫而言，投影數(shù)據(jù)庫的規(guī)模不斷減小167。 PrefixSpan算法的主要開銷在于投影數(shù)據(jù)庫的構(gòu)造88 挖掘序列模式? PrefixSpan算法的主要改進(jìn)：167。 逐層投影 ：使用隔層投影代替逐層投影，從而可以有效減小投影數(shù)據(jù)庫的個數(shù)167。 偽投影 ：當(dāng)序列數(shù)據(jù)庫可以直接放入內(nèi)存時，可以使用偽投影操作代替實際的投影數(shù)據(jù)庫，從而可以有效減少構(gòu)造投影數(shù)據(jù)庫的
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1