Changeset 15736

Timestamp:

02/07/18 20:55:57 (6 years ago)

Author:

abeham

Message:

#1614: updates from last night ...

Location:

branches/1614_GeneralizedQAP

Files:

• HeuristicLab.OptimizationExpertSystem.Common/3.3/KnowledgeCenter.cs (modified) (8 diffs)
• HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/KNearestNeighborModel.cs (modified) (2 diffs)
• HeuristicLab.OptimizationExpertSystem/3.3/Views/PerformanceModelingView.Designer.cs (modified) (8 diffs)
• HeuristicLab.OptimizationExpertSystem/3.3/Views/PerformanceModelingView.cs (modified) (10 diffs)

branches/1614_GeneralizedQAP/HeuristicLab.OptimizationExpertSystem.Common/3.3/KnowledgeCenter.cs

@@ -20 +20 @@
 #endregion
 
+using System;
+using System.Collections.Generic;
+using System.Drawing;
+using System.IO;
+using System.Linq;
+using System.Threading;
+using System.Threading.Tasks;
+using HeuristicLab.Algorithms.DataAnalysis;
 using HeuristicLab.Analysis;
 using HeuristicLab.Analysis.SelfOrganizingMaps;
@@ -32 +40 @@
 using HeuristicLab.Problems.DataAnalysis;
 using HeuristicLab.Random;
-using System;
-using System.Collections.Generic;
-using System.Drawing;
-using System.IO;
-using System.Linq;
-using System.Threading;
-using System.Threading.Tasks;
-using HeuristicLab.Algorithms.DataAnalysis;
 using Algorithm = HeuristicLab.Clients.OKB.Administration.Algorithm;
 using Problem = HeuristicLab.Clients.OKB.Administration.Problem;
@@ -296 +296 @@
 
     private static readonly HashSet<string> InterestingValueNames = new HashSet<string>() {
-      "QualityPerEvaluations", "Problem Name", "Problem Type", "Algorithm Name", "Algorithm Type", "Maximization", "BestKnownQuality"
+      "QualityPerEvaluations", "QualityPerClock", "Problem Name", "Problem Type", "Algorithm Name", "Algorithm Type", "Maximization", "BestKnownQuality"
     };
 
@@ -517 +517 @@
 
           IItem bkParam;
