Machine Learning (Chapter 36): Decision Trees - Missing Values, Imputation & Surrogate Splits

By

 



Machine Learning (Chapter 36): Decision Trees - Missing Values, Imputation & Surrogate Splits

Decision trees are a popular method for both classification and regression tasks. However, they can face challenges when data contains missing values. To handle such issues, various strategies, such as missing value imputation and surrogate splits, are employed. This article covers how decision trees address missing values, along with mathematical formulas and Python/Java code examples.

1. Missing Values in Decision Trees

Missing values in decision trees can occur in both features (predictor variables) and target variables. Some common strategies to handle missing values include:

  • Removing records: This is a simple method but can lead to loss of important data.
  • Imputation: Missing values are replaced using statistical methods.
  • Surrogate Splits: When a feature used for splitting has missing values, alternative features (surrogates) are used.

2. Mathematical Formulation

Imputation Methods:

  1. Mean/Median Imputation: For numeric features, missing values can be replaced by the mean or median.

    X^i=1n∑j=1nXj(mean)\hat{X}_i = \frac{1}{n} \sum_{j=1}^{n} X_j \quad \text{(mean)}

    or

    X^i=median(X)\hat{X}_i = \text{median}(X)

  2. Mode Imputation: For categorical features, the missing value can be imputed by the mode (the most frequent category).

    X^i=mode(X)\hat{X}_i = \text{mode}(X)
Surrogate Splits:

Surrogate splits find an alternative feature highly correlated with the primary feature used for splitting. Let the original splitting variable be XX and the surrogate variable be SS. If XX has missing values, we evaluate the surrogate feature SS for a split decision.

Given that XX is the primary split feature, SS should minimize the impurity (Gini Index or entropy) on the missing samples:

G(S)=∑i=1kpi(1−pi)G(S) = \sum_{i=1}^{k} p_i(1 - p_i)

where pip_i is the probability of class ii.

The surrogate split will be used when values for XX are missing.

3. Python Code Example: Decision Trees with Missing Values Handling

Below is an example using scikit-learn to handle missing values in decision trees. We’ll use imputation and explore how decision trees manage missing data.

python:

import numpy as np
from sklearn.impute import SimpleImputer
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# Sample dataset with missing values
X = np.array([[1, 2, np.nan], 
              [3, np.nan, 1], 
              [np.nan, 2, 0], 
              [3, 3, 1], 
              [2, np.nan, 0]])

y = np.array([0, 1, 0, 1, 0])

# Imputation of missing values (Mean strategy for simplicity)
imputer = SimpleImputer(strategy='mean')
X_imputed = imputer.fit_transform(X)

# Train-Test Split
X_train, X_test, y_train, y_test = train_test_split(X_imputed, y, test_size=0.2, random_state=42)

# Decision Tree Classifier
clf = DecisionTreeClassifier()
clf.fit(X_train, y_train)

# Prediction and Evaluation
y_pred = clf.predict(X_test)
accuracy = accuracy_score(y_test, y_pred)

print("Accuracy with imputed data:", accuracy)

In this code:

  • We create a dataset with missing values (np.nan).
  • The SimpleImputer replaces missing values using the mean strategy.
  • A decision tree is trained on the imputed data, and the accuracy is measured.
Imputation with Surrogate Splits:

scikit-learn automatically handles missing values internally for surrogate splits using different heuristics, but for direct control, we would need to modify how the tree handles missing data manually.

4. Java Code Example: Decision Trees with Missing Values Handling

Below is an example using Java and the Weka library, which supports decision trees (like J48) and handles missing values.

java:

import weka.core.Instances;
import weka.core.converters.ConverterUtils.DataSource;
import weka.classifiers.trees.J48;
import weka.filters.Filter;
import weka.filters.unsupervised.attribute.ReplaceMissingValues;

