Changeset 13794 for branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/KnowledgeCenter.cs

Timestamp:

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

Author:

abeham

Message:

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

File:

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

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

@@ -718 +718 @@
         result[problemMap[pr.Key]] = new Dictionary<long, int>();
 
-        var indexMap = new BidirectionalDictionary<long, int>();
-        var perf = new Dictionary<long, double>();
-        var idx = 0;
-        foreach (var kvp in pr.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())) {
-          var ert = ExpectedRuntimeHelper.CalculateErt(kvp.ToList(), "QualityPerEvaluations", GetTarget(bkq, max), max).ExpectedRuntime;
-          if (double.IsNaN(ert)) {
-            // algorithm can't solve that instance with the given target
-            // these are put into their own additional class
-            result[problemMap[pr.Key]][kvp.Key] = nClasses;
-            continue;
-          }
-          indexMap.Add(kvp.Key, idx);
-          perf[kvp.Key] = Math.Log10(ert);
-          idx++;
-        }
-        if (perf.Count == 0) continue;
-        
-        var points = perf.OrderBy(x => indexMap.GetByFirst(x.Key)).Select(x => x.Value).ToArray();
-        int[] clusters;
-        Ckmeans1dClusters(points, nClasses, out clusters);
-        var ranks = clusters.Select((c, i) => new { Cluster = c, Perf = perf[indexMap.GetBySecond(i)] })
-                            .GroupBy(x => x.Cluster, x => x.Perf)
-                            .Select(x => new { Cluster = x.Key, AvgPerf = x.Average() })
-                            .OrderBy(x => x.AvgPerf)
-                            .Select((c, i) => new { Cluster = c.Cluster, Rank = i })
-                            .ToDictionary(x => x.Cluster, x => x.Rank);
-        for (var i = 0; i < clusters.Length; i++)
-          result[problemMap[pr.Key]][indexMap.GetBySecond(i)] = ranks[clusters[i]];
+        var values = pr.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())
+                       .ToDictionary(x => x.Key, x => ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerEvaluations", GetTarget(bkq, max), max).ExpectedRuntime);
+        var ranks = ClusteringHelper<long>.Cluster(nClasses, values, x => double.IsNaN(x.Value))
+          .GetByCluster().ToList();
+        var minRank = ranks.Min(x => x.Key);
+        foreach (var c in ranks) {
+          foreach (var a in c.Value)
+            result[problemMap[pr.Key]][a.Key] = c.Key == nClasses ? c.Key : c.Key - minRank;
+        }
       }
       return result;
@@ -772 +753 @@
     }
 
-    // implement further classes and methods
-    private static SortedList<double, int> Ckmeans1dClusters(double[] estimations, int k, out int[] clusterValues) {
-      int nPoints = estimations.Length;
-      var distinct = estimations.Distinct().OrderBy(x => x).ToArray();
-      var max = distinct.Max();
-      if (distinct.Length <= k) {
-        var dict = distinct.Select((v, i) => new { Index = i, Value = v }).ToDictionary(x => x.Value, y => y.Index);
-        for (int i = distinct.Length; i < k; i++)
-          dict.Add(max + i - distinct.Length + 1, i);
-
-        clusterValues = new int[nPoints];
-        for (int i = 0; i < nPoints; i++)
-          if (!dict.ContainsKey(estimations[i])) clusterValues[i] = 0;
-          else clusterValues[i] = dict[estimations[i]];
-
-        return new SortedList<double, int>(dict);
-      }
-
-      var n = distinct.Length;
-      var D = new double[n, k];
-      var B = new int[n, k];
-
-      for (int m = 0; m < k; m++) {
-        for (int j = m; j <= n - k + m; j++) {
-          if (m == 0)
-            D[j, m] = SumOfSquaredDistances(distinct, 0, j + 1);
-          else {
-            var minD = double.MaxValue;
-            var minI = 0;
-            for (int i = 1; i <= j; i++) {
-              var d = D[i - 1, m - 1] + SumOfSquaredDistances(distinct, i, j + 1);
-              if (d < minD) {
-                minD = d;
-                minI = i;
-              }
-            }
-            D[j, m] = minD;
-            B[j, m] = minI;
-          }
-        }
-      }
-
-      var centers = new SortedList<double, int>();
-      var upper = B[n - 1, k - 1];
-      var c = Mean(distinct, upper, n);
-      centers.Add(c, k - 1);
-      for (int i = k - 2; i >= 0; i--) {
-        var lower = B[upper - 1, i];
-        var c2 = Mean(distinct, lower, upper);
-        centers.Add(c2, i);
-        upper = lower;
-      }
-
-      clusterValues = new int[nPoints];
-      for (int i = 0; i < estimations.Length; i++) {
-        clusterValues[i] = centers.MinItems(x => Math.Abs(estimations[i] - x.Key)).First().Value;
-      }
-
-      return centers;
-    }
-
-    private static double SumOfSquaredDistances(double[] x, int start, int end) {
-      if (start == end) throw new InvalidOperationException();
-      if (start + 1 == end) return 0.0;
-      double mean = 0.0;
-      for (int i = start; i < end; i++) {
-        mean += x[i];
-      }
-      mean /= (end - start);
-      var sum = 0.0;
-      for (int i = start; i < end; i++) {
-        sum += (x[i] - mean) * (x[i] - mean);
-      }
-      return sum;
-    }
-
-    private static double Mean(double[] x, int start, int end) {
-      if (start == end) throw new InvalidOperationException();
-      double mean = 0.0;
-      for (int i = start; i < end; i++) {
-        mean += x[i];
-      }
-      mean /= (end - start);
-      return mean;
-    }
-
-    public IEnumerable<Tuple<IAlgorithm, double>> GetAlgorithmInstanceRanking() {
+    public IEnumerable<KeyValuePair<IAlgorithm, double>> GetAlgorithmInstanceRanking() {
       return RecommendationModel.GetRanking(ProblemInstances.Single(IsCurrentInstance));
     }