[mlpack-git] master, mlpack-1.0.x: change a comment to be more accurate. Add on --r_tree option to the knn_all program. Doesn't do anything yet. (deb9fc7)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Thu Mar 5 21:48:37 EST 2015
Repository : https://github.com/mlpack/mlpack
On branches: master,mlpack-1.0.x
Link : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40
>---------------------------------------------------------------
commit deb9fc7948be7443ab405eabfd003a717cf7d785
Author: andrewmw94 <andrewmw94 at gmail.com>
Date: Fri Jun 6 15:45:32 2014 +0000
change a comment to be more accurate. Add on --r_tree option to the knn_all program. Doesn't do anything yet.
>---------------------------------------------------------------
deb9fc7948be7443ab405eabfd003a717cf7d785
src/mlpack/core/tree/CMakeLists.txt | 2 +
src/mlpack/methods/neighbor_search/allknn_main.cpp | 143 ++++++++++++---------
2 files changed, 82 insertions(+), 63 deletions(-)
diff --git a/src/mlpack/core/tree/CMakeLists.txt b/src/mlpack/core/tree/CMakeLists.txt
index 8f60033..2f61c29 100644
--- a/src/mlpack/core/tree/CMakeLists.txt
+++ b/src/mlpack/core/tree/CMakeLists.txt
@@ -34,6 +34,8 @@ set(SOURCES
rectangle_tree.hpp
rectangle_tree/rectangle_tree.hpp
rectangle_tree/rectangle_tree_impl.hpp
+ rectangle_tree/rectangle_tree_traverser.hpp
+ rectangle_tree/rectangle_tree_traverser_impl.hpp
rectangle_tree/r_tree_split.hpp
rectangle_tree/r_tree_split_impl.hpp
rectangle_tree/r_tree_descent_heuristic.hpp
diff --git a/src/mlpack/methods/neighbor_search/allknn_main.cpp b/src/mlpack/methods/neighbor_search/allknn_main.cpp
index 6d678ea..ae61205 100644
--- a/src/mlpack/methods/neighbor_search/allknn_main.cpp
+++ b/src/mlpack/methods/neighbor_search/allknn_main.cpp
@@ -24,7 +24,7 @@ using namespace mlpack::tree;
PROGRAM_INFO("All K-Nearest-Neighbors",
"This program will calculate the all k-nearest-neighbors of a set of "
"points using kd-trees or cover trees (cover tree support is experimental "
- "and may not be optimally fast). You may specify a separate set of "
+ "and may be slow). You may specify a separate set of "
"reference points and query points, or just a reference set which will be "
"used as both the reference and query set."
"\n\n"
@@ -57,6 +57,8 @@ PARAM_FLAG("single_mode", "If true, single-tree search is used (as opposed to "
"dual-tree search).", "S");
PARAM_FLAG("cover_tree", "If true, use cover trees to perform the search "
"(experimental, may be slow).", "c");
+PARAM_FLAG("r_tree", "If true, use an R-Tree to perform the search "
+ "(experimental, may be slow. Currently automatically sets single_mode.).", "R");
PARAM_FLAG("random_basis", "Before tree-building, project the data onto a "
"random orthogonal basis.", "R");
PARAM_INT("seed", "Random seed (if 0, std::time(NULL) is used).", "s", 0);
@@ -123,6 +125,15 @@ int main(int argc, char *argv[])
Log::Warn << "--single_mode ignored because --naive is present." << endl;
}
+ // cover_tree overrides r_tree.
+ if (CLI::HasParam("cover_tree") && CLI::HasParam("r_tree"))
+ {
+ Log::Warn << "--cover_tree overrides --r_tree." << endl;
+ } else if (!singleMode && CLI::HasParam("r_tree")) // R_tree requires single mode.
+ {
+ Log::Warn << "--single_mode assumed because --r_tree is present." << endl;
+ }
+
if (naive)
leafSize = referenceData.n_cols;
@@ -168,90 +179,96 @@ int main(int argc, char *argv[])
if (!CLI::HasParam("cover_tree"))
{
- // Because we may construct it differently, we need a pointer.
- AllkNN* allknn = NULL;
+ if(!CLI::HasParam("r_tree"))
+ {
+ // Because we may construct it differently, we need a pointer.
+ AllkNN* allknn = NULL;
- // Mappings for when we build the tree.
- std::vector<size_t> oldFromNewRefs;
+ // Mappings for when we build the tree.
+ std::vector<size_t> oldFromNewRefs;
- // Build trees by hand, so we can save memory: if we pass a tree to
- // NeighborSearch, it does not copy the matrix.
- Log::Info << "Building reference tree..." << endl;
- Timer::Start("tree_building");
+ // Build trees by hand, so we can save memory: if we pass a tree to
+ // NeighborSearch, it does not copy the matrix.
+ Log::Info << "Building reference tree..." << endl;
+ Timer::Start("tree_building");
- BinarySpaceTree<bound::HRectBound<2>,
- NeighborSearchStat<NearestNeighborSort> >
- refTree(referenceData, oldFromNewRefs, leafSize);
- BinarySpaceTree<bound::HRectBound<2>,
- NeighborSearchStat<NearestNeighborSort> >*
- queryTree = NULL; // Empty for now.
+ BinarySpaceTree<bound::HRectBound<2>,
+ NeighborSearchStat<NearestNeighborSort> >
+ refTree(referenceData, oldFromNewRefs, leafSize);
+ BinarySpaceTree<bound::HRectBound<2>,
+ NeighborSearchStat<NearestNeighborSort> >*
+ queryTree = NULL; // Empty for now.
- Timer::Stop("tree_building");
+ Timer::Stop("tree_building");
- std::vector<size_t> oldFromNewQueries;
+ std::vector<size_t> oldFromNewQueries;
- if (CLI::GetParam<string>("query_file") != "")
- {
- if (naive && leafSize < queryData.n_cols)
- leafSize = queryData.n_cols;
+ if (CLI::GetParam<string>("query_file") != "")
+ {
+ if (naive && leafSize < queryData.n_cols)
+ leafSize = queryData.n_cols;
- Log::Info << "Loaded query data from '" << queryFile << "' ("
- << queryData.n_rows << " x " << queryData.n_cols << ")." << endl;
+ Log::Info << "Loaded query data from '" << queryFile << "' ("
+ << queryData.n_rows << " x " << queryData.n_cols << ")." << endl;
- Log::Info << "Building query tree..." << endl;
+ Log::Info << "Building query tree..." << endl;
- // Build trees by hand, so we can save memory: if we pass a tree to
- // NeighborSearch, it does not copy the matrix.
- if (!singleMode)
- {
- Timer::Start("tree_building");
+ // Build trees by hand, so we can save memory: if we pass a tree to
+ // NeighborSearch, it does not copy the matrix.
+ if (!singleMode)
+ {
+ Timer::Start("tree_building");
- queryTree = new BinarySpaceTree<bound::HRectBound<2>,
- NeighborSearchStat<NearestNeighborSort> >(queryData,
- oldFromNewQueries, leafSize);
+ queryTree = new BinarySpaceTree<bound::HRectBound<2>,
+ NeighborSearchStat<NearestNeighborSort> >(queryData,
+ oldFromNewQueries, leafSize);
- Timer::Stop("tree_building");
+ Timer::Stop("tree_building");
+ }
+
+ allknn = new AllkNN(&refTree, queryTree, referenceData, queryData,
+ singleMode);
+
+ Log::Info << "Tree built." << endl;
}
+ else
+ {
+ allknn = new AllkNN(&refTree, referenceData, singleMode);
- allknn = new AllkNN(&refTree, queryTree, referenceData, queryData,
- singleMode);
+ Log::Info << "Trees built." << endl;
+ }
- Log::Info << "Tree built." << endl;
- }
- else
- {
- allknn = new AllkNN(&refTree, referenceData, singleMode);
+ arma::mat distancesOut;
+ arma::Mat<size_t> neighborsOut;
- Log::Info << "Trees built." << endl;
- }
+ Log::Info << "Computing " << k << " nearest neighbors..." << endl;
+ allknn->Search(k, neighborsOut, distancesOut);
- arma::mat distancesOut;
- arma::Mat<size_t> neighborsOut;
+ Log::Info << "Neighbors computed." << endl;
- Log::Info << "Computing " << k << " nearest neighbors..." << endl;
- allknn->Search(k, neighborsOut, distancesOut);
+ // We have to map back to the original indices from before the tree
+ // construction.
+ Log::Info << "Re-mapping indices..." << endl;
- Log::Info << "Neighbors computed." << endl;
+ // Map the results back to the correct places.
+ if ((CLI::GetParam<string>("query_file") != "") && !singleMode)
+ Unmap(neighborsOut, distancesOut, oldFromNewRefs, oldFromNewQueries,
+ neighbors, distances);
+ else if ((CLI::GetParam<string>("query_file") != "") && singleMode)
+ Unmap(neighborsOut, distancesOut, oldFromNewRefs, neighbors, distances);
+ else
+ Unmap(neighborsOut, distancesOut, oldFromNewRefs, oldFromNewRefs,
+ neighbors, distances);
- // We have to map back to the original indices from before the tree
- // construction.
- Log::Info << "Re-mapping indices..." << endl;
+ // Clean up.
+ if (queryTree)
+ delete queryTree;
- // Map the results back to the correct places.
- if ((CLI::GetParam<string>("query_file") != "") && !singleMode)
- Unmap(neighborsOut, distancesOut, oldFromNewRefs, oldFromNewQueries,
- neighbors, distances);
- else if ((CLI::GetParam<string>("query_file") != "") && singleMode)
- Unmap(neighborsOut, distancesOut, oldFromNewRefs, neighbors, distances);
- else
- Unmap(neighborsOut, distancesOut, oldFromNewRefs, oldFromNewRefs,
- neighbors, distances);
+ delete allknn;
+ } else { // R tree.
- // Clean up.
- if (queryTree)
- delete queryTree;
- delete allknn;
+ }
}
else // Cover trees.
{
More information about the mlpack-git
mailing list