Changeset 13794 for branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem

Timestamp:

04/26/16 00:02:05 (9 years ago)

Author:

abeham

Message:

#2457: worked on recommendation algorithms (x-validation)

Location:

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views

Files:

• PerformanceModelingView.Designer.cs (modified) (8 diffs)
• PerformanceModelingView.cs (modified) (2 diffs)
• SolverView.cs (modified) (5 diffs)

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/PerformanceModelingView.Designer.cs

@@ -55 +55 @@
       this.parameterCollectionView = new HeuristicLab.Core.Views.ParameterCollectionView();
       this.crossvalidationTabPage = new System.Windows.Forms.TabPage();
+      this.kendallsTauLabel = new System.Windows.Forms.Label();
+      this.absoluteErrorLabel = new System.Windows.Forms.Label();
+      this.kendallsTauView = new HeuristicLab.Data.Views.StringConvertibleValueView();
+      this.absoluteErrorView = new HeuristicLab.Data.Views.StringConvertibleValueView();
+      this.confusionMatrixView = new HeuristicLab.Data.Views.StringConvertibleMatrixView();
       this.xValidateButton = new System.Windows.Forms.Button();
       this.minTargetView = new HeuristicLab.Data.Views.StringConvertibleValueView();
       this.minimumTargetLabel = new System.Windows.Forms.Label();
+      this.actualLabel = new System.Windows.Forms.Label();
+      this.predictedLabel = new System.Windows.Forms.Label();
       this.tabControl.SuspendLayout();
       this.characteristicsTabPage.SuspendLayout();
@@ -75 +82 @@
       // recommenderComboBox
       // 
-      this.recommenderComboBox.Anchor = ((System.Windows.Forms.AnchorStyles)(((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Left) 
-            | System.Windows.Forms.AnchorStyles.Right)));
       this.recommenderComboBox.DropDownStyle = System.Windows.Forms.ComboBoxStyle.DropDownList;
       this.recommenderComboBox.FormattingEnabled = true;
@@ -87 +92 @@
       // recommendStartButton
       // 
-      this.recommendStartButton.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Right)));
       this.recommendStartButton.Location = new System.Drawing.Point(442, 1);
       this.recommendStartButton.Name = "recommendStartButton";
@@ -107 +111 @@
       this.tabControl.Name = "tabControl";
       this.tabControl.SelectedIndex = 0;
-      this.tabControl.Size = new System.Drawing.Size(700, 350);
+      this.tabControl.Size = new System.Drawing.Size(817, 509);
       this.tabControl.TabIndex = 14;
       // 
@@ -174 +178 @@
       // crossvalidationTabPage
       // 
+      this.crossvalidationTabPage.Controls.Add(this.kendallsTauLabel);
+      this.crossvalidationTabPage.Controls.Add(this.predictedLabel);
+      this.crossvalidationTabPage.Controls.Add(this.actualLabel);
+      this.crossvalidationTabPage.Controls.Add(this.absoluteErrorLabel);
+      this.crossvalidationTabPage.Controls.Add(this.kendallsTauView);
+      this.crossvalidationTabPage.Controls.Add(this.absoluteErrorView);
+      this.crossvalidationTabPage.Controls.Add(this.confusionMatrixView);
       this.crossvalidationTabPage.Controls.Add(this.xValidateButton);
       this.crossvalidationTabPage.Location = new System.Drawing.Point(4, 22);
       this.crossvalidationTabPage.Name = "crossvalidationTabPage";
       this.crossvalidationTabPage.Padding = new System.Windows.Forms.Padding(3);
-      this.crossvalidationTabPage.Size = new System.Drawing.Size(692, 324);
+      this.crossvalidationTabPage.Size = new System.Drawing.Size(809, 483);
       this.crossvalidationTabPage.TabIndex = 1;
       this.crossvalidationTabPage.Text = "Crossvalidation";
       this.crossvalidationTabPage.UseVisualStyleBackColor = true;
