机器学习手记[4]--Apriori关联准则挖掘方法

关联规则提取主要是两个步骤

数据为：[[1,3,4],[2,5],[1,2,5]]

1 候选集的创建和频繁集提炼

首先创建C1候选集，就是{1}呀{3}呀这种size为1的项集，然后计算他们的支持度（也就是在数据集中出现的频率），以0.5的支持度为阈值（也就是数据中4个项集中至少出现了2次的C1项集），继而得到频繁C1候选集。

此后利用频繁C1候选集进行一对一组合排列，比如{1}和{3}组合为{1,3},{2}和{4}组合为{2,4}这种操作，调用CkCreate(C1Content,2)函数可以生成C2候选集，之后利用CkSelect函数，可以设置支持度阈值，提取出C2频繁集。

之后利用C2频繁集，调用CkCreate(C1Content,3)继续组合出C3候选集。。。组合后提取。。。生成C3频繁集。

总之，

第一步的意思就是自低向上不断的组合，而且是size为n的，生成size为n+1的频繁集。

通俗可以说就是根正苗红这种，只有底层的根正苗红，有很高的出镜率的（就是支持度），才能够生成上一层。然后上一层苗红的再生成规模更大的频繁集。到最后我们生成的所I有的频繁集都是正统官家子弟。

需要注意的是组合的这个过程，需要排序，排序后size为n的频繁集只有在前n-1项相同的情况下才进行组合。只有这样size为n的才能生成size为n+1的，而不是n+2或n+3等等的集子，举个例子。我们用size为3的频繁集生成size为4的频繁集（尽管在这个数据集里面我们没遇到），两个频繁集set为{1,4,2}{1,5}

首先排序，将两个集子弄清晰了，频繁集为{1,3}和{1,4} 因为他们前n-1项也就是前2项是相同的所以这样才能组合生成size为3的集合，{1,4} ，而如果排序后集子分别是是{1.3,9}和{1,4} 只有第一项才相似，这个时候就生成的是{1,9}这种size为5的集子，这不是我们算法所要的，因此舍弃。

??

2 依据候选集中集合和子集的关系，提取关联规则

通过上述的方式我们得到各级size的频繁项集，下面要做的就是以置信度为阈值，生成关联规则。

上面可以发现所有的集子都是根正苗红的，都是频繁的，这个频繁是全局频繁。我们现在要做的关联，实质上就是局域频繁，还是统计频率，实质没有变.怎么说?

频繁集A的频率=频繁集A在总频繁集中出现次数 / 总频繁集的次数

频繁集A相对于B的置信度则=频繁集A在频繁集B中出现次数 / 频繁集B的次数

具体怎么做呢？具体就是先获取到频繁集的集合，也即{ 频繁集1，频繁集2，频繁集3,....}

然后从size为2的频繁集开始，进行拆分，拆分出很多自己，size为2的就是拆出来size为1.，size为3的拆出来size为1和2，以此类推。

这样我们就计算被拆的大集合A的出现频率 /?拆出来的子集B（也是频繁集）的出现频率，这就是置信度了，如果置信度大于阈值，那么就说明B-->A

而A中包含了B自己，因此可以理解为B--->A-B (A-B也即A排除B集合后剩下的集合)

具体代码函数解析如下
//第一步---加载原始数据集
loadDataSet() ?#其实就是[[1,5]]这个数据，包含size为2或3的项集


//第二步---创建候选集
C1Create(dataSet): ?#创建size为1的候选集，同时按照minSupport=0.5为支持度的阈值提取C1候选集
CkCreate(CP1Content,k): #根据C1候选集C1Content，和指定的k，创建size为k的候选集
CkSelect(dataSet,CkContent,minSupport=0.5): #按照minSupport为0.5的支持度阈值对候选集进行筛选，提取频繁集


//第三部---规则提取
getRelation(ContentList,SupportDict,brl,minCredit=0.7 ): //根据提取频繁集生成规则
setProcess(Set,brl):?
?

# -*- coding: utf-8 -*-
import collections

#------------加载数据集------------------------------------------------------------------
def loadDataSet():
    return [[1,5]]
   

#-----------频繁集提取函数-----------------------------------------------------------------   

