Tag: apriori

关联规则-剪枝的Apriori算法

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

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

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

Read more… »