频繁项集Apriori算法(3)

下面直接通过例子描述该算法：如下图所示（注意Items已经排好序），使用Apriori算法关联规则挖掘数据集中的频繁项集。（最小支持度技术为2）

具体过程如下所示：

具体分析结果：

第一次扫描：对每个候选商品计数得C1，由于候选{D}支持度计数为1<最小支持度计数2，故删除{D}得频繁1-项集合L1；

第二次扫描：由L1产生候选C2并对候选计数得C2，比较候选支持度计数与最小支持度计数2得频繁2-项集合L2；

第三次扫描：用Apriori算法对L2进行连接和剪枝产生候选3项集合C3的过程如下：

1.连接：

C3=L2 (连接)L2={{A,C},{B,C},{B,E},{C,E}} {{A,C},{B,C},{B,E},{C,E}}={{A,B,C},{A,C,E},{B,C,E}}

2.剪枝：

{A,B,C}的2项子集{A,B},{A,C}和{B,C}，其中{A,B}不是 2项子集L2,因此不是频繁的，从C3中删除；

{A,C,E}的2项子集{A,C},{A,E}和{C,E}，其中{A,E}不是2项子集L2，因此不是频繁的，从C3中删除；

{B,C,E}的2项子集{B,C},{B,E}和{C,E}，它的所有2项子集都是L2的元素，保留C3中.

经过Apriori算法对L2连接和剪枝后产生候选3项集的集合为C3={B,C,E}. 在对该候选商品计数，由于等于最小支持度计数2，故得频繁3-项集合L3，同时由于4-项集中仅1个，故为空集，算法终止。

四.举例：频繁项集产生强关联规则

强关联规则是指：如果规则R：X=>Y满足support(X=>Y)>=supmin(最小支持度，它 用于衡量规则需要满足的最低重要性)且confidence(X=>Y)>=confmin（最小置信度，它表示关联规则需要满足的最低可靠 性）称关联规则X=>Y为强关联规则，否则称关联规则X=>Y为弱关联规则。

例：下图是某日超市的购物记录（注意Items已经排好序），使用上面叙述的Apriori算法实现了挖掘频繁项集，其中频繁项集I={i1,i2,i5}为频繁3-项集合L3，求由I产生哪些强关联规则？（最小支持度阈值为20%，最小置信度阈值为80%）

I的非空子集有{i1,i2}、{i1,i5}、{i2,i5}、{i1}、{i2}和{i5}。

结果关联规则如下，每个都列出置信度

1).i1 ∧i2=>i5 ,共10个事务；5个事务包含i1,i2；2个事务包含i1,i2和i5 confidence=2/5=40%，support=2/10=20%

2).i1 ∧i5=>i2 ,共10个事务；2个事务包含i1,i5；2个事务包括i1,i2和i5 confidence=2/2=100%，support=2/10=20%

3).i2 ∧i5=>i1 ,共10个事务；2个事务包含i2,i5；2个事务包含i1,i2和i5 confidence=2/2=100%，support=2/10=20%

4).i1=>i2 ∧i5 ,共10个事务；7个事务包含i1；2个事务包含i1,i2和i5 confidence=2/7=28%，support=2/10=20%

5).i2=>i1 ∧i5 ,共10个事务；8个事务包含i2；2个事务包含i1,i2和i5 confidence=2/8=25%，support=2/10=20%

6).i5=>i1 ∧i2 ,共10个事务；2个事务包含i5；2个事务包含i1,i2和i5 confidence=2/2=100%，support=2/10=20%

因最小置信度阈值为80%,最小支持度阈值为20%,则236规则符合要求,是频繁项集I={i1,i2,i5}产生的强关联规则且可以输出。

(自己的推测：如果给定的是最小支持度计数为2，则有10个事务，最小支持度阈值supmin=2/10=20%)

在实际应用中订单每天增加，我们采用增量的方式计算，去掉支持度的限制

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-62906-3.html