关联分析-Apriori算法
Poblog 07月04日 2017
频繁项集:经常出现在一块的物品的集合
关联规则:暗示两种物品之间可能存在很强的关系
频繁的定义:支持度和可信度
项集的支持度:数据集中包含该项集的记录所占的比例,可以定义一个最小支持度,而只保留满足最小支持度的项集
可信度或置信度:针对一条诸如{尿布}->{葡萄酒}的关联规则来定义,规则的可信度被定义为“支持度({尿布, 葡萄酒})/支持度({尿布})”
Apriori 原理:Apriori原理是说如果某个项集是频繁的,那么它的所有子集也是频繁的。这意味着如果{0,1}是频繁的,那么{0}、{1}也一定是频繁的。这个原理直观上并没有什么帮助,但是如果反过来看就有用了,也就是说如果一个项集是非频繁集,那么它的所有超集也是非频繁的
使用 Apriori 算法来发现频繁集:
Apriori算法的两个输入参数分别是最小支持度和数据集
算法首先会生成所有单个物品的项集列表。接着扫描交易记录来查看哪些项集满足最小支持度要求,那些不满足最小支持度的集合会被去掉。然后,对剩下来的集合进行组合以生成包含两个元素的项集。接下来,再重新扫描交易记录,去掉不满足最小支持度的项集。该过程重复进行直到所有项集都被去掉
使用
dataSet=loadDataSet();
print(dataSet);
//dataSet:组合数据列表
[[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
//
c1=createC1(dataSet);
print(c1);
//c1:大小为1的所有候选项集的集合
[frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
//
retList,supportData=scanD(dataSet,c1,0.5);
print(retList);
print(supportData);
//retList:支持度比0.5大的点的集合
[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})]
supportData:所有点的支持度
{frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75}
//
算法流程1:
# C1 是大小为1的所有候选项集的集合
def createC1(dataSet):
//dataSet:组合数据列表
[[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
//
C1 = []
for transaction in dataSet:
//遍历每个组合
transaction:
[1, 3, 4]
//
for item in transaction:
//遍历transaction每个数据
item:
1
//
if not [item] in C1:
C1.append([item]) #store all the item unrepeatly
//往C1添加不重复的数据点//
C1.sort()
//C1:对C1从小到大排序
[[1], [2], [3], [4], [5]]
//
#return map(frozenset, C1)#frozen set, user can't change it.
return list(map(frozenset, C1))
//return:不可修改的数据类型
[frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
//
算法流程2:
def scanD(D,Ck,minSupport):
//D:原始数据
[[1, 3, 4], [2, 3, 5], [1, 2, 3, 5], [2, 5]]
Ck:通过createC1得到的不重复单个数据点的不可变集合
[frozenset({1}), frozenset({2}), frozenset({3}), frozenset({4}), frozenset({5})]
minSupport:需要满足的最小支持度
0.5
//
ssCnt={}
//记录数字项出现的次数//
for tid in D:
//tid:遍历数据集
[1, 3, 4]
//
for can in Ck:
//can:遍历每个最小项
frozenset({1})
//
if can.issubset(tid):
//最小项在该数据集项中出现
//
#if not ssCnt.has_key(can):
if not can in ssCnt:
ssCnt[can]=1
else: ssCnt[can]+=1
//ssCnt初始化或增加该数字项的出现次数
//
numItems=float(len(D))
//numItems:数字集合项的总数
4.0
//
retList = []
supportData = {}
for key in ssCnt:
//key:遍历数字项和出现次数关系的集合
frozenset({1})
//
support = ssCnt[key]/numItems #compute support
//support:计算key支持度
0.5
//
if support >= minSupport:
retList.insert(0,key)
//retList:存放在最小支持度范围内的数字点
[frozenset({1})]
//
supportData[key] = support
//supportData:记录全部的点和点的支持度
{frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25}
//
return retList, supportData