Point Cloud Library (PCL) 1.12.0
Loading...
Searching...
No Matches
decision_tree_trainer.hpp
1/*
2 * Software License Agreement (BSD License)
3 *
4 * Point Cloud Library (PCL) - www.pointclouds.org
5 * Copyright (c) 2010-2011, Willow Garage, Inc.
6 *
7 * All rights reserved.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 *
13 * * Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * * Redistributions in binary form must reproduce the above
16 * copyright notice, this list of conditions and the following
17 * disclaimer in the documentation and/or other materials provided
18 * with the distribution.
19 * * Neither the name of Willow Garage, Inc. nor the names of its
20 * contributors may be used to endorse or promote products derived
21 * from this software without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
26 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
27 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
28 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
29 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
30 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
31 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
33 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
34 * POSSIBILITY OF SUCH DAMAGE.
35 *
36 */
37
38#pragma once
39
40namespace pcl {
41
42template <class FeatureType,
43 class DataSet,
44 class LabelType,
45 class ExampleIndex,
46 class NodeType>
49: max_tree_depth_(15)
50, num_of_features_(1000)
51, num_of_thresholds_(10)
52, feature_handler_(nullptr)
53, stats_estimator_(nullptr)
54, data_set_()
55, label_data_()
56, examples_()
57, decision_tree_trainer_data_provider_()
58, random_features_at_split_node_(false)
59{}
60
61template <class FeatureType,
62 class DataSet,
63 class LabelType,
64 class ExampleIndex,
65 class NodeType>
69
70template <class FeatureType,
71 class DataSet,
72 class LabelType,
73 class ExampleIndex,
74 class NodeType>
75void
78{
79 // create random features
80 std::vector<FeatureType> features;
81
82 if (!random_features_at_split_node_)
83 feature_handler_->createRandomFeatures(num_of_features_, features);
84
85 // recursively build decision tree
86 NodeType root_node;
87 tree.setRoot(root_node);
88
89 if (decision_tree_trainer_data_provider_) {
90 std::cerr << "use decision_tree_trainer_data_provider_" << std::endl;
91
92 decision_tree_trainer_data_provider_->getDatasetAndLabels(
93 data_set_, label_data_, examples_);
94 trainDecisionTreeNode(
95 features, examples_, label_data_, max_tree_depth_, tree.getRoot());
96 label_data_.clear();
97 data_set_.clear();
98 examples_.clear();
99 }
100 else {
101 trainDecisionTreeNode(
102 features, examples_, label_data_, max_tree_depth_, tree.getRoot());
103 }
104}
105
106template <class FeatureType,
107 class DataSet,
108 class LabelType,
109 class ExampleIndex,
110 class NodeType>
111void
113 trainDecisionTreeNode(std::vector<FeatureType>& features,
114 std::vector<ExampleIndex>& examples,
115 std::vector<LabelType>& label_data,
116 const std::size_t max_depth,
117 NodeType& node)
118{
119 const std::size_t num_of_examples = examples.size();
120 if (num_of_examples == 0) {
121 PCL_ERROR(
122 "Reached invalid point in decision tree training: Number of examples is 0!\n");
123 return;
124 };
125
126 if (max_depth == 0) {
127 stats_estimator_->computeAndSetNodeStats(data_set_, examples, label_data, node);
128 return;
129 };
130
131 if (examples.size() < min_examples_for_split_) {
132 stats_estimator_->computeAndSetNodeStats(data_set_, examples, label_data, node);
133 return;
134 }
135
136 if (random_features_at_split_node_) {
137 features.clear();
138 feature_handler_->createRandomFeatures(num_of_features_, features);
139 }
140
141 std::vector<float> feature_results;
142 std::vector<unsigned char> flags;
143
144 feature_results.reserve(num_of_examples);
145 flags.reserve(num_of_examples);
146
147 // find best feature for split
148 int best_feature_index = -1;
149 float best_feature_threshold = 0.0f;
150 float best_feature_information_gain = 0.0f;
151
152 const std::size_t num_of_features = features.size();
153 for (std::size_t feature_index = 0; feature_index < num_of_features;
154 ++feature_index) {
155 // evaluate features
156 feature_handler_->evaluateFeature(
157 features[feature_index], data_set_, examples, feature_results, flags);
158
159 // get list of thresholds
160 if (!thresholds_.empty()) {
161 // compute information gain for each threshold and store threshold with highest
162 // information gain
163 for (std::size_t threshold_index = 0; threshold_index < thresholds_.size();
164 ++threshold_index) {
165
166 const float information_gain =
167 stats_estimator_->computeInformationGain(data_set_,
168 examples,
169 label_data,
170 feature_results,
171 flags,
172 thresholds_[threshold_index]);
173
174 if (information_gain > best_feature_information_gain) {
175 best_feature_information_gain = information_gain;
176 best_feature_index = static_cast<int>(feature_index);
177 best_feature_threshold = thresholds_[threshold_index];
178 }
179 }
180 }
181 else {
182 std::vector<float> thresholds;
183 thresholds.reserve(num_of_thresholds_);
184 createThresholdsUniform(num_of_thresholds_, feature_results, thresholds);
185
186 // compute information gain for each threshold and store threshold with highest
187 // information gain
188 for (std::size_t threshold_index = 0; threshold_index < num_of_thresholds_;
189 ++threshold_index) {
190 const float threshold = thresholds[threshold_index];
191
192 // compute information gain
193 const float information_gain = stats_estimator_->computeInformationGain(
194 data_set_, examples, label_data, feature_results, flags, threshold);
195
196 if (information_gain > best_feature_information_gain) {
197 best_feature_information_gain = information_gain;
198 best_feature_index = static_cast<int>(feature_index);
199 best_feature_threshold = threshold;
200 }
201 }
202 }
203 }
204
205 if (best_feature_index == -1) {
206 stats_estimator_->computeAndSetNodeStats(data_set_, examples, label_data, node);
207 return;
208 }
209
210 // get branch indices for best feature and best threshold
211 std::vector<unsigned char> branch_indices;
212 branch_indices.reserve(num_of_examples);
213 {
214 feature_handler_->evaluateFeature(
215 features[best_feature_index], data_set_, examples, feature_results, flags);
216
217 stats_estimator_->computeBranchIndices(
218 feature_results, flags, best_feature_threshold, branch_indices);
219 }
220
221 stats_estimator_->computeAndSetNodeStats(data_set_, examples, label_data, node);
222
223 // separate data
224 {
225 const std::size_t num_of_branches = stats_estimator_->getNumOfBranches();
226
227 std::vector<std::size_t> branch_counts(num_of_branches, 0);
228 for (std::size_t example_index = 0; example_index < num_of_examples;
229 ++example_index) {
230 ++branch_counts[branch_indices[example_index]];
231 }
232
233 node.feature = features[best_feature_index];
234 node.threshold = best_feature_threshold;
235 node.sub_nodes.resize(num_of_branches);
236
237 for (std::size_t branch_index = 0; branch_index < num_of_branches; ++branch_index) {
238 if (branch_counts[branch_index] == 0) {
239 NodeType branch_node;
240 stats_estimator_->computeAndSetNodeStats(
241 data_set_, examples, label_data, branch_node);
242 // branch_node->num_of_sub_nodes = 0;
243
244 node.sub_nodes[branch_index] = branch_node;
245
246 continue;
247 }
248
249 std::vector<LabelType> branch_labels;
250 std::vector<ExampleIndex> branch_examples;
251 branch_labels.reserve(branch_counts[branch_index]);
252 branch_examples.reserve(branch_counts[branch_index]);
253
254 for (std::size_t example_index = 0; example_index < num_of_examples;
255 ++example_index) {
256 if (branch_indices[example_index] == branch_index) {
257 branch_examples.push_back(examples[example_index]);
258 branch_labels.push_back(label_data[example_index]);
259 }
260 }
261
262 trainDecisionTreeNode(features,
263 branch_examples,
264 branch_labels,
265 max_depth - 1,
266 node.sub_nodes[branch_index]);
267 }
268 }
269}
270
271template <class FeatureType,
272 class DataSet,
273 class LabelType,
274 class ExampleIndex,
275 class NodeType>
276void
278 createThresholdsUniform(const std::size_t num_of_thresholds,
279 std::vector<float>& values,
280 std::vector<float>& thresholds)
281{
282 // estimate range of values
283 float min_value = ::std::numeric_limits<float>::max();
284 float max_value = -::std::numeric_limits<float>::max();
285
286 const std::size_t num_of_values = values.size();
287 for (std::size_t value_index = 0; value_index < num_of_values; ++value_index) {
288 const float value = values[value_index];
289
290 if (value < min_value)
291 min_value = value;
292 if (value > max_value)
293 max_value = value;
294 }
295
296 const float range = max_value - min_value;
297 const float step = range / static_cast<float>(num_of_thresholds + 2);
298
299 // compute thresholds
300 thresholds.resize(num_of_thresholds);
301
302 for (std::size_t threshold_index = 0; threshold_index < num_of_thresholds;
303 ++threshold_index) {
304 thresholds[threshold_index] =
305 min_value + step * (static_cast<float>(threshold_index + 1));
306 }
307}
308
309} // namespace pcl
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.