+      // 
+      // kendallsTauLabel
+      // 
+      this.kendallsTauLabel.AutoSize = true;
+      this.kendallsTauLabel.Location = new System.Drawing.Point(536, 110);
+      this.kendallsTauLabel.Margin = new System.Windows.Forms.Padding(3);
+      this.kendallsTauLabel.Name = "kendallsTauLabel";
+      this.kendallsTauLabel.Size = new System.Drawing.Size(104, 13);
+      this.kendallsTauLabel.TabIndex = 3;
+      this.kendallsTauLabel.Text = "Mean Kendall\'s Tau:";
+      // 
+      // absoluteErrorLabel
+      // 
+      this.absoluteErrorLabel.AutoSize = true;
+      this.absoluteErrorLabel.Location = new System.Drawing.Point(536, 52);
+      this.absoluteErrorLabel.Margin = new System.Windows.Forms.Padding(3);
+      this.absoluteErrorLabel.Name = "absoluteErrorLabel";
+      this.absoluteErrorLabel.Size = new System.Drawing.Size(106, 13);
+      this.absoluteErrorLabel.TabIndex = 3;
+      this.absoluteErrorLabel.Text = "Mean Absolute Error:";
+      // 
+      // kendallsTauView
+      // 
+      this.kendallsTauView.Caption = "StringConvertibleValue View";
+      this.kendallsTauView.Content = null;
+      this.kendallsTauView.LabelVisible = false;
+      this.kendallsTauView.Location = new System.Drawing.Point(520, 129);
+      this.kendallsTauView.Name = "kendallsTauView";
+      this.kendallsTauView.ReadOnly = true;
+      this.kendallsTauView.Size = new System.Drawing.Size(194, 21);
+      this.kendallsTauView.TabIndex = 2;
+      // 
+      // absoluteErrorView
+      // 
+      this.absoluteErrorView.Caption = "StringConvertibleValue View";
+      this.absoluteErrorView.Content = null;
+      this.absoluteErrorView.LabelVisible = false;
+      this.absoluteErrorView.Location = new System.Drawing.Point(520, 71);
+      this.absoluteErrorView.Name = "absoluteErrorView";
+      this.absoluteErrorView.ReadOnly = true;
+      this.absoluteErrorView.Size = new System.Drawing.Size(194, 21);
+      this.absoluteErrorView.TabIndex = 2;
+      // 
+      // confusionMatrixView
+      // 
+      this.confusionMatrixView.Caption = "StringConvertibleMatrix View";
+      this.confusionMatrixView.Content = null;
+      this.confusionMatrixView.Location = new System.Drawing.Point(37, 71);
+      this.confusionMatrixView.Name = "confusionMatrixView";
+      this.confusionMatrixView.ReadOnly = true;
+      this.confusionMatrixView.ShowRowsAndColumnsTextBox = false;
+      this.confusionMatrixView.ShowStatisticalInformation = false;
+      this.confusionMatrixView.Size = new System.Drawing.Size(477, 363);
+      this.confusionMatrixView.TabIndex = 1;
       // 
       // xValidateButton
@@ -212 +277 @@
       this.minimumTargetLabel.TabIndex = 17;
       this.minimumTargetLabel.Text = "Target:";
+      // 
+      // actualLabel
+      // 
+      this.actualLabel.AutoSize = true;
+      this.actualLabel.Font = new System.Drawing.Font("Microsoft Sans Serif", 8.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
+      this.actualLabel.Location = new System.Drawing.Point(16, 210);
+      this.actualLabel.Margin = new System.Windows.Forms.Padding(3);
+      this.actualLabel.Name = "actualLabel";
+      this.actualLabel.Size = new System.Drawing.Size(15, 78);
+      this.actualLabel.TabIndex = 3;
+      this.actualLabel.Text = "A\r\nC\r\nT\r\nU\r\nA\r\nL";
+      // 
+      // predictedLabel
+      // 
+      this.predictedLabel.AutoSize = true;
+      this.predictedLabel.Font = new System.Drawing.Font("Microsoft Sans Serif", 8.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
+      this.predictedLabel.Location = new System.Drawing.Point(241, 52);
+      this.predictedLabel.Margin = new System.Windows.Forms.Padding(3);
+      this.predictedLabel.Name = "predictedLabel";
+      this.predictedLabel.Size = new System.Drawing.Size(69, 13);
+      this.predictedLabel.TabIndex = 3;
+      this.predictedLabel.Text = "PREDICTED";
       // 
       // PerformanceModelingView
@@ -224 +311 @@
       this.Controls.Add(this.recommendStartButton);
       this.Name = "PerformanceModelingView";
+      this.Size = new System.Drawing.Size(817, 539);
       this.tabControl.ResumeLayout(false);
       this.characteristicsTabPage.ResumeLayout(false);
       this.parametersTabPage.ResumeLayout(false);
       this.crossvalidationTabPage.ResumeLayout(false);
+      this.crossvalidationTabPage.PerformLayout();
       this.ResumeLayout(false);
       this.PerformLayout();
@@ -248 +337 @@
     private Data.Views.StringConvertibleValueView minTargetView;
     private System.Windows.Forms.Label minimumTargetLabel;
+    private System.Windows.Forms.Label kendallsTauLabel;
+    private System.Windows.Forms.Label absoluteErrorLabel;
+    private Data.Views.StringConvertibleValueView kendallsTauView;
+    private Data.Views.StringConvertibleValueView absoluteErrorView;
+    private Data.Views.StringConvertibleMatrixView confusionMatrixView;
+    private System.Windows.Forms.Label predictedLabel;
+    private System.Windows.Forms.Label actualLabel;
   }
 }

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/PerformanceModelingView.cs

@@ -20 +20 @@
 #endregion
 
