Changeset 13878

Timestamp:

06/07/16 16:29:59 (8 years ago)

Author:

abeham

Message:

#2457: added standardization of features for recommendation and using log10 of the expected runtime for clustering

Location:

branches/PerformanceComparison

Files:

• HeuristicLab.OptimizationExpertSystem.Common/3.3/KnowledgeCenter.cs (modified) (3 diffs)
• HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/KNearestNeighborModel.cs (modified) (3 diffs)
• HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/KNearestNeighborRecommender.cs (modified) (1 diff)
• HeuristicLab.OptimizationExpertSystem/3.3/Views/PerformanceModelingView.cs (modified) (3 diffs)

branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/KnowledgeCenter.cs

@@ -657 +657 @@
     }
 
+    public static double[][] GetFeaturesStandardized(IRun[] problemInstances, string[] characteristics, out double[] means, out double[] sdevs, double[] medianValues = null) {
+      var instances = new double[problemInstances.Length][];
+      var columns = new List<double>[characteristics.Length];
+      for (var p = 0; p < problemInstances.Length; p++) {
+        instances[p] = new double[characteristics.Length];
+        for (var f = 0; f < characteristics.Length; f++) {
+          if (columns[f] == null) {
+            columns[f] = new List<double>(problemInstances.Length);
+          }
+          IItem item;
+          if (problemInstances[p].Results.TryGetValue(characteristics[f], out item)) {
+            double val = 0;
+            var dItem = item as DoubleValue;
+            if (dItem != null) {
+              val = dItem.Value;
+            } else {
+              var iItem = item as IntValue;
+              if (iItem != null) val = iItem.Value;
+              else val = double.NaN;
+            }
+            if (double.IsNaN(val) && medianValues != null)
+              instances[p][f] = medianValues[f];
+            else instances[p][f] = val;
+            columns[f].Add(instances[p][f]);
+          } else instances[p][f] = medianValues != null ? medianValues[f] : double.NaN;
+        }
+      }
+
+      means = new double[characteristics.Length];
+      sdevs = new double[characteristics.Length];
+      for (var f = 0; f < characteristics.Length; f++) {
+        var mean = columns[f].Average();
+        var dev = columns[f].StandardDeviation();
+        means[f] = mean;
+        sdevs[f] = dev;
+        for (var p = 0; p < problemInstances.Length; p++) {
+          if (dev.IsAlmost(0)) instances[p][f] = 0;
+          else instances[p][f] = (instances[p][f] - mean) / dev;
+        }
+      }
+
+      return instances;
+    }
+
     public static double[] GetMedianValues(IRun[] problemInstances, string[] characteristics) {
       var values = new List<double>[characteristics.Length];
@@ -704 +748 @@
                           .GroupBy(x => algorithmId2AlgorithmInstanceMapping.GetByFirst(algorithmId2RunMapping.GetBySecond(x).Single()))
                           .ToDictionary(x => x.Key, x => ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerEvaluations", target, Maximization).ExpectedRuntime);
+    }
+
+    public Dictionary<IAlgorithm, double> GetAlgorithmPerformanceLog10(IRun problemInstance) {
+      if (!problemInstance.Parameters.ContainsKey("BestKnownQuality")) return new Dictionary<IAlgorithm, double>();
+      var target = GetTarget(((DoubleValue)problemInstance.Parameters["BestKnownQuality"]).Value, MinimumTarget.Value, Maximization);
+      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));
     }
 
@@ -802 +854 @@
 
         var values = pr.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())
