关联规则挖掘与频繁项集算法比较-CSDN博客

本文链接：https://blog.csdn.net/weixin_43074474/article/details/122930295

项目github地址：点我跳转

1 实验说明

1.1 任务

本次实验的主要任务是对给定数据集进行关联规则挖掘。通过改变support和confidence的值，比较Aprioir、FP-growth和最基本的穷举法之间的差别，在进行比较时，主要着眼于产生的频繁项集的数目，算法运行过程中的内存消耗和时间消耗。

1.2 数据集

本次实验的数据集总共有两个，分别是GroceryStore和UNIX_usage。

GroceryStore数据集包含某商店一个月内的交易记录，数据存储的格式为csv，每一行是一条交易信息，购买的商品名称被“{”和“}”包围着。此数据集总共有9835条交易记录，涉及169种商品。

UNIX_usage数据集总共包含9个文件，每个文件都是真实用户的命令行输入历史，其中第0个文件和第1个文件是同一用户在不同平台和项目中产生的命令行记录，其余的7个文件都是来自不同用户的命令行历史记录。出于保护隐私的考虑，移除了原始文件中的文件名、用户名、文件结构等所有可能暴漏个人信息的部分，而是用<1>来代替此部分。在一个session的开始和结束会包含**SOF**和**EOF**，而之前在命令行中用空格分隔的参数部分，在此处会单独占据一行。下面是两个session的原始记录。

# Start session 1
cd ~/private/docs
ls -laF | more
cat foo.txt bar.txt zorch.txt > somewhere
exit
# End session 1

# Start session 2
cd ~/games/
xquake &
fg
vi scores.txt
mailx john_doe@somewhere.com
exit
# End session 2

在我们拿到的数据中，这两个session用如下形式来表示。

**SOF**
cd
<1>	 # one "file name" argument
ls
-laF
|
more
cat
<3>	 # three "file" arguments
>
<1>
exit
**EOF**
**SOF**
cd
<1>
xquake
&
fg
vi
<1>
mailx
<1>
exit
**EOF**

2 代码实现

2.1 Apriori

你 Apriori算法的核心是对先验知识的运用，具体来说是利用“频繁项集的所有非空子集也一定是频繁的”这条规则来减少搜索空间。我们利用 $k$ 频繁项集的集合 $L_k$ 生成 $k + 1$ 频繁项集的集合 $L_{k+1}$ ，在生成的过程中，会有一个中间步骤，即 $k + 1$ 频繁项集的候选集合 $C_{k+1}$ 。按照常规的做法，此时应该扫描一遍数据库，判断 $C_{k+1}$ 中的哪个项集是频繁的，哪个是非频繁的。但是我们现在考虑一下刚才提到的先验知识，如果 $C_{k+1}$ 集合中的某个 $k + 1$ 项集 $c$ 是频繁的，那么它的所有子集中长度为 $k$ 的集合，即 $k$ 项集，也一定是频繁的。所有的 $k$ 频繁项集都在 $L_k$ 中，因此可以通过判断 $c$ 的子集中的 $k$ 项集是否出现在 $L_k$ 中来减少搜索空间。此算法的伪代码如Algotithm1所示。

整个算法在实现的时候，由四个函数构成。apriori为主函数，find_frequent_1_itemset用于从原始数据库中寻找1频繁项集，apriori_gen用于从 $k$ 频繁项集中生成 $k + 1$ 候选频繁项集，上文中提到过，生成的过程中会进行剪枝，而has_infrequent_subset函数就是用于判断是否满足剪枝条件的。对候选集初步剪枝之后，需要去扫描一遍数据库，以找出那些真正的 $k + 1$ 项集，此操作由subset函数辅助完成。

对于计算出来的每个 $k$ 频繁项集，都是用list对象进行存储。比如

[ $item_1$ , $item_2$ , …, $item_k$ , frequency]

此list对象共包含 $k + 1$ 个元素，前 $k$ 个元素对应于 $k$ 频繁项集，最后一个元素是此 $k$ 频繁项集在数据库中出现的次数。

在这里插入图片描述

2.2 Dummy

