最近在看Peter Harrington写的“机器学习实战”,这是我的学习心得,这次是第11章 - 使用Apriori算法进行关联分析。
Apriori 是 A priori, “一个先验”的意思。可以说是一种发现关联的优化算法。 以购买商品为例,每条数据是一个交易的商品清单。我们是否可以发现哪些商品组合更容易出现? 客户可能购买1个商品,或者最多n个商品,如果商店一共有m个商品,那么共有种 \textstyle \coprod_{i=1}^n {m + 1 -i}组合方式。 计算每种组合方式的出现概率虽然看起来简单,但是效率非常低。
因此,它先计算1个元素的概率,去掉不满足最小支持度的项集,得到项集集合C1和每个项集的支持度; 然后在项集集合C1的基础上,找2个元素的支持度(这时将不会考虑去掉的项集,所以性能会优化),再去掉不满足最小支持度的2项项集,得到项集C2和每个项集的支持度; 以此类推,直到得到项集Cm和每个项集的支持度。
对每个Level的项集(Level>0):
对当前Level的每个项集:
获取项集的元素List.
如果Level = 1(2个项数的项集):
calculateConfidence(当前项集,元素List,项集的支持度,关联规则, 最小可信度)
如果Level > 1(至少3个项数的项集):
rulesFromConsequence(当前项集,元素List,项集的支持度,关联规则, 最小可信度)
对每个目标项集
计算当前目标项集在当前项集上的可信度。
如果可信度大于最小可信度:
把[当前项集 - 目标项集, 目标项集, 可信度]加入关联规则;
把当前目标项集加入有效目标集。
返回有效目标集
得到目标项集长度m.
如果当前项集元素的长度 > m + 1:
得到目标项集元素个数为m + 1的目标项集List。
有效目标集 = calculateConfidence(当前项集,目标项集,项集的支持度,关联规则, 最小可信度)
如果有效目标集的长度 > 1:
rulesFromConsequence(当前项集,有效目标集,项集的支持度,关联规则, 最小可信度)。