public class DecisionTreeWithMissingValues {
    public static void main(String[] args) throws Exception {
        // Load dataset
        DataSource source = new DataSource("data/your-dataset.arff");
        Instances data = source.getDataSet();
        
        // Impute missing values
        ReplaceMissingValues replaceMissing = new ReplaceMissingValues();
        replaceMissing.setInputFormat(data);
        Instances newData = Filter.useFilter(data, replaceMissing);
        
        // Set class attribute
        if (newData.classIndex() == -1)
            newData.setClassIndex(newData.numAttributes() - 1);
        
        // Train decision tree (J48 is Weka's implementation of C4.5)
        J48 tree = new J48();
        tree.buildClassifier(newData);
        
        System.out.println(tree);
    }
}

In this Java example:

  • The Weka ReplaceMissingValues filter imputes missing values.
  • The J48 classifier (a decision tree algorithm) builds a model on the imputed data.

5. Conclusion

Handling missing values is crucial for building robust decision tree models. Imputation techniques like mean, median, or mode filling are straightforward, but surrogate splits offer a more refined way of dealing with missing data during the splitting process. The choice of strategy depends on the problem and the data characteristics. The Python and Java examples demonstrate how to apply these techniques in practical decision tree models.

By properly managing missing data, you can enhance the performance and reliability of decision trees in machine learning applications.

Comments

Post a Comment

Popular posts from this blog

Machine Learning (Chapter 41): The ROC Curve

By
Image
  Machine Learning (Chapter 39): The ROC Curve Introduction to ROC Curve The ROC (Receiver Operating Characteristic) curve is a graphical representation used in binary classification problems to evaluate the performance of a classifier. It plots the True Positive Rate (TPR) against the False Positive Rate (FPR) at various threshold levels. The curve illustrates the trade-offs between sensitivity (recall) and specificity, helping to visualize a classifier’s capability. A perfect classifier would have a curve that reaches the top-left corner of the plot, whereas a random classifier would result in a diagonal line from (0, 0) to (1, 1). Key Definitions Before diving into the mathematics, let's define key metrics: True Positive (TP) : Correctly predicted positives. False Positive (FP) : Incorrectly predicted positives. True Negative (TN) : Correctly predicted negatives. False Negative (FN) : Incorrectly predicted negatives. From these, we calculate: True Positive Rate (TPR) , also kn...
Read more

Machine Learning (Chapter 39): Bootstrapping & Cross-Validation

By
Image
  Machine Learning (Chapter 39): Bootstrapping & Cross-Validation Introduction In the context of machine learning, evaluating the performance of models is a critical step. Two essential techniques widely used for model evaluation and resampling are Bootstrapping and Cross-Validation . Both help estimate the performance of a model by making efficient use of available data, reducing overfitting, and improving generalization. 1. Bootstrapping Bootstrapping is a resampling method where subsets of data are sampled with replacement. The goal is to create multiple training datasets, then build models for each dataset, and assess model variability and performance. Key Concept : When we sample with replacement, some observations may appear multiple times in the bootstrap sample, while others may not appear at all. Mathematical Foundation Given a dataset D = { x 1 , x 2 , … , x n } D = \{x_1, x_2, \dots, x_n\} D = { x 1 ​ , x 2 ​ , … , x n ​ } , a bootstrap sample D b D_b D b ​ is crea...
Read more

Machine Learning (Chapter 40): Class Evaluation Measures

By
Image
  Machine Learning (Chapter 39): Class Evaluation Measures In machine learning, particularly classification problems, evaluation metrics are critical for understanding how well a model performs. These metrics help in comparing models, tuning parameters, and determining which model fits best for a specific problem. In this chapter, we will focus on several widely-used class evaluation measures, along with the corresponding mathematical formulas and practical examples. 1. Accuracy Accuracy measures the proportion of correctly predicted instances out of all instances in the dataset. It is simple but can be misleading for imbalanced datasets. Accuracy = T P + T N T P + T N + F P + F N \text{Accuracy} = \frac{TP + TN}{TP + TN + FP + FN} Accuracy = TP + TN + FP + FN TP + TN ​ where: T P TP TP = True Positives T N TN TN = True Negatives F P FP FP = False Positives F N FN FN = False Negatives Example: Let’s calculate accuracy in Python. python Copy code from sklearn.metrics import ac...
Read more