01.22 關聯規則算法Apriori 學習筆記

A priori

集體智慧（Collective Intelligence）

單一個體所做出的決策往往會比起多數決的決策來的不精準，集體智慧是一種共享的或者群體的智能，以及集結眾人的意見進而轉化為決策的一種過程。它是從許多個體的合作與競爭中湧現出來的。通常含義為：為了創造新的想法而將一群人的行為、偏好或思想組合在一起，從獨立的數據提供者（用戶）中總結規律、經驗從而得到新的結論。隨著通信技術的發展，互聯網重構了知識體系，讓每一個用戶在享受知識的同時，也在默默貢獻著知識。信息的價值不由任何一個個體所決定，而是由群體的行為來確定的。

關聯規則（ Association rule ）

關聯規則分析也稱為購物籃分析，最早是為了發現超市銷售數據庫中不同的商品之間的關聯關係。關聯規則是反映一個事物與其他事物之間的關聯性，若多個事物之間存在著某種關聯關係，那麼其中的一個事物就能通過其他事物預測到。例如，從銷售數據中發現的規則 {洋蔥, 土豆}→{漢堡} 會表明如果顧客一起買洋蔥和土豆，他們也有可能買漢堡的肉。此類信息可以作為做出促銷定價或產品植入等營銷活動決定的根據。除了上面購物籃分析中的例子以外，關聯規則如今還被用在許多應用領域中，包括網絡用法挖掘、入侵檢測、連續生產及生物信息學中。與序列挖掘相比，關聯規則學習通常不考慮在事務中、或事務間的項目的順序。

頻繁項集 （ Frequent Itemset ）

經常一起出現的item集合稱為頻繁項集。常用的頻繁項集的評估標準有支持度、置信度和提升度：

支持度

支持度就是幾個關聯的數據在數據集中出現的次數佔總數據集的比重。或者說幾個數據關聯出現的概率。如果我們有兩個想分析關聯性的數據X和Y，則對應的支持度為：

以此類推，如果我們有三個想分析關聯性的數據X，Y和Z，則對應的支持度為：

一般來說，支持度高的數據不一定構成頻繁項集，但是支持度太低的數據肯定不構成頻繁項集。

置信度

置信度體現了一個數據出現後，另一個數據出現的概率，或者說數據的條件概率。如果我們有兩個想分析關聯性的數據X和Y，X對Y的置信度為：

也可以以此類推到多個數據的關聯置信度，比如對於三個數據X，Y，Z,則X對於Y和Z的置信度為：

提升度

提升度表示含有Y的條件下，同時含有X的概率，與X總體發生的概率之比，即：

提升度體先了X和Y之間的關聯關係, 提升度大於1則是有效的強關聯規則， 提升度小於等於1則是無效的強關聯規則 。一個特殊的情況，如果X和Y獨立，則有

，因為此時

。

支持度和可信度是用來量化關聯分析是否成功的方法。關聯分析的目的包括兩個：發現頻繁項集和發現關聯規則。首先我們要找到頻繁項集，然後根據頻繁項集找出關聯規則。一般來說，要選擇一個數據集合中的頻繁數據集，則需要自定義評估標準。最常用的評估標準是用自定義的支持度，或者是自定義支持度和置信度的一個組合。

Apriori 算法簡介

支持度和可信度是用來量化關聯分析是否成功的一個方法。假設想找到支持度大於 0.8 的所有項集，應該如何去做呢？ 一個辦法是生成一個物品所有可能組合的清單，然後對每一種組合統計它出現的頻繁程度。確實可以通過遍歷所有組合就能找出所有頻繁項集,但問題是遍歷所有組合花的時間太多，效率太低，假設有N個物品，那麼一共需要計算

次。每增加一個物品，數量級是成指數增長。而Apriori就是一種找出頻繁項集的高效算法。瞭解Apriori算法推導之前，我們先介紹一些基本概念：

• K項集（K-itemset）:同時購買的K項集合。
• 頻繁K項集（frequent itemset）：滿足最小支持度閾值的K項集合。
• 候選K項集（candidate itemset）：通過連接形成的K項集合。

Apriori的核心就是下面這句話： 某個項集是頻繁的，那麼它的所有子集也是頻繁的 。這句話看起來是沒什麼用，但是反過來就很有用了。如果一個項集是非頻繁項集，那麼它的所有超集也是非頻繁項集。

如圖所示，我們發現{A,B}這個項集是非頻繁的，那麼{A,B}這個項集的超集，{A,B,C},{A,B,D}等等也都是非頻繁的，這些就都可以忽略不去計算。運用Apriori算法的思想，我們就能去掉很多非頻繁的項集，大大簡化計算量。

