Apriori 演算法簡介及 python3實現

來自專欄數據科學與python小記12 人贊了文章

1 關聯規則簡介

1.1 從集體智慧談起

集體智慧（Collective Intelligence）通常含義為：為了創造新的想法而將一群人的行為、偏好或思想組合在一起，從獨立的數據提供者（用戶）中總結規律、經驗從而得到新的結論。隨著通信技術的發展，互聯網重構了知識體系，讓每一個用戶在享受知識的同時，也在默默貢獻著知識。信息的價值不由任何一個個體所決定，而是由群體的行為來確定的。「獨立性」是激發群體智慧的首要條件。

當前的Internet上有大量站點正在不斷從廣大用戶中搜集數據，越來越多的信息被製造出來，而數據科學家們則運用機器學習與統計學方法從中汲取集體智慧價值。儘管這些企業對於他們所使用的演算法、模型守口如瓶，但大量成功的案例顯示，其中的學習型演算法功不可沒。

1.2 什麼是關聯規則 ？

關聯規則分析也稱為購物籃分析，最早是為了發現超市銷售資料庫中不同的商品之間的關聯關係。關聯規則是反映一個事物與其他事物之間的關聯性，若多個事物之間存在著某種關聯關係，那麼其中的一個事物就能通過其他事物預測到。

舉個例子：菜品的合理搭配是有規律可循的。顧客的飲食習慣、菜品的葷素口味，有些菜品是相互關聯的，而有些菜品之間是對立或競爭關係(負關聯)，這些規律都隱藏在大量的歷史菜單數據中，如果能夠通過數據挖掘發現客戶點餐的規則，就可以快速識別客戶的口味，當他下了某個菜品的訂單時推薦相關聯的菜品，引導客戶消費，提高客戶的就餐體驗和餐飲企業的業績水平。

還有個很常見的例子：啤酒與尿布

Apriori 演算法是最經典也是最常用的挖掘頻繁項集的演算法，其核心思想是通過連接產生候選項及其支持度，然後通過剪枝生成頻繁項集。

1.3 與樸素貝葉斯分類器的區別

樸素貝葉斯分類器和關聯規則都是用到先驗知識，但是貝葉斯是多個概率推斷 True / False，關聯規則是解決 A → Who 的問題。

2 相關概念

定義 1 兩個不相交的非空集合 ，如果有 ，就說 是一條關聯規則。如吃鹹菜的人偏愛喝粥（ ）就是一條關聯規則。 關聯規則的強度(可信度)用支持度(support)和自信度(confidence)來描述。

定義 2 項集 種同時發生的概率稱為關聯規則 的支持度(support)：

最小支持度是用戶或專家定義的用來衡量支持度的一個閾值，表示關聯規則具有統計學意義的最低重要性。具有「統計學意義」的顯著特徵就是這個事件發生的概率/頻率不能太低（否則就不具有推廣到其他個體的價值）。

由於現實生活中，常用古典概型估計概率，因此，上式也可寫為：

定義 3 項集 發生的前提下，項集 發生的概率稱為關聯規則 的自信度(confidence 條件概率)：

最小置信度是用戶或專家定義的用來衡量置信度的一個閾值，表示關聯規則的最低可靠性。同理，在古典概型中，上式也可以寫為：

要做的工作：

1. 生成頻繁項集：

這一階段找出所有滿足最小支持度的項集（具有統計學意義的組合），找出的這些項集稱為頻繁項集。自信度與支持度的計算涉及到多個列表的循環，極大影響頻繁項集的生成時間。

2. 生成關聯規則：

在上一步產生的頻繁項集的基礎上生成滿足最小自信度的規則，產生的規則稱為強規則。

兩個重要的定理：

1. 如果一個集合是頻繁項集，則它的所有子集都是頻繁項集。假設一個集合{A,B}是頻繁項集，則它的子集{A}, {B} 都是頻繁項集。
2. 如果一個集合不是頻繁項集，則它的所有超集都不是頻繁項集。假設集合{A}不是頻繁項集，則它的任何超集如{A,B}，{A,B,C}必定也不是頻繁項集。

根據定理1和定理2易知：若 是強規則，則 都必須是頻繁項集。

3 Python3 實現

演算法原理很「繞」，本文使用面向對象結構來實現，結合代碼更容易理解演算法的原理。

編程實現過程需要考慮元素排列順序的問題：

在儲存的時候怎麼把 視為同一種候選集？本文使用如下轉換方式：

字元串.split(,) ：按 , 分割成列表，對列表元素可以使用 sorted 進行排序

,.join(列表或元組) ：使用 , 作為分隔符，將列表或元組轉為字元串

這樣就實現了歸併功能。

