Apriori算法介紹（Python實現(xiàn)）
隨著大數(shù)據(jù)概念的火熱，啤酒與尿布的故事廣為人知。我們?nèi)绾伟l(fā)現(xiàn)買啤酒的人往往也會買尿布這一規(guī)律?數(shù)據(jù)挖掘中的用于挖掘頻繁項集和關(guān)聯(lián)規(guī)則的Apriori算法可以告訴我們。本文首先對Apriori算法進行簡介，而后進一步介紹相關(guān)的基本概念，之后詳細的介紹Apriori算法的具體策略和步驟，***給出Python實現(xiàn)代碼。
1.Apriori算法簡介
Apriori算法是經(jīng)典的挖掘頻繁項集和關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法。A priori在拉丁語中指”來自以前”。當定義問題時，通常會使用先驗知識或者假設(shè)，這被稱作”一個先驗”(a priori)。Apriori算法的名字正是基于這樣的事實：算法使用頻繁項集性質(zhì)的先驗性質(zhì)，即頻繁項集的所有非空子集也一定是頻繁的。Apriori算法使用一種稱為逐層搜索的迭代方法，其中k項集用于探索(k+1)項集。首先，通過掃描數(shù)據(jù)庫，累計每個項的計數(shù)，并收集滿足最小支持度的項，找出頻繁1項集的集合。該集合記為L1。然后，使用L1找出頻繁2項集的集合L2，使用L2找出L3，如此下去，直到不能再找到頻繁k項集。每找出一個Lk需要一次數(shù)據(jù)庫的完整掃描。Apriori算法使用頻繁項集的先驗性質(zhì)來壓縮搜索空間。
2. 基本概念
項與項集：設(shè)itemset={item1, item_2, …, item_m}是所有項的集合，其中，item_k(k=1,2,…,m)成為項。項的集合稱為項集(itemset)，包含k個項的項集稱為k項集(k-itemset)。
事務(wù)與事務(wù)集：一個事務(wù)T是一個項集，它是itemset的一個子集，每個事務(wù)均與一個唯一標識符Tid相聯(lián)系。不同的事務(wù)一起組成了事務(wù)集D，它構(gòu)成了關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的事務(wù)數(shù)據(jù)庫。
關(guān)聯(lián)規(guī)則：關(guān)聯(lián)規(guī)則是形如A=>B的蘊涵式，其中A、B均為itemset的子集且均不為空集，而A交B為空。
支持度(support)：關(guān)聯(lián)規(guī)則的支持度定義如下：
其中P(A∪B)表示事務(wù)包含集合A和B的并(即包含A和B中的每個項)的概率。注意與P(A or B)區(qū)別，后者表示事務(wù)包含A或B的概率。
置信度(confidence)：關(guān)聯(lián)規(guī)則的置信度定義如下：
項集的出現(xiàn)頻度(support count)：包含項集的事務(wù)數(shù)，簡稱為項集的頻度、支持度計數(shù)或計數(shù)。
頻繁項集(frequent itemset)：如果項集I的相對支持度滿足事先定義好的最小支持度閾值(即I的出現(xiàn)頻度大于相應(yīng)的最小出現(xiàn)頻度(支持度計數(shù))閾值)，則I是頻繁項集。
強關(guān)聯(lián)規(guī)則：滿足最小支持度和最小置信度的關(guān)聯(lián)規(guī)則，即待挖掘的關(guān)聯(lián)規(guī)則。
3. 實現(xiàn)步驟
一般而言，關(guān)聯(lián)規(guī)則的挖掘是一個兩步的過程：
找出所有的頻繁項集
由頻繁項集產(chǎn)生強關(guān)聯(lián)規(guī)則
3.1挖掘頻繁項集
3.1.1 相關(guān)定義
- 連接步驟：頻繁(k-1)項集Lk-1的自身連接產(chǎn)生候選k項集Ck
Apriori算法假定項集中的項按照字典序排序。如果Lk-1中某兩個的元素(項集)itemset1和itemset2的前(k-2)個項是相同的，則稱itemset1和itemset2是可連接的。所以itemset1與itemset2連接產(chǎn)生的結(jié)果項集是{itemset1[1], itemset1[2], …, itemset1[k-1], itemset2[k-1]}。連接步驟包含在下文代碼中的create_Ck函數(shù)中。
- 剪枝策略
由于存在先驗性質(zhì)：任何非頻繁的(k-1)項集都不是頻繁k項集的子集。因此，如果一個候選k項集Ck的(k-1)項子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以從Ck中刪除，獲得壓縮后的Ck。下文代碼中的is_apriori函數(shù)用于判斷是否滿足先驗性質(zhì)，create_Ck函數(shù)中包含剪枝步驟，即若不滿足先驗性質(zhì)，剪枝。
- 刪除策略
基于壓縮后的Ck，掃描所有事務(wù)，對Ck中的每個項進行計數(shù)，然后刪除不滿足最小支持度的項，從而獲得頻繁k項集。刪除策略包含在下文代碼中的generate_Lk_by_Ck函數(shù)中。
3.1.2 步驟
- 每個項都是候選1項集的集合C1的成員。算法掃描所有的事務(wù)，獲得每個項，生成C1(見下文代碼中的create_C1函數(shù))。然后對每個項進行計數(shù)。然后根據(jù)最小支持度從C1中刪除不滿足的項，從而獲得頻繁1項集L1。
- 對L1的自身連接生成的集合執(zhí)行剪枝策略產(chǎn)生候選2項集的集合C2，然后，掃描所有事務(wù)，對C2中每個項進行計數(shù)。同樣的，根據(jù)最小支持度從C2中刪除不滿足的項，從而獲得頻繁2項集L2。
- 對L2的自身連接生成的集合執(zhí)行剪枝策略產(chǎn)生候選3項集的集合C3，然后，掃描所有事務(wù)，對C3每個項進行計數(shù)。同樣的，根據(jù)最小支持度從C3中刪除不滿足的項，從而獲得頻繁3項集L3。
- 以此類推，對Lk-1的自身連接生成的集合執(zhí)行剪枝策略產(chǎn)生候選k項集Ck，然后，掃描所有事務(wù)，對Ck中的每個項進行計數(shù)。然后根據(jù)最小支持度從Ck中刪除不滿足的項，從而獲得頻繁k項集。
3.2 由頻繁項集產(chǎn)生關(guān)聯(lián)規(guī)則
一旦找出了頻繁項集，就可以直接由它們產(chǎn)生強關(guān)聯(lián)規(guī)則。產(chǎn)生步驟如下：
- 對于每個頻繁項集itemset，產(chǎn)生itemset的所有非空子集(這些非空子集一定是頻繁項集);
- 對于itemset的每個非空子集s,如果
則輸出s=>(l-s)，其中min_conf是最小置信度閾值。
4. 樣例以及Python實現(xiàn)代碼
下圖是《數(shù)據(jù)挖掘：概念與技術(shù)》(第三版)中挖掘頻繁項集的樣例圖解。
本文基于該樣例的數(shù)據(jù)編寫Python代碼實現(xiàn)Apriori算法。代碼需要注意如下兩點：
由于Apriori算法假定項集中的項是按字典序排序的，而集合本身是無序的，所以我們在必要時需要進行set和list的轉(zhuǎn)換;
由于要使用字典(support_data)記錄項集的支持度，需要用項集作為key，而可變集合無法作為字典的key，因此在合適時機應(yīng)將項集轉(zhuǎn)為固定集合frozenset。
- """
- # Python 2.7
- # Filename: apriori.py
- # Author: llhthinker
- # Email: hangliu56[AT]gmail[DOT]com
- # Blog: http://www.cnblogs.com/llhthinker/p/6719779.html
- # Date: 2017-04-16
- """
- def load_data_set():
- """
- Load a sample data set (From Data Mining: Concepts and Techniques, 3th Edition)
- Returns:
- A data set: A list of transactions. Each transaction contains several items.
- """
- data_set = [['l1', 'l2', 'l5'], ['l2', 'l4'], ['l2', 'l3'],
- ['l1', 'l2', 'l4'], ['l1', 'l3'], ['l2', 'l3'],
- ['l1', 'l3'], ['l1', 'l2', 'l3', 'l5'], ['l1', 'l2', 'l3']]
- return data_set
- def create_C1(data_set):
- """
- Create frequent candidate 1-itemset C1 by scaning data set.
- Args:
- data_set: A list of transactions. Each transaction contains several items.
- Returns:
- C1: A set which contains all frequent candidate 1-itemsets
- """
- C1 = set()
- for t in data_set:
- for item in t:
- item_set = frozenset([item])
- C1.add(item_set)
- return C1
- def is_apriori(Ck_item, Lksub1):
- """
- Judge whether a frequent candidate k-itemset satisfy Apriori property.
- Args:
- Ck_item: a frequent candidate k-itemset in Ck which contains all frequent
- candidate k-itemsets.
- Lksub1: Lk-1, a set which contains all frequent candidate (k-1)-itemsets.
- Returns:
- True: satisfying Apriori property.
- False: Not satisfying Apriori property.
- """
- for item in Ck_item:
- sub_Ck = Ck_item - frozenset([item])
- if sub_Ck not in Lksub1:
- return False
- return True
- def create_Ck(Lksub1, k):
- """
- Create Ck, a set which contains all all frequent candidate k-itemsets
- by Lk-1's own connection operation.
- Args:
- Lksub1: Lk-1, a set which contains all frequent candidate (k-1)-itemsets.
- k: the item number of a frequent itemset.
- Return:
- Ck: a set which contains all all frequent candidate k-itemsets.
- """
- Ck = set()
- len_Lksub1 = len(Lksub1)
- list_Lksub1 = list(Lksub1)
- for i in range(len_Lksub1):
- for j in range(1, len_Lksub1):
- l1 = list(list_Lksub1[i])
- l2 = list(list_Lksub1[j])
- l1.sort()
- l2.sort()
- if l1[0:k-2] == l2[0:k-2]:
- Ck_item = list_Lksub1[i] | list_Lksub1[j]
- # pruning
- if is_apriori(Ck_item, Lksub1):
- Ck.add(Ck_item)
- return Ck
- def generate_Lk_by_Ck(data_set, Ck, min_support, support_data):
- """
- Generate Lk by executing a delete policy from Ck.
- Args:
- data_set: A list of transactions. Each transaction contains several items.
- Ck: A set which contains all all frequent candidate k-itemsets.
- min_support: The minimum support.
- support_data: A dictionary. The key is frequent itemset and the value is support.
- Returns:
- Lk: A set which contains all all frequent k-itemsets.
- """
- Lk = set()
- item_count = {}
- for t in data_set:
- for item in Ck:
- if item.issubset(t):
- if item not in item_count:
- item_count[item] = 1
- else:
- item_count[item] += 1
- t_num = float(len(data_set))
- for item in item_count:
- if (item_count[item] / t_num) >= min_support:
- Lk.add(item)
- support_data[item] = item_count[item] / t_num
- return Lk
- def generate_L(data_set, k, min_support):
- """
- Generate all frequent itemsets.
- Args:
- data_set: A list of transactions. Each transaction contains several items.
- k: Maximum number of items for all frequent itemsets.
- min_support: The minimum support.
- Returns:
- L: The list of Lk.
- support_data: A dictionary. The key is frequent itemset and the value is support.
- """
- support_data = {}
- C1 = create_C1(data_set)
- L1 = generate_Lk_by_Ck(data_set, C1, min_support, support_data)
- Lksub1 = L1.copy()
- L = []
- L.append(Lksub1)
- for i in range(2, k+1):
- Ci = create_Ck(Lksub1, i)
- Li = generate_Lk_by_Ck(data_set, Ci, min_support, support_data)
- Lksub1 = Li.copy()
- L.append(Lksub1)
- return L, support_data
- def generate_big_rules(L, support_data, min_conf):
- """
- Generate big rules from frequent itemsets.
- Args:
- L: The list of Lk.
- support_data: A dictionary. The key is frequent itemset and the value is support.
- min_conf: Minimal confidence.
- Returns:
- big_rule_list: A list which contains all big rules. Each big rule is represented
- as a 3-tuple.
- """
- big_rule_list = []
- sub_set_list = []
- for i in range(0, len(L)):
- for freq_set in L[i]:
- for sub_set in sub_set_list:
- if sub_set.issubset(freq_set):
- conf = support_data[freq_set] / support_data[freq_set - sub_set]
- big_rule = (freq_set - sub_set, sub_set, conf)
- if conf >= min_conf and big_rule not in big_rule_list:
- # print freq_set-sub_set, " => ", sub_set, "conf: ", conf
- big_rule_list.append(big_rule)
- sub_set_list.append(freq_set)
- return big_rule_list
- if __name__ == "__main__":
- """
- Test
- """
- data_set = load_data_set()
- L, support_data = generate_L(data_set, k=3, min_support=0.2)
- big_rules_list = generate_big_rules(L, support_data, min_conf=0.7)
- for Lk in L:
- print "="*50
- print "frequent " + str(len(list(Lk)[0])) + "-itemsets\t\tsupport"
- print "="*50
- for freq_set in Lk:
- print freq_set, support_data[freq_set]
- print "Big Rules"
- for item in big_rules_list:
- print item[0], "=>", item[1], "conf: ", item[2]
代碼運行結(jié)果截圖如下：