dummy方法是一种穷尽搜索的方法，虽然使用起来效率低，但是实现较为简单。算法伪代码如Algorithm2所示。
在这里插入图片描述
穷尽搜索，即尝试每一种可能的项集组合。先由 $i t e m s e t$ 生成所有只含一个元素的子集，即1频繁候选项集，然后扫描数据库，找出1频繁项集；再由 $i t e m s e t$ 生成所有只含两个元素的子集，即2频繁候选项集，然后扫描数据库，找出2频繁项集。依此类推，直到不能从 $k$ 频繁候选项集中找出 $k$ 频繁项集时结束。

2.3 FP-growth

FP-growth方法比Apriori方法在空间消耗和时间消耗上都有所提升，尤其是当设定的支持度比较低时，这种提升尤为明显。

首先介绍一下FP-Tree的结构。FP-Tree是一棵索引树，每个节点包含五个字段，name字段表示项目的名称，frequency字段表示此项目的频数，parent字段表示此项目的父节点索引，children字段表示此项目的子节点索引，因为一个项目可能有多个子节点，所以children字段为list类型，nextit字段表示下一个和此项目同名的节点索引号。

在FPTree这个类中，除了有nodes字段用来存储树的节点外，还有headtables字段用来存储每个项目的头节点索引。headtables是一个dic}类型，每个元素的key为项目名称，value是此项目第一次在FPTree中出现时的索引。headtables相当于一个头指针表，通过它，可以访问到某个项目在FPTree中的所有节点。

FP-growth算法的伪代码如Algorithm3所示。
在这里插入图片描述
按照FP-growth算法，首先需要扫描一遍数据库，找出所有的频繁1项集，然后再按照每个项集出现的次数逆序排序。之后再扫描一遍数据库，此时需要对数据库中的数据做一些修改，首先将那些没有出现在频繁1项集中的item从数据库中移除，再按照频繁1项集中每个item的顺序，对数据库中的每条transaction进行排序。上述操作完成之后，就可以用数据库中的数据来构建FP-Tree了。构建树的过程，其实就是把一个个结点插入到树中的过程。为了表述方便，假设现在我们要把一条包含n个item的交易记录 $t$ 插入到FP树中，因为 $t$ 有n个item，所以相当于是要插入n个结点。为了找到插入的位置，我们首先需要对现在的FP树进行递归搜索。搜索过程从根节点开始，即最初把根节点当作当前结点。如果根节点存在与 $t [0]$ (交易记录中的第一个item)相同的子节点 $n_0$ ，则递归的去搜索 $n_0$ 是否存在与 $t [1]$ 相同的子节点，依此类推，直到找不到相同的子节点或 $t$ 中的所有item在FP树中都有相同的结点。找到插入的位置之后，插入操作相对比较简单，只是需要注意一下，在插入结点的同时要构建 $h e a d t a b l e s$ 。

到目前为止，关于数据库的FP树已经构建出来了，接下来要做的是根据FP树生成所有的频繁项集。将FP树中出现的所有的item按照频数升序排序，然后遍历这些item，遍历过程由for循环完成，每当遍历到一个item时，将当前的item加入到前缀序列中，然后将此前缀序列作为频繁项集加入到总的频繁项集集合 $L$ 中。之后计算当前item所对应的条件模式基，若此条件模式基不为空，则由其继续构造FP树，然后递归的由此FP树生成所有的频繁项集。

利用FP-growth方法生成的频繁项集和用Apriori方法生成的相比，在表示形式上是相同，都是用list存储，前n-1个元素表示频繁项集中的item，最后一个元素表示此频繁项集的频数。

2.4 Association Rule

按照上述的方法，已经把所有的频繁项集都找出来了，接下来要做的就是从这些频繁项集中挖掘关联规则。对于一个频繁项集 $f i$ 来说，我们需要计算出它所有的非空真子集，然后遍历这些集合，对于 $f i$ 的某个真子集 $s$ 来说，如果满足：
$\frac{support(l)}{support(s)} \ge confidence$
则输出规则 $\Rightarrow (l-s)$

3 实验方案

在进行实验设计时，主要从四个方面切入。

比较不同的数据集产生的频繁项集的数量有什么特点。
对于相同的数据集，使用不同的频繁项集生成算法，在时间消耗上各自的表现如何。
对于相同的数据集，使用不同的频繁项集生成算法，在空间消耗上各自的表现如何。
寻找一些有趣的关联规则，并对这些规则进行讨论。

