频繁模式挖掘-Apriori算法

DM实验，写的比较二，好多情况还没有考虑，后续有时间会修改。

开始的时候数据结构没设计好导致写到后面费了很大的劲、不过还好python的列表有起死回生的功效、、、

数据集：database.txt

I1,I2,I5
I2,I4
I2,I3
I1,I2,I4
I1,I3
I2,I3
I1,I3
I1,I2,I3,I5
I1,I2,I3

#coding=utf-8
"""
    author:messiandzcy
    apriori.py
    date:2014.12.3
"""
#申请存数据库的矩阵，方便以后遍历
def matrix(num_of_transactions,num_of_items):
    mat = [['#' for y in range (num_of_items+1)]
              for x in range(num_of_transactions+1)]
    return mat

#输出数据库矩阵调试
def printf(mat,rows,cols):
    for i in range(rows):
        for j in range(cols):
            print mat[i][j],
        print
        
#读入文件，将数据库存到列表data里，并格式化输出
def ReadFile():
    filename = r'database.txt'
    try:
        fp = open(filename,"r")
        print "Reading File '%s'..." % filename
        print "%-10s%-10s" % ("TID","Items")
        pos = 1     #pos记录事务数（行数）
        MAX_j = 0 #记录项的最大宽度（列数）
        data = matrix(15,10) #最多15个事务,10个项
        for line in fp:
            string=line.strip("\n")
            print "%-10d%-10s" % (pos,string)
            j = 1   #记录项的宽度（列数）
            for items in string.split(","):
                data[pos][j]=items  #向数据库插入数据
                j += 1
            if j>MAX_j:MAX_j=j
            pos += 1
        fp.close()
        #print "pos=%d,j=%d" % (pos,MAX_j)
        #printf(data,pos,MAX_j)
        print "Read File Success!\n"
        return (data,pos,MAX_j)
    except IOError:
        print "Read File -->'%s' Failed!" % filename
        print "File --> '%s' does not exist!" % filename
    except:#other exceptions
        print "Other Exceptions!"
        
#将数据库转换成垂直格式的,计数时会很方便
def vertical(mat,rows,cols):
    #扫描一遍数据库并去掉重复的项
    lst = []    #项与整数的一一对应
    for i in range(rows):
        for j in range(cols):
            lst.append(mat[i][j])
    lst=list(set(lst))  #去重
    #print len(lst)
    #再扫描一遍数据库,生成新的vertical数据库
    I = [[],[],[],[],[],[],[],[],[],[]] #最多支持10个项，每个项对应一个列表
    for i in range(rows):
        for j in range(cols):
            if mat[i][j]!="#":I[lst.index(mat[i][j])].append(i)
    #print lst
    #print I
    return (lst,I)

#根据项集列表扫描数据库并返回支持计数
def count(itemSet,lst,I):
    if len(itemSet)==1:return len(I[lst.index(itemSet[0])]) #1-项集的情况
    x = itemSet[0]
    ggg =I[lst.index(x)]    #获得首元素对应的数据库I的列表
    #求多个集合的交
    for y in itemSet:
        ggg = list(set(ggg)&set(I[lst.index(y)]))
    #print ggg
    return len(ggg) #最后交集元素的个数即是支持度计数
    
#运行apriori算法,lst-->记录去重后的项集列表,I-->记录与lst对应索引的vertical数据库
def apriori(lst,I,min_sup):
    print "Start to Run Apriori!"
    #print lst
    #print I
    d=[[] for i in range(15)]    #假定每次自连接产生的项集个数不超过15
    num = 0 #记录项集个数
    for x in lst:
        if x!='#':
            d[num].append(x)    #构造初始项集d,第一次比较特殊,从第二次开始要通过自连接来构造
            num += 1
    #print count(["I1","I2"],lst,I)
    #格式化输出初始候选项C1,单独处理,不进循环
    print "\nCandidate:#1"
    print "%-10s%-10s" % ("Items","count")
    for i in range(15): #i是项集的序号
        if d[i]!=[]:
            print "%-10s%-10d" % ("".join(d[i]),count(d[i],lst,I))
    #print d
    iters=1 #迭代次数
    while iters<=7:
        #开始迭代,第一步,Ck-->Lk,根据最小阈值min_sup来剪枝
        print "\n#L%d" %iters
        print "%-10s%-10s" % ("Items","count")
        for i in range(15):
            if len(d[i])==iters:    #在频繁k项集中查找
                if count(d[i],lst,I)>=min_sup:
                    print "%-10s%-10d" % (",".join(d[i]),count(d[i],lst,I))
                else:d[i]=[]    #否则剪枝   
        #print d
        #迭代第二步,自连接Lk-->Ck+1
        new = []
        for i in d:
            if len(i)==iters:new.append(i)  #把频繁k项集Lk先挑出来，按顺序装在列表new中
        #print "new="
        #print new
        if len(new)==0:break #若已经找不到符合条件的频繁k项集，终止循环！
        
        if iters==1:    #第一次执行完全连接操作
            num = 0
            for i in range(len(new)):   #i,j是下标序号   
                for j in range(i+1,len(new)):
                    d[num]=[new[i][0],new[j][0]]    #自连接后更新项集列表d
                    num += 1
        else:           #否则执行真正的自连接操作
            tmp = []
            for i in range(len(new)):   #对于每个项集
                #print new[i][0:iters-1]
                if new[i][0:iters-1] not in tmp:    #去重
                    tmp.append(new[i][0:iters-1])   #把每个项集的前k-1项收集起来-->tmp
            #print "tmp="
            #print tmp
            num = 0
            for j in range(len(tmp)):   #对于每个前k-1项
                hehe = []
                for i in range(len(new)):   #扫描项集，提取出前缀和前k-1项一致的项集,后面部分-->hehe
                    if tmp[j]==new[i][0:iters-1]:hehe.append(new[i][iters-1])
                #得到hehe之后,开始做完全连接
                #print "hehe="
                #print hehe
                for m in range(len(hehe)):   #i,j是下标序号   
                    for n in range(m+1,len(hehe)):
                        #print tmp[j]+[hehe[m],hehe[n]]
                        d[num]=tmp[j]+[hehe[m],hehe[n]]    #自连接后更新项集列表d
                        num += 1
                #print "d="
                #print d
                #return 
        print "\nCandidate:#%d" % (iters+1)
        print "%-10s%-10s" % ("Items","count")
        for i in range(15): #i是项集的序号
            if len(d[i])==iters+1:
                print "%-10s%-10d" % (",".join(d[i]),count(d[i],lst,I))
        #print d
        iters += 1

#主函数
(data,pos,MAX_j)=ReadFile()
#printf(data,pos,MAX_j)
#print "pos=%d,j=%d" % (pos,MAX_j)
(lst,I)=vertical(data,pos,MAX_j)    #转换
#print lst
#print vertical
min_sup = 2     #设置最小支持度
apriori(lst,I,min_sup)