mlpack  2.2.5
neighbor_search.hpp
Go to the documentation of this file.
1 
13 #ifndef MLPACK_METHODS_NEIGHBOR_SEARCH_NEIGHBOR_SEARCH_HPP
14 #define MLPACK_METHODS_NEIGHBOR_SEARCH_NEIGHBOR_SEARCH_HPP
15 
16 #include <mlpack/prereqs.hpp>
17 #include <vector>
18 #include <string>
19 
23 
24 #include "neighbor_search_stat.hpp"
27 
28 namespace mlpack {
29 namespace neighbor {
32 
33 // Forward declaration.
34 template<typename SortPolicy>
36 
39 {
44 };
45 
69 template<typename SortPolicy = NearestNeighborSort,
70  typename MetricType = mlpack::metric::EuclideanDistance,
71  typename MatType = arma::mat,
72  template<typename TreeMetricType,
73  typename TreeStatType,
74  typename TreeMatType> class TreeType = tree::KDTree,
75  template<typename RuleType> class DualTreeTraversalType =
76  TreeType<MetricType,
77  NeighborSearchStat<SortPolicy>,
78  MatType>::template DualTreeTraverser,
79  template<typename RuleType> class SingleTreeTraversalType =
80  TreeType<MetricType,
81  NeighborSearchStat<SortPolicy>,
82  MatType>::template SingleTreeTraverser>
84 {
85  public:
87  typedef TreeType<MetricType, NeighborSearchStat<SortPolicy>, MatType> Tree;
88 
106  NeighborSearch(const MatType& referenceSet,
107  const NeighborSearchMode mode = DUAL_TREE_MODE,
108  const double epsilon = 0,
109  const MetricType metric = MetricType());
110 
128  NeighborSearch(MatType&& referenceSet,
129  const NeighborSearchMode mode = DUAL_TREE_MODE,
130  const double epsilon = 0,
131  const MetricType metric = MetricType());
132 
157  const Tree& referenceTree,
158  const NeighborSearchMode mode = DUAL_TREE_MODE,
159  const double epsilon = 0,
160  const MetricType metric = MetricType());
161 
187  Tree&& referenceTree,
188  const NeighborSearchMode mode = DUAL_TREE_MODE,
189  const double epsilon = 0,
190  const MetricType metric = MetricType());
191 
202  const double epsilon = 0,
203  const MetricType metric = MetricType());
204 
227  mlpack_deprecated NeighborSearch(const MatType& referenceSet,
228  const bool naive,
229  const bool singleMode = false,
230  const double epsilon = 0,
231  const MetricType metric = MetricType());
232 
255  mlpack_deprecated NeighborSearch(MatType&& referenceSet,
256  const bool naive,
257  const bool singleMode = false,
258  const double epsilon = 0,
259  const MetricType metric = MetricType());
260 
289  mlpack_deprecated NeighborSearch(Tree* referenceTree,
290  const bool singleMode,
291  const double epsilon = 0,
292  const MetricType metric = MetricType());
293 
307  mlpack_deprecated NeighborSearch(const bool naive,
308  const bool singleMode = false,
309  const double epsilon = 0,
310  const MetricType metric = MetricType());
311 
316  NeighborSearch(const NeighborSearch& other);
317 
322 
327  ~NeighborSearch();
328 
337  void Train(const MatType& referenceSet);
338 
347  void Train(MatType&& referenceSet);
348 
357  mlpack_deprecated void Train(Tree* referenceTree);
358 
367  void Train(const Tree& referenceTree);
368 
376  void Train(Tree&& referenceTree);
377 
395  void Search(const MatType& querySet,
396  const size_t k,
397  arma::Mat<size_t>& neighbors,
398  arma::mat& distances);
399 
423  mlpack_deprecated void Search(Tree* queryTree,
424  const size_t k,
425  arma::Mat<size_t>& neighbors,
426  arma::mat& distances,
427  bool sameSet = false);
428 
449  void Search(Tree& queryTree,
450  const size_t k,
451  arma::Mat<size_t>& neighbors,
452  arma::mat& distances,
453  bool sameSet = false);
454 
469  void Search(const size_t k,
470  arma::Mat<size_t>& neighbors,
471  arma::mat& distances);
472 
488  static double EffectiveError(arma::mat& foundDistances,
489  arma::mat& realDistances);
490 
502  static double Recall(arma::Mat<size_t>& foundNeighbors,
503  arma::Mat<size_t>& realNeighbors);
504 
507  size_t BaseCases() const { return baseCases; }
508 
510  size_t Scores() const { return scores; }
511 
515  bool Naive() const { return naive; }
519  bool& Naive() { return naive; }
520 
524  bool SingleMode() const { return singleMode; }
528  bool& SingleMode() { return singleMode; }
529 
533  bool Greedy() const { return greedy; }
537  bool& Greedy() { return greedy; }
538 
540  double Epsilon() const { return epsilon; }
542  double& Epsilon() { return epsilon; }
543 
545  const MatType& ReferenceSet() const { return *referenceSet; }
546 
548  const Tree& ReferenceTree() const { return *referenceTree; }
550  Tree& ReferenceTree() { return *referenceTree; }
551 
553  template<typename Archive>
554  void Serialize(Archive& ar, const unsigned int /* version */);
555 
556  private:
558  std::vector<size_t> oldFromNewReferences;
560  Tree* referenceTree;
562  const MatType* referenceSet;
563 
565  bool treeOwner;
567  bool setOwner;
568 
570  NeighborSearchMode searchMode;
572  bool naive;
574  bool singleMode;
576  bool greedy;
578  double epsilon;
579 
581  MetricType metric;
582 
584  size_t baseCases;
586  size_t scores;
587 
590  bool treeNeedsReset;
591 
595  void UpdateSearchMode();
596 
600  void UpdateSearchModeFlags();
601 
603  template<typename SortPol>
604  friend class TrainVisitor;
605 }; // class NeighborSearch
606 
607 } // namespace neighbor
608 } // namespace mlpack
609 
610 // Include implementation.
611 #include "neighbor_search_impl.hpp"
612 
613 // Include convenience typedefs.
614 #include "typedef.hpp"
615 
616 #endif
const MatType & ReferenceSet() const
Access the reference dataset.
double Epsilon() const
Access the relative error to be considered in approximate search.
size_t Scores() const
Return the number of node combination scores during the last search.
const Tree & ReferenceTree() const
Access the reference tree.
bool & Greedy()
Modify whether or not search is done in greedy mode.
bool Greedy() const
Access whether or not search is done in greedy mode.
Linear algebra utility functions, generally performed on matrices or vectors.
Definition: binarize.hpp:18
bool SingleMode() const
Access whether or not search is done in single-tree mode.
The core includes that mlpack expects; standard C++ includes and Armadillo.
The NeighborSearch class is a template class for performing distance-based neighbor searches...
void Train(const MatType &referenceSet)
Set the reference set to a new reference set, and build a tree if necessary.
#define mlpack_deprecated
Definition: deprecated.hpp:22
static double EffectiveError(arma::mat &foundDistances, arma::mat &realDistances)
Calculate the average relative error (effective error) between the distances calculated and the true ...
double & Epsilon()
Modify the relative error to be considered in approximate search.
Tree & ReferenceTree()
Modify the reference tree.
static double Recall(arma::Mat< size_t > &foundNeighbors, arma::Mat< size_t > &realNeighbors)
Calculate the recall (% of neighbors found) given the list of found neighbors and the true set of nei...
TreeType< MetricType, NeighborSearchStat< SortPolicy >, MatType > Tree
Convenience typedef.
void Serialize(Archive &ar, const unsigned int)
Serialize the NeighborSearch model.
TrainVisitor sets the reference set to a new reference set on the given NSType.
bool & Naive()
Modify whether or not search is done in naive linear scan mode.
NeighborSearch(const MatType &referenceSet, const NeighborSearchMode mode=DUAL_TREE_MODE, const double epsilon=0, const MetricType metric=MetricType())
Initialize the NeighborSearch object, passing a reference dataset (this is the dataset which is searc...
void Search(const MatType &querySet, const size_t k, arma::Mat< size_t > &neighbors, arma::mat &distances)
For each point in the query set, compute the nearest neighbors and store the output in the given matr...
size_t BaseCases() const
Return the total number of base case evaluations performed during the last search.
bool Naive() const
Access whether or not search is done in naive linear scan mode.
BinarySpaceTree< MetricType, StatisticType, MatType, bound::HRectBound, MidpointSplit > KDTree
The standard midpoint-split kd-tree.
Definition: typedef.hpp:63
LMetric< 2, true > EuclideanDistance
The Euclidean (L2) distance.
Definition: lmetric.hpp:112
bool & SingleMode()
Modify whether or not search is done in single-tree mode.
NeighborSearchMode
NeighborSearchMode represents the different neighbor search modes available.
~NeighborSearch()
Delete the NeighborSearch object.