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() const
Gets the parent of this node.
size_t NumDescendants() const
Return the number of descendants of this node.
BinarySpaceTree *& Parent()
Modify the parent of this node.
const StatisticType & Stat() const
Return the statistic object for this node.
double MinimumBoundDistance() const
Return the minimum distance from the center of the node to any bound edge.
BinarySpaceTree & Child(const size_t child) const
Return the specified child (0 will be left, 1 will be right).
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.
BinarySpaceTree * right
The right child node.
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 Count() const
Return the number of points in this subset.
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.
double MinDistance(const BinarySpaceTree *other) const
Return the minimum distance to another 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.
const BoundType< MetricType > & Bound() const
Return the bound object for this node.
BinarySpaceTree * Right() const
Gets the right child of this 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.
static bool HasSelfChildren()
Returns false: this tree type does not have self children.
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.
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
BinarySpaceTree *& Right()
Modify the right child of this node.
double FurthestDescendantDistance() const
Return the furthest possible descendant distance.
size_t NumPoints() const
Return the number of points in this node (0 if not a leaf).
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.
double parentDistance
The distance from the centroid of this node to the centroid of the parent.
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...
math::Range RangeDistance(const BinarySpaceTree *other) const
Return the minimum and maximum distance to another node.
BinarySpaceTree * Left() const
Gets the left child of this node.
const MatType & Dataset() const
Get the dataset which the tree is built on.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
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)
double MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the maximum distance to another point.
MetricType Metric() const
Get the metric that the tree uses.
size_t Begin() const
Return the index of the beginning point of this subset.
double MaxDistance(const BinarySpaceTree *other) const
Return the maximum distance to another node.
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 ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
size_t begin
The index of the first point in the dataset contained in this node (and its children).
size_t count
The number of points of the dataset contained in this node (and its children).
StatisticType stat
Any extra data contained in the node.
BinarySpaceTree *& Left()
Modify the left child of this node.
math::Range RangeDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum and maximum distance to another point.
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
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
size_t NumChildren() const
Return the number of children in this node.