序列及apriori生成候選算法(參考版)
2025-02-27 15:24本頁面
【正文】 2） 對于每個(gè)頻繁項(xiàng) b， 追加到 ?上 ， 形成一個(gè)序列模式 ?’ ， 輸出 ?’ ； 3） 對于每個(gè) ?’ ， 構(gòu)建 ?’ — 投影數(shù)據(jù)庫 S|?’ ， 調(diào)用 PrefixSpan(?’ ,l+1,S|?’ )。序列模式： (_c)， (_c)a， a， c（ 即 a(bc)，a(bc)a， aba， abc） 。 (ab)— 投影數(shù)據(jù)庫： (_c)(ac)d(cf)， (df)cb，包含前綴 (ab)的序列模式有： c， d， f， dc。 ?遞歸，所有具有前綴 a的序列劃分為 6個(gè)子集： 1）包含前綴 aa的子集； …… ； 6）包含前綴 af的子集 aa— 投影數(shù)據(jù)庫： (_bc)(ac)d(cf)。 ?a— 投影數(shù)據(jù)庫，由 4個(gè)后綴序列組成：(abc)(ac)d(cf)， (_d)c(bc)(ae)， (_b)(df)cb，(_f)cbc。構(gòu)建并遞歸挖掘投影數(shù)據(jù)庫。 ? （ ab） －投影數(shù)據(jù)庫 (_c)(ac)d(cf), (df)cb PrefixSpan算法 PrefixSpan算法 ?查找長度為 1的序列模式 a:4,b:4,c:4,d:3,e:3,f:3 ?分割搜索空間 序列模式集可按 6個(gè)前綴被劃分為六個(gè)子集： 1）包含前綴 a的子集； …… ； 6）包含前綴 f的子集。 ?的子序列 ?’（ ?’ ??）， ?’被稱為 ?關(guān)于前綴 ?的投影，當(dāng)且僅當(dāng) 1） ?是 ?’的前綴 2）不存在 ?’的超集 ?//（即 ?’ ? ?//， ?’ ? ?//），使得 ?//是 ?的子序列并且 ?是 ?//的前綴。 ?不需要生成候選序列。 PrefixSpan算法 （通過前綴投影挖掘序列模式） Prefixprojected Sequential pattern mining ?基本思想：序列數(shù)據(jù)庫投影時(shí)，并不考慮所有可能出現(xiàn)的頻繁子序列，而 只檢驗(yàn)前綴 序列 ， 然后把相應(yīng)的后綴序列投影成投影數(shù)據(jù)庫。 1. 掃描序列數(shù)據(jù)庫 S， 找到 S中的頻繁項(xiàng)集 ， 并以降序排列生成 f_list列表 。 FreeSpan算法 項(xiàng) 長度為 2的序列模式 循環(huán)項(xiàng)標(biāo)記 投影數(shù)據(jù)庫標(biāo)記 f bf:2,fb:2,(bf):2 ｛ b+ f+ ｝ Φ e be:3,(ce):2 b+ e (ce): d bd:2, db:2, (bd):2 cd:2, dc:2, da:2 ｛ b+ d ｝ d a+ da: {bc} {cd}: a …… …… …… c …… …… …… b bb:4 b b+ Φ FreeSpan算法 ? S，生成循環(huán)項(xiàng)模式和投影數(shù)據(jù)庫； ?｛ b+ f+ ｝ b+ e ｛ b+ d ｝ d a+ b b+ ?{bbf:2,fbf:2,(bf)b:2,(bf)(bf):2, (bd)b:2,bba:2,aba:2,aba:2, abb:2,bcb:2,bbc:2} 四個(gè)投影數(shù)據(jù)庫如下圖： FreeSpan算法 ?投影挖掘算法挖掘更長的候選模式。 ?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] 僅有一個(gè)計(jì)數(shù)值， F[j,k] 有三個(gè)計(jì)數(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的序列模式 ? 標(biāo)記循環(huán)項(xiàng)模式和投影數(shù)據(jù)庫； ?循環(huán)項(xiàng)模式標(biāo)記形如 $α iγ α jγ $，其中$…$ 表示兩種形式 … ， ｛ … ｝。 FreeSpan算法 序列 id 序列 項(xiàng) 10 (bd)cb(ac) {a,b,c,d} 20 (
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1