Changeset 12372 for branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs

Timestamp:

05/01/15 18:30:56 (10 years ago)

Author:

gkronber

Message:

#2261: implemented prototype view for gradient boosted trees

File:

• branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs (modified) (5 diffs)

branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs

@@ -33 +33 @@
     private readonly double[] outx;
     private readonly int[] outSortedIdx;
+
+    private RegressionTreeModel.TreeNode[] tree; // tree is represented as a flat array of nodes
+    private int curTreeNodeIdx; // the index where the next tree node is stored
+
     private readonly IList<RegressionTreeModel.TreeNode> nodeQueue; //TODO
 
@@ -128 +132 @@
         }
       }
+
+      // prepare array for the tree nodes (a tree of maxDepth=1 has 1 node, a tree of maxDepth=d has 2^d - 1 nodes)      
+      int numNodes = (int)Math.Pow(2, maxDepth) - 1;
+      //this.tree = new RegressionTreeModel.TreeNode[numNodes];
+      this.tree = Enumerable.Range(0, numNodes).Select(_=>new RegressionTreeModel.TreeNode()).ToArray();
+      this.curTreeNodeIdx = 0;
+
       // start and end idx are inclusive
-      var tree = CreateRegressionTreeForIdx(maxDepth, 0, effectiveRows - 1, lineSearch);
+      CreateRegressionTreeForIdx(maxDepth, 0, effectiveRows - 1, lineSearch);
       return new RegressionTreeModel(tree);
     }
 
     // startIdx and endIdx are inclusive
-    private RegressionTreeModel.TreeNode CreateRegressionTreeForIdx(int maxDepth, int startIdx, int endIdx, LineSearchFunc lineSearch) {
+    private void CreateRegressionTreeForIdx(int maxDepth, int startIdx, int endIdx, LineSearchFunc lineSearch) {
       Contract.Assert(endIdx - startIdx >= 0);
       Contract.Assert(startIdx >= 0);
       Contract.Assert(endIdx < internalIdx.Length);
 
-      RegressionTreeModel.TreeNode t;
       // TODO: stop when y is constant
       // TODO: use priority queue of nodes to be expanded (sorted by improvement) instead of the recursion to maximum depth
       if (maxDepth <= 1 || endIdx - startIdx == 0) {
-        // max depth reached or only one element         
-        t = new RegressionTreeModel.TreeNode(RegressionTreeModel.TreeNode.NO_VARIABLE, lineSearch(internalIdx, startIdx, endIdx));
-        return t;
+        // max depth reached or only one element    
+        tree[curTreeNodeIdx].varName = RegressionTreeModel.TreeNode.NO_VARIABLE;
+        tree[curTreeNodeIdx].val = lineSearch(internalIdx, startIdx, endIdx);
+        curTreeNodeIdx++;
       } else {
         int i, j;
@@ -154 +165 @@
         // if bestVariableName is NO_VARIABLE then no split was possible anymore
         if (bestVariableName == RegressionTreeModel.TreeNode.NO_VARIABLE) {
-          return new RegressionTreeModel.TreeNode(RegressionTreeModel.TreeNode.NO_VARIABLE, lineSearch(internalIdx, startIdx, endIdx));
+          // max depth reached or only one element    
+          tree[curTreeNodeIdx].varName = RegressionTreeModel.TreeNode.NO_VARIABLE;
+          tree[curTreeNodeIdx].val = lineSearch(internalIdx, startIdx, endIdx);
+          curTreeNodeIdx++;
         } else {
 
@@ -214 +228 @@
           Debug.Assert(j <= endIdx);
 
-          t = new RegressionTreeModel.TreeNode(bestVariableName,
-            threshold,
-            CreateRegressionTreeForIdx(maxDepth - 1, startIdx, j, lineSearch),
-            CreateRegressionTreeForIdx(maxDepth - 1, i, endIdx, lineSearch));
-
-          return t;
+          var parentIdx = curTreeNodeIdx;
+          tree[parentIdx].varName = bestVariableName;
+          tree[parentIdx].val = threshold;
+          curTreeNodeIdx++;
+
+          // create left subtree
+          tree[parentIdx].leftIdx = curTreeNodeIdx;
+          CreateRegressionTreeForIdx(maxDepth - 1, startIdx, j, lineSearch);
+
+          // create right subtree
+          tree[parentIdx].rightIdx = curTreeNodeIdx;
+          CreateRegressionTreeForIdx(maxDepth - 1, i, endIdx, lineSearch);
         }
       }
@@ -272 +292 @@
     // assumption is that the Average(y) = 0
     private void UpdateVariableRelevance(string bestVar, double sumY, double bestImprovement, int rows) {
+      if (string.IsNullOrEmpty(bestVar)) return;
       // update variable relevance
       double err = sumY * sumY / rows;