TL;DR
This paper introduces LAZYDT, a novel lazy learning algorithm for decision tree classification. Instead of building a single, general-purpose tree, LAZYDT constructs a specialized decision path tailored to each individual test instance, leading to improved accuracy and a natural handling of missing values.
What Problem Does This Paper Address?
Traditional "eager" decision tree algorithms, like C4.5 and CART, build a single, explicit decision tree during training. This tree is designed to perform well on average across all possible instances. However, this approach can lead to issues like fragmentation (data being split unnecessarily) and replication (subtrees being duplicated), especially when dealing with complex concepts or many features. Furthermore, eager algorithms often require complex mechanisms to handle missing feature values. The authors propose a "lazy" approach that delays the inductive process until classification time, aiming to create a more efficient and accurate classifier by tailoring the decision process to each specific instance.
Methods
LAZYDT is a lazy learning algorithm that conceptually builds a "best" decision tree for each test instance. In practice, this means tracing a path down a tree that is dynamically constructed based on the test instance's features. The core of the algorithm involves selecting the most informative test at each node, similar to eager algorithms, but using the test instance's specific feature values to guide this selection.
Key methodological aspects include:
- Lazy Classification: The inductive process (building the tree) is deferred until a test instance is presented.
- Instance-Specific Tree Construction: For each test instance, a path is traced through a decision tree that is optimized for that specific instance. This avoids building a full, general tree.
- Test Selection: The algorithm uses a measure related to information gain to select the best test at each node.
- Handling Missing Values: LAZYDT naturally handles missing values by simply not branching on tests where the feature value is unknown for the test instance. This avoids the complex imputation or surrogate split strategies often seen in eager algorithms.
- Normalization of Class Probabilities: To address issues with information gain calculations, class probabilities at each node are re-weighted to give equal importance to each class. This ensures positive information gain and improves the effectiveness of the splitting criteria.
- Caching Scheme: To improve efficiency, LAZYDT employs a caching mechanism that stores information gains and pointers to instances for commonly traversed paths, significantly speeding up classification after an initial set of instances have been processed.
Datasets
The experiments were conducted on a variety of datasets, primarily from the U.C. Irvine repository of machine learning databases. These include both real-world and artificial datasets. Specific datasets mentioned include:
- monk-1, monk-2, monk-3
- tic-tac-toe
- cleve
- glass, glass2
- hayes-roth
- anneal
- heart
- diabetes
- soybean-small
- labor-neg
- lymphography
- hepatitis
- german
- pima
- mushroom
- iris
- vote
- chess
- breast-(W), breast-(L)
- horse-colic
- australian
- crx
- votel
- audiology
The evaluation involved five-fold cross-validation for most datasets, with a standard training/test split for artificial domains.
Key Insights and Ideas
- Tailoring to the Instance: The core idea that a decision process optimized for a specific instance can be more accurate than a general one is a significant departure from traditional approaches. This addresses the "one size fits all" limitation of eager methods.
- Natural Missing Value Handling: The way LAZYDT avoids complex strategies for missing values by simply not branching on unknown features is elegant and effective, reducing implementation complexity and potentially improving robustness.
- Mitigating Fragmentation: By focusing on instance-specific paths, LAZYDT inherently reduces the fragmentation problem, as splits are only made when relevant to the current instance's classification.
- Normalization as a Key Improvement: The normalization of class probabilities is crucial for making the information gain metric effective and robust, particularly in scenarios with imbalanced class distributions.
Key Results
- Accuracy: LAZYDT generally performed comparably to or slightly better than C4.5 (with pruning) across the tested datasets. The average error rate for LAZYDT was 1.9% lower than C4.5, representing a relative improvement of 10.6%.
- Missing Values: When datasets were corrupted with 20% missing values, LAZYDT's accuracy decreased by a smaller margin (from 82.15% to 78.40%) compared to ID3 and C4.5, demonstrating its robustness.
- Speed: While the algorithm can be slow in its naive form, the caching scheme significantly speeds up classification, making it practical. The authors note that the caching scheme consumes considerable memory.
- Performance Differences: The paper highlights that LAZYDT and C4.5 exhibit different strengths and weaknesses on various datasets, suggesting that neither algorithm is universally superior. For instance, LAZYDT outperformed C4.5 on the monk2 dataset, while C4.5 was better on audiology.
Limitations and Future Work
- No Pruning: The current implementation of LAZYDT does not include a pruning mechanism, which is a standard feature in many eager decision tree algorithms to prevent overfitting. The authors acknowledge that pruning could potentially improve performance, especially on datasets with missing values where LAZYDT can overfit.
- Memory Consumption: The caching scheme, while effective for speed, requires a significant amount of memory. The authors suggest exploring space-time tradeoffs for the caching mechanism.
- Discretization: Data is discretized in advance, which is a pre-processing step that doesn't leverage the test instance. The authors suggest that extending LAZYDT to decide on thresholds during classification, similar to some eager algorithms, could be a future enhancement, though it would require modifications to the caching scheme.
- Dynamic Complexity: The authors propose comparing the dynamic complexity (average number of features used) of LAZYDT with that of C4.5 as an interesting area for future research.
Summary updated