Apriori算法是經典的挖掘頻繁項集和關聯規則的數據挖掘算法。A priori在拉丁語中指”來自以前”。當定義問題時，通常會使用先驗知識或者假設，這被稱作”一個先驗”（a priori）。Apriori算法的名字正是基於這樣的事實：算法使用頻繁項集性質的先驗性質，即頻繁項集的所有非空子集也一定是頻繁的。Apriori算法使用一種稱為逐層搜索的迭代方法，其中k項集用於探索(k+1)項集。首先，通過掃描數據庫，累計每個項的計數，並收集滿足最小支持度的項，找出頻繁1項集的集合。該集合記為L1。然後，使用L1找出頻繁2項集的集合L2，使用L2找出L3，如此下去，直到不能再找到頻繁k項集。每找出一個Lk需要一次數據庫的完整掃描。Apriori算法使用頻繁項集的先驗性質來壓縮搜索空間，其核心思想是通過連接產生候選項及其支持度，然後通過剪枝生成頻繁項集。。與樸素貝葉斯分類器一樣都是用到先驗知識，但是貝葉斯是多個概率推斷 True/False，關聯規則是解決A→Who 的問題。

Apriori 的優點：

• 適合稀疏數據集。
• 算法原理簡單，易實現。
• 適合事務數據庫的關聯規則挖掘。
• 易編碼實現

• 可能產生龐大的候選集。
• 算法需多次遍歷數據集，算法效率低，耗時。
• 在大數據集上可能較慢

Apriori算法能夠有效發現頻繁項集並獲取關聯規則，但是每次計算頻繁項集的支持度（主要是指：項集所構成的超集的支持度）都要遍歷整個數據庫，因此造成過多的時間開銷，無法高效處理大規模數據集。為了克服Apriori算法這一缺點，包括FP-Growth等算法應運而生，FP-Growth算法則需掃描原始數據兩遍，通過FP-tree數據結構對原始數據進行壓縮，效率較高。現在一般很少直接用Aprior算法來挖掘數據了，但是理解Aprior算法是理解其它Aprior類算法的前提，同時算法本身也不復雜，因此值得好好研究一番。

Apriori 代碼實現

<code># -*- coding: utf8 -*-

def load_data_set():
"""加載數據集"""
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
 


def create_C1(data_set):
"""創建集合 C1。即對 data_set 進行去重，排序，放入 list 中，然後轉換所有的元素為 frozenset"""
C1 = []
for transaction in data_set:
for item in transaction:
if not [item] in C1:
C1.append([item])
C1.sort()
return map(frozenset, C1)# frozenset 表示凍結的set集合，元素無改變；可以把它當字典的 key 來使用


def scan_D(D, Ck, min_support):
"""計算候選數據集 Ck 在數據集 D 中的支持度，並返回支持度大於最小支持度（min_support）的數據
Args:
D 數據集
Ck 候選項集列表
min_support 最小支持度
Returns:
ret_list 支持度大於 min_support 的集合
support_data 候選項集支持度數據
"""
ss_cnt = {}# ssCnt 臨時存放選數據集 Ck 的頻率. 例如: a->10, b->5, c->8
for tid in D:
for can in Ck:
if can.issubset(tid):
if can not in ss_cnt:
ss_cnt[can] = 1
else:
ss_cnt[can] += 1
num_items = float(len(D))# 數據集 D 的數量
ret_list = []
support_data = {}
for key in ss_cnt:
support = ss_cnt[key] / num_items# 支持度 = 候選項（key）出現的次數 / 所有數據集的數量 

if support >= min_support:
ret_list.insert(0, key)# 在 retList 的首位插入元素，只存儲支持度滿足頻繁項集的值
support_data[key] = support# 存儲所有的候選項（key）和對應的支持度（support）
return ret_list, support_data


def apriori_gen(Lk, k):
"""aprioriGen（輸入頻繁項集列表 Lk 與返回的元素個數 k，然後輸出候選項集 Ck。
 例如: 以 {0},{1},{2} 為輸入且 k = 2 則輸出 {0,1}, {0,2}, {1,2}. 以 {0,1},{0,2},{1,2} 為輸入且 k = 3 則輸出 {0,1,2}
Args:
Lk 頻繁項集列表
k 返回的項集元素個數（若元素的前 k-2 相同，就進行合併）
Returns:
ret_list 元素兩兩合併的數據集
"""
ret_list = []
len_Lk = len(Lk)
for i in range(len_Lk):
for j in range(i + 1, len_Lk):
L1 = list(Lk[i])[: k - 2]
L2 = list(Lk[j])[: k - 2]
L1.sort()
L2.sort()
if L1 == L2:# 第一次 L1,L2 為空，元素直接進行合併，返回元素兩兩合併的數據集
ret_list.append(Lk[i] | Lk[j])
return ret_list


