Point Cloud Library (PCL)  1.14.1
regression_variance_stats_estimator.h
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 
40 #include <pcl/common/common.h>
41 #include <pcl/ml/branch_estimator.h>
42 #include <pcl/ml/stats_estimator.h>
43 
44 #include <istream>
45 #include <ostream>
46 
47 namespace pcl {
48 
49 /** Node for a regression trees which optimizes variance. */
50 template <class FeatureType, class LabelType>
51 class PCL_EXPORTS RegressionVarianceNode {
52 public:
53  /** Constructor. */
54  RegressionVarianceNode() : value(0), variance(0), threshold(0), sub_nodes() {}
55 
56  /** Serializes the node to the specified stream.
57  *
58  * \param[out] stream the destination for the serialization
59  */
60  inline void
61  serialize(std::ostream& stream) const
62  {
63  feature.serialize(stream);
64 
65  stream.write(reinterpret_cast<const char*>(&threshold), sizeof(threshold));
66 
67  stream.write(reinterpret_cast<const char*>(&value), sizeof(value));
68  stream.write(reinterpret_cast<const char*>(&variance), sizeof(variance));
69 
70  const int num_of_sub_nodes = static_cast<int>(sub_nodes.size());
71  stream.write(reinterpret_cast<const char*>(&num_of_sub_nodes),
72  sizeof(num_of_sub_nodes));
73  for (int sub_node_index = 0; sub_node_index < num_of_sub_nodes; ++sub_node_index) {
74  sub_nodes[sub_node_index].serialize(stream);
75  }
76  }
77 
78  /** Deserializes a node from the specified stream.
79  *
80  * \param[in] stream the source for the deserialization
81  */
82  inline void
83  deserialize(std::istream& stream)
84  {
85  feature.deserialize(stream);
86 
87  stream.read(reinterpret_cast<char*>(&threshold), sizeof(threshold));
88 
89  stream.read(reinterpret_cast<char*>(&value), sizeof(value));
90  stream.read(reinterpret_cast<char*>(&variance), sizeof(variance));
91 
92  int num_of_sub_nodes;
93  stream.read(reinterpret_cast<char*>(&num_of_sub_nodes), sizeof(num_of_sub_nodes));
94  sub_nodes.resize(num_of_sub_nodes);
95 
96  if (num_of_sub_nodes > 0) {
97  for (int sub_node_index = 0; sub_node_index < num_of_sub_nodes;
98  ++sub_node_index) {
99  sub_nodes[sub_node_index].deserialize(stream);
100  }
101  }
102  }
103 
104 public:
105  /** The feature associated with the node. */
106  FeatureType feature;
107 
108  /** The threshold applied on the feature response. */
109  float threshold;
110 
111  /** The label value of this node. */
112  LabelType value;
113 
114  /** The variance of the labels that ended up at this node during training. */
115  LabelType variance;
116 
117  /** The child nodes. */
118  std::vector<RegressionVarianceNode> sub_nodes;
119 };
120 
121 /** Statistics estimator for regression trees which optimizes variance. */
122 template <class LabelDataType, class NodeType, class DataSet, class ExampleIndex>
124 : public pcl::StatsEstimator<LabelDataType, NodeType, DataSet, ExampleIndex> {
125 public:
126  /** Constructor. */
128  : branch_estimator_(branch_estimator)
129  {}
130 
131  /** Returns the number of branches the corresponding tree has. */
132  inline std::size_t
134  {
135  // return 2;
136  return branch_estimator_->getNumOfBranches();
137  }
138 
139  /** Returns the label of the specified node.
140  *
141  * \param[in] node the node which label is returned
142  */
143  inline LabelDataType
144  getLabelOfNode(NodeType& node) const
145  {
146  return node.value;
147  }
148 
149  /** Computes the information gain obtained by the specified threshold.
150  *
151  * \param[in] data_set the data set corresponding to the supplied result data
152  * \param[in] examples the examples used for extracting the supplied result data
153  * \param[in] label_data the label data corresponding to the specified examples
154  * \param[in] results the results computed using the specified examples
155  * \param[in] flags the flags corresponding to the results
156  * \param[in] threshold the threshold for which the information gain is computed
157  */
158  float
159  computeInformationGain(DataSet& data_set,
160  std::vector<ExampleIndex>& examples,
161  std::vector<LabelDataType>& label_data,
162  std::vector<float>& results,
163  std::vector<unsigned char>& flags,
164  const float threshold) const
165  {
166  const std::size_t num_of_examples = examples.size();
167  const std::size_t num_of_branches = getNumOfBranches();
168 
169  // compute variance
170  std::vector<LabelDataType> sums(num_of_branches + 1, 0);
171  std::vector<LabelDataType> sqr_sums(num_of_branches + 1, 0);
172  std::vector<std::size_t> branch_element_count(num_of_branches + 1, 0);
173 
174  for (std::size_t branch_index = 0; branch_index < num_of_branches; ++branch_index) {
175  branch_element_count[branch_index] = 1;
176  ++branch_element_count[num_of_branches];
177  }
178 
179  for (std::size_t example_index = 0; example_index < num_of_examples;
180  ++example_index) {
181  unsigned char branch_index;
182  computeBranchIndex(
183  results[example_index], flags[example_index], threshold, branch_index);
184 
185  LabelDataType label = label_data[example_index];
186 
187  sums[branch_index] += label;
188  sums[num_of_branches] += label;
189 
190  sqr_sums[branch_index] += label * label;
191  sqr_sums[num_of_branches] += label * label;
192 
193  ++branch_element_count[branch_index];
194  ++branch_element_count[num_of_branches];
195  }
196 
197  std::vector<float> variances(num_of_branches + 1, 0);
198  for (std::size_t branch_index = 0; branch_index < num_of_branches + 1;
199  ++branch_index) {
200  const float mean_sum =
201  static_cast<float>(sums[branch_index]) / branch_element_count[branch_index];
202  const float mean_sqr_sum = static_cast<float>(sqr_sums[branch_index]) /
203  branch_element_count[branch_index];
204  variances[branch_index] = mean_sqr_sum - mean_sum * mean_sum;
205  }
206 
207  float information_gain = variances[num_of_branches];
208  for (std::size_t branch_index = 0; branch_index < num_of_branches; ++branch_index) {
209  // const float weight = static_cast<float>(sums[branchIndex]) /
210  // sums[numOfBranches];
211  const float weight = static_cast<float>(branch_element_count[branch_index]) /
212  static_cast<float>(branch_element_count[num_of_branches]);
213  information_gain -= weight * variances[branch_index];
214  }
215 
216  return information_gain;
217  }
218 
219  /** Computes the branch indices for all supplied results.
220  *
221  * \param[in] results the results the branch indices will be computed for
222  * \param[in] flags the flags corresponding to the specified results
223  * \param[in] threshold the threshold used to compute the branch indices
224  * \param[out] branch_indices the destination for the computed branch indices
225  */
226  void
227  computeBranchIndices(std::vector<float>& results,
228  std::vector<unsigned char>& flags,
229  const float threshold,
230  std::vector<unsigned char>& branch_indices) const
231  {
232  const std::size_t num_of_results = results.size();
233  const std::size_t num_of_branches = getNumOfBranches();
234 
235  branch_indices.resize(num_of_results);
236  for (std::size_t result_index = 0; result_index < num_of_results; ++result_index) {
237  unsigned char branch_index;
238  computeBranchIndex(
239  results[result_index], flags[result_index], threshold, branch_index);
240  branch_indices[result_index] = branch_index;
241  }
242  }
243 
244  /** Computes the branch index for the specified result.
245  *
246  * \param[in] result the result the branch index will be computed for
247  * \param[in] flag the flag corresponding to the specified result
248  * \param[in] threshold the threshold used to compute the branch index
249  * \param[out] branch_index the destination for the computed branch index
250  */
251  inline void
252  computeBranchIndex(const float result,
253  const unsigned char flag,
254  const float threshold,
255  unsigned char& branch_index) const
256  {
257  branch_estimator_->computeBranchIndex(result, flag, threshold, branch_index);
258  // branch_index = (result > threshold) ? 1 : 0;
259  }
260 
261  /** Computes and sets the statistics for a node.
262  *
263  * \param[in] data_set the data set which is evaluated
264  * \param[in] examples the examples which define which parts of the data set are use
265  * for evaluation
266  * \param[in] label_data the label_data corresponding to the examples
267  * \param[out] node the destination node for the statistics
268  */
269  void
270  computeAndSetNodeStats(DataSet& data_set,
271  std::vector<ExampleIndex>& examples,
272  std::vector<LabelDataType>& label_data,
273  NodeType& node) const
274  {
275  const std::size_t num_of_examples = examples.size();
276 
277  LabelDataType sum = 0.0f;
278  LabelDataType sqr_sum = 0.0f;
279  for (std::size_t example_index = 0; example_index < num_of_examples;
280  ++example_index) {
281  const LabelDataType label = label_data[example_index];
282 
283  sum += label;
284  sqr_sum += label * label;
285  }
286 
287  sum /= num_of_examples;
288  sqr_sum /= num_of_examples;
289 
290  const float variance = sqr_sum - sum * sum;
291 
292  node.value = sum;
293  node.variance = variance;
294  }
295 
296  /** Generates code for branch index computation.
297  *
298  * \param[in] node the node for which code is generated
299  * \param[out] stream the destination for the generated code
300  */
301  void
302  generateCodeForBranchIndexComputation(NodeType& node, std::ostream& stream) const
303  {
304  stream << "ERROR: RegressionVarianceStatsEstimator does not implement "
305  "generateCodeForBranchIndex(...)";
306  }
307 
308  /** Generates code for label output.
309  *
310  * \param[in] node the node for which code is generated
311  * \param[out] stream the destination for the generated code
312  */
313  void
314  generateCodeForOutput(NodeType& node, std::ostream& stream) const
315  {
316  stream << "ERROR: RegressionVarianceStatsEstimator does not implement "
317  "generateCodeForBranchIndex(...)";
318  }
319 
320 private:
321  /// The branch estimator
322  pcl::BranchEstimator* branch_estimator_;
323 };
324 
325 } // namespace pcl
Statistics estimator for regression trees which optimizes variance.
LabelType value
The label value of this node.
Node for a regression trees which optimizes variance.
void computeAndSetNodeStats(DataSet &data_set, std::vector< ExampleIndex > &examples, std::vector< LabelDataType > &label_data, NodeType &node) const
Computes and sets the statistics for a node.
LabelType variance
The variance of the labels that ended up at this node during training.
FeatureType feature
The feature associated with the node.
void serialize(std::ostream &stream) const
Serializes the node to the specified stream.
float threshold
The threshold applied on the feature response.
void computeBranchIndex(const float result, const unsigned char flag, const float threshold, unsigned char &branch_index) const
Computes the branch index for the specified result.
Class interface for gathering statistics for decision tree learning.
void computeBranchIndices(std::vector< float > &results, std::vector< unsigned char > &flags, const float threshold, std::vector< unsigned char > &branch_indices) const
Computes the branch indices for all supplied results.
RegressionVarianceStatsEstimator(BranchEstimator *branch_estimator)
Constructor.
std::vector< RegressionVarianceNode > sub_nodes
The child nodes.
void deserialize(std::istream &stream)
Deserializes a node from the specified stream.
void generateCodeForBranchIndexComputation(NodeType &node, std::ostream &stream) const
Generates code for branch index computation.
LabelDataType getLabelOfNode(NodeType &node) const
Returns the label of the specified node.
void generateCodeForOutput(NodeType &node, std::ostream &stream) const
Generates code for label output.
float computeInformationGain(DataSet &data_set, std::vector< ExampleIndex > &examples, std::vector< LabelDataType > &label_data, std::vector< float > &results, std::vector< unsigned char > &flags, const float threshold) const
Computes the information gain obtained by the specified threshold.
Interface for branch estimators.
std::size_t getNumOfBranches() const
Returns the number of branches the corresponding tree has.