序列及apriori生成候選算法-資料下載頁(yè)
2025-02-25 15:24本頁(yè)面
【正文】 數(shù)據(jù)庫(kù)為 S中所有以 ?為前綴的序列相對(duì)于 ?的后綴，記為 S|? ? 例： a— 投影數(shù)據(jù)庫(kù)，由 4個(gè)后綴序列組成：(abc)(ac)d(cf)， (_d)c(bc)(ae)， (_b)(df)cb，(_f)cbc。 ? （ ab） －投影數(shù)據(jù)庫(kù) (_c)(ac)d(cf), (df)cb PrefixSpan算法 PrefixSpan算法 ?查找長(zhǎng)度為 1的序列模式 a:4,b:4,c:4,d:3,e:3,f:3 ?分割搜索空間 序列模式集可按 6個(gè)前綴被劃分為六個(gè)子集： 1）包含前綴 a的子集； …… ； 6）包含前綴 f的子集。 ?尋找序列模式的子集。構(gòu)建并遞歸挖掘投影數(shù)據(jù)庫(kù)。 PrefixSpan算法 ?尋找具有前綴 a的序列模式。 ?a— 投影數(shù)據(jù)庫(kù)，由 4個(gè)后綴序列組成：(abc)(ac)d(cf)， (_d)c(bc)(ae)， (_b)(df)cb，(_f)cbc。 ?掃描 a— 投影數(shù)據(jù)庫(kù)一遍 ， 找到含有前綴 a的長(zhǎng)度為 2的序列模式 ， 包括： aa： 2， ab： 4， (ab)：2， ac： 4， ad： 2， af： 2。 ?遞歸，所有具有前綴 a的序列劃分為 6個(gè)子集： 1）包含前綴 aa的子集； …… ； 6）包含前綴 af的子集 aa— 投影數(shù)據(jù)庫(kù)： (_bc)(ac)d(cf)。 不產(chǎn)生任何頻繁子序列 ， 結(jié)束 。 (ab)— 投影數(shù)據(jù)庫(kù)： (_c)(ac)d(cf)， (df)cb，包含前綴 (ab)的序列模式有： c， d， f， dc。 即 (ab)c， （ ab） d ， （ ab） f， （ ab） dc ab— 投影數(shù)據(jù)庫(kù)： (_c)(ac)d(cf)， (_c)a， c。序列模式： (_c)， (_c)a， a， c（ 即 a(bc)，a(bc)a， aba， abc） 。 ac— ， ad— ， af— 投影數(shù)據(jù)庫(kù) b－ ， c－ ， d－ ， e－ ， f－投影數(shù)據(jù)庫(kù) (ab)d— 投影數(shù)據(jù)庫(kù)： (cf)， (_f)cb 包含前綴 (ab)d的序列模式有： c 找到含有前綴 （ ab） d的序列模式，包括： (ab)dc ? 子程序 PrefixSpan(?, L, S|?) 參數(shù)： ? ：一個(gè)序列模式 ； L：序列模式 ?的長(zhǎng)度 S|? ： 如果 ?不為空時(shí)，為 ?－投影數(shù)據(jù)庫(kù)，否則為投影數(shù)據(jù)庫(kù) S， 1 掃描 S|?， 找到頻繁項(xiàng) b， b滿足： a)b可以作為 ?的最后一個(gè)元素 ， 形成一個(gè)序列模式；或者 b) b可以追加到 ?上 ， 形成一個(gè)序列模式 。 2） 對(duì)于每個(gè)頻繁項(xiàng) b， 追加到 ?上 ， 形成一個(gè)序列模式 ?’ ， 輸出 ?’ ； 3） 對(duì)于每個(gè) ?’ ， 構(gòu)建 ?’ — 投影數(shù)據(jù)庫(kù) S|?’ ， 調(diào)用 PrefixSpan(?’ ,l+1,S|?’ )。 前綴 投影 （ 后綴 ） 數(shù)據(jù)庫(kù) 序列模式 a (abc)(ac)d(cf),(_d)c(bc)(ae), (_b)(df)cb,(_f)cbc a,aa,ab,a(bc),a(bc)a,aba,abc,(ab), (ab)c,(ab)d,(ab)f,(ab)dc,ac,aca,acb,acc,ad,adc,af b (_c)(ac)d(cf),(_c)(ae), (df)cb,c b,ba,bc,(bc),(bc)a,bd, bdc,bf c (ac)d(cf),(bc)(ae),b,bc c,ca,cb,cc d (cf),c(bc)(ae),(_f)cb d,dbdc,dcb e (_f)(ab)(df)cb,(af)cbc e,ea,eab,eac,eacb,eb, ebc,ec,ecb, ef,efb,efc,efcb f (ab)(df)cb,cbc f,fb,fbc,fc,fcb PrefixSpan算法分析： PrefixSpan算法不需要產(chǎn)生候選序列模式，從 而大大縮減了檢索空間 相對(duì)于原始的序列數(shù)據(jù)庫(kù)而言，投影數(shù)據(jù)庫(kù) 的規(guī)模不斷減小 PrefixSpan算法的主要開(kāi)銷(xiāo)在于投影數(shù)據(jù)庫(kù)的 構(gòu)造 PrefixSpan算法 謝 謝！
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1