对于第一个方面，我们可以变换不同的support，然后用本次实验提供的Groceries和UNIX_usage这两个数据集进行实验。

对于第二个方面，我们可以使用同一数据集（我选用的是Groceries），变换不同的support，分别使用dummy、Aprioir、FP-growth算法进行实验，来查看不同算法上的时间消耗。

对于第三个方面，实验方案与探究时间消耗的方案大致相同，只不过我们用mprof run命令代替python命令来记录内存使用情况，当程序运行结束之后，会在当前目录下生成mprofile_xxxxxxxxxxx.data文件，里面存储了相同时间跨度的时间点上内存的使用情况，使用mprof list可以查看文件对应的索引(0,1,2 …)，然后通过执行mprof plot file_index加载对应文件数据来绘制图形

mprof plot 0

对于第四个方面，我们可以变换不同的support和confidence，并且根据lift来查看生成的关联规则。

4 实验结果

4.1 频繁项集的数量

在support设置为0.01的情况下，在两个数据集上进行频繁项集数量的比较。

对于Groceries数据集，不同的频繁项集的数量如表1所示。


k	1	2	3	4
数量	88	213	32	0

表1: Groceries数据集

对于UNIX_usage数据集，不同的频繁项集的数量如表2所示。


k	1	2	3	4	5	6	7	8	9	10	11
数量	61	329	781	1086	1004	635	289	91	19	2	0

UNIX_usage数据集

Groceries数据集中共有9835条transaction，UNIX_usage数据集中共有5058条session。从表1和表2的对比中可以看出，UNIX_usage数据集最多可以产生10频繁项集，而Groceries数据集最多只能产生3频繁项集。从数量关系上来看，虽然UNIX_usage的数据要比Groceries少，但是前者的k频繁项集的数目要远多于后者。出现这种现象的原因，与两个数据集本身的特性有关。UNIX_usage数据集是由真实用户的命令行记录构成的，我们在输入cd <1>命令后，可能会习惯性的再输入ls命令查看当前目录的所有文件。

4.2 频繁项集生成算法的时间性能

用Groceries数据进行实验，来评判dummy、Apriori、FP-growth这三个频繁项集生成算法的时间性能。进行实验的设备为个人笔记本电脑，重要参数为：2 GHz 4 核 Intel Core i5 处理器，16 GB 3733 MHz LPDDR4X 内存。分别设置support为0.1，0.01和0.001，生成所有频繁项集所用的时间如表3所示。
在这里插入图片描述
dummy算法进行的是穷尽搜索，假设数据集中总共有n种不同的item，那么总共有 $C^k_n$ 个候选k频繁项集，因此要想找到所有的k频繁项集，需要扫描数据库 $C^k_n$ 遍。在进行实验时，发现对于三种不同的support，dummy算法都无法在20分钟内结束，因此表3中dummy算法的执行时间用-代替，表示未测得其执行时间。

Apriori算法相较于dummy算法在时间性能上有了很大的提升。相较于dummy的穷尽搜索，Apriori用了一些剪枝的方法，因此减少了搜索空间，提高了执行效率。根据先验知识，“k频繁项集的所有非空子集也是频繁的”，我们可以由k频繁项集生成候选(k+1)频繁项集，相较于dummy算法会产生 $C^{k+1}_n$ 个候选(k+1)频繁项集，此方法会减少候选频繁项集的数量。除此之外，我们还可以再做一次剪枝操作。如果一个(k+1)项集是频繁的，那么它的所有k子集也一定是频繁的，也就是说它的所有k子集一定在k频繁项集的集合里面，假若存在某个k子集不满足此条件，那么这个候选(k+1)频繁项集也一定不是频繁的。通过这两步剪枝操作，可以尽可能的减少候选频繁项集的数目，从而减少扫描数据库的次数（扫描数据库非常耗时）。

FP-growth算法和Apriori算法的思想不同，它通过“树”这种数据结构，使得在生成频繁项集的时候，只需要扫描两次数据库即可。第一次扫描数据库，找出所有的1频繁项集，第二次扫描数据库，构建FP树，之后的所有操作，都是针对FP树进行的。

