mlpack
2.0.1
|
The NeighborSearch class is a template class for performing distance-based neighbor searches. More...
Public Types | |
typedef TreeType< MetricType, NeighborSearchStat< SortPolicy >, MatType > | Tree |
Convenience typedef. More... | |
Public Member Functions | |
NeighborSearch (const MatType &referenceSet, const bool naive=false, const bool singleMode=false, const MetricType metric=MetricType()) | |
Initialize the NeighborSearch object, passing a reference dataset (this is the dataset which is searched). More... | |
NeighborSearch (MatType &&referenceSet, const bool naive=false, const bool singleMode=false, const MetricType metric=MetricType()) | |
Initialize the NeighborSearch object, taking ownership of the reference dataset (this is the dataset which is searched). More... | |
NeighborSearch (Tree *referenceTree, const bool singleMode=false, const MetricType metric=MetricType()) | |
Initialize the NeighborSearch object with the given pre-constructed reference tree (this is the tree built on the points that will be searched). More... | |
NeighborSearch (const bool naive=false, const bool singleMode=false, const MetricType metric=MetricType()) | |
Create a NeighborSearch object without any reference data. More... | |
~NeighborSearch () | |
Delete the NeighborSearch object. More... | |
size_t | BaseCases () const |
Return the total number of base case evaluations performed during the last search. More... | |
bool | Naive () const |
Access whether or not search is done in naive linear scan mode. More... | |
bool & | Naive () |
Modify whether or not search is done in naive linear scan mode. More... | |
const MatType & | ReferenceSet () const |
Access the reference dataset. More... | |
size_t | Scores () const |
Return the number of node combination scores during the last search. More... | |
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 matrices. More... | |
void | Search (Tree *queryTree, const size_t k, arma::Mat< size_t > &neighbors, arma::mat &distances) |
Given a pre-built query tree, search for the nearest neighbors of each point in the query tree, storing the output in the given matrices. More... | |
void | Search (const size_t k, arma::Mat< size_t > &neighbors, arma::mat &distances) |
Search for the nearest neighbors of every point in the reference set. More... | |
template<typename Archive > | |
void | Serialize (Archive &ar, const unsigned int) |
Serialize the NeighborSearch model. More... | |
bool | SingleMode () const |
Access whether or not search is done in single-tree mode. More... | |
bool & | SingleMode () |
Modify whether or not search is done in single-tree mode. More... | |
void | Train (const MatType &referenceSet) |
Set the reference set to a new reference set, and build a tree if necessary. More... | |
void | Train (MatType &&referenceSet) |
Set the reference set to a new reference set, taking ownership of the set, and build a tree if necessary. More... | |
void | Train (Tree *referenceTree) |
Set the reference tree to a new reference tree. More... | |
Private Attributes | |
size_t | baseCases |
The total number of base cases. More... | |
MetricType | metric |
Instantiation of metric. More... | |
bool | naive |
Indicates if O(n^2) naive search is being used. More... | |
std::vector< size_t > | oldFromNewReferences |
Permutations of reference points during tree building. More... | |
const MatType * | referenceSet |
Reference dataset. In some situations we may be the owner of this. More... | |
Tree * | referenceTree |
Pointer to the root of the reference tree. More... | |
size_t | scores |
The total number of scores (applicable for non-naive search). More... | |
bool | setOwner |
If true, we own the reference set. More... | |
bool | singleMode |
Indicates if single-tree search is being used (as opposed to dual-tree). More... | |
bool | treeNeedsReset |
If this is true, the reference tree bounds need to be reset on a call to Search() without a query set. More... | |
bool | treeOwner |
If true, this object created the trees and is responsible for them. More... | |
The NeighborSearch class is a template class for performing distance-based neighbor searches.
It takes a query dataset and a reference dataset (or just a reference dataset) and, for each point in the query dataset, finds the k neighbors in the reference dataset which have the 'best' distance according to a given sorting policy. A constructor is given which takes only a reference dataset, and if that constructor is used, the given reference dataset is also used as the query dataset.
The template parameters SortPolicy and Metric define the sort function used and the metric (distance function) used. More information on those classes can be found in the NearestNeighborSort class and the kernel::ExampleKernel class.
SortPolicy | The sort policy for distances; see NearestNeighborSort. |
MetricType | The metric to use for computation. |
MatType | The type of data matrix. |
TreeType | The tree type to use; must adhere to the TreeType API. |
TraversalType | The type of traversal to use (defaults to the tree's default traverser). |
Definition at line 71 of file neighbor_search.hpp.
typedef TreeType<MetricType, NeighborSearchStat<SortPolicy>, MatType> mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, MatType, TreeType, TraversalType >::Tree |
Convenience typedef.
Definition at line 75 of file neighbor_search.hpp.
mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, MatType, TreeType, TraversalType >::NeighborSearch | ( | const MatType & | referenceSet, |
const bool | naive = false , |
||
const bool | singleMode = false , |
||
const MetricType | metric = MetricType() |
||
) |
Initialize the NeighborSearch object, passing a reference dataset (this is the dataset which is searched).
Optionally, perform the computation in naive mode or single-tree mode. An initialized distance metric can be given, for cases where the metric has internal data (i.e. the distance::MahalanobisDistance class).
This method will copy the matrices to internal copies, which are rearranged during tree-building. You can avoid this extra copy by pre-constructing the trees and passing them using a different constructor, or by using the construct that takes an rvalue reference to the dataset.
referenceSet | Set of reference points. |
naive | If true, O(n^2) naive search will be used (as opposed to dual-tree search). This overrides singleMode (if it is set to true). |
singleMode | If true, single-tree search will be used (as opposed to dual-tree search). |
metric | An optional instance of the MetricType class. |
mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, MatType, TreeType, TraversalType >::NeighborSearch | ( | MatType && | referenceSet, |
const bool | naive = false , |
||
const bool | singleMode = false , |
||
const MetricType | metric = MetricType() |
||
) |
Initialize the NeighborSearch object, taking ownership of the reference dataset (this is the dataset which is searched).
Optionally, perform the computation in naive mode or single-tree mode. An initialized distance metric can be given, for cases where the metric has internal data (i.e. the distance::MahalanobisDistance class).
This method will not copy the data matrix, but will take ownership of it, and depending on the type of tree used, may rearrange the points. If you would rather a copy be made, consider using the constructor that takes a const reference to the data instead.
referenceSet | Set of reference points. |
naive | If true, O(n^2) naive search will be used (as opposed to dual-tree search). This overrides singleMode (if it is set to true). |
singleMode | If true, single-tree search will be used (as opposed to dual-tree search). |
metric | An optional instance of the MetricType class. |
mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, MatType, TreeType, TraversalType >::NeighborSearch | ( | Tree * | referenceTree, |
const bool | singleMode = false , |
||
const MetricType | metric = MetricType() |
||
) |
Initialize the NeighborSearch object with the given pre-constructed reference tree (this is the tree built on the points that will be searched).
Optionally, choose to use single-tree mode. Naive mode is not available as an option for this constructor. Additionally, an instantiated distance metric can be given, for cases where the distance metric holds data.
There is no copying of the data matrices in this constructor (because tree-building is not necessary), so this is the constructor to use when copies absolutely must be avoided.
referenceTree | Pre-built tree for reference points. |
referenceSet | Set of reference points corresponding to referenceTree. |
singleMode | Whether single-tree computation should be used (as opposed to dual-tree computation). |
metric | Instantiated distance metric. |
mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, MatType, TreeType, TraversalType >::NeighborSearch | ( | const bool | naive = false , |
const bool | singleMode = false , |
||
const MetricType | metric = MetricType() |
||
) |
Create a NeighborSearch object without any reference data.
If Search() is called before a reference set is set with Train(), an exception will be thrown.
naive | Whether to use naive search. |
singleMode | Whether single-tree computation should be used (as opposed to dual-tree computation). |
metric | Instantiated metric. |
mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, MatType, TreeType, TraversalType >::~NeighborSearch | ( | ) |
Delete the NeighborSearch object.
The tree is the only member we are responsible for deleting. The others will take care of themselves.
|
inline |
Return the total number of base case evaluations performed during the last search.
Definition at line 260 of file neighbor_search.hpp.
|
inline |
Access whether or not search is done in naive linear scan mode.
Definition at line 266 of file neighbor_search.hpp.
|
inline |
Modify whether or not search is done in naive linear scan mode.
Definition at line 268 of file neighbor_search.hpp.
|
inline |
Access the reference dataset.
Definition at line 276 of file neighbor_search.hpp.
|
inline |
Return the number of node combination scores during the last search.
Definition at line 263 of file neighbor_search.hpp.
void mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, MatType, TreeType, TraversalType >::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 matrices.
The matrices will be set to the size of n columns by k rows, where n is the number of points in the query dataset and k is the number of neighbors being searched for.
If querySet contains only a few query points, the extra cost of building a tree on the points for dual-tree search may not be warranted, and it may be worthwhile to set singleMode = false (either in the constructor or with SingleMode()).
querySet | Set of query points (can be just one point). |
k | Number of neighbors to search for. |
neighbors | Matrix storing lists of neighbors for each query point. |
distances | Matrix storing distances of neighbors for each query point. |
void mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, MatType, TreeType, TraversalType >::Search | ( | Tree * | queryTree, |
const size_t | k, | ||
arma::Mat< size_t > & | neighbors, | ||
arma::mat & | distances | ||
) |
Given a pre-built query tree, search for the nearest neighbors of each point in the query tree, storing the output in the given matrices.
The matrices will be set to the size of n columns by k rows, where n is the number of points in the query dataset and k is the number of neighbors being searched for.
queryTree | Tree built on query points. |
k | Number of neighbors to search for. |
neighbors | Matrix storing lists of neighbors for each query point. |
distances | Matrix storing distances of neighbors for each query point. |
void mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, MatType, TreeType, TraversalType >::Search | ( | const size_t | k, |
arma::Mat< size_t > & | neighbors, | ||
arma::mat & | distances | ||
) |
Search for the nearest neighbors of every point in the reference set.
This is basically equivalent to calling any other overload of Search() with the reference set as the query set; so, this lets you do all-k-nearest-neighbors search. The results are stored in the given matrices. The matrices will be set to the size of n columns by k rows, where n is the number of points in the query dataset and k is the number of neighbors being searched for.
k | Number of neighbors to search for. |
neighbors | Matrix storing lists of neighbors for each query point. |
distances | Matrix storing distances of neighbors for each query point. |
void mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, MatType, TreeType, TraversalType >::Serialize | ( | Archive & | ar, |
const unsigned | int | ||
) |
Serialize the NeighborSearch model.
|
inline |
Access whether or not search is done in single-tree mode.
Definition at line 271 of file neighbor_search.hpp.
|
inline |
Modify whether or not search is done in single-tree mode.
Definition at line 273 of file neighbor_search.hpp.
void mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, MatType, TreeType, TraversalType >::Train | ( | const MatType & | referenceSet | ) |
Set the reference set to a new reference set, and build a tree if necessary.
This method is called 'Train()' in order to match the rest of the mlpack abstractions, even though calling this "training" is maybe a bit of a stretch.
referenceSet | New set of reference data. |
void mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, MatType, TreeType, TraversalType >::Train | ( | MatType && | referenceSet | ) |
Set the reference set to a new reference set, taking ownership of the set, and build a tree if necessary.
This method is called 'Train()' in order to match the rest of the mlpack abstractions, even though calling this "training" is maybe a bit of a stretch.
referenceSet | New set of reference data. |
void mlpack::neighbor::NeighborSearch< SortPolicy, MetricType, MatType, TreeType, TraversalType >::Train | ( | Tree * | referenceTree | ) |
Set the reference tree to a new reference tree.
|
private |
The total number of base cases.
Definition at line 304 of file neighbor_search.hpp.
Referenced by mlpack::neighbor::NeighborSearch< tree::RStarTree >::BaseCases().
|
private |
Instantiation of metric.
Definition at line 301 of file neighbor_search.hpp.
|
private |
Indicates if O(n^2) naive search is being used.
Definition at line 296 of file neighbor_search.hpp.
Referenced by mlpack::neighbor::NeighborSearch< tree::RStarTree >::Naive().
|
private |
Permutations of reference points during tree building.
Definition at line 284 of file neighbor_search.hpp.
|
private |
Reference dataset. In some situations we may be the owner of this.
Definition at line 288 of file neighbor_search.hpp.
Referenced by mlpack::neighbor::NeighborSearch< tree::RStarTree >::ReferenceSet().
|
private |
Pointer to the root of the reference tree.
Definition at line 286 of file neighbor_search.hpp.
|
private |
The total number of scores (applicable for non-naive search).
Definition at line 306 of file neighbor_search.hpp.
Referenced by mlpack::neighbor::NeighborSearch< tree::RStarTree >::Scores().
|
private |
If true, we own the reference set.
Definition at line 293 of file neighbor_search.hpp.
|
private |
Indicates if single-tree search is being used (as opposed to dual-tree).
Definition at line 298 of file neighbor_search.hpp.
Referenced by mlpack::neighbor::NeighborSearch< tree::RStarTree >::SingleMode().
|
private |
If this is true, the reference tree bounds need to be reset on a call to Search() without a query set.
Definition at line 310 of file neighbor_search.hpp.
|
private |
If true, this object created the trees and is responsible for them.
Definition at line 291 of file neighbor_search.hpp.