mlpack  2.0.1
binary_space_tree.hpp
Go to the documentation of this file.
1 
13 #ifndef __MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP
14 #define __MLPACK_CORE_TREE_BINARY_SPACE_TREE_BINARY_SPACE_TREE_HPP
15 
16 #include <mlpack/core.hpp>
17 
18 #include "../statistic.hpp"
19 #include "midpoint_split.hpp"
20 
21 namespace mlpack {
22 namespace tree {
23 
49 template<typename MetricType,
50  typename StatisticType = EmptyStatistic,
51  typename MatType = arma::mat,
52  template<typename BoundMetricType> class BoundType = bound::HRectBound,
53  template<typename SplitBoundType, typename SplitMatType>
54  class SplitType = MidpointSplit>
56 {
57  private:
66  size_t begin;
69  size_t count;
71  BoundType<MetricType> bound;
73  StatisticType stat;
83  MatType* dataset;
84 
85  public:
87  typedef MatType Mat;
88 
91  template<typename RuleType>
93 
95  template<typename RuleType>
97 
98  template<typename RuleType>
100 
109  BinarySpaceTree(const MatType& data, const size_t maxLeafSize = 20);
110 
123  BinarySpaceTree(const MatType& data,
124  std::vector<size_t>& oldFromNew,
125  const size_t maxLeafSize = 20);
126 
142  BinarySpaceTree(const MatType& data,
143  std::vector<size_t>& oldFromNew,
144  std::vector<size_t>& newFromOld,
145  const size_t maxLeafSize = 20);
146 
156  BinarySpaceTree(MatType&& data,
157  const size_t maxLeafSize = 20);
158 
171  BinarySpaceTree(MatType&& data,
172  std::vector<size_t>& oldFromNew,
173  const size_t maxLeafSize = 20);
174 
190  BinarySpaceTree(MatType&& data,
191  std::vector<size_t>& oldFromNew,
192  std::vector<size_t>& newFromOld,
193  const size_t maxLeafSize = 20);
194 
207  const size_t begin,
208  const size_t count,
209  SplitType<BoundType<MetricType>, MatType>& splitter,
210  const size_t maxLeafSize = 20);
211 
231  const size_t begin,
232  const size_t count,
233  std::vector<size_t>& oldFromNew,
234  SplitType<BoundType<MetricType>, MatType>& splitter,
235  const size_t maxLeafSize = 20);
236 
259  const size_t begin,
260  const size_t count,
261  std::vector<size_t>& oldFromNew,
262  std::vector<size_t>& newFromOld,
263  SplitType<BoundType<MetricType>, MatType>& splitter,
264  const size_t maxLeafSize = 20);
265 
272  BinarySpaceTree(const BinarySpaceTree& other);
273 
279 
285  template<typename Archive>
287  Archive& ar,
288  const typename boost::enable_if<typename Archive::is_loading>::type* = 0);
289 
296 
298  const BoundType<MetricType>& Bound() const { return bound; }
300  BoundType<MetricType>& Bound() { return bound; }
301 
303  const StatisticType& Stat() const { return stat; }
305  StatisticType& Stat() { return stat; }
306 
308  bool IsLeaf() const;
309 
311  BinarySpaceTree* Left() const { return left; }
313  BinarySpaceTree*& Left() { return left; }
314 
316  BinarySpaceTree* Right() const { return right; }
318  BinarySpaceTree*& Right() { return right; }
319 
321  BinarySpaceTree* Parent() const { return parent; }
323  BinarySpaceTree*& Parent() { return parent; }
324 
326  const MatType& Dataset() const { return *dataset; }
328  MatType& Dataset() { return *dataset; }
329 
331  MetricType Metric() const { return MetricType(); }
332 
334  size_t NumChildren() const;
335 
340  double FurthestPointDistance() const;
341 
349  double FurthestDescendantDistance() const;
350 
352  double MinimumBoundDistance() const;
353 
356  double ParentDistance() const { return parentDistance; }
359  double& ParentDistance() { return parentDistance; }
360 
367  BinarySpaceTree& Child(const size_t child) const;
368 
369  BinarySpaceTree*& ChildPtr(const size_t child)
370  { return (child == 0) ? left : right; }
371 
373  size_t NumPoints() const;
374 
380  size_t NumDescendants() const;
381 
389  size_t Descendant(const size_t index) const;
390 
399  size_t Point(const size_t index) const;
400 
402  double MinDistance(const BinarySpaceTree* other) const
403  {
404  return bound.MinDistance(other->Bound());
405  }
406 
408  double MaxDistance(const BinarySpaceTree* other) const
409  {
410  return bound.MaxDistance(other->Bound());
411  }
412 
415  {
416  return bound.RangeDistance(other->Bound());
417  }
418 
420  template<typename VecType>
421  double MinDistance(const VecType& point,
422  typename boost::enable_if<IsVector<VecType> >::type* = 0)
423  const
424  {
425  return bound.MinDistance(point);
426  }
427 
429  template<typename VecType>
430  double MaxDistance(const VecType& point,
431  typename boost::enable_if<IsVector<VecType> >::type* = 0)
432  const
433  {
434  return bound.MaxDistance(point);
435  }
436 
438  template<typename VecType>
440  RangeDistance(const VecType& point,
441  typename boost::enable_if<IsVector<VecType> >::type* = 0) const
442  {
443  return bound.RangeDistance(point);
444  }
445 
447  size_t Begin() const { return begin; }
449  size_t& Begin() { return begin; }
450 
452  size_t Count() const { return count; }
454  size_t& Count() { return count; }
455 
457  static bool HasSelfChildren() { return false; }
458 
460  void Center(arma::vec& center) { bound.Center(center); }
461 
462  private:
469  void SplitNode(const size_t maxLeafSize,
470  SplitType<BoundType<MetricType>, MatType>& splitter);
471 
480  void SplitNode(std::vector<size_t>& oldFromNew,
481  const size_t maxLeafSize,
482  SplitType<BoundType<MetricType>, MatType>& splitter);
483 
484  protected:
491  BinarySpaceTree();
492 
494  friend class boost::serialization::access;
495 
496  public:
500  template<typename Archive>
501  void Serialize(Archive& ar, const unsigned int version);
502 };
503 
504 } // namespace tree
505 } // namespace mlpack
506 
507 // Include implementation.
508 #include "binary_space_tree_impl.hpp"
509 
510 // Include everything else, if necessary.
511 #include "../binary_space_tree.hpp"
512 
513 #endif
BinarySpaceTree *& Parent()
Modify the parent of this node.
BinarySpaceTree * left
The left child node.
void Serialize(Archive &ar, const unsigned int version)
Serialize the tree.
MatType * dataset
The dataset.
A dual-tree traverser for binary space trees; see dual_tree_traverser.hpp.
Linear algebra utility functions, generally performed on matrices or vectors.
MatType Mat
So other classes can use TreeType::Mat.
const BoundType< MetricType > & Bound() const
Return the bound object for this node.
BinarySpaceTree * right
The right child node.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
size_t NumDescendants() const
Return the number of descendants of this node.
double MinDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum distance to another point.
double FurthestPointDistance() const
Return the furthest distance to a point held in this node.
BinarySpaceTree * Left() const
Gets the left child of this node.
BoundType< MetricType > bound
The bound object for this node.
double & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
MatType & Dataset()
Modify the dataset which the tree is built on. Be careful!
A binary space partitioning tree, such as a KD-tree or a ball tree.
double ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
BinarySpaceTree * Right() const
Gets the right child of this node.
static bool HasSelfChildren()
Returns false: this tree type does not have self children.
double MaxDistance(const BinarySpaceTree *other) const
Return the maximum distance to another node.
double minimumBoundDistance
The minimum distance from the center to any edge of the bound.
~BinarySpaceTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn...
A binary space partitioning tree node is split into its left and right child.
BinarySpaceTree *& Right()
Modify the right child of this node.
double MinimumBoundDistance() const
Return the minimum distance from the center of the node to any bound edge.
Hyper-rectangle bound for an L-metric.
Definition: hrectbound.hpp:56
double furthestDescendantDistance
The worst possible distance to the furthest descendant, cached to speed things up.
math::Range RangeDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum and maximum distance to another point.
MetricType Metric() const
Get the metric that the tree uses.
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
double parentDistance
The distance from the centroid of this node to the centroid of the parent.
const MatType & Dataset() const
Get the dataset which the tree is built on.
Simple real-valued range.
Definition: range.hpp:21
void Center(arma::vec &center)
Store the center of the bounding region in the given vector.
StatisticType & Stat()
Return the statistic object for this node.
A single-tree traverser for binary space trees; see single_tree_traverser.hpp for implementation...
BinarySpaceTree()
A default constructor.
Include all of the base components required to write MLPACK methods, and the main MLPACK Doxygen docu...
BinarySpaceTree *& ChildPtr(const size_t child)
size_t Descendant(const size_t index) const
Return the index (with reference to the dataset) of a particular descendant of this node...
size_t NumPoints() const
Return the number of points in this node (0 if not a leaf).
const StatisticType & Stat() const
Return the statistic object for this node.
BinarySpaceTree * Parent() const
Gets the parent of this node.
BinarySpaceTree & Child(const size_t child) const
Return the specified child (0 will be left, 1 will be right).
size_t Begin() const
Return the index of the beginning point of this subset.
BoundType< MetricType > & Bound()
Return the bound object for this node.
size_t & Count()
Modify the number of points in this subset.
void SplitNode(const size_t maxLeafSize, SplitType< BoundType< MetricType >, MatType > &splitter)
Splits the current node, assigning its left and right children recursively.
double MinDistance(const BinarySpaceTree *other) const
Return the minimum distance to another node.
size_t begin
The index of the first point in the dataset contained in this node (and its children).
size_t Count() const
Return the number of points in this subset.
size_t count
The number of points of the dataset contained in this node (and its children).
double MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the maximum distance to another point.
math::Range RangeDistance(const BinarySpaceTree *other) const
Return the minimum and maximum distance to another node.
StatisticType stat
Any extra data contained in the node.
BinarySpaceTree *& Left()
Modify the left child of this node.
double FurthestDescendantDistance() const
Return the furthest possible descendant distance.
size_t & Begin()
Modify the index of the beginning point of this subset.
If value == true, then VecType is some sort of Armadillo vector or subview.
Definition: arma_traits.hpp:37
size_t NumChildren() const
Return the number of children in this node.
BinarySpaceTree * parent
The parent node (NULL if this is the root of the tree).
Empty statistic if you are not interested in storing statistics in your tree.
Definition: statistic.hpp:26