Tag: 关联规则

关联规则-剪枝的Apriori算法

上一篇简单介绍了关联规则的基本概念,继续这个部分,这篇来说一些稍微优化的算法,最后以“挖掘”我们的文具系统为例收尾。

上篇的“啤酒尿布”事件中,我们如果要算频繁三项集,使用的是“蛮力法”,即产生C(6,3) =20个 所有的三项集,再每个去判断它是不是频繁的。但数据集的项只有6个时,这不算什么,假设有400个时,如果要把全部三项集都算出来,那么要计算C(400,3) = 10586800 个,然后再去查每个是否是频繁的。有没有更快的方法,减少这么大的计算量?

在上一个例子中,我们可以发现,鸡蛋在5个事务中,只出现了一次,而包含了鸡蛋的所有三项集的支持度计数都不会超过1,如果按上一篇,我们要求支持度为0.4,也就是要求在5个事务中,至少出现2次,所以这就意味着“所有包含了鸡蛋的三项集必然不符合要求”。这就意味着,我们可以先计算“频繁1项集”,对于不符合条件的1项集就直接减掉,不再在它的基础上产生3项集了。这样就大大减少了最后产生项集的个数。

Read more… »

关联规则-基本概念

分类,聚类,关联规则是数据挖掘的三大部分,先记下关联规则的概念

关联规则有两个关键概念,支持度和置信度。先放概念:关联规则是形如 X -> Y的表达式,其中X和Y是不相交的项集。关联规则的强度可以用它的支持度和置信度来度量。支持度确定规则可以用于给定数据集的频繁程度,而置信度确定Y在包含X的事务中出现的频繁程度。

举例配合下这个说明,著名的啤酒和尿布事件。

假设有这几件物品, [ 面包 | 牛奶 | 尿布 | 啤酒 | 鸡蛋 | 可乐],有以下几个客户的一次购买数据,0表示没有买,1表示买了:

  1. [1,1,0,0,0,0]
  2. [1,0,1,1,1,0]
  3. [0,1,1,1,0,1]
  4. [1,1,1,1,0,0]
  5. [1,1,1,0,0,1]

Read more… »