关联规则分析Apriori

关联分析用来寻找事务之间的相关性，这些关系主要有两种形式，频繁项目集或者关联规则。

关联分析涉及的术语和指标：

术语

   频繁项目集合（frequent item ）经常出现在一块的物品的集合；

   关联规则（association rules），暗示两种物品之间可能会存在很强的关系。

指标

支持度：数据集合中包含该项集的记录比例。（集合出现概率p(a)）

可信度：支持度（ab）/支持度(a) 。（集合的条件概率p(ab)/p(a)）

重要定理：

1.0 如果一个项目集是频繁的那么它的子集也是频繁的 

2.0如果项目abc对d的支持度不够那么，那么ab>-cd，ac>-bd也是不够的

Apriori算法图解：

0,1,2,3表示4种不同的商品，下面是他们可能的集合

可能的商品集合

1.0 关于支持度的 

Apriori:如果一个项目集合是频繁的，那么它的子集也是频繁的

反过来说：如果一个项目集是非频繁的，那么它的所有超集也是非频繁的 

（如果p(a)<0.5，那么p(ab)一定小于0.5），见下图23组合被排除，灰色的组合也将被排除

非频繁

2.0关于置信度 

对于集合{a,b,c,d}而言，如果abc，对d的支持度是不够的那么，ab对cd，ac对bd，a对bcd的支持度也是不够的。

通过这两种算法可以排除大量的，非候选项目，从而减少运算量。

--------py代码实现

#coding: utf-8

import  xlrd ,xlwt

from  pprint  import  pprint

import chardet

data=xlrd.open_workbook(r"C:\Users\mei-huang\Desktop\data1.xlsx")

try:

    table=data.sheets()[1]  #通过索引顺序获取

    # table = data.sheet_by_index(0)  # 通过索引顺序获取

    # table = data.sheet_by_name(u'Sheet1')  # 通过名称获取

except:

    print("no sheet  in %s named  sheet1"%data)

print(table.nrows,table.ncols)

# print(table.cell(2,3).value)

dataset=[]

for  n  in  range(table.nrows):

    col=[]

    for  c in range(table.ncols):

        if  not  len(table.cell(n,c).value)==0 :

            col.append(table.cell(n,c).value)

    dataset.append(col)

# pprint(len(dataset)，type(dataset)))

#1.1 定义函数集合 返回整个数据集的单元素集合

def createS1(Dataset):

    S1=[]

    for  a  in dataset :

        for  b  in  a :

            if  [b] not in  S1 :

                S1.append([b])

    S1.sort()

    return map(frozenset,S1)

# 1.2返回满足支持度的集合（用于构建二元集合）和集合的支持度

def  applyS1(Dataset,S1,MINsuport):

    supportS1_dir1 = {}

    for  a  in S1  :

        x=0

        for  b  in  dataset :

          if    set(a).issubset(b) :

              x+=1

              supportS1_dir1[frozenset(a)]=x

    # print(supportS1_dir1)

    supportS1_list=[]

    supportS1_dir = {}

    itemlen=len(dataset)

    for  x  ,y  in  supportS1_dir1.items():

        if  y>= MINsuport*itemlen :

            supportS1_list.append(x)

            supportS1_dir[x]=supportS1_dir1[x]/itemlen

    return supportS1_list ,supportS1_dir

# 查看返回结果

xx,yy=applyS1(dataset,createS1(dataset),0)

print(sorted(yy.items(), key=lambda e: e[1], reverse=True))

import  xlwt

book = xlwt.Workbook(encoding='utf-8', style_compression=0)

sheet = book.add_sheet('test', cell_overwrite_ok=True)

n=0

for  x,y in  yy.items():

    sheet.write(n, 1, str(x))

    sheet.write(n, 2, str(y))

    n+=1

book.save(r'e:\test1.csv')

#生成包含两个元素的集合S2

