Frequent Itemset and Association Rule 频繁项集和关联规则

频繁项集

市场-篮子模型(market-basket model):

  1. 东西(items)的集和,例如超市所有商品的集和
  2. 篮子 (baskets)的集和,例如人们在超市购物的各个清单的集和

频繁项集(frequent itemset)关心的问题:

  • 找出篮子中常见的itemset
  • 支持度:包含这个itemset的篮子数量
  • 阈值:超过多少个篮子中有这个itemset时称这一系列东西是频繁的

假设超市共有5样商品,一共有8笔账单:

找出支持度大于3的2个东西构成的频繁项集:

找出所有支持度大于3频繁项集:

关联规则

关联规则{i_1,i_2,dots,i_k}rightarrow j表示,如果一个篮子里有这k样东西,那么狠有可能篮子里同时还有j这样东西。

衡量规则的强弱,用信心(confidence)来衡量,即条件概率 P(j text{in basket}| i_1,i_2,dots,i_k text{in basket})

例如:{'beer','milk'} -> 'coke'这个关联规则的信心是0.5。

找出关联规则:

  1. 找出所有支持度至少为cs的频繁项集(结果中{i_1,i_2,dots,i_k, j}的最低支持度)
  2. 找出所有支持度至少为s的频繁项集(结果中{i_1,i_2,dots,i_k}的最低支持度,通常s > cs)
  3. 对于1.所获频繁项集中的每一个itemset:
    取itemset一个去掉一个商品后的子集,看该子集是否在2.所获频繁项集中:
    如果在,计算相应规则的confidence,若超过信心阈值c,则表示发现一条规则,信心的计算方式为:itemset的支持度/子集的支持度

Leave a Reply

Your email address will not be published. Required fields are marked *