FP-growth算法克服了Apriori算法需要多次扫描数据库的缺点，因此当生成的频繁项集较多时，FP-growth的执行时间要远少于Apriori。从表3中可以看出，当support为0.1时，FP-growth算法和Apriori算法的执行时间都是毫秒级的，且两者的差异不明显。当support减小为0.01时，生成的频繁项集的数量会增加，此时就能看出FFP-growth算法的优势了，它的时间消耗仅为Apriori算法的 $\frac{1}{10}$ 。当support继续减小到0.001时，FP-growth算法的优势表现的更为明显，生成同样的频繁项集，FP-growth算法的时间消耗仅为Apriori算法的 $\frac{1}{100}$ ，时间性能上提升了两个数量级。

当support减小时，生成的频繁项集的数量会增多。对于Apriori算法来说，它的时间主要是消耗在频繁扫描数据库上，而对于FP-growth算法来说，它的时间主要是消耗在递归构建FP树上。因为扫描数据库是一件非常耗时的工作，所以FP-grow算法的执行时间要远小于Apriori。

4.3 频繁项集生成算法的空间性能

与时间性能的实验类似，仍然使用Groceries数据集评估不同算法的空间性能。由之前的实验已经知道，dummy算法即使在support较小的情况下也很难在短时间内终止，因此本实验只考虑Apriori和FP-growth算法的空间性能。对于不同的support，两种算法占用内存的峰值如表4所示。
在这里插入图片描述
从表4中可以看出，随着support的减小，两种算法所占用的内存都在增加。对于Apriori算法，当support减小时，需要更多的内存空间来存储候选频繁项集。对于FP-growth算法，当support减小时，需要更多的内存空间来递归生成FP树。从实验结果中可以发现一个有趣的现象，当support较大时，FP-growth算法的空间效率要低于Apriori，但是当support较小时，前者的空间效率却又优于后者。

4.4 挖掘关联规则

4.4.1 挖掘Groceries

在进行关联规则挖掘时，首先需要选择合适的support和confidence。若参数的值设的太小，则容易产生大量的关联规则，从而很难从中发现有价值的规则。同理，若参数的值设的太大，则可能会忽略掉一些有意义的关联规则。经过多次尝试，发现对于Groceries数据，support=0.01，confidence=0.5可以产生15条关联规则。所有的这些规则如表5所示。
在这里插入图片描述
在表5中，除了我们熟悉的support和confidence之外，还引入了一个新的指标：lift。lift指标的计算公式为：
$\rightarrow B) = \frac{p(B|A)}{p(B)} = \frac{confidence}{support}$
它的含义是：在已知 $A$ 的前提下 $B$ 发生的概率，和没有先验条件时 $B$ 单独发生的概率之间的相对关系。若lift<1，则说明 $A$ 的发生对 $B$ 的发生起着抑制作用；若lift=1，则说明 $A$ 的发生对 $B$ 是否发生没有任何影响，即 $A$ 和 $B$ 相互独立；若lift>1，则说明 $A$ 的发生对 $B$ 的发生起着促进作用。

从表5中可以看出，每一条强关联规则的lift都大于1，且都大于20，这说明这些规则的关联性较强。在后续进行商品布局时，可以参考上述规则设计每种商品的摆放位置。比如说将yogurt、curd和whole milk摆放在一起，根据过往的统计规律，当顾客购买了yogurt和curd之后，有58.24%的概率会购买whole milk。

观察挖掘出来的所有关联规则，可以发现规则的左部出现最频繁的是root/other vegetables，规则的右部出现最频繁的是whole milk，但是强关联规则中却没有\par \noindent vegetables—>whole milk这条规则。另一个有趣的现象是，挖掘出来的这些规则都是来自3频繁项集，由表1可知，当support为0.01时，有221个2频繁项集，有32个3频繁项集，也就是说2频繁项集的数目要远多于3频繁项集，但是却不能从2频繁项集中挖掘出强关联规则。

4.4.2 挖掘UNIX_usage

在1.2节中，我们对UNIX_usage数据集进行了介绍。每个session相当于Groceries数据集的一个transaction，但是每行数据却不能等同于Groceries中的一个item。UNIX_usage数据集文件中的每行数据是一个unix命令或者命令的参数，如果我们直接对原始的数据集进行挖掘，那么可能会挖掘到一些含有参数的规则，而这种规则是没有实际意义的，因为我们要找的是命令于命令之间的联系。为了避免这种现象的发生，在数据挖掘之前，首先对原始数据集进行清洗，即把那些命令参数过滤掉，只保留真正的命令。

