Apriori算法是通過(guò)限制候選產(chǎn)生發(fā)現(xiàn)頻繁項(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)集诬留。
為了提高頻繁項(xiàng)集逐層產(chǎn)生的效率斜纪，一種稱為先驗(yàn)性質(zhì)（Apriori property）的重要性質(zhì)用于壓縮搜索空間。
先驗(yàn)性質(zhì)：頻繁項(xiàng)集的所有非空子集也一定是頻繁的文兑。
其實(shí)盒刚，算法的描述理解起來(lái)是困難的，有例子幫助理解最好不過(guò)绿贞。恩伪冰，盜圖一張。
Python實(shí)現(xiàn)：
我們的期望：
輸入：數(shù)據(jù)庫(kù)中數(shù)據(jù)和最小支持度
輸出：頻繁項(xiàng)集
例：
輸入：數(shù)據(jù)樟蠕，[['A','B','C','D'],['B','C','E'],['A','B','C','E'],['B','D','E'],['A','B','C','D']]；最小支持度：0.7
輸出：[['B'], ['C'], ['B', 'C']]
寫(xiě)一個(gè)方法 def apriori(D, minSup)靠柑，參數(shù)D就是輸入的數(shù)據(jù)庫(kù)數(shù)據(jù)寨辩，minSup是最小支持度。
def apriori(D, minSup):
'''頻繁項(xiàng)集用keys表示歼冰，
key表示項(xiàng)集中的某一項(xiàng)靡狞，
cutKeys表示經(jīng)過(guò)剪枝步的某k項(xiàng)集。
C表示某k項(xiàng)集的每一項(xiàng)在事務(wù)數(shù)據(jù)庫(kù)D中的支持計(jì)數(shù)
'''
#先求出1項(xiàng)集的集合及其支持計(jì)數(shù)隔嫡，注意此處C1是字典甸怕，key為項(xiàng)集，value是計(jì)數(shù)腮恩，與下不同梢杭，下的C是列表只有計(jì)數(shù)
C1 = {}
for T in D:
for I in T:
if I in C1:
C1[I] += 1
else:
C1[I] = 1
_keys1 = C1.keys()
#此處對(duì)keys的存儲(chǔ)格式進(jìn)行處理，為了方便后邊由此得出k+1項(xiàng)集的集合
keys1 = []
for i in _keys1:
keys1.append([i])
n = len(D)
cutKeys1 = []
#對(duì)keys1（1項(xiàng)集）進(jìn)行剪枝步
for k in keys1[:]:
if C1[k[0]]*1.0/n >= minSup:
cutKeys1.append(k)
cutKeys1.sort()
總之秸滴，對(duì)于1項(xiàng)集要進(jìn)行特殊處理武契，然后再用迭代的方法求k+1項(xiàng)集。
好，迭代來(lái)了：
all_keys = []
while keys != []:
C = getC(D, keys)
cutKeys = getCutKeys(keys, C, minSup, D)
for key in cutKeys:
all_keys.append(key)
keys = aproiri_gen(cutKeys)
return all_keys
注意咒唆，all_keys是全局變量届垫，存儲(chǔ)所有通過(guò)剪枝步的k項(xiàng)集。
函數(shù)getC(D, keys)是對(duì)keys中的每一個(gè)key進(jìn)行計(jì)數(shù)全释，函數(shù)getCutKeys(keys, C, minSup, D)是剪枝步的實(shí)現(xiàn)装处，函數(shù)aproiri_gen(cutKeys)是由k項(xiàng)集獲得k+1項(xiàng)集（連接步）。
這樣浸船，算法Apriori就實(shí)現(xiàn)了妄迁，輸入輸出試一下：
D = [['A','B','C','D'],['B','C','E'],['A','B','C','E'],['B','D','E'],['A','B','C','D']]
F = apriori(D, 0.7)
print '\nfrequent itemset:\n', F
把最小支持度改成
0.5試試：
恩，沒(méi)有問(wèn)題糟袁。
完整代碼見(jiàn)：https://github.com/youthpasses/apriori