-                       .ToDictionary(x => x.Key, x => ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerEvaluations", GetTarget(bkq, target, max), max).ExpectedRuntime);
+                       .ToDictionary(x => x.Key, x => Math.Log10(ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerEvaluations", GetTarget(bkq, target, max), max).ExpectedRuntime));
         var ranks = ClusteringHelper<long>.Cluster(nClasses, values, x => double.IsInfinity(x.Value))
           .GetByCluster().ToList();

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

@@ -21 +21 @@
 
 using HeuristicLab.Collections;
+using HeuristicLab.Common;
 using HeuristicLab.Optimization;
+using System;
 using System.Collections.Generic;
 using System.Linq;
@@ -46 +48 @@
 
     public IEnumerable<KeyValuePair<IAlgorithm, double>> GetRanking(IRun problemInstance) {
-      var features = KnowledgeCenter.GetFeatures(performance.Keys.OrderBy(problemInstanceMap.GetBySecond).ToArray(), characteristics, medianValues);
+      double[] means, sdevs;
+      var features = KnowledgeCenter.GetFeaturesStandardized(performance.Keys.OrderBy(problemInstanceMap.GetBySecond).ToArray(), characteristics, out means, out sdevs, medianValues);
       var feature = KnowledgeCenter.GetFeatures(new [] { problemInstance }, characteristics, medianValues)[0];
+      for (var f = 0; f < feature.Length; f++) {
+        if (sdevs[f].IsAlmost(0)) feature[f] = 0;
+        else feature[f] = (feature[f] - means[f]) / sdevs[f];
+      }
       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());
@@ -60 +67 @@
         
         foreach (var p in perfs) {
-          var ert = p.Value;
+          var ert = Math.Pow(10, p.Value);
           Performance perf;
           if (!performances.TryGetValue(p.Key, out perf)) {

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

@@ -49 +49 @@
 
     public IRecommendationModel TrainModel(IRun[] problemInstances, KnowledgeCenter kc, string[] characteristics) {
-      var perfData = problemInstances.Select(pi => new { ProblemInstance = pi, Performance = kc.GetAlgorithmPerformance(pi) })
+      var perfData = problemInstances.Select(pi => new { ProblemInstance = pi, Performance = kc.GetAlgorithmPerformanceLog10(pi) })
                                      .ToDictionary(x => x.ProblemInstance, x => x.Performance);
       return new KNearestNeighborModel(KParameter.Value.Value, perfData, characteristics);

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

@@ -186 +186 @@
         var count = 0;
         foreach (var pi in trainingSet) {
-          var observed = Content.GetAlgorithmPerformance(pi);
+          var observed = Content.GetAlgorithmPerformanceLog10(pi);
           if (observed.Count == 0) continue;
           progress.Status = pi.Name + "...";
           var model = recommender.TrainModel(trainingSet.Where(x => x != pi).ToArray(), Content, features);
-          var predictedTopN = model.GetRanking(pi).Take(topN).ToDictionary(x => x.Key, x => x.Value);
-          var predicted = model.GetRanking(pi).ToDictionary(x => x.Key, x => x.Value);
+          var predictedTopN = model.GetRanking(pi).Take(topN).ToDictionary(x => x.Key, x => Math.Log10(x.Value));
+          var predicted = model.GetRanking(pi).ToDictionary(x => x.Key, x => Math.Log10(x.Value));
           var ae = AbsoluteError(observed, predictedTopN);
           if (!double.IsNaN(ae)) {
@@ -240 +240 @@
         double actual;
         if (!performance.TryGetValue(tuple.Key, out actual)) continue;
-        if (double.IsInfinity(actual)) actual = int.MaxValue;
-        error += Math.Abs(actual - tuple.Value);
+        if (double.IsInfinity(actual)) actual = Math.Log10(int.MaxValue);
+        error += Math.Abs(Math.Pow(10, actual) - Math.Pow(10, tuple.Value));
         count++;
       }
@@ -253 +253 @@
         double actual;
         if (!performance.TryGetValue(tuple.Key, out actual)) continue;
-        if (double.IsInfinity(actual)) actual = int.MaxValue;
-        error += Math.Abs(Math.Log10(actual) - Math.Log10(tuple.Value));
+        if (double.IsInfinity(actual)) actual = Math.Log10(int.MaxValue);
+        error += Math.Abs(actual - tuple.Value);
         count++;
       }