Index: /branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs
===================================================================
--- /branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs	(revision 12619)
+++ /branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/GradientBoostedTreesAlgorithm.cs	(revision 12620)
@@ -186,5 +186,5 @@
 
       // init
-      var problemData = Problem.ProblemData;
+      var problemData = (IRegressionProblemData)Problem.ProblemData.Clone();
       var lossFunction = ApplicationManager.Manager.GetInstances<ILossFunction>()
         .Single(l => l.ToString() == LossFunctionParameter.Value.Value);
@@ -245,5 +245,5 @@
         } else {
           // otherwise we produce a regression solution
-          Results.Add(new Result("Solution", new RegressionSolution(state.GetModel(), (IRegressionProblemData)problemData.Clone())));
+          Results.Add(new Result("Solution", new RegressionSolution(state.GetModel(), problemData)));
         }
       }
Index: /branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs
===================================================================
--- /branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs	(revision 12619)
+++ /branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeBuilder.cs	(revision 12620)
@@ -22,4 +22,5 @@
 
 using System;
+using System.Collections;
 using System.Collections.Generic;
 using System.Diagnostics;
@@ -53,5 +54,5 @@
     private readonly int[][] sortedIdx; // random selection from sortedIdxAll (for r < 1.0)
 
-
+    private int calls = 0;
 
     // helper arrays which are allocated to maximal necessary size only once in the ctor
@@ -64,5 +65,5 @@
 
     private class Partition {
-      public int TreeNodeIdx { get; set; }
+      public int ParentNodeIdx { get; set; }
       public int Depth { get; set; }
       public int StartIdx { get; set; }
@@ -70,5 +71,5 @@
       public bool Left { get; set; }
     }
-    private readonly IList<Partition> queue;
+    private readonly SortedList<double, Partition> queue;
 
     // prepare and allocate buffer variables in ctor
@@ -94,5 +95,5 @@
       outx = new double[rows];
       outSortedIdx = new int[rows];
-      queue = new List<Partition>();
+      queue = new SortedList<double, Partition>();
 
       x = new double[nCols][];
@@ -179,5 +180,5 @@
 
       // start and end idx are inclusive
-      queue.Add(new Partition() { TreeNodeIdx = -1, Depth = maxDepth, StartIdx = 0, EndIndex = effectiveRows - 1 });
+      queue.Add(calls++, new Partition() { ParentNodeIdx = -1, Depth = maxDepth, StartIdx = 0, EndIndex = effectiveRows - 1 });
       CreateRegressionTreeForIdx(lineSearch);
 
