42template <
class FeatureType,
50, num_of_features_(1000)
51, num_of_thresholds_(10)
52, feature_handler_(nullptr)
53, stats_estimator_(nullptr)
57, decision_tree_trainer_data_provider_()
58, random_features_at_split_node_(false)
61template <
class FeatureType,
69template <
class FeatureType,
79 std::vector<FeatureType> features;
81 if (!random_features_at_split_node_)
82 feature_handler_->createRandomFeatures(num_of_features_, features);
88 if (decision_tree_trainer_data_provider_) {
89 std::cerr <<
"use decision_tree_trainer_data_provider_" << std::endl;
91 decision_tree_trainer_data_provider_->getDatasetAndLabels(
92 data_set_, label_data_, examples_);
93 trainDecisionTreeNode(
94 features, examples_, label_data_, max_tree_depth_, tree.
getRoot());
100 trainDecisionTreeNode(
101 features, examples_, label_data_, max_tree_depth_, tree.
getRoot());
105template <
class FeatureType,
113 std::vector<ExampleIndex>& examples,
114 std::vector<LabelType>& label_data,
115 const std::size_t max_depth,
118 const std::size_t num_of_examples = examples.size();
119 if (num_of_examples == 0) {
121 "Reached invalid point in decision tree training: Number of examples is 0!\n");
125 if (max_depth == 0) {
126 stats_estimator_->computeAndSetNodeStats(data_set_, examples, label_data, node);
130 if (examples.size() < min_examples_for_split_) {
131 stats_estimator_->computeAndSetNodeStats(data_set_, examples, label_data, node);
135 if (random_features_at_split_node_) {
137 feature_handler_->createRandomFeatures(num_of_features_, features);
140 std::vector<float> feature_results;
141 std::vector<unsigned char> flags;
143 feature_results.reserve(num_of_examples);
144 flags.reserve(num_of_examples);
147 int best_feature_index = -1;
148 float best_feature_threshold = 0.0f;
149 float best_feature_information_gain = 0.0f;
151 const std::size_t num_of_features = features.size();
152 for (std::size_t feature_index = 0; feature_index < num_of_features;
155 feature_handler_->evaluateFeature(
156 features[feature_index], data_set_, examples, feature_results, flags);
159 if (!thresholds_.empty()) {
162 for (std::size_t threshold_index = 0; threshold_index < thresholds_.size();
165 const float information_gain =
166 stats_estimator_->computeInformationGain(data_set_,
171 thresholds_[threshold_index]);
173 if (information_gain > best_feature_information_gain) {
174 best_feature_information_gain = information_gain;
175 best_feature_index =
static_cast<int>(feature_index);
176 best_feature_threshold = thresholds_[threshold_index];
181 std::vector<float> thresholds;
182 thresholds.reserve(num_of_thresholds_);
183 createThresholdsUniform(num_of_thresholds_, feature_results, thresholds);
187 for (std::size_t threshold_index = 0; threshold_index < num_of_thresholds_;
189 const float threshold = thresholds[threshold_index];
192 const float information_gain = stats_estimator_->computeInformationGain(
193 data_set_, examples, label_data, feature_results, flags, threshold);
195 if (information_gain > best_feature_information_gain) {
196 best_feature_information_gain = information_gain;
197 best_feature_index =
static_cast<int>(feature_index);
198 best_feature_threshold = threshold;
204 if (best_feature_index == -1) {
205 stats_estimator_->computeAndSetNodeStats(data_set_, examples, label_data, node);
210 std::vector<unsigned char> branch_indices;
211 branch_indices.reserve(num_of_examples);
213 feature_handler_->evaluateFeature(
214 features[best_feature_index], data_set_, examples, feature_results, flags);
216 stats_estimator_->computeBranchIndices(
217 feature_results, flags, best_feature_threshold, branch_indices);
220 stats_estimator_->computeAndSetNodeStats(data_set_, examples, label_data, node);
224 const std::size_t num_of_branches = stats_estimator_->getNumOfBranches();
226 std::vector<std::size_t> branch_counts(num_of_branches, 0);
227 for (std::size_t example_index = 0; example_index < num_of_examples;
229 ++branch_counts[branch_indices[example_index]];
232 node.feature = features[best_feature_index];
233 node.threshold = best_feature_threshold;
234 node.sub_nodes.resize(num_of_branches);
236 for (std::size_t branch_index = 0; branch_index < num_of_branches; ++branch_index) {
237 if (branch_counts[branch_index] == 0) {
238 NodeType branch_node;
239 stats_estimator_->computeAndSetNodeStats(
240 data_set_, examples, label_data, branch_node);
243 node.sub_nodes[branch_index] = branch_node;
248 std::vector<LabelType> branch_labels;
249 std::vector<ExampleIndex> branch_examples;
250 branch_labels.reserve(branch_counts[branch_index]);
251 branch_examples.reserve(branch_counts[branch_index]);
253 for (std::size_t example_index = 0; example_index < num_of_examples;
255 if (branch_indices[example_index] == branch_index) {
256 branch_examples.push_back(examples[example_index]);
257 branch_labels.push_back(label_data[example_index]);
261 trainDecisionTreeNode(features,
265 node.sub_nodes[branch_index]);
270template <
class FeatureType,
278 std::vector<float>& values,
279 std::vector<float>& thresholds)
282 float min_value = ::std::numeric_limits<float>::max();
283 float max_value = -::std::numeric_limits<float>::max();
285 const std::size_t num_of_values = values.size();
286 for (std::size_t value_index = 0; value_index < num_of_values; ++value_index) {
287 const float value = values[value_index];
289 if (value < min_value)
291 if (value > max_value)
295 const float range = max_value - min_value;
296 const float step = range /
static_cast<float>(num_of_thresholds + 2);
299 thresholds.resize(num_of_thresholds);
301 for (std::size_t threshold_index = 0; threshold_index < num_of_thresholds;
303 thresholds[threshold_index] =
304 min_value + step * (
static_cast<float>(threshold_index + 1));
Class representing a decision tree.
NodeType & getRoot()
Returns the root node of the tree.
void setRoot(const NodeType &root)
Sets the root node of the tree.
static void createThresholdsUniform(const std::size_t num_of_thresholds, std::vector< float > &values, std::vector< float > &thresholds)
Creates uniformely distrebuted thresholds over the range of the supplied values.
void trainDecisionTreeNode(std::vector< FeatureType > &features, std::vector< ExampleIndex > &examples, std::vector< LabelType > &label_data, std::size_t max_depth, NodeType &node)
Trains a decision tree node from the specified features, label data, and examples.
void train(DecisionTree< NodeType > &tree)
Trains a decision tree using the set training data and settings.
virtual ~DecisionTreeTrainer()
Destructor.
DecisionTreeTrainer()
Constructor.