source: trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/GradientBoostedTrees/RegressionTreeModel.cs @ 12868

Last change on this file since 12868 was 12868, checked in by gkronber, 6 years ago

#2450: introduced surrogate for GBT-models which recalculates the actual model on demand to improve persistence of GBT solutions

File size: 6.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 * and the BEACON Center for the Study of Evolution in Action.
5 *
6 * This file is part of HeuristicLab.
7 *
8 * HeuristicLab is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * HeuristicLab is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
20 */
21#endregion
22
23using System;
24using System.Collections.Generic;
25using System.Globalization;
26using System.Linq;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
30using HeuristicLab.Problems.DataAnalysis;
31
32namespace HeuristicLab.Algorithms.DataAnalysis {
33  [StorableClass]
34  [Item("RegressionTreeModel", "Represents a decision tree for regression.")]
35  public sealed class RegressionTreeModel : NamedItem, IRegressionModel {
36
37    // trees are represented as a flat array   
38    internal struct TreeNode {
39      public readonly static string NO_VARIABLE = null;
40
41      public TreeNode(string varName, double val, int leftIdx = -1, int rightIdx = -1)
42        : this() {
43        VarName = varName;
44        Val = val;
45        LeftIdx = leftIdx;
46        RightIdx = rightIdx;
47      }
48
49      public string VarName { get; private set; } // name of the variable for splitting or NO_VARIABLE if terminal node
50      public double Val { get; private set; } // threshold
51      public int LeftIdx { get; private set; }
52      public int RightIdx { get; private set; }
53
54      internal IList<double> Data { get; set; } // only necessary to improve efficiency of evaluation
55
56      // necessary because the default implementation of GetHashCode for structs in .NET would only return the hashcode of val here
57      public override int GetHashCode() {
58        return LeftIdx ^ RightIdx ^ Val.GetHashCode();
59      }
60      // necessary because of GetHashCode override
61      public override bool Equals(object obj) {
62        if (obj is TreeNode) {
63          var other = (TreeNode)obj;
64          return Val.Equals(other.Val) &&
65            LeftIdx.Equals(other.LeftIdx) &&
66            RightIdx.Equals(other.RightIdx) &&
67            EqualStrings(VarName, other.VarName);
68        } else {
69          return false;
70        }
71      }
72
73      private bool EqualStrings(string a, string b) {
74        return (a == null && b == null) ||
75               (a != null && b != null && a.Equals(b));
76      }
77    }
78
79    // not storable!
80    private TreeNode[] tree;
81
82    [Storable]
83    // to prevent storing the references to data caches in nodes
84    // seemingly it is bad (performance-wise) to persist tuples (tuples are used as keys in a dictionary) TODO
85    private Tuple<string, double, int, int>[] SerializedTree {
86      get { return tree.Select(t => Tuple.Create(t.VarName, t.Val, t.LeftIdx, t.RightIdx)).ToArray(); }
87      set { this.tree = value.Select(t => new TreeNode(t.Item1, t.Item2, t.Item3, t.Item4)).ToArray(); }
88    }
89
90    [StorableConstructor]
91    private RegressionTreeModel(bool serializing) : base(serializing) { }
92    // cloning ctor
93    private RegressionTreeModel(RegressionTreeModel original, Cloner cloner)
94      : base(original, cloner) {
95      if (original.tree != null) {
96        this.tree = new TreeNode[original.tree.Length];
97        Array.Copy(original.tree, this.tree, this.tree.Length);
98      }
99    }
100
101    internal RegressionTreeModel(TreeNode[] tree)
102      : base("RegressionTreeModel", "Represents a decision tree for regression.") {
103      this.tree = tree;
104    }
105
106    private static double GetPredictionForRow(TreeNode[] t, int nodeIdx, int row) {
107      while (nodeIdx != -1) {
108        var node = t[nodeIdx];
109        if (node.VarName == TreeNode.NO_VARIABLE)
110          return node.Val;
111
112        if (node.Data[row] <= node.Val)
113          nodeIdx = node.LeftIdx;
114        else
115          nodeIdx = node.RightIdx;
116      }
117      throw new InvalidOperationException("Invalid tree in RegressionTreeModel");
118    }
119
120    public override IDeepCloneable Clone(Cloner cloner) {
121      return new RegressionTreeModel(this, cloner);
122    }
123
124    public IEnumerable<double> GetEstimatedValues(IDataset ds, IEnumerable<int> rows) {
125      // lookup columns for variableNames in one pass over the tree to speed up evaluation later on
126      for (int i = 0; i < tree.Length; i++) {
127        if (tree[i].VarName != TreeNode.NO_VARIABLE) {
128          tree[i].Data = ds.GetReadOnlyDoubleValues(tree[i].VarName);
129        }
130      }
131      return rows.Select(r => GetPredictionForRow(tree, 0, r));
132    }
133
134    public IRegressionSolution CreateRegressionSolution(IRegressionProblemData problemData) {
135      return new RegressionSolution(this, new RegressionProblemData(problemData));
136    }
137
138    // mainly for debugging
139    public override string ToString() {
140      return TreeToString(0, "");
141    }
142
143    private string TreeToString(int idx, string part) {
144      var n = tree[idx];
145      if (n.VarName == TreeNode.NO_VARIABLE) {
146        return string.Format(CultureInfo.InvariantCulture, "{0} -> {1:F}{2}", part, n.Val, Environment.NewLine);
147      } else {
148        return
149          TreeToString(n.LeftIdx, string.Format(CultureInfo.InvariantCulture, "{0}{1}{2} <= {3:F}", part, string.IsNullOrEmpty(part) ? "" : " and ", n.VarName, n.Val))
150        + TreeToString(n.RightIdx, string.Format(CultureInfo.InvariantCulture, "{0}{1}{2} >  {3:F}", part, string.IsNullOrEmpty(part) ? "" : " and ", n.VarName, n.Val));
151      }
152    }
153  }
154}
Note: See TracBrowser for help on using the repository browser.