TL;DR
This paper introduces a novel system that automatically plans and optimizes data mining workflows. By learning from past experiments, it creates workflows tailored to specific datasets and tasks, significantly outperforming existing methods that can only select pre-defined workflows.
What Problem Does This Paper Address?
Designing effective data mining (DM) workflows is a complex and time-consuming task. Modern Knowledge Discovery Support Systems (KDSS) offer hundreds of operators, leading to a combinatorial explosion of possible workflows. While existing systems can help users construct valid workflows, they struggle to guide users towards workflows that are optimal for a given DM task and dataset. This often leaves the user to rely on intuition and extensive experimentation. The paper aims to bridge this gap by providing automated support for designing high-performing DM workflows.
Methods
The core of the proposed system is a meta-mining module that learns meta-mining models. These models associate dataset characteristics with workflow descriptors to predict workflow performance.
- Meta-mining Model Learning:
- Offline Mode: The system analyzes past DM experiments (datasets, workflows, and their performance) stored in a Data Mining Experiment Repository (DMER).
- Dataset Characteristics: Datasets are described using a rich set of features (around 150) including statistical, information-theoretic, geometrical, topological, and landmarking measures.
- Workflow Characteristics: Workflows are characterized by mining generalized, relational, frequent patterns from their tree representations, leveraging domain knowledge from the Data Mining Optimization (DMOP) ontology. This results in a propositional representation of each workflow.
- Performance Measures: Workflows are ranked based on statistical significance tests of their performance on a given dataset.
- Learning Approach: The paper explores two main strategies:
- Homogeneous Similarity Measures (P1): Learns separate similarity measures for datasets and workflows using Mahalanobis metric learning. These are then combined to estimate workflow performance.
- Heterogeneous Similarity Measure (P2): Learns a single metric that directly estimates the appropriateness of a workflow for a dataset, modeling interactions between dataset and workflow characteristics. This is achieved through a non-convex optimization problem.
- Workflow Planning:
- The system uses a Hierarchical Task Network (HTN) planner (based on Kietz et al.) to decompose DM tasks into smaller steps.
- Online Mode: During planning, the meta-mining module guides the planner. At each step, it ranks partial candidate workflows based on their predicted performance, allowing the planner to greedily explore promising paths.
Datasets
The paper uses a collection of 65 real-world datasets for training and evaluation. These datasets are primarily from the genomic microarray or proteomic data domain, related to cancer diagnosis or prognosis. They are characterized by high dimensionality and small sample sizes.
Key Insights and Ideas
- Meta-mining for Workflow Optimization: The core idea is to move beyond simply selecting existing workflows to actively planning and optimizing them for specific tasks and datasets.
- Dataset-Workflow Interaction: The most significant insight is that directly modeling the interaction between dataset characteristics and workflow characteristics (as in the P2 strategy) leads to better performance than learning these independently.
- Generalization is Key: The system's ability to generalize to unseen datasets is crucial. The P2 strategy, by learning heterogeneous similarity, shows promise in this regard.
- Ontology-Driven Characterization: Using a domain ontology (DMOP) to characterize workflows and operators allows for generalized pattern mining, which is essential for effective meta-learning.
Key Results
The proposed system, particularly the P2 planning strategy (heterogeneous similarity), significantly outperforms baseline methods and a default strategy.
- Scenario 1 (Tested Operators Only):
- P2 achieved an average Kendall similarity gain of 5-10% over the default strategy.
- For k=3, P2 achieved 1.25% higher average accuracy than the default strategy, and this advantage persisted for various k values.
- P2 was statistically significantly better than the default for 16 out of 34 k values in terms of Kendall similarity.
- Scenario 2 (Tested and Untested Operators):
- P2's advantage over the default strategy became less pronounced but still showed gains.
- In terms of average accuracy, P2 showed a slight advantage for very small k (up to 4), but was worse for larger k values.
- The paper suggests that while P2's direct modeling of interactions is powerful, it can be disadvantaged when dealing with operators not seen during training, where P1's dataset/workflow similarity approach might cope better.
Limitations and Future Work
- Untested Operators: The system's performance degrades when planning with operators not encountered during the base-level experiments, especially if their properties are not represented by other operators. This is particularly true for the P2 strategy.
- Ontology Dependency: While the system can function without a full ontology, using one allows for more generalized patterns and better characterization. The quality of the ontology is crucial.
- Parameter Tuning: The paper notes that parameters like kernel widths were not tuned but set based on prior belief.
- Future Work:
- Gain a deeper understanding of the reduced performance when planning over untested operators.
- Experiment with parameter tuning by treating parameters as operator properties.
- Study the impact of missing information in the preference matrix on system performance.
- Explore using ranking-based loss functions instead of sum of squares in metric learning.
- Investigate ideas from reinforcement learning to systematically design workflows and derive better characterizations of workflow and dataset spaces.
Summary updated