[mlpack-git] master: Merge branch 'master' into spill-trees (d22e65a)
gitdub at mlpack.org
gitdub at mlpack.org
Thu Aug 11 18:02:41 EDT 2016
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/0f4b25acd6aaa14294c044874ba6cc0751712baa...0a19d07bd39e6223991976474bc79671ba8aa0f0
>---------------------------------------------------------------
commit d22e65acf2ba59ce4d2df1bb5b0a74b3ece76fee
Merge: f33a19d 067ff77
Author: MarcosPividori <marcos.pividori at gmail.com>
Date: Thu Aug 11 19:02:41 2016 -0300
Merge branch 'master' into spill-trees
>---------------------------------------------------------------
d22e65acf2ba59ce4d2df1bb5b0a74b3ece76fee
HISTORY.md | 9 +-
src/mlpack/core/dists/gamma_distribution.cpp | 134 +++++-
src/mlpack/core/dists/gamma_distribution.hpp | 105 ++++-
src/mlpack/core/math/random.hpp | 38 ++
src/mlpack/core/tree/CMakeLists.txt | 13 +
src/mlpack/core/tree/ballbound_impl.hpp | 2 -
.../tree/binary_space_tree/binary_space_tree.hpp | 3 -
src/mlpack/core/tree/binary_space_tree/traits.hpp | 7 +
src/mlpack/core/tree/bounds.hpp | 1 +
src/mlpack/core/tree/cosine_tree/cosine_tree.cpp | 43 +-
src/mlpack/core/tree/cover_tree/cover_tree.hpp | 3 -
.../core/tree/cover_tree/cover_tree_impl.hpp | 32 +-
src/mlpack/core/tree/cover_tree/traits.hpp | 6 +
.../tree/{ballbound.hpp => hollow_ball_bound.hpp} | 125 ++---
src/mlpack/core/tree/hollow_ball_bound_impl.hpp | 380 ++++++++++++++++
src/mlpack/core/tree/hrectbound_impl.hpp | 2 -
.../core/tree/rectangle_tree/rectangle_tree.hpp | 3 -
src/mlpack/core/tree/rectangle_tree/traits.hpp | 12 +
src/mlpack/core/tree/tree_traits.hpp | 8 +-
src/mlpack/core/tree/vantage_point_tree.hpp | 21 +
.../dual_tree_traverser.hpp | 34 +-
.../dual_tree_traverser_impl.hpp | 237 ++++++++++
.../single_tree_traverser.hpp | 18 +-
.../single_tree_traverser_impl.hpp | 113 +++++
src/mlpack/core/tree/vantage_point_tree/traits.hpp | 66 +++
.../core/tree/vantage_point_tree/typedef.hpp | 76 ++++
.../vantage_point_tree/vantage_point_split.hpp | 157 +++++++
.../vantage_point_split_impl.hpp | 233 ++++++++++
.../vantage_point_tree.hpp} | 220 +++++----
.../vantage_point_tree_impl.hpp} | 503 ++++++++++++---------
src/mlpack/methods/neighbor_search/kfn_main.cpp | 12 +-
src/mlpack/methods/neighbor_search/knn_main.cpp | 12 +-
.../neighbor_search/neighbor_search_impl.hpp | 27 +-
.../neighbor_search/neighbor_search_rules_impl.hpp | 53 ++-
src/mlpack/methods/neighbor_search/ns_model.hpp | 5 +-
.../methods/neighbor_search/ns_model_impl.hpp | 6 +
src/mlpack/methods/preprocess/CMakeLists.txt | 1 +
.../preprocess/preprocess_describe_main.cpp | 228 ++++++++++
.../methods/range_search/range_search_main.cpp | 12 +-
.../range_search/range_search_rules_impl.hpp | 42 +-
src/mlpack/methods/range_search/rs_model.cpp | 21 +-
src/mlpack/methods/range_search/rs_model.hpp | 6 +-
src/mlpack/methods/range_search/rs_model_impl.hpp | 14 +
src/mlpack/methods/rann/ra_search_impl.hpp | 4 +-
src/mlpack/methods/rann/ra_search_rules_impl.hpp | 46 +-
src/mlpack/methods/rann/ra_util.cpp | 16 -
src/mlpack/tests/CMakeLists.txt | 1 +
src/mlpack/tests/aknn_test.cpp | 16 +-
src/mlpack/tests/distribution_test.cpp | 118 +++++
src/mlpack/tests/knn_test.cpp | 12 +-
src/mlpack/tests/quic_svd_test.cpp | 11 +-
src/mlpack/tests/range_search_test.cpp | 12 +-
src/mlpack/tests/union_find_test.cpp | 40 +-
src/mlpack/tests/vantage_point_tree_test.cpp | 337 ++++++++++++++
54 files changed, 3107 insertions(+), 549 deletions(-)
diff --cc src/mlpack/methods/neighbor_search/knn_main.cpp
index 2e2d9cd,10cbd5d..32fe239
--- a/src/mlpack/methods/neighbor_search/knn_main.cpp
+++ b/src/mlpack/methods/neighbor_search/knn_main.cpp
@@@ -63,15 -63,11 +63,15 @@@ PARAM_INT_IN("k", "Number of nearest ne
// The user may specify the type of tree to use, and a few parameters for tree
// building.
- PARAM_STRING_IN("tree_type", "Type of tree to use: 'kd', 'cover', 'r', "
+ PARAM_STRING_IN("tree_type", "Type of tree to use: 'kd', 'vp', 'cover', 'r', "
- "'r-star', 'x', 'ball', 'hilbert-r', 'r-plus', 'r-plus-plus'.", "t", "kd");
+ "'r-star', 'x', 'ball', 'hilbert-r', 'r-plus', 'r-plus-plus', 'spill'.",
+ "t", "kd");
- PARAM_INT_IN("leaf_size", "Leaf size for tree building (used for kd-trees, R "
- "trees, R* trees, X trees, Hilbert R trees, R+ trees, R++ trees, and Spill "
- "trees).", "l", 20);
+ PARAM_INT_IN("leaf_size", "Leaf size for tree building (used for kd-trees, vp "
- "trees, R trees, R* trees, X trees, Hilbert R trees, R+ trees and R++ "
- "trees).", "l", 20);
++ "trees, R trees, R* trees, X trees, Hilbert R trees, R+ trees, R++ trees "
++ "and spill trees).", "l", 20);
+PARAM_DOUBLE_IN("tau", "Overlapping size (for spill trees).", "u", 0);
+PARAM_DOUBLE_IN("rho", "Balance threshold (for spill trees).", "b", 0.7);
+
PARAM_FLAG("random_basis", "Before tree-building, project the data onto a "
"random orthogonal basis.", "R");
PARAM_INT_IN("seed", "Random seed (if 0, std::time(NULL) is used).", "s", 0);
@@@ -211,12 -180,12 +211,14 @@@ int main(int argc, char *argv[]
tree = KNNModel::R_PLUS_TREE;
else if (treeType == "r-plus-plus")
tree = KNNModel::R_PLUS_PLUS_TREE;
+ else if (treeType == "spill")
+ tree = KNNModel::SPILL_TREE;
+ else if (treeType == "vp")
+ tree = KNNModel::VP_TREE;
else
Log::Fatal << "Unknown tree type '" << treeType << "'; valid choices are "
<< "'kd', 'cover', 'r', 'r-star', 'x', 'ball', 'hilbert-r', "
- << "'r-plus', 'r-plus-plus' and 'spill'." << endl;
- << "'r-plus', 'r-plus-plus' and 'vp'." << endl;
++ << "'r-plus', 'r-plus-plus', 'vp' and 'spill'." << endl;
knn.TreeType() = tree;
knn.RandomBasis() = randomBasis;
diff --cc src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
index da3b28e,d5112cb..cbc89ff
--- a/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
+++ b/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
@@@ -550,11 -553,11 +554,14 @@@ Search(Tree* queryTree
scores += rules.Scores();
baseCases += rules.BaseCases();
+ Log::Info << rules.Scores() << " node combinations were scored." << std::endl;
+ Log::Info << rules.BaseCases() << " base cases were calculated." << std::endl;
+
rules.GetResults(*neighborPtr, distances);
+ Log::Info << rules.Scores() << " node combinations were scored.\n";
+ Log::Info << rules.BaseCases() << " base cases were calculated.\n";
+
Timer::Stop("computing_neighbors");
// Do we need to map indices?
diff --cc src/mlpack/methods/neighbor_search/ns_model.hpp
index 4f34e07,fc782fe..2162903
--- a/src/mlpack/methods/neighbor_search/ns_model.hpp
+++ b/src/mlpack/methods/neighbor_search/ns_model.hpp
@@@ -13,10 -13,9 +13,11 @@@
#include <mlpack/core/tree/binary_space_tree.hpp>
#include <mlpack/core/tree/cover_tree.hpp>
#include <mlpack/core/tree/rectangle_tree.hpp>
+#include <mlpack/core/tree/spill_tree.hpp>
+ #include <mlpack/core/tree/vantage_point_tree.hpp>
#include <boost/variant.hpp>
#include "neighbor_search.hpp"
+#include "spill_search.hpp"
namespace mlpack {
namespace neighbor {
@@@ -283,7 -258,7 +284,8 @@@ class NSMode
HILBERT_R_TREE,
R_PLUS_TREE,
R_PLUS_PLUS_TREE,
- SPILL_TREE
++ SPILL_TREE,
+ VP_TREE
};
private:
@@@ -317,7 -287,7 +319,8 @@@
NSType<SortPolicy, tree::HilbertRTree>*,
NSType<SortPolicy, tree::RPlusTree>*,
NSType<SortPolicy, tree::RPlusPlusTree>*,
- NSType<SortPolicy, tree::VPTree>*> nSearch;
++ NSType<SortPolicy, tree::VPTree>*,
+ NSSpillType*> nSearch;
public:
/**
diff --cc src/mlpack/methods/neighbor_search/ns_model_impl.hpp
index 29cc167,2ca8be5..07c6f21
--- a/src/mlpack/methods/neighbor_search/ns_model_impl.hpp
+++ b/src/mlpack/methods/neighbor_search/ns_model_impl.hpp
@@@ -459,12 -394,13 +459,16 @@@ void NSModel<SortPolicy>::BuildModel(ar
nSearch = new NSType<SortPolicy, tree::RPlusPlusTree>(naive, singleMode,
epsilon);
break;
+ case VP_TREE:
+ nSearch = new NSType<SortPolicy, tree::VPTree>(naive, singleMode,
+ epsilon);
+ break;
+ case SPILL_TREE:
+ nSearch = new NSSpillType(naive, singleMode, tau, leafSize, rho, epsilon);
+ break;
}
- TrainVisitor<SortPolicy> tn(std::move(referenceSet), leafSize);
+ TrainVisitor<SortPolicy> tn(std::move(referenceSet), leafSize, tau, rho);
boost::apply_visitor(tn, nSearch);
if (!naive)
@@@ -546,8 -482,8 +550,10 @@@ std::string NSModel<SortPolicy>::TreeNa
return "R+ tree";
case R_PLUS_PLUS_TREE:
return "R++ tree";
+ case SPILL_TREE:
+ return "Spill tree";
+ case VP_TREE:
+ return "Vantage point tree";
default:
return "unknown tree";
}
diff --cc src/mlpack/tests/CMakeLists.txt
index a4b7420,4beb2e1..ecd2d58
--- a/src/mlpack/tests/CMakeLists.txt
+++ b/src/mlpack/tests/CMakeLists.txt
@@@ -85,6 -79,11 +85,7 @@@ add_executable(mlpack_tes
tree_test.cpp
tree_traits_test.cpp
union_find_test.cpp
- svd_batch_test.cpp
- svd_incremental_test.cpp
- nystroem_method_test.cpp
- armadillo_svd_test.cpp
+ vantage_point_tree_test.cpp
)
# Link dependencies of test executable.
target_link_libraries(mlpack_test
More information about the mlpack-git
mailing list