最近开始做语义识别，所以不得不开始钻研机器学习算法，最近主要看的是《机器学习实战》这本书，所以里面很多的内容都是出自《机器学习实战》那本书，同时加入了自己的理解。
Apriori算法简介： Apriori算法是一种挖掘关联规则的频繁项集算法，其核心思想是通过候选集生成和情节的向下封闭检测两个阶段来挖掘频繁项集。 Apriori（先验的，推测的）算法应用广泛，可用于消费市场价格分析，猜测顾客的消费习惯；网络安全领域中的入侵检测技术；可用在用于高校管理中，根据挖掘规则可以有效地辅助学校管理部门有针对性的开展贫困助学工作；也可用在移动通信领域中，指导运营商的业务运营和辅助业务提供商的决策制定。
1、挖掘步骤：
a,依据支持度找出所有频繁项集（频度）
b,依据置信度产生关联规则（强度）
2，apriori算法涉及的基本概念
对于A->B
a,支持度：P(A ∩ B)，既有A又有B的概率
b,置信度：P（B|A），P(B|A)，在A发生的事件中同时发生B的概率 p(AB)/P(A) 例如购物篮分析：牛奶 ⇒ 面包
例子：[支持度：3%，置信度：40%]
支持度3%：意味着3%顾客同时购买牛奶和面包
置信度40%：意味着购买牛奶的顾客40%也购买面包
c,如果事件A中包含k个元素，那么称这个事件A为k项集事件A满足最小支持度阈值的事件称为频繁k项集。
d,同时满足最小支持度阈值和最小置信度阈值的规则称为强规则
3,算法的实现步奏
Apriori算法是一种最有影响的挖掘布尔关联规则频繁项集的算法Apriori使用一种称作逐层搜索的迭代方法，“K-1项集”用于搜索“K项集”。
首先，找出频繁“1项集”的集合，该集合记作L1。L1用于找频繁“2项集”的集合L2，而L2用于找L3。如此下去，直到不能找到“K项集”。找每个Lk都需要一次数据库扫描。
Apriori算法的核心需要做的一下两件事情：连接步和剪枝步。连接步是自连接，原则是保证前k-2项相同，并按照字典顺序连接。剪枝步，是使任一频繁项集的所有非空子集也必须是频繁的。反之，如果某个候选的非空子集不是频繁的，那么该候选肯定不是频繁的，从而可以将其从CK（所得频繁集结果）中删除。
简单的讲，1、发现频繁项集，过程为（1）扫描（2）计数（3）比较（4）产生频繁项集（5）连接、剪枝，产生候选项集 重复步骤（1）~（5）直到不能发现更大的频集
4，产生关联步骤
该部分主要采用前面提到的置信度的定义，关联规则的产生步骤如下：
a,对于每个频繁项集L，产生L的所有非空子集：
b,对于L的每个非空子集S，如果 P（L）/P（S）≧min_conf
则输出规则“SàL-S”
注：L-S表示在项集L中除去S子集的项集 
5、算法实现
Apriori算法是发现频繁项集的一种方法，对于两个输出参数分别是最小支持度和数据集。首先生成所有单个物品的项目列表，然后查看那个项目集满足最小支持度。接下把不满足的去掉。将剩下的合并成为2个两素项集。重复继续去掉不满足最小支持度的项集。
对于数据集的每条交易记录tran
对于每个候选can:
检查can是否是tran子集
增加计数
对每个候选can:
如果支持度不小于最小保留
返回所有频繁项集
代码如下：
from numpy import *
def loadDataSet():
s=[[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
w=[]
for i in s:
w.append(set(i))
return s,w
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
def scanD(D, Ck, minSupport):
ssCnt = {}
for can in Ck:
for tid in D:
if can.issubset(tid):
if not (can in ssCnt):
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这里面我对书上的代码进行了修改，在使用书上原有代码时会报错：
TypeError: object of type ‘map’ has no len()
我上面贴出的是正确代码。
而整体算法如下：
当集合项个数大于0时候
构建一个K个项组成的候选列表
检查是否每个项集是频繁的
保留频繁的并且构建K+1项的候选项列表
#前面K-1x项目相同的时候可以生成Lk
def aprioriGen(Lk,k):
#前面k-1项目相同就可以合成
retList = []
lenLk = len(Lk)
for i in range(lenLk):
for j in range(i+1,lenLk):
L1 = list(Lk[i])[:k-2]#可以考虑1个元素的时候是0直接合并
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#项集为2
#频繁n-1项目总数为
while(len(L[k-2])>0):#因为项集存的位置是0
Ck = aprioriGen(L[k-2],k)
Lk,supK = scanD(D,Ck,minSupport)
supportData.update(supK)#加入字典更新
L.append(Lk)#L+1
k+=1#当空集的时候退出
return L,supportData 挖掘数据规则代码：
要找到关联规则。首先需要从频繁项集开始。我们知道集合中元素是不重复的，但是我们想基于这些元素获得其他内容。某个元素或者某个元素的集合可以推导另外一个元素。
关联规则也可以想频繁项集一样量化。频繁项集是需要满足最小支持度的要求。对于关联规则我们就可以用可信度来衡量。一条规则的可信度为P->H定义为support{P|h}/support(P)其实也就是P条件下H的概率满足最小可信度就是关联规则
如果某条规则不满足最小可信度的要求。假设{0,1,2}->{3}不满足最小可信度的要求。那么任何{0,1,2}的子集也不会满足最小可信度的要求。可以利用这个规则来
减少需要测试的规则数目。利用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()
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]#获得条件概率（freq-conseq) -> 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)):#一直到该频繁项集能包含的右边推出等于项的个数-1为止例如{1，2，3，4}当{1}-{2,3,4}以后此时H[0]长度为3
Hmp1 = aprioriGen(H,m+1)#右边推出过程类似生成过程
Hmp1 = calcConf(freqSet,Hmp1,supportData,brl,minConf)#过滤过程返回被推出的右边的项集的集合
if (len(Hmp1)>1):#若有新规则生成继续递归处理
rulesFromConseq(freqSet,Hmp1,supportData,brl,minConf) 上面就是Apriori算法实现关联分析，加入了很多我自己的理解。