序列及apriori生成候選算法(編輯修改稿)
2025-03-15 15:24 本頁面
【文章內容簡介】 1 3 4 1 3 5 2 3 4 3 4 5 AprioriSome算法 C3 C4 1 2 3 4 1 2 4 3 1 3 4 5 1 3 5 4 修剪 AprioriSome算法 C5為空結束前階段進入回溯階段 1 3 5 3 4 5 刪除了 L4的子序列后的 C3 再計數(shù)發(fā)現(xiàn) 1 3 5是最大 3序列 L4 4序列 支持度 1 2 3 4 2 序列 支持度 1 2 3 4 2 1 3 5 2 4 5 2 AprioriSome算法 最大的頻繁序列 除 4 5以外 L2中所有的序列都被刪除 L1中所有的序列都被刪除 ? 類 Apriori算法有以下缺點： ? 有可能生成龐大眾多的候選序列。 ? 多遍掃描數(shù)據(jù)庫。 ? 不易發(fā)生長度較大的序列模式。序列模式越長，所需要生成的序列就越多。 FreeSpan算法 頻繁模式投影的序列模式挖掘 Frequent patternprojected Sequential pattern mining ? 基本思想（基于數(shù)據(jù)庫投影和分片技術） 利用頻繁項遞歸地將序列數(shù)據(jù)庫投影到更小 的投影數(shù)據(jù)庫集中，在每個投影數(shù)據(jù)庫中生 成子序列片段。 FreeSpan算法 序列 id 序列 項 10 (bd)cb(ac) {a,b,c,d} 20 (bf)(ce)b(fg) {b,c,e,f,g} 30 (ah)(bf)abf {a,b,f,h} 40 (be)(ce)d {b,c,d,e} 50 a(bd)bcb(ade) {a,b,c,d,e} 序列數(shù)據(jù)庫 最小支持度設為 2 FreeSpan算法 ? L1 ?頻繁項按支持度降序排列形成頻繁項列表， ?f_list=b:5,c:4,a:3,d:3,e:3,f:3 ?根據(jù) f_list，序列模式集被分為不相交的六個子集： 1）只包含項 f； ?? ?分而自治策略 FreeSpan算法 ? 頻繁項矩陣 F用于生成長度為 2的序列模式， 投影數(shù)據(jù)庫 集用于生成長度為 3及更長的序列模式 ?F是一個三角矩陣 F[j,k]（ 1≤j≤m ，1≤k≤j ）。其中 F[j,j]（ 1≤j≤m ）僅有一個計數(shù)值，而其他每個 F[j,k]（ 1≤j≤m ， 1≤k≤j ）有三個計數(shù)值：（ A,B,C） 序列模式 α 的投影數(shù)據(jù)庫 是含有 α 的序列集的子序列，非頻繁項及 α 后的項也被刪除。 ?F矩陣圖 4 (4,3,0) 1 (3,2,0) (2,1,1) 2 (2,2,2) (2,2,0) (1,2,1) 1 (3,1,1) (1,1,2) (1,0,1) (1,1,1) 1 (2,2,2) (1,1,0) (1,1,0) (0,0,0) (1,1,0) 2 1b 2c 3a 4d 5e 6f 1b 2c 3a 4d 5e 6f F[j,j] 僅有一個計數(shù)值， F[j,k] 有三個計數(shù)值：（ A,B,C） ijikikij （ ikij） 序列 (bd)cb(ac) (bf)(ce)b(fg) (ah)(bf)abf (be)(ce)d a(bd)bcb(ade) FreeSpan算法 ? 2的序列模式 ? 標記循環(huán)項模式和投影數(shù)據(jù)庫； ?循環(huán)項模式標記形如 $α iγ α jγ $，其中$…$ 表示兩種形式 … ， ｛ … ｝。 ?投 影 數(shù) 據(jù) 庫 標 記 形 如 $ α i α j $ ：｛ bp,… ,bq｝ ， ｛ bp,… ,bq｝ 表示在子序列挖掘過程中與 $α iα j$合在一起生成長度更長的序列模式的頻繁項集 。 FreeSpan算法 項 長度為 2的序列模式 循環(huán)項標記 投影數(shù)據(jù)庫標記 f bf:2,fb:2,(bf):2 ｛ b+ f+ ｝
環(huán)評公示相關推薦
鄂ICP備17016276號-1