Apriori算法关联分析与pyhon实现-技术方案-@大数据资讯

算法中核心性质：频繁项集的所有非空子集也必须是频繁的。逆反命题也成立：如果一个项集是非频繁的，那么所有它的超集也是非频繁。

一、Apriori算法简介：

Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。 Apriori（先验的，推测的）算法应用广泛，可用于消费市场价格分析，猜测顾客的消费习惯；网络安全领域中的入侵检测技术；可用在用于高校管理中，根据挖掘规则可以有效地辅助学校管理部门有针对性的开展贫困助学工作；也可用在移动通信领域中，指导运营商的业务运营和辅助业务提供商的决策制定。

二、挖掘步骤：

1. 依据支持度找出所有频繁项集（频度）

2. 依据置信度产生关联规则（强度）

三、基本概念

对于 A->B

①支持度： P(A ∩ B) ，既有 A 又有 B 的概率

②置信度：

P(B|A) ，在 A 发生的事件中同时发生 B 的概率 p(AB)/P(A) 例如购物篮分析：牛奶 ⇒ 面包

例子：[ 支持度： 3% ，置信度： 40%]

支持度 3% ：意味着 3% 顾客同时购买牛奶和面包

置信度 40% ：意味着购买牛奶的顾客 40% 也购买面包

③如果事件 A 中包含 k 个元素，那么称这个事件 A 为 k 项集事件 A 满足最小支持度阈值的事件称为频繁 k 项集。

④同时满足最小支持度阈值和最小置信度阈值的规则称为强规则

四、实现步骤

Apriori 算法是一种最有影响的挖掘布尔关联规则频繁项集的算法 Apriori 使用一种称作逐层搜索的迭代方法，“ K-1 项集”用于搜索“ K 项集”。

首先，找出频繁“ 1 项集”的集合，该集合记作 L1 。 L1 用于找频繁“ 2 项集”的集合 L2 ，而 L2 用于找 L3 。如此下去，直到不能找到“ K 项集”。找每个 Lk 都需要一次数据库扫描。

核心思想是：连接步和剪枝步。连接步是自连接，原则是保证前 k-2 项相同，并按照字典顺序连接。剪枝步，是使任一频繁项集的所有非空子集也必须是频繁的。反之，如果某

个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从 CK 中删除。

简单的讲， 1 、发现频繁项集，过程为（ 1 ）扫描（ 2 ）计数（ 3 ）比较（ 4 ）产生频繁项集（ 5 ）连接、剪枝，产生候选项集重复步骤（ 1 ） ~ （ 5 ）直到不能发现更大的频集

2 、产生关联规则，过程为:根据前面提到的置信度的定义，关联规则的产生如下：

（ 1 ）对于每个频繁项集 L ，产生 L 的所有非空子集；

（ 2 ）对于 L 的每个非空子集 S ，如果

P （ L ） /P （ S ）≧ min_conf

注： L-S 表示在项集 L 中除去 S 子集的项集

下面代码实现了一个简单数据集下的Apriori 算法实现：

def loadDataSet():
return [[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
 
def createC1(dataSet):# return C1 frequent item set
C1 = []
for transaction in dataSet:
for item in transaction:
if not [item] in C1:
C1.append([item])
C1.sort()
return map(frozenset,C1) # frozenset can't changed !

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 # return result list and support data is a map

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

if __name__ == "__main__":
'''
dataSet = loadDataSet()
print(dataSet)
C1 = createC1(dataSet)
print(C1)
D = map(set, dataSet)
print(D)
L1,supportData = scanD(D, C1, 0.5)
print(L1)
print(supportData)
'''
dataSet = loadDataSet()
L,supportData = apriori(dataSet)
print(L[1])

结果输出：[[frozenset([1]), frozenset([3]), frozenset([2]), frozenset([5])], [frozenset([1, 3]), frozenset([2, 5]), frozenset([2, 3]), frozenset([3, 5])], [frozenset([2, 3, 5])], []]

从频繁项集中发现关联规则生成：

这里用到很重要的一个剪枝条件：如 0,1,2 --> 3 是一条低可信度的规则，那么所有其他以3做为后件的规则可信度也会较低，这就是简单快速的剪枝规则。

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,br1,minConf = 0.7):
prunedH = []
for conseq in H:
conf = supportData[freqSet]/supportData[freqSet-conseq]
if conf>= minConf:
print freqSet-conseq,' --> ',conseq, 'confidence:',conf
br1.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)

输出support 0.5 confidence 0.5 的关联规则：

frozenset([3]) --> frozenset([1]) confidence: 0.666666666667

frozenset([1]) --> frozenset([3]) confidence: 1.0

frozenset([5]) --> frozenset([2]) confidence: 1.0

frozenset([2]) --> frozenset([5]) confidence: 1.0

frozenset([3]) --> frozenset([2]) confidence: 0.666666666667

frozenset([2]) --> frozenset([3]) confidence: 0.666666666667

frozenset([5]) --> frozenset([3]) confidence: 0.666666666667

frozenset([3]) --> frozenset([5]) confidence: 0.666666666667

frozenset([5]) --> frozenset([2, 3]) confidence: 0.666666666667

frozenset([3]) --> frozenset([2, 5]) confidence: 0.666666666667

frozenset([2]) --> frozenset([3, 5]) confidence: 0.666666666667

原文链接http://blog.csdn.net/huruzun/article/details/40835053