用哈希加速模式集选择，效率提升显著且结果接近最优。
Hashing for Fast Pattern Set Selection
- 基于bottom-k哈希快速筛选高质量模式集。
- 在合成与真实数据上速度远超传统贪心算法，误差几乎相同。
- 适用于数据库拼贴、布尔矩阵分解等场景，适合大数据处理需求。
模式集挖掘是数据挖掘中的基础问题，目标是从所有模式中选出一个优质集合而非全部。近年来提出了多种衡量集合优劣的标准。本文以重构误差作为集合质量的代理指标，重点解决高效寻找优质集合的问题。提出一种基于bottom-k哈希的方法，用于快速选择模式集，并将其扩展至模式在数据中仅以近似形式出现的常见情况。该方法在数据库拼贴、布尔矩阵分解、重新描述挖掘等领域具有应用价值。实验表明，相比标准贪心算法，本方法在合成与真实数据集上均显著更快，同时获得几乎相当的重构精度。
原文摘要 · Abstract (English)
Pattern set mining, which is the task of finding a good set of patterns instead of all patterns, is a fundamental problem in data mining. Many different definitions of what constitutes a good set have been proposed in recent years. In this paper, we consider the reconstruction error as a proxy measure for the goodness of the set, and concentrate on the adjacent problem of how to find a good set efficiently. We propose a method based on bottom-k hashing for efficiently selecting the set and extend the method for the common case where the patterns might only appear in approximate form in the data. Our approach has applications in tiling databases, Boolean matrix factorization, and redescription mining, among others. We show that our hashing-based approach is significantly faster than the standard greedy algorithm while obtaining almost equally good results in both synthetic and real-world data sets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。