深度剖析Apriori算法

Apriori算法是第一個關聯規則挖掘算法，也是最經典的算法。它利用逐層搜尋的疊代方法找出資料庫中項集的關系，以形成規則，其過程由連接配接（類矩陣運算）與剪枝（去掉那些沒必要的中間結果）組成。

Apriori算法是關聯規則中常用的一種算法。該算法主要包含兩個步驟：首先找出資料集中所有的頻繁項集，這些項集出現的頻繁性要大于或等于最小支援度，然後根據頻繁項集産生強關聯規則，這些規則必須滿足最小支援度和最小置信度。

上面提到了最小支援度和最小置信度，事實上，在關聯規則中用于度量規則品質的兩個主要名額即為支援度和置信度。那麼，什麼是支援度和置信度呢？接下來進行講解。

給定關聯規則X=>Y，即根據X推出Y。形式化定義為：

算法步驟：

找出出現頻率最大的一個項L1。
根據L1找頻繁“2項集”的集合C2.
并剪掉不滿足支援度門檻值的項，得到L2。
根據L2找頻繁“3項集”的集合C3。
根據性質和支援度門檻值進行剪枝，得到L3。
循環上述過程，直到得到空集C，即直到不能發現更大的頻集L。
計算最大頻集L的非空子集，兩兩計算置信度，得到大于置信度門檻值的強關聯規則。

Apriori性質：一個頻繁項集的任一子集也應該是頻繁項集。也就是，生成一個k-itemset的候選項時，如果這個候選項有子集不在(k-1)-itemset(已經确定是frequent的)中時，那麼這個候選項就不用拿去和支援度判斷了，直接删除。

舉個栗子：

1. 首先看一下我們的資料，假設給定如下電子商務網站的使用者交易資料集。

