Python之Apriori关联分析

斑点鱼在看过《白话大数据与机器学习》关于关联分析的章节之后甚是失望，因为只有一些SQL语句去解释关联分析的支持度和置信度怎么演算，而且稍微和《机器学习实战》这本书中的频繁项集和关联规则有些不一样，个人感觉还是后一本书比较详细具体一点。

Anyway,对于这两本书，斑点鱼给到的建议是，先看《白话大数据与机器学习》，浅显易懂的掌握算法基本概念，然后再看《机器学习实战》加深对概念的理解，并且让你将文字型的伪代码转换为python code。

好的，开始进入今天的正题，说一下Apriori算法的概念、步骤和具体示例~~

code如下：

%PYTHON 2.7

from numpy import *

def loadDataSet():

return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

#生成所有单个元素的集合

def createC1(dataSet):

C1 = []

for transaction in dataSet:

for item in transaction:

if not [item] in C1:

C1.append([item])

C1.sort()

return map(frozenset, C1)#use frozen set so we

#can use it as a key in a dict

#扫描交易记录，计算所有项集支持度，D为数据集，CK为k个元素组成的集合，minsupport为最小支持度

def scanD(D, Ck, minSupport):

ssCnt = {}

for tid in D:

for can in Ck:

if can.issubset(tid):

if not ssCnt.has_key(can): ssCnt[can]=1

else: ssCnt[can] += 1

numItems = float(len(D))

retList = []#那些满足最小支持度的项集集合

supportData = {}

for key in ssCnt:

support = ssCnt[key]/numItems#计算支持度

if support >= minSupport:

retList.insert(0,key)

supportData[key] = support

return retList, supportData#所有项集的支持度的集合

############################

dataSet=loadDataSet()

dataSet

C1=createC1(dataSet)

C1

D=map(set,dataSet)#将dataSet列表变成集合

D

L1,suppData0=scanD(D,C1,0.5)

L1

suppData0

############################

%PYTHON 3

与PYTHON2.7不一样的地方

1. Python 3,returns an iterator not a list:

2。has_key方法在python2中是可以使用的，在python3中删除了。

比如：if dict.has_key(word):改为：if word in dict:

from numpy import *

def loadDataSet():

return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]

#生成所有单个元素的集合

def createC1(dataSet):

C1 = []

for transaction in dataSet:

for item in transaction:

if not [item] in C1:

C1.append([item])

C1.sort()

returnlist(map(frozenset, C1))#use frozen set so we

#can use it as a key in a dict

#扫描交易记录，计算所有项集支持度，D为数据集，CK为k个元素组成的集合，minsupport为最小支持度

def scanD(D, Ck, minSupport):

ssCnt = {}

for tid in D:

for can in Ck:

if can.issubset(tid):

if can not in ssCnt:ssCnt[can]=1

else: ssCnt[can] += 1

numItems = float(len(list(D)))

retList = []#那些满足最小支持度的项集集合

supportData = {}

for key in ssCnt:

support = ssCnt[key]/numItems#计算支持度

if support >= minSupport:

retList.insert(0,key)

supportData[key] = support

return retList, supportData #所有项集的支持度的集合

############################

dataSet=loadDataSet()

dataSet

C1=createC1(dataSet)

C1

D=list(map(set,dataSet))#将dataSet列表变成集合

D

L1,suppData0=scanD(D,C1,0.5)

L1

suppData0

############################

##组织完整的Apriori算法

#函数aprioriGen()的输入参数为频繁项集列表Lk与项集元素个数k，输出为Ck。举例来说，

#该函数以、 、 作为输入，会生成、 以及。

def aprioriGen(Lk, k): #creates Ck

retList = []

lenLk = len(Lk)

for i in range(lenLk):

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

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

L1.sort(); L2.sort()

if L1==L2: #if first k-2 elements are equal

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

return retList

##首先使用aprioriGen()来创建Ck，

#然后使用scanD()基于Ck来创建Lk。 Ck是一个候选项集列表，

#然后scanD()会遍历Ck，丢掉不满足最小支持度要求的项集 。

#Lk列表被添加到L，同时增加k的值，重复上述过程。

#最后，当Lk为空时，程序返回L并退出。

def apriori(dataSet, minSupport = 0.5):

C1 = createC1(dataSet)

D =list(map(set, dataSet))

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

L = [L1]

k = 2

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

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

Lk, supK = scanD(D, Ck, minSupport)#scan DB to get Lk

supportData.update(supK)

L.append(Lk)

k += 1

return L, supportData

##################################################

L,suppData=apriori(dataSet)

L

###关联规则的生成

##函数最后要生成一个包含可信度的规则列表，后面可以基于可信度对它们进行排序。该函数遍历L中的每一个频繁项集并对每个频繁项集创建只包含单个元素集合的列表H1。

def generateRules(L, supportData, minConf=0.7): #频繁项集列表、包含那些频繁项集支持数据的字典、最小可信度阈值

bigRuleList = []

for i in range(1, len(L)):#only get the sets with two or more items

for freqSet in L[i]:#freqSet为频繁项集

H1 = [frozenset([item]) for item in freqSet]#如果从集合开始，那么H1应该是[,,]

if (i > 1):

rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)#之后创建的函数

else:

calcConf(freqSet, H1, supportData, bigRuleList, minConf)#之后创建的函数

return bigRuleList

#函数会返回一个满足最小可信度要求的规则列表，为了保存这些规则，需要创建一个空列表prunedH。接下来，遍历H中的所有项集并计算它们的可信度值。可信度计算时使用supportData中的支持度数据。

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

prunedH = [] #create new list to return

for conseq in H:

conf = supportData[freqSet]/supportData[freqSet-conseq] #计算可信度P(A|B)/P(A)

if conf >= minConf:

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

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

prunedH.append(conseq)

return prunedH#满足最小置信度的B的集合

#该函数有2个参数：一个是频繁项集，另一个是可以出现在规则右部的元素列表H

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

m = len(H[0])#函数先计算H中的频繁集大小m

if (len(freqSet) > (m + 1)): #try further merging

Hmp1 = aprioriGen(H, m+1)#aprioriGen()来生成H中元素的无重复组合，该结果会存储在Hmp1中，这也是下一次迭代的H列表。

Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)#Hmp1包含所有可能的规则。可以利用calcConf()来测试它们的可信度以确定规则是否满足要求。

if (len(Hmp1) > 1): #如果不止一条规则满足要求，那么使用Hmp1迭代调用函数rulesFromConseq()来判断是否可以进一步组合这些规则。

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

###################################################

L,suppData=apriori(dataSet,minSupport=0.5)

rules=generateRules(L,suppData,minConf=0.7)

一起学习的小伙伴如果有什么想法或者意见，欢迎沟通~