MLPACK  1.0.10
cover_tree.hpp
Go to the documentation of this file.
1 
22 #ifndef __MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP
23 #define __MLPACK_CORE_TREE_COVER_TREE_COVER_TREE_HPP
24 
25 #include <mlpack/core.hpp>
27 #include "first_point_is_root.hpp"
28 #include "../statistic.hpp"
29 
30 namespace mlpack {
31 namespace tree {
32 
100 template<typename MetricType = metric::LMetric<2, true>,
101  typename RootPointPolicy = FirstPointIsRoot,
102  typename StatisticType = EmptyStatistic>
104 {
105  public:
106  typedef arma::mat Mat;
107 
118  CoverTree(const arma::mat& dataset,
119  const double base = 2.0,
120  MetricType* metric = NULL);
121 
131  CoverTree(const arma::mat& dataset,
132  MetricType& metric,
133  const double base = 2.0);
134 
166  CoverTree(const arma::mat& dataset,
167  const double base,
168  const size_t pointIndex,
169  const int scale,
170  CoverTree* parent,
171  const double parentDistance,
172  arma::Col<size_t>& indices,
173  arma::vec& distances,
174  size_t nearSetSize,
175  size_t& farSetSize,
176  size_t& usedSetSize,
177  MetricType& metric = NULL);
178 
195  CoverTree(const arma::mat& dataset,
196  const double base,
197  const size_t pointIndex,
198  const int scale,
199  CoverTree* parent,
200  const double parentDistance,
201  const double furthestDescendantDistance,
202  MetricType* metric = NULL);
203 
210  CoverTree(const CoverTree& other);
211 
215  ~CoverTree();
216 
219  template<typename RuleType>
221 
223  template<typename RuleType>
225 
227  const arma::mat& Dataset() const { return dataset; }
228 
230  size_t Point() const { return point; }
232  size_t Point(const size_t) const { return point; }
233 
234  bool IsLeaf() const { return (children.size() == 0); }
235  size_t NumPoints() const { return 1; }
236 
238  const CoverTree& Child(const size_t index) const { return *children[index]; }
240  CoverTree& Child(const size_t index) { return *children[index]; }
241 
243  size_t NumChildren() const { return children.size(); }
244 
246  const std::vector<CoverTree*>& Children() const { return children; }
248  std::vector<CoverTree*>& Children() { return children; }
249 
251  size_t NumDescendants() const;
252 
254  size_t Descendant(const size_t index) const;
255 
257  int Scale() const { return scale; }
259  int& Scale() { return scale; }
260 
262  double Base() const { return base; }
264  double& Base() { return base; }
265 
267  const StatisticType& Stat() const { return stat; }
269  StatisticType& Stat() { return stat; }
270 
272  double MinDistance(const CoverTree* other) const;
273 
276  double MinDistance(const CoverTree* other, const double distance) const;
277 
279  double MinDistance(const arma::vec& other) const;
280 
283  double MinDistance(const arma::vec& other, const double distance) const;
284 
286  double MaxDistance(const CoverTree* other) const;
287 
290  double MaxDistance(const CoverTree* other, const double distance) const;
291 
293  double MaxDistance(const arma::vec& other) const;
294 
297  double MaxDistance(const arma::vec& other, const double distance) const;
298 
300  math::Range RangeDistance(const CoverTree* other) const;
301 
304  math::Range RangeDistance(const CoverTree* other, const double distance)
305  const;
306 
308  math::Range RangeDistance(const arma::vec& other) const;
309 
312  math::Range RangeDistance(const arma::vec& other, const double distance)
313  const;
314 
316  static bool HasSelfChildren() { return true; }
317 
319  CoverTree* Parent() const { return parent; }
321  CoverTree*& Parent() { return parent; }
322 
324  double ParentDistance() const { return parentDistance; }
326  double& ParentDistance() { return parentDistance; }
327 
329  double FurthestPointDistance() const { return 0.0; }
330 
333  { return furthestDescendantDistance; }
337 
341 
343  void Centroid(arma::vec& centroid) const { centroid = dataset.col(point); }
344 
346  MetricType& Metric() const { return *metric; }
347 
348  private:
350  const arma::mat& dataset;
351 
353  size_t point;
354 
356  std::vector<CoverTree*> children;
357 
359  int scale;
360 
362  double base;
363 
365  StatisticType stat;
366 
369 
372 
375 
378 
381 
383  MetricType* metric;
384 
388  void CreateChildren(arma::Col<size_t>& indices,
389  arma::vec& distances,
390  size_t nearSetSize,
391  size_t& farSetSize,
392  size_t& usedSetSize);
393 
405  void ComputeDistances(const size_t pointIndex,
406  const arma::Col<size_t>& indices,
407  arma::vec& distances,
408  const size_t pointSetSize);
423  size_t SplitNearFar(arma::Col<size_t>& indices,
424  arma::vec& distances,
425  const double bound,
426  const size_t pointSetSize);
427 
447  size_t SortPointSet(arma::Col<size_t>& indices,
448  arma::vec& distances,
449  const size_t childFarSetSize,
450  const size_t childUsedSetSize,
451  const size_t farSetSize);
452 
453  void MoveToUsedSet(arma::Col<size_t>& indices,
454  arma::vec& distances,
455  size_t& nearSetSize,
456  size_t& farSetSize,
457  size_t& usedSetSize,
458  arma::Col<size_t>& childIndices,
459  const size_t childFarSetSize,
460  const size_t childUsedSetSize);
461  size_t PruneFarSet(arma::Col<size_t>& indices,
462  arma::vec& distances,
463  const double bound,
464  const size_t nearSetSize,
465  const size_t pointSetSize);
466 
471  void RemoveNewImplicitNodes();
472 
473  public:
477  std::string ToString() const;
478 
479  size_t DistanceComps() const { return distanceComps; }
480  size_t& DistanceComps() { return distanceComps; }
481 
482  private:
484 };
485 
486 }; // namespace tree
487 }; // namespace mlpack
488 
489 // Include implementation.
490 #include "cover_tree_impl.hpp"
491 
492 #endif