![](http://cookdata.cn/media/bbs/images/2020_09_11_16_52_IMG_6697_[原始大小]_1599825711294_5d14.jpg =700x*)

代碼如下（這裡我用函數進行封裝，便于之後的操作）

# 傳回為dict類型，代表不同使用者購買了哪些商品，key為str類型，代表不同使用者，value為frozenset類型，其中的元素代表不同的商品。
def load_example():
    data = {
        'user1': ['I1', 'I2', 'I5'],
        'user2': ['I2', 'I4'],
        'user3': ['I2', 'I3'],
        'user4': ['I1', 'I2', 'I4'],
        'user5': ['I1', 'I3'],
        'user6': ['I2', 'I3'],
        'user7': ['I1', 'I3'],
        'user8': ['I1', 'I2', 'I3', 'I5'],
        'user9': ['I1', 'I2', 'I3']
    }
    return {i: frozenset(data[i]) for i in data}

2. 計算頻繁1項集。掃描交易資料集，統計每種商品出現的次數，選取大于或等于最小支援度的商品，得到了候選項集。

代碼如下

# 函數傳回為dict類型，key為frozenset類型，表示每個商品名稱，value為int類型，表示該商品出現的次數。
# data: 商品清單，類型為dict，key為str類型，代表使用者名稱，value為frozenset類型，代表該使用者所購買的商品名稱。
def freq_one(data):
    freq_1 = {}
    for item in data:
        for record in data[item]:
            if frozenset([record]) in freq_1:
                freq_1[frozenset([record])] += 1
            else:
                freq_1[frozenset([record])] = 1
    return {v: freq_1[v] for v in freq_1 if freq_1[v] >= 2}

3. 計算頻繁k項集（k>=2）。根據頻繁1項集，計算頻繁2項集。首先将頻繁1項集和頻繁1項集進行連接配接運算，得到2項集。

![](http://cookdata.cn/media/bbs/images/2020_09_11_16_52_IMG_6699_[原始大小]_1599825756996_5d14.jpg =350x*)

掃描使用者交易資料集，計算包含每個候選2項集的記錄數。

![](http://cookdata.cn/media/bbs/images/2020_09_11_16_52_IMG_6700_[原始大小]_1599825802444_5d14.jpg =600x*)

這裡呢我定義最小支援度為2/9，即支援度計數為2，根據最小支援度，得到頻繁2項集，如圖所示。

![](http://cookdata.cn/media/bbs/images/2020_09_11_16_52_IMG_6701_[原始大小]_1599825818128_5d14.jpg =600x*)

根據頻繁2項集，再計算頻繁3項集。首先将頻繁2項集進行連接配接，得到{{I1，I2，I3}，{I1，I2，I5}，{I1，I3，I5}，{I2，I3，I4}，{I2，I3，I5}，{I2，I4，I5}}，然後根據頻繁項集性質進行剪枝（第一種剪枝），即頻繁項集的非空子集必須是頻繁的。

{I1，I2，I3}的2項子集為{I1，I2}，{I1，I3}，{I2，I3}，都在頻繁2項集中則保留；

{I1，I2，I5}的2項子集為{I1，I2}，{I1，I5}，{I2，I5}，都在頻繁2項集中則保留；

{I1，I3，I5}的2項子集為{I1，I3}，{I1，I5}，{I3，I5}，由于{I3，I5}不是頻繁2項集，移除該候選集；

{I2，I3，I4}的2項子集為{I2，I3}，{I2，I4}，{I3，I4}，由于{I3，I4}不是頻繁2項集，移除該候選集；

{I2，I3，I5}的2項子集為{I2，I3}，{I2，I5}，{I3，I5}，由于{I3，I5}不是頻繁2項集，移除該候選集；

{I2，I4，I5}的2項子集為{I2，I4}，{I2，I5}，{I4，I5}，由于{I4，I5}不是頻繁2項集，移除該候選集。

通過剪枝，得到候選集{{I1，I2，I3}，{I1，I2，I5}}，掃描交易資料庫，計算包含候選3項集的記錄數（第二種門檻值剪枝）

根據頻繁3項集，計算頻繁4項集。重複上述的思路，得到{I1，I2，I3，I5}，根據頻繁項集定理，它的子集{I2，I3，I5}為非頻繁項集，是以移除該候選集。進而，頻繁4項集為空，至此，計算頻繁項集的步驟結束。

代碼如下(這裡我先定義兩個函數，這兩個函數将會在計算頻繁k項集中用到。第一個函數是用來得到所有k項子集，第二個是用來得到所有非空子集并剔除自身)

# 函數傳回為list類型，每一個元素都是k項子集。
# item是一個可疊代對象。
# k是想要得到的第幾項集（k要小于等于item的長度），類型為int。
def get_subset(item, k):
    import itertools as its
    return [frozenset(item) for item in its.combinations(item, k)]

# 函數傳回為list類型，每一個元素也為一個list。
# item是一個可疊代對象。
def get_all_subsets_not_self(item):
    subsets = []
    for i in range(1, len(item)):
        subsets.append(get_subset(item, i))
    return subsets

然後定義計算頻繁k項集的函數，如果我們想要得到頻繁2項集，則函數第二個參數

frequent_k_minus_one

要傳入頻繁1項集，參數k要傳入2；同理如果我們想要得到頻繁3項集，則函數第二個參數

frequent_k_minus_one

要傳入頻繁2項集，參數k要傳入3。

# 函數傳回為dict類型，key為frozenset類型，表示每幾個的商品名稱，value為int類型，表示這幾個商品出現的次數。
# data是商品清單，類型為dict，key為str類型，代表使用者名稱，value為frozenset類型，代表該使用者所購買的商品名稱。
# frequent_k_minus_one是頻繁k-1項集，類型為dict。
# k是生成的第k項集（k>=2），類型為int。
# min_support是最小支援度，預設為2，類型為int。
def freq_k(data, frequent_k_minus_one, k, min_support=2):
    # 連接配接步，生成k項候選集
    items = frequent_k_minus_one.keys()
    candidate_items = [m.union(n) for m in items for n in items if m != n and len(m.union(n)) == k]
    # 剪枝步，剔除不能成為頻繁k項集的候選集
    final_candidate = set()
    for candidate in candidate_items:
        if set(items) > set(get_subset(candidate, (k - 1))):
            final_candidate.add(candidate)
    # 周遊資料集data，對final_candidate中的元素進行統計
    current_k = dict()
    for record in data.items():
        for item in final_candidate:
            if item.issubset(record[1]):
                if item in current_k:
                    current_k[item] += 1
                else:
                    current_k[item] = 1
    # 傳回支援度大于最小門檻值的頻繁項
    return {v: current_k[v] for v in current_k if current_k[v] >= min_support}

同時，我還定義了兩個函數，第一個可以直接生成最終頻繁項集，第二個可以生成所有頻繁項集，代碼如下所示。

# 函數傳回為tuple類型，其中，第一個元素為int類型，代表最終生成的頻繁第幾項集，第二個元素為set類型，代表最終生成的頻繁項集元素。
# data是商品清單，類型為dict，key為str類型，代表使用者名稱，value為frozenset類型，代表該使用者所購買的商品名稱。
# freq_one是頻繁1項集，類型為dict。
# min_support是最小支援度，預設為2，類型為int。
def frequent_final(data, freq_one, min_support=2):
    frequent_k = freq_one
    k = 2
    while True:
        frequent_k = freq_k(data=data, frequent_k_minus_notallow=frequent_k, k=k, min_support=min_support)
        k += 1
        if not (freq_k(data=data, frequent_k_minus_notallow=frequent_k, k=k, min_support=min_support)):
            break
    return (k - 1, frequent_k)

# 函數傳回為list類型，每一個元素為dict類型。
# data是商品清單，類型為dict，key為str類型，代表使用者名稱，value為frozenset類型，代表該使用者所購買的商品名稱。
# freq_one是頻繁1項集，類型為dict。
# min_support是最小支援度，預設為2，類型為int。
def frequent_all(data, freq_one, min_support=2):
    frequent_k = freq_one
    frequent_list = [frequent_k]
    k = 2

    while True:
        frequent_k = freq_k(data=data, frequent_k_minus_notallow=frequent_k, k=k, min_support=min_support)
        frequent_list.append(frequent_k)
        k += 1
        if not (freq_k(data=data, frequent_k_minus_notallow=frequent_k, k=k, min_support=min_support)):
            break
    return frequent_list

4. 我設定最小置信度為60%，即0.6，根據頻繁項集，計算關聯規則。這裡以頻繁3項集{I1，I2，I5}為例，計算關聯規則。{I1，I2，I5}的非空子集為{I1，I2}、{I1，I5}、{I2，I5}、{I1}、{I2}和{I5}。規則1，{I1，I2}=>{I5}，置信度為{I1，I2，I5}的支援度除以{I1，I2}的支援度，即2/4=50%，因其小于最小置信度，是以删除該規則。同理，最後可以得到{I1，I5}=>{I2}，{I2，I5}=>{I1}和{I5}=>{I1，I2}為3條強關聯規則。

代碼如下

# 函數傳回為list類型，每一個元素為一個tuple，tuple中第一個元素為str類型，代表由A->B的強關聯商品，第二個元素為float類型，代表由商品A->B的置信度。
# data是商品清單，類型為dict，key為str類型，代表使用者名稱，value為frozenset類型，代表該使用者所購買的商品名稱。
# freq_one是頻繁1項集，類型為dict。
# min_support是最小支援度，預設為2，類型為int。
# min_conf是最小置信度，預設為0.6，類型為float。
def rule(data, freq_one, min_support=2, min_cnotallow=0.6): 
    strong_rule = []
    final_itemsets = frequent_all(data=data, freq_notallow=freq_one, min_support=min_support)
    for item_set in final_itemsets[1:]:
        for AB in item_set:
            for A in [j for i in get_all_subsets_not_self(AB) for j in i]:
                B = frozenset([i for i in AB if i not in A])
                if len(B) > 0:
                    x = float(final_itemsets[len(AB) - 1][AB])
                    y = float(final_itemsets[len(A) - 1][A])
                    confidence = x / y
                    if confidence >= min_confidence:
                        strong_rules.append((str(A) + ' -> ' + str(B), confidence))
    return strong_rules

至此我們就得到了商品之間的關聯關系。最後我就可以使用以上定義好的函數直接調用得到關聯規則，代碼隻需一行，如下所示：

print(rule(data=load_example(), freq_notallow=freq_one(data=load_example()),min_support=2, min_cnotallow=0.6))

運作結果如下：

深度剖析Apriori算法

算法步驟：

舉個栗子：

1. 首先看一下我們的資料，假設給定如下電子商務網站的使用者交易資料集。

2. 計算頻繁1項集。掃描交易資料集，統計每種商品出現的次數，選取大于或等于最小支援度的商品，得到了候選項集。

3. 計算頻繁k項集（k>=2）。根據頻繁1項集，計算頻繁2項集。首先将頻繁1項集和頻繁1項集進行連接配接運算，得到2項集。

繼續閱讀

Makefile中字元串處理函數

PHP取得剛插入資料的ID 并将這個ID插入到别的表

VC++判斷網絡連接配接狀态

删除數組中重複的元素plus【數組專題】

s-systemtap工具使用圖譜（持續更新）

資料挖掘之關聯規則(Apriori算法)

Vue學習之--------路由的query、params參數、路由命名（3）（2022/9/5）

2022高教社杯數學模組化思路 - 案例：Apriori-關聯規則挖掘算法

Iceberg 源碼閱讀(一) ContentFile統一檔案接口

機器學習推薦算法之關聯規則（Apriori）——支援度；置信度；提升度

Spark mllib FP Growth

Python 資料分析執行個體——關聯規則

拓端tecdat|關聯規則APRIORI挖掘豆瓣讀書評論爬蟲采集資料與可視化

002 Rust異步程式設計，async await簡單介紹

[Win32]一個調試器的實作（八）單步執行

關聯規則APRIORI挖掘豆瓣讀書評論爬蟲采集資料與可視化