Skip to main content

Decision tree

The Decision Tree algorithm creates a tree structure where each internal node represents a test on one or more attributes. Each branch emerging from a node represents the outcome of a test, and each leaf node represents a class label or a predicted value.

This implementation only supports numeric features and a binary target variable. Additionally, it utilizes binning for efficient tree building when dealing with large datasets. The splitting rule employed by the algorithm is entropy.

The Decision Tree algorithm is a powerful tool for classification and regression tasks.

Defining a decision tree model​

All parameters are optional unless specified as required.

Algorithm-specific parameters​

  • max_depth: Specify the maximum depth of the final decision tree. The final depth can be less than the defined max_depth if another stopping criterion is met first. This value defaults to 20.
  • min_rows: Specify the minimum number of observations for a leaf. This value defaults to 10.

Common parameters​

  • categorical_encoding: Specify one of the following encoding schemes for handling categorical features:

    • auto or AUTO (default): Allow the algorithm to decide. In DRF, the algorithm will automatically perform enum encoding
    • enum or Enum: 1 column per categorical feature
    • enum_limited or EnumLimited: Automatically reduce categorical levels to the most prevalent ones during training and only keep the T (10) most frequent levels
    • one_hot_explicit or OneHotExplicit: N+1 new columns for categorical features with N levels
    • binary or Binary: No more than 32 columns per categorical feature
    • eigen or Eigen: k columns per categorical feature, keeping projections of one-hot-encoded matrix onto k-dim eigen space only
    • label_encoder or LabelEncoder: Convert every enum into the integer of its index (for example, level 0 -> 0, level 1 -> 1, etc.)
    • sort_by_response or SortByResponse: Reorders the levels by the mean response (for example, the level with lowest response -> 0, the level with second-lowest response -> 1, etc.). This is useful in GBM/DRF, for example, when you have more levels than nbins_cats, and where the top level splits now have a chance at separating the data with a split. Note that this requires a specified response column

  • ignore_const_cols: Specify whether to ignore constant training columns since no information can be gained from them. This option defaults to True (enabled).

  • ignored_columns: (Python only) Specify the column or columns to be excluded from the model.

  • model_id: Specify a custom name for the model to use as a reference. By default, H2O automatically generates a destination key.

  • seed: Specify the random number generator (RNG) seed for algorithm components dependent on randomization. The seed is consistent for each H2O instance so that you can create models with the same starting conditions in alternative configurations. This value defaults to -1 (time-based random number).

  • training_frame: Required Specify the dataset used to build the model.

  • x: Specify a vector containing the names or indices of the predictor variables to use when building the model. If x is missing, then all columns except y are used.

  • y: Required Specify the column to use as the dependent variable. The data can be numeric or categorical.

Decision tree workflow​

The Decision Tree algorithm follows a recursive process to build the tree structure. The basic workflow can be summarized as:

  1. Input: The algorithm takes a dataset consisting of numerical features and a binary target variable.

  2. Binning: The algorithm applies binning to discretize continuous features into a set of bins to optimize tree construction on large datasets. Binning is executed at each internal node prior to the selection of the splitting rule.

  3. Splitting rule selection: The algorithm uses entropy as the splitting rule to determine the best attribute and threshold for each node.

  4. Building the tree: The tree construction process begins with a root node and recursively divides the dataset based on the selected attribute and threshold.

  5. Stopping criteria: The recursive division process stops when specific conditions are met. The employed criteria include:

    1. Maximum tree depth: The process stops when the tree reaches a predefined maximum depth (set with max_depth).
    2. Minimum number of samples: The process stops when a node contains a minimum number of samples or instances (set with min_rows).
    3. Limit of entropy improvement: The process stops when the improvement of entropy between the parent node and the current split reaches a specified minimum threshold (refer to the Entropy as a splitting rule section for more information).

  6. Leaf node labeling: The leaf nodes are labeled with the majority class or predicted value based on the training samples they contain at the end of the tree construction.

Binning for tree building​

To handle large datasets efficiently, the Decision Tree algorithm utilizes binning as a preprocessing step at each internal node. Binning involves discretizing continuous features into a finite number of bins. This reduces the computational complexity of finding the best attribute and threshold for each split.

The binning process can be summarized as:

  1. Input: Inputting continuous feature values for a particular attribute.
  2. Binning algorithm: Applying a binning algorithm to divide the feature values into a specified number of bins (this technique is equal width binning).
  3. Binning result: Obtaining the bin boundaries for the feature values.
  4. Statistic calculation: Calculating statistics for each bin, such as the count of samples for each class.

The binned features are then used for split point selection during tree construction. This allows for faster computation.

Entropy as a splitting rule​

The Decision Tree algorithm employs entropy as the splitting rule to determine the best attribute and threshold for each node. Entropy measures the impurity or disorder within a set of samples. The goal is to find splits that minimize the entropy and create homogenous subsets with respect to the target variable.

The entropy of a set SS with respect to a binary target variable can be calculated using the following formula:

Entropy(S)=−p1×log⁡2(p1)−p0×log⁡2(p0)\text{Entropy}(S) = -p_1 \times \log2 (p_1) - p_0 \times \log2(p_0)

where

  • p1p_1 is the proportion of positive (or class 1) samples in SS
  • p0p_0 is the proportion of negative (or class 0) samples in SS

The attribute and threshold combination that minimizes the weighted average of the entropies of the resulting subsets is selected as the best split point.

Examples​

library(h2o)
h2o.init()

# Import the prostate dataset:
prostate <- h2o.importFile("http://s3.amazonaws.com/h2o-public-test-data/smalldata/prostate/prostate.csv")

# Set the target variable:
target_variable <- 'CAPSULE'
prostate[target_variable] <- as.factor(prostate['CAPSULE'])

# Split the dataset into train and test:
splits <- h2o.splitFrame(data = prostate, ratios = 0.7, seed =1)
train <- splits[[1]]
test <- splits[[2]]

# Build and train the model:
h2o_dt <- h2o.decision_tree(y = target_variable, training_frame = train, max_depth = 5)

# Predict on the test data:
h2o_pred <- h2o.predict(h2o_dt, test)$predict

References​

  1. Hastie, R. Tibshirani, J. Friedman, “The elements of Statistical Learning Data Mining, Inference and Prediction”, Chapter 9.2, Second Edition, Springer Series in Statistics, 2017.
Feedback