11.4 从频繁项集中挖掘关联规则
11.2节曾经提到，可以利用关联分析发现许多有趣的内容。人们最常寻找的两个目标是频繁项集与关联规则。上一节介绍如何使用Apriori算法来发现频繁项集，现在需要解决的问题是如何找出关联规则。
要找到关联规则，我们首先从一个频繁项集开始。我们知道集合中的元素是不重复的，但我们想知道基于这些元素能否获得其他内容。某个元素或者某个元素集合可能会推导出另一个元素。从杂货店的例子可以得到，如果有一个频繁项集{豆奶, 莴苣}，那么就可能有一条关联规则“豆奶 ➞ 莴苣”。这意味着如果有人购买了豆奶，那么在统计上他会购买莴苣的概率较大。但是,这一条反过来并不总是成立。也就是说，即使“豆奶 ➞ 莴苣”统计上显著，那么“莴苣 ➞ 豆奶”也不一定成立。（从逻辑研究上来讲，箭头左边的集合称作前件，箭头右边的集合称为后件。）
11.3节给出了频繁项集的量化定义，即它满足最小支持度要求。对于关联规则，我们也有类似的量化方法，这种量化指标称为可信度。一条规则P ➞ H的可信度定义为support(P | H)/support(P)。记住，在Python中，操作符|表示集合的并操作，而数学上集合并的符号是U。P | H是指所有出现在集合P或者集合H中的元素。前面一节已经计算了所有频繁项集支持度。现在想获得可信度，所需要做的只是取出那些支持度值做一次除法运算。
从一个频繁项集中可以产生多少条关联规则？图11-4的网格图给出的是从项集{0,1,2,3}产生的所有关联规则。为找到感兴趣的规则，我们先生成一个可能的规则列表，然后测试每条规则的可信度。如果可信度不满足最小要求，则去掉该规则。
现0,1,2→3是一条低可信度规则，那么所有其他以3作为后件的规则可信度也会较低类似于上一节的频繁项集生成，我们可以为每个频繁项集产生许多关联规则。如果能够减少规则数目来确保问题的可解性，那么计算起来就会好很多。可以观察到，如果某条规则并不满足最小可信度要求，那么该规则的所有子集也不会满足最小可信度要求。以图11-4为例，假设规则0,1,2 ➞ 3并不满足最小可信度要求，那么就知道任何左部为{0,1,2}子集的规则也不会满足最小可信度要求。在图11-4中这些规则上都加了阴影来表示。
可以利用关联规则的上述性质属性来减少需要测试的规则数目。类似于程序清单11-2中的Apriori算法，可以首先从一个频繁项集开始，接着创建一个规则列表，其中规则右部只包含一个元素，然后对这些规则进行测试。接下来合并所有剩余规则来创建一个新的规则列表，其中规则右部包含两个元素。这种方法也被称作分级法。下面看一下这种方法的实际效果，打开apriori.py文件，加入下面的代码。
程序清单11-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, brl, minConf=0.7):
prunedH = []
for conseq in H:
conf = supportData[freqSet]/supportData[freqSet-conseq]
if conf >= minConf:
print freqSet-conseq,'-->',conseq,'conf:',conf
brl.append((freqSet-conseq, conseq, conf))
prunedH.append(conseq)
return prunedHdef rulesFromConseq(freqSet, H, supportData, brl, minConf=0.7):
m = len(H[0])
#❷ 尝试进一步合并
if (len(freqSet) > (m + 1)):
#❸ 创建Hm+1条新候选规则
Hmp1 = aprioriGen(H, m + 1)
Hmp1 = calcConf(freqSet, Hmp1, supportData, brl, minConf)
if (len(Hmp1) > 1):
rulesFromConseq(freqSet, Hmp1, supportData, brl, minConf)
上述程序中包含三个函数。第一个函数generateRules()是主函数，它调用其他两个函数。其他两个函数是rulesFromConseq()和calcConf()，分别用于生成候选规则集合以及对规则进行评估。
函数generateRules()有3个参数：频繁项集列表、包含那些频繁项集支持数据的字典、最小可信度阈值。函数最后要生成一个包含可信度的规则列表，后面可以基于可信度对它们进行排序。这些规则存放在bigRuleList中。如果事先没有给定最小可信度的阈值，那么默认值设为0.7。generateRules()的另两个输入参数正好是程序清单11-2中函数apriori()的输出结果。该函数遍历L中的每一个频繁项集并对每个频繁项集创建只包含单个元素集合的列表H1。因为无法从单元素项集中构建关联规则，所以要从包含两个或者更多元素的项集开始规则构建过程❶。如果从集合{0,1,2}开始，那么H1应该是[{0},{1},{2}]。如果频繁项集的元素数目超过2，那么会考虑对它做进一步的合并。具体合并可以通过函数rulesFromConseq()来完成，后面会详细讨论合并过程。如果项集中只有两个元素，那么使用函数calcConf()来计算可信度值。
我们的目标是计算规则的可信度以及找到满足最小可信度要求的规则。所有这些可以使用函数calcConf()来完成，而程序清单11-3中的其余代码都用来准备规则。函数会返回一个满足最小可信度要求的规则列表，为了保存这些规则，需要创建一个空列表prunedH。接下来，遍历H中的所有项集并计算它们的可信度值。可信度计算时使用supportData中的支持度数据。通过导入这些支持度数据，可以节省大量计算时间。如果某条规则满足最小可信度值，那么将这些规则输出到屏幕显示。通过检查的规则也会被返回，并被用在下一个函数rulesFromConseq()中。同时也需要对列表brl进行填充，而brl是前面通过检查的bigRuleList。
为从最初的项集中生成更多的关联规则，可以使用rulesFromConseq()函数。该函数有2个参数：一个是频繁项集，另一个是可以出现在规则右部的元素列表H。函数先计算H中的频繁集大小m❷。接下来查看该频繁项集是否大到可以移除大小为m的子集。如果可以的话，则将其移除。可以使用程序清单11-2中的函数aprioriGen()来生成H中元素的无重复组合❸。该结果会存储在Hmp1中，这也是下一次迭代的H列表。
Hmp1包含所有可能的规则。可以利用calcConf()来测试它们的可信度以确定规则是否满足要求。如果不止一条规则满足要求，那么使用Hmp1迭代调用函数rulesFromConseq()来判断是否可以进一步组合这些规则。
下面看一下实际的运行效果，保存apriori.py文件，在Python提示符下输入：
>>> reload(apriori)
现在，让我们生成一个最小支持度是0.5的频繁项集的集合：
>>> L,suppData=apriori.apriori(dataSet,minSupport=0.5)
>>> rules=apriori.generateRules(L,suppData, minConf=0.7)
>>> rules
[(frozenset([1]), frozenset([3]), 1.0), (frozenset([5]), frozenset([2]),1.0), (frozenset([2]), fr
frozenset([1]) --> frozenset([3]) conf: 1.0
frozenset([5]) --> frozenset([2]) conf: 1.0
frozenset([2]) --> frozenset([5]) conf: 1.0结果中给出三条规则：{1} ➞ {3}、{5} ➞ {2}及{2} ➞ {5}。可以看到，后两条包含2和5的规则可以互换前件和后件，但是前一条包含1和3 的规则不行。下面降低可信度阈值之后看一下结果：
>>> rules=apriori.generateRules(L,suppData, minConf=0.5)
>>> rules
[(frozenset([3]), frozenset([1]), 0.6666666666666666), (frozenset([1]),frozenset([3]), 1.0), (frozenset([5]), frozen
0.6666666666666666), (frozenset([3]), frozenset([2, 5]),0.6666666666666666), (frozenset([2]), frozenset([3, 5]),0.66
frozenset([3]) --> frozenset([1]) conf: 0.666666666667
frozenset([1]) --> frozenset([3]) conf: 1.0
frozenset([5]) --> frozenset([2]) conf: 1.0
frozenset([2]) --> frozenset([5]) conf: 1.0
frozenset([3]) --> frozenset([2]) conf: 0.666666666667
frozenset([2]) --> frozenset([3]) conf: 0.666666666667
frozenset([5]) --> frozenset([3]) conf: 0.666666666667
frozenset([3]) --> frozenset([5]) conf: 0.666666666667
frozenset([5]) --> frozenset([2, 3]) conf: 0.666666666667
frozenset([3]) --> frozenset([2, 5]) conf: 0.666666666667
frozenset([2]) --> frozenset([3, 5]) conf: 0.666666666667一旦降低可信度阈值，就可以获得更多的规则。到现在为止，我们看到上述程序能够在一个小数据集上正常运行，接下来将在一个更大的真实数据集上测试一下效果。具体地，下一节将检查其在美国国会投票记录上的处理效果。
本书评论