source: branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/PerformanceModelingView.cs @ 13794

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2016 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 HeuristicLab.Analysis;
using HeuristicLab.Common.Resources;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.MainForm;
using HeuristicLab.Optimization;
using HeuristicLab.OptimizationExpertSystem.Common;
using HeuristicLab.PluginInfrastructure;
using System;
using System.Collections.Generic;
using System.Linq;

namespace HeuristicLab.OptimizationExpertSystem {
  [View("Performance Modeling View")]
  [Content(typeof(KnowledgeCenter), IsDefaultView = false)]
  public partial class PerformanceModelingView : KnowledgeCenterViewBase {
    private readonly CheckedItemList<StringValue> characteristics;

    public PerformanceModelingView() {
      InitializeComponent();
      characteristics = new CheckedItemList<StringValue>();
      characteristics.CheckedItemsChanged += CharacteristicsOnCheckedItemsChanged;
      characteristicsViewHost.Content = characteristics;
      recommendStartButton.Text = string.Empty;
      recommendStartButton.Image = VSImageLibrary.Play;
      refreshCharacteristicsButton.Text = string.Empty;
      refreshCharacteristicsButton.Image = VSImageLibrary.Refresh;
      UpdateRecommenderCombobox();
    }

    protected override void OnContentChanged() {
      base.OnContentChanged();
      if (Content == null) {
        minTargetView.Content = null;
      } else {
        minTargetView.Content = Content.MinimumTarget;
      }
      UpdateCharacteristics();
    }

    protected override void SetEnabledStateOfControls() {
      base.SetEnabledStateOfControls();
      // TODO: up/download state
      recommendStartButton.Enabled = Content != null && recommenderComboBox.SelectedIndex >= 0 && characteristics.CheckedItems.Any();
      characteristicsViewHost.Enabled = Content != null;
      xValidateButton.Enabled = Content != null && recommenderComboBox.SelectedIndex >= 0 && characteristics.CheckedItems.Any();
    }

    #region Update Controls
    private void UpdateRecommenderCombobox() {
      if (InvokeRequired) { Invoke((Action)UpdateRecommenderCombobox); return; }
      var prevSelection = (IAlgorithmInstanceRecommender)recommenderComboBox.SelectedItem;
      var prevNewIndex = -1;
      recommenderComboBox.Items.Clear();

      var i = 0;
      foreach (var rcmd in ApplicationManager.Manager.GetInstances<IAlgorithmInstanceRecommender>()) {
        recommenderComboBox.Items.Add(rcmd);
        if (prevSelection == null || rcmd.GetType() == prevSelection.GetType())
          prevNewIndex = prevSelection == null ? 0 : i;
        i++;
      }
      
      recommenderComboBox.SelectedIndex = prevNewIndex;
    }

    private void UpdateCharacteristics() {
      if (InvokeRequired) { Invoke((Action)UpdateCharacteristics); return; }

      var @checked = new HashSet<string>(characteristics.CheckedItems.Select(x => x.Value.Value));
      if (@checked.Count == 0 && Content.ProblemInstances.ResultNames.Any(x => x.StartsWith("Characteristic.")))
        @checked = new HashSet<string>(Content.ProblemInstances.ResultNames.Where(x => x.StartsWith("Characteristic.")));

      characteristics.Clear();
      if (Content == null || Content.ProblemInstances.Count == 0) return;

      foreach (var c in Content.ProblemInstances.ResultNames) {
        characteristics.Add(new StringValue(c), @checked.Contains(c));
      }
    }
    #endregion

    #region Content Event Handlers
    protected override void OnProblemInstancesChanged() {
      base.OnProblemInstancesChanged();
      UpdateCharacteristics();
      SetEnabledStateOfControls();
    }
    #endregion

    #region Control Event Handlers
    private void RecommenderComboBoxOnSelectedIndexChanged(object sender, EventArgs e) {
      if (InvokeRequired) { Invoke((Action<object, EventArgs>)RecommenderComboBoxOnSelectedIndexChanged, sender, e); return; }
      var rcmd = (IAlgorithmInstanceRecommender)recommenderComboBox.SelectedItem;
      parameterCollectionView.Content = rcmd != null ? rcmd.Parameters : null;
      SetEnabledStateOfControls();
    }

