一种基于滑动窗口矩阵的流数据高效用项集挖掘算法

《Data & Knowledge Engineering》：A matrix-based high-utility itemsets mining algorithm over streaming data using sliding windows

　　

摘要

从大规模数据集中获取有价值的信息长期以来一直是大数据领域的核心研究焦点。近年来，随着计算机科学和物联网的快速发展，各种数据以数据流的形式不断生成。数据流中的数据具有无限规模和快速更新的特点，使得从中获取有用信息成为数据挖掘中至关重要的研究课题。在工业产品质量检测和电网数据管理等工程应用场景中，数据表现出密集且无限体量的特征。因此，如何在数据流场景下有效处理密集数据集已成为一个亟待解决的问题。针对这一问题，本研究提出了一种名为PFUMS（前缀无关效用矩阵流，Prefix-free Utility-Matrix Stream）的算法，该算法采用稀疏矩阵结构来简化项目集的合并过程，同时占用更少的内存。此外，该算法在连接过程中采用了前缀无关项目集扩展方法和两阶段局部效用修剪策略。该修剪策略可以在不等待项目集完全扩展的情况下及时修剪无前景的项目集，从而有效减少扩展阶段的搜索空间。在整个过程中，使用向量指针和映射来维护必要的数据。此外，在窗口滑动过程中，全局变量保留两个窗口的公共部分数据不被清除，从而减少新窗口中的数据扫描时间。实验结果表明，该算法在密集数据集上保持了优异的性能。

引言

近几十年来，随着计算机技术的进步和海量数据的产生，如何从大规模数据集中提取有价值的信息成为了一个极具挑战性的问题——而这恰恰是数据挖掘领域的一个关键研究方向。最初，研究工作的重心主要集中在频繁项目集挖掘上，这是一种旨在识别数据库中发生频率超过预设阈值的项目和项目集的方法。频繁项目集挖掘（FIM）[1]的出现为从海量数据中提取重要信息建立了一种新的范式。然而，该方法存在固有的局限性。FIM主要关注项目集在数据库中的出现频率，而忽视了二元存在/缺失指示符所伴随的内部效用（如项目利润）和外部效用（如出现次数），这些效用在真实世界的数据系统中是普遍存在的。因此，FIM只能识别高频项目集，而无法发现具有重大经济意义的高效用项目集。

为解决频繁项目集在实际应用中面临的问题及其固有的挖掘局限性，高效用项目集挖掘（HUIM）应运而生，旨在发现事务性数据库中具有显著效用值的项目集[2]、[3]。近年来，高效用项目集挖掘已发展成为前沿数据分析领域中一个成熟的研究领域——伴随着显著的理論进展和跨学科的实践应用。HUIM已被广泛应用于网络数据流点击分析[4]、电子商务[5]、[6]和物联网[7]。

虽然高效用项目集挖掘能够有效地在静态数据库中发现所有重要的效用模式，但在处理由传感器网络、零售连锁和网络点击流等动态来源产生的流数据时，它表现出根本性的局限性。在处理无限长度的数据流时，人们往往优先考虑最近的数据段，而忽略过时信息。数据流的信息处理被分为三种模型：衰减窗口模型[8]、[9]、标记窗口模型[10]和滑动窗口模型[11]、[12]、[13]。衰减窗口模型根据数据的时效性分配不同的权重：在当前窗口中，较新的数据具有较高权重，而较旧的数据具有较低权重。标记窗口模型将标记节点设为数据流的起始点，并处理此后到达的所有数据。滑动窗口模型保持固定的窗口大小，通常被划分为一组固定数量的批次——每个批次持有特定数量的事务。完成挖掘过程后，窗口通过丢弃最旧的批次并纳入最新的批次来前进并更新其内容。在每次窗口更新后开始后续的挖掘迭代，循环此周期性过程。滑动窗口模型是处理数据流最常用的模型。

自Apriori算法[14]引入以来，HUIM一直专注于简化修剪[1]和合并[15]过程。它们使用更紧的上界对项目集进行更精细的修剪，并采用各种改进的效用列表结构来加速合并。然而，这些修剪策略在实现中严重依赖效用列表来存储相应数据，并且在运行过程中搜索效用列表的操作消耗了大量的计算资源和内存。此外，传统合并操作[16]、[17]需要扫描来自三个项目集的数据以合并为更长的项目集。在这种方法中，合并过程必须始终考虑小项目集之间的公共部分，还需要在合并为更长的项目集时消除重复项目集的影响。这种合并方法不仅在合并开始时需要扫描更多的数据，而且在合并过程中还需要额外的计算和判断。结果导致了不必要的资源浪费，并影响了算法的运行效率。

为了解决上述挑战，我们提出了一种在数据流上进行前缀无关扩展和效用矩阵的高效用项目集挖掘算法，称为PFUMS。前缀无关扩展方法仅需要两个项目集的数据进行扩展而不需要公共部分，从而消除了引入第三个项目数据的需求。独特的矩阵结构还允许在合并过程中使用与运算而不是重复扫描事务来快速实现项目集扩展。此外，所提出的方法结合了一种专门为矩阵结构设计的全新两阶段局部修剪策略。两阶段修剪策略分别在合并过程之前和合并过程中发挥作用，减少候选项目集的数量，并能够在合并过程中及时识别和修剪无前景的项目集，从而提高算法的运行速度。该算法的主要贡献如下。

