Apri 算法 Python 实现

#!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文件内容
A	C	D
B	C	E
A	B	C	E
B	E
"""

#生成候选集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)