apriori算法的学习

一、apriori算法产生

  1993年美国学者Agrawal提出通过分析购物篮中的商品集合，从而找出商品之间关联关系的关联算法，并根据商品之间的关系，找出客户的购买行为。Agrawal从数学及计算机算法角度提出了商品关联关系的计算方法——Apriori算法。 沃尔玛从上个世纪90年代尝试将Aprior算 法引入到POS机数据分析中，并获得了成功，于是产生了“啤酒与尿布”的故事。

1.1、如何寻找？

在历史购物记录中，一些商品总是在一起购买。但人看上去不是那么的直观的，而是隐蔽的。让计算机做这事，设法计算法让计算机自动去找，找到这样的模式(规律)。

1.1.1、目标:寻找那些总是一起出现商品。

A和B一起出现

1.1.2、判断的阈值

• 支持度： A,B一起出现的次数 占 总购买次数的 比例
  • support(A->B) = P(AB)
• 置信度(局部)： A,B一起出现的次数 占 购买A次数的 比例
  • confidence(A->B) = P(B|A) =P(AB)/P(A)=AB一起出现次数/A的次数
  • 注意A->B， 和B->A是不同的。
  • 条件概率是指事件A在另外一个事件B已经发生条件下的发生概率。条件概率表示为：P（A|B），读作“在B的条件下A的概率”。

支持度、置信度越大，商品出现一起购买的次数就越多，可信度就越大。

1.1.3 介绍几个概念

项集：项的集合称为项集，即商品的组合。 k项集：k种商品的组合，不关心商品件数，仅商品的种类。 项集频率：商品的购买记录数，简称为项集频率，支持度计数。 注意，定义项集的支持度有时称为相对支持度，而出现的频率(比例)称为绝对支持度。 频繁项集：如果项集的相对支持度满足给定的最小支持度阈值，则该项集是频繁项集。 强关联规则:满足给定支持度和置信度阈值的关联规则

1.2、明确问题

1、找出总是在一起出现的商品组合 2、提出衡量标准支持度、置信度(达到一定的阈值) 3、给出支持度、置信度直观计算方法 4、得出在计算方法中起决定因素的是频繁项集 5、由频繁项集轻松找到强关联规则

找关联规则--------->找频繁项集 步骤：

1. 找出所有的频繁项集；这个项集出现的次数至少与要求的最小计数一样。如在100次购买记录中，至少一起出现30次。
2. 由频繁项集产生强关联规则；这些关联规则满足最小支持度与最小置信度。

1.3、不满足的商品组合的剔除 1.3.1、先验性质:频繁项集的所有非空子集也一定是频繁的。

• 买AB两种商品的次数比较多， 买A一定也比较多

1.3.2、逆否命题:若一个项集是非频繁的,则它的任何超集也是非频繁的。

• 买A商品比较少， 那么同时买AB组合一定也比较少。

像下图中红色的部分就是根据1.3.2进行剔除的。如D出现的次数比较少， 它的组合次数一定比较少， 所以将商品D剔除。

二、Apriori算法的确定和改进 2.1、问题

多次数据库扫描 巨大数量的候补项集 繁琐的支持度计算

2.2、改善Apriori: 基本想法

减少扫描数据库的次数 减少候选项集的数量 简化候选项集的支持度计算