Python实现Apriori算法

发表于   |   分类于   |  

前言

数据挖掘课程讲到了Apriori关联规则挖掘算法，老师要求完成实验并分析，所以就来写博客啦。

正文

Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。而且算法已经被广泛的应用到商业、网络安全等各个领域。

实验要求：

  • 合理的算法开发工具+数据库模式
  • 给定minsupport，测试算法时间与数据量大小的关系
  • 给定数据量，测试算法时间与minsupport的关系

我采用的是python3.5+Sql server2012的实验环境，最后图形化实验结果靠的是python的matplotlib库，网上也有很多教程的。

数据库是随机生成的，数据量分别是1W,2w,5w,10w,20w,50w,100w。形式如下：

A C E I J
C E F G H
C E E G H I J
C E F G H J
B C G H
B C F H J
C E H I
A B E F H
C G J
….

算法框架

1
2
3
4
5
6
7
8
9
10
11
12
13
L1={large 1-itemset};    // 生成含有1个项目的频繁集   
	for (k=2; Lk-1≠Ø; k++) do   
	{   
		Ck=Apriori_gen(Lk-1);  
    	forall transaction t∈D do  
        {    
        	Ct=subset(Ck,t);   //产生包含于事务t中的k项目集Ct  
            forall Candidate c∈Ct  do  
        		c.count++;     
		}  
  		Lk={c∈Ck∣c.count≥minsup 
	}    
Answer=Uk Lk;

Apriori_gen(Lk-1)的算法步骤：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
insert into Ck 
	select p.item1，p.item2，……，p.itemk-1，q.itemk-1
 	from Lk-1.p， Lk-1.q
 	where p.item1=q.item1，p.item2=q.item2，
	…，p.itemk-2=q.itemk-2，p.item k-1<q.item k-1；
forall itemsets c∈Ck do
	forall (k-1)_subsets s of c do
		if (s not in Lk-1) then 
			delete c from Ck;
```   
# 代码
```python  
 -*- coding: utf-8 -*-
Created on Sun Nov 20 13:13:08 2016
@author: xc
"""
import copy
import pymssql
import time
import csv 
def init_data():
    try:
        conn = pymssql.connect(host="localhost",user="sa",password="12345", database="apriori")            //连接数据库
    except pymssql.OperationalError:
        print( "error: Could not Connection SQL Server!please check your dblink configure!")
    else:
        cur = conn.cursor()
        
    cur.execute("select * from tab20")
    rows=cur.fetchall()    //读取数据库  取出所有记录
    conn.close()
        
    T=[]
    count=0
    for item in rows:
        T.append([])
        for i in item:
            if i != ' ':
                T[count].append(i)
        count+=1
        
    for item in T:
        print(item)
        
    return T
    
    
初始化所有一项集
def init_pass(T):
    C = {}  #C为字典
    for t in T: 
        for i in t:
            if i in C.keys():
                C[i] += 1
            else:
                C[i] = 1
    return C
def generate(F):
    C = []
    k = len(F[0]) + 1
    for f1 in F:
        for f2 in F:
            if f1[k-2] < f2[k-2]:
                c = copy.copy(f1)
                c.append(f2[k-2])
                flag = True
                for i in range(0,k-1):
                    s = copy.copy(c)
                    s.pop(i)
                    if s not in F:
                        flag = False
                        break
                if flag and c not in C:
                    C.append(c)
    return C
def compareList(A,B):
    for a in A:
        if a not in B:
            return False
    return True
    
def apriori(T,minSupport):
    D=[]
    C=init_pass(T)
    keys=C.keys();#.keys()方法，求出字典中的索引
    D.append(sorted(keys))#加入D集中
    F=[[]]
    for f in D[0]:
        if C[f]>=minSupport:
            F[0].append([f])
    k=1
    while F[k-1]!=[]:
        D.append(generate(F[k-1]))
        F.append([])
        count={}
        for t in T:
            i=0
            for c in D[k]:
                if compareList(c,t):
                    if i in count.keys():
                        count[i] += 1
                    else:
                        count[i] = 1
                i+=1
        print(count)
        for i in count:
            if count[i]>=minSupport:
                F[k].append(D[k][i])
        print(F)
        
        k+=1
    U = []
    for f in F:
        for x in f:
            U.append(x)
    return U
if __name__ == "__main__":
    start=time.clock()
    T=init_data()
    Z= apriori(T,100000)       //第二个参数为最小支持度
    
    try:
        datacsv=open(r'C:\Users\xc\Desktop\test.csv',"w",newline="") 
        csvwriter = csv.writer(datacsv)
        for item in Z:
            print(item)
            csvwriter.writerow(item)
        datacsv.close()
    except:
        pass
    print(time.clock()-start)

成果

后记

  1. 从这个实验接触了python与Sql server的连接过程，熟悉使用了pymssql，异常好用。
  1. python的速度还是不能和C语言之类的比，只能说数据处理更方便，所以我这个程序也好写很多。如果叫我用Java写我是拒绝的。

附源码地址：https://github.com/xucheng7112/Apriori