[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