使用的編程語言：python3.6.4 (Anaconda3)

使用的編輯器：pycharm

使用的模塊：pandas、itertools（標準庫模塊）

3.1 導入模塊

import itertoolsimport pandas as pd

3.2 測試數據及標準化

測試數據：

data = [a,c,e, b,d, b,c, a,b,c,d, a,b, b,c, a,b, a,b,c,e, a,b,c, a,c,e]

標準化函數：

def str2itemsets(strings, split=,): 將字元串列錶轉化為對應的集合 itemsets = [] for string in strings: itemsets.append(sorted(string.split(split))) return itemsets

• str2itemsets(strings, split=,)
• 輸入：需要轉換的數據，數據分割方法
• 返回：標準化項集

測試數據進行標準化及結果

data = str2itemsets(data, split=,)

data = [[a, c, e], [b, d], [b, c], [a, b, c, d], [a, b], [b, c], [a, b], [a, b, c, e], [a, b, c], [a, c, e]]

3.3 定義類及初始化(class)

class Apriori(object): def __init__(self, itemSets, minSupport=0.5, minConf=0.7): self.itemSets = itemSets self.minSupport = minSupport self.minConf = minConf self.supportDates = dict() self.support_select = dict() self.confidence_select = dict() self.__Initialize()

• itemSets 是傳入的標準化數據
• minSupport=0.5, minConf=0.7 分別代表最小支持度和最小自信度
• supportDates 是一個空字典，用於儲存每一種可能情況的支持度(初始頻繁項集)
• support_select 是一個空字典，用於儲存在滿足最小支持度後的頻繁項集
• confidence_select 是一個空字典，用於儲存在滿足最小自信度後的關聯規則
• __Initialize() 是一個初始化函數(下文提到作用)

3.4 獲取項集所有元素

只有知道 itemSets 裡面到底有什麼元素(客戶點了什麼菜)，才能分析元素之間的組合情況(菜之間的關聯情況)。

def __item(self): 獲取項目元素列表 self.item = [] for itemSet in self.itemSets: for item in itemSet: if item not in self.item: self.item.append(item) self.item.sort()

第一個 for 循環是對標準化項集進行遍歷，取出裡面的每一項；第二個 for 循環是對項進行遍歷，取出裡面的每一個元素再做 if 判斷，構造一個不含有重複元素、按照名稱排序的 item 列表。

處理結果：item: [a, b, c, d, e]

• 這裡的函數名前加上"__"代表類的私有函數，只能在類的內部調用，僅為作者編程習慣(在後記中說明)

3.5 為每種組合情況進行計數(頻數)

def __count_dict(self): 為每個可能的候選集計數 for itemSet in self.itemSets: for i in range(1, len(itemSet) + 1): for factor in list(itertools.combinations(itemSet, i)): self.supportDates.setdefault(,.join(factor), 0) self.supportDates[,.join(factor)] += 1 / len(self.itemSets)

• 第一個 for 循環是對標準化項集進行遍歷，其中 itemSet 依次取 [[a, c, e], [b, d], [b, c], [a, b, c, d], [a, b], [b, c], [a, b], [a, b, c, e], [a, b, c], [a, c, e]]
• 第二個 for 循環是獲取該子集([a,c,e])的元素個數(如此例子中為3)，根據長度得到所有可能的組合的長度(可能包含1個元素,2個元素,3個元素)進行遍歷
• 第三個for 循環是在第二個 for 循環給定了長度下(長度1，長度2，長度3)，獲取所有可能的組合，並對這些組合都計數 +1 ：如在itemSet取[a, c, e]時，長度 2 可能的情況為[a,c],[a,e],[c,e]，此時 factor 依次取這三個值，接下來 supportDatates 將 a,c、a,e，c,e 的計數分別 +1

執行結果：

supportDates = {a: 0.7, c: 0.7, e: 0.30000000000000004, a,c: 0.5, a,e: 0.30000000000000004, c,e: 0.30000000000000004, a,c,e: 0.30000000000000004, b: 0.7999999999999999, d: 0.2, b,d: 0.2, b,c: 0.5, a,b: 0.5, a,d: 0.1, c,d: 0.1, a,b,c: 0.30000000000000004, a,b,d: 0.1, a,c,d: 0.1, b,c,d: 0.1, a,b,c,d: 0.1, b,e: 0.1, a,b,e: 0.1, b,c,e: 0.1, a,b,c,e: 0.1}

3.6 選擇所有符合最小支持度要求的組合作為頻繁項集

def __support_select_fun(self): 選擇所有符合最小支持度要求的元素作為頻繁項集 for k, v in self.supportDates.items(): if v >= self.minSupport: self.support_select[k] = v

執行結果：