@@ -187,5 +188,5 @@
     private void CreateRegressionTreeForIdx(LineSearchFunc lineSearch) {
       while (queue.Any()) {
-        var f = queue[0]; // actually a stack
+        var f = queue.First().Value; // actually a stack
         queue.RemoveAt(0);
 
@@ -204,8 +205,8 @@
         if (depth <= 1 || endIdx - startIdx == 0 || !FindBestVariableAndThreshold(startIdx, endIdx, out threshold, out bestVariableName)) {
           CreateLeafNode(startIdx, endIdx, lineSearch);
-          if (f.TreeNodeIdx >= 0) if (f.Left) {
-              tree[f.TreeNodeIdx].leftIdx = curTreeNodeIdx;
+          if (f.ParentNodeIdx >= 0) if (f.Left) {
+              tree[f.ParentNodeIdx].leftIdx = curTreeNodeIdx;
             } else {
-              tree[f.TreeNodeIdx].rightIdx = curTreeNodeIdx;
+              tree[f.ParentNodeIdx].rightIdx = curTreeNodeIdx;
             }
           curTreeNodeIdx++;
@@ -215,8 +216,8 @@
 
           // connect to parent tree
-          if (f.TreeNodeIdx >= 0) if (f.Left) {
-              tree[f.TreeNodeIdx].leftIdx = curTreeNodeIdx;
+          if (f.ParentNodeIdx >= 0) if (f.Left) {
+              tree[f.ParentNodeIdx].leftIdx = curTreeNodeIdx;
             } else {
-              tree[f.TreeNodeIdx].rightIdx = curTreeNodeIdx;
+              tree[f.ParentNodeIdx].rightIdx = curTreeNodeIdx;
             }
 
@@ -224,6 +225,6 @@
           Debug.Assert(startIdx <= splitIdx);
 
-          queue.Insert(0, new Partition() { TreeNodeIdx = curTreeNodeIdx, Left = false, Depth = depth - 1, StartIdx = splitIdx + 1, EndIndex = endIdx });
-          queue.Insert(0, new Partition() { TreeNodeIdx = curTreeNodeIdx, Left = true, Depth = depth - 1, StartIdx = startIdx, EndIndex = splitIdx }); // left part before right part (stack organization)
+          queue.Add(calls++, new Partition() { ParentNodeIdx = curTreeNodeIdx, Left = true, Depth = depth - 1, StartIdx = startIdx, EndIndex = splitIdx }); // left part before right part (stack organization)
+          queue.Add(calls++, new Partition() { ParentNodeIdx = curTreeNodeIdx, Left = false, Depth = depth - 1, StartIdx = splitIdx + 1, EndIndex = endIdx });
           curTreeNodeIdx++;
 
@@ -318,5 +319,5 @@
       }
 
-      double bestImprovement = 0.0;
+      double bestImprovement = 1.0 / rows * sumY * sumY;
       double bestThreshold = double.PositiveInfinity;
       bestVar = RegressionTreeModel.TreeNode.NO_VARIABLE;
@@ -384,5 +385,5 @@
       double nr = rows;
 
-      bestImprovement = 0.0;
+      bestImprovement = 1.0 / rows * sumY * sumY;
       bestThreshold = double.NegativeInfinity;
       // for all thresholds
@@ -398,6 +399,21 @@
 
         if (x[i] < x[i + 1]) { // don't try to split when two elements are equal
+
+          // goal is to find the split with leading to minimal total variance of left and right parts
+          // without partitioning the variance is var(y) = E(y²) - E(y)²  
+          //    = 1/n * sum(y²) - (1/n * sum(y))²
+          //      -------------
+          // if we split into right and left part the overall variance is the weigthed combination nl/n * var(y_l) + nr/n * var(y_r)  
+          //    = nl/n * (1/nl * sum(y_l²) - (1/nl * sum(y_l))²) + nr/n * (1/nr * sum(y_r²) - (1/nr * sum(y_r))²)
+          //    = 1/n * sum(y_l²) - 1/nl * 1/n * sum(y_l)² + 1/n * sum(y_r²) - 1/nr * 1/n * sum(y_r)²
+          //    = 1/n * (sum(y_l²) + sum(y_r²)) - 1/n * (sum(y_l)² / nl + sum(y_r)² / nr)
+          //    = 1/n * sum(y²) - 1/n * (sum(y_l)² / nl + sum(y_r)² / nr)
+          //      -------------
+          //       not changed by split (and the same for total variance without partitioning)
+          //
+          //   therefore we need to find the maximum value (sum(y_l)² / nl + sum(y_r)² / nr) (ignoring the factor 1/n)
+          //   and this value must be larger than 1/n * sum(y)² to be an improvement over no split 
+
           double curQuality = sl * sl / nl + sr * sr / nr;
-          // curQuality = nl*nr / (nl+nr) * Sqr(sl / nl - sr / nr) // greedy function approximation page 12 eqn (35)
 
           if (curQuality > bestImprovement) {
Index: /branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/Test.cs
===================================================================
--- /branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/Test.cs	(revision 12620)
+++ /branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/Test.cs	(revision 12620)
@@ -0,0 +1,181 @@
+﻿using System;
+using System.Collections;
+using System.Globalization;
+using System.Linq;
+using System.Runtime.CompilerServices;
+using HeuristicLab.Problems.DataAnalysis;
+using HeuristicLab.Random;
+using Microsoft.VisualStudio.TestTools.UnitTesting;
+
+namespace HeuristicLab.Algorithms.DataAnalysis.GradientBoostedTrees {
+  [TestClass()]
+  public class Test {
+    [TestMethod]
+    [TestCategory("Algorithms.DataAnalysis")]
+    [TestProperty("Time", "short")]
+    public void DecisionTreeTest() {
+      {
+        var xy = new double[,]
+        {
+          {1, 20, 0},
+          {1, 20, 0},
+          {2, 10, 0},
+          {2, 10, 0},
+        };
+        var allVariables = new string[] { "y", "x1", "x2" };
+
+        // x1 <= 15 -> 1 
+        // x1 >  15 -> 2
+        BuildTree(xy, allVariables, 10);
+      }
+
+
+      {
+        var xy = new double[,]
+        {
+          {1, 20,  1},
+          {1, 20, -1},
+          {2, 10, -1},
+          {2, 10, 1},
+        };
+        var allVariables = new string[] { "y", "x1", "x2" };
+
+        // ignore irrelevant variables
+        // x1 <= 15 -> 1 
+        // x1 >  15 -> 2
+        BuildTree(xy, allVariables, 10);
+      }
+
+      {
+        // split must be by x1 first 
+        var xy = new double[,]
+        {
+          {1, 20,  1},
+          {2, 20, -1},
+          {3, 10, -1},
+          {4, 10, 1},
+        };
+
+        var allVariables = new string[] { "y", "x1", "x2" };
+
+        // x1 <= 15 AND x2 <= 0 -> 3 
+        // x1 <= 15 AND x2 >  0 -> 4 
+        // x1 >  15 AND x2 <= 0 -> 1
+        // x1 >  15 AND x2 >  0 -> 2
+        BuildTree(xy, allVariables, 10);
+      }
+
+      {
+        // averaging ys
+        var xy = new double[,]
+        {
+          {0.5, 20,  1},
+          {1.5, 20,  1},
+          {1.5, 20, -1},
+          {2.5, 20, -1},
+          {2.5, 10, -1},
+          {3.5, 10, -1},
+          {3.5, 10, 1},
+          {4.5, 10, 1},
+        };
+
+        var allVariables = new string[] { "y", "x1", "x2" };
+
+        // x1 <= 15 AND x2 <= 0 -> 3 
+        // x1 <= 15 AND x2 >  0 -> 4 
+        // x1 >  15 AND x2 <= 0 -> 1
+        // x1 >  15 AND x2 >  0 -> 2
+        BuildTree(xy, allVariables, 10);
+      }
+
+
+      {
+        // diagonal split (no split possible)
+        var xy = new double[,]
+        {
+          {10, 1, 1},
+          {1, 1, 2},
+          {1, 2, 1},
+          {10, 2, 2},
+        };
+
+        var allVariables = new string[] { "y", "x1", "x2" };
+
+        // split cannot be found
+        BuildTree(xy, allVariables, 3);
+      }
+      {
+        // almost diagonal split 
+        var xy = new double[,]
+        {
+          {10, 1, 1},
+          {1, 1, 2},
+          {1, 2, 1},
+          {10.1, 2, 2},
+        };
+
+        var allVariables = new string[] { "y", "x1", "x2" };
+        // x1 <= 1.5 AND x2 <= 1.5 -> 10 
+        // x1 <= 1.5 AND x2 >  1.5 -> 1 
+        // x1 >  1.5 AND x2 <= 1.5 -> 1
+        // x1 >  1.5 AND x2 >  1.5 -> 10.1
+        BuildTree(xy, allVariables, 3);
+      }
+      {
+        // unbalanced split
+        var xy = new double[,]
+        {
+          {-1, 1, 1},
+          {-1, 1, 2},
+          {0.9, 2, 1},
+          {1.1, 2, 2},
+        };
+
+        var allVariables = new string[] { "y", "x1", "x2" };
+        // x1 <= 1.5 -> -1.0 
+        // x1 >  1.5 AND x2 <= 1.5 -> 0.9
+        // x1 >  1.5 AND x2 >  1.5 -> 1.1
+        BuildTree(xy, allVariables, 3);
+      }
+
+    }
+
+    private void BuildTree(double[,] xy, string[] allVariables, int maxDepth) {
+      int nRows = xy.GetLength(0);
+      var allowedInputs = allVariables.Skip(1);
+      var dataset = new Dataset(allVariables, xy);
+      var problemData = new RegressionProblemData(dataset, allowedInputs, allVariables.First());
+      problemData.TrainingPartition.Start = 0;
+      problemData.TrainingPartition.End = nRows;
+      problemData.TestPartition.Start = nRows;
+      problemData.TestPartition.End = nRows;
+      var rand = new MersenneTwister(31415);
+      var builder = new RegressionTreeBuilder(problemData, rand);
+      var model = (GradientBoostedTreesModel)builder.CreateRegressionTree(maxDepth, 1, 1); // maximal depth and use all rows and cols
+      var constM = model.Models.First() as ConstantRegressionModel;
+      var treeM = model.Models.Skip(1).First() as RegressionTreeModel;
+      WriteTree(treeM.tree, 0, "", constM.Constant);
+      Console.WriteLine();
+    }
+
+    private void WriteTree(RegressionTreeModel.TreeNode[] tree, int idx, string partialRule, double offset) {
+      var n = tree[idx];
+      if (n.varName == RegressionTreeModel.TreeNode.NO_VARIABLE) {
+        Console.WriteLine("{0} -> {1:F}", partialRule, n.val + offset);
+      } else {
+        WriteTree(tree, n.leftIdx,
+          string.Format(CultureInfo.InvariantCulture, "{0}{1}{2} <= {3:F}",
+          partialRule,
+          string.IsNullOrEmpty(partialRule) ? "" : " and ",
+          n.varName,
+          n.val), offset);
+        WriteTree(tree, n.rightIdx,
+          string.Format(CultureInfo.InvariantCulture, "{0}{1}{2} >  {3:F}",
+          partialRule,
+          string.IsNullOrEmpty(partialRule) ? "" : " and ",
+          n.varName,
+          n.val), offset);
+      }
+    }
+  }
+}
Index: /branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis-3.4.csproj
===================================================================
--- /branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis-3.4.csproj	(revision 12619)
+++ /branches/GBT-trunkintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/HeuristicLab.Algorithms.DataAnalysis-3.4.csproj	(revision 12620)
@@ -199,4 +199,5 @@
       <Private>False</Private>
     </Reference>
+    <Reference Include="Microsoft.VisualStudio.QualityTools.UnitTestFramework, Version=10.1.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=MSIL" />
     <Reference Include="System" />
     <Reference Include="System.Core">
@@ -289,4 +290,5 @@
     <Compile Include="GradientBoostedTrees\RegressionTreeBuilder.cs" />
     <Compile Include="GradientBoostedTrees\RegressionTreeModel.cs" />
+    <Compile Include="GradientBoostedTrees\Test.cs" />
     <Compile Include="Interfaces\IGaussianProcessClassificationModelCreator.cs" />
     <Compile Include="Interfaces\IGaussianProcessRegressionModelCreator.cs" />
