source: branches/M5Regression/HeuristicLab.Algorithms.DataAnalysis/3.4/M5Regression/Pruning/BottomUpPruningBase.cs @ 15614

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * 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.Collections.Generic;
using System.Linq;
using System.Threading;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Problems.DataAnalysis;

namespace HeuristicLab.Algorithms.DataAnalysis {
  public abstract class BottomUpPruningBase : ParameterizedNamedItem, IPruning {
    private const string PruningStrengthParameterName = "PruningStrength";

    public IFixedValueParameter<DoubleValue> PruningStrengthParameter {
      get { return (IFixedValueParameter<DoubleValue>)Parameters[PruningStrengthParameterName]; }
    }

    public double PruningStrength {
      get { return PruningStrengthParameter.Value.Value; }
    }

    #region Constructors & Cloning
    [StorableConstructor]
    protected BottomUpPruningBase(bool deserializing) : base(deserializing) { }
    protected BottomUpPruningBase(BottomUpPruningBase original, Cloner cloner) : base(original, cloner) { }
    protected BottomUpPruningBase() {
      Parameters.Add(new FixedValueParameter<DoubleValue>(PruningStrengthParameterName, "The strength of the pruning. Higher values force the algorithm to create simpler models", new DoubleValue(4.0)));
    }
    #endregion

    public abstract ILeafModel PruningLeafModel(ILeafModel leafModel);

    #region IPruning
    public int MinLeafSize(IRegressionProblemData pd, ILeafModel leafModel) {
      return PruningLeafModel(leafModel).MinLeafSize(pd);
    }
    #endregion

    internal void Prune(M5TreeModel treeModel, IReadOnlyList<int> trainingRows, IReadOnlyList<int> pruningRows, M5Parameters m5Params, CancellationToken cancellationToken) {
      var globalStdDev = m5Params.Data.GetDoubleValues(m5Params.TargetVariable, trainingRows).StandardDeviationPop();

      Prune(treeModel.Root, trainingRows, pruningRows, m5Params, new Dictionary<M5NodeModel, int>(), new Dictionary<M5NodeModel, int>(), cancellationToken, globalStdDev);
    }

    private bool Prune(M5NodeModel node, IReadOnlyList<int> trainingRows, IReadOnlyList<int> pruningRows, M5Parameters m5Params,
      Dictionary<M5NodeModel, int> modelComplexities, Dictionary<M5NodeModel, int> nodeComplexities,
      CancellationToken cancellationToken, double globalStdDev) {
      //build pruning model
      int numModelParams;
      var pruningModel = M5StaticUtilities.BuildModel(trainingRows, m5Params, PruningLeafModel(m5Params.LeafModel), cancellationToken, out numModelParams);
      node.Model = pruningModel;
      modelComplexities.Add(node, numModelParams);

      if (node.IsLeaf) {
        nodeComplexities.Add(node, numModelParams);
        return true;
      }

      //split training & pruning data
      IReadOnlyList<int> leftTest, rightTest;
      M5StaticUtilities.SplitRows(pruningRows, m5Params.Data, node.SplitAttribute, node.SplitValue, out leftTest, out rightTest);
      IReadOnlyList<int> leftTraining, rightTraining;
      M5StaticUtilities.SplitRows(trainingRows, m5Params.Data, node.SplitAttribute, node.SplitValue, out leftTraining, out rightTraining);

      //prune children frist
      var lpruned = Prune(node.Left, leftTraining, leftTest, m5Params, modelComplexities, nodeComplexities, cancellationToken, globalStdDev);
      var rpruned = Prune(node.Right, rightTraining, rightTest, m5Params, modelComplexities, nodeComplexities, cancellationToken, globalStdDev);
      nodeComplexities.Add(node, nodeComplexities[node.Left] + nodeComplexities[node.Right] + 1);

      //TODO check if this reduces quality. It reduces training effort (consideraby for some pruningTypes)
      if (!lpruned && !rpruned) return false;

      //check if pruning will happen on this node
      if (!DecidePruneNode(node, m5Params, pruningRows, modelComplexities, nodeComplexities, globalStdDev)) return false;

      //convert to leafNode
      ((IntValue)m5Params.Results[M5TreeModel.NumCurrentLeafsResultName].Value).Value -= node.EnumerateNodes().Count(x => x.IsLeaf) - 1;

      //TODO chack wether removal is beneficial 
      nodeComplexities.Remove(node.Left);
      nodeComplexities.Remove(node.Right);
      modelComplexities.Remove(node.Left);
      modelComplexities.Remove(node.Right);

      node.ToLeaf();

      return true;
    }

    private bool DecidePruneNode(M5NodeModel node, M5Parameters m5Params, IReadOnlyCollection<int> testRows,
      IReadOnlyDictionary<M5NodeModel, int> modelComplexities, IReadOnlyDictionary<M5NodeModel, int> nodeComplexities,
      double globalStdDev) {
      if (testRows.Count == 0) return true;

      //create regressionProblemdata from pruning data 
      var vars = m5Params.AllowedInputVariables.Concat(new[] {m5Params.TargetVariable}).ToArray();
      var reducedData = new Dataset(vars, vars.Select(x => m5Params.Data.GetDoubleValues(x, testRows).ToList()));
      var pd = new RegressionProblemData(reducedData, m5Params.AllowedInputVariables, m5Params.TargetVariable);
      pd.TrainingPartition.Start = pd.TrainingPartition.End = pd.TestPartition.Start = 0;
      pd.TestPartition.End = reducedData.Rows;

      //evaluate combined sub nodes and pruning model
      var rmsModel = node.Model.CreateRegressionSolution(pd).TestRootMeanSquaredError;
      var rmsSubTree = node.CreateRegressionSolution(pd).TestRootMeanSquaredError;

      //weigh, compare and decide
      var adjustedRmsModel = rmsModel * PruningFactor(pd.Dataset.Rows, modelComplexities[node]);
      var adjustedRmsTree = rmsSubTree * PruningFactor(pd.Dataset.Rows, nodeComplexities[node.Left] + nodeComplexities[node.Right] + 1);
      return adjustedRmsModel <= adjustedRmsTree;
    }

    private double PruningFactor(int noInstances, int noParams) {
      return noInstances <= noParams ? 10.0 : (noInstances + PruningStrength * noParams) / (noInstances - PruningStrength * noParams);
    }
  }
}