首页 » 机器学习实战 » 机器学习实战全文在线阅读

《机器学习实战》11.2 Apriori原理

关灯直达底部

假设我们在经营一家商品种类并不多的杂货店,我们对那些经常在一起被购买的商品非常感兴趣。我们只有4种商品:商品0,商品1,商品2和商品3。那么所有可能被一起购买的商品组合都有哪些?这些商品组合可能只有一种商品,比如商品0,也可能包括两种、三种或者所有四种商品。我们并不关心某人买了两件商品0以及四件商品2的情况,我们只关心他购买了一种或多种商品。

Apriori算法的一般过程

  1. 收集数据:使用任意方法。
  2. 准备数据:任何数据类型都可以,因为我们只保存集合。
  3. 分析数据:使用任意方法。
  4. 训练算法:使用Apriori算法来找到频繁项集。
  5. 测试算法:不需要测试过程。
  6. 使用算法:用于发现频繁项集以及物品之间的关联规则。

图11-2显示了物品之间所有可能的组合。为了让该图更容易懂,图中使用物品的编号0来取代物品0本身。另外,图中从上往下的第一个集合是Ø,表示空集或不包含任何物品的集合。物品集合之间的连线表明两个或者更多集合可以组合形成一个更大的集合。

图11-2 集合{0,1,2,3}中所有可能的项集组合

前面说过,我们的目标是找到经常在一起购买的物品集合。而在11.1节中,我们使用集合的支持度来度量其出现的频率。一个集合的支持度是指有多少比例的交易记录包含该集合。如何对一个给定的集合,比如{0,3},来计算其支持度?我们遍历每条记录并检查该记录包含0和3,如果记录确实同时包含这两项,那么就增加总计数值。在扫描完所有数据之后,使用统计得到的总数除以总的交易记录数,就可以得到支持度。上述过程和结果只是针对单个集合{0,3}。要获得每种可能集合的支持度就需要多次重复上述过程。我们可以数一下图11-2中的集合数目,会发现即使对于仅有4种物品的集合,也需要遍历数据15次。而随着物品数目的增加遍历次数会急剧增长。对于包含N种物品的数据集共有2N-1种项集组合。事实上,出售10 000或更多种物品的商店并不少见。即使只出售100种商品的商店也会有1.26 * 1030种可能的项集组合。对于现代的计算机而言,需要很长的时间才能完成运算。

为了降低所需的计算时间,研究人员发现一种所谓的Apriori原理。Apriori原理可以帮我们减少可能感兴趣的项集。Apriori原理是说如果某个项集是频繁的,那么它的所有子集也是频繁的。对于图11-2给出的例子,这意味着如果{0,1}是频繁的,那么{0}、{1}也一定是频繁的。这个原理直观上并没有什么帮助,但是如果反过来看就有用了,也就是说如果一个项集是非频繁集,那么它的所有超集也是非频繁的(如图11-3所示)。

A priori

A priori在拉丁语中指“来自以前”。当定义问题时,通常会使用先验知识或者假设,这被称作“一个先验”(a priori)。在贝叶斯统计中,使用先验知识作为条件进行推断也很常见。先验知识可能来自领域知识、先前的一些测量结果,等等。

图11-3 图中给出了所有可能的项集,其中非频繁项集用灰色表示。由于集合{2,3}是非频繁的,因此{0,2,3}、{1,2,3}和{0,1,2,3}也是非频繁的,它们的支持度根本不需要计算

在图11-3中,已知阴影项集{2,3}是非频繁的。利用这个知识,我们就知道项集{0,2,3},{1,2,3}以及{0,1,2,3}也是非频繁的。这也就是说,一旦计算出了{2,3}的支持度,知道它是非频繁的之后,就不需要再计算{0,2,3}、{1,2,3}和{0,1,2,3}的支持度,因为我们知道这些集合不会满足我们的要求。使用该原理就可以避免项集数目的指数增长,从而在合理时间内计算出频繁项集。

下一节将介绍基于Apriori原理的Apriori算法,并使用Python来实现,然后将其应用于虚拟商店Hole Foods的数据集上。