NiaAutoARM: Automated generation and evaluation of Association Rule Mining pipelines

基本信息

• 论文ID: 2501.00138
• 标题: NiaAutoARM: Automated generation and evaluation of Association Rule Mining pipelines
• 作者: Uroš Mlakar, Iztok Fister Jr., Iztok Fister (University of Maribor, Slovenia)
• 分类: cs.NE (Neural and Evolutionary Computation), cs.AI (Artificial Intelligence)
• 发表时间: 2024年12月30日 (arXiv预印本)
• 论文链接: https://arxiv.org/abs/2501.00138

摘要

数值关联规则挖掘(Numerical Association Rule Mining, NARM)范式能够同时处理数值和分类属性，对于从包含两种特征类型的数据集中发现关联关系非常有益。然而，该过程并不简单，因为它包含多个顺序执行的处理步骤来形成完整的管道，如预处理、算法选择、超参数优化和评估关联规则质量的指标定义。本文提出了一种新颖的自动机器学习方法NiaAutoARM，基于随机种群元启发式算法自动构建完整的关联规则挖掘管道。除了方法的理论表示，论文还提供了对所提方法的全面实验评估。

研究背景与动机

1. 问题定义

关联规则挖掘(ARM)是一种用于发现事务数据库中项目间关系的机器学习方法。传统的ARM仅限于处理分类属性，而数值关联规则挖掘(NARM)作为ARM的变体，能够同时处理数值和分类属性，从而消除了传统ARM的瓶颈。

2. 问题重要性

• 民主化需求: 自动机器学习(AutoML)旨在让非专业用户也能使用ML方法，避免"人在环中"的原则
• 复杂性挑战: ARM管道包含多个复杂组件：数据预处理、算法选择、超参数优化、评估指标选择和评估
• 无通用解: 根据No Free Lunch定理，不存在适用于所有数据集的通用ARM元启发式算法

3. 现有方法局限性

• 手动构建ARM管道需要大量人工干预，耗时且复杂
• 现有研究对ARM预处理步骤关注不足
• 缺乏专门针对ARM管道自动构建的AutoML方法

4. 研究动机

基于NiaAML方法的启发，将ARM管道构建问题建模为连续优化问题，使用种群元启发式算法自动搜索最优管道配置。

核心贡献

1. 首创性: 提出第一个专门用于ARM管道自动搜索的AutoML解决方案，将自动搜索表示为优化问题
2. 预处理关注: 特别关注ARM预处理步骤，弥补了近期研究工作的不足
3. 实现框架: 实现了名为NiaAutoARM的Python包，提供完整的实用工具
4. 全面评估: 在多个数据集上对所提方法进行了严格的实验评估

方法详解

任务定义

将ARM管道构建定义为连续优化问题，其中每个个体代表一个可行的ARM管道配置，包括：

• 算法选择
• 超参数设置
• 预处理方法
• 评估指标及权重

模型架构

1. 解表示

每个个体 $x_i^{(t)}$ 表示为：

$x_i^{(t)} = \langle x_{i,1}^{(t)}, y_{i,1}^{(t)}, y_{i,2}^{(t)}, p_{i,1}^{(t)}, \ldots, p_{i,P}^{(t)}, z_{i,1}^{(t)}, \ldots, z_{i,M}^{(t)}, w_{i,1}^{(t)}, \ldots, w_{i,M}^{(t)} \rangle$

其中：

• $x_{i,1}^{(t)}$: 算法选择
• $y_{i,1}^{(t)}, y_{i,2}^{(t)}$: 超参数(种群大小NP, 最大评估次数MAXFES)
• $p_{i,1}^{(t)}, \ldots, p_{i,P}^{(t)}$: 预处理方法
• $z_{i,1}^{(t)}, \ldots, z_{i,M}^{(t)}$: 评估指标
• $w_{i,1}^{(t)}, \ldots, w_{i,M}^{(t)}$: 指标权重

2. 组件设计

算法池: 包括PSO、DE、GA、LSHADE、ILSHADE、jDE等6种元启发式算法

预处理方法:

• Min-Max标准化(MM)
• Z-Score标准化(ZS)
• 数据压缩(DS)
• 移除高相关特征(RHC)
• K-means离散化(DK)

评估指标: 支持度、置信度、覆盖度、幅度、包含度、可理解性

3. 适应度函数

NiaAutoARM使用公平性适应度函数：

$f(x_i^{(t)}) = \frac{\alpha \cdot supp(X \Rightarrow Y) + \beta \cdot conf(X \Rightarrow Y)}{\alpha + \beta}$

其中α和β表示不同ARM指标对解质量的影响。

技术创新点

1. 双层优化结构: 外层元启发式控制内层算法的行为，搜索最优配置
2. 自适应权重: 支持ARM指标权重的动态调整
3. 多预处理组合: 允许选择多个预处理方法的组合
4. 连续优化建模: 将离散的管道构建问题转化为连续优化问题

实验设置

数据集

使用10个UCI机器学习数据集进行评估：

评价指标

• 适应度值（支持度和置信度的加权平均）
• 生成规则数量
• 算法选择频率
• 预处理方法使用频率

对比方法

与VARDE（Variable-length Association Rule mining using Differential Evolution）最新算法进行间接比较。

实现细节

