高效检索前K个频繁项集的技术

《Expert Systems with Applications》：Efficient techniques for retrieving top-K Frequent itemsets

本文提出HTK-Miner和HTK-negFIN两种算法，分别基于候选生成和模式增长范式，通过动态调整支持阈值和优化技术，高效挖掘Top-k频繁项集，实验表明其性能优于现有方法。

　　

Konstantinos Malliaridis | Stefanos Ougiaroglou

组织：信息与电子工程系，国际希腊大学 地址：Alexander Campus, 塞萨洛尼基市, 邮编：57400, 中马其顿州, 希腊

摘要

频繁项集挖掘是一种核心的数据挖掘任务，旨在发现事务数据库中的重复模式。传统方法依赖于最小支持度阈值，而这通常难以确定。Top-k挖掘通过检索最常见的k个项集提供了一种实用的替代方案。我们提出了两种新颖的算法：HTK-Miner和HTK-negFIN。HTK-Miner基于等价类理论和广度优先搜索，利用四种操作模式（TS、BSN、DTS和DBSN）。其关键创新在于快速堆（Q-Heap），它可以动态提高支持度阈值，从而实现早期剪枝和加速识别。此外，HTK-Miner只需扫描一次数据库，并采用压缩表示来减少执行时间和内存使用。HTK-negFIN通过将高效的negFIN算法扩展到Top-k框架中，并结合Q-Heap和共享优化来提高性能。在多种基准数据集上的实验表明，我们提出的算法在运行时间和内存效率方面均显著优于现有方法。

引言

频繁模式挖掘是数据挖掘中的基本操作，能够完成关联规则挖掘、相关性分析、序列模式发现以及分类和聚类等关键任务（Pei等人，2007年）。在事务数据库中，模式也称为频繁项集，是指频繁共同出现的项的子集。在本文中，我们统一使用“频繁项集”这一术语。频繁项集挖掘最初由Agrawal、Imieliński和Swami（1993年）提出，用于市场篮子分析，旨在解决关联规则挖掘问题。自那时起，已经提出了许多相关算法。人们对频繁项集挖掘持续感兴趣的一个主要原因是其计算复杂性较高。即使对于中等规模的数据集，搜索空间也可能变得非常庞大，并且在密集数据集中呈指数级增长（Aggarwal、Bhuiyan和Hasan，2014年）。

大多数频繁项集挖掘（FIM）算法需要一个最小支持度阈值作为输入参数，该参数指定了项集必须在给定数据集中出现的最小交易次数。这个参数可以定义为绝对值（即确切的交易数量），也可以定义为相对值——包含该项集的交易数量与总交易数量的比例。

尽管已经提出了高效的算法，但确定适当的最小支持度阈值仍然具有挑战性。过低的阈值可能会导致大量频繁项集的产生，从而增加计算成本；而过高的阈值则可能产生很少甚至没有频繁项集，阻碍用户探索和分析。

为了解决这个问题，后来提出了基于排名k的算法，该参数指示要发现的最频繁项集的位置。这样更容易检索到排名靠前的频繁项集，而无需猜测会产生类似结果的最小支持度阈值。然而，Top-k排名方法并不总是最有效的参数，因为研究人员通常更直接请求前k个最频繁的项集，而不是依赖它们的排名。

从操作角度来看，FIM算法主要分为两类：候选项生成和模式增长。候选项生成算法主要基于称为Apriori原理的反单调性质（Agrawal等人，1993年首次提出）。根据处理数据的方式，它们进一步分为按交易逐个扫描数据集的算法（水平表示）和构建垂直表示的算法，在这种表示中，每个项集都与它出现的交易列表（tidset）相关联。另一方面，模式增长算法使用专门的树结构以压缩格式存储初始数据，形成频繁项集链。然后递归遍历这些结构，创建树状投影或基于列表的表示，用于发现频繁项集及其支持度。这一类别中第一个提出的算法是FP-Growth（Han、Pei和Yin，2000年），随后出现了许多采用最小支持度阈值的算法。代表性算法包括Pei等人（2007年）、PREPOST（Deng、Wang和Jiang，2012年）、FIN（Deng和Lv，2014年）以及negFIN（Aryabarzan、Minaei-Bidgoli和Teshnehlab，2018年）。此外，还有一些模式增长算法被实现了Top-k排名方式，例如NTK（Deng，2014年）、CRM（Pyun和Yun，2014年）、iNTK（Huynh-Thi-Le、Le、Vo和Le，2015年）以及BTK（Dam、Li、Fournier-Viger和Duong，2016年）。

FIM算法还可以根据搜索策略分为广度优先和深度优先两种方法。广度优先算法（如Apriori）逐层探索搜索空间，在进入下一层之前生成并评估所有给定长度的候选项集。相比之下，深度优先算法（如FP-Growth（Han等人，2000年）和Eclat（Zaki，2000年）会尽可能深入地遍历搜索树的每个分支，从而通常实现更快的执行速度和更低的内存使用。

