[mlpack-git] master, mlpack-1.0.x: require kd-trees to have leafSize of at least 1. Add an assert to ensure that the SingleTreeTraverser isn't called on a tree with only one node. (8766861)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Thu Mar 5 21:48:33 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 8766861165fa8832b6e486730a4d4a43b796485d
Author: andrewmw94 <andrewmw94 at gmail.com>
Date: Thu Jun 5 17:22:25 2014 +0000
require kd-trees to have leafSize of at least 1. Add an assert to ensure that the SingleTreeTraverser isn't called on a tree with only one node.
>---------------------------------------------------------------
8766861165fa8832b6e486730a4d4a43b796485d
.../rectangle_tree/r_tree_descent_heuristic.hpp | 4 +-
.../r_tree_descent_heuristic_impl.hpp | 4 +-
.../rectangle_tree/rectangle_tree_traverser.hpp | 2 +-
.../rectangle_tree_traverser_impl.hpp | 46 ++++++++++++++++++++++
src/mlpack/methods/neighbor_search/allknn_main.cpp | 6 +--
.../neighbor_search/neighbor_search_impl.hpp | 4 ++
6 files changed, 58 insertions(+), 8 deletions(-)
diff --git a/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic.hpp b/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic.hpp
index 40e07b4..f023a02 100644
--- a/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic.hpp
@@ -18,7 +18,7 @@ namespace tree /** Trees and tree-building procedures. */ {
* The split is done in the dimension that has the maximum width. The points are
* divided into two parts based on the mean in this dimension.
*/
-template<typename BoundType, typename MatType = arma::mat>
+template<typename MatType = arma::mat>
class RTreeDescentHueristic
{
public:
@@ -30,7 +30,7 @@ class RTreeDescentHueristic
* @param bound The bound used for the node that is being evaluated.
* @param point The point that is being inserted.
*/
- static double EvalNode(const BoundType& bound, const arma::vec& point);
+ static double EvalNode(const HRectBound& bound, const arma::vec& point);
};
}; // namespace tree
diff --git a/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp b/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp
index 0df3110..9039a78 100644
--- a/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/r_tree_descent_heuristic_impl.hpp
@@ -18,8 +18,8 @@ namespace tree {
* The split is done in the dimension that has the maximum width. The points are
* divided into two parts based on the mean in this dimension.
*/
-template<typename BoundType, typename MatType = arma::mat>
-double RTreeDescentHeuristic<BoundType, MatType>::EvalNode(const BoundType& bound, const arma::vec& point)
+template<typename MatType = arma::mat>
+double RTreeDescentHeuristic<MatType>::EvalNode(const HRectBound& bound, const arma::vec& point)
{
return bound.contains(point) ? 0 : bound.minDistance(point);
}
diff --git a/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser.hpp b/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser.hpp
index 5dbea6f..c8b699b 100644
--- a/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser.hpp
@@ -16,7 +16,7 @@
namespace mlpack {
namespace tree {
-template<typename Statistic Type,
+template<typename StatisticType,
typename MatType,
typename SplitType>
template<typename RuleType>
diff --git a/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser_impl.hpp b/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser_impl.hpp
index 8d1c8b6..013c951 100644
--- a/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser_impl.hpp
@@ -1 +1,47 @@
+/**
+ * @file rectangle_tree_traverser.hpp
+ * @author Andrew Wells
+ *
+ * A class for traversing rectangle type trees with a given set of rules
+ * which indicate the branches to prune and the order in which to recurse.
+ * This is a depth-first traverser.
+ */
+#ifndef __MLPAC_CORE_TREE_RECTANGLE_TREE_RECTANGLE_TREE_TRAVERSER_IMPL_HPP
+#define __MLPAC_CORE_TREE_RECTANGLE_TREE_RECTANGLE_TREE_TRAVERSER_IMPL_HPP
+#include "rectangle_tree_traverser.hpp"
+
+#include <stack>
+
+namespace mlpack {
+namespace tree {
+
+template<typename StatisticType,
+ typename MatType,
+ typename SplitType,
+ typename DescentType>
+template<typename RuleType>
+RectangleTree<StatisticType, MatType, SplitType, DescentType>::
+RectangleTreeTraverser<RuleType>::RectangleTreeTraverser(RuleType& rule) :
+ rule(rule),
+ numPrunes(0)
+{ /* Nothing to do */ }
+
+template<typename StatisticType,
+ typename MatType,
+ typename SplitType
+ typename DescentType>
+template<typename RuleType>
+void RectangleTree<StatisticType, MatType, SplitType, DescentType>::
+RectangleTreeTraverser<RuleType>::Traverse(
+ const size_t queryIndex,
+ RectangeTree<StatisticType, MatyType, SplitType, DescentType>&
+ referenceNode)
+{
+
+}
+
+}; // namespace tree
+}; // namespace mlpack
+
+#endif
\ No newline at end of file
diff --git a/src/mlpack/methods/neighbor_search/allknn_main.cpp b/src/mlpack/methods/neighbor_search/allknn_main.cpp
index 533af85..6d678ea 100644
--- a/src/mlpack/methods/neighbor_search/allknn_main.cpp
+++ b/src/mlpack/methods/neighbor_search/allknn_main.cpp
@@ -101,7 +101,7 @@ int main(int argc, char *argv[])
}
// Sanity check on k value: must be greater than 0, must be less than the
- // number of reference points.
+ // number of reference points. Since it is unsigned, we only test the upper bound.
if (k > referenceData.n_cols)
{
Log::Fatal << "Invalid k: " << k << "; must be greater than 0 and less ";
@@ -110,10 +110,10 @@ int main(int argc, char *argv[])
}
// Sanity check on leaf size.
- if (lsInt < 0)
+ if (lsInt < 1)
{
Log::Fatal << "Invalid leaf size: " << lsInt << ". Must be greater "
- "than or equal to 0." << endl;
+ "than 0." << endl;
}
size_t leafSize = lsInt;
diff --git a/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp b/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
index c694aa0..dac46c0 100644
--- a/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
+++ b/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
@@ -252,6 +252,10 @@ void NeighborSearch<SortPolicy, MetricType, TreeType>::Search(
}
else if (singleMode)
{
+ // The search doesn't work if the root node is also a leaf node.
+ // if this is the case, it is suggested that you use the naive method.
+ assert(!(referenceTree->IsLeaf()));
+
// Create the traverser.
typename TreeType::template SingleTreeTraverser<RuleType> traverser(rules);
More information about the mlpack-git
mailing list