MLPACK  1.0.7
binary_space_tree.hpp
Go to the documentation of this file.
1 
21 #ifndef __MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP
22 #define __MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP
23 
24 #include <mlpack/core.hpp>
25 
26 #include "../statistic.hpp"
27 
28 namespace mlpack {
29 namespace tree {
30 
49 template<typename BoundType,
50  typename StatisticType = EmptyStatistic,
51  typename MatType = arma::mat>
53 {
54  private:
63  size_t begin;
66  size_t count;
68  size_t leafSize;
70  BoundType bound;
72  StatisticType stat;
78  MatType& dataset;
79 
80  public:
82  typedef MatType Mat;
83 
86  template<typename RuleType>
88 
90  template<typename RuleType>
92 
100  BinarySpaceTree(MatType& data, const size_t leafSize = 20);
101 
112  BinarySpaceTree(MatType& data,
113  std::vector<size_t>& oldFromNew,
114  const size_t leafSize = 20);
115 
129  BinarySpaceTree(MatType& data,
130  std::vector<size_t>& oldFromNew,
131  std::vector<size_t>& newFromOld,
132  const size_t leafSize = 20);
133 
145  BinarySpaceTree(MatType& data,
146  const size_t begin,
147  const size_t count,
148  BinarySpaceTree* parent = NULL,
149  const size_t leafSize = 20);
150 
169  BinarySpaceTree(MatType& data,
170  const size_t begin,
171  const size_t count,
172  std::vector<size_t>& oldFromNew,
173  BinarySpaceTree* parent = NULL,
174  const size_t leafSize = 20);
175 
197  BinarySpaceTree(MatType& data,
198  const size_t begin,
199  const size_t count,
200  std::vector<size_t>& oldFromNew,
201  std::vector<size_t>& newFromOld,
202  BinarySpaceTree* parent = NULL,
203  const size_t leafSize = 20);
204 
211  BinarySpaceTree(const BinarySpaceTree& other);
212 
219 
231  const BinarySpaceTree* FindByBeginCount(size_t begin,
232  size_t count) const;
233 
245  BinarySpaceTree* FindByBeginCount(size_t begin, size_t count);
246 
248  const BoundType& Bound() const { return bound; }
250  BoundType& Bound() { return bound; }
251 
253  const StatisticType& Stat() const { return stat; }
255  StatisticType& Stat() { return stat; }
256 
258  bool IsLeaf() const;
259 
261  size_t LeafSize() const { return leafSize; }
263  size_t& LeafSize() { return leafSize; }
264 
266  size_t ExtendTree(const size_t level);
267 
269  BinarySpaceTree* Left() const { return left; }
271  BinarySpaceTree*& Left() { return left; }
272 
274  BinarySpaceTree* Right() const { return right; }
276  BinarySpaceTree*& Right() { return right; }
277 
279  BinarySpaceTree* Parent() const { return parent; }
281  BinarySpaceTree*& Parent() { return parent; }
282 
284  size_t SplitDimension() const { return splitDimension; }
286  size_t& SplitDimension() { return splitDimension; }
287 
289  const arma::mat& Dataset() const { return dataset; }
291  arma::mat& Dataset() { return dataset; }
292 
294  typename BoundType::MetricType Metric() const { return bound.Metric(); }
295 
297  void Centroid(arma::vec& centroid) { bound.Centroid(centroid); }
298 
300  size_t NumChildren() const;
301 
309  double FurthestDescendantDistance() const;
310 
317  BinarySpaceTree& Child(const size_t child) const;
318 
320  size_t NumPoints() const;
321 
327  size_t NumDescendants() const;
328 
336  size_t Descendant(const size_t index) const;
337 
346  size_t Point(const size_t index) const;
347 
349  double MinDistance(const BinarySpaceTree* other) const
350  {
351  return bound.MinDistance(other->Bound());
352  }
353 
355  double MaxDistance(const BinarySpaceTree* other) const
356  {
357  return bound.MaxDistance(other->Bound());
358  }
359 
362  {
363  return bound.RangeDistance(other->Bound());
364  }
365 
367  double MinDistance(const arma::vec& point) const
368  {
369  return bound.MinDistance(point);
370  }
371 
373  double MaxDistance(const arma::vec& point) const
374  {
375  return bound.MaxDistance(point);
376  }
377 
379  math::Range RangeDistance(const arma::vec& point) const
380  {
381  return bound.RangeDistance(point);
382  }
383 
387  size_t GetSplitDimension() const;
388 
392  size_t TreeSize() const;
393 
398  size_t TreeDepth() const;
399 
401  size_t Begin() const { return begin; }
403  size_t& Begin() { return begin; }
404 
408  size_t End() const;
409 
411  size_t Count() const { return count; }
413  size_t& Count() { return count; }
414 
416  static bool HasSelfChildren() { return false; }
417 
418  private:
423  BinarySpaceTree(const size_t begin,
424  const size_t count,
425  BoundType bound,
426  StatisticType stat,
427  const int leafSize = 20) :
428  left(NULL),
429  right(NULL),
430  begin(begin),
431  count(count),
432  bound(bound),
433  stat(stat),
434  leafSize(leafSize) { }
435 
437  {
438  return new BinarySpaceTree(begin, count, bound, stat, leafSize);
439  }
440 
446  void SplitNode(MatType& data);
447 
455  void SplitNode(MatType& data, std::vector<size_t>& oldFromNew);
456 
465  size_t GetSplitIndex(MatType& data, int splitDim, double splitVal);
466 
477  size_t GetSplitIndex(MatType& data, int splitDim, double splitVal,
478  std::vector<size_t>& oldFromNew);
479  public:
483  std::string ToString() const;
484 
485 };
486 
487 }; // namespace tree
488 }; // namespace mlpack
489 
490 // Include implementation.
491 #include "binary_space_tree_impl.hpp"
492 
493 #endif