mlpack  1.0.12
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 #include "mean_split.hpp"
18 
19 #include "../statistic.hpp"
20 
21 namespace mlpack {
22 namespace tree {
23 
47 template<typename BoundType,
48  typename StatisticType = EmptyStatistic,
49  typename MatType = arma::mat,
50  typename SplitType = MeanSplit<BoundType, MatType> >
52 {
53  private:
62  size_t begin;
65  size_t count;
67  size_t maxLeafSize;
69  BoundType bound;
71  StatisticType stat;
82  MatType& dataset;
83 
84  public:
86  typedef MatType Mat;
87 
90  template<typename RuleType>
92 
94  template<typename RuleType>
96 
104  BinarySpaceTree(MatType& data, const size_t maxLeafSize = 20);
105 
116  BinarySpaceTree(MatType& data,
117  std::vector<size_t>& oldFromNew,
118  const size_t maxLeafSize = 20);
119 
133  BinarySpaceTree(MatType& data,
134  std::vector<size_t>& oldFromNew,
135  std::vector<size_t>& newFromOld,
136  const size_t maxLeafSize = 20);
137 
149  BinarySpaceTree(MatType& data,
150  const size_t begin,
151  const size_t count,
152  BinarySpaceTree* parent = NULL,
153  const size_t maxLeafSize = 20);
154 
173  BinarySpaceTree(MatType& data,
174  const size_t begin,
175  const size_t count,
176  std::vector<size_t>& oldFromNew,
177  BinarySpaceTree* parent = NULL,
178  const size_t maxLeafSize = 20);
179 
201  BinarySpaceTree(MatType& data,
202  const size_t begin,
203  const size_t count,
204  std::vector<size_t>& oldFromNew,
205  std::vector<size_t>& newFromOld,
206  BinarySpaceTree* parent = NULL,
207  const size_t maxLeafSize = 20);
208 
215  BinarySpaceTree(const BinarySpaceTree& other);
216 
223 
235  const BinarySpaceTree* FindByBeginCount(size_t begin,
236  size_t count) const;
237 
249  BinarySpaceTree* FindByBeginCount(size_t begin, size_t count);
250 
252  const BoundType& Bound() const { return bound; }
254  BoundType& Bound() { return bound; }
255 
257  const StatisticType& Stat() const { return stat; }
259  StatisticType& Stat() { return stat; }
260 
262  bool IsLeaf() const;
263 
265  size_t MaxLeafSize() const { return maxLeafSize; }
267  size_t& MaxLeafSize() { return maxLeafSize; }
268 
270  size_t ExtendTree(const size_t level);
271 
273  BinarySpaceTree* Left() const { return left; }
275  BinarySpaceTree*& Left() { return left; }
276 
278  BinarySpaceTree* Right() const { return right; }
280  BinarySpaceTree*& Right() { return right; }
281 
283  BinarySpaceTree* Parent() const { return parent; }
285  BinarySpaceTree*& Parent() { return parent; }
286 
288  size_t SplitDimension() const { return splitDimension; }
290  size_t& SplitDimension() { return splitDimension; }
291 
293  const MatType& Dataset() const { return dataset; }
295  MatType& Dataset() { return dataset; }
296 
298  typename BoundType::MetricType Metric() const { return bound.Metric(); }
299 
301  void Centroid(arma::vec& centroid) { bound.Centroid(centroid); }
302 
304  size_t NumChildren() const;
305 
310  double FurthestPointDistance() const;
311 
319  double FurthestDescendantDistance() const;
320 
322  double MinimumBoundDistance() const;
323 
326  double ParentDistance() const { return parentDistance; }
329  double& ParentDistance() { return parentDistance; }
330 
337  BinarySpaceTree& Child(const size_t child) const;
338 
340  size_t NumPoints() const;
341 
347  size_t NumDescendants() const;
348 
356  size_t Descendant(const size_t index) const;
357 
366  size_t Point(const size_t index) const;
367 
369  double MinDistance(const BinarySpaceTree* other) const
370  {
371  return bound.MinDistance(other->Bound());
372  }
373 
375  double MaxDistance(const BinarySpaceTree* other) const
376  {
377  return bound.MaxDistance(other->Bound());
378  }
379 
382  {
383  return bound.RangeDistance(other->Bound());
384  }
385 
387  template<typename VecType>
388  double MinDistance(const VecType& point,
389  typename boost::enable_if<IsVector<VecType> >::type* = 0)
390  const
391  {
392  return bound.MinDistance(point);
393  }
394 
396  template<typename VecType>
397  double MaxDistance(const VecType& point,
398  typename boost::enable_if<IsVector<VecType> >::type* = 0)
399  const
400  {
401  return bound.MaxDistance(point);
402  }
403 
405  template<typename VecType>
407  RangeDistance(const VecType& point,
408  typename boost::enable_if<IsVector<VecType> >::type* = 0) const
409  {
410  return bound.RangeDistance(point);
411  }
412 
416  size_t GetSplitDimension() const;
417 
421  size_t TreeSize() const;
422 
427  size_t TreeDepth() const;
428 
430  size_t Begin() const { return begin; }
432  size_t& Begin() { return begin; }
433 
437  size_t End() const;
438 
440  size_t Count() const { return count; }
442  size_t& Count() { return count; }
443 
445  static bool HasSelfChildren() { return false; }
446 
447  private:
452  BinarySpaceTree(const size_t begin,
453  const size_t count,
454  BoundType bound,
455  StatisticType stat,
456  const int maxLeafSize = 20) :
457  left(NULL),
458  right(NULL),
459  begin(begin),
460  count(count),
461  bound(bound),
462  stat(stat),
463  maxLeafSize(maxLeafSize) { }
464 
466  {
467  return new BinarySpaceTree(begin, count, bound, stat, maxLeafSize);
468  }
469 
475  void SplitNode(MatType& data);
476 
484  void SplitNode(MatType& data, std::vector<size_t>& oldFromNew);
485 
486  public:
490  std::string ToString() const;
491 
492 };
493 
494 }; // namespace tree
495 }; // namespace mlpack
496 
497 // Include implementation.
498 #include "binary_space_tree_impl.hpp"
499 
500 #endif
double MinDistance(const BinarySpaceTree *other) const
Return the minimum distance to another node.
void SplitNode(MatType &data)
Splits the current node, assigning its left and right children recursively.
size_t NumChildren() const
Return the number of children in this node.
size_t Point(const size_t index) const
Return the index (with reference to the dataset) of a particular point in this node.
BinarySpaceTree * left
The left child node.
size_t TreeSize() const
Obtains the number of nodes in the tree, starting with this.
BinarySpaceTree *& Parent()
Modify the parent of this node.
std::string ToString() const
Returns a string representation of this object.
A dual-tree traverser for binary space trees; see dual_tree_traverser.hpp.
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: load.hpp:23
size_t & Begin()
Modify the index of the beginning point of this subset.
double parentDistance
The distance from the centroid of this node to the centroid of the parent.
BinarySpaceTree * parent
The parent node (NULL if this is the root of the tree).
BinarySpaceTree * Left() const
Gets the left child of this node.
MatType & dataset
The dataset.
BinarySpaceTree *& Right()
Modify the right 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 TreeDepth() const
Obtains the number of levels below this node in the tree, starting with this.
double minimumBoundDistance
The minimum distance from the center to any edge of the bound.
double furthestDescendantDistance
The worst possible distance to the furthest descendant, cached to speed things up.
BinarySpaceTree(const size_t begin, const size_t count, BoundType bound, StatisticType stat, const int maxLeafSize=20)
Private copy constructor, available only to fill (pad) the tree to a specified level.
double MaxDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the maximum distance to another point.
BoundType bound
The bound object for this node.
BinarySpaceTree & Child(const size_t child) const
Return the specified child (0 will be left, 1 will be right).
double FurthestDescendantDistance() const
Return the furthest possible descendant distance.
const BinarySpaceTree * FindByBeginCount(size_t begin, size_t count) const
Find a node in this tree by its begin and count (const).
size_t SplitDimension() const
Get the split dimension for this node.
const StatisticType & Stat() const
Return the statistic object for this node.
size_t splitDimension
The dimension this node split on if it is a parent.
~BinarySpaceTree()
Deletes this node, deallocating the memory for the children and calling their destructors in turn...
size_t Count() const
Return the number of points in this subset.
math::Range RangeDistance(const BinarySpaceTree *other) const
Return the minimum and maximum distance to another node.
size_t ExtendTree(const size_t level)
Fills the tree to the specified level.
size_t NumDescendants() const
Return the number of descendants of this node.
size_t begin
The index of the first point in the dataset contained in this node (and its children).
A binary space partitioning tree, such as a KD-tree or a ball tree.
BinarySpaceTree * right
The right child node.
size_t & MaxLeafSize()
Modify the max leaf size.
double MinDistance(const VecType &point, typename boost::enable_if< IsVector< VecType > >::type *=0) const
Return the minimum distance to another point.
MatType Mat
So other classes can use TreeType::Mat.
size_t Descendant(const size_t index) const
Return the index (with reference to the dataset) of a particular descendant of this node...
StatisticType & Stat()
Return the statistic object for this node.
size_t MaxLeafSize() const
Return the max leaf size.
bool IsLeaf() const
Return whether or not this node is a leaf (true if it has no children).
StatisticType stat
Any extra data contained in the node.
BinarySpaceTree *& Left()
Modify the left child of this node.
A single-tree traverser for binary space trees; see single_tree_traverser.hpp for implementation...
size_t maxLeafSize
The max leaf size.
BoundType & Bound()
Return the bound object for this node.
double & ParentDistance()
Modify the distance from the center of this node to the center of the parent node.
size_t NumPoints() const
Return the number of points in this node (0 if not a leaf).
size_t Begin() const
Return the index of the beginning point of this subset.
size_t count
The number of points of the dataset contained in this node (and its children).
size_t & SplitDimension()
Modify the split dimension for this node.
size_t & Count()
Modify the number of points in this subset.
double MaxDistance(const BinarySpaceTree *other) const
Return the maximum distance to another node.
double MinimumBoundDistance() const
Return the minimum distance from the center of the node to any bound edge.
A binary space partitioning tree node is split into its left and right child.
Definition: mean_split.hpp:30
BinarySpaceTree * Right() const
Gets the right child of this node.
const MatType & Dataset() const
Get the dataset which the tree is built on.
static bool HasSelfChildren()
Returns false: this tree type does not have self children.
double ParentDistance() const
Return the distance from the center of this node to the center of the parent node.
BinarySpaceTree(MatType &data, const size_t maxLeafSize=20)
Construct this as the root node of a binary space tree using the given dataset.
BinarySpaceTree * Parent() const
Gets the parent of this node.
size_t GetSplitDimension() const
Returns the dimension this parent's children are split on.
double FurthestPointDistance() const
Return the furthest distance to a point held in this node.
const BoundType & Bound() const
Return the bound object for this node.
size_t End() const
Gets the index one beyond the last index in the subset.
If value == true, then VecType is some sort of Armadillo vector or subview.
Definition: arma_traits.hpp:37
void Centroid(arma::vec &centroid)
Get the centroid of the node and store it in the given vector.
BoundType::MetricType Metric() const
Get the metric which the tree uses.
Simple real-valued range.
Definition: range.hpp:23
Empty statistic if you are not interested in storing statistics in your tree.
Definition: statistic.hpp:26
MatType & Dataset()
Modify the dataset which the tree is built on. Be careful!