1 Introduction
1.1 Problem
频繁模式是频繁出现在数据集中的模式，对于数据分类、聚类、和其他数据挖掘任务有极大的帮助，频繁模式的挖掘成为了一项重要的数据挖掘任务和数据挖掘关注的主题。本次实验应用不同的频繁模式挖掘的算法（Apriori, FP-Growth, Dummy）对于购物数据以及用户计算机使用数据进行挖掘，以期发现其中有趣的关联规则。
1.2 Dataset
本次实验有两个数据集。第一个数据集为某杂货店一个月内的交易记录，每一行为一条交易内容，总共包含了9835条记录和169件商品；第二个数据集为在UNIX系统上的9个命令行集合，其中仅保留了命令名、信号、元字符这三项，在会话的首尾分别插入SOF和EOF作为标记，数据已按照时间和令牌顺序拼接，不含时间戳。
2 Methods
2.0 Basic Concepts
数据挖掘任务中频繁模式可以用关联规则的形式表示，
，规则的支持度( )和置信度( )，反映所发现规则的有用性和确定性。项的集合称为项集，包含k个项的集合称为k-项集，如果项集相对支持度满足预定义的最小支持度阈值，则是频繁项集。
关联规则的挖掘分为以下两步
（1）找出所有的频繁项集：每个出现次数至少为最小支持度计数(
)
（2）由频繁项集产生强关联规则：必须满足最小支持度和最小置信度的规则
2.1 Dummy Algorithm
输入：事务集T，最小支持度min_sup
输出：所有频繁项集
对事务集T中每一个事务求出其幂集for in :for item in : for in T: if item in : subset_count+=1if subset_count min_sup:return
Dummy算法即为暴力搜索算法，不考虑任何其他情况下，总能找到问题的解答，但是消耗代价较大，假设事务集长度为n，其中最长事务长度为m，考虑平均时间复杂度，为
，由于事务集中事务长度通常长度远小于不同事务元素总数，所以这种算法比起在总的空间内搜索较优。
2.2 Apriori Algorithm
输入：事务集T，最小支持度min_sup
输出：所有频繁项集
while : for : for :return
Apriori算法采用逐层搜索的迭代方法，其中k项集用于探索(k+1)项集。首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记为
，然后，使用 找出频繁2项集的集合 ，使用 找出 ，直到不能找到频繁k项集。先验性质频繁项集的所有非空子集也一定是频繁的用于提高频繁项集逐层产生的效率。
2.3 FP-Growth Algorithm
输入：D:事务数据库 min_sup:最小支持度阈值
输出：频繁模式的完全集
按以下规则构造FP树：
（a）扫描事务数据库D一次，收集频繁项的集合F和它们的支持度计数。对F按支持度计数降序排序，结果为频繁项列表L。
（b）创建FP树的根结点，以"null"标记。对于D中每个事务Trans，执行：
选择Trans中的频繁项，并将L中的次序排序，。设Trans排序后的频繁项列数为 ，其中 是第一个元素，而 是剩余元素的列表。调用 。该过程执行情况如下。如果T有子女N使得 ，则N的计数增加1；否则，创建一个新结点N，将其计数设置为1，链接到它的父结点T，并且通过结点链结构将其链接到具有相同的结点 。如果非空，则递归地调用 FP树的挖掘通过调用 实现。该过程实现如下：
procedure
（1）if 包含单个路径 then:
（2） for 路径中结点的每个组合（记作）:
（3） 产生模式 ，其支持度计数 等于中结点的最小支持度计数
（4）else for 的头表中的每个 :
（5） 产生一个模式 ，其支持度计数
（6） 构造的条件模式基，然后构造 的条件FP树
（7） if then:
（8） 调用
FP-growth方法将发现长频繁模式的问题转换成在较小的条件数据库中递归地搜索一些较短模式，然后连接后缀。它使用最不频繁的项作后缀，提供了较好的选择性。该方法显著地降低了搜索开销。
3 Experience
对于本次实验的两个数据集，分别采用了三种方法多种不同指标进行评测。对于杂货店商品销售数据集，有9835条记录，将所有的事务存储成事务集列表后，调用暴力解法、Apriori方法、FP-growth方法，并且设置最小支持度为0.01，最小置信度为0.5，能够挖掘适合数量的频繁项集从而生成强关联规则（最小支持度设置为0.05以上最小置信度难以设置以挖掘强关联规则）。对于用户UNIX系统的命令行记录，按照和切分为单个事务段，整体形成一个事务集列表，UNIX0和UNIX1中的数据为同一个用户记录，有1082条事务段，对其进行设置最小支持度为0.3，最小置信度为0.9，挖掘该用户的行为记录；对于整体8位用户，形成事务集列表后有11113条事务段，设置最小支持度为0.2，最小置信度为0.8.
实验条件为Windows 10系统，python3.8，实验所用到主要模块为mlxtend, pyfpgrowth。实验中作为baseline的暴力算法自行完成，Apriori算法和FP-growth算法分别调用了mlxtend模块中的apriori方法和pyfpgrowth中的方法。
4 Result
以下为分别对货品销售数据集、单个用户UNIX命令行记录、8位用户UNIX命令行记录进行挖掘其中的频繁项集和强关联规则所得到的结果，并对其进行可视化分析。
从结果上可以看出购买whole milk的人最多，其后是other vegetables和rollsbuns，从强关联规则上可以看出，大部分人在购买了其他商品后，会选择购买whole milk,另有一部分人会选择购买other vegetables， 从结果上可以发现大家对于购买whole milk有着特殊的偏爱。(或许牛奶就在前台处，离开时促销打折等等有趣的规则)
通过对第一位用户命令行操作的记录和多位用户的命令行操作分析，我们可以发现用户最常用的命令集中在对于文件的操作上，主要为文件夹的查看，切换，文件vim下的编辑，退出等常见操作；通过对所有用户的常用命令进行挖掘和分析，可以发现不同用户的习惯相近，并且大多数用户的最常用命令为文件夹的查看，切换进入子目录，进行文件的编辑，并且这些操作常常是组合使用，符合一般用户的习惯。
在本次实验中，调用了不同的方法，其中暴力搜素无法在有限时间内运行结束，所以记录只对比了Apriori算法和FP-growth算法，其中在两个数据集上可以清楚地发现在数据集较小的时候，时间开销上FP-growth算法并不具备优势，因为FP-growth算法在进行挖掘之前会花费额外的开销去构建FP-tree，但是在数据集较大的时候其会为后续挖掘任务节省很大一笔时间。并且我们可以从图中发现，当min_sup设置的越来越多时，两个算法的运行时逐渐接近，可知当最小支持度增大到一定值时，第一轮扫描即可获得几乎所有结果的频繁项集，于是运行时开销都变小。
从两个算法的理论上也可知道，apriori算法多次扫描交易数据库，每次利用候选频繁集产生频繁集；而FP-growth则利用树形结构，无需产生候选频繁集而是直接得到频繁集，大大减少扫描交易数据库的次数，从而提高了算法的效率，但是需要一定的额外内存。
5 Conclusion
本次实验通过在不同数据集上运行这两种算法，获得了不同数据集上的频繁项集和强关联规则以及一些有趣的信息，并且在设置不同的最小支持度来对比分析两种算法的运行时间开销，进而对理论进行深入的探讨。
Apriori算法最大的优点就是原理简单，采用逐层搜索的方法，利用Apriori的两大先验知识不断地迭代执行连接和剪枝步骤，大大压缩了数据集，省略了许多不必要的步骤，使得算法更加高效。而且的扩展性比价好，可应用于并行计算等领域。Apriori的缺点是决定该算法效率的两大重要因素，（1）需要不断地扫描事务数据库，高频率的IO操作大大降低了算法的执行速率；（2）在算法迭代时，生成了许多候选集，执行连接步骤后得到的候选k项集可能会迅速上升，严重影响了算法效率。
Fp-growth算法最大的优点就是它执行速率快，而且要比Apriori算法快一个数量级。整个算法过程只需要扫描两次数据库，可以不用产生候选项集而直接生成频繁项集，这样就节约了很大的内存资源，降低了空间复杂度。创建Fp-tree的时候，采用哈夫曼原理，从而大大压缩了存储空间。但是Fp-growth算法并不能所有的数据集上都取得良好的效果，如果在一个稀疏的数据集上执行此算法，由于数据之间的交集很小，可以合并的元素少，创建的Fp-tree包含特别多的子孙节点，将这样的树保存在内存中丝毫没有起到压缩效果，反而影响算法的效率。而且该算法在构造条件Fp树时使用了递归策略，空间复杂度相对较高，内存开销较大，这在实验中也得到了验证。
作为最经典、应用最广泛的数据挖掘算法，Apriori和FP-growth被应用于众多领域，在实际任务中，我们需要根据不同的数据、不同的要求，选择最为合适的算法，并能够基于此不断改进和提升。
6 Reference
[1] J. Han, M. Kamber and J. Pei. Data Mining: Concepts and Techniques, 3rd edition, Morgan Kaufmann, .
[2] Agrawal R, Srikant R. Fast algorithms for mining association rules[C]//Proc. 20th int. conf. very large data bases, VLDB. 1994, 1215: 487-499.
[3] Han J, Pei J, Yin Y. Mining frequent patterns without candidate generation[J]. ACM sigmod record, 2000, 29(2): 1-12.
如果觉得《关联规则挖掘算法_数据挖掘 | 关联规则分析》对你有帮助，请点赞、收藏，并留下你的观点哦！
