Apriori 算法

Apriori 算法是一種發現頻繁項集的基本算法。

一、基本概念

1、項與項集（item and itemsets）

設itemset={item_1, item_2, …, item_m}是所有項的集合，其中，item_n(n=1,2,…,m)成為項。項的集合稱為項集（itemset），包含k個項的項集稱為k項集(k-itemset)。

2、事物與事物集

一個事務T是一個項集，它是itemset的一個子集，每個事務均與一個唯一辨別符Tid相聯系。不同的事務一起組成了事務集D，它構成了關聯規則發現的事務資料庫。

3、關聯規則(association rule)

關聯規則是形如A=>B的蘊涵式，其中A、B均為itemset的子集且均不為空集，而A交B為空。

4、支援度(support)

關聯規則的支援度定義如下：

**

support(A => B) = P(A | B)
           

$P(A\bigcup B)$

表示事務包含集合A和B的并（即包含A和B中的每個項）的機率。注意與

$P(A or B)$

差別，後者表示事務包含A或B的機率。

5、置信度(confidence)

關聯規則的置信度定義如下：

confidence(A => B) = P(B | A) 
P(B | A) = support_count(A | B)/supportcount(A)
           

6、項集的頻度(support count)

包含項集的事務數，簡稱為項集的頻度、支援度計數或計數。

7、頻繁項集(frequent itemset)

如果項集I的相對支援度滿足事先定義好的最小支援度門檻值(min_sup)（即I的出現頻度大于相應的最小出現頻度（支援度計數）門檻值），則I是頻繁項集。

8、強關聯規則

滿足最小支援度和最小置信度的關聯規則，即待挖掘的關聯規則。

二、一個例子

下面通過一個例子解釋上面的概念

現在有一個超市的銷售記錄資料集：

TID	商品清單
T100	牛奶, 面包, 尿布
T200	面包, 啤酒
T300	面包, 黃油
T400	牛奶, 面包, 啤酒
T500	牛奶, 黃油
T600	面包, 黃油
T700	牛奶, 黃油
T800	牛奶, 面包, 黃油, 尿布
T900	牛奶, 面包, 黃油

該表就是一個 事務集，每一條銷售記錄就是一個 事務，用TID唯一标志。牛奶、面包這些商品就是一個 項（item）,{牛奶,面包,尿布,啤酒,黃油}表示所有項的 項集（itemset）。每一個事務都是項集的子集，例如T100表示的就是含有三個項的項集，稱之為 3項集（3-itemset）。一個2項集{牛奶，面包}在事務集中出現了4次，該項集的 項集頻度(support count) 就是4。我們可以設定一個最小頻度的門檻值min_sup,保留項集頻度大于min_sup的項集，過濾出來的項集就是 頻繁項集（frequent itemset）。一般來說買完面包一般都會買牛奶，這個購買模式就可以用 關聯規則（association rule） 來表示:

牛奶

$\Rightarrow$

面包[suppor = 44%;confidence = 67%]

該關聯規則的支援度代表同時在一個事務中出現的頻次占事務總數的44%，置信度表示購買面包的顧客有60%也購買了牛奶。若該關聯規則的支援度和置信度滿足最小支援度和最小置信度門檻值，那麼該關聯規則就是我們要找的 強關聯規則（big rule） 。

三、Python實作Apriori算法

1、算法步驟

Apriori算法主要用來找出事務集中的頻繁項集。

（1）由于剛開始還沒有産生頻繁項集，我們首先掃描事務集D生成候選1項集C1。生成C1的過程中同時對每一個1項集出現的頻次計數，得到項集的頻度。

for i in data_set:
        for j in i:
            j = frozenset({j})
            if j not in candidate_itemset:
                candidate_itemset[j] = 1
            else:
                candidate_itemset[j] += 1
           

這裡候選項集及其項集頻度用python中的字典存儲，項集的資料類型是集合（set），項資料類型是字元串（str）。由于字典的key隻能是不可更改的資料類型，是以項集存入字典時需要變成frozenset類型。

（2）有了C1就可以通過疊代得到Lk了。

for i in frozenset(Ck.keys()):
        if Ck[i] < min_sup:
            Ck.pop(i)
    Lk = list(Ck.keys())
    frequent_itemset.update(Ck)
    
    Ck.clear()
    len_Lk = len(Lk)
    for i in range(len_Lk):
        for j in range(1,len_Lk):
            L1 = list(Lk[i])
            L2 = list(Lk[j])
            L1.sort()
            L2.sort()
            if (L1[:-2] == L2[:-2]) & (L1 != L2):
                Cki = set(L1) | set(L2)
                
                if not is_pruning(Cki, Lk):
                    CKi = frozenset(Cki)
                    Ck[CKi] = 0

    for i in Ck:
        item = list(i)
        for j in data_set:
            if set(item) & set(j) == set(item):
                Ck[i] += 1
           

疊代部分的輸入為C(k-2),輸出為C(k),當C(k)為空集合時疊代結束，表示已經找到了所有的頻繁項集。疊代過程可由下圖表示

graph LR
删除-->Lk-1
Lk-1-->連結
連結-->枝剪
枝剪-->Ck
Ck-->計數
計數-->删除
           

首先删除不滿足最小支援度門檻值的候選項集，留下的就是頻繁項集；将得到的頻繁(k-1)項集添加到L(k-1)和頻繁項集的合集frequent_itemset中；然後對L(k-1)做連結操作，對k-1項集兩兩取出，逐對排序、判斷是否能連結。連結的條件為：排序後的兩個頻繁項集的前k-2項要相同；若能連結，就生成k項集，然後做枝剪操作，看此k項集的(k-1)項子集是不是頻繁項（在L(k-1)中）；若沒有被枝剪，就添加到候選k項集的集合Ck中；最後對Ck中的後選項集計數，将Ck再次傳入疊代函數。

（3）疊代結束後，所有符合條件的頻繁項集就都存入了字典frequent_itemset中。最後通過頻繁項集得到強關聯規則。

for i in range(len(frequent_itemset)):
        itemset_1 = set(list(frequent_itemset.keys())[i])
        for j in range(1, len(frequent_itemset)):
            itemset_2 = set(list(frequent_itemset.keys())[j])
            if (not itemset_1 & itemset_2) and (frozenset(itemset_1|itemset_2) in frequent_itemset):
                confidence = frequent_itemset[frozenset(itemset_1|itemset_2)]/frequent_itemset[frozenset(itemset_1)]
                if (confidence > min_conf) and ([itemset_1, itemset_2] not in big_rules_list):
                    big_rules_list.append([itemset_1, itemset_2])
                    confidence_list.append(confidence)
           

依然是從頻繁項集的集合中依次取出兩個頻繁項集來判斷。若取出的兩個頻繁項集是A和B，能産生相關聯規則A=>B的條件是：

（1）A與B不能有交集，即A & B為空。

（2）A與B的并集也是頻繁項集，即A | B在頻繁項集的集合中。

（3）A與B的置信度大于等于最小置信度門檻值。求解A與B的置信度，簡單來說就是用A與B的并集的頻繁項集頻度除以A的頻繁項集頻度。

2、程式運作結果

程式源碼：https://github.com/huwenhao1127/DataMining/tree/master/Frequent Itemsets Mining