Please enable JavaScript.
Coggle requires JavaScript to display documents.
Apriori - Coggle Diagram
Apriori
方法
Ct = subset(Ck,t); //得到t的子集
for each candidate c∈Ct
for each transaction t∈D{ //掃描D進行候選計數
c.count++; //支持度計數}
Ck = aproiri_gen(Lk-1,min_sup);
Lk={c∈Ck| c.count ≥min_sup} //返回候選項集中不小於最小支持度的項集}
for(k = 2; Lk-1 ≠ ∅; k++) {//產生候選，並剪枝
return L = ∪kLk；//所有的頻繁集
L1 = find_frequent_1_itemsets(D);//找出頻繁1-項集的集合L1
性質
先驗定理
如果一個項集是頻繁的，則它的所有子集一定也是頻繁的。
反單調
意指如果一個集合不能通過測試，則它的所有超集也都不能通過相同的測試。稱它為反單調的，因為在通不過測試的意義下，該性質是單調的。
挖掘頻繁項集
連接步
for each itemset l1∈Lk-1
for each itemset l2∈Lk-1
Procedure apriori_gen(Lk-1: frequent (k-1)-itemset; min_sup: support)
if has_infrequent_subset(c,Lk-1) then
if(l1[1]=l2[1])∧...∧(l1[k-2]=l2[k-2])∧(l1[k-1]<l2[k-1]) then{
c = l1 l2; //連接步：l1連接l2 //連接步產生候選，若K-1項集中已經存在子集c，則進行剪枝
delete c; //剪枝步：刪除非頻繁候選
else add c to Ck;}
return Ck;
剪枝步
return TRUE;
if c∉Lk-1 then
for each (k-1)-subset s of c
Procedure has_infrequent_subset(c:candidate k-itemset; Lk-1:frequent (k-1)-itemset) //使用先驗定理
return FALSE;