source: branches/2904_CalculateImpacts/3.4/Implementation/Classification/ClassificationSolutionVariableImpactsCalculator.cs @ 16036

#region License Information

/* HeuristicLab
 * Copyright (C) 2002-2018 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;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Random;

namespace HeuristicLab.Problems.DataAnalysis {
  [StorableClass]
  [Item("ClassificationSolution Impacts Calculator", "Calculation of the impacts of input variables for any classification solution")]
  public sealed class ClassificationSolutionVariableImpactsCalculator : ParameterizedNamedItem {
    #region Parameters/Properties
    public enum ReplacementMethodEnum {
      Median,
      Average,
      Shuffle,
      Noise
    }
    public enum FactorReplacementMethodEnum {
      Best,
      Mode,
      Shuffle
    }
    public enum DataPartitionEnum {
      Training,
      Test,
      All
    }

    private const string ReplacementParameterName = "Replacement Method";
    private const string FactorReplacementParameterName = "Factor Replacement Method";
    private const string DataPartitionParameterName = "DataPartition";

    public IFixedValueParameter<EnumValue<ReplacementMethodEnum>> ReplacementParameter {
      get { return (IFixedValueParameter<EnumValue<ReplacementMethodEnum>>)Parameters[ReplacementParameterName]; }
    }
    public IFixedValueParameter<EnumValue<FactorReplacementMethodEnum>> FactorReplacementParameter {
      get { return (IFixedValueParameter<EnumValue<FactorReplacementMethodEnum>>)Parameters[FactorReplacementParameterName]; }
    }
    public IFixedValueParameter<EnumValue<DataPartitionEnum>> DataPartitionParameter {
      get { return (IFixedValueParameter<EnumValue<DataPartitionEnum>>)Parameters[DataPartitionParameterName]; }
    }

    public ReplacementMethodEnum ReplacementMethod {
      get { return ReplacementParameter.Value.Value; }
      set { ReplacementParameter.Value.Value = value; }
    }
    public FactorReplacementMethodEnum FactorReplacementMethod {
      get { return FactorReplacementParameter.Value.Value; }
      set { FactorReplacementParameter.Value.Value = value; }
    }
    public DataPartitionEnum DataPartition {
      get { return DataPartitionParameter.Value.Value; }
      set { DataPartitionParameter.Value.Value = value; }
    }
    #endregion

    #region Ctor/Cloner
    [StorableConstructor]
    private ClassificationSolutionVariableImpactsCalculator(bool deserializing) : base(deserializing) { }
    private ClassificationSolutionVariableImpactsCalculator(ClassificationSolutionVariableImpactsCalculator original, Cloner cloner)
      : base(original, cloner) { }
    public ClassificationSolutionVariableImpactsCalculator()
      : base() {
      Parameters.Add(new FixedValueParameter<EnumValue<ReplacementMethodEnum>>(ReplacementParameterName, "The replacement method for variables during impact calculation.", new EnumValue<ReplacementMethodEnum>(ReplacementMethodEnum.Shuffle)));
      Parameters.Add(new FixedValueParameter<EnumValue<DataPartitionEnum>>(DataPartitionParameterName, "The data partition on which the impacts are calculated.", new EnumValue<DataPartitionEnum>(DataPartitionEnum.Training)));
    }

    public override IDeepCloneable Clone(Cloner cloner) {
      return new ClassificationSolutionVariableImpactsCalculator(this, cloner);
    }
    #endregion

    //mkommend: annoying name clash with static method, open to better naming suggestions
    public IEnumerable<Tuple<string, double>> Calculate(IClassificationSolution solution) {
      return CalculateImpacts(solution, ReplacementMethod, FactorReplacementMethod, DataPartition);
    }

    public static IEnumerable<Tuple<string, double>> CalculateImpacts(
      IClassificationSolution solution,
      ReplacementMethodEnum replacementMethod = ReplacementMethodEnum.Shuffle,
      FactorReplacementMethodEnum factorReplacementMethod = FactorReplacementMethodEnum.Best,
      DataPartitionEnum dataPartition = DataPartitionEnum.Training) {
      return CalculateImpacts(solution.Model, solution.ProblemData, solution.EstimatedClassValues, replacementMethod, factorReplacementMethod, dataPartition);
    }

    public static IEnumerable<Tuple<string, double>> CalculateImpacts(
      IClassificationModel model,
      IClassificationProblemData problemData,
      IEnumerable<double> estimatedValues,
      ReplacementMethodEnum replacementMethod = ReplacementMethodEnum.Shuffle,
      FactorReplacementMethodEnum factorReplacementMethod = FactorReplacementMethodEnum.Best,
      DataPartitionEnum dataPartition = DataPartitionEnum.Training) {
      IEnumerable<int> rows = GetPartitionRows(dataPartition, problemData);
      return CalculateImpacts(model, problemData, estimatedValues, rows, replacementMethod, factorReplacementMethod);
    }


    public static IEnumerable<Tuple<string, double>> CalculateImpacts(
     IClassificationModel model,
     IClassificationProblemData problemData,
     IEnumerable<double> estimatedClassValues,
     IEnumerable<int> rows,
     ReplacementMethodEnum replacementMethod = ReplacementMethodEnum.Shuffle,
     FactorReplacementMethodEnum factorReplacementMethod = FactorReplacementMethodEnum.Best) {
      //Calculate original quality-values (via calculator, default is Accuracy)
      OnlineCalculatorError error;
      IEnumerable<double> targetValuesPartition = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, rows);
      IEnumerable<double> estimatedValuesPartition = rows.Select(v => estimatedClassValues.ElementAt(v));
      var originalCalculatorValue = CalculateVariableImpact(targetValuesPartition, estimatedValuesPartition, out error);
      if (error != OnlineCalculatorError.None) throw new InvalidOperationException("Error during calculation.");

      var impacts = new Dictionary<string, double>();
      var inputvariables = new HashSet<string>(problemData.AllowedInputVariables.Union(model.VariablesUsedForPrediction));
      var allowedInputVariables = problemData.Dataset.VariableNames.Where(v => inputvariables.Contains(v)).ToList();
      var modifiableDataset = ((Dataset)(problemData.Dataset).Clone()).ToModifiable();

      foreach (var inputVariable in allowedInputVariables) {
        impacts[inputVariable] = CalculateImpact(inputVariable, model, modifiableDataset, rows, targetValuesPartition, originalCalculatorValue, replacementMethod, factorReplacementMethod);
      }

      return impacts.OrderByDescending(i => i.Value).Select(i => Tuple.Create(i.Key, i.Value));
    }


    public static double CalculateImpact(string variableName,
      IClassificationModel model,
      ModifiableDataset modifiableDataset,
      IEnumerable<int> rows,
      IEnumerable<double> targetValues,
      double originalValue,
      ReplacementMethodEnum replacementMethod = ReplacementMethodEnum.Shuffle,
      FactorReplacementMethodEnum factorReplacementMethod = FactorReplacementMethodEnum.Best) {
      double impact = 0;
      OnlineCalculatorError error;
      IRandom random;
      double replacementValue;
      IEnumerable<double> newEstimates = null;
      double newValue = 0;

      if (modifiableDataset.VariableHasType<double>(variableName)) {
        #region NumericalVariable
        var originalValues = modifiableDataset.GetReadOnlyDoubleValues(variableName).ToList();
        List<double> replacementValues;
        IRandom rand;

        switch (replacementMethod) {
          case ReplacementMethodEnum.Median:
            replacementValue = rows.Select(r => originalValues[r]).Median();
            replacementValues = Enumerable.Repeat(replacementValue, modifiableDataset.Rows).ToList();
            break;
          case ReplacementMethodEnum.Average:
            replacementValue = rows.Select(r => originalValues[r]).Average();
            replacementValues = Enumerable.Repeat(replacementValue, modifiableDataset.Rows).ToList();
            break;
          case ReplacementMethodEnum.Shuffle:
            // new var has same empirical distribution but the relation to y is broken
            rand = new FastRandom(31415);
            // prepare a complete column for the dataset
            replacementValues = Enumerable.Repeat(double.NaN, modifiableDataset.Rows).ToList();
            // shuffle only the selected rows
            var shuffledValues = rows.Select(r => originalValues[r]).Shuffle(rand).ToList();
            int i = 0;
            // update column values 
            foreach (var r in rows) {
              replacementValues[r] = shuffledValues[i++];
            }
            break;
          case ReplacementMethodEnum.Noise:
            var avg = rows.Select(r => originalValues[r]).Average();
            var stdDev = rows.Select(r => originalValues[r]).StandardDeviation();
            rand = new FastRandom(31415);
            // prepare a complete column for the dataset
            replacementValues = Enumerable.Repeat(double.NaN, modifiableDataset.Rows).ToList();
            // update column values 
            foreach (var r in rows) {
              replacementValues[r] = NormalDistributedRandom.NextDouble(rand, avg, stdDev);
            }
            break;

          default:
            throw new ArgumentException(string.Format("ReplacementMethod {0} cannot be handled.", replacementMethod));
        }

        newEstimates = GetReplacedEstimates(originalValues, model, variableName, modifiableDataset, rows, replacementValues);
        newValue = CalculateVariableImpact(targetValues, newEstimates, out error);
        if (error != OnlineCalculatorError.None) { throw new InvalidOperationException("Error during calculation with replaced inputs."); }

        impact = originalValue - newValue;
        #endregion
      } else if (modifiableDataset.VariableHasType<string>(variableName)) {
        #region FactorVariable
        var originalValues = modifiableDataset.GetReadOnlyStringValues(variableName).ToList();
        List<string> replacementValues;

        switch (factorReplacementMethod) {
          case FactorReplacementMethodEnum.Best:
            // try replacing with all possible values and find the best replacement value
            var smallestImpact = double.PositiveInfinity;
            foreach (var repl in modifiableDataset.GetStringValues(variableName, rows).Distinct()) {
              newEstimates = GetReplacedEstimates(originalValues, model, variableName, modifiableDataset, rows, Enumerable.Repeat(repl, modifiableDataset.Rows).ToList());
              newValue = CalculateVariableImpact(targetValues, newEstimates, out error);
              if (error != OnlineCalculatorError.None) throw new InvalidOperationException("Error during calculation with replaced inputs.");

              var curImpact = originalValue - newValue;
              if (curImpact < smallestImpact) smallestImpact = curImpact;
            }
            impact = smallestImpact;
            break;
          case FactorReplacementMethodEnum.Mode:
            var mostCommonValue = rows.Select(r => originalValues[r])
              .GroupBy(v => v)
              .OrderByDescending(g => g.Count())
              .First().Key;
            replacementValues = Enumerable.Repeat(mostCommonValue, modifiableDataset.Rows).ToList();

            newEstimates = GetReplacedEstimates(originalValues, model, variableName, modifiableDataset, rows, replacementValues);
            newValue = CalculateVariableImpact(targetValues, newEstimates, out error);
            if (error != OnlineCalculatorError.None) throw new InvalidOperationException("Error during calculation with replaced inputs.");

            impact = originalValue - newValue;
            break;
          case FactorReplacementMethodEnum.Shuffle:
            // new var has same empirical distribution but the relation to y is broken
            random = new FastRandom(31415);
            // prepare a complete column for the dataset
            replacementValues = Enumerable.Repeat(string.Empty, modifiableDataset.Rows).ToList();
            // shuffle only the selected rows
            var shuffledValues = rows.Select(r => originalValues[r]).Shuffle(random).ToList();
            int i = 0;
            // update column values 
            foreach (var r in rows) {
              replacementValues[r] = shuffledValues[i++];
            }

            newEstimates = GetReplacedEstimates(originalValues, model, variableName, modifiableDataset, rows, replacementValues);
            newValue = CalculateVariableImpact(targetValues, newEstimates, out error);
            if (error != OnlineCalculatorError.None) throw new InvalidOperationException("Error during calculation with replaced inputs.");

            impact = originalValue - newValue;
            break;
          default:
            throw new ArgumentException(string.Format("FactorReplacementMethod {0} cannot be handled.", factorReplacementMethod));
        }
        #endregion
      } else {
        throw new NotSupportedException("Variable not supported");
      }

      return impact;
    }

    /// <summary>
    /// Calculates and returns the VariableImpact (calculated via Accuracy).
    /// </summary>
    /// <param name="targetValues">The actual values</param>
    /// <param name="estimatedValues">The calculated/replaced values</param>
    /// <param name="errorState"></param>
    /// <returns></returns>
    public static double CalculateVariableImpact(IEnumerable<double> targetValues, IEnumerable<double> estimatedValues, out OnlineCalculatorError errorState) {
      //Theoretically, all calculators implement a static Calculate-Method which provides the same functionality
      //as the code below does. But this way we can easily swap the calculator later on, so the user  
      //could choose a Calculator during runtime in future versions.
      IOnlineCalculator calculator = new OnlineAccuracyCalculator();
      IEnumerator<double> firstEnumerator = targetValues.GetEnumerator();
      IEnumerator<double> secondEnumerator = estimatedValues.GetEnumerator();

      // always move forward both enumerators (do not use short-circuit evaluation!)
      while (firstEnumerator.MoveNext() & secondEnumerator.MoveNext()) {
        double original = firstEnumerator.Current;
        double estimated = secondEnumerator.Current;
        calculator.Add(original, estimated);
        if (calculator.ErrorState != OnlineCalculatorError.None) break;
      }

      // check if both enumerators are at the end to make sure both enumerations have the same length
      if (calculator.ErrorState == OnlineCalculatorError.None &&
           (secondEnumerator.MoveNext() || firstEnumerator.MoveNext())) {
        throw new ArgumentException("Number of elements in first and second enumeration doesn't match.");
      } else {
        errorState = calculator.ErrorState;
        return calculator.Value;
      }
    }

    /// <summary>
    /// Replaces the values of the original model-variables with the replacement variables, calculates the new estimated values 
    /// and changes the value of the model-variables back to the original ones.
    /// </summary>
    /// <param name="originalValues"></param>
    /// <param name="model"></param>
    /// <param name="variableName"></param>
    /// <param name="modifiableDataset"></param>
    /// <param name="rows"></param>
    /// <param name="replacementValues"></param>
    /// <returns></returns>
    private static IEnumerable<double> GetReplacedEstimates(
     IList originalValues,
     IClassificationModel model,
     string variableName,
     ModifiableDataset modifiableDataset,
     IEnumerable<int> rows,
     IList replacementValues) {
      modifiableDataset.ReplaceVariable(variableName, replacementValues);

      var discModel = model as IDiscriminantFunctionClassificationModel;
      if (discModel != null) {
        var problemData = new ClassificationProblemData(modifiableDataset, modifiableDataset.VariableNames, model.TargetVariable);
        discModel.RecalculateModelParameters(problemData, rows);
      }

      //mkommend: ToList is used on purpose to avoid lazy evaluation that could result in wrong estimates due to variable replacements
      var estimates = model.GetEstimatedClassValues(modifiableDataset, rows).ToList();
      modifiableDataset.ReplaceVariable(variableName, originalValues);

      return estimates;
    }


    /// <summary>
    /// Returns a collection of the row-indices for a given DataPartition (training or test)
    /// </summary>
    /// <param name="dataPartition"></param>
    /// <param name="problemData"></param>
    /// <returns></returns>
    public static IEnumerable<int> GetPartitionRows(DataPartitionEnum dataPartition, IClassificationProblemData problemData) {
      IEnumerable<int> rows;

      switch (dataPartition) {
        case DataPartitionEnum.All:
          rows = problemData.AllIndices;
          break;
        case DataPartitionEnum.Test:
          rows = problemData.TestIndices;
          break;
        case DataPartitionEnum.Training:
          rows = problemData.TrainingIndices;
          break;
        default:
          throw new NotSupportedException("DataPartition not supported");
      }

      return rows;
    }

  }
}