[mlpack-git] master,mlpack-1.0.x: tree traversal (ea0fb14)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Thu Mar 5 21:51:35 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 ea0fb146be822573f9c3ea951dd1264515efb9f9
Author: andrewmw94 <andrewmw94 at gmail.com>
Date: Mon Jul 7 14:32:14 2014 +0000
tree traversal
>---------------------------------------------------------------
ea0fb146be822573f9c3ea951dd1264515efb9f9
.../core/tree/binary_space_tree/binary_space_tree.hpp | 2 +-
.../core/tree/rectangle_tree/rectangle_tree_impl.hpp | 14 +++++++-------
.../tree/rectangle_tree/single_tree_traverser_impl.hpp | 8 +++-----
src/mlpack/methods/neighbor_search/allknn_main.cpp | 9 +++++----
.../methods/neighbor_search/neighbor_search_impl.hpp | 4 ----
src/mlpack/tests/rectangle_tree_test.cpp | 6 +++---
6 files changed, 19 insertions(+), 24 deletions(-)
diff --git a/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp b/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
index 62131d0..142683a 100644
--- a/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
+++ b/src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp
@@ -66,7 +66,7 @@ class BinarySpaceTree
size_t splitDimension;
//! The distance from the centroid of this node to the centroid of the parent.
double parentDistance;
- //! The distance to the furthest descendant, cached to speed things up.
+ //! The worst possible distance to the furthest descendant, cached to speed things up.
double furthestDescendantDistance;
//! The dataset.
MatType& dataset;
diff --git a/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp b/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp
index 0b16246..d1ed3e2 100644
--- a/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/rectangle_tree_impl.hpp
@@ -268,7 +268,6 @@ inline bool RectangleTree<SplitType, DescentType, StatisticType, MatType>::
return numChildren == 0;
}
-
/**
* Return a bound on the furthest point in the node form the centroid.
* This returns 0 unless the node is a leaf.
@@ -301,7 +300,8 @@ template<typename SplitType,
inline double RectangleTree<SplitType, DescentType, StatisticType, MatType>::
FurthestDescendantDistance() const
{
- return furthestDescendantDistance;
+ //return the distance from the centroid to a corner of the bound.
+ return 0.5 * bound.Diameter();
}
/**
@@ -342,7 +342,7 @@ inline size_t RectangleTree<SplitType, DescentType, StatisticType, MatType>::
}
/**
- * Return the index of a particular descendant contained in this node. SEE OTHER WARNINGS
+ * Return the index of a particular descendant contained in this node.
*/
template<typename SplitType,
typename DescentType,
@@ -351,11 +351,11 @@ template<typename SplitType,
inline size_t RectangleTree<SplitType, DescentType, StatisticType, MatType>::
Descendant(const size_t index) const
{
- return (begin + index);
+ return (points[index]);
}
/**
- * Return the index of a particular point contained in this node. SEE OTHER WARNINGS
+ * Return the index of a particular point contained in this node.
*/
template<typename SplitType,
typename DescentType,
@@ -368,8 +368,8 @@ inline size_t RectangleTree<SplitType, DescentType, StatisticType, MatType>::
}
/**
- * Return the last point in the tree. SINCE THE TREE STORES DATA SEPARATELY IN EACH LEAF
- * THIS IS CURRENTLY MEANINGLESS.
+ * Return the last point in the tree. WARNING: POINTS ARE NOT MOVED IN THE ORIGINAL DATASET,
+ * SO THIS IS RATHER POINTLESS.
*/
template<typename SplitType,
typename DescentType,
diff --git a/src/mlpack/core/tree/rectangle_tree/single_tree_traverser_impl.hpp b/src/mlpack/core/tree/rectangle_tree/single_tree_traverser_impl.hpp
index d9f0d70..5168fc0 100644
--- a/src/mlpack/core/tree/rectangle_tree/single_tree_traverser_impl.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/single_tree_traverser_impl.hpp
@@ -6,8 +6,8 @@
* 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_SINGLE_TREE_TRAVERSER_IMPL_HPP
-#define __MLPAC_CORE_TREE_RECTANGLE_TREE_SINGLE_TREE_TRAVERSER_IMPL_HPP
+#ifndef __MLPACK_CORE_TREE_RECTANGLE_TREE_SINGLE_TREE_TRAVERSER_IMPL_HPP
+#define __MLPACK_CORE_TREE_RECTANGLE_TREE_SINGLE_TREE_TRAVERSER_IMPL_HPP
#include "single_tree_traverser.hpp"
@@ -42,7 +42,6 @@ SingleTreeTraverser<RuleType>::Traverse(
// If we reach a leaf node, we need to run the base case.
if(referenceNode.IsLeaf()) {
- std::cout << "we reached a leaf" << std::endl;
for(size_t i = 0; i < referenceNode.Count(); i++) {
rule.BaseCase(queryIndex, referenceNode.Points()[i]);
}
@@ -62,9 +61,8 @@ SingleTreeTraverser<RuleType>::Traverse(
// one that isn't good enough.
for(int i = 0; i < referenceNode.NumChildren(); i++) {
if(rule.Rescore(queryIndex, *nodesAndScores[i].node, nodesAndScores[i].score) != DBL_MAX)
- Traverse(queryIndex, nodesAndScores[i].node);
+ Traverse(queryIndex, *nodesAndScores[i].node);
else {
- std::cout << "we are pruning: " << referenceNode.NumChildren() - i << " nodes." << std::endl;
numPrunes += referenceNode.NumChildren() - i;
return;
}
diff --git a/src/mlpack/methods/neighbor_search/allknn_main.cpp b/src/mlpack/methods/neighbor_search/allknn_main.cpp
index f55ccbc..83a0be9 100644
--- a/src/mlpack/methods/neighbor_search/allknn_main.cpp
+++ b/src/mlpack/methods/neighbor_search/allknn_main.cpp
@@ -318,15 +318,16 @@ int main(int argc, char *argv[])
}
Log::Info << "Tree built." << endl;
- arma::mat distancesOut;
- arma::Mat<size_t> neighborsOut;
+ //arma::mat distancesOut;
+ //arma::Mat<size_t> neighborsOut;
Log::Info << "Computing " << k << " nearest neighbors..." << endl;
- allknn->Search(k, neighborsOut, distancesOut);
+ allknn->Search(k, neighbors, distances);
Log::Info << "Neighbors computed." << endl;
+
delete allknn;
}
}
@@ -387,7 +388,7 @@ int main(int argc, char *argv[])
delete queryTree;
}
- // Save output.
+ // Save put.
data::Save(distancesFile, distances);
data::Save(neighborsFile, neighbors);
}
diff --git a/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp b/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
index 1ff8a2e..12f8f46 100644
--- a/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
+++ b/src/mlpack/methods/neighbor_search/neighbor_search_impl.hpp
@@ -253,7 +253,6 @@ void NeighborSearch<SortPolicy, MetricType, TreeType>::Search(
else if (singleMode)
{
- std::cout << " we are in NeighborSearchImpl" << std::endl;
// 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()));
@@ -261,9 +260,6 @@ void NeighborSearch<SortPolicy, MetricType, TreeType>::Search(
// Create the traverser.
typename TreeType::template SingleTreeTraverser<RuleType> traverser(rules);
- std::cout << " n_cols = " << querySet.n_cols << std::endl;
-
-
// Now have it traverse for each point.
for (size_t i = 0; i < querySet.n_cols; ++i)
traverser.Traverse(i, *referenceTree);
diff --git a/src/mlpack/tests/rectangle_tree_test.cpp b/src/mlpack/tests/rectangle_tree_test.cpp
index 83caf30..5e00d75 100644
--- a/src/mlpack/tests/rectangle_tree_test.cpp
+++ b/src/mlpack/tests/rectangle_tree_test.cpp
@@ -47,7 +47,7 @@ BOOST_AUTO_TEST_CASE(RectangeTreeTraitsTest)
BOOST_AUTO_TEST_CASE(RectangleTreeConstructionCountTest)
{
arma::mat dataset;
- dataset.randu(8, 1000); // 1000 points in 3 dimensions.
+ dataset.randu(3, 1000); // 1000 points in 3 dimensions.
RectangleTree<tree::RTreeSplit<tree::RTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
tree::RTreeDescentHeuristic,
@@ -80,7 +80,7 @@ std::vector<arma::vec*> getAllPointsInTree(const RectangleTree<tree::RTreeSplit<
BOOST_AUTO_TEST_CASE(RectangleTreeConstructionRepeatTest)
{
arma::mat dataset;
- dataset.randu(8, 15); // 1000 points in 8 dimensions.
+ dataset.randu(8, 1000); // 1000 points in 8 dimensions.
RectangleTree<tree::RTreeSplit<tree::RTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
tree::RTreeDescentHeuristic,
@@ -130,7 +130,7 @@ bool checkContainment(const RectangleTree<tree::RTreeSplit<tree::RTreeDescentHeu
BOOST_AUTO_TEST_CASE(RectangleTreeContainmentTest)
{
arma::mat dataset;
- dataset.randu(8, 15); // 1000 points in 8 dimensions.
+ dataset.randu(8, 1000); // 1000 points in 8 dimensions.
RectangleTree<tree::RTreeSplit<tree::RTreeDescentHeuristic, NeighborSearchStat<NearestNeighborSort>, arma::mat>,
tree::RTreeDescentHeuristic,
More information about the mlpack-git
mailing list