关联规则apriori算法的python实现

学了两天python，想实践下，正好最近在学习数据挖掘，先用python实现下

注：由于后面加了注释，由于编码问题，可能即使是注释，有的环境也不支持汉字的编码，运行报错的话可以将汉字删除后再运行

环境 ubuntu 13.4 python 2

1. 
   
2. import itertools
3. import copy
5. '''
6. 定义全局变量k，即支持度计数k,此k也可以在运行程序之前输入，简单改动即可
7. '''
8. k = 2
10. '''
11. 存储频繁项集的列表
12. '''
13. frequenceItem = []
16. '''
17. 从txt文件dataset.txt里获取事务集
18. '''
19. def getDataSet(args):
20. f = open(args,'r')
21. source = f.readlines()
22. f.close()
23. dataset = []
24. for line in source:
25. temp1 = line.strip('')
26. temp2 = temp1.split(',')
27. dataset.append(temp2)
28. return dataset
31. '''
32. 初步扫描事务集，从事务集里获取候选1项集
33. 方法的基本思路是：
34. 定义一个集合tmp，将事务集的第一项作为tmp的初始集合
35. 然后扫描事务集，将不在tmp里的数据项加入tmp中
36. '''
37. def find_item( dataset ):
38. length = len(dataset)
39. for i in range(0, length):
40. if i == 0:
41. tmp = set(dataset[i])
42. tmp.update(set(dataset[i]))
43. candidate=list(tmp)
44. candidate.sort()
45. return candidate
49. '''
50. 从候选项集里找出频繁项集，其中num代表频繁num+1项集
51. 如num为0的为从候选1项集里找出频繁1项集
52. 方法基本思路：
53. 1、定义一个支持度列表count
54. 2、对于每一个候选项，依次扫描事务集，如果该项出现在事务集中就将该项对应的count+1、定义一个支持度列表count+1
55. 3、将每一项的count和k（支持度计数）进行比较，将count小于k的项剔除
56. '''
57. def find_frequent( candidate, dataset, num):
58. frequence = []
59. length = len(candidate)
60. count = []
61. for i in range(0, length):
62. count.append(0)
63. count[i] = 0
64. if num == 0:
65. '''
66. 其实不管num为0还是别的值算法应该是一样的，但是由于程序实现上的问题
67. num为0的时候选项集是一维列表，其它的时候，候选项集是二维列表，
68. 毕竟只是自己写着玩的，python还不熟，牵一发而动全身，懒得改了
69. '''
70. child= set([candidate[i]])
71. else:
72. child = set(candidate[i])
73. for j in dataset:
74. parent = set(j)
75. if child.issubset(parent):
76. count[i] = count[i]+1
77. for m in range(0, length):
78. if count[m] >= k:
79. frequence.append(candidate[m])
80. return frequence
83. '''
84. 先验定理，剪枝掉不必要的候选n项集
85. 方法思路：
86. 1、依次取出候选项集里的项
87. 2、取出n项集里的n-1项子集
88. 3、如果所有的n-1项集不都都是频繁n-1项集的子集，则删除该候选项集
89. '''
90. def pre_test(candidate, num,frequence):
91. r_candidate = copy.deepcopy(candidate)
92. for each in candidate:
93. for each2 in itertools.combinations(each,num):
94. tmp= (list(each2))
95. tag = 0
96. for j in frequence:
97. if num == 1:
98. if (tmp[0] == j):
99. tag = 1
100. break
101. else:
102. if tmp == j:
103. tag = 1
104. break
105. if tag == 0:
106. r_candidate.remove(each)
107. break
108. return r_candidate
112. '''
113. 通过频繁n-1项集产生候选n项集，并通过先验定理对候选n项集进行剪枝
114. 方法思路：
115. 1、如果是频繁1项集，则通过笛卡尔积产生频繁2项集
116. 2、如果不是频繁一项集，采用F（k-1） * F（k-1）方法通过频繁n-1项集产生候选n项集
117. 注：F（k-1） * F（k-1）方法在我的另一篇关联算法博客上做了理论上的简单介绍，或者也可以直接参看《数据挖掘导论》
118. '''
119. def get_candidata( frequence, num ):
120. length = len(frequence)
121. candidate =[]
122. if num == 1:
123. for each in itertools.combinations(frequence,2):
124. tmp = list(each)
125. tmp3 = []
126. tmp3.append(tmp[0])
127. tmp3.append(tmp[1])
128. candidate.append(tmp3)
129. else:
130. for i in range(0,length-1):
131. tmp1 = copy.deepcopy(frequence[i])
132. tmp1.pop(num-1)
133. for j in range(i+1, length):
134. tmp2 = copy.deepcopy(frequence[j])
135. tmp2.pop(num-1)
136. if tmp1 == tmp2:
137. tmp3 = copy.deepcopy(frequence[i])
138. tmp3.append(frequence[j][num-1])
139. candidate.append(tmp3)
140. candidate2 = pre_test(candidate, num, frequence)
141. return candidate2
144. '''
145. main程序
146. '''
147. if __name__=='__main__':
148. dataset = getDataSet('dataset.txt')
149. Item = find_item(dataset)
150. num = 0
151. frequenceItem= []
153. '''
154. 通过事务集找到频繁项集，直至频繁n项集为空，则退出循环
155. '''
156. while 1:
157. if num == 0:
158. candidate = Item
159. else:
160. candidate = get_candidata(frequenceItem[num-1],num)
161. frequenceItem.append(find_frequent( candidate, dataset, num))
162. if frequenceItem[num] == []:
163. frequenceItem.pop(num)
164. break
165. num = num+1
166. '''
167. 打印出频繁项集
168. '''
169. for each in frequenceItem:
170. print each

目录位置：

编译结果：

事务集合