Apriori算法学习笔记(二)

Apriori算法学习笔记(二)

此笔记主要参考数据挖掘导论一书

1. 基于置信度的剪枝

将频繁项集Y划分成两个非空子集X和Y-X，使得X->Y-X满足置信度阈值。此时项集X和项集Y-X已经满足支持度阈值，因为它们是Y的子集且Y为频繁项集。
与频繁项集的产生相似，规则的产生也有两个重要的定理：
1. 如果规则X->Y-X不满足置信度阈值，若X’是X的子集，则X’->Y-X’的规则也不满足置信度阈值。
2. 如果规则X->Y-X满足置信度阈值，若X’是X的超集且X’是Y的子集，则X’->Y-X’的规则也满足置信度阈值。

2. Apriori算法中规则的产生

在关联规则X->Y中，X称为规则的前件，Y称为规则的后件。Apriori算法使用一种逐层(从小到大)的方法来产生关联规则，其中每层对应于规则后件中的中的项数。得到频繁项目集之后，则需要从频繁项目集中找出符合条件的关联规则。最简单的办法是：遍历所有的频繁项目集，然后从每个项目集中依次取1、2、…k个元素作为后件，该项目集中的其他元素作为前件，计算该规则的置信度进行筛选即可，利用上文提到的两个重要定理，可知若规则前件X不满足置信度阈值，则X的子集也全都不满足，这样减少了很多计算量。

3. Apriori算法的规则产生的伪代码

Apriori算法中规则的产生：

for 每一个频繁k-项集fk, k>=2 do
    H1={i|i属于fk}    {规则的1-项后件}
    ap-genrules(fk,H1)
end for
···

过程ap-genrules(fk,Hm)：
···
k=|fk|            {频繁项集的大小}
m=|Hm|            {规则后件的大小}
if k>m+1 then
    Hm+1=apriori-gen(Hm)
    for 每个hm+1属于Hm+1 do
        conf=fk的支持度计数/(fk-hm+1)的支持度计数
        if conf>=minconf then
            output:规则(fk-hm+1)->hm+1
        else
            从Hm+1 delete hm+1
        end if
    end for
    call ap-genrules(fk, Hm+1)
end if