MLPACK  1.0.7
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 
330  { return furthestDescendantDistance; }
333 
335  void Centroid(arma::vec& centroid) const { centroid = dataset.col(point); }
336 
338  MetricType& Metric() const { return *metric; }
339 
340  private:
342  const arma::mat& dataset;
343 
345  size_t point;
346 
348  std::vector<CoverTree*> children;
349 
351  int scale;
352 
354  double base;
355 
357  StatisticType stat;
358 
361 
364 
367 
370 
373 
375  MetricType* metric;
376 
380  void CreateChildren(arma::Col<size_t>& indices,
381  arma::vec& distances,
382  size_t nearSetSize,
383  size_t& farSetSize,
384  size_t& usedSetSize);
385 
397  void ComputeDistances(const size_t pointIndex,
398  const arma::Col<size_t>& indices,
399  arma::vec& distances,
400  const size_t pointSetSize);
415  size_t SplitNearFar(arma::Col<size_t>& indices,
416  arma::vec& distances,
417  const double bound,
418  const size_t pointSetSize);
419 
439  size_t SortPointSet(arma::Col<size_t>& indices,
440  arma::vec& distances,
441  const size_t childFarSetSize,
442  const size_t childUsedSetSize,
443  const size_t farSetSize);
444 
445  void MoveToUsedSet(arma::Col<size_t>& indices,
446  arma::vec& distances,
447  size_t& nearSetSize,
448  size_t& farSetSize,
449  size_t& usedSetSize,
450  arma::Col<size_t>& childIndices,
451  const size_t childFarSetSize,
452  const size_t childUsedSetSize);
453  size_t PruneFarSet(arma::Col<size_t>& indices,
454  arma::vec& distances,
455  const double bound,
456  const size_t nearSetSize,
457  const size_t pointSetSize);
458 
463  void RemoveNewImplicitNodes();
464 
465  public:
469  std::string ToString() const;
470 
471  size_t DistanceComps() const { return distanceComps; }
472  size_t& DistanceComps() { return distanceComps; }
473 
474  private:
476 };
477 
478 }; // namespace tree
479 }; // namespace mlpack
480 
481 // Include implementation.
482 #include "cover_tree_impl.hpp"
483 
484 #endif