???導(dǎo)讀

隨著大數(shù)據(jù)概念的火熱，啤酒與尿布的故事廣為人知。我們?nèi)绾伟l(fā)現(xiàn)買(mǎi)啤酒的人往往也會(huì)買(mǎi)尿布這一規(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)代碼。

1Apriori算法簡(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è)，這被稱(chēng)作"一個(gè)先驗(yàn)"（a priori）。Apriori算法的名字正是基于這樣的事實(shí)：算法使用頻繁項(xiàng)集性質(zhì)的先驗(yàn)性質(zhì)，即頻繁項(xiàng)集的所有非空子集也一定是頻繁的。Apriori算法使用一種稱(chēng)為逐層搜索的迭代方法，其中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)的集合稱(chēng)為項(xiàng)集（itemset），包含k個(gè)項(xiàng)的項(xiàng)集稱(chē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ī)則的支持度定義如下：

其中表示事務(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)稱(chēng)為項(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ò)程：

a. 找出所有的頻繁項(xiàng)集

b. 由頻繁項(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)是相同的，則稱(chē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（見(jiàn)下文代碼中的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。

以此類(lèi)推，對(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,如果

4樣例以及Python實(shí)現(xiàn)代碼

下圖是《數(shù)據(jù)挖掘：概念與技術(shù)》（第三版）中挖掘頻繁項(xiàng)集的樣例圖解。

本文基于該樣例的數(shù)據(jù)編寫(xiě)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

print "Big Rules"

for item in big_rules_list:

print item[0], "=>", item[1], "conf: ", item[2]

代碼運(yùn)行結(jié)果截圖如下：