Apriori這個詞的意思是“先驗的”，從priori這個詞根可以猜出來~;)?。該算法用于從數(shù)據(jù)中挖掘頻繁項數(shù)據(jù)集以及關(guān)聯(lián)規(guī)則。其核心原理是基于這樣一類“先驗知識”：?

如果一個數(shù)據(jù)項在數(shù)據(jù)庫中是頻繁出現(xiàn)的，那么該數(shù)據(jù)項的子集在數(shù)據(jù)庫中也應(yīng)該是頻繁出現(xiàn)的（命題1）

???

?X,Y∈J:(X?Y)→f(X)≤f(Y)?X,Y∈J:(X?Y)→f(X)≤f(Y)

反之亦然，其逆否命題為：

如果一個數(shù)據(jù)項在數(shù)據(jù)庫中很少出現(xiàn)，那么包含該數(shù)據(jù)項的父集（superset）在數(shù)據(jù)庫中也應(yīng)該很少出現(xiàn)。(命題2)

? ??

f(X)≥f(Y)→?X,Y∈J:(X?Y)f(X)≥f(Y)→?X,Y∈J:(X?Y)

?

背景知識：

①假設(shè)我們要從數(shù)據(jù)庫中找到如下一種關(guān)聯(lián)規(guī)則：

x→yx→y

??也就是說，當(dāng)某一數(shù)據(jù)項包含包含集合X時，該數(shù)據(jù)項肯定包含集合Y。

②既然說有X的地方必定有Y，那么我們需要大量的數(shù)據(jù)來說明這一點。用X和Y同時出現(xiàn)的次數(shù)除以數(shù)據(jù)庫中數(shù)據(jù)項的總數(shù)得到“支持度”的概念：

? ?

Support,s(X→Y)=δ(X∪Y)N;Support,s(X→Y)=δ(X∪Y)N;

③在集合X出現(xiàn)的數(shù)據(jù)項中，是否一定會出現(xiàn)集合Y呢？我們用X和Y同時出現(xiàn)的次數(shù)除以X出現(xiàn)的全部次數(shù)，得到“置信度”的概念：

? ???

Confidence,c(X→Y)=δ(X∪Y)δ(X);Confidence,c(X→Y)=δ(X∪Y)δ(X);

深入理解apriori算法：

分析“支持度”和“置信度”的概念可知，在給定“支持度”和“置信度”的條件下為了找到關(guān)聯(lián)規(guī)則，首先需要找到符合“支持度”條件的X和Y的并集{X，Y}。由命題1可知，如果集合{X,Y}滿足“支持度”條件（即頻繁出現(xiàn)），那么集合中的每個元素也應(yīng)該是頻繁出現(xiàn)的。集合的構(gòu)成可以用樹來表示，下面用圖1來說明。

?

圖?1?若{c,d,e}頻繁出現(xiàn)，則{cd}{ce}{de}，{c}ze8trgl8bvbq{e}也頻繁出現(xiàn)

?

圖?2如果{a,b}不是頻繁集，那么{abc}{abd}{abe}{abcd}{abce}{abde}{abcde}也都不是頻繁集。

?

由此可見，如果我們從單一元素所構(gòu)成的集合下手（也就是上圖中樹的第一層，記為C1），根據(jù)“支持度”判別條件對該樹進(jìn)行“剪枝”，將大大降低計算的次數(shù)。

得到C1后，如果根據(jù)組合原理直接生成C2然后對每個可能的組合計算“支持度”，計算量依然很大。這里再次進(jìn)行剪枝。為了不失一般性，對于Ck-1層中的每個集合先排序，然后將滿足以下條件的集合融合，構(gòu)成Ck層

???

ai=bi(fori=1,2,...,k?2)andak?1≠bk?1ai=bi(fori=1,2,...,k?2)andak?1≠bk?1

之所以這樣做是因為，根據(jù)命題2，如果集合C4層的{acde}是頻繁集，那么C3層中必定要存在{acd}和{ace}。因此只需在C3成對這兩個集合融合即可，不必再將{ace}和{ade}融合，在C3層對元素排序的目的也正是在此，快速地找到滿足條件的子集并融合，避免重復(fù)計算。

?

優(yōu)化：

在得到Ck層后，計算其中每個集合的“支持度”時，需要從數(shù)據(jù)庫中遍歷所有的數(shù)據(jù)項看是否包含該集合。這里可以采用Hash表將所有的數(shù)據(jù)映射到一張表上，以后就不用遍歷整個數(shù)據(jù)庫而是只遍歷Hash值相同的所有數(shù)據(jù)項。

?

生成規(guī)則：

對于前面得到的頻繁項集合中每個元素，其可能生成的規(guī)則可以表示為下圖

?

圖3 從頻繁項生成規(guī)則

以上圖為例來說明，假設(shè)由{bcd}生成{a}這一規(guī)則不滿足置信度公式，回顧“置信度”的公式，也就是說{bcd}在數(shù)據(jù)庫中出現(xiàn)的次數(shù)偏多，而{a}出現(xiàn)的次數(shù)偏少，根據(jù)命題1，{bcd}的子集也是頻繁項，根據(jù)命題2，{a}的父集也很少出現(xiàn)，從而{bc}生成{ad}等規(guī)則的置信度更低，然后將其從集合樹上減去。

