Knowledge Discovery in Inductive Databases: 5th International Workshop, KDID 2006 Berlin, Germany, September 18th, 2006 Revised Selected and Invited Papers (Lecture Notes in Computer Science, 4747)

✍ Scribed by Saso Dzeroski (editor), Jan Struyf (editor)

• Publisher: Springer
• Year: 2007
• Tongue: English
• Leaves: 310
• Category: Library

✦ Synopsis

This book constitutes the thoroughly refereed joint postproceedings of the 5th International Workshop on Knowledge Discovery in Inductive Databases, KDID 2006, held in association with ECML/PKDD. Bringing together the fields of databases, machine learning, and data mining, the papers address various current topics in knowledge discovery and data mining in the framework of inductive databases such as constraint-based mining, database technology and inductive querying.

✦ Table of Contents

Title Page
Preface
Organization
Table of Contents
Value, Cost, and Sharing: Open Issues in Constrained Clustering
Introduction
Constrained Clustering
Pairwise Constraints
Beyond Pairwise Constraints
Open Questions
Value: How Useful Is a Given Set of Constraints?
Cost: How Can We Make Constraints Cheaper to Acquire?
Sharing: When and How Should Constraints Be Propagated to Neighboring Points?
Conclusions
Mining Bi-sets in Numerical Data
Introduction
A New Pattern Domain for Numerical Data Analysis
Algorithm
Candidate Enumeration
Candidate Pruning
Propagation
Experiments
Related Work
Conclusion
Extending the Soft Constraint Based Mining Paradigm
Introduction
Soft Constraint Based Pattern Mining
Mining Mining $int_p^\items(\lambda)$ ($\lambda$-Interesting Itemsets on the Probabilistic Semiring)
Mining $int_w^\items(\lambda)$ ($\lambda$-Interesting Itemsets on the Weighted Semiring)
Mining Top-$k$ Itemsets
Soft Constraints in ConQueSt
Related Work
On Interactive Pattern Mining from Relational Databases
Introduction
Constraint Based Pattern Mining
A Simple Data Mining Query Language
Architecture of the System
Graphical User Interface
Query Interpreter and Pre-processor
The Mining Engine
Other Mining Query Languages
Conclusion
Analysis of Time Series Data with Predictive Clustering Trees
Introduction
Predictive Clustering Trees
Prediction, Clustering, and Predictive Clustering Trees
Building Predictive Clustering Trees
PCTs for Time Series Clustering
Distance Measures
Computing Cluster Variance
Cluster Centroids for the Tree Leaves
Analyzing Gene Expression Time Series with PCTs
The Problem
The Mining Scenario
Predicting Time Series with PCTs
Hierarchical Agglomerative Clustering
Clustering Time Series with PCTs
Future Work
Conclusion
Integrating Decision Tree Learning into Inductive Databases
Introduction
The ADReM Approach to Association Rule Mining
The Conceptual View
The Implementation
Advantages of the Approach
Integration of Decision Tree Learning
Motivation
Representing Trees in a Relational Database
Querying Decision Trees Using Virtual Views
User Defined Virtual Views
Implementation
Greedy Tree Learning
Exhaustive Tree Learning
Perspectives
Conclusion
Using a Reinforced Concept Lattice to Incrementally Mine Association Rules from Closed Itemsets
Introduction
Formal Concept Analysis: Definitions and Notations
Association Rule and Closed Itemset Mining in Formal Concept Analysis
The Line Diagram
The Incremental Algorithm
Experimental Evaluation
Conclusions and Future Work
An Integrated Multi-task Inductive Database VINLEN: Initial Implementation and Early Results
Introduction
An Overview of VINLEN
Knowledge Representation and VINLEN Operators
Knowledge Scouts
An Example of Application to a Medical Domain
Relation to Other Work
Summary and Future Work
References
Beam Search Induction and Similarity Constraints for Predictive Clustering Trees
Introduction
Predictive Clustering Trees
Beam Search
Anti-monotonic Constraints
Similarity Constraints
Experiments
Aims
Setup
Results and Discussion
Predictive Performance
Induction Time
Conclusion and Further Work
Frequent Pattern Mining and Knowledge Indexing Based on Zero-Suppressed BDDs
Introduction
BDDs and Zero-Suppressed BDDs
BDDs
Sets of Combinations and ZBDDs
ZBDD-Based Database Analysis
A ZBDD-Based Pattern-Mining Algorithm
Itemset-Histograms and ZBDD Vectors
ZBDD Vectors and FP-Trees
A Frequent Pattern Mining Algorithm
Extension for Maximal Pattern Mining
Experimental Results
Experiment with a Mathematical Example
Experiments for Benchmark Examples
Maximal Frequent Pattern Mining
Postprocessing for Generated Frequent Patterns
Related Works
Conclusion
Extracting Trees of Quantitative Serial Episodes
Introduction
Preliminary Definitions
Quantitative Episodes
Informal Presentation
Quantitative Episode Definition
Extracting q-Episodes
Principle
Abstract Algorithm
Experiments
Performance Analysis on Synthetic Datasets
Experiments on a Real Dataset
Related Work
Conclusion
IQL: A Proposal for an Inductive Query Language
Introduction
Some Example Queries
Manipulation of Data
Evaluation of Queries
Primitives and Extensions
Reasoning
Scenario
Extensions of Other Query Languages
Conclusions
Mining Correct Properties in Incomplete Databases
Introduction
$k$-Free Patterns and Generalized Association Rules
Preliminaries
Generalized Association Rules and $k$-Freeness
Generalized Association Rules Mining
Missing Values
Damages of Missing Values on $k$-Free Patterns
Position of Our Work
Mining $k$-Free Patterns in Incomplete Databases
Missing Values Modeling Operator
Temporarily Deactivating Objects
Differences with Ragel's Approach
$k$-Freeness Definition and Correction in Incomplete Databases
Properties of the $k$-Freeness in Incomplete Databases
Prototype $MV-k-miner$
Experiments on UCI Benchmarks
Conclusion
Efficient Mining Under Rich Constraints Derived from Various Datasets
Introduction
Defining Constraints on Several Datasets
Integrating Background Knowledge Within Constraints
Primitive-Based Constraints
MUSIC-DFS Tool
Main Features of the Interval Pruning
Interval Condensed Representation
Mining Primitive-Based Constraints in Large Datasets
Mining Constrained Patterns from Transcriptomic Data
Gene Expression Data and Background Knowledge
Efficiency of MUSIC-DFS
Use of Background Knowledge to Mine Plausible Patterns
Conclusion
Three Strategies for Concurrent Processing of Frequent Itemset Queries Using FP-Growth
Introduction
Related Work
Organization of the Paper
Frequent Itemset Mining and Review of FP-Growth
Multiple-Query Optimization for Frequent Itemset Queries
Basic Definitions and Problem Statement
Mine Merge
Common Counting
Common Building: Adaptation of Common Counting for FP-Growth
Common FP-Tree: Integration of Queries’ FP-Trees into One Data Structure
Experimental Results
Conclusions
References
Towards a General Framework for Data Mining
Introduction: The Challenges for Data Mining
Inductive Databases and Inductive Queries
Desiderata for a General Data Mining Framework
The Basic Concepts of Data Mining
Data
Patterns and Models
Data Mining Tasks
The Dual Nature of Patterns and Models
The Data Aspect: Classes of Patterns and Models
The Function Aspect: Interpreters
Constraints in Data Mining: Introduction
Language Constraints
Evaluation Constraints
Optimization Constraints
Soft Constraints
The Task(s) of (Constraint-Based) Data Mining
The Key Ingredients of Data Mining Algorithms
Generality and Refinement Operators
Distances and Prototypes
Features and Background Knowledge
Kernels
Constraints in Data Mining: Revisited
Evaluation Functions for the Basic Data Mining Tasks
Cost Functions for Language Constraints
Monotonicity and Closedness
Multi-objective Optimization and Constraint-Based Data Mining
Generic Algorithms for Mining Structured Data
Distances and Distance-Based Algorithms
Kernels and Kernel Methods
Features and Feature-Based Methods
Refinement Orders and (Frequent) Pattern Discovery
Towards a Language for Data Mining and Knowledge Discovery
Data and Background Knowledge
Generalizations
Cross-Over Queries
Generic Data Mining: Components and Algorithms
Constraints and Data Mining Queries
Re-using the Results of Learning
Operations on Generalizations
Integration Aspects, Compositionality, and Scenarios
Related Work
Author Index