Changeset 13803 for branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/KNearestNeighborModel.cs

Timestamp:

04/27/16 16:21:07 (8 years ago)

Author:

abeham

Message:

#2457:

• changed expected runtime calculation
  • now outputs positive infinity instead of nan when no run was successful
  • now filters outliers in successful and unsuccessful runs by using two standard deviations of the mean of successful runs as lower bound
    • this change allows having unsuccessful runs in the database with low evaluations / runtime (e.g. due to being aborted early or from an experiment where the max budget was lower)
• worked on recommendation algorithms
  • implemented several performance measures (absolute error, absolute log error, ndcp, kendall's tau) to evaluate the ranking

File:

• branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/KNearestNeighborModel.cs (modified) (2 diffs)

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/KNearestNeighborModel.cs

@@ -49 +49 @@
       var feature = KnowledgeCenter.GetFeatures(new [] { problemInstance }, characteristics, medianValues)[0];
       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())
-                             .Take(K);
+                             .OrderBy(x => x.Feature.Select((f, i) => (f - feature[i]) * (f - feature[i])).Sum());
       
-      var performances = new Dictionary<IAlgorithm, List<double>>();
+      var performances = new Dictionary<IAlgorithm, Performance>();
+
+      var k = 0;
       foreach (var next in nearestK) {
+        if (k >= K) break;
         var perfs = performance[problemInstanceMap.GetByFirst(next.ProblemInstanceIndex)];
         if (perfs.Count == 0) continue;
@@ -59 +61 @@
         foreach (var p in perfs) {
           var ert = p.Value;
-          if (double.IsNaN(ert)) ert = int.MaxValue;
-          List<double> erts;
-          if (!performances.TryGetValue(p.Key, out erts)) {
-            performances[p.Key] = new List<double>() { ert }; ;
-          } else erts.Add(ert);
+          Performance perf;
+          if (!performances.TryGetValue(p.Key, out perf)) {
+            perf = new Performance();
+            performances[p.Key] = perf;
+          }
+          perf.Add(ert);
         }
+
+        k++;
       }
 
-      return performances.Select(x => new { Alg = x.Key, Perf = x.Value.Average() })
+      return performances.Select(x => new { Alg = x.Key, Perf = x.Value.ExpectedRuntime() })
                          .OrderBy(x => x.Perf)
                          .Select(x => new KeyValuePair<IAlgorithm, double>(x.Alg, x.Perf));
     }
+
+    private class Performance {
+      private readonly List<double> successful;
+      private int runs;
+      public int Fails { get { return runs - successful.Count; } }
+
+      public Performance() {
+        successful = new List<double>();
+      }
+
+      public void Add(double ert) {
+        if (!double.IsInfinity(ert)) successful.Add(ert);
+        runs++;
+      }
+
+      public double ExpectedRuntime() {
+        if (successful.Count == 0) return int.MaxValue;
+        return successful.Average() / (successful.Count / (double)runs);
+      }
+    }
   }
 }