快捷導(dǎo)航

python中Apriori算法實(shí)現(xiàn)講解

更新時(shí)間：2017年12月10日 18:29:12 作者：三年一夢(mèng)

給大家詳細(xì)講解一下Apriori 算法在python中的實(shí)現(xiàn)過程，有需要的朋友收藏一下本片文章吧。

本文主要給大家講解了Apriori算法的基礎(chǔ)知識(shí)以及Apriori算法python中的實(shí)現(xiàn)過程，以下是所有內(nèi)容：

1. Apriori算法簡(jiǎn)介

Apriori算法是挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。Apriori算法利用頻繁項(xiàng)集性質(zhì)的先驗(yàn)知識(shí)，通過逐層搜索的迭代方法，即將K-項(xiàng)集用于探察(k+1)項(xiàng)集，來窮盡數(shù)據(jù)集中的所有頻繁項(xiàng)集。先找到頻繁項(xiàng)集1-項(xiàng)集集合L1，然后用L1找到頻繁2-項(xiàng)集集合L2，接著用L2找L3，知道找不到頻繁K-項(xiàng)集，找到每個(gè)Lk需要一次數(shù)據(jù)庫(kù)掃描。注意：頻繁項(xiàng)集的所有非空子集也必須是頻繁的。Apriori性質(zhì)通過減少搜索空間，來提高頻繁項(xiàng)集逐層產(chǎn)生的效率。Apriori算法由連接和剪枝兩個(gè)步驟組成。

2. Apriori算法步驟

根據(jù)一個(gè)實(shí)例來解釋：下圖是一個(gè)交易單，I1至I5可看作5種商品。下面通過頻繁項(xiàng)集合來找出關(guān)聯(lián)規(guī)則。

假設(shè)我們的最小支持度閾值為2，即支持度計(jì)數(shù)小于2的都要?jiǎng)h除。

上表第一行（第一項(xiàng)交易）表示：I1和I2和I5一起被購(gòu)買。

C1至L1的過程：只需查看支持度是否高于閾值，然后取舍。上圖C1中所有閾值都大于2，故L1中都保留。

L1至C2的過程分三步：

遍歷產(chǎn)生L1中所有可能性組合，即（I1,I2）...（I4,I5 ) 對(duì)便利產(chǎn)生的每個(gè)組合進(jìn)行拆分，以保證頻繁項(xiàng)集的所有非空子集也必須是頻繁的。即對(duì)于（I1，I2）來說進(jìn)行拆分為I1，I2.由于I1和I2在L1中都為頻繁項(xiàng)，所以這一組合保留。對(duì)于剩下的C2根據(jù)原數(shù)據(jù)集中進(jìn)行支持度計(jì)數(shù)

C2至L2的過程：只需查看支持度是否高于閾值，然后取舍。

L2至C3的過程：

還是上面的步驟。首先生成（1，2，3）、（1，2，4）、（1，2，5）....為什么最后只剩（1，2，3）和（1，2，5）呢？因?yàn)榧糁^程：（1，2，4）拆分為（1，2）和（1，4）和（2，4）.然而（1，4）在L2中不存在，即非頻繁項(xiàng)。所有剪枝刪除。然后對(duì)C3中剩下的組合進(jìn)行計(jì)數(shù)。發(fā)現(xiàn)（1，2，3）和（1，2，5）的支持度2。迭代結(jié)束。

所以算法過程就是 Ck - Lk - Ck+1 的過程：

3.Apriori算法實(shí)現(xiàn)

# -*- coding: utf-8 -*-
"""
Created on Sat Dec 9 15:33:45 2017
@author: LPS
"""
import numpy as np
from itertools import combinations # 迭代工具
data = [[1,2,5], [2,4], [2,3], [1,2,4], [1,3], [2,3], [1,3], [1,2,3,5], [1,2,3]]
minsp = 2
d = []
for i in range(len(data)):
 d.extend(data[i])
new_d = list(set(d))
def satisfy(s, s_new, k): # 更新確實(shí)存在的L 
 e =[]
 ss_new =[]
 for i in range(len(s_new)):
  for j in combinations(s_new[i], k): # 迭代產(chǎn)生所有元素可能性組合
   e.append(list(j))
  if ([l for l in e if l not in s]) ==[] :
   ss_new.append(s_new[i])
  e = []
  return ss_new # 篩選滿足條件的結(jié)果 
def count(s_new): # 返回narray格式的C
 num = 0
 C = np.copy(s_new)
 C = np.column_stack((C, np.zeros(C.shape[0])))
 for i in range(len(s_new)):
  for j in range(len(data)):
   if ([l for l in s_new[i] if l not in data[j]]) ==[] :
    num = num+1
  C[i,-1] = num
  num = 0   
 return C
def limit(L): # 刪掉不滿足閾值的C
 row = []
 for i in range(L.shape[0]):
  if L[i,-1] < minsp :
   row.append(i)
 L = np.delete(L, row, 0) 
 return L
def generate(L, k): # 實(shí)現(xiàn)由L至C的轉(zhuǎn)換
 s = []
 for i in range(L.shape[0]):
  s.append(list(L[i,:-1]))
 s_new = []
# L = L.delete(L, -1, 1)
# l = L.shape[1]
 for i in range(L.shape[0]-1):
  for j in range(i+1, L.shape[0]):
   if (L[j,-2]>L[i,-2]):
    t = list(np.copy(s[i]))
    t.append(L[j,-2])
    s_new.append(t) # s_new為列表
    
 s_new = satisfy(s, s_new, k) 
 C = count(s_new)
 return C
# 初始的C與L
C = np.zeros([len(new_d), 2])
for i in range(len(new_d)):
 C[i:] = np.array([new_d[i], d.count(new_d[i])])
L = np.copy(C)
L = limit(L)
# 開始迭代
k = 1
while (np.max(L[:,-1]) > minsp):
 C = generate(L, k) # 由L產(chǎn)生C
 L = limit(C)  # 由C產(chǎn)生L
 k = k+1
# 對(duì)最終結(jié)果去重復(fù)
print((list(set([tuple(t) for t in L])))
# 結(jié)果為 [(1.0, 2.0, 3.0, 2.0), (1.0, 2.0, 5.0, 2.0)]

您可能感興趣的文章: