python中Apriori算法实现讲解

本文主要给大家讲解了Apriori算法的基础知识以及Apriori算法python中的实现过程，以下是所有内容：

1. Apriori算法简介

Apriori算法是挖掘布尔关联规则频繁项集的算法。Apriori算法利用频繁项集性质的先验知识，通过逐层搜索的迭代方法，即将K-项集用于探察(k+1)项集，来穷尽数据集中的所有频繁项集。先找到频繁项集1-项集集合L1， 然后用L1找到频繁2-项集集合L2，接着用L2找L3，知道找不到频繁K-项集，找到每个Lk需要一次数据库扫描。注意：频繁项集的所有非空子集也必须是频繁的。Apriori性质通过减少搜索空间，来提高频繁项集逐层产生的效率。Apriori算法由连接和剪枝两个步骤组成。

2. Apriori算法步骤

 根据一个实例来解释：下图是一个交易单，I1至I5可看作5种商品。下面通过频繁项集合来找出关联规则。

假设我们的最小支持度阈值为2，即支持度计数小于2的都要删除。

        

上表第一行（第一项交易）表示：I1和I2和I5一起被购买。

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

L1至C2的过程分三步：

遍历产生L1中所有可能性组合，即（I1,I2）...（I4,I5 )    对便利产生的每个组合进行拆分，以保证频繁项集的所有非空子集也必须是频繁的。即对于（I1，I2）来说进行拆分为I1，I2.由于I1和I2在L1中都为频繁项，所以这一组合保留。对于剩下的C2根据原数据集中进行支持度计数

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

L2至C3的过程：

还是上面的步骤。首先生成（1，2，3）、（1，2，4）、（1，2，5）....为什么最后只剩（1，2，3）和（1，2，5）呢？因为剪枝过程：（1，2，4）拆分为（1，2）和（1，4）和（2，4）.然而（1，4）在L2中不存在，即非频繁项。所有剪枝删除。然后对C3中剩下的组合进行计数。发现（1，2，3）和（1，2，5）的支持度2。迭代结束。

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

3.Apriori算法实现

1. # -*- coding: utf-8 -*- 
2. """ 
3. Created on Sat Dec 9 15:33:45 2017 
4. @author: LPS 
5. """ 
6. import numpy as np 
7. from itertools import combinations # 迭代工具 
8. data = [[1,2,5], [2,4], [2,3], [1,2,4], [1,3], [2,3], [1,3], [1,2,3,5], [1,2,3]] 
9. minsp = 2 
10. d = [] 
11. for i in range(len(data)): 
12.  d.extend(data[i]) 
13. new_d = list(set(d)) 
14. def satisfy(s, s_new, k): # 更新确实存在的L  
15.  e =[] 
16.  ss_new =[] 
17.  for i in range(len(s_new)): 
18.   for j in combinations(s_new[i], k): # 迭代产生所有元素可能性组合 
19.    e.append(list(j)) 
20.   if ([l for l in e if l not in s]) ==[] : 
21.    ss_new.append(s_new[i]) 
22.   e = [] 
23.   return ss_new # 筛选满足条件的结果  
24. def count(s_new): # 返回narray格式的C 
25.  num = 0 
26.  C = np.copy(s_new) 
27.  C = np.column_stack((C, np.zeros(C.shape[0]))) 
28.  for i in range(len(s_new)): 
29.   for j in range(len(data)): 
30.    if ([l for l in s_new[i] if l not in data[j]]) ==[] : 
31.     num = num+1 
32.   C[i,-1] = num 
33.   num = 0    
34.  return C 
35. def limit(L): # 删掉不满足阈值的C 
36.  row = [] 
37.  for i in range(L.shape[0]): 
38.   if L[i,-1] < minsp : 
39.    row.append(i) 
40.  L = np.delete(L, row, 0)  
41.  return L 
42. def generate(L, k): # 实现由L至C的转换 
43.  s = [] 
44.  for i in range(L.shape[0]): 
45.   s.append(list(L[i,:-1])) 
46.  s_new = [] 
47. # L = L.delete(L, -1, 1) 
48. # l = L.shape[1] 
49.  for i in range(L.shape[0]-1): 
50.   for j in range(i+1, L.shape[0]): 
51.    if (L[j,-2]>L[i,-2]): 
52.     t = list(np.copy(s[i])) 
53.     t.append(L[j,-2]) 
54.     s_new.append(t) # s_new为列表 
55.      
56.  s_new = satisfy(s, s_new, k)  
57.  C = count(s_new) 
58.  return C 
59. # 初始的C与L 
60. C = np.zeros([len(new_d), 2]) 
61. for i in range(len(new_d)): 
62.  C[i:] = np.array([new_d[i], d.count(new_d[i])]) 
63. L = np.copy(C) 
64. L = limit(L) 
65. # 开始迭代 
66. k = 1 
67. while (np.max(L[:,-1]) > minsp): 
68.  C = generate(L, k) # 由L产生C 
69.  L = limit(C)  # 由C产生L 
70.  k = k+1 
71. # 对最终结果去重复 
72. print((list(set([tuple(t) for t in L]))) 
73. # 结果为 [(1.0, 2.0, 3.0, 2.0), (1.0, 2.0, 5.0, 2.0)] 

原文链接：https://www.cnblogs.com/king-lps/p/8013036.html