1. 提出一种稀疏矩阵数据存储结构来替代传统的效用列表结构，通过逻辑与运算，该结构增强了项目集合并过程中搜索相同事务的效率。
2. 开发了一种前缀无关扩展方法，以减少项目集合并过程中所需的项目集数量。前缀无关扩展方法通过将当前项目集与一个单项目集合并来实现项目集的扩展，从而避免了产生公共部分，进而消除了对第三个项目集信息的需求。
3. 引入了一种无自嵌套扩展方法，使用向量和指针来维护扩展后的项目集。为了解决传统自嵌套扩展方法导致的内存使用过多的问题，该算法采用循环方式来实现项目集的扩展过程。
4. 为了解决效用列表修剪策略无法应用的问题，设计了针对效用矩阵和自嵌套迭代的两阶段修剪策略，从而提高了搜索效率。两阶段修剪分别作用于项目集扩展之前和合并期间。它可以有效减少内存使用，避免不必要的合并过程，并加速算法的进展。
5. 全面的实验评估：我们在六个数据集上进行了大量实验，将我们的算法与最先进的方进行对比评估，提供了关于执行时间、内存消耗和连接操作数量的详细对比分析。

本文后续章节描述如下：第2节详细阐述了高效用项目集挖掘的发展背景以及数据流场景下算法的演进历程。第3节介绍了PFUMS中的相关定义。第4节描述了PFUMS中的基本数据结构、前缀无关扩展方法、连接操作、两阶段局部效用修剪策略以及窗口滑动过程中的数据更新维护方法。第5节在六个数据集上进行了全面的实验评估，将所提出的算法的性能与最先进的方法进行了对比。第6节总结了所提出算法的性能、优缺点；最后，提出了未来研究中的进一步优化方向。

片段：高效用项目集挖掘

HUIM算法可根据其各自的挖掘流程分为两阶段和单阶段两种类型。Apriori[14]算法是频繁项目集挖掘的一种创新方法，属于两阶段算法类别。然而，由于其缺乏有效的修剪策略，导致了过大的搜索空间并降低了运行效率。而且它只能发现高频项目集，无法获得高效用项目集。

片段：预备知识

数据流被正式定义为DS={T?, T?……, T?}，其中T?定义为数据流中第k个到达的事务。设I={i?, i?,……i?}为数据流中出现的所有项目的集合。因此，每个事务T由从I中选出的不同项目组成。在发现高效用项目集时，多个项目的组合是关注的核心。我们正式将多个项目的集合定义为模式P={i?, i?,……i?}（也称为一个……

片段：所提出的算法

本章提出了一种针对数据流的高效用项目集挖掘深度优先方法，命名为PFUMS。采用稀疏矩阵结构来存储关键挖掘相关信息，与效用列表相比占用显著更少的内存。此外，引入了基于矩阵的连接操作和前缀无关扩展方法，使得项目集扩展不需要自嵌套操作。另外，两阶段局部效用修剪……

片段：实验

PFUMS的实验评估基于开源SPMF库进行，所有Java代码使用OpenJDK 23.0.2编译。实验在一台配备AMD Ryzen 9 7940HX CPU、32 GB内存和Windows 11操作系统的笔记本电脑上执行。

结论

本文提出了一种名为PFUMS的算法，旨在在数据流中挖掘高效用项目集。该算法使用稀疏效用矩阵结构来存储项目集的iu和ru值。与传统的全零矩阵相比，它占用的内存更少，并且由于其矩阵结构，可以使用与运算来快速实现项目集的合并过程。此外，提出了一种前缀无关扩展方法，使得扩展过程可以通过……

CRediT作者贡献声明

李谷丰：撰写——原始草稿，方法论，概念设计。张晓凯：撰写——原始草稿，软件，数据整理。王华科：撰写——审阅与编辑，验证，形式化分析。尚涛：撰写——审阅与编辑，监督，项目管理。

利益冲突声明

作者声明他们没有已知的可能影响本文所报告工作的竞争经济利益或个人关系。

致谢

本工作部分得到中央高校基本科研业务费、西安电子科技大学创新基金[项目编号YJSJ26004]、西安电子科技大学杭州工商学院概念验证基金[项目编号GNYZ2024GY004]以及国家自然科学基金[项目编号62301410]的支持。

李谷丰，2015年、2018年和2022年分别在西安电子科技大学获得通信工程、软件工程和信息与通信工程专业的工学学士、工学硕士和博士学位。目前是西安电子科技大学杭州工商学院的副研究员。他的研究兴趣包括数据挖掘、异构信息处理和智能信号处理。

李谷丰 | 张晓凯 | 王华科 | 尚涛
西安电子科技大学杭州工商学院，杭州，311231，浙江省，中国