Frequent Pattern Discovery in First-Order Logic
Frequent Pattern Discovery in First-Order Logic
复制标题
一阶逻辑中的频繁模式发现
DOI：
--
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
L. Dehaspe
中科院分区：
文献类型：
--
作者：
L. Dehaspe
近年来，由于收集和存储大量数据的成本不断下降，数据库的使用和规模急剧增长。对利用流行的数据仓库的工具的需求相应地增长，并在统计，数据库和机器学习的交叉点上产生了一个快速发展的研究领域：数据挖掘和数据库中的知识发现（KDD）。在KDD中，发现（潜在的巨大）数据集合中的重复模式已成为中心主题之一。在目标是揭示数据中的结构并且没有预设目标概念的任务中，发现相对简单但频繁出现的模式已经显示出良好的前景。这种应用程序的动机是所发现的模式的潜在高业务价值。任务的核心是确定频繁出现的项目的所有组合的问题，其中“频繁”被定义为“超过用户指定的频率阈值”。使用频率阈值来过滤掉不感兴趣的模式对于大量的数据挖掘问题来说是很自然的。罕见的模式，例如，只涉及几个客户，可能对用户来说既不可靠也不有用。频繁模式发现已经在各种设置中进行了研究。在其最简单的形式中，该任务是从关联规则挖掘中得知的。这个基本设置的一个典型应用例子是在购物篮分析中：找出哪些物品倾向于一起出售。关联规则和频繁集发现的基本任务已经在各个方向上扩展，允许更有用的模式（例如，序列模式或情节），以利用专用算法来发现。我们提出了一个通用公式的频繁模式发现问题，其中数据库和模式都表示在一阶逻辑的某个子集，即，基本上是Prolog显然，与频繁模式发现算法中采用的基于属性值的原始格式相比，Prolog数据库格式更具表达力。在关系数据库术语中：传统技术假设每个示例一行的单个表表示，在Prolog中，示例可以通过从一组相关表中提取的行的集合来表示。在这个框架中，每个示例都对应于一个（小型）数据库。我们考虑的模式的中心类型是Prolog查询。这样的查询是项集的一阶逻辑等价物。为了验证一个查询是否匹配一个特定的示例，我们可以将其提交到与该示例相对应的（迷你）数据库。然后我们得出结论，该模式适用于w.r.t.当且仅当查询成功时，与关联规则的情况非常相似，我们可以将联合收割机两个查询（其中一个查询扩展另一个查询）组合成一个规则，称为查询扩展。例如：
In recent years, the usage and size of databases have grown dramatically, due to a constant decrease in the cost of both the collection and the storage of huge amounts of data. The need for tools to exploit the popular Data Warehouse has grown accordingly and has given rise to a rapidly evolving research field at the intersection of statistics, databases, and machine learning: Data Mining and Knowledge Discovery in Databases (KDD). Within KDD, the discovery of recurrent patterns in (potentially huge) data collections has become one of the central topics. In tasks where the goal is to uncover structure in the data and where there is no preset target concept, the discovery of relatively simple but frequently occurring patterns has shown good promise. The motivation for such an application is the potentially high business value of the discovered patterns. At the heart of the task is the problem of determining all combinations of items that occur frequently together, where ‘frequent’ is defined as ‘exceeding a user-specified frequency threshold’. The use of a frequency threshold for filtering out non-interesting patterns is natural for a large number of data mining problems. Patterns that are rare, e.g., that concern only a couple of customers, are probably not reliable nor useful for the user. Frequent pattern discovery has been studied in a variety of settings. In its simplest form, the task is known from association rule mining. A prototypical application example of this basic setting is in market basket analysis: find out which items tend to be sold together. The fundamental task of association rule and frequent set discovery has been extended in various directions, allowing more useful patterns (e.g., sequential patterns or episodes) to be discovered with special purpose algorithms. We present a general formulation of the frequent pattern discovery problem, where both the database and the patterns are represented in some subset of first-order logic, i.e., essentially Prolog. Obviously, when compared to the original, attributevalue based format employed in frequent pattern discovery algorithms, the Prolog database format is more expressive. In relational databases terminology: where traditional techniques assume a single table representation with one row per example, in Prolog an example can be represented by means of a collection of rows drawn from a set of related tables. In this framework, each example as it were corresponds to a (mini-)database. The central type of pattern we consider is that of a Prolog query. Such a query is the first-order logic equivalent of an item set. To verify whether a query matches a particular example we can submit it to the (mini-)database that corresponds to the example. We then conclude the pattern holds w.r.t. the example if and only if the query succeeds. Much like in the case of association rules, we can combine two queries, where one extends the other, into a rule, called a query extension. For instance: