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>= do
    H1={i|i屬于fk}    {規則的-項後件}
    ap-genrules(fk,H1)
end for
···

過程ap-genrules(fk,Hm)：
···
k=|fk|            {頻繁項集的大小}
m=|Hm|            {規則後件的大小}
if k>m+ then
    Hm+=apriori-gen(Hm)
    for 每個hm+屬于Hm+ do
        conf=fk的支援度計數/(fk-hm+)的支援度計數
        if conf>=minconf then
            output:規則(fk-hm+)->hm+
        else
            從Hm+ delete hm+
        end if
    end for
    call ap-genrules(fk, Hm+)
end if