Apri 算法 Python 实现

yorknong

#!C:/Python27/python.exe
#coding=gbk
import sys
__author__ = "junfeng_feng"
"""Python实现Apri算法
input:数据文件名 最小支持度
ouput:所有频繁项集  支持度
Usage:python Apri.py filename min_surpport
Exampe: python Apri.py data.txt 2
3点说明
1、使用Python不到70行的代码，简洁完整的实现Apri算法
2、使用内存存放数据(Python会做相应大文件的优化)
3、代码易读，易理解
存在的问题：
1、超大的文件，处理将很慢
2、原始的apri，没有优化
data.txt文件内容
ACD
BCE
ABCE
BE
"""
#生成候选集C1
#return：字典key=item;value=item出现的次数
def getC1(srcdata):
c1 = {}
for transaction in srcdata:
for item in transaction:
key = frozenset(set([item])) #frozenset才可以作为字典的key
#计数item
if key in c1:
c1[key] = c1[key] + 1
else:
c1[key] = 1
return c1
#return： 满足最小支持度的候选集
def getL(c, supct):
# 删除小于最小支持度的item
for key in [item for item in c if c[item] < supct]:
del c[key]
return c
#根据上一个L产生候选集C
#扫描源数据，计数item
def getnextcandi(preL, srcdata):
c = {}
for key1 in preL:
for key2 in preL:
if key1 != key2:
# preL 和 preL 生成笛卡尔积
key = key1.union(key2)
c[key] = 0
#计数item
for i in srcdata:
for item in c:
if item.issubset(i):
c[item] = c[item] + 1
return c
# Apriori 算法
def Apriori(filename, supct):
#读取数据文件
#文件格式:一行一个事务,一个事务的各个元素以Tab(\t)分隔
srcdata = [line.strip().split("\t") for line in file(filename)]
c = getC1(srcdata)
L = {}
while True:
temp_L = getL(c, supct)
if not temp_L:
break
else:
L = temp_L
#由上一个L，产生候选集c
c = getnextcandi(L, srcdata)
return L
if __name__ == "__main__":
if len(sys.argv) == 3:
#Usage:   apri.py filename surpport
print Apriori(sys.argv[0], sys.argv[1])
else:
#for example
print Apriori("awk.txt", 8)