Decision Forests#
Decision forests (also referred to as random forests) are ensembles of decision trees. Decision trees split the feature domain into rectangular regions and make predictions based on the label values in each region.
A node in the decision tree is terminal if it does not have any child nodes. Let \(m\) be the index of a terminal node in the tree. If we are solving a classification problem with two classes, the proportion of observations in the second class for node m is defined as,
where \(R_m\) is the rectangular region corresponding to node \(m\), \(x_i\) is a (multi-dimensional) observation, \(y_i\) is a label, and \(N_m\) is the number of observations in \(R_m\).
The node impurity is defined as,
where \(Q(\hat{p}^0_m)\) is a function that quantifies the error in the classification fit, with the property that if all observations in \(R_m\) are in the same class, then \(Q(\hat{p}^0_m)=0\) and we say that the node is pure.
AOCL-DA supports the following choices of \(Q(p)\),
Fitting#
Decision tree fitting is performed by growing a tree recursively, starting with a single base node. Each node has an associated depth, which corresponds to the number of splits required to get to that node from the base node. If the depth of the node is less than the maximum depth and the node is not pure, we minimize the sum of the node impurities over each possible split,
where
and \(j\) is the feature index, so that \(x_i(j)\) is the \(j\)-th feature of the \(i\)-th observation.
Then node \(m\) stops being a terminal node, and two new terminal nodes are created as children of node \(m\). The domains for the new child nodes are defined by splitting \(R_m\) into two rectangles using the variable index \(j^*\) and the threshold \(s^*\).
This recursive splitting continues until all terminal nodes are either pure, or have reached the maximum depth. The maximum depth is a user-defined parameter and, for decision trees, needs to be selected in such a way that avoids overfitting.
Decision forest fitting is performed by creating an ensemble of decision trees. The training data for each decision tree in the ensemble is generated by bootstrapping observations from the training data. The fitting for each decision tree in the ensemble follows a modified version of the decision tree fitting algorithm. In contrast to standard decision tree fitting, the candidate set of features for each split is a randomly sampled subset. The subset selection is repeated at each split so a different subset of candidate features is used on each split. In both decision trees and decision forests, the order in which features are selected is randomized. This means that if two different splits have the same value of \(C_m(j, s)\), then whichever value of \(j\) is sampled first will be the split variable.
Prediction#
Decision tree prediction is performed by using the set of split feature indices and thresholds to determine which terminal node a new observation belongs to. Once the terminal node has been identified, the prediction is determined by the proportion of observations with label \(1\) in the training set: if an observation \(x\) is associated with a terminal node \(m\), and \(\hat{p}^0_m > 0.5\), the predicted label is \(1\), otherwise it is \(0\).
Decision forest prediction is performed by producing an ensemble of decision tree predictions and using a majority vote to determine the prediction of the decision forest.
Typical workflow for decision trees and decision forests#
The following workflow can be used to fit a decision tree or a decision forest model and use it to make predictions,
Decision trees
Initialize a
aoclda.decision_tree.decision_tree()object with options set in the class constructor.Fit the model using
aoclda.decision_tree.decision_tree.fit().Evaluate prediction accuracy on test data using
aoclda.decision_tree.decision_tree.score().Make predictions using the fitted model using
aoclda.decision_tree.decision_tree.predict().
Decision forests
Initialize a
aoclda.decision_forest.decision_forest()object with options set in the class constructor.Fit the model using the
aoclda.decision_forest.decision_forest.fit().Evaluate prediction accuracy on test data using
aoclda.decision_forest.decision_forest.score().Make predictions using the fitted model using
aoclda.decision_forest.decision_forest.predict().
Decision trees
Initialize a
da_handlewithda_handle_typeda_handle_decision_tree.Pass data to the handle using da_tree_set_training_data_?.
Set optional parameters, such as maximum depth, using da_options_set_? (see options section).
Fit the model using da_tree_fit_?.
Evaluate prediction accuracy on test data using da_tree_score_?.
Make predictions using the fitted model using da_tree_predict_?.
Decision forests
Initialize a
da_handlewithda_handle_typeda_handle_decision_forest.Pass data to the handle using da_forest_set_training_data_?.
Set optional parameters, such as maximum depth, using da_options_set_? (see options section).
Fit the model using da_forest_fit_?.
Evaluate prediction accuracy on test data using da_forest_score_?.
Make predictions using the fitted model using da_forest_predict_?.
Options#
The available Python options are detailed in the aoclda.decision_tree.decision_tree() and
aoclda.decision_forest.decision_forest() class constructors.
The following options can be set using da_options_set_?:
Option name |
Type |
Default |
Description |
Constraints |
|---|---|---|---|---|
block size |
integer |
\(i=256\) |
Set the size of the blocks for parallel computations. |
\(1 \le i \le 2147483647\) |
node minimum samples |
integer |
\(i=2\) |
Minimum number of samples to consider a node for splitting. |
\(2 \le i\) |
scoring function |
string |
\(s=\) gini |
Select scoring function to use. |
\(s=\) cross-entropy, entropy, gini, misclass, misclassification, or misclassification-error. |
maximum depth |
integer |
\(i=29\) |
Set the maximum depth of trees. |
\(0 \le i \le 29\) |
seed |
integer |
\(i=-1\) |
Set random seed for the random number generator. If the value is -1, a random seed is automatically generated. In this case the resulting classification will create non-reproducible results. |
\(-1 \le i\) |
tree building order |
string |
\(s=\) depth first |
Select in which order to explore the nodes. |
\(s=\) breadth first, or depth first. |
feature threshold |
real |
\(r=1e-06\) |
Minimum difference in feature value required for splitting. |
\(0 \le r\) |
bootstrap |
string |
\(s=\) yes |
Select whether to bootstrap the samples in the trees. |
\(s=\) no, or yes. |
bootstrap samples factor |
real |
\(r=0.8\) |
Proportion of samples to draw from the data set to build each tree if ‘bootstrap’ was set to ‘yes’. |
\(0 < r \le 1\) |
features selection |
string |
\(s=\) sqrt |
Select how many features to use for each split. |
\(s=\) all, custom, log2, or sqrt. |
number of trees |
integer |
\(i=100\) |
Set the number of trees to compute. |
\(1 \le i\) |
minimum split score |
real |
\(r=0.03\) |
Minimum score needed for a node to be considered for splitting. |
\(0 \le r \le 1\) |
maximum features |
integer |
\(i=0\) |
Set the number of features to consider when splitting a node. 0 means take all the features. |
\(0 \le i\) |
minimum split improvement |
real |
\(r=0.03\) |
Minimum score improvement needed to consider a split from the parent node. |
\(0 \le r\) |
Choosing the decision forest options#
By default, the number of features to use in each split is set to be the square root of the total number of
features. This can be changed through the features selection option. If features
selection is set to custom, then the value of maximum features will be used. Otherwise, the value of
the maximum features option is ignored.
By default, bootstrap sampling is used, with the number of bootstrap samples set through the bootstrap samples
factor option. However, if the value of the bootstrap option is set to no then no bootstrapping is
done, i.e., each tree uses the full dataset.
The optimal values of the optional parameters is typically problem dependent. Cross-validation is typically used to tune options / hyperparameters.
The memory requirements for decision forests are proportional to \(\textit{number of trees} \times \textit{number of bootstrap samples}\).
Reducing the number of bootstrap samples through the bootstrap samples factor option may
improve performance. If the dataset is large, reducing bootstrap samples factor may be needed to ensure
that that all the data required to fit the decision forest can be stored in DRAM.
Examples#
The code below is supplied with your installation (see Python examples).
1# Copyright (C) 2024 Advanced Micro Devices, Inc. All rights reserved.
2#
3# Redistribution and use in source and binary forms, with or without modification,
4# are permitted provided that the following conditions are met:
5# 1. Redistributions of source code must retain the above copyright notice,
6# this list of conditions and the following disclaimer.
7# 2. Redistributions in binary form must reproduce the above copyright notice,
8# this list of conditions and the following disclaimer in the documentation
9# and/or other materials provided with the distribution.
10# 3. Neither the name of the copyright holder nor the names of its contributors
11# may be used to endorse or promote products derived from this software without
12# specific prior written permission.
13#
14# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
15# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
16# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17# IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
18# INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
19# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
20# OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
21# WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
23# POSSIBILITY OF SUCH DAMAGE.
24#
25
26"""
27Decision tree example Python script
28"""
29
30import sys
31from aoclda.decision_tree import decision_tree
32import numpy as np
33
34def decision_tree_example():
35 """
36 Decision tree classification
37 """
38
39 X_train = np.array([[0.0, 0.0], [1.0, 1.0]])
40 y_train = np.array([0, 1])
41 X_test = np.array([[2., 2.]])
42 y_test = np.array([[1]])
43
44 tree = decision_tree()
45 tree.fit(X_train, y_train)
46
47 pred = tree.predict(X_test)
48 print(f"predictions: [{pred[0]:d}]")
49
50 score = tree.score(X_test, y_test)
51 print(f"score: {score:.3f}")
52
53if __name__ == "__main__":
54 try:
55 decision_tree_example()
56 except RuntimeError:
57 sys.exit(1)
The code below can be found in decision_tree.cpp in the examples folder of your installation.
1/*
2 * Copyright (C) 2023-2024 Advanced Micro Devices, Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without modification,
5 * are permitted provided that the following conditions are met:
6 * 1. Redistributions of source code must retain the above copyright notice,
7 * this list of conditions and the following disclaimer.
8 * 2. Redistributions in binary form must reproduce the above copyright notice,
9 * this list of conditions and the following disclaimer in the documentation
10 * and/or other materials provided with the distribution.
11 * 3. Neither the name of the copyright holder nor the names of its contributors
12 * may be used to endorse or promote products derived from this software without
13 * specific prior written permission.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
17 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
19 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
20 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA,
21 * OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
22 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24 * POSSIBILITY OF SUCH DAMAGE.
25 *
26 */
27
28#include "aoclda.h"
29#include <algorithm>
30#include <iostream>
31#include <vector>
32
33#ifndef DATA_DIR
34#define DATA_DIR "data/df_data"
35#endif
36
37int main() {
38 std::cout << "----------------------------------------" << std::endl;
39 std::cout << "Decision tree model (single precision)" << std::endl;
40 std::cout << "----------------------------------------" << std::endl;
41 std::cout << std::fixed;
42 std::cout.precision(3);
43
44 da_status status;
45 bool pass = true;
46
47 // Read in training data
48 da_datastore csv_store = nullptr;
49 std::string filename = DATA_DIR;
50 filename += "/decision_train.csv";
51 da_int n_cols = 0, n_rows = 0;
52 pass = da_datastore_init(&csv_store) == da_status_success;
53 pass &= da_datastore_options_set_string(csv_store, "CSV datastore precision",
54 "single") == da_status_success;
55 pass &= da_data_load_from_csv(csv_store, filename.c_str()) == da_status_success;
56 pass &= da_data_get_n_cols(csv_store, &n_cols) == da_status_success;
57 pass &= da_data_get_n_rows(csv_store, &n_rows) == da_status_success;
58 pass &=
59 da_data_select_columns(csv_store, "features", 0, n_cols - 2) == da_status_success;
60 pass &= da_data_select_columns(csv_store, "labels", n_cols - 1, n_cols - 1) ==
61 da_status_success;
62 da_int n_features = n_cols - 1;
63 da_int n_samples = n_rows;
64 std::vector<float> X(n_features * n_samples);
65 std::vector<da_int> y(n_rows);
66 pass &= da_data_extract_selection_real_s(csv_store, "features", X.data(), n_rows) ==
67 da_status_success;
68 pass &= da_data_extract_selection_int(csv_store, "labels", y.data(), n_rows) ==
69 da_status_success;
70 da_int n_class = *std::max_element(y.begin(), y.end()) + 1;
71 da_datastore_destroy(&csv_store);
72 if (!pass) {
73 std::cout << "Something went wrong while loading data.\n";
74 return 1;
75 }
76
77 // Set up and train the decision tree
78 da_handle tree_handle = nullptr;
79 pass = da_handle_init_s(&tree_handle, da_handle_decision_tree) == da_status_success;
80 pass &=
81 da_tree_set_training_data_s(tree_handle, n_samples, n_features, n_class, X.data(),
82 n_samples, y.data()) == da_status_success;
83 pass &= da_options_set_int(tree_handle, "maximum depth", 5) == da_status_success;
84 pass &= da_options_set_int(tree_handle, "seed", 77) == da_status_success;
85 pass &= da_options_set_string(tree_handle, "scoring function", "gini") ==
86 da_status_success;
87 if (!pass) {
88 std::cout << "Something went wrong setting up the decision tree data and "
89 "optional parameters.\n";
90 return 1;
91 }
92
93 status = da_tree_fit_s(tree_handle);
94 if (status != da_status_success) {
95 std::cout << "Failure while fitting the tree\n";
96 return 1;
97 }
98 // Read in data for making predictions
99 filename = DATA_DIR;
100 filename += "/decision_test.csv";
101 pass = da_datastore_init(&csv_store) == da_status_success;
102 pass &= da_datastore_options_set_string(csv_store, "CSV datastore precision",
103 "single") == da_status_success;
104 pass &= da_data_load_from_csv(csv_store, filename.c_str()) == da_status_success;
105 pass &= da_data_get_n_rows(csv_store, &n_rows) == da_status_success;
106 pass &=
107 da_data_select_columns(csv_store, "features", 0, n_cols - 2) == da_status_success;
108 pass &= da_data_select_columns(csv_store, "labels", n_cols - 1, n_cols - 1) ==
109 da_status_success;
110 n_samples = n_rows;
111 std::vector<float> X_test(n_features * n_samples);
112 std::vector<da_int> y_test(n_samples);
113 pass &= da_data_extract_selection_real_s(csv_store, "features", X_test.data(),
114 n_samples) == da_status_success;
115 pass &= da_data_extract_selection_int(csv_store, "labels", y_test.data(),
116 n_samples) == da_status_success;
117 da_datastore_destroy(&csv_store);
118 if (!pass) {
119 std::cout << "Something went wrong while loading test data.\n";
120 return 1;
121 }
122
123 // Make predictions with model and evaluate score
124 std::vector<da_int> y_pred(n_samples);
125 pass = da_tree_predict_s(tree_handle, n_samples, n_features, X_test.data(), n_samples,
126 y_pred.data()) == da_status_success;
127 std::vector<float> y_proba(n_samples * n_class);
128 pass = da_tree_predict_proba_s(tree_handle, n_samples, n_features, X_test.data(),
129 n_samples, y_proba.data(), n_class,
130 n_samples) == da_status_success;
131
132 for (da_int i = 0; i < 5; i++) {
133 std::cout << "Class prediction: " << y_pred[i];
134 std::cout << ", Class probabilities: ";
135 for (da_int j = 0; j < n_class - 1; j++)
136 std::cout << y_proba[j * n_samples + i] << ", ";
137 std::cout << y_proba[(n_class - 1) * n_samples + i];
138 std::cout << std::endl;
139 }
140 float mean_accuracy;
141 pass &= da_tree_score_s(tree_handle, n_samples, n_features, X_test.data(), n_samples,
142 y_test.data(), &mean_accuracy);
143 std::cout << "Mean accuracy of the tree on the test data: " << mean_accuracy
144 << std::endl;
145 if (mean_accuracy < 0.75) {
146 std::cout << "Performance unexpectedly low.\n";
147 return 1;
148 }
149 da_handle_destroy(&tree_handle);
150
151 return 0;
152}