首页
学习
活动
专区
工具
TVP
发布

关联规则apriori算法的python实现

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

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

环境 ubuntu 13.4 python 2

import itertools

import copy

'''

定义全局变量k,即支持度计数k,此k也可以在运行程序之前输入,简单改动即可

'''

k = 2

'''

存储频繁项集的列表

'''

frequenceItem = []

'''

从txt文件dataset.txt里获取事务集

'''

def getDataSet(args):

f = open(args,'r')

source = f.readlines()

f.close()

dataset = []

for line in source:

temp1 = line.strip(\n')

temp2 = temp1.split(',')

dataset.append(temp2)

return dataset

'''

初步扫描事务集,从事务集里获取候选1项集

方法的基本思路是:

定义一个集合tmp,将事务集的第一项作为tmp的初始集合

然后扫描事务集,将不在tmp里的数据项加入tmp中

'''

def find_item( dataset ):

length = len(dataset)

for i in range(0, length):

if i == 0:

tmp = set(dataset[i])

tmp.update(set(dataset[i]))

candidate=list(tmp)

candidate.sort()

return candidate

'''

从候选项集里找出频繁项集,其中num代表频繁num+1项集

如num为0的为从候选1项集里找出频繁1项集

方法基本思路:

1、定义一个支持度列表count

2、对于每一个候选项,依次扫描事务集,如果该项出现在事务集中就将该项对应的count+1、定义一个支持度列表count+1

3、将每一项的count和k(支持度计数)进行比较,将count小于k的项剔除

'''

def find_frequent( candidate, dataset, num):

frequence = []

length = len(candidate)

count = []

for i in range(0, length):

count.append(0)

count[i] = 0

if num == 0:

'''

其实不管num为0还是别的值算法应该是一样的,但是由于程序实现上的问题

num为0的时候选项集是一维列表,其它的时候,候选项集是二维列表,

毕竟只是自己写着玩的,python还不熟,牵一发而动全身,懒得改了

'''

child= set([candidate[i]])

else:

child = set(candidate[i])

for j in dataset:

parent = set(j)

if child.issubset(parent):

count[i] = count[i]+1

for m in range(0, length):

if count[m] >= k:

frequence.append(candidate[m])

return frequence

'''

先验定理,剪枝掉不必要的候选n项集

方法思路:

1、依次取出候选项集里的项

2、取出n项集里的n-1项子集

3、如果所有的n-1项集不都都是频繁n-1项集的子集,则删除该候选项集

'''

def pre_test(candidate, num,frequence):

r_candidate = copy.deepcopy(candidate)

for each in candidate:

for each2 in itertools.combinations(each,num):

tmp= (list(each2))

tag = 0

for j in frequence:

if num == 1:

if (tmp[0] == j):

tag = 1

break

else:

if tmp == j:

tag = 1

break

if tag == 0:

r_candidate.remove(each)

break

return r_candidate

'''

通过频繁n-1项集产生候选n项集,并通过先验定理对候选n项集进行剪枝

方法思路:

1、如果是频繁1项集,则通过笛卡尔积产生频繁2项集

2、如果不是频繁一项集,采用F(k-1) * F(k-1)方法通过频繁n-1项集产生候选n项集

注:F(k-1) * F(k-1)方法在我的另一篇关联算法博客上做了理论上的简单介绍,或者也可以直接参看《数据挖掘导论》

'''

def get_candidata( frequence, num ):

length = len(frequence)

candidate =[]

if num == 1:

for each in itertools.combinations(frequence,2):

tmp = list(each)

tmp3 = []

tmp3.append(tmp[0])

tmp3.append(tmp[1])

candidate.append(tmp3)

else:

for i in range(0,length-1):

tmp1 = copy.deepcopy(frequence[i])

tmp1.pop(num-1)

for j in range(i+1, length):

tmp2 = copy.deepcopy(frequence[j])

tmp2.pop(num-1)

if tmp1 == tmp2:

tmp3 = copy.deepcopy(frequence[i])

tmp3.append(frequence[j][num-1])

candidate.append(tmp3)

candidate2 = pre_test(candidate, num, frequence)

return candidate2

'''

main程序

'''

if __name__=='__main__':

dataset = getDataSet('dataset.txt')

Item = find_item(dataset)

num = 0

frequenceItem= []

'''

通过事务集找到频繁项集,直至频繁n项集为空,则退出循环

'''

while 1:

if num == 0:

candidate = Item

else:

candidate = get_candidata(frequenceItem[num-1],num)

frequenceItem.append(find_frequent( candidate, dataset, num))

if frequenceItem[num] == []:

frequenceItem.pop(num)

break

num = num+1

'''

打印出频繁项集

'''

for each in frequenceItem:

print each

目录位置:

编译结果:

事务集合

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180821A05EWQ00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券