Changeset 12372 for branches/GBT/HeuristicLab.Algorithms.DataAnalysis/3.4

Timestamp:

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

Author:

gkronber

Message:

#2261: implemented prototype view for gradient boosted trees

Location:

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

Files:

• GradientBoostedTreesModel.cs (modified) (2 diffs)
• RegressionTreeBuilder.cs (modified) (5 diffs)
• RegressionTreeModel.cs (modified) (4 diffs)

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

@@ -8 +8 @@
 
 namespace GradientBoostedTrees {
-  [Item("GradientBoostedTreesSolution", "")]
   [StorableClass]
+  [Item("Gradient boosted tree model", "")]
   public sealed class GradientBoostedTreesModel : NamedItem, IRegressionModel {
 
     [Storable]
     private readonly IList<IRegressionModel> models;
+    public IEnumerable<IRegressionModel> Models { get { return models; } }
+
     [Storable]
     private readonly IList<double> weights;
+    public IEnumerable<double> Weights { get { return weights; } }
 
     [StorableConstructor]
@@ -25 +28 @@
     }
     public GradientBoostedTreesModel(IEnumerable<IRegressionModel> models, IEnumerable<double> weights)
-      : base() {
+      : base("Gradient boosted tree model", string.Empty) {
       this.models = new List<IRegressionModel>(models);
       this.weights = new List<double>(weights);

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;

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

@@ -1 @@
-using System.Collections.Generic;
+using System;
+using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
@@ -12 +13 @@
   public class RegressionTreeModel : NamedItem, IRegressionModel {
 
+    // trees are represented as a flat array
+    // object-graph-travesal has problems if this is defined as a struct. TODO investigate...
     [StorableClass]
     public class TreeNode {
       public readonly static string NO_VARIABLE = string.Empty;
       [Storable]
-      public readonly string varName; // name of the variable for splitting or -1 if terminal node
+      public string varName; // name of the variable for splitting or -1 if terminal node
       [Storable]
-      public readonly double val; // threshold
+      public double val; // threshold
       [Storable]
-      public readonly TreeNode left;
+      public int leftIdx;
       [Storable]
-      public readonly TreeNode right;
+      public int rightIdx;
 
+      public TreeNode() {
+        varName = NO_VARIABLE;
+        leftIdx = -1;
+        rightIdx = -1;
+      }
       [StorableConstructor]
       private TreeNode(bool deserializing) { }
-
-      public TreeNode(string varName, double value, TreeNode left = null, TreeNode right = null) {
-        this.varName = varName;
-        this.val = value;
-        this.left = left;
-        this.right = right;
-      }
     }
 
     [Storable]
-    public readonly TreeNode tree;
+    public readonly TreeNode[] tree;
 
     [StorableConstructor]
@@ -43 +44 @@
     public RegressionTreeModel(RegressionTreeModel original, Cloner cloner)
       : base(original, cloner) {
-      this.tree = original.tree;
+      this.tree = original.tree; // shallow clone, tree must be readonly
     }
 
-    public RegressionTreeModel(TreeNode tree)
-      : base() {
-      this.name = ItemName;
-      this.description = ItemDescription;
-
+    public RegressionTreeModel(TreeNode[] tree)
+      : base("RegressionTreeModel", "Represents a decision tree for regression.") {
       this.tree = tree;
     }
 
-    private static double GetPredictionForRow(TreeNode t, Dataset ds, int row) {
-      if (t.varName == TreeNode.NO_VARIABLE)
-        return t.val;
-      else if (ds.GetDoubleValue(t.varName, row) <= t.val)
-        return GetPredictionForRow(t.left, ds, row);
+    private static double GetPredictionForRow(TreeNode[] t, int nodeIdx, Dataset ds, int row) {
+      var node = t[nodeIdx];
+      if (node.varName == TreeNode.NO_VARIABLE)
+        return node.val;
+      else if (ds.GetDoubleValue(node.varName, row) <= node.val)
+        return GetPredictionForRow(t, node.leftIdx, ds, row);
       else
-        return GetPredictionForRow(t.right, ds, row);
+        return GetPredictionForRow(t, node.rightIdx, ds, row);
     }
 
@@ -68 +67 @@
 
     public IEnumerable<double> GetEstimatedValues(Dataset ds, IEnumerable<int> rows) {
-      return rows.Select(r => GetPredictionForRow(tree, ds, r));
+      return rows.Select(r => GetPredictionForRow(tree, 0, ds, r));
     }