数挖 | 关联分析
关联分析
概念
在数据挖掘中，关联分析是一种较为常用的无监督学习算法，与分类、聚类等算法不同的是，这一类算法的主要目的在于发掘数据内在结构特征之间的关联性。关联规则大致包含以下内容，本文主要介绍其中的简单关联分析及 Apriori 算法。
简单一点来说，关联规则就是在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性或因果结构。
或者说，关联分析是发现交易数据库中不同商品（项）之间的关系。
这些关系可以有两种形式：频繁项集或者关联规则
- 频繁项集（frequent item sets）是经常出现在一块的物品的集合；
- 关联规则（association rules）暗示两种物品之间可能存在很强的关系。
下面举个例子来说明这两种概念，下表展示了某个杂货铺的交易清单：
| 交易代码 | 商品 |
|---|---|
| 0 | 豆奶，莴苣 |
| 1 | 莴苣，尿布，葡萄酒，甜菜 |
| 2 | 豆奶，尿布，葡萄酒，橙汁 |
| 3 | 莴苣，豆奶，尿布，葡萄酒 |
| 4 | 莴苣，豆奶，尿布，橙汁 |
频繁项集是指那些经常出现在一起的物品集合，表中的集合 ${葡萄酒，尿布，豆奶}$ 就是频繁项集的一个例子。从数据集中也可以找到诸如 $尿布\rightarrow葡萄酒$ 的关联规则。这意味着如果有人买了尿布，那么他很可能也会买葡萄酒。使用频繁项集和关联规则，商家可以更好地理解他们的顾客。
应该如何定义这些有趣的关系？谁来定义什么是有趣？当寻找频繁项集时，频繁（frequent）的定义是什么？有许多概念可以解答上述问题，不过其中最重要的是
支持度和可信度。
有效性指标
支持度
一个项集的支持度（support）被定义为数据集中包含该项集的记录所占的比例，即事件发生的频率。
$$
support({A, B})=\operatorname{num}(A \cup B)=P(AB)
$$
从上表中可以得到，$\{豆奶\}$ 的支持度为 4/5。而在5 条交易记录中有 3 条包含 $\{豆奶，尿布\}$，因此 $\{豆奶，尿布\}$ 的支持度为 3/5。支持度是针对项集来说的，因此可以定义一个最小支持度，而只保留满足最小支持度的项集。
可信度
可信度或置信度（confidence）是针对一条关联规则来定义的，揭示了如果事件 A 发生了，则事件 B 发生的的概率。
$$
confidence(A \rightarrow B)=\frac{\text { support }({A, B})}{\operatorname{support}({A})}=P(B \mid A)=\frac{P(A B)}{P(A)}
$$
比如 ${尿布}\rightarrow{葡萄酒}$ 这条规则的可信度被定义为 $支持度({尿布，葡萄酒}) / 支持度({尿布})$ 。从表中可以看到，由于 ${尿布, 葡萄酒}$ 的支持度为 3/5，${尿布}$ 的支持度为 4/5，所以 $尿布\rightarrow葡萄酒$ 的可信度为 3/4=0.75。
这意味着对于包含「尿布」的所有记录，我们的规则对其中 75% 的记录都适用。
支持度和可信度是用来量化关联分析是否成功的方法。假设想找到支持度大于 0.8 的所有项集，应该如何去做？一个办法是生成一个物品所有可能组合的清单，然后对每一种组合统计它出现的频繁程度，但当物品成千上万时，上述做法非常非常慢。下一节会详细分析这种情况并讨论 Apriori 原理，该原理会减少关联规则学习时所需的计算量。
Apriori 算法发现频繁项集
上文提到，关联分析的目标包括两项：发现频繁项集和发现关联规则。首先需要找到频繁项集，然后才能获得关联规则。本节将只关注于发现频繁项集。
频繁项集定理
频繁项集具有以下两条定理，这两条定理将应用于我们后面频繁项集及其关联规则的寻找中：
定理1： 频繁项集的子集必为频繁项集（假设项集 $\{A,C\}$ 是频繁项集，那么 $\{A\}$ 和 $\{C\}$ 也为频繁项集）
定理2： 非频繁集的超集一定也是非频繁的（假设项集 $\{D\}$ 不是频繁项集，那么 $\{A,D\}$ 和 $\{C,D\}$ 也不是频繁项集）
定理 1 比较容易证明，因为某项集的子集的支持度一定不小于该项集，定理 2 是定理 1 的逆反定理。
图中给出了所有可能的项集，其中非频繁项集用灰色表示。由于集合 $\{2,3\}$ 是非频繁的， 因此 $\{0,2,3\}$、$\{1,2,3\}$ 和 $\{0,1,2,3\}$ 也是非频繁的，它们的支持度根本不需要计算。
频繁项集生成
Apriori 算法是发现频繁项集的一种方法。Apriori 算法的两个输入参数分别是最小支持度和数据集。该算法首先会生成所有单个物品的项集列表。接着扫描交易记录来查看哪些项集满足最小 支持度要求，那些不满足最小支持度的集合会被去掉。然后，对剩下来的集合进行组合以生成包含两个元素的项集。接下来，再重新扫描交易记录，去掉不满足最小支持度的项集。该过程重复进行直到所有项集都被去掉。
综上所述，Apriori 算法采用迭代的方式逐层寻找下层的超集，并在超集中发现频繁项集。经过层层迭代，直到最顶层得到最大频繁项集为止。在每一轮的迭代中都包含以下两个步骤：
- 产生候选集 $C_k$，它是有可能成为频繁项集的项目集合；
- 修剪候选集 $C_k$，即基于 $C_k$ 计算相应的支持度，并依据最小支持度 $S_{min}$ 对候选集 $C_k$ 进行删减，得到新的候选集 $C_{k+1}$，如此循环迭代，直到无法产生候选项集为止，这样最后一轮所得到的频繁项集就是 Apriori 所要求的最大频繁项集。
整个 Apriori 算法的伪代码如下：
当集合中项的个数大于0时
构建一个k个项组成的候选项集的列表
检查数据以确认每个项集都是频繁的
对数据集中的每条交易记录tran
对每个候选项集can：
检查一下can是否是tran的子集：
如果是，则增加can的计数值
对每个候选项集：
如果其支持度不低于最小值，则保留该项集
返回所有频繁项集列表
保留频繁项集并构建k+1项组成的候选项集的列表
频繁项集第二定理：非频繁项集的超集一定也是非频繁的
从频繁项集中挖掘关联规则
得到最大频繁项集并不是最终的目的。之前在判断关联规则的有效性时，我们学习了置信度与支持度两个指标。其中，支持度已经在寻找最大频繁项集的过程中发挥了作用，那么，在接下来关联规则的产生上，就轮到置信度大显身手了。
从一个频繁项集中可以产生多少条关联规则？下图的网格图给出的是从项集 $\{0,1,2,3\}$ 产生的所有关联规则。为找到感兴趣的规则，我们先生成一个可能的规则列表，然后测试每条规则的置信度。如果置信度不满足最小要求，则去掉该规则。
类似于上一节的频繁项集生成，我们可以为每个频繁项集产生许多关联规则。如果能够减少规则数目来确保问题的可解性，那么计算起来就会好很多。可以观察到，如果某条规则并不满足 最小可信度要求，那么该规则的所有子集也不会满足最小可信度要求。以上图为例，假设规则 $0,1,2 \rightarrow 3$ 并不满足最小可信度要求，那么就知道任何左部为 $\{0,1,2\}$ 子集的规则也不会满足最小可 信度要求。在图中这些规则上都加了阴影来表示。
可以利用关联规则的上述性质属性来减少需要测试的规则数目。类似于
Apriori 算法，可以首先从一个频繁项集开始，接着创建一个规则列表，其中规则右部只包含一个元素，然后对这些规则进行测试。接下来合并所有剩余规则来创建一个新的规则列表，其中规则右部包含两个元素。这种方法也被称作分级法。
程序清单
Python
# Apriori算法中的辅助函数
def loadDataSet():
"""
创建一个用于测试的简单数据集
"""
return [[1,3,4], [2,3,5], [1,2,3,5], [2,5]]
def creatC1(dataSet):
"""
输入：数据集dataSet
输出：C1是大小为1的所有候选项集的集合
过程：首先创建一个空列表C1，它用来存储所有不重复的项值。接下来遍历数据集中的所有交易记录。对每一条记录，遍历记录中的每一个项。如果某个物品项没有在C1中出现，则将其添加到C1中。这里并不是简单地添加每个物品项，而是添加只包含该物品项的一个列表。这样做的目的是为每个物品项构建一个集合。因为在Apriori算法的后续处理中，需要做集合操作。Python不能创建只有一个整数的集合，因此这里实现必须使用列表（有兴趣的读者可以试一下）。这就是我们使用一个由单物品列表组成的大列表的原因。最后，对大列表进行排序并将其中的每个单元素列表映射到frozenset()，最后返回frozenset的列表
细节：由于算法一开始是从输入数据中提取候选项集列表，所以这里需要一个特殊的函数来处理，而后续的项集列表则是按一定的格式存放的。这里使用的格式就是Python中的frozenset类型。frozenset是指被“冰冻”的集合，就是说它们是不可改变的，即用户不能修改它们。这里必须要使用frozenset而不是set类型，因为之后必须要将这些集合作为字典键值使用，使用frozenset可以实现这一点，而set却做不到
"""
C1 = []
for transaction in dataSet:
for item in transaction:
if not [item] in C1:
C1.append([item])
C1.sort()
return map(frozenset, C1)
def scanD(D, Ck, minSupport):
"""
输入：数据集，候选项集列表Ck，感兴趣项集的最小支持度minSupport
输出：该函数用于从Ck生成Lk，另外，该函数会返回一个 包含支持度值的字典以备后用
过程：函数首先创建一个空字典ssCnt，然后遍历数据集中的所有交易记录以及C1中的所有候选集。如果C1中的集合是记录的一部分，那么增加字典中对应的计数值。这里字典的键就是集合。当扫描完数据集中的所有项以及所有候选集时，就需要计算支持度。不满足最小支持度要求的集合不会输出。函数也会先构建一个空列表，该列表包含满足最小支持度要求的集合。下一个循环遍历字典中的每个元素并且计算支持度。如果支持度满足最小支持度要求，则将字典元素添加到retList中，函数最后返回最频繁项集的支持度supportData
细节：可以使用语句retList.insert(0,key) 在列表的首部插入任意新的集合。当然也不一定非要在首部插入，这只是为了让列表看起来有组织
"""
ssCnt = {}
for tid in D:
for can in Ck:
if can.issubset(tid):
if not ssCnt.has_key(can): 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
# Apriori算法
def aprioriGen(Lk, k):
"""
输入：频繁项集列表Lk，项集元素个数k
输出：候选项集Ck
举例：以{0}、{1}、{2}作为输入，会生成{0,1}、{0,2}以及{1,2}
过程：首先创建一个空列表，然后计算Lk中的元素数目。接下来，比较Lk中的每一个元素与其他元素，这可以通过两个for循环来实现。紧接着，取列表中的两个集合进行比较。如果这两个集合的前面k-2个元素都相等，那么就将这两个集合合成一个大小为k的集合
细节：k-2有点让人疑惑。接下来再进一步讨论细节。当利用{0}、{1}、{2}构建{0,1}、{0,2}、{1,2}时，这实际上是将单个项组合到一块。现在如果想利用{0,1}、{0,2}、{1,2}来创建三元素项集，应该怎么做？如果将每两个集合合并，就会得到{0,1,2}、{0,1,2}、{0,1,2}。也就是说，同样的结果集合会重复3次。接下来需要扫描三元素项集列表来得到非重复结果，我们要做的是确保遍历列表的次数最少。现在，如果比较集合{0,1}、{0,2}、{1,2}的第1个元素并只对第1个元素相同的集合求并操作，又会得到什么结果？{0,1,2}，而且只有一次操作！这样就不需要遍历列表来寻找非重复值
"""
retList = []
lenLk = len(Lk)
for i in range(lenLk):
for j in range(i+1, lenLk):
L1 = list(Lk[i])[:k-2]; 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):
"""
输入：数据集dataSet，支持度minSupport
输出：L包含满足最小支持度的频繁项集列表，suppData是包含项集的支持度值字典
过程：函数会生成候选项集的列表，这通过首先创建C1然后读入数据集将其转化为D（集合列表）来完成。程序中使用map函数将set()映射到dataSet列表中的每一项。接下来，使用scanD()函数来创建L1，并将L1放入列表L中。L会包含L1、L2、L3…。现在有了L1，后面会继续找L2，L3…，这可以通过while循环来完成，它创建包含更大项集的更大列表，直到下一个大的项集为空。如果这听起来让人有点困惑的话，那么等一下你会看到它的工作流程。首先使用aprioriGen()来创建Ck，然后使用scanD()基于Ck来创建Lk。Ck是一个候选项集列表，然后scanD()会遍历Ck，丢掉不满足最小支持度要求的项集。Lk列表被添加到L，同时增加k的值，重复上述过程。最后，当Lk为空时，程序返回L并退出。
"""
C1 = creatC1(dataSet)
D = map(set, dataSet)
L1, supportData = scanD(D, C1, minSupport)
L = [L1]
k = 2
while (len(L[k-2]) > 0):
Ck = aprioriGen(L[k-2], k)
Lk, supK = scanD(D, Ck, minSupport)
supportData.update(supK)
L.append(Lk)
k += 1
return L, supportData
# 关联规则生成函数
def generateRules(L, supportData, minConf=0.7):
"""
输入：频繁项集列表、包含那些频繁项集支持数据的字典、最小可信度阈值
输出：生成一个包含可信度的规则列表，后面可以基于可信度对它们进行排序
过程：该函数遍历L中的每一个频繁项集并对每个频繁项集创建只包含单个元素集合的列表H1。因为无法从单元素项集中构建关联规则，所以要从包含两个或者更多元素的项集开始规则构建过程。如果从集合{0,1,2}开始，那么H1应该是[{0},{1},{2}]。如果频繁项集的元素数目超过2，那么会考虑对它做进一步的合并。具体合并可以通过函数rulesFromConseq()来完成，后面会详细讨论合并过程。如果项集中只有两个元素，那么使用函数calcConf()来计算可信度值
"""
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。接下来，遍历H中的所有项集并计算它们的可信度值。可信度计算时使用supportData中的支持度数据。通过导入这些支持度数据，可以节省大量计算时间。如果某条规则满足最小可信度值，那么将这些规则输出到屏幕显示。通过检查的规则也会被返回，并被用在下一个函数rulesFromConseq()中。同时也需要对列表brl进行填充，而brl是前面通过检查的bigRuleList
"""
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 prunedH
def rulesFromconseq(freqSet, H, supportData, brl, minConf=0.7):
"""
作用：生成候选规则集合
过程：为从最初的项集中生成更多的关联规则，可以使用rulesFromConseq()函数。该函数有2个参数：一个是频繁项集，另一个是可以出现在规则右部的元素列表H。函数先计算H中的频繁集大小m。接下来查看该频繁项集是否大到可以移除大小为m的子集。如果可以的话，则将其移除。可以使用函数aprioriGen()来生成H中元素的无重复组合。该结果会存储在Hmp1中，这也是下一次迭代的H列表。Hmp1包含所有可能的规则。可以利用calcConf()来测试它们的可信度以确定规则是否满足要求。如果不止一条规则满足要求，那么使用Hmp1迭代调用函数rulesFromConseq()来判断是否可以进一步组合这些规则
"""
m = len(H[0])
if (len(freqSet) > (m+1)):
Hmpl = aprioriGen(H, m+1)
Hmpl = calcConf(freqSet, Hmpl, supportData, brl, minConf)
if (len(Hmpl) > 1):
rulesFromConseq(freqSet, Hmpl, supportData, brl, minConf)
R
详见 用 R 语言进行关联分析
参考文献：