-          if (!prob.Parameters.TryGetValue("BestKnownQuality", out bkParam) || !(bkParam is DoubleValue)) {
+          if (!prob.Parameters.TryGetValue("BestKnownQuality", out bkParam) || !(bkParam is DoubleValue) || double.IsNaN(((DoubleValue)bkParam).Value)) {
             var list = kvp.Value.SelectMany(x => x.Value)
-              .Where(x => x.Results.ContainsKey("QualityPerEvaluations"))
-              .Select(x => ((IndexedDataTable<double>)x.Results["QualityPerEvaluations"]).Rows.First().Values.Last().Item2);
+              .Where(x => x.Results.ContainsKey("QualityPerClock"))
+              .Select(x => (IndexedDataTable<double>)x.Results["QualityPerClock"])
+              .Where(x => x.Rows.Count > 0 && x.Rows.First().Values.Count > 0)
+              .Select(x => x.Rows.First().Values.Last().Item2);
             if (!list.Any()) continue;
             bkParam = new DoubleValue(maximization ? list.Max() : list.Min());
@@ -765 +767 @@
       return knowledgeBase.Where(x => ((StringValue)x.Parameters["Problem Name"]).Value == ((StringValue)problemInstance.Parameters["Problem Name"]).Value)
                           .GroupBy(x => algorithmId2AlgorithmInstanceMapping.GetByFirst(algorithmId2RunMapping.GetBySecond(x).Single()))
-                          .ToDictionary(x => x.Key, x => ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerEvaluations", target, Maximization).ExpectedRuntime);
+                          .ToDictionary(x => x.Key, x => ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerClock", target, Maximization).ExpectedRuntime);
     }
 
@@ -773 +775 @@
       return knowledgeBase.Where(x => ((StringValue)x.Parameters["Problem Name"]).Value == ((StringValue)problemInstance.Parameters["Problem Name"]).Value)
                           .GroupBy(x => algorithmId2AlgorithmInstanceMapping.GetByFirst(algorithmId2RunMapping.GetBySecond(x).Single()))
-                          .ToDictionary(x => x.Key, x => Math.Log10(ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerEvaluations", target, Maximization).ExpectedRuntime));
+                          .ToDictionary(x => x.Key, x => Math.Log10(ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerClock", target, Maximization).ExpectedRuntime));
     }
 
@@ -806 +808 @@
           var max = ((BoolValue)prob.Parameters["Maximization"]).Value;
           var bkq = ((DoubleValue)prob.Parameters["BestKnownQuality"]).Value;
-          var ert = ExpectedRuntimeHelper.CalculateErt(pr.ToList(), "QualityPerEvaluations", GetTarget(bkq, target, max), max).ExpectedRuntime;
+          var ert = ExpectedRuntimeHelper.CalculateErt(pr.ToList(), "QualityPerClock", GetTarget(bkq, target, max), max).ExpectedRuntime;
           if (double.IsInfinity(ert)) ert = int.MaxValue;
           ds.AddRow(new object[] { pr.Key }.Concat(f.Cast<object>()).Concat(new object[] { ert }));
@@ -872 +874 @@
 
         var values = pr.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())
-                       .ToDictionary(x => x.Key, x => Math.Log10(ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerEvaluations", GetTarget(bkq, target, max), max).ExpectedRuntime));
+                       .ToDictionary(x => x.Key, x => Math.Log10(ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerClock", GetTarget(bkq, target, max), max).ExpectedRuntime));
         var ranks = ClusteringHelper<long>.Cluster(nClasses, values, x => double.IsInfinity(x.Value))
           .GetByCluster().ToList();

branches/1614_GeneralizedQAP/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/KNearestNeighborModel.cs

@@ -20 +20 @@
 #endregion
 
+using System;
+using System.Collections.Generic;
+using System.Linq;
 using HeuristicLab.Collections;
 using HeuristicLab.Common;
 using HeuristicLab.Optimization;
-using System;
-using System.Collections.Generic;
-using System.Linq;
 
 namespace HeuristicLab.OptimizationExpertSystem.Common {
@@ -55 +55 @@
         else feature[f] = (feature[f] - means[f]) / sdevs[f];
       }
+      var dist = features.Select((f, i) => Math.Sqrt(f.Select((g, j) => Math.Sqrt((g - feature[j]) * (g - feature[j]))).Sum())).ToList();
       var nearestK = features.Select((f, i) => new { ProblemInstanceIndex = i, Feature = f })
-                             .OrderBy(x => x.Feature.Select((f, i) => (f - feature[i]) * (f - feature[i])).Sum());
+                             .OrderBy(x => dist[x.ProblemInstanceIndex]);
       
       var performances = new Dictionary<IAlgorithm, Performance>();

branches/1614_GeneralizedQAP/HeuristicLab.OptimizationExpertSystem/3.3/Views/PerformanceModelingView.Designer.cs

@@ -57 +57 @@
       this.topNComboBox = new System.Windows.Forms.ComboBox();
       this.topNlabel = new System.Windows.Forms.Label();
+      this.ndcgLabel = new System.Windows.Forms.Label();
       this.kendallsTauLabel = new System.Windows.Forms.Label();
       this.predictedLabel = new System.Windows.Forms.Label();
       this.absoluteLogErrorLabel = new System.Windows.Forms.Label();
       this.absoluteErrorLabel = new System.Windows.Forms.Label();
+      this.ncdgView = new HeuristicLab.Data.Views.StringConvertibleValueView();
       this.kendallsTauView = new HeuristicLab.Data.Views.StringConvertibleValueView();
       this.absoluteLogErrorView = new HeuristicLab.Data.Views.StringConvertibleValueView();
@@ -68 +70 @@
       this.minTargetView = new HeuristicLab.Data.Views.StringConvertibleValueView();
       this.minimumTargetLabel = new System.Windows.Forms.Label();
-      this.ncdgView = new HeuristicLab.Data.Views.StringConvertibleValueView();
-      this.ndcgLabel = new System.Windows.Forms.Label();
+      this.spearmansRhoView = new HeuristicLab.Data.Views.StringConvertibleValueView();
+      this.spearmansRhoLabel = new System.Windows.Forms.Label();
       this.tabControl.SuspendLayout();
       this.characteristicsTabPage.SuspendLayout();
@@ -186 +188 @@
       this.crossvalidationTabPage.Controls.Add(this.topNlabel);
       this.crossvalidationTabPage.Controls.Add(this.ndcgLabel);
+      this.crossvalidationTabPage.Controls.Add(this.spearmansRhoLabel);
       this.crossvalidationTabPage.Controls.Add(this.kendallsTauLabel);
       this.crossvalidationTabPage.Controls.Add(this.predictedLabel);
@@ -191 +194 @@
       this.crossvalidationTabPage.Controls.Add(this.absoluteErrorLabel);
       this.crossvalidationTabPage.Controls.Add(this.ncdgView);
+      this.crossvalidationTabPage.Controls.Add(this.spearmansRhoView);
       this.crossvalidationTabPage.Controls.Add(this.kendallsTauView);
       this.crossvalidationTabPage.Controls.Add(this.absoluteLogErrorView);
@@ -223 +227 @@
       this.topNlabel.Text = "Evaluate only best ranked:";
       // 
+      // ndcgLabel
+      // 
+      this.ndcgLabel.AutoSize = true;
+      this.ndcgLabel.Location = new System.Drawing.Point(519, 165);
+      this.ndcgLabel.Margin = new System.Windows.Forms.Padding(3);
+      this.ndcgLabel.Name = "ndcgLabel";
+      this.ndcgLabel.Size = new System.Drawing.Size(106, 13);
+      this.ndcgLabel.TabIndex = 3;
+      this.ndcgLabel.Text = "Mean NDCG (top N):";
+      // 
       // kendallsTauLabel
       // 
@@ -263 +277 @@
       this.absoluteErrorLabel.TabIndex = 3;
       this.absoluteErrorLabel.Text = "Mean Absolute Error (top N):";
+      // 
+      // ncdgView
+      // 
+      this.ncdgView.Caption = "StringConvertibleValue View";
+      this.ncdgView.Content = null;
+      this.ncdgView.LabelVisible = false;
+      this.ncdgView.Location = new System.Drawing.Point(503, 184);
+      this.ncdgView.Name = "ncdgView";
+      this.ncdgView.ReadOnly = true;
+      this.ncdgView.Size = new System.Drawing.Size(194, 21);
+      this.ncdgView.TabIndex = 2;
       // 
       // kendallsTauView
@@ -339 +364 @@
       this.minimumTargetLabel.Text = "Target:";
       // 
-      // ncdgView
-      // 
-      this.ncdgView.Caption = "StringConvertibleValue View";
-      this.ncdgView.Content = null;
-      this.ncdgView.LabelVisible = false;
-      this.ncdgView.Location = new System.Drawing.Point(503, 184);
-      this.ncdgView.Name = "ncdgView";
-      this.ncdgView.ReadOnly = true;
-      this.ncdgView.Size = new System.Drawing.Size(194, 21);
-      this.ncdgView.TabIndex = 2;
-      // 
-      // ndcgLabel
-      // 
-      this.ndcgLabel.AutoSize = true;
-      this.ndcgLabel.Location = new System.Drawing.Point(519, 165);
-      this.ndcgLabel.Margin = new System.Windows.Forms.Padding(3);
-      this.ndcgLabel.Name = "ndcgLabel";
-      this.ndcgLabel.Size = new System.Drawing.Size(106, 13);
-      this.ndcgLabel.TabIndex = 3;
-      this.ndcgLabel.Text = "Mean NDCG (top N):";
+      // spearmansRhoView
+      // 
+      this.spearmansRhoView.Caption = "StringConvertibleValue View";
+      this.spearmansRhoView.Content = null;
+      this.spearmansRhoView.LabelVisible = false;
+      this.spearmansRhoView.Location = new System.Drawing.Point(503, 303);
+      this.spearmansRhoView.Name = "spearmansRhoView";
+      this.spearmansRhoView.ReadOnly = true;
+      this.spearmansRhoView.Size = new System.Drawing.Size(194, 21);
+      this.spearmansRhoView.TabIndex = 2;
+      // 
+      // spearmansRhoLabel
+      // 
+      this.spearmansRhoLabel.AutoSize = true;
+      this.spearmansRhoLabel.Location = new System.Drawing.Point(519, 284);
+      this.spearmansRhoLabel.Margin = new System.Windows.Forms.Padding(3);
+      this.spearmansRhoLabel.Name = "spearmansRhoLabel";
+      this.spearmansRhoLabel.Size = new System.Drawing.Size(118, 13);
+      this.spearmansRhoLabel.TabIndex = 3;
+      this.spearmansRhoLabel.Text = "Mean Spearman\'s Rho:";
       // 
       // PerformanceModelingView
@@ -409 +434 @@
     private System.Windows.Forms.Label ndcgLabel;
     private Data.Views.StringConvertibleValueView ncdgView;
+    private System.Windows.Forms.Label spearmansRhoLabel;
+    private Data.Views.StringConvertibleValueView spearmansRhoView;
   }
 }

branches/1614_GeneralizedQAP/HeuristicLab.OptimizationExpertSystem/3.3/Views/PerformanceModelingView.cs

@@ -20 +20 @@
 #endregion
 
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Threading.Tasks;
 using HeuristicLab.Analysis;
 using HeuristicLab.Common.Resources;
@@ -28 +32 @@
 using HeuristicLab.OptimizationExpertSystem.Common;
 using HeuristicLab.PluginInfrastructure;
-using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Threading.Tasks;
 
 namespace HeuristicLab.OptimizationExpertSystem {
@@ -181 +181 @@
         var tau = 0.0;
         var tauCnt = 0;
+        var rho = 0.0;
+        var rhoCnt = 0;
         var ndcg = 0.0;
         var ndcgCnt = 0;
@@ -207 +209 @@
           }
           var kt = KendallsTau(observed, predicted);
-          if (!double.IsNaN(kt)) {
+          if (!double.IsNaN(kt) && !double.IsInfinity(kt)) {
             tau += kt;
             tauCnt++;
+          }
+          var sr = SpearmansRho(observed, predicted);
+          if (!double.IsNaN(sr)) {
+            rho += sr;
+            rhoCnt++;
           }
           var gain = NDCG(observed, model.GetRanking(pi).Take(topN).Select(x => x.Key).ToList());
@@ -216 +223 @@
             ndcgCnt++;
           }
-          // mean reciprocal rank
-          // optional: expected reciprocal rank
           progress.ProgressValue = ++count / (double)trainingSet.Length;
         }
@@ -223 +228 @@
         absLogErr /= absLogErrCnt;
         tau /= tauCnt;
+        rho /= rhoCnt;
         ndcg /= ndcgCnt;
 
@@ -230 +236 @@
         confusionMatrixView.Content = new IntMatrix(confMatrix) {ColumnNames = description};
         kendallsTauView.Content = new DoubleValue(tau);
+        spearmansRhoView.Content = new DoubleValue(rho);
         ncdgView.Content = new DoubleValue(ndcg);
       } finally { progress.Finish(); }
@@ -272 +279 @@
     }
 
+    private static double SpearmansRho(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
+      var commonKeys = performance.Keys.Intersect(ranking.Keys).ToList();
+      var n = commonKeys.Count;
+      if (n == 0) return double.NaN;
+
+      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 = double.IsPositiveInfinity(x.Perf) ? int.MaxValue : i })
+                                  .OrderBy(x => x.Index).Select(x => (double)x.Rank).ToArray();
+      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 = double.IsPositiveInfinity(x.Perf) ? int.MaxValue : i })
+                                     .OrderBy(x => x.Index).Select(x => (double)x.Rank).ToArray();
+
+      return alglib.spearmancorr2(actualRanks, predictedRanks);
+    }
+
     private static double KendallsTau(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
       var commonKeys = performance.Keys.Intersect(ranking.Keys).ToList();
@@ -278 +300 @@
 
       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.Perf).Select((x, i) => new { Index = x.Index, Rank = double.IsPositiveInfinity(x.Perf) ? int.MaxValue : 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.Perf).Select((x, i) => new { Index = x.Index, Rank = double.IsPositiveInfinity(x.Perf) ? int.MaxValue : i })
                                      .OrderBy(x => x.Index).Select(x => x.Rank).ToList();
 
@@ -292 +314 @@
             || paired[i].Actual < paired[j].Actual && paired[i].Predicted < paired[j].Predicted)
             concordant++;
-          else discordant++;
+          else 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)
+            discordant++;
         }
-      return (2.0 * (concordant - discordant)) / (n * (n - 1));
+
+      var ti = performance.GroupBy(x => x.Value).Sum(x => x.Count() * (x.Count() - 1));
+      var uj = ranking.GroupBy(x => x.Value).Sum(x => x.Count() * (x.Count() - 1));
+      return (2.0 * (concordant - discordant)) / Math.Sqrt( (n * (n - 1) - ti * (ti - 1)) * (n * (n - 1) - uj * (uj - 1)) );
     }