Apriori算法进行数据关联分析

从大规模数据集中寻找物品间的隐含关系被称作关联分析或者关联规则学习。这里的主要问题在于，寻找物品的不同组合是一项十分耗时的任务，所需的计算代价很高，蛮力搜索方法并不能解决这个问题，所以需要用更智能的方法在合理的时间范围内找到频繁项集。

为了快速明确概念，从例子出发，现在面对一沓超市购物单，我们要从中分析出哪些物品与哪些物品的关联度特别高，换句话说，当顾客买了商品A后，有多大的几率会购买B商品。通过关联分析可以帮助超市摆放不同商品之间就有了隐形的规则，比如葡萄酒旁边摆着尿布明显提升了两者的销量。

a.解释几个概念

1、数据对象：

假如对超市购物单进行分析，用0，1，2，3代替一种物品，列表如[[1,2],[1,3,0],[0,1],[0,2],[1,2,3,0]]就是一组由5个购物单组成的数据对象，其中每个子列表代替一个购物单（如[1,2]），目标就是分析通过以上的数据分析每种物品的关联关系。

2、支持度定义

支持度是衡量某个物品或物品组合是否频繁的有效指标，计算公式为

支持度=该物品或物品组合出现次数/总购物单数

3、可信度定义

可信度是衡量两个物品或物品组合之间的关联程度的有效指标

如衡量A与B的关联程度 A->B，简单理解就是买了A的顾客会不会买B的关联率

可信度=同时包含AB的支持度/A的支持度（{A,B}/{A}）

b.创建频繁项集的apriori算法

1、什么是频繁项集？简单理解就是满足它的支持度大于最小支持度的集合，比如集合[1,2]的支持度是0.8，它大于最小支持度是0.7，那么它就是一个频繁项集，由这样的频繁项集组合而成的集合，也可以大体理解为这个项目的所有频繁项集的集。那么超市购物单这个频繁项集有多少呢？假如我们只有{0，1，2，3}这四个商品，那么一共有15种，具体见下图。

发现什么不爽的事了吗？那就是仅仅4个商品就有15种集合，假如5种商品那就是31种集合，商品数越多带来的集合数越大，就会影响计算机计算性能了。这里apriori算法的作用就来了。Apriori原理是说如果某个项集是频繁的，那么它的所有子集也是频繁的。更常用的是它的逆否命题，即如果一个项集是非频繁的，那么它的所有超集也是非频繁的。我们记住最后一句话，假如[2,3]是非频繁的话，那么就可以直接排除{0，2，3}，{1，2，3}，{0，1，2，3}等集合了。具体的程序怎么解释这个算法呢，就像上图一样，一层一层地计算是否频繁集，下一层频繁集来自于上一层频繁集的合并，具体实现见下面代码。

from numpy import *
def dataset():
    return [[1,3,4],[2,3,5],[1,2,3,5],[2,5]]
dataset=dataset()
def createC1(dataset):
    sub=[]
    for line in dataset:
        for i in line:
            if [i] not in sub:
                sub.append([i])
    sub.sort()
    return map(frozenset,sub)
 
def scanD(D,C1,minsupport=0.7):
    ssdict={}
    L=[]
    supportData={}
    for tid in D:
        for i in C1:
            if i.issubset(tid):
                if i not in ssdict:
                    ssdict[i] = 1
                else:
                    ssdict[i] += 1
    num=float(len(D))
    for key in ssdict:
        support=ssdict[key]/num
        if support >= minsupport:
            L.insert(0,key)
            supportData[key] = support
    return L,supportData
 
def apriorizuhe(lk,k):
    lenlk=len(lk)
    readlist=[]
    for i in range(lenlk):
        for j in range(i+1,lenlk):
            L1=list(lk[i])[:k-2];L2=list(lk[j])[:k-2]
            if L1 == L2:
                readlist.append(lk[i]|lk[j])
    return readlist
 
def main(dataset,minsupport=0.7):
    D=map(set,dataset)
    C1=createC1(dataset)
    L,supportData=scanD(D,C1,minsupport)
    L=[L]
    k=2
    while(len(L[k-2])>0):
        ck=apriorizuhe(L[k-2],k)
        L1,supportdata=scanD(D,ck,minsupport)
        L.append(L1)
        supportData.update(supportdata)
        k += 1
    return L,supportData

