引例

啤酒与尿布

在一家超市里，有一个有趣的现象：尿布和啤酒赫然摆在一起出售。但是这个奇怪的举措却使尿布和啤酒的销量双双增加了。这不是一个笑话，而是发生在美国沃尔玛连锁店超市的真实案例，并一直为商家所津津乐道。沃尔玛拥有世界上最大的数据仓库系统，为了能够准确了解顾客在其门店的购买习惯，沃尔玛对其顾客的购物行为进行购物篮分析，想知道顾客经常一起购买的商品有哪些。沃尔玛数据仓库里集中了其各门店的详细原始交易数据。在这些原始交易数据的基础上，沃尔玛利用数据挖掘方法对这些数据进行分析和挖掘。

一个意外的发现是：”跟尿布一起购买最多的商品竟是啤酒！经过大量实际调查和分析，揭示了一个隐藏在”尿布与啤酒”背后的美国人的一种行为模式：在美国，一些年轻的父亲下班后经常要到超市去买婴儿尿布，而他们中有30%～40%的人同时也为自己买一些啤酒。产生这一现象的原因是：美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。
按常规思维，尿布与啤酒风马牛不相及，若不是借助数据挖掘技术对海量交易数据进行挖掘和分析，沃尔玛是不可能发现数据内在这一有价值的规律的。

概念

从上例可以看出某些看起来不具有关联的事务实际上也有关联，为了找到这些关联，首先定义一些符号。

关联规则是一个蕴含式 x=>y。他表示当x出现时y也一定会出现。

当然这种情况是非常少的，一般带有一定概率，为了表示这种概率，我们定义了支持度进行表示：D（所有样本）中包含X、Y的数量和所有交易数之比，记为Support(x=>y)或S

置信度是D中包含X、Y的交易数和X的交易数之比，记为confidence(x=>y)或C

支持度表示了这种类型在所有样本中出现的概率，如果概率太小表示这种情况出现很少，不具有代表性。而置信度表示了二者之间的联系，置信度越高联系越紧密。

关联规则就是要找支持度和置信度都大于某一范围的。

使用文字描述可以认为

C = 同时购买商品X和Y的交易数/购买X的交易数
S = 同时购买X和Y的交易数/总交易数

Apriori算法

术语：

  • 频繁项集： 支持度大于最小支持度的项集

规则：

  • 一个频繁项集的子集一定是频繁项集
  • 一个非频繁项集的超集一定不是频繁项集
  • 连接规则： 我们可以把两个部分相同项集相同的部分合并，变成一个项集。例如ABC和BCE可以合成ABCE

例如：

第一次购买    AB
2          BCE
3          ABCE
4         AD
假设置信度和支持度最少都要是50%

  1. 首先选择只有一个的项集。A B C D E.其中D的支持度只有25%小于最小支持度，抛弃
  2. 从A、B、C、E中得到两个的项集，有AB、AC、AE、BC、BE、CE。其中AC、AE小于最小支持度，抛弃
  3. 使用连接规则得到ABC、ABE、BCE、ACE。其中AC不是频繁项，所以ABC不存在，同理可以排除ACE、ABE，只剩下BCE。而BCE是频繁项集，所以保留

从上面我们可以看出，算法过程大致为：

  1. 首先找一个元素的频繁项集
  2. 根据一个元素的频繁项集找到两个元素的频繁项集
  3. 在多于两个元素的频繁项集中，首先使用联接规则找到k+1个元素的项集，然后使用前两个规则进行剪枝，最后找到频繁项集
  4. 重复上述步骤直到不能产生新的项集