Computational Complexity of Frequent Itemset Mining How many itemsets are potentially to be generated in the worst case? The number of frequent itemsets to be generated is senstive to the minsup threshold When minsup is low, there exist potentially an exponential number of frequent itemsets The worst case: M where M: distinct items, and N: max length of transactions The worst case complexty vS the expected probability Ex. Suppose Walmart has 104 kinds of products The chance to pick up one product 10-4 The chance to pick up a particular set of 10 products: w10-40 What is the chance this particular set of 10 products to be frequent 103 times in 109 transactions? 11
11 Computational Complexity of Frequent Itemset Mining ◼ How many itemsets are potentially to be generated in the worst case? ◼ The number of frequent itemsets to be generated is senstive to the minsup threshold ◼ When minsup is low, there exist potentially an exponential number of frequent itemsets ◼ The worst case: MN where M: # distinct items, and N: max length of transactions ◼ The worst case complexty vs. the expected probability ◼ Ex. Suppose Walmart has 104 kinds of products ◼ The chance to pick up one product 10-4 ◼ The chance to pick up a particular set of 10 products: ~10-40 ◼ What is the chance this particular set of 10 products to be frequent 103 times in 109 transactions?
烤鸭、面饼和甜面酱←-趣味数据挖掘 ■来自管理层的需求设想某理想小型超市,采用mini 版超市销售系统,管理了6种商品,记录了5个顾客 的购物单 流水号 所购物品清单 啤酒、薄饼、牛奶 2 烤鸭、薄饼、面酱 啤酒、烤鸭、薄饼、面酱 4 面酱,鸡蛋 烤鸭、面酱
烤鸭、面饼和甜面酱 ---趣味数据挖掘 ◼ 来自管理层的需求 设想某理想小型超市, 采用mini 版超市销售系统, 管理了6种商品，记录了5个顾客 的购物单 12 流水号 所购物品清单 1 啤酒、薄饼、牛奶 2 烤鸭、薄饼、面酱 3 啤酒、烤鸭、薄饼、面酱 4 面酱，鸡蛋 5 烤鸭、面酱
朴素方法 ■模仿选举计票方法统计单项高频集。模仿“唱票- 计票-写正字”的方法,逐条唱票-计票,得票不少 于两票的商品为: 单项统计 支持度 啤酒} 2/5 烤鸭 3/5 面饼} 3/5 面酱} 4/5
朴素方法 ◼ 模仿选举计票方法统计单项高频集。模仿 “唱票- 计票-写正字”的方法，逐条唱票-计票，得票不少 于两票的商品为： 13 单项统计 支持度 {啤酒} 2/5 {烤鸭} 3/5 {面饼} 3/5 {面酱} 4/5
■模仿选举计票方法统计双项高频集 商品总数记为M,M=6,M个对象的两两组合数目为 T=M*(M-1)/2,这里T=15,(与M变化趋势大致相 同),逐条唱票-计票,得票超过两票的“同购商品对” 双项统计 支持度 啤酒,面饼 2/5 烤鸭,面饼} 2/5 烤鸭,面酱} 3/5 {面饼,面酱} 2/5 14
◼ 模仿选举计票方法统计双项高频集 ◼ 商品总数记为M，M=6, M个对象的两两组合数目为 T=M*（M-1）/2，这里T=15 ,（与M2变化趋势大致相 同），逐条 唱票-计票，得票超过两票的“同购商品对” 14 双项统计 支持度 {啤酒，面饼} 2/5 {烤鸭，面饼} 2/5 {烤鸭，面酱} 3/5 {面饼，面酱} 2/5
模仿选举计票方法统计三项高频集 ■类似地,得到高频的同购三项集只有一项: 三项统计 支持度 烤鸭,面饼,面酱} 2/5 ■说明2/5=40%的顾客同时买了烤鸭、面饼和面酱 15
模仿选举计票方法统计三项高频集 ◼ 类似地，得到高频的同购三项集只有一项： ◼ 说明2/5=40%的顾客同时买了烤鸭、面饼和面酱。 15 三项统计 支持度 {烤鸭，面饼，面酱} 2/5