def createS2(Lk, k=1): #creates s2

    retList = []

    lenLk = len(Lk)

    for i in range(lenLk):

        for j in range(i+1, lenLk):

            #❶（以下三行）前k-2个项相同时，将两个集合合并

            # 一个k+1集合存在的话，其中每个元素都在k集合中出现

            L1 = list(Lk[i])[:k-2]; L2 = list(Lk[j])[:k-2]

            L1.sort(); L2.sort()

            if L1==L2: #如果出现共同集合就合并

                retList.append(set(Lk[i]) | set(Lk[j]))

    return retList

# xx=createS2(createS1(dataset))

# x,y=applyS1(dataset,xx,0.1)

# print(sorted(y.items(), key=lambda e: e[1], reverse=True))

def apriori(dataSet, minSupport = 0.5):

    #算出单元素的频繁项目集

    C1 = createS1(dataSet)

    D = map(set, dataSet)

    L1, supportData = applyS1(D, C1, minSupport)

    L = [L1]

    k = 2

    #计算多元素的频繁项目集合

    while (len(L[k-2]) > 0):

        Ck = createS2(L[k-2], k)

        #❷  扫描数据集，从Ck得到Lk

        Lk, supK = applyS1(D, Ck, minSupport)

        supportData.update(supK)

        L.append(Lk)

        k += 1

    return L, supportData

xx, yy = apriori(dataset, 0.0)

# print(type(yy))

# print(yy)

# print(len(yy),sorted(yy.items(), key=lambda e: e[1], reverse=True))

# # print(yy[('丹参', '黄芪', '大黄')])

#导出excel

# #生成关联规则

#主函数

def generateRules(L, supportData, minConf=0.7):  #频繁项目集，频繁项目集合字典，支持度

    bigRuleList = []

    #❶ 只获取有两个或更多元素的集合

    for i in range(1, len(L)):  #循环频繁项目集

        for freqSet in L[i]:  #频繁项目集中的元素

            # print(freqSet)

            H1 = [tuple([item]) for item in freqSet]

            # print("aa",H1)

            if (i > 1):  #频繁集的元素>2

                rulesFromConseq(freqSet, H1, supportData, bigRuleList,minConf)

            else:

                calcConf(freqSet, H1, supportData, bigRuleList, minConf)

    return bigRuleList

#判断指定的规则是否满足

def calcConf(freqSet, H, supportData, brl, minConf=0.7):

    prunedH = []

    for conseq in H:

        conseq=frozenset(list(conseq))

        conf = supportData[freqSet]/ supportData[freqSet - conseq]

        #若果找不就对变量进行顺序倒置然后再找

        if conf >= minConf:

            print (freqSet-conseq,'-->',conseq,'conf:',conf)

            brl.append((freqSet-conseq, conseq, conf))

            prunedH.append(conseq)

    return prunedH

#生成关联规则

def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7): #频繁项目集，可以出现在右侧的元素列表

    m = len(H[0])  #右侧列表第一个元素的长度

    #❷ 尝试进一步合并

    if (len(freqSet) > (m + 1)):

        #❸ 创建Hm+1条新候选规则

        Hmp1 = createS2(H, m + 1)

        Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)

        if (len(Hmp1) > 1): #递归函数

            rulesFromConseq(freqSet, Hmp1,supportData, brl, minConf)

# print(sorted(yy.items(), key=lambda e: e[1], reverse=True))

z=generateRules(xx, yy, minConf=0.1)

print(z)

#导出数据

import  xlwt

book = xlwt.Workbook(encoding='utf-8', style_compression=0)

sheet = book.add_sheet('test', cell_overwrite_ok=True)

sheet2 = book.add_sheet('test2', cell_overwrite_ok=True)

n=0

for  x in  yy.items():

    # print(x)

    sheet.write(n, 1, str(x))

    n+=1

b=0

for  y  in  z:

    sheet2.write(b, 1, str(y))

    b += 1

book.save(r'e:\test1.csv')