为了全面研究Top-k挖掘的效率，本文提出了两种不同的算法，代表两种主要的FIM范式：HTK-Miner是一种基于垂直数据表示和等价类理论的候选项生成方法；HTK-negFIN是一种利用专门的NegNodeset结构的模式增长方法。开发这两种算法的动机在于Top-k挖掘中最小支持度阈值的动态性质；通过实现这两种算法，我们旨在评估哪种范式在阈值增加时具有更好的剪枝能力和稳定性。这两种算法都采用了轻量级的Q-Heap结构和新颖的加速技术，用于快速提高支持度阈值并最小化搜索空间探索。最后，我们提供了与BTK和negFIN等现有方法的全面比较分析，根据数据集的密度和规模明确了最佳挖掘策略。

本文的其余部分组织如下：第2节回顾了频繁项集挖掘领域的相关工作和背景。第3节定义了问题及其必要的预备知识。第4节介绍了HTK-Miner算法，详细说明了其核心结构和实现方式，以高效发现Top-k频繁项集。第5节介绍了基于negFIN的HTK-negFIN算法。第6节介绍了挖掘过程的复杂性分析。第7节报告了实验结果。最后，第8节总结了本文并指出了未来研究的方向。

相关工作和背景

FIM的目标是发现事务数据集中频繁一起出现的项组合。由于其广泛应用，包括生物信息学、文本挖掘、产品推荐和网络点击流分析，FIM已成为一个重要的研究领域（Fournier-Viger等人，2017年）。此外，Top-k频繁项集挖掘为现代AI应用提供了重要的基础支持，包括智能推荐和行为模式分析

预备知识

设$I=\{i_1,i_2,..,i_n\}$ $I=\{i_1,i_2,.,i_{\mathrm{n}}\}$ 设数据D是一组交易t₁, t₂, ..., t_m，其中每个交易t∈D是一组项i₁, i₂, ..., i_t的列表，且i₁ ≤ i_n ? I。

定义1 项集/模式：

一组项x?I称为项集或模式。一个包含l个项的项集称为l项集。

项集x的支持度，表示为sup(x)或|x|，定义为x作为子集出现的交易数量：

定义2 最小支持度阈值：

设minSup(0 ≤ minSup ≤ m)，其中m为

算法概述

HTK-Miner是一种频繁项集挖掘算法，旨在高效发现前k个最频繁的项集，而无需预定义最小支持度阈值。该算法基于垂直数据库表示（VR），其中每个项集都与一个tidset相关联。tidset是该项集出现的交易ID列表。这种表示方式允许通过tidset交集来计算支持度，从而无需复杂的候选结构。

HTK-Miner在

HTK-negFIN算法

在本节中，我们介绍了HTK-negFIN，它是negFIN算法（Aryabarzan等人，2018年）的扩展，用于频繁项集挖掘。尽管negFIN使用最小支持度阈值，但HTK-negFIN引入了一个关键修改：它接受一个k参数值来发现前k个最频繁的项集，这与第4节中介绍的HTK-Miner算法的方法一致。

复杂性分析

在本节中，我们提供了正式的复杂性分析。我们的分析主要集中在HTK-Miner的BSN模式上，因为第7.2节的实验结果表明这种配置在Top-k搜索空间探索中表现最佳。至于HTK-negFIN，它使用了从原始negFIN算法继承的专门NegNodeset数据结构，而不是HTK-Miner的多模式表示。

实验结果与分析

我们进行了两组实验。在第一组实验中，比较了HTK-Miner的四种模式（VR with TS、BSN、DTS和DBSN，见第4.5节）在运行时间和内存消耗方面的性能。在第二组实验中，将HTK-Miner和HTK-negFIN相互比较，同时也与BTK（Dam等人，2016年）进行了比较。为了评估它们的整体性能，我们还包含了negFIN（Aryabarzan等人，2018年），该算法需要最小支持度阈值。

结论

本文提出了两种算法HTK-Miner和HTK-negFIN，以解决高效发现前k个最频繁项集的挑战。HTK-Miner基于等价类理论和广度优先候选项生成策略，利用垂直数据结构。其核心优势在于灵活性，提供了四种操作模式（TS、BSN、DTS和DBSN），并包含了一系列强大的优化措施，包括用于快速估计支持度的Q-Heap。

CRediT作者贡献声明

Konstantinos Malliaridis：概念化、方法论、软件开发、验证、形式分析、调查、数据整理、初稿撰写、审阅与编辑、可视化。Stefanos Ougiaroglou：概念化、方法论、验证、形式分析、审阅与编辑、监督、项目管理。

利益冲突声明

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

在准备本文的过程中，作者使用了AI工具来使其更加简洁和正式。使用该工具/服务后，作者根据需要审阅和编辑了内容，并对出版物的内容负全责。