Free cookie consent management tool by TermsFeed Policy Generator

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, 8 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
RevLine 
[13787]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
[13791]22using HeuristicLab.Collections;
[13787]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;
[13791]31    private readonly Dictionary<IRun, Dictionary<IAlgorithm, double>> performance;
32    private readonly BidirectionalDictionary<int, IRun> problemInstanceMap;
33    private readonly double[] medianValues;
[13787]34
[13791]35    public KNearestNeighborModel(int k, Dictionary<IRun, Dictionary<IAlgorithm, double>> perfData, string[] characteristics) {
[13787]36      this.K = k;
[13791]37      this.performance = perfData;
[13787]38      this.characteristics = characteristics;
[13791]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);
[13787]45    }
46
[13794]47    public IEnumerable<KeyValuePair<IAlgorithm, double>> GetRanking(IRun problemInstance) {
[13791]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 })
[13803]51                             .OrderBy(x => x.Feature.Select((f, i) => (f - feature[i]) * (f - feature[i])).Sum());
[13791]52     
[13803]53      var performances = new Dictionary<IAlgorithm, Performance>();
54
55      var k = 0;
[13791]56      foreach (var next in nearestK) {
[13803]57        if (k >= K) break;
[13791]58        var perfs = performance[problemInstanceMap.GetByFirst(next.ProblemInstanceIndex)];
59        if (perfs.Count == 0) continue;
60       
[13787]61        foreach (var p in perfs) {
62          var ert = p.Value;
[13803]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);
[13787]69        }
[13803]70
71        k++;
[13787]72      }
73
[13803]74      return performances.Select(x => new { Alg = x.Key, Perf = x.Value.ExpectedRuntime() })
[13787]75                         .OrderBy(x => x.Perf)
[13794]76                         .Select(x => new KeyValuePair<IAlgorithm, double>(x.Alg, x.Perf));
[13787]77    }
[13803]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    }
[13787]98  }
99}
Note: See TracBrowser for help on using the repository browser.