support_select = {a: 0.7, c: 0.7, e: 0.30000000000000004, a,c: 0.5, a,e: 0.30000000000000004, c,e: 0.30000000000000004, a,c,e: 0.30000000000000004, b: 0.7999999999999999, d: 0.2, b,d: 0.2, b,c: 0.5, a,b: 0.5, a,b,c:0.30000000000000004}

3.7 選擇所有符合最小自信度要求的元素作為關聯規則

def __confidence_select_fun(self): 選擇所有符合最小自信度要求的元素作為關聯規則 for k, v in self.support_select.items(): for i in range(1, len(self.item) - len(k.split(,)) + 1): for factor in list(itertools.combinations(set(self.item) - set(k.split(,)), i)): if self.support_select.get(,.join(sorted(k.split(,) + list(factor)))): Supp = self.support_select[,.join(sorted(k.split(,) + list(factor)))] Conf = Supp / self.support_select[k] if Conf >= self.minConf: self.confidence_select[k + --> + ,.join(sorted(factor))] = {Support: Supp, Confidence: Conf}

• 第一個 for 循環對頻繁項集(滿足最小支持度)的組合情況進行遍歷。這裡使用到了定理 2 ，如果該組合不在頻繁項集種，那麼它的超集(關聯規則)，又怎麼會在頻繁項集中呢？又怎麼會滿足最小支持度呢？
• 第二個 for 循環，先計算頻繁項集給定的當前組合的關聯規則可能的長度，根據長度得到所有可能的組合的長度(可能包含1個元素,2個元素,3個元素,4個元素)進行遍歷，如頻繁項集遍歷到第一個元素 a，則剩餘長度為4，此時循環：1,2,3,4
• 第三個for 循環是在第二個 for 循環給定了長度下(長度1，長度2，長度3，長度4)，獲取所有可能的組合，並對這些組合都計數 +1 ：如在 itemSet 取第一項 a 時，可能的情況為[b],[c],[d],[e],[b,c],[b,d],[b,e],[c,d],[c,e],[d,e],[b,c,d],[b,c,e],[b,d,e],[c,d,e],[b,c,d,e]，此時 factor 依次取這15值
• 接下來做判斷，如果上面取到的 factor 與 k(頻繁項集)組成的關聯規則（新的組合方案）不在頻繁項集中則跳過，否則計算自信度，對滿足最小自信度要求的關聯規則儲存在字典 confidence_select。
• ,.join(sorted(k.split(,) + list(factor)))，先將 k 轉化成列表，列表的加法即為元素的合併，再進行排序，最後用 , 分割成字元串
• self.support_select.get(,.join(sorted(k.split(,) + list(factor)))) 實際上使用的是字典的get方法，如果字典中有此鍵則返回值，否則返回None（此時不會觸發 if 語句）
• 為保證輸出結構也具有順序，在最後一行中 self.confidence_select[k + --> + ,.join(sorted(factor))] 也進行了元素排序。

執行結果：（太丑了）

{a-->c: {Support: 0.5, Confidence: 0.7142857142857143}, a-->b: {Support: 0.5, Confidence: 0.7142857142857143}, c-->b: {Support: 0.5, Confidence: 0.7142857142857143}, c-->a: {Support: 0.5, Confidence: 0.7142857142857143}, e-->c: {Support: 0.30000000000000004, Confidence: 1.0}, e-->a: {Support: 0.30000000000000004, Confidence: 1.0}, e-->c,a: {Support: 0.30000000000000004, Confidence: 1.0}, a,c-->b: {Support: 0.30000000000000004, Confidence: 0.6000000000000001}, a,c-->e: {Support: 0.30000000000000004, Confidence: 0.6000000000000001}, a,e-->c: {Support: 0.30000000000000004, Confidence: 1.0}, c,e-->a: {Support: 0.30000000000000004, Confidence: 1.0}, b-->c: {Support: 0.5, Confidence: 0.625}, b-->a: {Support: 0.5, Confidence: 0.625}, d-->b: {Support: 0.2, Confidence: 1.0}, b,c-->a: {Support: 0.30000000000000004, Confidence: 0.6000000000000001}, a,b-->c: {Support: 0.30000000000000004, Confidence: 0.6000000000000001}}

3.8 讓顯示效果更漂亮

def __visualization(self): print(pd.DataFrame(self.confidence_select, index=[Support, Confidence]).T.sort_values( by=[Support, Confidence], ascending=False))

• 使用 pandas.DataFrame 數據格式能很好地輸出結果(這裡使用了print，如果希望獲取到元素，可以使用 return 或 魔術方法)
• sort_values(by=[Support, Confidence], ascending=False))
• by=[Support, Confidence] 表示按照支持度、自信度的優先順序進行排序
• ascending = False 表示從大到小

