Changeset 14345 for trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4

Timestamp:

10/21/16 17:59:36 (8 years ago)

Author:

gkronber

Message:

#2690: implemented methods to generate symbolic expression tree solutions for decision tree models (random forest and gradient boosted) as well as views which make it possible to inspect each of the individual trees in a GBT and RF solution

Location:

trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4

Files:

• GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs (modified) (1 diff)
• GradientBoostedTrees/GradientBoostedTreesSolution.cs (modified) (1 diff)
• GradientBoostedTrees/RegressionTreeModel.cs (modified) (2 diffs)
• Interfaces/IRandomForestClassificationSolution.cs (modified) (1 diff)
• Interfaces/IRandomForestModel.cs (modified) (2 diffs)
• Interfaces/IRandomForestRegressionSolution.cs (modified) (2 diffs)
• RandomForest/RandomForestClassificationSolution.cs (modified) (1 diff)
• RandomForest/RandomForestModel.cs (modified) (4 diffs)
• RandomForest/RandomForestRegressionSolution.cs (modified) (2 diffs)

trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs

@@ -269 +269 @@
         } else {
           // otherwise we produce a regression solution
-          Results.Add(new Result("Solution", new RegressionSolution(model, problemData)));
+          Results.Add(new Result("Solution", new GradientBoostedTreesSolution(model, problemData)));
         }
       }

trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesSolution.cs

@@ -20 +20 @@
 #endregion
 
-using System.Collections.Generic;
-using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;

trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeModel.cs

@@ -28 +28 @@
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.DataAnalysis;
+using HeuristicLab.Problems.DataAnalysis.Symbolic;
+using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
 
 namespace HeuristicLab.Algorithms.DataAnalysis {
@@ -210 +213 @@
     }
 
+    /// <summary>
+    /// Transforms the tree model to a symbolic regression solution
+    /// </summary>
+    /// <param name="problemData"></param>
+    /// <returns>A new symbolic regression solution which matches the tree model</returns>
+    public ISymbolicRegressionSolution CreateSymbolicRegressionSolution(IRegressionProblemData problemData) {
+      var rootSy = new ProgramRootSymbol();
+      var startSy = new StartSymbol();
+      var varCondSy = new VariableCondition() { IgnoreSlope = true };
+      var constSy = new Constant();
+
+      var startNode = startSy.CreateTreeNode();
+      startNode.AddSubtree(CreateSymbolicRegressionTreeRecursive(tree, 0, varCondSy, constSy));
+      var rootNode = rootSy.CreateTreeNode();
+      rootNode.AddSubtree(startNode);
+      var model = new SymbolicRegressionModel(TargetVariable, new SymbolicExpressionTree(rootNode), new SymbolicDataAnalysisExpressionTreeLinearInterpreter());
+      return model.CreateRegressionSolution(problemData);
+    }
+
+    private ISymbolicExpressionTreeNode CreateSymbolicRegressionTreeRecursive(TreeNode[] treeNodes, int nodeIdx, VariableCondition varCondSy, Constant constSy) {
+      var curNode = treeNodes[nodeIdx];
+      if (curNode.VarName == TreeNode.NO_VARIABLE) {
+        var node = (ConstantTreeNode)constSy.CreateTreeNode();
+        node.Value = curNode.Val;
+        return node;
+      } else {
+        var node = (VariableConditionTreeNode)varCondSy.CreateTreeNode();
+        node.VariableName = curNode.VarName;
+        node.Threshold = curNode.Val;
+
+        var left = CreateSymbolicRegressionTreeRecursive(treeNodes, curNode.LeftIdx, varCondSy, constSy);
+        var right = CreateSymbolicRegressionTreeRecursive(treeNodes, curNode.RightIdx, varCondSy, constSy);
+        node.AddSubtree(left);
+        node.AddSubtree(right);
+        return node;
+      }
+    }
+
+
     private string TreeToString(int idx, string part) {
       var n = tree[idx];

trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/Interfaces/IRandomForestClassificationSolution.cs

@@ -30 +30 @@
   public interface IRandomForestClassificationSolution : IClassificationSolution {
     new IRandomForestModel Model { get; }
+    int NumberOfTrees { get; }
   }
 }

trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/Interfaces/IRandomForestModel.cs

@@ -20 +20 @@
 #endregion
 
-using HeuristicLab.Optimization;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Problems.DataAnalysis;
-using HeuristicLab.Core;
-using System.Collections.Generic;
+
 
 namespace HeuristicLab.Algorithms.DataAnalysis {
@@ -30 +29 @@
   /// </summary>
   public interface IRandomForestModel : IConfidenceRegressionModel, IClassificationModel {
+    int NumberOfTrees { get; }
+    ISymbolicExpressionTree ExtractTree(int treeIdx); // returns a specific tree from the random forest as a ISymbolicRegressionModel
   }
 }

trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/Interfaces/IRandomForestRegressionSolution.cs

@@ -20 +20 @@
 #endregion
 
-using HeuristicLab.Optimization;
 using HeuristicLab.Problems.DataAnalysis;
