Itemset mining: A constraint programming perspective
Itemset mining: A constraint programming perspective
复制标题
DOI：
10.1016/j.artint.2011.05.002
复制
发表时间：
2011-08
期刊：
影响因子：
--
通讯作者：
Tias Guns;Siegfried Nijssen;L. D. Raedt
中科院分区：
文献类型：
--
作者：
Tias Guns;Siegfried Nijssen;L. D. Raedt
数据挖掘领域已经习惯于指定对感兴趣模式的约束。已经开发了大量的系统和技术来解决这种基于约束的挖掘问题，特别是针对挖掘项集。在数据挖掘领域采取的方法与人工智能社区内制定的约束编程原则形成了鲜明对比。虽然大多数数据挖掘研究集中在算法问题上，并旨在开发针对特定任务量身定做的高度优化和可伸缩的实现，但约束编程采用了更具声明性的方法。重点在于开发高级建模语言和通用解算器，这些语言和通用解算器指定问题是什么，而不是概述解决方案应该如何计算，但又足够强大，可以用于各种应用程序和应用程序领域。本文提出了一种用于数据挖掘的声明性约束编程方法。更具体地说，我们展示了使用现成的约束编程技术来建模和求解各种基于约束的项目集挖掘任务是可能的，例如频繁的、封闭的、区分的和基于成本的项目集挖掘。特别地，我们开发了一个用于指定频繁项集的基本约束规划模型，并表明该模型可以很容易地扩展以实现其他设置。这与典型的过程性数据挖掘系统不同，在典型的过程性数据挖掘系统中，需要修改底层过程以适应新类型的约束或其新颖的组合。尽管最先进的数据挖掘系统在一些标准任务上的性能优于约束编程方法，但我们也表明，约束编程方法在数据挖掘中导致显著的性能改进，以及对潜在数据挖掘问题的新见解。通过将数据挖掘和约束编程系统的基本搜索算法相互关联，可以获得许多这样的见解。我们讨论了数据挖掘的声明性约束编程方法带来的一些有趣的新研究问题和挑战。
The field of data mining has become accustomed to specifying constraints on patterns of interest. A large number of systems and techniques has been developed for solving such constraint-based mining problems, especially for mining itemsets. The approach taken in the field of data mining contrasts with the constraint programming principles developed within the artificial intelligence community. While most data mining research focuses on algorithmic issues and aims at developing highly optimized and scalable implementations that are tailored towards specific tasks, constraint programming employs a more declarative approach. The emphasis lies on developing high-level modeling languages and general solvers that specify what the problem is, rather than outlining how a solution should be computed, yet are powerful enough to be used across a wide variety of applications and application domains. This paper contributes a declarative constraint programming approach to data mining. More specifically, we show that it is possible to employ off-the-shelf constraint programming techniques for modeling and solving a wide variety of constraint-based itemset mining tasks, such as frequent, closed, discriminative, and cost-based itemset mining. In particular, we develop a basic constraint programming model for specifying frequent itemsets and show that this model can easily be extended to realize the other settings. This contrasts with typical procedural data mining systems where the underlying procedures need to be modified in order to accommodate new types of constraint, or novel combinations thereof. Even though the performance of state-of-the-art data mining systems outperforms that of the constraint programming approach on some standard tasks, we also show that there exist problems where the constraint programming approach leads to significant performance improvements over state-of-the-art methods in data mining and as well as to new insights into the underlying data mining problems. Many such insights can be obtained by relating the underlying search algorithms of data mining and constraint programming systems to one another. We discuss a number of interesting new research questions and challenges raised by the declarative constraint programming approach to data mining.