1. 关联分析
1.1 定义
关联分析是一种在大规模数据上寻找物品间隐含关系的一种任务.这种关系有2种形式:频繁项集和关联规则.
(1) 频繁项集(frequent item sets): 经常出现在一起的物品的集合;
(2) 关联规则(association rules): 暗示两种物品之间可能存在很强的关系.
1.2 量化关联分析是否成功的算法
支持度和可信度是用来量化关联分析是否成功的方法.
(1)支持度(support) : 一个项集的支持度被定义为数据集中包含该项集的记录所占的比例. 支持度针对项集而言,可以设置最小支持度,只保留满足最小支持度的项集.以下图中的清 单为例, {豆奶}的支持度为4/5;{豆奶,尿布}的支持度为3/5.
(2) 可信度或置信度(confidence) : 针对关联规则定义的. 例如: 规则{尿布}->{葡萄酒}的可信度被定义为 "支持度{尿布,葡萄酒}/支持度{尿布}" . 支持度{尿布,葡萄酒}为3/5 , 支持度{尿布} 为4/5, 即这条规则可信度为3/4. 这意味着对于包含"尿布"的所有记录,我们的规则对其中75%的记录都适用.
2. Apriori
2.1 问题: 假设一家商店里只有4种商品:0,1,2,3. 下图显示了所有可能被购买的商品组合:
对于单个项集的支持度, 通过遍历每条记录并检查该记录是否包含该项集来计算.但是对于包含N种物品的数据集共有
2.2 Apriori原理
Apriori原理能够减少计算量.
其内容是: 若某个项集是频繁的, 那么它的子集也是频繁的; 则其逆否命题也是正确的,即 若一个项集是非频繁的, 则它的所有超集也是非频繁的.
举例说明: 已知阴影项集{2,3}是非频繁的。利用这个知识，我们就知道项集{0,2,3}，{1,2,3}以及{0,1,2,3}也是非频繁的。也就是说，一旦计算出了{2,3}的支持度，知道它是非频繁的后，就可以紧接着排除{0,2,3}、{1,2,3}和{0,1,2,3}。使用该原理可以避免项集数目的指数增长,从而在合理时间内计算出频繁项集.
2.3 实现Apriori算法来发现频繁项集
(1) Apriori算法是发现频繁项集的一种方法. 其两个输入参数分别是数据集和最小支持度.
(2) Apriori算法流程:
(3) Apriori算法生成频繁项集的伪代码
对数据集中的每条交易记录tran:
对每个候选项集can:
检查交易记录tran是否包含候选项集can:
若包含,则增加can的计数;
对每个候选项集:
若该候选项集的支持度不低于最小支持度, 则保留; 反之, 则去掉.
返回所有频繁项集列表
其具体实现代码如下:
<span style="font-size:14px;"><span style="font-size:18px;">#c1是所有单个物品的集合
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) #frozenset是不能改变的集合,用户不能修改
#由ck得到lk的过程,即从ck选出支持度不小于指定值的项构成lk
def scanD(data,ck,minSupport):
#统计每个候选项集及其对应的出现次数
ssCnt = {}
for transaction in data:
for can in ck:
if can.issubset(transaction):
if not ssCnt.has_key(can):
ssCnt[can] = 1
else:
ssCnt[can] += 1
#去掉不满足最小支持度的候选项集
numItems = float(len(data))
retList = [] #存储满足支持度不低于最小值的项集
supportData = {} #存储所有项集及其支持度
for key in ssCnt:
support = ssCnt[key]/numItems
if support >= minSupport:
retList.insert(0,key)
supportData[key] = support
return retList,supportData #返回的retlist是ck中满足最小支持度项集的集合</span></span>整个Apriori算法的伪代码如下:
当集合中项的个数大于0时: