Inductive Querying with Virtual Mining Views

Hendrik Blockeel, Toon Calders, Élisa Fromont, Adriana Prado, Bart Goethals, Céline Robardet

TL;DR

This paper introduces "virtual mining views," a novel approach to inductive databases that allows users to query data mining patterns (like itemsets, association rules, and decision trees) using standard SQL. This bridges the gap between traditional database querying and complex data mining tasks, making pattern discovery more accessible and integrated.

What Problem Does This Paper Address?

Traditional databases excel at querying stored data. However, extracting implicit patterns and knowledge from that data (data mining) often requires specialized tools and languages, creating a disconnect. Inductive databases aim to bridge this gap by allowing users to query both stored data and discovered patterns. Existing approaches often involve extending query languages like SQL, which can be complex. This paper addresses the challenge of integrating data mining into databases in a user-friendly way, specifically by enabling users to query patterns using familiar SQL syntax without needing to learn new, complex query languages.

Methods

The core innovation is the concept of virtual mining views. These are essentially relational tables that virtually represent the output of data mining tasks. Crucially, these views are empty; when a query is issued against them, the system triggers the relevant data mining algorithm to compute the requested patterns on the fly. This is analogous to how regular database views are computed only when queried.

The authors propose a framework where different data mining tasks are mapped to specific virtual mining views:

  • T_Concepts: Represents all possible patterns (conjunctions of attribute-value pairs) definable over a dataset.
  • T_Sets: Represents itemsets, including their support and size.
  • T_Rules: Represents association rules, including their confidence and identifiers for antecedent, consequent, and their union.
  • T_Trees_Ai and T_Treescharac_Ai: Represent decision trees, their structure (as concepts), and characteristics like accuracy and size.

The system is implemented on top of PostgreSQL, leveraging its extensibility. Constraint extraction algorithms are used to push user-defined constraints from SQL queries into the data mining algorithms, optimizing the process.

Datasets

The paper uses the Playtennis dataset for illustrative examples of itemset mining, association rule discovery, and decision tree learning.

For a more comprehensive demonstration, they present a scenario involving gene expression data from Plasmodium Falciparum. This data was pre-processed into three tables: GeneFunctions, Samples, and Plasmodium.

Key Insights and Ideas

  • SQL as a Universal Query Language: The most significant insight is demonstrating that standard SQL can be powerful enough to express complex data mining queries, provided the underlying data mining results are exposed as relational tables (virtual mining views).
  • Virtualization for Simplicity: By making mining views virtual, the system avoids storing potentially massive amounts of patterns, computing them only when needed. This simplifies management and improves efficiency for queries that only require a subset of patterns.
  • Unified Representation: Representing various mining outputs (itemsets, rules, trees) as sets of "concepts" (attribute-value pairs, potentially with wildcards) provides a generic and interpretable way to handle different pattern types.
  • Declarative Data Mining: The approach shifts data mining from an imperative, procedural task to a declarative one, where users specify what they want (e.g., "find all rules with confidence 100% and stage as antecedent") rather than how to find it.

Key Results

The paper demonstrates the feasibility of the virtual mining views framework by showing how various data mining tasks, including:

  • Itemset mining: Finding itemsets with specific support and size constraints.
  • Association rule discovery: Extracting rules with minimum support and confidence.
  • Decision tree learning: Querying for trees with specific characteristics like maximum accuracy or size.
  • A real-world gene expression analysis scenario: Successfully extracting meaningful association rules to characterize parasite stages.

The authors highlight that their framework allows for these tasks to be performed using SQL queries over the mining views, without requiring separate pre- or post-processing steps that are common in other approaches.

Limitations and Future Work

  • Intra-tuple Patterns Only: The current system primarily handles intra-tuple patterns (patterns within a single tuple or row). Mining inter-tuple patterns (patterns across multiple tuples or relations) requires pre-processing the data into a new representation, which can be laborious.
  • Materialization Strategy: Currently, mining views are only materialized upon request. The authors suggest investigating which views could be pre-materialized to speed up query evaluation.
  • Limited Task Coverage: While the framework covers itemsets, association rules, and decision trees, it doesn't currently support all data mining tasks (e.g., clustering).
  • Extensibility: Extending the framework to new pattern types requires defining new mining views or adding attributes, which is seen as a strength but also implies that new tasks aren't immediately available without such definitions.

Future work directions include:

  • Investigating pre-materialization of mining views.
  • Developing methods to integrate inter-tuple pattern mining directly into the system.
  • Extending the framework to support a wider range of data mining models and tasks.

Summary updated

Abstract

In an inductive database, one can not only query the data stored in the database, but also the patterns that are implicitly present in these data. In this chapter, we present an inductive database system in which the query language is traditional SQL. More specifically, we present a system in which the user can query the collection of all possible patterns as if they were stored in traditional relational tables. We show how such tables, or mining views, can be developed for three popular data mining tasks, namely itemset mining, association rule discovery and decision tree learning. To illustrate the interactive and iterative capabilities of our system, we describe a complete data mining scenario that consists in extracting knowledge from real gene expression data, after a pre-processing phase.
BibTeX
@inproceedings{blockeel2010inductive,
  author = {Hendrik Blockeel and Toon Calders and Élisa Fromont and Adriana Prado and Bart Goethals and Céline Robardet},
  title = {{Inductive Querying with Virtual Mining Views}},
  booktitle = {Inductive Databases and Constraint-Based Data Mining},
  year = {2010},
  url = {https://openreview.net/forum?id=R5xYIpVFO_},
}
Figure