102 std::vector<ExampleIndex>& examples,
103 std::vector<LabelType>& label_data,
104 const std::size_t max_depth,
107 const std::size_t num_of_examples = examples.size();
108 if (num_of_examples == 0) {
110 "Reached invalid point in decision tree training: Number of examples is 0!\n");
114 if (max_depth == 0) {
115 stats_estimator_->computeAndSetNodeStats(data_set_, examples, label_data, node);
119 if (examples.size() < min_examples_for_split_) {
120 stats_estimator_->computeAndSetNodeStats(data_set_, examples, label_data, node);
124 if (random_features_at_split_node_) {
126 feature_handler_->createRandomFeatures(num_of_features_, features);
129 std::vector<float> feature_results;
130 std::vector<unsigned char> flags;
132 feature_results.reserve(num_of_examples);
133 flags.reserve(num_of_examples);
136 int best_feature_index = -1;
137 float best_feature_threshold = 0.0f;
138 float best_feature_information_gain = 0.0f;
140 const std::size_t num_of_features = features.size();
141 for (std::size_t feature_index = 0; feature_index < num_of_features;
144 feature_handler_->evaluateFeature(
145 features[feature_index], data_set_, examples, feature_results, flags);
148 if (!thresholds_.empty()) {
151 for (
const float& threshold : thresholds_) {
153 const float information_gain = stats_estimator_->computeInformationGain(
154 data_set_, examples, label_data, feature_results, flags, threshold);
156 if (information_gain > best_feature_information_gain) {
157 best_feature_information_gain = information_gain;
158 best_feature_index =
static_cast<int>(feature_index);
159 best_feature_threshold = threshold;
164 std::vector<float> thresholds;
165 thresholds.reserve(num_of_thresholds_);
166 createThresholdsUniform(num_of_thresholds_, feature_results, thresholds);
170 for (std::size_t threshold_index = 0; threshold_index < num_of_thresholds_;
172 const float threshold = thresholds[threshold_index];
175 const float information_gain = stats_estimator_->computeInformationGain(
176 data_set_, examples, label_data, feature_results, flags, threshold);
178 if (information_gain > best_feature_information_gain) {
179 best_feature_information_gain = information_gain;
180 best_feature_index =
static_cast<int>(feature_index);
181 best_feature_threshold = threshold;
187 if (best_feature_index == -1) {
188 stats_estimator_->computeAndSetNodeStats(data_set_, examples, label_data, node);
193 std::vector<unsigned char> branch_indices;
194 branch_indices.reserve(num_of_examples);
196 feature_handler_->evaluateFeature(
197 features[best_feature_index], data_set_, examples, feature_results, flags);
199 stats_estimator_->computeBranchIndices(
200 feature_results, flags, best_feature_threshold, branch_indices);
203 stats_estimator_->computeAndSetNodeStats(data_set_, examples, label_data, node);
207 const std::size_t num_of_branches = stats_estimator_->getNumOfBranches();
209 std::vector<std::size_t> branch_counts(num_of_branches, 0);
210 for (std::size_t example_index = 0; example_index < num_of_examples;
212 ++branch_counts[branch_indices[example_index]];
215 node.feature = features[best_feature_index];
216 node.threshold = best_feature_threshold;
217 node.sub_nodes.resize(num_of_branches);
219 for (std::size_t branch_index = 0; branch_index < num_of_branches; ++branch_index) {
220 if (branch_counts[branch_index] == 0) {
221 NodeType branch_node;
222 stats_estimator_->computeAndSetNodeStats(
223 data_set_, examples, label_data, branch_node);
226 node.sub_nodes[branch_index] = branch_node;
231 std::vector<LabelType> branch_labels;
232 std::vector<ExampleIndex> branch_examples;
233 branch_labels.reserve(branch_counts[branch_index]);
234 branch_examples.reserve(branch_counts[branch_index]);
236 for (std::size_t example_index = 0; example_index < num_of_examples;
238 if (branch_indices[example_index] == branch_index) {
239 branch_examples.push_back(examples[example_index]);
240 branch_labels.push_back(label_data[example_index]);
244 trainDecisionTreeNode(features,
248 node.sub_nodes[branch_index]);