MLPACK  1.0.8
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 
339  void Centroid(arma::vec& centroid) const { centroid = dataset.col(point); }
340 
342  MetricType& Metric() const { return *metric; }
343 
344  private:
346  const arma::mat& dataset;
347 
349  size_t point;
350 
352  std::vector<CoverTree*> children;
353 
355  int scale;
356 
358  double base;
359 
361  StatisticType stat;
362 
365 
368 
371 
374 
377 
379  MetricType* metric;
380 
384  void CreateChildren(arma::Col<size_t>& indices,
385  arma::vec& distances,
386  size_t nearSetSize,
387  size_t& farSetSize,
388  size_t& usedSetSize);
389 
401  void ComputeDistances(const size_t pointIndex,
402  const arma::Col<size_t>& indices,
403  arma::vec& distances,
404  const size_t pointSetSize);
419  size_t SplitNearFar(arma::Col<size_t>& indices,
420  arma::vec& distances,
421  const double bound,
422  const size_t pointSetSize);
423 
443  size_t SortPointSet(arma::Col<size_t>& indices,
444  arma::vec& distances,
445  const size_t childFarSetSize,
446  const size_t childUsedSetSize,
447  const size_t farSetSize);
448 
449  void MoveToUsedSet(arma::Col<size_t>& indices,
450  arma::vec& distances,
451  size_t& nearSetSize,
452  size_t& farSetSize,
453  size_t& usedSetSize,
454  arma::Col<size_t>& childIndices,
455  const size_t childFarSetSize,
456  const size_t childUsedSetSize);
457  size_t PruneFarSet(arma::Col<size_t>& indices,
458  arma::vec& distances,
459  const double bound,
460  const size_t nearSetSize,
461  const size_t pointSetSize);
462 
467  void RemoveNewImplicitNodes();
468 
469  public:
473  std::string ToString() const;
474 
475  size_t DistanceComps() const { return distanceComps; }
476  size_t& DistanceComps() { return distanceComps; }
477 
478  private:
480 };
481 
482 }; // namespace tree
483 }; // namespace mlpack
484 
485 // Include implementation.
486 #include "cover_tree_impl.hpp"
487 
488 #endif