关联分析

发表于 |

1 引言

频繁项集：集合，${a, b, c}$

关联规则：映射，$a\to b$

支持度：针对某个频繁项集，$support(频繁项集a) = \frac{freq(频繁项集a)}{freq(所有项集)}$

可信度：衡量某条关联规则，$confidence(a\to b) = \frac{support(a|b)}{support(a)}$

对于包含N个元素的数据集，可能的集合有$2^N - 1$种，暴力遍历显然药丸，因此引入Apriori原理。

Apriori原理：减少可能的项集，避免指数增长。

  • backwards：如果某个项集是频繁的，那么它的所有子集也是频繁的。
  • forwards：如果一个项集是非频繁项集，那么它的所有超集也是非频繁的。

2 Apriori算法

1
def apriori(dataSet, minSupport=0.5):

算法思路：从单个项集开始检查，去掉那些不满足最小支持度的项集，然后对剩下的集合进行组合，得到包含两个元素的项集，重复扫描，然后将剩余项集组合成包含三个元素的集合，依次类推，直到所有项集都被去掉。

  • 为啥最后会得到空集：因为包含所有元素的项集一定不是频繁项集，否则根据Apriori原理，它的全部子集都是频繁项集。
  • 如何从包含k个元素的项集集合生成包含k+1个元素的项集集合：从k个元素的项集到k+1个元素项集的扩充，只允许有一个元素的不同，算法中为了避免重复结果，只对前k-1个元素相同的两个项集求并集。

代码实现过程中发现了几个知识记录一下：

  • map函数的返回值：python2下直接返回列表，python3下返回的是迭代器：
1
2
3
4
5
map(frozenset, C1)
# 返回 <map object at 0x101e78940> 

list(map(frozenset, C1))
# 返回 list[frozenset1(), frozenset2(), ...]
  • 字典的update方法：
1
2
# 将dict2的键值添加到dict1中，在涉及迭代操作时可以省略传递中间值
dict1.update(dict2)
  • set & frozenset：set无排序且不重复，并且可变，因此unhashable。frozenset不可变，可以用作字典的key。

3 关联规则

对一个包含k个元素的频繁项集，其中可能的关联规则有：

暴力遍历肯定又药丸，因此延续Apriori的思路，关联规则也有一条类似的属性：

  • 如果某条规则的前件不满足最小可信度要求，那么它的所有子集也不满足最小可信度要求。
  • 对应的，如果某条规则的后件不满足最小可信度要求，那么它的所有超集也不满足。

算法思路：对每个至少包含两个元素的频繁项集，从后部只包含一个元素的规则开始，对这些规则进行测试，接下来对所有剩余规则的后件进行组合，得到包含两个元素的后件（对应的补集就是前件），依次类推，直到测试完所有可能的后件。

  • 为啥只检查前后件互补的规则：因为一个频繁项集的所有子集也都是频繁项集，所以一个频繁项集中不互补的规则将是该频繁项集的某个子集的互补规则。

4 FP-growth算法

Apriori算法避免了暴力遍历子项集的指数式增长，但是对每一个新生成的频繁项集，都要扫描整个数据集，当数据集很大时，这种抛物线式增长的时间复杂度也不太令人满意。

FP-growth算法借助一种称为FP树的数据结构存储数据，来抽象原始数据集：

  • 项集以路径的方式存储在树中
  • 相似项之间相连接成链表
  • 一个元素项可以在FP树中出现多次
  • FP树存储的是元素的出现频率
  • 项集完全不同时，树才会分叉，否则会有复用路径

​算法思路：首先遍历一遍原始数据集，记录元素的出现频率，去掉不满足最小支持度的元素。然后再遍历一遍剩下的集合元素，构建FP树。然后就可以通过FP树挖掘频繁项集。

构建FP树：依次遍历每一个项集，首先将其中的非频繁项移除，并按照元素出现频率对过滤后的元素进行重排序。对过滤、排序后的集合，如果树中已存在现有元素，则增加现有元素的计数值，如果不存在，则向树中添加一个分支，新增节点的同时还要更新链表元素。主要就涉及两个数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
# 自定义节点数据结构
class treeNode:
    def __init__(self, nameValue, numOccur, parentNode):
        self.name
        self.count
        self.nodeLink   # 链表信息，指向下一个相似项
        self.parent
        self.children
        
        
# 用于存储元素frequency以及链接相似项的字典数据结构
freq = {}
freq[node_name] = [frequency, node1, node2, ...]
  • 因为集合中元素的出现频率可能相等，因此过滤排序的结果不唯一，生成的树结构也会有差异。
  • 第一次遍历删除非频繁元素时，发现字典在迭代过程中不能删除item，我转化成list暴力解决了，不知道有没有什么优雅的方式。
1
2
3
4
5
6
del freq[item]
# 返回 RuntimeError: dictionary changed size during iteration

for item in list(freq.keys()):
    if freq[item] < minSupport:
        del(freq[item])

挖掘频繁项集：首先创建条件模式基，然后利用条件模式基，构建条件FP树。

1 条件模式基：以所查找元素项为结尾的前缀路径集合，并且每条前缀路径都与起始元素项的计数值相关联。（这里面用到了前面定义的parent和nodeLink属性）

2 构造条件FP树：与构造树的过程相同，使用的dataSet换成了条件模式基而已，函数参数count就是预留彩蛋。这样得到的就是指定频繁项的条件FP树。

1
2
3
4
5
def updateTree(cond_set, myTree, freq_header, count):
# cond_set: 一条path
# myTree: 根节点
# freq_header: dict[node_name] = [frequency, head_node]
# count: path对应的count
  • 构造的条件FP树过滤掉了条件模式基中的一些元素：这些元素本身是频繁项，但是与指定元素组合的集合不是频繁的。
  • 相应地，条件树中剩余元素与指定频繁项组合的集合是频繁的。

3 迭代：从生成的条件FP树中，可以得到更复杂的频繁项。求解复杂频繁项的条件模式基，进而生成对应的条件FP树，就能得到更复杂的频繁项，依次类推进行迭代，直到FP树为空。

​