同Groceries数据集一样，我们首先需要找到合适的support和confidence，经过多次尝试，最终选定support=0.1，confidence=0.8。UNIX_usage数据集的关联性比较高，即便选择了限制性比较强的参数，得到的关联规则的confidence仍较高。在此设定下，总共有11条关联规则，如表6所示。
在这里插入图片描述

从表6中，我们可以看到一些符合事实的关联规则，比如cd, vi $\Rightarrow$ ls，它表示在一个session中，如果执行了cd和vi命令，那么有95.74%的概率也执行了ls命令。这是非常符合人的直觉的，首先用cd命令进入某个指定的文件夹，然后用vi命令编辑文件，最后用ls命令查看一下这个文件。

如果将UNIX_usage的关联规则和Groceries的关联规则做类比，那么会发现一些违反事实的规则。比如cd, exit $\Rightarrow$ ls，按照之前的理解，这条关联规则应该解释成执行了cd和exit这两条命令之后，在后续的过程中执行ls的概率为94.34%，但是这一解释显然不符合常识。在执行exit之后，当前session就已经结束了，后续也不会再执行其他命令，当然也不可能执行ls命令了。

出现上述现象的原因是UNIX_usage数据集和Groceries数据集本质上并不相同。Groceries数据集是transaction的集合，每个transaction由若干商品名构成，且若干商品名之间是无序的；UNIX_usage数据集是session的集合，每个session由若干命令构成，且若干命令之间是有序的，可以先执行ls再执行exit，但是反过来却不行。

5 总结

关联规则的挖掘过程分为两步：第一步找到所有的频繁项集，第二步从这些频繁项集中生成强关联规则。第二步相对来说比较简单，只需要遍历每个频繁项集的所有非空子集，然后判断confidence是否满足要求即可。第一步要困难许多，这种困难也在本次实验中有所体现。当用dummy方法找所有的频繁项集时，即使是support设置成0.1，也无法在规定的时间内完成。为了应对这种挑战，人们发明了各种各样的方法来寻找频繁项集，其中最具代表性的便是Apriori算法和FP-growth算法。Apriori算法的精髓是运用先验知识来减少搜索空间，从而提高执行效率，相比于dummy算法，它有了质的提升。但是人们对于这种算法仍然不是特别满意，这主要归因于它的两个最主要的缺点：当support较小时会生成大量的候选频繁项集和多次重复扫描数据库。为了克服这两个缺点，人们提出了FP-growth算法。这种方法无论support多小，都只需要扫描两遍数据库，且不会产生候选频繁项集。FP-growth算法的核心思想是用到了“树”这种数据结构，将原始数据库构建成一棵树，这样后续的所有操作都只需在这棵树上进行。

穷尽搜索方法dummy在实际场景中的应用性不强，因为它会暴力穷举所有可能的候选频繁项集。对于含有n种item的数据集，至多可以产生 $2^n-1$ 个候选项集，所以dummy方法的时间复杂度是 $O(2^n)$ 级别的。同时由于穷举所有的候选频繁项集，所以空间复杂度也很高。Apriori方法相较于dummy方法，减少了候选频繁项集的数目，因此提高了时间和空间的效率。FP-growth算法没有从候选频繁项集的角度考虑，而是直接生成频繁项集，因此又进一步地提高了时空效率。

Groceries数据集来自于真实顾客的购物记录，它的关联规则的置信度（confidence）并不算特别高，但是由于support也较小，所以lift较大，也就是说如果购买了关联规则左边的商品，那么对关联规则右边的商品的销售也有极大的促进作用。UNIX_usage数据集来自于真实用户的命令行历史记录，处于隐私保护的需求，替换了一些敏感内容。这个数据集的关联性比较高，置信度（confidence）最高可达1.0，但是因为support也较高，所以lift整体上不如Groceries。在用程序挖掘出关联规则之后，并不能直接应用这些规则来解决现实问题，因为有部分规则并不符合实际情况，所以还需要再人工筛选一次。