# 创建C1候选集
def C1Create(dataSet):
    minSupport=0.1
    C1Dict={}
    C1Content=[]
    for itemset in dataSet:
        for item in itemset:
            if item not in C1Dict:
                C1Dict[item]=1
            else:
                C1Dict[item]+=1
    C1Support=[ C1Dict[k]/float(len(dataSet)) 
                for k in C1Dict if (C1Dict[k]/float(len(dataSet)))>=minSupport]  
    C1Content=[ [k]                           
                for k in C1Dict if (C1Dict[k]/float(len(dataSet)))>=minSupport]
    C1SupportDict={frozenset([k]):C1Dict[k]/float(len(dataSet)) 
                    for k in C1Dict if (C1Dict[k]/float(len(dataSet)))>=minSupport}
    return  C1Content,C1SupportDict

# 根据C1候选集，创建Ck候选集
def CkCreate(CPreContent,k):#k,如果想生成粒度为2的项集合，k=2
    if(len(CPreContent[0])<k):
        length=len(CPreContent)
        CNewContent=[]
        for i in range(length):
            for j in range(i+1,length):
                if (  sorted(CPreContent[i])[:-1]== sorted(CPreContent[j])[:-1]  ):                     
                    CNewContent.append(set(CPreContent[i])| set(CPreContent[j]) )   
        return CkCreate(CNewContent,k)
    else:
        return map(list,CPreContent)
    #返回setList
    #起始条件：C1Content
    #终止条件：粒度
    #步进条件：一个贴一个

# 提取Ck候选集
def CkSelect(dataSet,minSupport=0.5):
    #input setting
    dataLength=float(len(dataSet))
   
    #output setting
    CkDict=collections.defaultdict(lambda:0)
    for dataItemset in dataSet:
        for CkItemset in CkContent:
            if set(CkItemset).issubset(set(dataItemset)):
                CkDict[frozenset(CkItemset)]+=1  
 
    C1SelectedContent=[ set(k) 
                        for k in CkDict if (CkDict[k]/dataLength)>=minSupport]
    C1SelectedSupport=[ CkDict[k]/dataLength 
                        for k in CkDict if (CkDict[k]/dataLength)>=minSupport]
    C1SelectedSupportDict={ k:CkDict[k]/dataLength 
                            for k in CkDict if (CkDict[k]/dataLength)>=minSupport}

    return map(list,C1SelectedContent),C1SelectedSupportDict


   


#----------------关联规则提取函数------------------------------------------------------------

#获取关联规则方法
def getRelation(ContentList,minCredit=0.7 ):
    for SetList in ContentList:
        if len(SetList[0])>0:
            for Set in SetList:
                setProcess(Set,brl)
 
#对单个项集进行处理   
def setProcess(Set,brl):  #[2,5] 长度3
    length=len(Set)  #项集的规模 2    
    C1Content=[ [k] for k in Set]  
    splitLidu=length/2
    for i in range(1,splitLidu+1): #长度3，切分粒度为1-2，切分范围  
        if (i==1):
            for oneSet in C1Content:
                credit=SupportDict[frozenset(Set)]/SupportDict[frozenset(oneSet)]
                if (credit>0.7):
                    brl.append(
                    (frozenset(oneSet),frozenset(Set)-frozenset(oneSet),credit))
        else:
            CkContent=CkCreate(C1Content,i)
            for iSet in CkContent:
                credit=SupportDict[frozenset(Set)]/SupportDict[frozenset(iSet)]                
                if (credit>0.7):
                    brl.append(
                    (frozenset(iSet),frozenset(Set)-frozenset(iSet),credit))

#--------------------执行函数--------------------------------------------------------
def run():
    dataSet=loadDataSet()  #加载数据[[1,5]]
    C1Content,C1SupportDict=C1Create(dataSet)#C1候选集（提炼后）创建

    ContentList=[]
    ContentList.append(C1Content)
    SupportDict={}
    SupportDict.update(C1SupportDict) #加载候选集和支持度信息
  
    MAX_ELEM_SIZE=4; #最长的项集size为4
    for k in range(2,MAX_ELEM_SIZE+1): #k从2-3 创建候选集
        CkContent=CkCreate(C1Content,k)  #候选集创建
        CkSelected,CkSupport=CkSelect(dataSet,CkContent)#候选集提炼
        ContentList.append(CkSelected)#添加新候选集
        SupportDict.update(CkSupport) #添加新候选集的支持度数据

    relationRules=[]
    getRelation(ContentList,SupportList,relationRules,0.7)

    return ContentList,relationRules