解析apriorizuhe函数实现过程：假设以上都是满足最小支持度的频繁项集，从第一层到第二层的计算，依据apriorizuhe函数的过程，先找前k-2数，第一层前k-2数是空集，那么第一层所有的频繁项集都可以排列组合进行合并成第二层。但是到了第二层，前k-2个数相等的只有{0,1}和{0,2}了，所以只能这俩合并，减少了多余计算。根据apriori算法原则，不符合最小支持度的频繁项集在计算支持度时直接被过滤了，所以能进行这步运算的都是过

滤完符合最小支持度的频繁项集。

c.关联规则apriori进行关联分析

频繁项集已经搭建好了，接下来才是数据挖掘的主场部分，开启挖掘机模式。为了简洁地表达挖掘方式，这里用一个频繁项集{0，1，2，3}作为示例。我们依旧用遍历的方法计算所有符合最小可信度的关联关系，与计算频繁项集一样，挖掘依然采用分层方式，见下图。

从图中可以发现：假设规则{0,1,2} ➞ {3}并不满足最小可信度要求，那么就知道任何左部为{0,1,2}子集的规则也不会满足最小可信度要求。如果{0,1,2}➞{3}是一条低可信度规则，那么所有其他以3作为后件（箭头右部包含3）的规则均为低可信度的。当然这两条规则是重复的，我们按照第二条规则编写代码（只用可用后件的并集或‘子集’）。

def generateRules(L,supportData,minconf=0.7):  #minconf为可信度
    bigrulelist=[]   #新建列表用于储存关联信息
    for i in range(1,len(L)):   #从第二个开始遍历每一个由频繁项集组成的列表
        for freqset in L[i]:   #从列表里遍历每一个频繁项集
            H1=[frozenset([item]) for item in freqset]   #对频繁项集里的每个项提出来化为frozenset的形式储存在列表中，如[frozenset([1]),frozenset([2])]
            print 'H1:',H1
            if (i > 1):   #因为第二行的频繁项集里的项都只有2个，所以选择大于二行的进行迭代求解，第一行只有一个直接忽略
                H1=clacconf(freqset,H1,supportData,bigrulelist,minconf)   #先算第二层匹配
                rulesfromconseq(freqset,H1,supportData,bigrulelist,minconf)              
            else:
                clacconf(freqset,H1,supportData,bigrulelist,minconf)   #直接求每个频繁项作为后项的可信度，并保留可信度符合要求的项
    return bigrulelist
 
def clacconf(freqset,H,supportData,bigrulelist,minconf):   #输入频繁项集如frozenset([0,1])，H值作为后项，形式如[frozenset([0]),frozenset([1])]
    returnlist=[]
    for conseq in H:   #对频繁项集里的每个项都假设是后项，计算该可信度
        a=supportData[freqset]/supportData[freqset-conseq]
        if a >= minconf:   #若该可信度符合要求，则输出该后项
            print freqset-conseq,'-->',conseq, 'conf:',a
            bigrulelist.append((freqset-conseq,conseq,a))
            returnlist.append(conseq)
    return returnlist
    
def rulesfromconseq(freqset,H,supportData,bigrulelist,minconf):   #当频繁项集的内容大于1时，如frozenset([0,1,2,3]),其H值为[frozenset([0]),frozenset([1]),...frozenset([3])]
    if len(H) == 0:   #如果上一层没有匹配上则H为空集
        pass
    else:
        m=len(H[0])   #计算H值的第一个值的长度
        if (len(freqset) > (m+1)):   #若freqset的长度大于m+1的长度，则继续迭代
            hmp=apriorigen(H,m+1)   #将单类别加类别，如{0,1,2}转化为{0,1},{1,2}等
            print 'hmp:',hmp
            hmp=clacconf(freqset,hmp,supportData,bigrulelist,minconf)   #计算可信度
            if (len(hmp) > 1):   #如果后项的数量大于1，则还有合并的可能，继续递归
                rulesfromconseq(freqset,hmp,supportData,bigrulelist,minconf)