从频繁项集中挖掘关联规则
Poblog 07月09日 2017
从杂货店的例子可以得到，如果有一个频繁项集{豆奶, 莴苣}，那么就可能有一条关联规则“豆奶 -> 莴苣”。这意味着如果有人购买了豆奶，那么在统计上他会购买莴苣的概率较大。但是,这一条反过来并不总是成立。箭头左边的集合称作前件，箭头右边的集合称为后件。
关联规则量化方法:可信度
一条规则P -> H的可信度定义为 support(P | H)/support(P) P | H 是指所有出现在集合 P 或者集合 H 中的元素
生成一个可能的规则列表，然后测试每条规则的可信度。如果可信度不满足最小要求，则去掉该规则
先验知识:
如果发现0,1,2->3是一条低可信度规则，那么所有其他以3作为后件的规则可信度也会较低
假设规则0,1,2 ->3并不满足最小可信度要求，那么就知道任何左部为{0,1,2}子集的规则也不会满足最小可信度要求。
算法使用:
dataSet=loadDataSet();
L, supportData=apriori(dataSet);//L:频繁项集
[[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})], [frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})], [frozenset({2, 3, 5})], []]
//
bigRuleList2=generateRules(L, supportData,0.5);//bigRuleList2:满足最低可信度的推倒关系
[(frozenset({3}), frozenset({2}), 0.6666666666666666), (frozenset({2}), frozenset({3}), 0.6666666666666666), (frozenset({5}), frozenset({3}), 0.6666666666666666), (frozenset({3}), frozenset({5}), 0.6666666666666666), (frozenset({5}), frozenset({2}), 1.0), (frozenset({2}), frozenset({5}), 1.0), (frozenset({3}), frozenset({1}), 0.6666666666666666), (frozenset({1}), frozenset({3}), 1.0), (frozenset({5}), frozenset({2, 3}), 0.6666666666666666), (frozenset({3}), frozenset({2, 5}), 0.6666666666666666), (frozenset({2}), frozenset({3, 5}), 0.6666666666666666)]
//
#生成候选规则集合：计算规则的可信度以及找到满足最小可信度要求的规则
def calcConf(freqSet, H, supportData, brl, minConf=0.7):
//freqSet:候选规则列表
frozenset({2, 3})
H:规则列表的全部数字项
[frozenset({2}), frozenset({3})]
supportData:所有组合的支持度
{frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({1, 3}): 0.5, frozenset({2, 5}): 0.75, frozenset({3, 5}): 0.5, frozenset({2, 3}): 0.5, frozenset({1, 5}): 0.25, frozenset({1, 2}): 0.25, frozenset({2, 3, 5}): 0.5}
brl:
[]
minConf:最小要求的可信度
0.7
//
#针对项集中只有两个元素时，计算可信度
prunedH = []#返回一个满足最小可信度要求的规则列表
for conseq in H:#后件，遍历 H中的所有项集并计算它们的可信度值
//conseq:遍历所有数字项集
frozenset({2})
//
conf = supportData[freqSet]/supportData[freqSet-conseq] #可信度计算，结合支持度数据
//freqSet-conseq:差集对应可信度计算公式的support(P)
frozenset({3})
conf: freqSet这条规则的可信度
0.6666666666666666
//
if conf >= minConf:
//符合最小可信度要求的处理（注:下面说明数据和上面的数据记录无关）//
print (freqSet-conseq,'-->',conseq,'conf:',conf)
#如果某条规则满足最小可信度值,那么将这些规则输出到屏幕显示
brl.append((freqSet-conseq, conseq, conf))#添加到规则里，brl 是前面通过检查的
//brl:存放符合最小可信度时的规则记录，已经存放的是之前检查过的
: [(frozenset({3}), frozenset({2}), 0.6666666666666666)]
//
prunedH.append(conseq)#同样需要放入列表到后面检查
//prunedH:存放通过了可信度检查的规则关系的起点项
[frozenset({2})]
//
return prunedH
//prunedH:返回所有的规则起点
[frozenset({3}), frozenset({5})]
//
#合并
def rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
#参数:一个是频繁项集,另一个是可以出现在规则右部的元素列表 H
//freqSet:候选规则列表
frozenset({2, 3, 5})
H:规则列表的全部数字项
[frozenset({2}), frozenset({3}), frozenset({5})]
supportData:所有组合的支持度
{frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({1, 3}): 0.5, frozenset({2, 5}): 0.75, frozenset({3, 5}): 0.5, frozenset({2, 3}): 0.5, frozenset({1, 5}): 0.25, frozenset({1, 2}): 0.25, frozenset({2, 3, 5}): 0.5}
brl:存放符合最小可信度时的规则记录，已经存放的是之前检查过的
[(frozenset({3}), frozenset({2}), 0.6666666666666666), (frozenset({2}), frozenset({3}), 0.6666666666666666), (frozenset({5}), frozenset({3}), 0.6666666666666666), (frozenset({3}), frozenset({5}), 0.6666666666666666), (frozenset({5}), frozenset({2}), 1.0), (frozenset({2}), frozenset({5}), 1.0), (frozenset({3}), frozenset({1}), 0.6666666666666666), (frozenset({1}), frozenset({3}), 1.0)]
minConf:最小要求的可信度
0.5
//
m = len(H[0])
//m:
1
//
if (len(freqSet) > (m + 1)): #频繁项集元素数目大于单个集合的元素数
//len(freqSet):规则列表元素的个数大于单个集合的元素数,即可以向上合并
3
//
Hmp1 = aprioriGen(H, m+1)#存在不同顺序、元素相同的集合，合并具有相同部分的集合
//Hmp1:合并出规则组合作为右侧推导结果
[frozenset({2, 3}), frozenset({2, 5}), frozenset({3, 5})]
//
Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)#计算可信度
//Hmp1:验证规则是否符合最小可信度
[frozenset({2, 3}), frozenset({2, 5}), frozenset({3, 5})]
//
if (len(Hmp1) > 1): #满足最小可信度要求的规则列表多于1,则递归
//len(Hmp1):将右侧推倒组合生成新的推倒
3
//
rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
#生成关联规则
def generateRules(L, supportData, minConf=0.7):
#频繁项集列表、包含那些频繁项集支持数据的字典、最小可信度阈值
//L:频繁项集列表(满足最小支持度)
[[frozenset({5}), frozenset({2}), frozenset({3}), frozenset({1})], [frozenset({2, 3}), frozenset({3, 5}), frozenset({2, 5}), frozenset({1, 3})], [frozenset({2, 3, 5})], []]
supportData://支持度关系
{frozenset({1}): 0.5, frozenset({3}): 0.75, frozenset({4}): 0.25, frozenset({2}): 0.75, frozenset({5}): 0.75, frozenset({1, 3}): 0.5, frozenset({2, 5}): 0.75, frozenset({3, 5}): 0.5, frozenset({2, 3}): 0.5, frozenset({1, 5}): 0.25, frozenset({1, 2}): 0.25, frozenset({2, 3, 5}): 0.5}
minConf://最小要求的可信度
0.5
//
bigRuleList = [] #存储所有的关联规则
for i in range(1, len(L)): #只获取有两个或者更多集合的项目，从1,即第二个元素开始，L[0]是单个元素的
# 两个及以上的才可能有关联一说，单个元素的项集不存在关联问题
//i:遍历L有两个或者更多集合的项目
1
//
for freqSet in L[i]:
//freqSet:遍历每一个有两个元素的频繁项
frozenset({2, 3})
//
H1 = [frozenset([item]) for item in freqSet]
//H1:得到freqSet的全部单个项
[frozenset({2}), frozenset({3})]
//
#该函数遍历L中的每一个频繁项集并对每个频繁项集创建只包含单个元素集合的列表H1
if (i > 1):
#如果频繁项集元素数目超过2,那么会考虑对它做进一步的合并
rulesFromConseq(freqSet, H1, supportData, bigRuleList, minConf)
else:#第一层时，后件数为1
calcConf(freqSet, H1, supportData, bigRuleList, minConf)# 调用函数2
//bigRuleList:获得关联规则
[(frozenset({3}), frozenset({2}), 0.6666666666666666), (frozenset({2}), frozenset({3}), 0.6666666666666666)]
//
return bigRuleList
