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 // Neighbor-search routines. These include all-nearest-neighbors and
30 // all-furthest-neighbors searches.
31 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,
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 
105  NeighborSearch(MatType referenceSet,
106  const NeighborSearchMode mode = DUAL_TREE_MODE,
107  const double epsilon = 0,
108  const MetricType metric = MetricType());
109 
134  NeighborSearch(Tree referenceTree,
135  const NeighborSearchMode mode = DUAL_TREE_MODE,
136  const double epsilon = 0,
137  const MetricType metric = MetricType());
138 
149  const double epsilon = 0,
150  const MetricType metric = MetricType());
151 
158  NeighborSearch(const NeighborSearch& other);
159 
167 
173  NeighborSearch& operator=(const NeighborSearch& other);
174 
181 
186  ~NeighborSearch();
187 
197  void Train(MatType referenceSet);
198 
208  void Train(Tree referenceTree);
209 
227  void Search(const MatType& querySet,
228  const size_t k,
229  arma::Mat<size_t>& neighbors,
230  arma::mat& distances);
231 
252  void Search(Tree& queryTree,
253  const size_t k,
254  arma::Mat<size_t>& neighbors,
255  arma::mat& distances,
256  bool sameSet = false);
257 
272  void Search(const size_t k,
273  arma::Mat<size_t>& neighbors,
274  arma::mat& distances);
275 
291  static double EffectiveError(arma::mat& foundDistances,
292  arma::mat& realDistances);
293 
305  static double Recall(arma::Mat<size_t>& foundNeighbors,
306  arma::Mat<size_t>& realNeighbors);
307 
310  size_t BaseCases() const { return baseCases; }
311 
313  size_t Scores() const { return scores; }
314 
316  NeighborSearchMode SearchMode() const { return searchMode; }
318  NeighborSearchMode& SearchMode() { return searchMode; }
319 
321  double Epsilon() const { return epsilon; }
323  double& Epsilon() { return epsilon; }
324 
326  const MatType& ReferenceSet() const { return *referenceSet; }
327 
329  const Tree& ReferenceTree() const { return *referenceTree; }
331  Tree& ReferenceTree() { return *referenceTree; }
332 
334  template<typename Archive>
335  void serialize(Archive& ar, const unsigned int /* version */);
336 
337  private:
339  std::vector<size_t> oldFromNewReferences;
341  Tree* referenceTree;
343  const MatType* referenceSet;
344 
346  NeighborSearchMode searchMode;
348  double epsilon;
349 
351  MetricType metric;
352 
354  size_t baseCases;
356  size_t scores;
357 
360  bool treeNeedsReset;
361 
363  template<typename SortPol>
364  friend class TrainVisitor;
365 }; // class NeighborSearch
366 
367 } // namespace neighbor
368 } // namespace mlpack
369 
370 // Include implementation.
371 #include "neighbor_search_impl.hpp"
372 
373 // Include convenience typedefs.
374 #include "typedef.hpp"
375 
376 #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.
.hpp
Definition: add_to_po.hpp:21
Extra data for each node in the tree.
The core includes that mlpack expects; standard C++ includes and Armadillo.
NeighborSearch(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...
The NeighborSearch class is a template class for performing distance-based neighbor searches...
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...
NeighborSearchMode & SearchMode()
Modify the search mode.
NeighborSearchMode SearchMode() const
Access the search mode.
NeighborSearch & operator=(const NeighborSearch &other)
Copy the given NeighborSearch object.
TreeType< MetricType, NeighborSearchStat< SortPolicy >, MatType > Tree
Convenience typedef.
TrainVisitor sets the reference set to a new reference set on the given NSType.
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.
void Train(MatType referenceSet)
Set the reference set to a new reference set, and build a tree if necessary.
void serialize(Archive &ar, const unsigned int)
Serialize the NeighborSearch model.
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
NeighborSearchMode
NeighborSearchMode represents the different neighbor search modes available.
~NeighborSearch()
Delete the NeighborSearch object.