mlpack  2.2.5
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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
size_t Scores() const
Return the number of node combination scores during the last search.
bool & Greedy()
Modify whether or not search is done in greedy mode.
The core includes that mlpack expects; standard C++ includes and Armadillo.
bool Naive() const
Access whether or not search is done in naive linear scan mode.
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.
const MatType & ReferenceSet() const
Access the reference dataset.
double Epsilon() const
Access the relative error to be considered in approximate search.
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.
const Tree & ReferenceTree() const
Access the reference tree.
bool Greedy() const
Access whether or not search is done in greedy 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() const
Access whether or not search is done in single-tree mode.
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.