1联结分析（Association Rules）范例.pptVIP

Rule Measures: Support and Confidence Find all the rules X Y ? Z with minimum confidence and support support, s, probability that a transaction contains {X ? Y ? Z} confidence, c, conditional probability that a transaction having {X ? Y} also contains Z Mining Association Rules—An Example For rule A ? C: support = support({A ?C}) = 50% confidence = support({A ?C})/support({A}) = 66.6% The Apriori principle: Any subset of a frequent itemset must be frequent The Apriori Algorithm — Example 1.聯結分析(Association Rules) 範例 聯結分析 Rule X→Y 滿足X∩Y=? 1.X和Y的所有交易項目的集合，必須出現在至少S%全部交易中…minimum support 2.在所有包含X之交易中，至少有C%包含Y的交易…minimum confidence 聯結分析演算法(一) 1.計算出所有1-itemset的支持度，並找出1-itemsets的支持率大於或等於最小支持率的集合(稱之為large 1-itemsets)若large 1-itemsets為空集合，則停止執行 2.結合所有large 1-itemsets中的項目，形成多個候選的2-itemset ，同樣地找出2-itemset的支持率大於或等於最小支持率的集合(稱之為large 2-itemsets)若large 2-itemsets為空集合，則停止執行 3.對於large 2-itemsets中每一個2-itemset ，列出所有可能的聯結法則，並且選擇其信賴度大於或等於最小信賴度的聯結法則 4.結合large 2-itemsets中的項目，形成多個候選的3-itemset ，若候選的3-itemset之任一個2-itemset子集合沒有出現在large 2-itemsets中，則刪除此候選的3-itemset 對於留下之後選的3-itemset ，找出3-itemset的支持率大於或等於最小支持率的集合(稱之為large 3-itemsets)若large 3-itemsets為空集合，則停止執行 5.對於large 3-itemsets中的每一個3-itemset ，列出所有可能的聯結法則，並且選擇其信賴度大或等於最小信賴度的聯結法則 6.重複步驟4和5 ，產生large k-itemsets(k3)與大於或等於最小信賴度的聯結法則，直到large k-itemsets為空集合為止 1-itemset(S%=30%) 2-itemset * 1.聯結分析(Association Rules) 範例 Let minimum support 50%, and minimum confidence 50%, we have A ? C (50%, 66.6%) C ? A (50%, 100%) Customer buys diaper Customer buys both Customer buys beer Min. support 50% Min. confidence 50% Database D Scan D C1 L1 L2 C2 C2 Scan D C3 L3 Scan D 碳酸飲料，洋芋片 5 碳酸飲料，底片 4 柳橙汁，洗衣精，碳酸飲料 3 牛奶，柳橙汁，清潔用品 2 柳橙汁，碳酸飲料，清潔用品 1 交易項目 交易代號 ╳ 20% 洋芋片 ╳ 20% 底片 ╳ 20% 洗衣精 ╳ 20% 牛奶 ˇ 40% 清潔用品 ˇ 80% 碳酸飲料 ˇ 60% 柳橙汁 Large 1-itemset 支持率 1-itemset ╳ 20% 碳酸飲料，清潔用品 ˇ 40% 柳橙汁，清潔用品 ˇ 40% 柳橙汁，碳酸飲料 Large 2-itemset 支持率 2-itemset 1.柳橙汁 → 碳酸飲料 c=66.67 % 2.碳酸飲料 → 柳橙汁 c=50 % 3.柳橙汁 → 清潔用品 c=66.67 % 4.清潔用品 → 柳橙汁 c=100 % * Large 3-itemset is empty *