?

總結(jié)：

將以上過程聯(lián)系起來，就得到了書上的偽代碼，我將其用通俗的語言解釋一下：

?

1.?遍歷數(shù)據(jù)庫，得到所有數(shù)據(jù)項構(gòu)成的并集（也就是得到圖1的C1層）

2.?計算Ck層中每個元素的支持度（該過程可用Hash表優(yōu)化），刪除不符合的元素，將剩下的元素排序，并加入頻繁項集R

3.?根據(jù)融合規(guī)則將Ck層的元素融合得到Ck+1,

4.?重復(fù)2,3步直到某一層元素融合后得到的是空集

5.?遍歷R中的元素，設(shè)該元素為A={a1，a2......，ak}

6.?按照圖?所示方法先生成I1層規(guī)則，即{x|x屬于A且≠ai}?→{ai}

7.?計算該層所有規(guī)則的“置信度”，刪除不符合的規(guī)則，將剩下的規(guī)則作為結(jié)果輸出。

8.?生成下一層的規(guī)則，計算“置信度”，輸出結(jié)果。

?

參考文獻(xiàn)：

?

? ? ? ? Machine Learning in Action:http://pan.baidu.com/s/1Gc4ss

? ? ? ? Introduction to Data Mining?chapter 6 :http://pan.baidu.com/s/1oskIS

?

?

Python源碼：

去GitHub下載該文件源碼

01?fromnumpyimport*
02?importitertools
03?
04?support_dic={}
05?
06?#生成原始數(shù)據(jù)，用于測試
07?defloadDataSet():
08?return[[1,3,4],[2,3,5],[1,2,3,5],[2,5]]
09?
10?#獲取整個數(shù)據(jù)庫中的一階元素
11?defcreateC1(dataSet):
12?C1=set([])
13?foritemindataSet:
14?C1=C1.union(set(item))
15?return[frozenset([i])foriinC1]
16?
17?#輸入數(shù)據(jù)庫（dataset） 和 由第K-1層數(shù)據(jù)融合后得到的第K層數(shù)據(jù)集（Ck），
18?#用最小支持度（minSupport)對 Ck 過濾，得到第k層剩下的數(shù)據(jù)集合（Lk）
19?defgetLk(dataset,Ck,minSupport):
20?globalsupport_dic
21?Lk={}
22?#計算Ck中每個元素在數(shù)據(jù)庫中出現(xiàn)次數(shù)
23?foritemindataset:
24?forCiinCk:
25?ifCi.issubset(item):
26?ifnotCiinLk:
27?Lk[Ci]=1
28?else:
29?Lk[Ci]+=1
30?#用最小支持度過濾
31?Lk_return=[]
32?forLiinLk:
33?support_Li=Lk[Li]/float(len(dataSet))
34?ifsupport_Li>=minSupport:
35?Lk_return.append(Li)
36?support_dic[Li]=support_Li
37?returnLk_return
38?
39?#將經(jīng)過支持度過濾后的第K層數(shù)據(jù)集合（Lk）融合
40?#得到第k+1層原始數(shù)據(jù)Ck1
41?defgenLk1(Lk):
42?Ck1=[]
43?foriinrange(len(Lk)-1):
44?forjinrange(i+1,len(Lk)):
45?ifsorted(list(Lk[i]))[0:-1]==sorted(list(Lk[j]))[0:-1]:
46?Ck1.append(Lk[i]|Lk[j])
47?returnCk1
48?
49?#遍歷所有二階及以上的頻繁項集合
50?defgenItem(freqSet,support_dic):
51?foriinrange(1,len(freqSet)):
52?forfreIteminfreqSet[i]:
53?genRule(freItem)
54?
55?#輸入一個頻繁項，根據(jù)“置信度”生成規(guī)則
56?#采用了遞歸，對規(guī)則樹進(jìn)行剪枝
57?defgenRule(Item,minConf=0.7):
58?iflen(Item)>=2:
59?forelementinitertools.combinations(list(Item),1):
60?ifsupport_dic[Item]/float(support_dic[Item-frozenset(element)])>=minConf:
61?printstr([Item-frozenset(element)])+"—–>"+str(element)
62?printsupport_dic[Item]/float(support_dic[Item-frozenset(element)])
63?genRule(Item-frozenset(element))
64?
65?#輸出結(jié)果
66?ifname=='main':
67?dataSet=loadDataSet()
68?result_list=[]
69?Ck=createC1(dataSet)
70?#循環(huán)生成頻繁項集合，直至產(chǎn)生空集
71?whileTrue:
72?Lk=getLk(dataSet,Ck,0.5)
73?ifnotLk:
74?break
75?result_list.append(Lk)
76?Ck=genLk1(Lk)
77?ifnotCk:
78?break
79?#輸出頻繁項及其“支持度”
80?printsupport_dic
81?#輸出規(guī)則
82?genItem(result_list,support_dic)

from: http://tianjun.me/essays/17/

總結(jié)

以上是生活随笔為你收集整理的Apriori算法简介及实现（python）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。