关联规则apriori算法的python实现

cady 2018-08-20

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

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

环境 ubuntu 13.4 python 2


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

目录位置:

关联规则apriori算法的python实现

编译结果:

关联规则apriori算法的python实现

事务集合

关联规则apriori算法的python实现