#
def apriori(data_set, min_support=0.5):
"""找出數據集 data_set 中支持度 >= 最小支持度的候選項集以及它們的支持度。即我們的頻繁項集。 

Args:
data_set 原始數據集
min_support 支持度的閾值
Returns:
L 頻繁項集的全集
support_data 所有元素和支持度的全集
"""
C1 = create_C1(data_set)# C1 即對 data_set 進行去重，排序，放入 list 中，然後轉換所有的元素為 frozenset
D = list(map(set, data_set))# 對每一行進行 set 轉換，然後存放到集合中
L1, support_data = scan_D(D, C1, min_support)# 計算候選數據集 C1 在數據集 D 中的支持度，並返回支持度大於 min_support 的數據
L = [L1]# L 加了一層 list, L 一共 2 層 list
k = 2
while (len(L[k - 2]) > 0):# 判斷 L 的第 k-2 項的數據長度是否 > 0。
Ck = apriori_gen(L[k - 2], k)
Lk, supK = scan_D(D, Ck, min_support)# 計算候選數據集 CK 在數據集 D 中的支持度，並返回支持度大於 min_support 的數據
support_data.update(supK)# 保存所有候選項集的支持度，如果字典沒有，就追加元素，如果有，就更新元素
if len(Lk) == 0:
break
L.append(Lk)# Lk 表示滿足頻繁子項的集合，L 元素在增加，
k += 1
return L, support_data


def calc_conf(freq_set, H, support_data, brl, min_conf=0.7):
"""計算可信度（confidence）
Args:
freq_set 頻繁項集中的元素，例如: frozenset([1, 3])
H 頻繁項集中的元素的集合，例如: [frozenset([1]), frozenset([3])] 

support_data 所有元素的支持度的字典
brl 關聯規則列表的空數組
min_conf 最小可信度
Returns:
pruned_H 記錄 可信度大於閾值的集合
"""

pruned_H = []# 記錄可信度大於最小可信度（minConf）的集合
for conseq in H:
conf = support_data[freq_set] / support_data[freq_set - conseq]
if conf >= min_conf:
brl.append((freq_set - conseq, conseq, conf))
pruned_H.append(conseq)
return pruned_H


def rules_from_conseq(freq_set, H, support_data, brl, min_conf=0.7):
"""遞歸計算頻繁項集的規則
Args:
freq_set 頻繁項集中的元素，例如: frozenset([2, 3, 5])
H 頻繁項集中的元素的集合，例如: [frozenset([2]), frozenset([3]), frozenset([5])]
support_data 所有元素的支持度的字典
brl 關聯規則列表的數組
min_conf 最小可信度
"""
m = len(H[0])# H[0] 是 freq_set 的元素組合的第一個元素，並且 H 中所有元素的長度都一樣，長度由 apriori_gen(H, m+1) 這裡的 m + 1 來控制
if len(freq_set) > (m + 1):
Hmp1 = apriori_gen(H, m + 1)# 生成 m+1 個長度的所有可能的 H 中的組合
Hmp1 = calc_conf(freq_set, Hmp1, support_data, brl, min_conf)# 返回可信度大於最小可信度的集合
print('Hmp1=', Hmp1)
print('len(Hmp1)=', len(Hmp1), 'len(freqSet)=', len(freq_set))
if len(Hmp1) > 1:# 計算可信度後，還有數據大於最小可信度的話，那麼繼續遞歸調用，否則跳出遞歸 

rules_from_conseq(freq_set, Hmp1, support_data, brl, min_conf)


def generate_rules(L, support_data, min_conf=0.7):
"""生成關聯規則
Args:
L 頻繁項集列表
support_data 頻繁項集支持度的字典
min_conf 最小置信度
Returns:
big_rule_list 可信度規則列表（關於 (A->B+置信度) 3個字段的組合）
"""
big_rule_list = []
for i in range(1, len(L)):
for freq_set in L[i]:
H1 = [frozenset([item]) for item in freq_set]
if (i > 1):# 2 個的組合，走 else, 2 個以上的組合，走 if
rules_from_conseq(freq_set, H1, support_data, big_rule_list, min_conf)
else:
calc_conf(freq_set, H1, support_data, big_rule_list, min_conf)
return big_rule_list


def test_apriori():
data_set = load_data_set()

L1, support_data1 = apriori(data_set, min_support=0.7)
print('L(0.7): ', L1)
print('support_data(0.7): ', support_data1)

L2, support_data2 = apriori(data_set, min_support=0.5)
print('L(0.5): ', L2)
print('support_data(0.5): ', support_data2)


def test_gnerate_rules():
# 加載測試數據集
data_set = load_data_set()
L1, support_data1 = apriori(data_set, min_support=0.5)
print('L(0.7): ', L1)
print('support_data(0.7): ', support_data1)

# 生成關聯規則 

rules = generate_rules(L1, support_data1, min_conf=0.5)
print('rules: ', rules)


if __name__ == "__main__":
# 測試 Apriori 算法
test_apriori()

# 生成關聯規則
test_gnerate_rules()
/<code>

閱讀更多 sandag 的文章

關鍵字: 規則 洋蔥 數據庫