MLPACK  1.0.10
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 #include "mean_split.hpp"
26 
27 #include "../statistic.hpp"
28 
29 namespace mlpack {
30 namespace tree {
31 
55 template<typename BoundType,
56  typename StatisticType = EmptyStatistic,
57  typename MatType = arma::mat,
58  typename SplitType = MeanSplit<BoundType, MatType> >
60 {
61  private:
70  size_t begin;
73  size_t count;
75  size_t maxLeafSize;
77  BoundType bound;
79  StatisticType stat;
90  MatType& dataset;
91 
92  public:
94  typedef MatType Mat;
95 
98  template<typename RuleType>
100 
102  template<typename RuleType>
104 
112  BinarySpaceTree(MatType& data, const size_t maxLeafSize = 20);
113 
124  BinarySpaceTree(MatType& data,
125  std::vector<size_t>& oldFromNew,
126  const size_t maxLeafSize = 20);
127 
141  BinarySpaceTree(MatType& data,
142  std::vector<size_t>& oldFromNew,
143  std::vector<size_t>& newFromOld,
144  const size_t maxLeafSize = 20);
145 
157  BinarySpaceTree(MatType& data,
158  const size_t begin,
159  const size_t count,
160  BinarySpaceTree* parent = NULL,
161  const size_t maxLeafSize = 20);
162 
181  BinarySpaceTree(MatType& data,
182  const size_t begin,
183  const size_t count,
184  std::vector<size_t>& oldFromNew,
185  BinarySpaceTree* parent = NULL,
186  const size_t maxLeafSize = 20);
187 
209  BinarySpaceTree(MatType& data,
210  const size_t begin,
211  const size_t count,
212  std::vector<size_t>& oldFromNew,
213  std::vector<size_t>& newFromOld,
214  BinarySpaceTree* parent = NULL,
215  const size_t maxLeafSize = 20);
216 
223  BinarySpaceTree(const BinarySpaceTree& other);
224 
231 
243  const BinarySpaceTree* FindByBeginCount(size_t begin,
244  size_t count) const;
245 
257  BinarySpaceTree* FindByBeginCount(size_t begin, size_t count);
258 
260  const BoundType& Bound() const { return bound; }
262  BoundType& Bound() { return bound; }
263 
265  const StatisticType& Stat() const { return stat; }
267  StatisticType& Stat() { return stat; }
268 
270  bool IsLeaf() const;
271 
273  size_t MaxLeafSize() const { return maxLeafSize; }
275  size_t& MaxLeafSize() { return maxLeafSize; }
276 
278  size_t ExtendTree(const size_t level);
279 
281  BinarySpaceTree* Left() const { return left; }
283  BinarySpaceTree*& Left() { return left; }
284 
286  BinarySpaceTree* Right() const { return right; }
288  BinarySpaceTree*& Right() { return right; }
289 
291  BinarySpaceTree* Parent() const { return parent; }
293  BinarySpaceTree*& Parent() { return parent; }
294 
296  size_t SplitDimension() const { return splitDimension; }
298  size_t& SplitDimension() { return splitDimension; }
299 
301  const MatType& Dataset() const { return dataset; }
303  MatType& Dataset() { return dataset; }
304 
306  typename BoundType::MetricType Metric() const { return bound.Metric(); }
307 
309  void Centroid(arma::vec& centroid) { bound.Centroid(centroid); }
310 
312  size_t NumChildren() const;
313 
318  double FurthestPointDistance() const;
319 
327  double FurthestDescendantDistance() const;
328 
330  double MinimumBoundDistance() const;
331 
334  double ParentDistance() const { return parentDistance; }
337  double& ParentDistance() { return parentDistance; }
338 
345  BinarySpaceTree& Child(const size_t child) const;
346 
348  size_t NumPoints() const;
349 
355  size_t NumDescendants() const;
356 
364  size_t Descendant(const size_t index) const;
365 
374  size_t Point(const size_t index) const;
375 
377  double MinDistance(const BinarySpaceTree* other) const
378  {
379  return bound.MinDistance(other->Bound());
380  }
381 
383  double MaxDistance(const BinarySpaceTree* other) const
384  {
385  return bound.MaxDistance(other->Bound());
386  }
387 
390  {
391  return bound.RangeDistance(other->Bound());
392  }
393 
395  template<typename VecType>
396  double MinDistance(const VecType& point,
397  typename boost::enable_if<IsVector<VecType> >::type* = 0)
398  const
399  {
400  return bound.MinDistance(point);
401  }
402 
404  template<typename VecType>
405  double MaxDistance(const VecType& point,
406  typename boost::enable_if<IsVector<VecType> >::type* = 0)
407  const
408  {
409  return bound.MaxDistance(point);
410  }
411 
413  template<typename VecType>
415  RangeDistance(const VecType& point,
416  typename boost::enable_if<IsVector<VecType> >::type* = 0) const
417  {
418  return bound.RangeDistance(point);
419  }
420 
424  size_t GetSplitDimension() const;
425 
429  size_t TreeSize() const;
430 
435  size_t TreeDepth() const;
436 
438  size_t Begin() const { return begin; }
440  size_t& Begin() { return begin; }
441 
445  size_t End() const;
446 
448  size_t Count() const { return count; }
450  size_t& Count() { return count; }
451 
453  static bool HasSelfChildren() { return false; }
454 
455  private:
460  BinarySpaceTree(const size_t begin,
461  const size_t count,
462  BoundType bound,
463  StatisticType stat,
464  const int maxLeafSize = 20) :
465  left(NULL),
466  right(NULL),
467  begin(begin),
468  count(count),
469  bound(bound),
470  stat(stat),
472 
474  {
476  }
477 
483  void SplitNode(MatType& data);
484 
492  void SplitNode(MatType& data, std::vector<size_t>& oldFromNew);
493 
494  public:
498  std::string ToString() const;
499 
500 };
501 
502 }; // namespace tree
503 }; // namespace mlpack
504 
505 // Include implementation.
506 #include "binary_space_tree_impl.hpp"
507 
508 #endif