+using HeuristicLab.Analysis;
 using HeuristicLab.Common.Resources;
 using HeuristicLab.Core;
@@ -134 +135 @@
       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 ranking = model.GetRanking(pi).ToList();
-        var realPerformance = Content.GetAlgorithmPerformance(pi);
-        // absolute error predicting ert
-        // confusion matrix predicting class
-        // Kendall's tau
+        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
       }
-    }
-
-    private static double AbsoluteError(Dictionary<IAlgorithm, double> performance, List<Tuple<IAlgorithm, double>> ranking) {
+      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.Item1, out actual)) continue;
-        error += Math.Abs(actual - tuple.Item2);
+        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, List<Tuple<IAlgorithm, double>> ranking) {
-      var confMatrix = new int[5,5];
+    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

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/SolverView.cs

@@ -28 +28 @@
 using HeuristicLab.OptimizationExpertSystem.Common;
 using System;
+using System.Collections.Generic;
 using System.Linq;
 using System.Windows.Forms;
@@ -96 +97 @@
       for (var i = 0; i < ranking.Count; i++) {
         suggestedInstancesComboBox.Items.Add(new AlgorithmInstanceItem(ranking[i]));
-        if (prevSelection == null || ranking[i].Item1.Name == prevSelection.Item.Item1.Name)
+        if (prevSelection == null || ranking[i].Key.Name == prevSelection.Item.Key.Name)
           prevNewIndex = prevSelection == null ? 0 : i;
       }
@@ -119 +120 @@
     private void AlgorithmStartButtonOnClick(object sender, EventArgs e) {
       if (suggestedInstancesComboBox.SelectedIndex >= 0)
-        Content.StartAlgorithmAsync(Content.AlgorithmInstances.Select((a, i) => new { Alg = a, Index = i}).Single(x => x.Alg.Name == ((AlgorithmInstanceItem)suggestedInstancesComboBox.SelectedItem).Item.Item1.Name).Index);
+        Content.StartAlgorithmAsync(Content.AlgorithmInstances.Select((a, i) => new { Alg = a, Index = i}).Single(x => x.Alg.Name == ((AlgorithmInstanceItem)suggestedInstancesComboBox.SelectedItem).Item.Key.Name).Index);
     }
 
     private void AlgorithmCloneButtonOnClick(object sender, EventArgs e) {
       if (suggestedInstancesComboBox.SelectedIndex >= 0)
-        MainForm.ShowContent((IAlgorithm)Content.AlgorithmInstances[Content.AlgorithmInstances.Select((a, i) => new { Alg = a, Index = i }).Single(x => x.Alg.Name == ((AlgorithmInstanceItem)suggestedInstancesComboBox.SelectedItem).Item.Item1.Name).Index].Clone());
+        MainForm.ShowContent((IAlgorithm)Content.AlgorithmInstances[Content.AlgorithmInstances.Select((a, i) => new { Alg = a, Index = i }).Single(x => x.Alg.Name == ((AlgorithmInstanceItem)suggestedInstancesComboBox.SelectedItem).Item.Key.Name).Index].Clone());
     }
 
@@ -130 +131 @@
       if (InvokeRequired) { Invoke((Action<object, EventArgs>)SuggestedInstancesComboBoxOnSelectedIndexChanged, sender, e); return; }
       if (suggestedInstancesComboBox.SelectedIndex >= 0) {
-        var alg = Content.AlgorithmInstances[Content.AlgorithmInstances.Select((a, i) => new { Alg = a, Index = i }).Single(x => x.Alg.Name == ((AlgorithmInstanceItem)suggestedInstancesComboBox.SelectedItem).Item.Item1.Name).Index];
+        var alg = Content.AlgorithmInstances[Content.AlgorithmInstances.Select((a, i) => new { Alg = a, Index = i }).Single(x => x.Alg.Name == ((AlgorithmInstanceItem)suggestedInstancesComboBox.SelectedItem).Item.Key.Name).Index];
         solverParametersView.Content = alg.Parameters;
         var engineAlg = alg as EngineAlgorithm;
@@ -145 +146 @@
     #region Helper Classes and Methods
     private class AlgorithmInstanceItem {
-      private readonly Tuple<IAlgorithm, double> item;
-      public Tuple<IAlgorithm, double> Item { get { return item; } }
+      private readonly KeyValuePair<IAlgorithm, double> item;
+      public KeyValuePair<IAlgorithm, double> Item { get { return item; } }
 
-      public AlgorithmInstanceItem(Tuple<IAlgorithm, double> item) {
+      public AlgorithmInstanceItem(KeyValuePair<IAlgorithm, double> item) {
         this.item = item;
       }
 
       public override string ToString() {
-        return item.Item2.ToString("N0") + ": " + item.Item1.Name;
+        return item.Value.ToString("N0") + ": " + item.Key.Name;
       }
     }