-using HeuristicLab.Core;
+using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
 
 namespace HeuristicLab.Algorithms.DataAnalysis {
@@ -30 +29 @@
   public interface IRandomForestRegressionSolution : IConfidenceRegressionSolution {
     new IRandomForestModel Model { get; }
+    int NumberOfTrees { get; }
   }
 }

trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/RandomForest/RandomForestClassificationSolution.cs

@@ -38 +38 @@
     }
 
+    public int NumberOfTrees {
+      get { return Model.NumberOfTrees; }
+    }
+
     [StorableConstructor]
     private RandomForestClassificationSolution(bool deserializing) : base(deserializing) { }

trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/RandomForest/RandomForestModel.cs

@@ -25 +25 @@
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.DataAnalysis;
+using HeuristicLab.Problems.DataAnalysis.Symbolic;
 
 namespace HeuristicLab.Algorithms.DataAnalysis {
@@ -49 +51 @@
     }
 
+    public int NumberOfTrees {
+      get { return nTrees; }
+    }
 
     // instead of storing the data of the model itself
@@ -64 +69 @@
     [Storable]
     private double m;
-
 
     [StorableConstructor]
@@ -197 +201 @@
     }
 
+    public ISymbolicExpressionTree ExtractTree(int treeIdx) {
+      // hoping that the internal representation of alglib is stable
+
+      // TREE FORMAT
+      // W[Offs]      -   size of sub-array (for the tree)
+      //     node info:
+      // W[K+0]       -   variable number        (-1 for leaf mode)
+      // W[K+1]       -   threshold              (class/value for leaf node)
+      // W[K+2]       -   ">=" branch index      (absent for leaf node)
+
+      // skip irrelevant trees
+      int offset = 0;
+      for (int i = 0; i < treeIdx - 1; i++) {
+        offset = offset + (int)Math.Round(randomForest.innerobj.trees[offset]);
+      }
+
+      var constSy = new Constant();
+      var varCondSy = new VariableCondition() { IgnoreSlope = true };
+
+      var node = CreateRegressionTreeRec(randomForest.innerobj.trees, offset, offset + 1, constSy, varCondSy);
+
+      var startNode = new StartSymbol().CreateTreeNode();
+      startNode.AddSubtree(node);
+      var root = new ProgramRootSymbol().CreateTreeNode();
+      root.AddSubtree(startNode);
+      return new SymbolicExpressionTree(root);
+    }
+
+    private ISymbolicExpressionTreeNode CreateRegressionTreeRec(double[] trees, int offset, int k, Constant constSy, VariableCondition varCondSy) {
+
+      // alglib source for evaluation of one tree (dfprocessinternal)
+      // offs = 0
+      //
+      // Set pointer to the root
+      //
+      // k = offs + 1;
+      // 
+      // //
+      // // Navigate through the tree
+      // //
+      // while (true) {
+      //   if ((double)(df.trees[k]) == (double)(-1)) {
+      //     if (df.nclasses == 1) {
+      //       y[0] = y[0] + df.trees[k + 1];
+      //     } else {
+      //       idx = (int)Math.Round(df.trees[k + 1]);
+      //       y[idx] = y[idx] + 1;
+      //     }
+      //     break;
+      //   }
+      //   if ((double)(x[(int)Math.Round(df.trees[k])]) < (double)(df.trees[k + 1])) {
+      //     k = k + innernodewidth;
+      //   } else {
+      //     k = offs + (int)Math.Round(df.trees[k + 2]);
+      //   }
+      // }
+
+      if ((double)(trees[k]) == (double)(-1)) {
+        var constNode = (ConstantTreeNode)constSy.CreateTreeNode();
+        constNode.Value = trees[k + 1];
+        return constNode;
+      } else {
+        var condNode = (VariableConditionTreeNode)varCondSy.CreateTreeNode();
+        condNode.VariableName = AllowedInputVariables[(int)Math.Round(trees[k])];
+        condNode.Threshold = trees[k + 1];
+        condNode.Slope = double.PositiveInfinity;
+
+        var left = CreateRegressionTreeRec(trees, offset, k + 3, constSy, varCondSy);
+        var right = CreateRegressionTreeRec(trees, offset, offset + (int)Math.Round(trees[k + 2]), constSy, varCondSy);
+
+        condNode.AddSubtree(left); // not 100% correct because interpreter uses: if(x <= thres) left() else right() and RF uses if(x < thres) left() else right() (see above)
+        condNode.AddSubtree(right);
+        return condNode;
+      }
+    }
+
 
     public IRegressionSolution CreateRegressionSolution(IRegressionProblemData problemData) {

trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/RandomForest/RandomForestRegressionSolution.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.Problems.DataAnalysis;
+using HeuristicLab.Problems.DataAnalysis.Symbolic.Regression;
 
 namespace HeuristicLab.Algorithms.DataAnalysis {
@@ -36 +38 @@
       get { return (IRandomForestModel)base.Model; }
       set { base.Model = value; }
+    }
+
+    public int NumberOfTrees {
+      get { return Model.NumberOfTrees; }
     }