Changeset 12590 for branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs

Timestamp:

07/04/15 16:03:36 (9 years ago)

Author:

gkronber

Message:

#2261: preparations for trunk integration (adapt to current trunk version, add license headers, add comments, improve code quality)

File:

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

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

@@ -1 @@
-using System;
+#region License Information
+/* HeuristicLab
+ * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * and the BEACON Center for the Study of Evolution in Action.
+ * 
+ * This file is part of HeuristicLab.
+ *
+ * HeuristicLab is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * HeuristicLab is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
+ */
+#endregion
+
+using System;
 using System.Collections.Generic;
 using System.Diagnostics;
 using System.Diagnostics.Contracts;
 using System.Linq;
-using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Problems.DataAnalysis;
 
-namespace GradientBoostedTrees {
+namespace HeuristicLab.Algorithms.DataAnalysis {
+  // This class implements a greedy decision tree learner which selects splits with the maximum reduction in sum of squared errors.
+  // The tree builder also tracks variable relevance metrics based on the splits and improvement after the split.
+  // The implementation is tuned for gradient boosting where multiple trees have to be calculated for the same training data 
+  // each time with a different target vector. Vectors of idx to allow iteration of intput variables in sorted order are
+  // pre-calculated so that optimal thresholds for splits can be calculated in O(n) for each input variable.
+  // After each split the row idx are partitioned in a left an right part.
   public class RegressionTreeBuilder {
     private readonly IRandom random;
@@ -14 +41 @@
 
     private readonly int nCols;
-    private readonly double[][] x; // all training data (original order from problemData)
-    private double[] y; // training labels (original order from problemData)
+    private readonly double[][] x; // all training data (original order from problemData), x is constant
+    private double[] y; // training labels (original order from problemData), y can be changed
 
     private Dictionary<string, double> sumImprovements; // for variable relevance calculation
@@ -76 +103 @@
     }
 
+    // simple API produces a single regression tree optimizing sum of squared errors
+    // this can be used if only a simple regression tree should be produced
+    // for a set of trees use the method CreateRegressionTreeForGradientBoosting below
+    //
     // r and m work in the same way as for alglib random forest
     // r is fraction of rows to use for training
@@ -92 +123 @@
     }
 
-    // specific interface that allows to specify the target labels and the training rows which is necessary when this functionality is called by the gradient boosting routine
+    // specific interface that allows to specify the target labels and the training rows which is necessary when for gradient boosted trees
     public IRegressionModel CreateRegressionTreeForGradientBoosting(double[] y, int maxDepth, int[] idx, LineSearchFunc lineSearch, double r = 0.5, double m = 0.5) {
       Contract.Assert(maxDepth > 0);
@@ -111 +142 @@
       HeuristicLab.Random.ListExtensions.ShuffleInPlace(allowedVariables, random);
 
+      // only select a part of the rows and columns randomly
       effectiveRows = (int)Math.Ceiling(nRows * r);
       effectiveVars = (int)Math.Ceiling(nCols * m);
 
+      // the which array is used for partining row idxs 
       Array.Clear(which, 0, which.Length);
 
       // mark selected rows
       for (int row = 0; row < effectiveRows; row++) {
-        which[idx[row]] = 1;
+        which[idx[row]] = 1; // we use the which vector as a temporary variable here
         internalIdx[row] = idx[row];
       }
@@ -126 +159 @@
         for (int row = 0; row < nRows; row++) {
           if (which[sortedIdxAll[col][row]] > 0) {
-            Trace.Assert(i < effectiveRows);
+            Debug.Assert(i < effectiveRows);
             sortedIdx[col][i] = sortedIdxAll[col][row];
             i++;
@@ -135 +168 @@
       // 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.tree = new RegressionTreeModel.TreeNode[numNodes];
       this.curTreeNodeIdx = 0;
 
@@ -144 +176 @@
     }
 
+    // recursive routine for building the tree for the row idx stored in internalIdx between startIdx and endIdx
+    // the lineSearch function calculates the optimal prediction value for tree leaf nodes 
+    // (in the case of squared errors it is the average of target values for the rows represented by the node)
     // startIdx and endIdx are inclusive
     private void CreateRegressionTreeForIdx(int maxDepth, int startIdx, int endIdx, LineSearchFunc lineSearch) {
@@ -214 +249 @@
             else if (which[internalIdx[j]] > 0) j--;
             else {
-              Trace.Assert(which[internalIdx[i]] > 0);
-              Trace.Assert(which[internalIdx[j]] < 0);
+              Debug.Assert(which[internalIdx[i]] > 0);
+              Debug.Assert(which[internalIdx[j]] < 0);
               // swap
               int tmp = internalIdx[i];
@@ -283 +318 @@
 
       threshold = bestThreshold;
-
-      // Contract.Assert(bestImprovement > 0);
-      // Contract.Assert(bestImprovement < double.PositiveInfinity);
-      // Contract.Assert(bestVar != string.Empty);
-      // Contract.Assert(allowedVariables.Contains(bestVar));
     }
 
@@ -351 +381 @@
 
     public IEnumerable<KeyValuePair<string, double>> GetVariableRelevance() {
+      // values are scaled: the most important variable has relevance = 100
       double scaling = 100 / sumImprovements.Max(t => t.Value);
       return