Report-implement the Apriori algorithm
第 21 組 108062468 張志宇
一、 Apriori 演算法介紹
1. 輸入 dataset 和 itemset,itemset 作爲初始候選集 C
1
2. 計算 C
1
中每個 item 的在 dataset 中的支持度(support), 對比閾值(s)
生成頻繁項集 L
1
,此時 k=1
3. 將 L
k
×L
k
,進行 cartesian product 得到候選集 C
k+1
4. 通過和 L
k
的比較,對 C
k+1
進行剪枝(prune)
5. 計算 C
k+1
中每個 item pair 的在 dataset 中的支持度(support),對比閾值
(s)生成頻繁項集 L
k+1
6. 轉入步驟 3 直到符合給定的條件
二、 程式設計
1、第一個 mapreduce
Mapper 中[setup]讀取輸入的 itemset,把每一個 item 找出來;[map]中一行行