• 外层算法：DE和PSO
• 种群大小：NP = 30
• 最大适应度评估次数：MAXFES = 1000
• 独立运行次数：30次
• 内层算法超参数范围：NP ∈ 10, 30, MAXFES ∈ 2000, 10000

实验结果

主要结果

1. 基线实验

• 预处理选择: Min-Max标准化(MM)、Z-Score标准化(ZS)和无预处理被最频繁选择
• 指标偏好: 支持度和置信度在几乎所有管道中都存在
• 算法选择: PSO和jDE作为内层优化算法被最频繁选择
• 超参数: 复杂数据集(如Buying、German、House16)倾向于选择较高的NP值

2. 权重自适应实验

启用ARM指标权重自适应后：

• 适应度值略有提升（虽然Wilcoxon检验p值=0.41，差异不显著）
• 权重值呈现动态分布，支持度和置信度仍保持较高权重
• 幅度和可理解性指标使用频率较低

3. 多预处理方法实验

允许选择多个预处理方法时：

• PSO: 最频繁组合为{MM,RHC}和单独的MM
• DE: 最频繁组合为{RHC,ZS}、{MM,RHC,ZS}和单独的RHC
• DE算法产生的管道适应度值略高，PSO生成更多规则

4. 与VARDE比较

Wilcoxon符号秩检验结果显示：

• 在多种配置下，NiaAutoARM生成的管道显著优于VARDE
• 特别是在启用权重自适应和多预处理方法时表现更佳

消融实验

通过逐步启用不同功能验证了各组件的贡献：

1. 基线配置（单预处理，无权重自适应）
2. 启用权重自适应
3. 启用多预处理方法选择

计算复杂度分析

平均执行时间在15,000-40,000秒范围内，虽然计算复杂度较高，但考虑到自动化带来的便利性，这是可接受的权衡。

相关工作

AutoML领域

• NiaAML: 基于自然启发算法的分类管道自动构建
• NiaAML2: 改进版本，将管道构建和超参数优化分为两个独立阶段
• 通用AutoML: TPOT、Auto-sklearn等框架主要针对分类和回归任务

ARM领域

• NiaARM: 实现ARM-DE算法的Python框架
• 传统ARM: 主要处理分类属性
• NARM: 能够同时处理数值和分类属性的改进版本

技术差异

NiaAutoARM是首个专门针对ARM管道自动构建的AutoML方法，填补了该领域的空白。

结论与讨论

主要结论

1. NiaAutoARM能够有效自动构建高质量的ARM管道
2. PSO作为内层算法表现最佳，Min-Max标准化是最受青睐的预处理方法
3. 支持度和置信度是ARM中的核心指标
4. 与现有最先进方法相比，该框架展现出优越性能

局限性

1. 计算复杂度: 由于迭代优化和多种预处理组合探索，计算成本较高
2. 评估指标: 目前主要基于支持度和置信度的组合，可能不适用于所有应用场景
3. 数据集规模: 实验主要在中小规模数据集上进行，大规模数据集的表现有待验证
4. 算法池限制: 内层算法池相对有限，可能错过其他有效算法

未来方向

1. 算法扩展: 集成更多具有自适应参数调整的自然启发算法
2. 预处理增强: 纳入更多高级预处理技术和特定领域指标
3. 并行计算: 探索并行和分布式计算策略以降低计算复杂度
4. 多目标优化: 扩展框架支持多目标优化，探索冲突指标间的权衡

深度评价

优点

1. 创新性强: 首次将AutoML应用于ARM领域，填补重要空白
2. 方法完整: 涵盖从预处理到评估的完整管道优化
3. 实验充分: 在多个数据集上进行了全面的实验验证
4. 实用价值高: 提供了完整的Python实现，便于实际应用
5. 理论基础扎实: 基于成熟的元启发式优化理论

不足

1. 计算效率: 双层优化结构导致计算成本较高
2. 可扩展性: 在大规模数据集上的性能表现未充分验证
3. 比较局限: 与VARDE的比较是间接的，缺乏更多基线方法对比
4. 参数敏感性: 对外层算法参数设置的敏感性分析不足

影响力

1. 学术贡献: 开创了AutoARM这一新的研究方向
2. 实用价值: 降低了ARM应用的技术门槛，促进方法普及
3. 可复现性: 提供开源实现，便于后续研究
4. 扩展潜力: 为相关领域的自动化研究提供了参考框架

适用场景

1. 中小规模数据集: 特别适合属性数量和实例数量适中的数据集
2. 混合属性数据: 同时包含数值和分类属性的数据集
3. 非专业用户: 缺乏ARM专业知识但需要进行关联分析的用户
4. 快速原型: 需要快速构建和测试ARM管道的研究场景

参考文献

论文引用了25篇相关文献，主要涵盖：

• AutoML相关工作（Yao et al., Hutter et al., He et al.）
• 进化计算基础（Eiben & Smith, Blum & Merkle）
• 具体算法实现（Storn & Price for DE, Kennedy & Eberhart for PSO）
• 相关框架（NiaPy, NiaARM, NiaAML系列）

总体评价: 这是一篇高质量的研究论文，在AutoML和ARM的交叉领域做出了重要贡献。虽然在计算效率和大规模数据处理方面还有改进空间，但其创新性、完整性和实用价值使其成为该领域的重要里程碑工作。