    private void RecommendStartButtonOnClick(object sender, EventArgs e) {
      var rcmd = (IAlgorithmInstanceRecommender)recommenderComboBox.SelectedItem;
      var trainingSet = Content.ProblemInstances.Where(x => !Content.IsCurrentInstance(x)).ToArray();
      Content.RecommendationModel = rcmd.TrainModel(trainingSet, Content, characteristics.CheckedItems.Select(x => x.Value.Value).ToArray());
    }

    private void RefreshCharacteristicsButtonOnClick(object sender, EventArgs e) {
      UpdateCharacteristics();
      SetEnabledStateOfControls();
    }

    private void xValidateButton_Click(object sender, EventArgs e) {
      var recommender = (IAlgorithmInstanceRecommender)recommenderComboBox.SelectedItem;
      var features = characteristics.CheckedItems.Select(x => x.Value.Value).ToArray();

      var trainingSet = Content.ProblemInstances.Where(x => !Content.IsCurrentInstance(x)).ToArray();

      var absErr = 0.0;
      var confMatrix = new int[6, 6];
      var tau = 0.0;
      // leave one out crossvalidation
      foreach (var pi in trainingSet) {
        var model = recommender.TrainModel(trainingSet.Where(x => x != pi).ToArray(), Content, features);
        var predicted = model.GetRanking(pi).ToDictionary(x => x.Key, x => x.Value);
        var observed = Content.GetAlgorithmPerformance(pi);
        absErr += AbsoluteError(observed, predicted);
        var confMat = ConfusionMatrix(observed, predicted);
        for (var i = 0; i < confMat.GetLength(0); i++)
          for (var j = 0; j < confMat.GetLength(1); j++)
            confMatrix[i, j] += confMat[i, j];
        tau += KendallsTau(observed, predicted);
        // average NCDG ... relevance determined by clustering (unsuccessful algorithms being penalized with negative relevance)
        // mean reciprocal rank
        // optional: expected reciprocal rank
      }
      absErr /= trainingSet.Length;
      tau /= trainingSet.Length;

      confusionMatrixView.Content = new IntMatrix(confMatrix);
      absoluteErrorView.Content = new DoubleValue(absErr);
      kendallsTauView.Content = new DoubleValue(tau);
    }

    private static double AbsoluteError(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
      var error = 0.0;
      foreach (var tuple in ranking) {
        double actual;
        if (!performance.TryGetValue(tuple.Key, out actual)) continue;
        if (double.IsNaN(actual)) actual = int.MaxValue;
        error += Math.Abs(actual - tuple.Value);
      }
      return error;
    }

    private static int[,] ConfusionMatrix(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
      var confMatrix = new int[6,6];
      var clusteredPerformance = ClusteringHelper<IAlgorithm>.Cluster(5, performance, a => double.IsNaN(a.Value)).GetByInstance().ToDictionary(x => x.Key, x => x.Value.Item2);
      var clusteredRanks = ClusteringHelper<IAlgorithm>.Cluster(5, ranking, x => double.IsNaN(x.Value) || x.Value >= int.MaxValue).GetByInstance().ToDictionary(x => x.Key, x => x.Value.Item2);
      foreach (var cr in clusteredRanks) {
        int realRank;
        if (!clusteredPerformance.TryGetValue(cr.Key, out realRank)) continue;
        confMatrix[realRank, cr.Value]++;
      }
      return confMatrix;
    }

    private static double KendallsTau(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
      var commonKeys = performance.Keys.Intersect(ranking.Keys).ToList();
      var n = commonKeys.Count;
      if (n == 0) return 0.0;

      var actualRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = performance[x] })
                                  .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = i })
                                  .OrderBy(x => x.Index).Select(x => x.Rank).ToList();
      var predictedRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = ranking[x] })
                                     .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = i })
                                     .OrderBy(x => x.Index).Select(x => x.Rank).ToList();
      
      var paired = actualRanks.Zip(predictedRanks, (a, p) => new { Actual = a, Predicted = p }).ToList();
      var concordant = 0;
      var discordant = 0;
      for (var i = 0; i < paired.Count - 1; i++)
        for (var j = 0; j < paired.Count; j++) {
          if (paired[i].Actual > paired[j].Actual && paired[i].Predicted > paired[j].Predicted
            || paired[i].Actual < paired[j].Actual && paired[i].Predicted < paired[j].Predicted)
            concordant++;
          else discordant++;
        }
      return (2.0 * (concordant - discordant)) / (n * (n - 1));
    }
    #endregion

    #region Other Event Handlers
    private void CharacteristicsOnCheckedItemsChanged(object sender, EventArgs e) {
      SetEnabledStateOfControls();
    }
    #endregion
  }
}