定制关联规则的增量提取

《Knowledge-Based Systems》：Incremental Extraction of Bespoke Association Rules

提出基于层次框架的关联规则挖掘方法，通过整合用户偏好和结构最大化，提升可扩展性并发现传统方法忽略的复杂模式。

　　

金英熙（Eung-Hee Kim）| 金洪吉（Hong-Gee Kim）| 黄淑亨（Suk-Hyung Hwang）

大数据融合与开放共享系统，首尔国立大学，韩国首尔冠岳区冠岳路1号，邮编08826

摘要

关联规则挖掘是发现事务数据库中共现模式的基本技术。然而，传统方法往往难以捕捉复杂的用户偏好，这限制了它们在需要表达性强的事前条件和上下文感知的后验条件的应用场景中的实用性。我们提出了lode模型，这是一个分层框架，它结合了用户定义的偏好，并明确表示了关联规则之间的关系。“lode”一词隐喻性地表示了一条富含价值信息的矿脉，反映了我们逐步揭示大规模事务数据中嵌入的模式的目标。该框架的核心是挖掘算法，它通过逐步提取有信息量的后验条件，并利用父子关系来提高可扩展性和可解释性。通过将支持度和置信度与用户特定的约束条件相结合，该算法能够发现定制的关联规则，以满足多样化的分析需求。在多个真实世界数据集上的实验证明了该框架的计算效率、可扩展性以及揭示传统方法经常忽略的模式的能力。

引言

关联规则挖掘（ARM）由Agrawal和Srikant在1993年提出，旨在发现满足用户指定阈值（minsupp, minconf）的支持度和置信度的蕴含规则X_i?X_j [1]。在部署的系统中，前提条件X_i通常作为描述用户上下文的查询，而后验条件X_j则作为解决方案返回，例如推荐产品、行动或诊断结果。这一范式支持心脏病风险的临床决策支持[2]、将症状与COVID-19趋势联系起来的疫情监测[3]以及大规模电子商务分析[4]。尽管这些应用展示了经典的“项集前提?项集后验”模型的实际价值，但它们也凸显了对更丰富的前提条件和更快速更新周期的日益增长的需求。

Web规模的服务进一步说明了这种矛盾。亚马逊的“购买过X_i的用户也购买了X_j”面板依赖于市场篮子规则[5]；Netflix将基于规则的信号整合到商品推荐和搜索中[1]；而Google搜索允许使用诸如-keyword或site:等布尔式筛选条件[2]。这三项服务都需要足够表达性的前提条件来描述详细的用户意图，以及能够适应快速变化的数据的后验条件。持续的插入、删除和修改使得批量ARM流程很快就会过时，因此需要基于用户特定偏好的实时提取。

为了解决这些挑战，先前的研究沿着四个主要方向进行了探索[6], [7], [8], [9]。面向效率的方法引入了先进的数据结构或分布式执行策略（例如FP-Growth的变体[10]）。注重冗余的方法构建了紧凑的规则库，如CauRuler[11]。其他研究通过包含模糊逻辑、布尔逻辑或模态逻辑规则[12], [13]来丰富前提条件。增量和top-k框架在流式更新下保持规则列表的更新[14]。个性化或混合系统——包括基于偏好的挖掘[12]、像PyAerial[15]这样的神经符号管道以及基于元启发式搜索的引擎如NiaARM[16]——通过引入各种形式的适应性和表达性扩展了这一领域。第2.2节将对这些工作进行了详细讨论。

尽管有如此广泛的研究成果，但目前还没有现有的框架能够（i）直接根据用户偏好来调整证据，（ii）保证结果集无冗余且满足包含性最大化，以及（iii）在统一的偏序模型内支持分层、渐进式的探索。这些属性对于可扩展的定制规则提取至关重要，但它们之前尚未被结合到一个单一的数学结构或算法流程中。由此产生的检索问题需要根据支持度和置信度对候选后验进行排序，无需预先构建的索引，并且能够快速响应以跟踪持续的更新。本研究通过（i）允许使用表达性强的偏好语句而不是简单的项集，（ii）支持每个查询的阈值（minsupp, minconf和top-k），以及（iii）直接在当前数据库状态下操作，从而扩展了经典的ARM。