執行結果：

3.9 封裝初始化函數

def __Initialize(self): 初始化函數，執行一次 self.__item() self.__count_dict() self.__support_select_fun() self.__confidence_select_fun() self.__visualization()

初始化函數在對象實例化時執行一次，並關閉對外介面。

3.10 對外介面——更新函數

def update(self, minSupport, minConf): 用於更新數據 self.minSupport = minSupport self.minConf = minConf self.support_select = dict() self.confidence_select = dict() self.__support_select_fun() self.__confidence_select_fun() self.__visualization()

設置新的最小支持度、最小自信度後，重新執行支持度選擇、自信度選擇、可視化函數，不必再次執行初始化參數。

3.11 完整apriori演算法代碼

# !/usr/bin/env python# -*- coding:utf-8 -*-# version: Python 3.6.4 on win64# author: Suranyi time: 7/17# title: Apriori演算法import itertoolsimport pandas as pdclass Apriori(object): def __init__(self, itemSets, minSupport=0.5, minConf=0.7): self.itemSets = itemSets self.minSupport = minSupport self.minConf = minConf self.supportDates = dict() self.support_select = dict() self.confidence_select = dict() self.__Initialize() def __item(self): 獲取項目元素列表 self.item = [] for itemSet in self.itemSets: for item in itemSet: if item not in self.item: self.item.append(item) self.item.sort() def __count_dict(self): 為每個可能的候選集計數 for itemSet in self.itemSets: for i in range(1, len(itemSet)+1): for factor in list(itertools.combinations(itemSet, i)): self.supportDates.setdefault(,.join(factor), 0) self.supportDates[,.join(factor)] += 1 / len(self.itemSets) def __support_select_fun(self): 選擇所有符合最小支持度要求的元素作為頻繁項集 for k, v in self.supportDates.items(): if v >= self.minSupport: self.support_select[k] = v def __confidence_select_fun(self): 選擇所有符合最小自信度要求的元素作為關聯規則 for k, v in self.support_select.items(): for i in range(1, len(self.item) - len(k.split(,)) + 1): for factor in list(itertools.combinations(set(self.item) - set(k.split(,)), i)): if self.support_select.get(,.join(sorted(k.split(,) + list(factor)))): Supp = self.support_select[,.join(sorted(k.split(,) + list(factor)))] Conf = Supp / self.support_select[k] if Conf >= self.minConf: self.confidence_select[k + --> + ,.join(factor)] = {Support: Supp, Confidence: Conf} def __visualization(self): 可視化輸出 print(pd.DataFrame(self.confidence_select, index=[Support, Confidence]).T.sort_values( by=[Support, Confidence], ascending=False)) def __Initialize(self): 初始化函數，執行一次 self.__item() self.__count_dict() self.__support_select_fun() self.__confidence_select_fun() self.__visualization() def update(self, minSupport, minConf): 用於更新數據 self.minSupport = minSupport self.minConf = minConf self.support_select = dict() self.confidence_select = dict() self.__support_select_fun() self.__confidence_select_fun() self.__visualization()def str2itemsets(strings, split=,): 將字元串列錶轉化為對應的集合 itemsets = [] for string in strings: itemsets.append(sorted(string.split(split))) return itemsetsif __name__ == __main__: data = [紫菜蛋花湯,糖醋排骨,爆炒花甲, 紅燒裡脊,酸辣魚, 紅燒裡脊,糖醋排骨, 紫菜蛋花湯,紅燒裡脊,糖醋排骨,酸辣魚, 紫菜蛋花湯,紅燒裡脊, 紅燒裡脊,糖醋排骨, 紫菜蛋花湯,紅燒裡脊, 紫菜蛋花湯,紅燒裡脊,糖醋排骨,爆炒花甲, 紫菜蛋花湯,紅燒裡脊,糖醋排骨, 紫菜蛋花湯,糖醋排骨,爆炒花甲] itemSets = str2itemsets(data) # 轉化為標準格式 a = Apriori(itemSets, 0.2, 0.6) a.update(0.4, 0.7) # 更新修改這裡

4 後記

參考資料 使用Apriori演算法和FP-growth演算法進行關聯分析 - qwertWZ - 博客園

編程風格說明：最近開始學面向對象編程，筆者編程時習慣先構思好需要的函數，分為：初始化函數、工程函數，更新函數，方法函數。只有更新函數和方法函數提供對外介面。在編寫的時候先寫好名字、注釋佔位

每完成一個功能，先執行一次，沒有問題的話在初始化函數前面加上"__"私有化。

作者：張柳彬 仇禮鴻

如有疑問，請聯繫QQ：965579168

轉載請聲明出處

推薦閱讀：