[mlpack-git] master: Merge remote-tracking branch 'upstream/master' into ubtree (2c5eb57)
gitdub at mlpack.org
gitdub at mlpack.org
Thu Aug 18 13:58:22 EDT 2016
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/1797a49c8f76d65814fec4a122d0d2fea01fc2d9...9e5cd0ac9c5cde9ac141bc84e7327bd11e19d42e
>---------------------------------------------------------------
commit 2c5eb5780226c30b8fb088ee928487f0970dc802
Merge: 9bd634a 0a19d07
Author: Mikhail Lozhnikov <lozhnikovma at gmail.com>
Date: Thu Aug 18 20:58:22 2016 +0300
Merge remote-tracking branch 'upstream/master' into ubtree
>---------------------------------------------------------------
2c5eb5780226c30b8fb088ee928487f0970dc802
CMakeLists.txt | 4 +-
src/mlpack/core/data/load_impl.hpp | 4 +-
src/mlpack/core/tree/CMakeLists.txt | 18 +
.../core/tree/binary_space_tree/mean_split.hpp | 1 +
src/mlpack/core/tree/binary_space_tree/traits.hpp | 20 +
.../core/tree/cover_tree/cover_tree_impl.hpp | 25 +-
src/mlpack/core/tree/cover_tree/traits.hpp | 5 +
.../tree/rectangle_tree/r_star_tree_split_impl.hpp | 8 +-
src/mlpack/core/tree/rectangle_tree/traits.hpp | 12 +
.../core/tree/rectangle_tree/x_tree_split_impl.hpp | 2 +-
src/mlpack/core/tree/space_split/hyperplane.hpp | 151 +++++
.../core/tree/space_split/mean_space_split.hpp | 45 ++
.../tree/space_split/mean_space_split_impl.hpp | 45 ++
.../core/tree/space_split/midpoint_space_split.hpp | 45 ++
.../tree/space_split/midpoint_space_split_impl.hpp | 40 ++
.../core/tree/space_split/projection_vector.hpp | 149 ++++
src/mlpack/core/tree/space_split/space_split.hpp | 67 ++
.../core/tree/space_split/space_split_impl.hpp | 103 +++
src/mlpack/core/tree/spill_tree.hpp | 21 +
src/mlpack/core/tree/spill_tree/is_spill_tree.hpp | 38 ++
.../spill_dual_tree_traverser.hpp} | 35 +-
.../spill_tree/spill_dual_tree_traverser_impl.hpp | 416 ++++++++++++
.../spill_single_tree_traverser.hpp} | 29 +-
.../spill_single_tree_traverser_impl.hpp | 125 ++++
src/mlpack/core/tree/spill_tree/spill_tree.hpp | 450 ++++++++++++
.../core/tree/spill_tree/spill_tree_impl.hpp | 755 +++++++++++++++++++++
src/mlpack/core/tree/spill_tree/traits.hpp | 68 ++
src/mlpack/core/tree/spill_tree/typedef.hpp | 119 ++++
src/mlpack/core/tree/tree_traits.hpp | 6 +
src/mlpack/core/util/backtrace.cpp | 4 +-
.../simple_tolerance_termination.hpp | 8 +-
.../validation_RMSE_termination.hpp | 10 +-
.../svd_complete_incremental_learning.hpp | 8 +-
.../svd_incomplete_incremental_learning.hpp | 6 +-
.../ann/activation_functions/logistic_function.hpp | 2 +-
src/mlpack/methods/ann/layer/dropconnect_layer.hpp | 28 +-
src/mlpack/methods/cf/svd_wrapper_impl.hpp | 4 +-
src/mlpack/methods/hmm/hmm_regression_impl.hpp | 2 +-
src/mlpack/methods/neighbor_search/kfn_main.cpp | 73 +-
src/mlpack/methods/neighbor_search/knn_main.cpp | 115 +++-
.../methods/neighbor_search/neighbor_search.hpp | 54 +-
.../neighbor_search/neighbor_search_impl.hpp | 237 +++++--
.../neighbor_search/neighbor_search_rules.hpp | 3 +
.../neighbor_search/neighbor_search_rules_impl.hpp | 7 +-
src/mlpack/methods/neighbor_search/ns_model.hpp | 47 +-
.../methods/neighbor_search/ns_model_impl.hpp | 99 ++-
src/mlpack/methods/neighbor_search/typedef.hpp | 29 +
src/mlpack/methods/pca/pca_main.cpp | 4 +-
src/mlpack/methods/rann/ra_search_rules.hpp | 3 +
.../regularized_svd/regularized_svd_function.cpp | 2 +-
src/mlpack/tests/CMakeLists.txt | 12 +-
src/mlpack/tests/adaboost_test.cpp | 2 +-
src/mlpack/tests/aknn_test.cpp | 41 ++
src/mlpack/tests/hyperplane_test.cpp | 135 ++++
src/mlpack/tests/knn_test.cpp | 90 +++
src/mlpack/tests/rectangle_tree_test.cpp | 4 +-
src/mlpack/tests/spill_tree_test.cpp | 306 +++++++++
57 files changed, 3933 insertions(+), 208 deletions(-)
diff --cc src/mlpack/core/tree/binary_space_tree/traits.hpp
index 8516eec,f5dc4ac..69bda7c
--- a/src/mlpack/core/tree/binary_space_tree/traits.hpp
+++ b/src/mlpack/core/tree/binary_space_tree/traits.hpp
@@@ -194,31 -213,9 +213,32 @@@ class TreeTraits<BinarySpaceTree<Metric
static const bool HasSelfChildren = false;
static const bool RearrangesDataset = true;
static const bool BinaryTree = true;
+ static const bool UniqueNumDescendants = true;
};
+/**
+ * This is a specialization of the TreeType class to the UBTree tree type.
+ * The only difference with general BinarySpaceTree is that UBTree can have
+ * overlapping children.
+ * See mlpack/core/tree/tree_traits.hpp for more information.
+ */
+template<typename MetricType,
+ typename StatisticType,
+ typename MatType,
+ template<typename SplitBoundType, typename SplitMatType>
+ class SplitType>
+class TreeTraits<BinarySpaceTree<MetricType, StatisticType, MatType,
+ bound::CellBound, SplitType>>
+{
+ public:
+ static const bool HasOverlappingChildren = true;
+ static const bool HasDuplicatedPoints = false;
+ static const bool FirstPointIsCentroid = false;
+ static const bool HasSelfChildren = false;
+ static const bool RearrangesDataset = true;
+ static const bool BinaryTree = true;
+};
+
} // namespace tree
} // namespace mlpack
diff --cc src/mlpack/methods/neighbor_search/knn_main.cpp
index 33f2afd,9b2921f..aa6f152
--- a/src/mlpack/methods/neighbor_search/knn_main.cpp
+++ b/src/mlpack/methods/neighbor_search/knn_main.cpp
@@@ -64,11 -69,16 +69,16 @@@ 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', 'vp', 'rp', 'max-rp', "
- "'cover', 'r', 'r-star', 'x', 'ball', 'hilbert-r', 'r-plus', 'r-plus-plus',"
- " 'spill'.", "t", "kd");
+ "'ub', 'cover', 'r', 'r-star', 'x', 'ball', 'hilbert-r', 'r-plus', "
- "'r-plus-plus'.", "t", "kd");
- PARAM_INT_IN("leaf_size", "Leaf size for tree building (used for kd-trees, "
- "vp trees, random projection trees, UB trees, R trees, R* trees, X trees, "
- "Hilbert R trees, R+ trees and R++ trees).", "l", 20);
++ "'r-plus-plus', 'spill'.", "t", "kd");
+ PARAM_INT_IN("leaf_size", "Leaf size for tree building (used for kd-trees, vp "
- "trees, random projection trees, R trees, R* trees, X trees, "
++ "trees, random projection trees, UB 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 (only valid for spill trees).", "u",
+ 0);
+ PARAM_DOUBLE_IN("rho", "Balance threshold (only valid 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);
@@@ -187,12 -219,10 +219,13 @@@ int main(int argc, char *argv[]
tree = KNNModel::RP_TREE;
else if (treeType == "max-rp")
tree = KNNModel::MAX_RP_TREE;
+ else if (treeType == "ub")
+ tree = KNNModel::UB_TREE;
else
Log::Fatal << "Unknown tree type '" << treeType << "'; valid choices are "
- << "'kd', 'vp', 'rp', 'max-rp', 'cover', 'r', 'r-star', 'x', 'ball', "
- << "'hilbert-r', 'r-plus' and 'r-plus-plus', and 'spill'." << endl;
+ << "'kd', 'vp', 'rp', 'max-rp', 'ub', 'cover', 'r', 'r-star', 'x', "
- << "'ball', 'hilbert-r', 'r-plus' and 'r-plus-plus'." << endl;
++ << "'ball', 'hilbert-r', 'r-plus' and 'r-plus-plus', and 'spill'."
++ << endl;
knn.TreeType() = tree;
knn.RandomBasis() = randomBasis;
diff --cc src/mlpack/methods/neighbor_search/ns_model.hpp
index b6778b9,48f6b26..28971a9
--- a/src/mlpack/methods/neighbor_search/ns_model.hpp
+++ b/src/mlpack/methods/neighbor_search/ns_model.hpp
@@@ -260,7 -280,7 +280,8 @@@ class NSMode
VP_TREE,
RP_TREE,
MAX_RP_TREE,
- SPILL_TREE
++ SPILL_TREE,
+ UB_TREE
};
private:
@@@ -292,7 -317,7 +318,8 @@@
NSType<SortPolicy, tree::VPTree>*,
NSType<SortPolicy, tree::RPTree>*,
NSType<SortPolicy, tree::MaxRPTree>*,
- SpillKNN*> nSearch;
++ SpillKNN*,
+ NSType<SortPolicy, tree::UBTree>*> nSearch;
public:
/**
diff --cc src/mlpack/methods/neighbor_search/ns_model_impl.hpp
index 28d2731,bdc0366..b232cfd
--- a/src/mlpack/methods/neighbor_search/ns_model_impl.hpp
+++ b/src/mlpack/methods/neighbor_search/ns_model_impl.hpp
@@@ -405,14 -470,12 +470,16 @@@ void NSModel<SortPolicy>::BuildModel(ar
case MAX_RP_TREE:
nSearch = new NSType<SortPolicy, tree::MaxRPTree>(naive, singleMode,
epsilon);
+ case SPILL_TREE:
+ nSearch = new SpillKNN(naive, singleMode, epsilon);
break;
+ case UB_TREE:
+ nSearch = new NSType<SortPolicy, tree::UBTree>(naive, singleMode,
+ 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)
More information about the mlpack-git
mailing list