• 前提条件泛化：将前提条件扩展到用户的具体偏好，并由专门的$〈\mathrm{解析器}和\mathrm{解释器}$
• 有信息量的后验：在相同证据下，形式化一个无冗余的结果集，仅保留满足包含性最大化的模式。
• lode模型：将有信息量的后验组织成一个偏序，支持分层、父子遍历，以实现可扩展的探索。
• 挖掘算法：利用这种结构，采用分层top-k策略，在动态的、用户指定的阈值下实时提供定制规则。

本文的其余部分结构如下。第2节回顾相关工作并进行概念定位。第3节开发lode模型及其组件。第4节介绍挖掘算法。第5节描述实现和实验评估。第6节讨论研究结果的意义，第7节总结未来的研究方向。

节选

初步介绍

事务数据库是一个三元组，其中T是一组事务，I是一组项目，R?T×I是一个表示成员关系的二元关系[17]。一对(t, i)∈R表示事务t包含项目i。表1-2展示了运行示例的横向（以事务为中心）和纵向（以项目为中心）表示；这两种视图描述了相同的结构，但支持不同的挖掘策略。

一个关联规则X_i?X_j由两个不相交的项集X_i, X_j?I组成

Lode模型

在本节中，我们介绍了lode模型，这是一个用于逐步提取有信息量的定制关联规则的分层框架。如图1所示，该模型使用挖掘的隐喻来传达有信息量后验的结构组织。虽然这些隐喻性术语旨在提供直观的洞察，但每个术语都直接对应于关联规则挖掘中的一个标准概念。为了确保概念清晰，表3提供了它们之间的精确映射

挖掘算法

挖掘算法通过遍历有信息量后验的分层结构来逐步提取定制的关联规则。如图3所示，该过程包括三个核心函数：excavateAdits、excavateStopes和mineConsequents。excavateAdits函数通过识别最通用的有信息量后验（adits）来启动这一过程。excavateStopes函数随后通过发现其子后验（stopes）来扩展每个adit。在这两个步骤的核心是

实现与实验

为了验证所提出的lode模型和挖掘算法，我们实现了整个框架，并在几个真实世界数据集上评估了其性能。实现过程忠实再现了lode模型指定的分层提取过程，使用挖掘算法逐步推导出符合复杂用户偏好的有信息量关联规则。本节的组织结构如下：第5.1节描述了实现细节，包括代码

讨论

第5.3节中的定量实验表明，挖掘过程在不同大小的数据集上的运行时间和内存消耗具有可预测的扩展性。现在我们转向使用MovieLens进行定性分析，以展示表达性强、基于偏好的前提条件如何揭示在仅基于集合的前提条件下会隐藏的行为结构。为此，我们固定了项目“The Shawshank Redemption”，并通过对相反条件的设定来定义两种对比鲜明的偏好

结论

本研究提出了lode模型和挖掘算法，这是一个用于根据用户定义的偏好逐步提取定制关联规则的分层框架。该方法将偏好感知的支持度和置信度与基于相同证据下的结构最大化信息量的标准相结合，从而能够系统地识别简洁且无冗余的后验条件。

在三个真实世界数据集（OnlineRetail II）上进行了全面的实验

未引用的参考文献

算法1、算法2、算法3、表5、图4、图5、图6和表5

CRediT作者贡献声明

金英熙（Eung-Hee Kim）：撰写——原始草稿、方法论、形式分析、数据整理、概念化。金洪吉（Hong-Gee Kim）：撰写——审阅与编辑、验证、监督。黄淑亨（Suk-Hyung Hwang）：撰写——审阅与编辑、监督、资源管理、项目协调、资金获取。

利益冲突声明

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

致谢

本项工作得到了信息与通信技术规划与评估研究所（IITP）-创新人力资源开发地方知识化计划的支持，该计划由韩国政府（MSIT）资助（IITP-2025-RS-2024-00436765）