Apriori算法介紹（Python實(shí)現(xiàn)）
隨著大數(shù)據(jù)概念的火熱，啤酒與尿布的故事廣為人知。我們?nèi)绾伟l(fā)現(xiàn)買啤酒的人往往也會(huì)買尿布這一規(guī)律?數(shù)據(jù)挖掘中的用于挖掘頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則的Apriori算法可以告訴我們。本文首先對(duì)Apriori算法進(jìn)行簡(jiǎn)介，而后進(jìn)一步介紹相關(guān)的基本概念，之后詳細(xì)的介紹Apriori算法的具體策略和步驟，***給出Python實(shí)現(xiàn)代碼。
1.Apriori算法簡(jiǎn)介
Apriori算法是經(jīng)典的挖掘頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則的數(shù)據(jù)挖掘算法。A priori在拉丁語(yǔ)中指”來(lái)自以前”。當(dāng)定義問(wèn)題時(shí)，通常會(huì)使用先驗(yàn)知識(shí)或者假設(shè)，這被稱作”一個(gè)先驗(yàn)”(a priori)。Apriori算法的名字正是基于這樣的事實(shí)：算法使用頻繁項(xiàng)集性質(zhì)的先驗(yàn)性質(zhì)，即頻繁項(xiàng)集的所有非空子集也一定是頻繁的。Apriori算法使用一種稱為逐層搜索的迭代方法，其中k項(xiàng)集用于探索(k+1)項(xiàng)集。首先，通過(guò)掃描數(shù)據(jù)庫(kù)，累計(jì)每個(gè)項(xiàng)的計(jì)數(shù)，并收集滿足最小支持度的項(xiàng)，找出頻繁1項(xiàng)集的集合。該集合記為L(zhǎng)1。然后，使用L1找出頻繁2項(xiàng)集的集合L2，使用L2找出L3，如此下去，直到不能再找到頻繁k項(xiàng)集。每找出一個(gè)Lk需要一次數(shù)據(jù)庫(kù)的完整掃描。Apriori算法使用頻繁項(xiàng)集的先驗(yàn)性質(zhì)來(lái)壓縮搜索空間。
2. 基本概念
項(xiàng)與項(xiàng)集：設(shè)itemset={item1, item_2, …, item_m}是所有項(xiàng)的集合，其中，item_k(k=1,2,…,m)成為項(xiàng)。項(xiàng)的集合稱為項(xiàng)集(itemset)，包含k個(gè)項(xiàng)的項(xiàng)集稱為k項(xiàng)集(k-itemset)。
事務(wù)與事務(wù)集：一個(gè)事務(wù)T是一個(gè)項(xiàng)集，它是itemset的一個(gè)子集，每個(gè)事務(wù)均與一個(gè)唯一標(biāo)識(shí)符Tid相聯(lián)系。不同的事務(wù)一起組成了事務(wù)集D，它構(gòu)成了關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的事務(wù)數(shù)據(jù)庫(kù)。
關(guān)聯(lián)規(guī)則：關(guān)聯(lián)規(guī)則是形如A=>B的蘊(yùn)涵式，其中A、B均為itemset的子集且均不為空集，而A交B為空。
支持度(support)：關(guān)聯(lián)規(guī)則的支持度定義如下：
其中P(A∪B)表示事務(wù)包含集合A和B的并(即包含A和B中的每個(gè)項(xiàng))的概率。注意與P(A or B)區(qū)別，后者表示事務(wù)包含A或B的概率。
置信度(confidence)：關(guān)聯(lián)規(guī)則的置信度定義如下：
項(xiàng)集的出現(xiàn)頻度(support count)：包含項(xiàng)集的事務(wù)數(shù)，簡(jiǎn)稱為項(xiàng)集的頻度、支持度計(jì)數(shù)或計(jì)數(shù)。
頻繁項(xiàng)集(frequent itemset)：如果項(xiàng)集I的相對(duì)支持度滿足事先定義好的最小支持度閾值(即I的出現(xiàn)頻度大于相應(yīng)的最小出現(xiàn)頻度(支持度計(jì)數(shù))閾值)，則I是頻繁項(xiàng)集。
強(qiáng)關(guān)聯(lián)規(guī)則：滿足最小支持度和最小置信度的關(guān)聯(lián)規(guī)則，即待挖掘的關(guān)聯(lián)規(guī)則。
3. 實(shí)現(xiàn)步驟
一般而言，關(guān)聯(lián)規(guī)則的挖掘是一個(gè)兩步的過(guò)程：
找出所有的頻繁項(xiàng)集
由頻繁項(xiàng)集產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則
3.1挖掘頻繁項(xiàng)集
3.1.1 相關(guān)定義
- 連接步驟：頻繁(k-1)項(xiàng)集Lk-1的自身連接產(chǎn)生候選k項(xiàng)集Ck
Apriori算法假定項(xiàng)集中的項(xiàng)按照字典序排序。如果Lk-1中某兩個(gè)的元素(項(xiàng)集)itemset1和itemset2的前(k-2)個(gè)項(xiàng)是相同的，則稱itemset1和itemset2是可連接的。所以itemset1與itemset2連接產(chǎn)生的結(jié)果項(xiàng)集是{itemset1[1], itemset1[2], …, itemset1[k-1], itemset2[k-1]}。連接步驟包含在下文代碼中的create_Ck函數(shù)中。
- 剪枝策略
由于存在先驗(yàn)性質(zhì)：任何非頻繁的(k-1)項(xiàng)集都不是頻繁k項(xiàng)集的子集。因此，如果一個(gè)候選k項(xiàng)集Ck的(k-1)項(xiàng)子集不在Lk-1中，則該候選也不可能是頻繁的，從而可以從Ck中刪除，獲得壓縮后的Ck。下文代碼中的is_apriori函數(shù)用于判斷是否滿足先驗(yàn)性質(zhì)，create_Ck函數(shù)中包含剪枝步驟，即若不滿足先驗(yàn)性質(zhì)，剪枝。
- 刪除策略
基于壓縮后的Ck，掃描所有事務(wù)，對(duì)Ck中的每個(gè)項(xiàng)進(jìn)行計(jì)數(shù)，然后刪除不滿足最小支持度的項(xiàng)，從而獲得頻繁k項(xiàng)集。刪除策略包含在下文代碼中的generate_Lk_by_Ck函數(shù)中。
3.1.2 步驟
- 每個(gè)項(xiàng)都是候選1項(xiàng)集的集合C1的成員。算法掃描所有的事務(wù)，獲得每個(gè)項(xiàng)，生成C1(見下文代碼中的create_C1函數(shù))。然后對(duì)每個(gè)項(xiàng)進(jìn)行計(jì)數(shù)。然后根據(jù)最小支持度從C1中刪除不滿足的項(xiàng)，從而獲得頻繁1項(xiàng)集L1。
- 對(duì)L1的自身連接生成的集合執(zhí)行剪枝策略產(chǎn)生候選2項(xiàng)集的集合C2，然后，掃描所有事務(wù)，對(duì)C2中每個(gè)項(xiàng)進(jìn)行計(jì)數(shù)。同樣的，根據(jù)最小支持度從C2中刪除不滿足的項(xiàng)，從而獲得頻繁2項(xiàng)集L2。
- 對(duì)L2的自身連接生成的集合執(zhí)行剪枝策略產(chǎn)生候選3項(xiàng)集的集合C3，然后，掃描所有事務(wù)，對(duì)C3每個(gè)項(xiàng)進(jìn)行計(jì)數(shù)。同樣的，根據(jù)最小支持度從C3中刪除不滿足的項(xiàng)，從而獲得頻繁3項(xiàng)集L3。
- 以此類推，對(duì)Lk-1的自身連接生成的集合執(zhí)行剪枝策略產(chǎn)生候選k項(xiàng)集Ck，然后，掃描所有事務(wù)，對(duì)Ck中的每個(gè)項(xiàng)進(jìn)行計(jì)數(shù)。然后根據(jù)最小支持度從Ck中刪除不滿足的項(xiàng)，從而獲得頻繁k項(xiàng)集。
3.2 由頻繁項(xiàng)集產(chǎn)生關(guān)聯(lián)規(guī)則
一旦找出了頻繁項(xiàng)集，就可以直接由它們產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。產(chǎn)生步驟如下：
- 對(duì)于每個(gè)頻繁項(xiàng)集itemset，產(chǎn)生itemset的所有非空子集(這些非空子集一定是頻繁項(xiàng)集);
- 對(duì)于itemset的每個(gè)非空子集s,如果
則輸出s=>(l-s)，其中min_conf是最小置信度閾值。
4. 樣例以及Python實(shí)現(xiàn)代碼
下圖是《數(shù)據(jù)挖掘：概念與技術(shù)》(第三版)中挖掘頻繁項(xiàng)集的樣例圖解。
本文基于該樣例的數(shù)據(jù)編寫Python代碼實(shí)現(xiàn)Apriori算法。代碼需要注意如下兩點(diǎn)：
由于Apriori算法假定項(xiàng)集中的項(xiàng)是按字典序排序的，而集合本身是無(wú)序的，所以我們?cè)诒匾獣r(shí)需要進(jìn)行set和list的轉(zhuǎn)換;
由于要使用字典(support_data)記錄項(xiàng)集的支持度，需要用項(xiàng)集作為key，而可變集合無(wú)法作為字典的key，因此在合適時(shí)機(jī)應(yīng)將項(xià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]
代碼運(yùn)行結(jié)果截圖如下：
