[mlpack-git] master, mlpack-1.0.x: Rectangle Tree Traversal implementation. (c7e7684)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Thu Mar 5 21:48: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 c7e768470a3ab4bf00f4aba186574912bfe9f6ff
Author: andrewmw94 <andrewmw94 at gmail.com>
Date: Thu Jun 5 20:52:29 2014 +0000
Rectangle Tree Traversal implementation.
>---------------------------------------------------------------
c7e768470a3ab4bf00f4aba186574912bfe9f6ff
.../rectangle_tree/rectangle_tree_traverser.hpp | 5 ++--
.../rectangle_tree_traverser_impl.hpp | 32 +++++++++++++++++++++-
2 files changed, 34 insertions(+), 3 deletions(-)
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 c8b699b..1531832 100644
--- a/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser.hpp
+++ b/src/mlpack/core/tree/rectangle_tree/rectangle_tree_traverser.hpp
@@ -18,9 +18,10 @@ namespace tree {
template<typename StatisticType,
typename MatType,
- typename SplitType>
+ typename SplitType
+ typename DescentType>
template<typename RuleType>
-class RectangleTree<StatisticType, MatType, SplitType>::
+class RectangleTree<StatisticType, MatType, SplitType, DescentType>::
RectangleTreeTraverser
{
public:
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 013c951..ce09feb 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,5 +1,5 @@
/**
- * @file rectangle_tree_traverser.hpp
+ * @file rectangle_tree_traverser_impl.hpp
* @author Andrew Wells
*
* A class for traversing rectangle type trees with a given set of rules
@@ -11,6 +11,7 @@
#include "rectangle_tree_traverser.hpp"
+#include <algorithm>
#include <stack>
namespace mlpack {
@@ -38,7 +39,36 @@ RectangleTreeTraverser<RuleType>::Traverse(
RectangeTree<StatisticType, MatyType, SplitType, DescentType>&
referenceNode)
{
+ // If we reach a leaf node, we need to run the base case.
+ if(referenceNode.IsLeaf()) {
+ for(size_t i = 0; i < referenceNode.Count(); i++) {
+ rule.BaseCase(queryIndex, i);
+ }
+ return;
+ }
+ // This is not a leaf node so we:
+ // Sort the children of this node by their scores.
+ std::vector<RectangleTree*> nodes = new std::vector<RectangleTree*>(referenceNode.NumChildren());
+ std::vector<double> scores = new std::vector<double>(referenceNode.NumChildren());
+ for(int i = 0; i < referenceNode.NumChildren(); i++) {
+ nodes[i] = referenceNode.Children()[i];
+ scores[i] = Rule.Score(nodes[i]);
+ }
+ Rule.sortNodesAndScores(&nodes, &scores);
+
+ // Iterate through them starting with the best and stopping when we reach
+ // one that isn't good enough.
+ for(int i = 0; i < referenceNode.NumChildren(); i++) {
+ if(Rule.Rescore(queryIndex, nodes[i], scores[i]) != DBL_MAX)
+ Traverse(queryIndex, nodes[i]);
+ else {
+ numPrunes += referenceNode.NumChildren - i;
+ return;
+ }
+ }
+ // We only get here if we couldn't prune any of them.
+ return;
}
}; // namespace tree
More information about the mlpack-git
mailing list