source: branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/KNearestNeighborModel.cs @ 13803

Last change on this file since 13803 was 13803, checked in by abeham, 3 years ago

#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 size: 3.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using HeuristicLab.Collections;
23using HeuristicLab.Optimization;
24using System.Collections.Generic;
25using System.Linq;
26
27namespace HeuristicLab.OptimizationExpertSystem.Common {
28  public class KNearestNeighborModel : IRecommendationModel {
29    private readonly int K;
30    private readonly string[] characteristics;
31    private readonly Dictionary<IRun, Dictionary<IAlgorithm, double>> performance;
32    private readonly BidirectionalDictionary<int, IRun> problemInstanceMap; 
33    private readonly double[] medianValues;
34
35    public KNearestNeighborModel(int k, Dictionary<IRun, Dictionary<IAlgorithm, double>> perfData, string[] characteristics) {
36      this.K = k;
37      this.performance = perfData;
38      this.characteristics = characteristics;
39      problemInstanceMap = new BidirectionalDictionary<int, IRun>();
40      var i = 0;
41      foreach (var pi in perfData.Keys) {
42        problemInstanceMap.Add(i++, pi);
43      }
44      this.medianValues = KnowledgeCenter.GetMedianValues(perfData.Keys.OrderBy(problemInstanceMap.GetBySecond).ToArray(), characteristics);
45    }
46
47    public IEnumerable<KeyValuePair<IAlgorithm, double>> GetRanking(IRun problemInstance) {
48      var features = KnowledgeCenter.GetFeatures(performance.Keys.OrderBy(problemInstanceMap.GetBySecond).ToArray(), characteristics, medianValues);
49      var feature = KnowledgeCenter.GetFeatures(new [] { problemInstance }, characteristics, medianValues)[0];
50      var nearestK = features.Select((f, i) => new { ProblemInstanceIndex = i, Feature = f })
51                             .OrderBy(x => x.Feature.Select((f, i) => (f - feature[i]) * (f - feature[i])).Sum());
52     
53      var performances = new Dictionary<IAlgorithm, Performance>();
54
55      var k = 0;
56      foreach (var next in nearestK) {
57        if (k >= K) break;
58        var perfs = performance[problemInstanceMap.GetByFirst(next.ProblemInstanceIndex)];
59        if (perfs.Count == 0) continue;
60       
61        foreach (var p in perfs) {
62          var ert = p.Value;
63          Performance perf;
64          if (!performances.TryGetValue(p.Key, out perf)) {
65            perf = new Performance();
66            performances[p.Key] = perf;
67          }
68          perf.Add(ert);
69        }
70
71        k++;
72      }
73
74      return performances.Select(x => new { Alg = x.Key, Perf = x.Value.ExpectedRuntime() })
75                         .OrderBy(x => x.Perf)
76                         .Select(x => new KeyValuePair<IAlgorithm, double>(x.Alg, x.Perf));
77    }
78
79    private class Performance {
80      private readonly List<double> successful;
81      private int runs;
82      public int Fails { get { return runs - successful.Count; } }
83
84      public Performance() {
85        successful = new List<double>();
86      }
87
88      public void Add(double ert) {
89        if (!double.IsInfinity(ert)) successful.Add(ert);
90        runs++;
91      }
92
93      public double ExpectedRuntime() {
94        if (successful.Count == 0) return int.MaxValue;
95        return successful.Average() / (successful.Count / (double)runs);
96      }
97    }
98  }
99}
Note: See TracBrowser for help on using the repository browser.