二进制的top-k闭合频繁模式挖掘

【摘" 要】 自从引入频繁模式的概念以来，闭合频繁模式挖掘和增量频繁模式挖掘就成为很多人研究的课题。目前增量模式挖掘有两大类，一类是基于先验算法Apriori，另一类是基于频繁模式树算法FP-tree，前者挖掘时间太长，后者维护FP-tree的开销太大。为了降低数据维护和数据挖掘的时间成本，本文提出了一种基于链表的比特流结构，称为Bitlink。Bitlink算法首先选择大于或等于指定阈值的k+Δ个项，合并计数和比特流都相同的项，从合并项中选择k个作为候选项并按降序排序，根据这k个候选进行迭代，最终生成top-k个闭合频繁模式。实验使用OnlineRetail和BMSWebView两个数据集进行模拟，对比实验为 closed frequent patterns by considering anti-monotonic constraint算法（CFPA），实验结果表明Bitlink比CFPA快四分之一。

【关键词】 闭合频繁模式；数据挖掘；滑动窗口；迭代；二进制

一、文献综述

林志杰等人在先验算法Apriori和频繁模式树算法FP-Growth的基础上提出一种数据挖掘方法；Saihua Cai等人在基于反单调约束的条件下提出一种离群点检测方法；Meng Han等人提出一种封闭高效用项集算法，施一飞根据神经网络的特点建立对应的神经网络模型，通过剪枝不频繁项加快数据挖掘速率；Jerry Chun-Wei Lin等人提出一种大规模的信息融合体系结构；Da Yan等人提出一个基于前缀投影思想的通用框-PrefixFPM；Yu等人提出CooMine算法来挖掘闭合模式；Amagata和Hara等人提出CPGraph算法来挖掘共生模式，并通过裁剪一些不必要的模式，有效地获取模式的计数并更新答案；罗旋等人设计异常检测方法，并验证方法的有效性；李洁通过构建频繁项特征并对图数据进行特征检测，从中提取数值属性并建立图数据模型。

上述讨论的方法大多数是基于FP-tree算法进行改进的，而基于FP-tree的算法主要是为交互式挖掘而设计的，但是基于FP-tree改进的相关算法不一定适用于增量式挖掘。有没有针对增量挖掘的算法？由此本文提出一种基于二进制链表的结构，称为BitLink。链表中每个节点都包含三个部分数据，第一部分是项集，第二部分是该项集的计数，第三部分是比特流。该算法通过不同项集之间比特流的与运算来实现模式的增长，在数据的更新与删除阶段只需要简单的对比特流的值进行简单更新即可。

对比现有的方法本文主要有以下创新：1. 提出一种不同于FP-tree的新链表结构，二进制链表；2. 设计基于二进制链表结构的项比特流，比特流与运算更接近计算机底层运算；3. 对本文提出的BitLink算法进行理论分析与实验证明该算法的可行性。

二、二进制链表

（一）频繁模式的基本概念

（二）构造二进制链表

（三）数据挖掘与更新

选出k+Δ个项，其中Δ表示计数可能一样的两个项或者多个项，一共有Δ个项的计数跟其他项的计数一样，这k+Δ个项一共有k个不同的计数值，因为其中有些项的计数是一样的，按照支持度从大到小对这些项顺序排列。

合并同源项，对选出k+Δ个项中计数和项比特流都相同的项进行合并，同源项合并完成后我们选k个计数较大的候选项集，其中这k个候选项集可以包含同源项集。根据选出来k个候选项集按照支持度进行降序排列。自顶向下进行迭代，每一次迭代得出的项集的计数都要跟第k个候选项集的计数进行比较，假如迭代项集的计数比第k个候选项集的计数要大，那么就用迭代项集将第k项候选集代替掉，第k个候选集的阈值迭代项集代替。

随着时间的流逝，部分的数据可能失去时效性，使得对这部分的研究没有意义，而新的数据对于研究意义的重要性更加重大，因此删除失去时效性的数据，获取新到来的数据。对链表进行一次遍历，找到链表中每个项对应的事务数据流，将已经失去时效性的事务ti对应的事务数据流部分删除，假如被删除的比特流包含1，那么将更新相关项的计数，假如被删除的比特流为0，那么相关项的计数不需要更新，有多少个1被删除，相关项的计数就要减多少。为新到的事务创建相关节点信息，项与项之间按照字典递增排序，假如该事务中包含该项，则相应的比特值为1，否则为0，并且对比特流为1的项的相关计数进行累加，对比特流为0的项不做相关操作。整个算法在执行过程中先调用算法1，再调用算法2进行数据挖掘，后期不断地调用算法3和算法2。

（四）性能分析

三、应用实验

（一）实验方法

本节为BitLink算法进行实验，硬件设备为Intel Core i7，内存容量8GB，使用Python实现，对比算法为CFPA。使用数据集OnlineRetail、BMSWebView2进行实验，其中OnlineRetail有541909条事务2603个项，BMSWebView2有77512条事务3340个项。

（二）实验结果

采用top-k作为指标衡量算法的性能，图1和图2是在窗口大小固定为200条数据，top-k从50变化到250，在OnlineRetail和BMSWebView2这两个数据集的时间变化，在窗口大小一样的情况下，top-k越大，要挖掘的数据就越多，所以时间会随着top-k的变大而变大。总体来说，因为BitLink算法比CFPA算法迭代的次数少，所以BitLink所用的整体时间要更少。

四、结语

关于关联规则的数据挖掘已经有很多成熟的算法，比如先验算法、FP-tree算法，先验算法需要多次扫描数据而使得挖掘效率降低，FP-tree算法需要维护一个复杂的树结构而增加了维护成本的开销。本文将数据以简单的存储形式实现，数据的存储形式接近计算机底层，所以提高的算法的效率。对于未来的高维大数据，可以对这些数据进行降维，使得存储实现接近计算机的一维结构，从而提高算法的效率。

参考文献：

［1］ 林志杰，彭珍连，曹步清，等. 一种面向高校学生体测数据的模式挖掘方法［J］. 信息与电脑，2023，35（04）：184-189.

［2］ 施一飞. 分布式多维数据流频繁模式挖掘算法设计［J］. 吉林大学学报：信息科学版，2023，41（1）：174-179.

［3］ 罗旋，罗玮，贺增良，等. 频繁模式的水电信号异常检测［J］. 现代电子技术，2023，46（10）：61-65.

［4］ 李洁. 基于解耦概要图的图数据频繁模式挖掘算法［J］. 内蒙古民族大学学报（自然科学版），2021，36（05）：391-395.