基于Apriori的数据关联分析 | 工业数据分析 | 冰水数据智能专题 | 4th
基于Apriori的数据关联分析 | 工业数据分析 | 冰水数据智能专题 | 4th
背景
工业数据中的相关性分析是开展工业数据分析的基础性分析，决定数据分析的优先级，通过支持度和可信度来定义发现数据之间存在的关系。在状态参数列表中，可能存在单一参数组成的频繁项集，当然也存在两个以及两个以上的参数组成的频繁项集。而在计算一个频繁项集的支持度时，通常需要遍历所有的参数列表求得，对于列表数目 较少的情况该方法无疑是没问题的，但当列表数目成千上万时，计算量过大，这种方法势必是不适用的。
那么如何解决上述问题呢，Apriori 原理可以解决。Apriori 原理是说如果某个项集是频繁的，那么它的所有子集势必也是频繁的。这个原理从表面上看没什么大用，但是反过来，如果一个项集是非频繁项集，那么它所对应的超集就全都是非频繁项集。这样在确定了一个项 集是非频繁项集了之后，它所对应的超集的支持度我们就可以不去计算了，这在很大程度上 避免了项集数目的指数增长，可以更加合理的计算频繁项集。
Apriori 算法
Apriori 算法是用来发现频繁项集的一种方法。Apriori 算法的两个输入参数分别是最小支持度和数据集。该算法首先生成所有单个物品的项集列表，遍历之后去掉不满足最小支持度要求的项集；接下来对剩下的集合进行组合生成包含两个元素的项集，去掉不满足最小支 持度的项集；重复该过程直到去掉所有不满足最小支持度的项集。
首先采用 python 生成所有的单个物品所对应的项集，并构建一个得到频繁项集的函数， 代码如下：
# -*- coding: cp936 -*- ''' Apriori 算法 Ben 2015.09.28 ''' #coding:utf-8 from numpy import *
def loadData():
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)
def scanD(D,Ck,minSupport):
ssCnt = {} for tid in D:
for can in Ck:
if can.issubset(tid):#判断 tid 是否在 can 中
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
对上述代码进行测试：
#test dataSet = loadData()
c1 = createC1(dataSet)
D = map(set,dataSet) L1,supportData = scanD(D,c1,0.5)
print L1 print supportData
结合构建的单个参数项集判断上述代码是可用的。据此结合之前的分析构建完整的算法， 代码如下：
#构建多个参数对应的项集
def aprioriGen(Lk,k):
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:
retList.append(Lk[i]|Lk[j]) return retList
def apriori(dataSet,minSupport = 0.5):
C1 = createC1(dataSet)
D = 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) supportData.update(supK)
L.append(Lk) k += 1
return L,supportData
这样就对得到频繁项集的思想进行了实现，下面验证： dataSet = loadData() minSupport = 0.5 a,b = apriori(dataSet,minSupport) print a print b 结果为所有频繁项集以及其所对应的支持度，符合预期。
频繁项集可以使用 Apriori 算法寻找，当然下来就是要找出关联规则了。我们知道，假 设有一个频繁项集，它们之间就有可能有一条关联规则，即可以表示为："...—>..."，但反过 来并不一定成立（其中箭头左边对应的集合为前件，箭头右边对应的集合为后件）。
可信度
在上一节，我们使用最小支持度来量化频繁项集，对应的，采用可信度来量化关联规则。 其中一条规则 p—>H 的可信度定义为：
support(P|H)/support(P)，为找到其中的关联规则，我 们可以先生成一个可能的规则列表，然后测试每条规则的可信度，结合可信度的最小要求， 得到关联规则。同寻找频繁项集类似，我们可以为每个频繁项集产生许多关联规则，这样就 会有很多的关联规则产生。
结合 Apriori 原理，如果某条规则不满足最小可信度要求，那么 该规则的所有子集也就不满足最小可信度要求，据此我们可以减少需要测试的规则数目，简化问题。
寻找关联规则的思想是：从一个频繁项集开始，创建一个规则列表，首先将规则的右边 限定为一个元素，对这些规则进行测试，接下来合并剩下的规则来创建一个新的规则列表， 规则的右边限定为两个元素，就这样一步一步实现，代码如下：
#使用关联规则生成函数
def generateRules(L,supportData,minConf = 0.7):
bigRuleList = []
for i in range(1,len(L)):
for freqSet in L[i]:
H1 = [frozenset([item]) for item in freqSet]
if (i > 1): 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:
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,br1,minConf = 0.7): m = len(H[0])
if (len(freqSet)>(m + 1)):
Hmp1 = aprioriGen(H,m+1)
Hmp1 = calcConf(freqSet,Hmp1,supportData,br1,minConf) if (len(Hmp1) > 1): rulesFromConseq(freqSet,Hmp1,supportData,br1,minConf)
接下来对上述的程序进行测试：
#test dataSet = loadData() minSupport = 0.5 L,suppData = apriori(dataSet,minSupport)
rules = generateRules(L,suppData,minConf = 0.5) print rules
上述程序的结果表明该算法在小数据集中可以实现，其中更换可信度阈值 minConf 可以 获得不同的关联规则。