Free cookie consent management tool by TermsFeed Policy Generator

Changeset 13803 for branches


Ignore:
Timestamp:
04/27/16 16:21:07 (9 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
Location:
branches/PerformanceComparison
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • branches/PerformanceComparison/HeuristicLab.Analysis/3.3/QualityAnalysis/ExpectedRuntimeHelper.cs

    r13774 r13803  
    1 using HeuristicLab.Optimization;
     1using HeuristicLab.Common;
     2using HeuristicLab.Optimization;
    23using System;
    34using System.Collections.Generic;
    … …  
    2425      }
    2526
    26       var ert = double.NaN;
     27      var ert = double.PositiveInfinity;
    2728
     29      var nRuns = successful.Count + unsuccessful.Count;
    2830      if (successful.Count > 0) {
    29         if (unsuccessful.Count == 0) ert = successful.Average();
    30         else {
    31           var ps = successful.Count / (double)(successful.Count + unsuccessful.Count);
    32           ert = successful.Average() + ((1.0 - ps) / ps) * unsuccessful.Average();
    33         }
     31        var succAvg = successful.Average();
     32        var succDev = successful.StandardDeviation();
     33        successful.RemoveAll(x => x < succAvg - 2 * succDev);
     34        unsuccessful.RemoveAll(x => x < succAvg - 2 * succDev);
     35        nRuns = successful.Count + unsuccessful.Count;
     36
     37        ert = successful.Average() / (successful.Count / (double)nRuns);
    3438      }
    35       return new ErtCalculationResult(successful.Count, (successful.Count + unsuccessful.Count), ert);
     39      return new ErtCalculationResult(successful.Count, nRuns, ert);
    3640    }
    3741

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

    r13797 r13803  
    654654          var bkq = ((DoubleValue)prob.Parameters["BestKnownQuality"]).Value;
    655655          var ert = ExpectedRuntimeHelper.CalculateErt(pr.ToList(), "QualityPerEvaluations", GetTarget(bkq, target, max), max).ExpectedRuntime;
    656           if (double.IsNaN(ert)) ert = int.MaxValue;
     656          if (double.IsInfinity(ert)) ert = int.MaxValue;
    657657          ds.AddRow(new object[] { pr.Key }.Concat(f.Cast<object>()).Concat(new object[] { ert }));
    658658        }
    … …  
    720720        var values = pr.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())
    721721                       .ToDictionary(x => x.Key, x => ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerEvaluations", GetTarget(bkq, target, max), max).ExpectedRuntime);
    722         var ranks = ClusteringHelper<long>.Cluster(nClasses, values, x => double.IsNaN(x.Value))
     722        var ranks = ClusteringHelper<long>.Cluster(nClasses, values, x => double.IsInfinity(x.Value))
    723723          .GetByCluster().ToList();
    724724        foreach (var c in ranks) {

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

    r13794 r13803  
    4949      var feature = KnowledgeCenter.GetFeatures(new [] { problemInstance }, characteristics, medianValues)[0];
    5050      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                              .Take(K);
     51                             .OrderBy(x => x.Feature.Select((f, i) => (f - feature[i]) * (f - feature[i])).Sum());
    5352     
    54       var performances = new Dictionary<IAlgorithm, List<double>>();
     53      var performances = new Dictionary<IAlgorithm, Performance>();
     54
     55      var k = 0;
    5556      foreach (var next in nearestK) {
     57        if (k >= K) break;
    5658        var perfs = performance[problemInstanceMap.GetByFirst(next.ProblemInstanceIndex)];
    5759        if (perfs.Count == 0) continue;
    … …  
    5961        foreach (var p in perfs) {
    6062          var ert = p.Value;
    61           if (double.IsNaN(ert)) ert = int.MaxValue;
    62           List<double> erts;
    63           if (!performances.TryGetValue(p.Key, out erts)) {
    64             performances[p.Key] = new List<double>() { ert }; ;
    65           } else erts.Add(ert);
     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);
    6669        }
     70
     71        k++;
    6772      }
    6873
    69       return performances.Select(x => new { Alg = x.Key, Perf = x.Value.Average() })
     74      return performances.Select(x => new { Alg = x.Key, Perf = x.Value.ExpectedRuntime() })
    7075                         .OrderBy(x => x.Perf)
    7176                         .Select(x => new KeyValuePair<IAlgorithm, double>(x.Alg, x.Perf));
    7277    }
     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    }
    7398  }
    7499}

  • branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/OverallBestRecommender.cs

    r13797 r13803  
    6363          if (!pis.TryGetValue(problemRuns.Key, out bkq)) continue;
    6464          var ert = ExpectedRuntimeHelper.CalculateErt(problemRuns.ToList(), "QualityPerEvaluations", kc.GetTarget(bkq, kc.MinimumTarget.Value, kc.Maximization), kc.Maximization).ExpectedRuntime;
    65           if (double.IsNaN(ert)) ert = int.MaxValue;
     65          if (double.IsInfinity(ert)) ert = int.MaxValue;
    6666          avgERT += ert;
    6767          count++;

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

    r13797 r13803  
    5555      this.parameterCollectionView = new HeuristicLab.Core.Views.ParameterCollectionView();
    5656      this.crossvalidationTabPage = new System.Windows.Forms.TabPage();
     57      this.topNComboBox = new System.Windows.Forms.ComboBox();
     58      this.topNlabel = new System.Windows.Forms.Label();
    5759      this.kendallsTauLabel = new System.Windows.Forms.Label();
    5860      this.predictedLabel = new System.Windows.Forms.Label();
    59       this.actualLabel = new System.Windows.Forms.Label();
    6061      this.absoluteLogErrorLabel = new System.Windows.Forms.Label();
    6162      this.absoluteErrorLabel = new System.Windows.Forms.Label();
    … …  
    6768      this.minTargetView = new HeuristicLab.Data.Views.StringConvertibleValueView();
    6869      this.minimumTargetLabel = new System.Windows.Forms.Label();
     70      this.ncdgView = new HeuristicLab.Data.Views.StringConvertibleValueView();
     71      this.ndcgLabel = new System.Windows.Forms.Label();
    6972      this.tabControl.SuspendLayout();
    7073      this.characteristicsTabPage.SuspendLayout();
    … …  
    139142      this.characteristicsViewHost.Name = "characteristicsViewHost";
    140143      this.characteristicsViewHost.ReadOnly = false;
    141       this.characteristicsViewHost.Size = new System.Drawing.Size(680, 283);
     144      this.characteristicsViewHost.Size = new System.Drawing.Size(940, 442);
    142145      this.characteristicsViewHost.TabIndex = 1;
    143146      this.characteristicsViewHost.ViewsLabelVisible = true;
    … …  
    180183      // crossvalidationTabPage
    181184      //
     185      this.crossvalidationTabPage.Controls.Add(this.topNComboBox);
     186      this.crossvalidationTabPage.Controls.Add(this.topNlabel);
     187      this.crossvalidationTabPage.Controls.Add(this.ndcgLabel);
    182188      this.crossvalidationTabPage.Controls.Add(this.kendallsTauLabel);
    183189      this.crossvalidationTabPage.Controls.Add(this.predictedLabel);
    184       this.crossvalidationTabPage.Controls.Add(this.actualLabel);
    185190      this.crossvalidationTabPage.Controls.Add(this.absoluteLogErrorLabel);
    186191      this.crossvalidationTabPage.Controls.Add(this.absoluteErrorLabel);
     192      this.crossvalidationTabPage.Controls.Add(this.ncdgView);
    187193      this.crossvalidationTabPage.Controls.Add(this.kendallsTauView);
    188194      this.crossvalidationTabPage.Controls.Add(this.absoluteLogErrorView);
    … …  
    198204      this.crossvalidationTabPage.UseVisualStyleBackColor = true;
    199205      //
     206      // topNComboBox
     207      //
     208      this.topNComboBox.DropDownStyle = System.Windows.Forms.ComboBoxStyle.DropDownList;
     209      this.topNComboBox.FormattingEnabled = true;
     210      this.topNComboBox.Location = new System.Drawing.Point(331, 9);
     211      this.topNComboBox.Name = "topNComboBox";
     212      this.topNComboBox.Size = new System.Drawing.Size(76, 21);
     213      this.topNComboBox.TabIndex = 5;
     214      this.topNComboBox.SelectedIndexChanged += new System.EventHandler(this.topNComboBox_SelectedIndexChanged);
     215      //
     216      // topNlabel
     217      //
     218      this.topNlabel.AutoSize = true;
     219      this.topNlabel.Location = new System.Drawing.Point(192, 12);
     220      this.topNlabel.Name = "topNlabel";
     221      this.topNlabel.Size = new System.Drawing.Size(133, 13);
     222      this.topNlabel.TabIndex = 4;
     223      this.topNlabel.Text = "Evaluate only best ranked:";
     224      //
    200225      // kendallsTauLabel
    201226      //
    202227      this.kendallsTauLabel.AutoSize = true;
    203       this.kendallsTauLabel.Location = new System.Drawing.Point(519, 165);
     228      this.kendallsTauLabel.Location = new System.Drawing.Point(519, 224);
    204229      this.kendallsTauLabel.Margin = new System.Windows.Forms.Padding(3);
    205230      this.kendallsTauLabel.Name = "kendallsTauLabel";
    … …  
    219244      this.predictedLabel.Text = "PREDICTED";
    220245      //
    221       // actualLabel
    222       //
    223       this.actualLabel.AutoSize = true;
    224       this.actualLabel.Font = new System.Drawing.Font("Microsoft Sans Serif", 8.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
    225       this.actualLabel.Location = new System.Drawing.Point(16, 155);
    226       this.actualLabel.Margin = new System.Windows.Forms.Padding(3);
    227       this.actualLabel.Name = "actualLabel";
    228       this.actualLabel.Size = new System.Drawing.Size(15, 78);
    229       this.actualLabel.TabIndex = 3;
    230       this.actualLabel.Text = "A\r\nC\r\nT\r\nU\r\nA\r\nL";
    231       //
    232246      // absoluteLogErrorLabel
    233247      //
    … …  
    236250      this.absoluteLogErrorLabel.Margin = new System.Windows.Forms.Padding(3);
    237251      this.absoluteLogErrorLabel.Name = "absoluteLogErrorLabel";
    238       this.absoluteLogErrorLabel.Size = new System.Drawing.Size(127, 13);
     252      this.absoluteLogErrorLabel.Size = new System.Drawing.Size(162, 13);
    239253      this.absoluteLogErrorLabel.TabIndex = 3;
    240       this.absoluteLogErrorLabel.Text = "Mean Absolute Log Error:";
     254      this.absoluteLogErrorLabel.Text = "Mean Absolute Log Error (top N):";
    241255      //
    242256      // absoluteErrorLabel
    … …  
    246260      this.absoluteErrorLabel.Margin = new System.Windows.Forms.Padding(3);
    247261      this.absoluteErrorLabel.Name = "absoluteErrorLabel";
    248       this.absoluteErrorLabel.Size = new System.Drawing.Size(106, 13);
     262      this.absoluteErrorLabel.Size = new System.Drawing.Size(141, 13);
    249263      this.absoluteErrorLabel.TabIndex = 3;
    250       this.absoluteErrorLabel.Text = "Mean Absolute Error:";
     264      this.absoluteErrorLabel.Text = "Mean Absolute Error (top N):";
    251265      //
    252266      // kendallsTauView
    … …  
    255269      this.kendallsTauView.Content = null;
    256270      this.kendallsTauView.LabelVisible = false;
    257       this.kendallsTauView.Location = new System.Drawing.Point(503, 184);
     271      this.kendallsTauView.Location = new System.Drawing.Point(503, 243);
    258272      this.kendallsTauView.Name = "kendallsTauView";
    259273      this.kendallsTauView.ReadOnly = true;
    … …  
    292306      this.confusionMatrixView.ShowRowsAndColumnsTextBox = false;
    293307      this.confusionMatrixView.ShowStatisticalInformation = false;
    294       this.confusionMatrixView.Size = new System.Drawing.Size(438, 244);
     308      this.confusionMatrixView.Size = new System.Drawing.Size(438, 134);
    295309      this.confusionMatrixView.TabIndex = 1;
    296310      //
    … …  
    324338      this.minimumTargetLabel.TabIndex = 17;
    325339      this.minimumTargetLabel.Text = "Target:";
     340      //
     341      // ncdgView
     342      //
     343      this.ncdgView.Caption = "StringConvertibleValue View";
     344      this.ncdgView.Content = null;
     345      this.ncdgView.LabelVisible = false;
     346      this.ncdgView.Location = new System.Drawing.Point(503, 184);
     347      this.ncdgView.Name = "ncdgView";
     348      this.ncdgView.ReadOnly = true;
     349      this.ncdgView.Size = new System.Drawing.Size(194, 21);
     350      this.ncdgView.TabIndex = 2;
     351      //
     352      // ndcgLabel
     353      //
     354      this.ndcgLabel.AutoSize = true;
     355      this.ndcgLabel.Location = new System.Drawing.Point(519, 165);
     356      this.ndcgLabel.Margin = new System.Windows.Forms.Padding(3);
     357      this.ndcgLabel.Name = "ndcgLabel";
     358      this.ndcgLabel.Size = new System.Drawing.Size(106, 13);
     359      this.ndcgLabel.TabIndex = 3;
     360      this.ndcgLabel.Text = "Mean NDCG (top N):";
    326361      //
    327362      // PerformanceModelingView
    … …  
    368403    private Data.Views.StringConvertibleMatrixView confusionMatrixView;
    369404    private System.Windows.Forms.Label predictedLabel;
    370     private System.Windows.Forms.Label actualLabel;
    371405    private System.Windows.Forms.Label absoluteLogErrorLabel;
    372406    private Data.Views.StringConvertibleValueView absoluteLogErrorView;
     407    private System.Windows.Forms.ComboBox topNComboBox;
     408    private System.Windows.Forms.Label topNlabel;
     409    private System.Windows.Forms.Label ndcgLabel;
     410    private Data.Views.StringConvertibleValueView ncdgView;
    373411  }
    374412}

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

    r13797 r13803  
    5959      }
    6060      UpdateCharacteristics();
     61      UpdateTopNCombobox();
    6162    }
    6263
    … …  
    6667      recommendStartButton.Enabled = Content != null && recommenderComboBox.SelectedIndex >= 0 && characteristics.CheckedItems.Any();
    6768      characteristicsViewHost.Enabled = Content != null;
    68       xValidateButton.Enabled = Content != null && recommenderComboBox.SelectedIndex >= 0 && characteristics.CheckedItems.Any();
     69      xValidateButton.Enabled = Content != null && recommenderComboBox.SelectedIndex >= 0 && characteristics.CheckedItems.Any() && topNComboBox.SelectedIndex >= 0;
    6970    }
    7071
    … …  
    101102      }
    102103    }
     104
     105    private void UpdateTopNCombobox() {
     106      if (InvokeRequired) { Invoke((Action)UpdateTopNCombobox); return; }
     107
     108      int selected = 3;
     109      if (topNComboBox.SelectedIndex >= 0) selected = (int)topNComboBox.SelectedItem;
     110      topNComboBox.Items.Clear();
     111      if (Content == null) return;
     112
     113      var algInstances = Content.AlgorithmInstances.Count;
     114      for (var i = 1; i <= algInstances; i++) {
     115        topNComboBox.Items.Add(i);
     116      }
     117      topNComboBox.SelectedIndex = Math.Min(selected, topNComboBox.Items.Count) - 1;
     118    }
    103119    #endregion
    104120
    … …  
    108124      UpdateCharacteristics();
    109125      SetEnabledStateOfControls();
     126    }
     127
     128    protected override void OnAlgorithmInstancesChanged() {
     129      base.OnAlgorithmInstancesChanged();
     130      UpdateTopNCombobox();
    110131    }
    111132    #endregion
    … …  
    133154      var recommender = (IAlgorithmInstanceRecommender)recommenderComboBox.SelectedItem;
    134155      var progress = MainForm.AddOperationProgressToView(this, "Performing Leave-one-out Crossvalidation");
    135 
    136       Task.Factory.StartNew(() => { DoCrossvalidate(recommender, progress); }, TaskCreationOptions.LongRunning);
    137     }
    138 
    139     private void DoCrossvalidate(IAlgorithmInstanceRecommender recommender, IProgress progress) {
    140       var features = characteristics.CheckedItems.Select(x => x.Value.Value).ToArray();
    141       var trainingSet = Content.ProblemInstances.Where(x => !Content.IsCurrentInstance(x)).ToArray();
    142 
    143       var absErr = 0.0;
    144       var absLogError = 0.0;
    145       var confMatrix = new int[6, 6];
    146       var tau = 0.0;
    147       // leave one out crossvalidation
    148       var count = 0;
    149       foreach (var pi in trainingSet) {
    150         progress.Status = pi.Name + "...";
    151         var model = recommender.TrainModel(trainingSet.Where(x => x != pi).ToArray(), Content, features);
    152         var predicted = model.GetRanking(pi).ToDictionary(x => x.Key, x => x.Value);
    153         var observed = Content.GetAlgorithmPerformance(pi);
    154         absErr += AbsoluteError(observed, predicted);
    155         absLogError += AbsoluteLogError(observed, predicted);
    156         var confMat = ConfusionMatrix(observed, predicted);
    157         for (var i = 0; i < confMat.GetLength(0); i++) {
    158           for (var j = 0; j < confMat.GetLength(1); j++)
    159             confMatrix[i, j] += confMat[i, j];
     156      var topN = (int)topNComboBox.SelectedItem;
     157      Task.Factory.StartNew(() => { DoCrossvalidate(recommender, topN, progress); }, TaskCreationOptions.LongRunning);
     158    }
     159
     160    private void topNComboBox_SelectedIndexChanged(object sender, EventArgs e) {
     161      SetEnabledStateOfControls();
     162    }
     163    #endregion
     164
     165    #region Other Event Handlers
     166    private void CharacteristicsOnCheckedItemsChanged(object sender, EventArgs e) {
     167      SetEnabledStateOfControls();
     168    }
     169    #endregion
     170   
     171    private void DoCrossvalidate(IAlgorithmInstanceRecommender recommender, int topN, IProgress progress) {
     172      try {
     173        var features = characteristics.CheckedItems.Select(x => x.Value.Value).ToArray();
     174        var trainingSet = Content.ProblemInstances.Where(x => !Content.IsCurrentInstance(x)).ToArray();
     175
     176        var absErr = 0.0;
     177        var absErrCnt = 0;
     178        var absLogErr = 0.0;
     179        var absLogErrCnt = 0;
     180        var confMatrix = new int[1, 6];
     181        var tau = 0.0;
     182        var tauCnt = 0;
     183        var ndcg = 0.0;
     184        var ndcgCnt = 0;
     185        // leave one out crossvalidation
     186        var count = 0;
     187        foreach (var pi in trainingSet) {
     188          var observed = Content.GetAlgorithmPerformance(pi);
     189          if (observed.Count == 0) continue;
     190          progress.Status = pi.Name + "...";
     191          var model = recommender.TrainModel(trainingSet.Where(x => x != pi).ToArray(), Content, features);
     192          var predictedTopN = model.GetRanking(pi).Take(topN).ToDictionary(x => x.Key, x => x.Value);
     193          var predicted = model.GetRanking(pi).ToDictionary(x => x.Key, x => x.Value);
     194          var ae = AbsoluteError(observed, predictedTopN);
     195          if (!double.IsNaN(ae)) {
     196            absErr += ae; // in case we only predicted instances that have not been observed
     197            absErrCnt++;
     198          }
     199          var ale = AbsoluteLogError(observed, predictedTopN);
     200          if (!double.IsNaN(ale)) {
     201            absLogErr += ale; // in case we only predicted instances that have not been observed
     202            absLogErrCnt++;
     203          }
     204          var confMat = ConfusionMatrix(observed, predictedTopN);
     205          for (var i = 0; i < confMat.Length; i++) {
     206            confMatrix[0, i] += confMat[i];
     207          }
     208          var kt = KendallsTau(observed, predicted);
     209          if (!double.IsNaN(kt)) {
     210            tau += kt;
     211            tauCnt++;
     212          }
     213          var gain = NDCG(observed, model.GetRanking(pi).Take(topN).Select(x => x.Key).ToList());
     214          if (!double.IsNaN(gain)) {
     215            ndcg += gain;
     216            ndcgCnt++;
     217          }
     218          // mean reciprocal rank
     219          // optional: expected reciprocal rank
     220          progress.ProgressValue = ++count / (double)trainingSet.Length;
    160221        }
    161         tau += KendallsTau(observed, predicted);
    162         // average NCDG ... relevance determined by clustering (unsuccessful algorithms being penalized with negative relevance)
    163         // mean reciprocal rank
    164         // optional: expected reciprocal rank
    165         progress.ProgressValue = ++count / (double)trainingSet.Length;
    166       }
    167       absErr /= trainingSet.Length;
    168       absLogError /= trainingSet.Length;
    169       tau /= trainingSet.Length;
    170 
    171       absoluteErrorView.Content = new DoubleValue(absErr);
    172       absoluteLogErrorView.Content = new DoubleValue(absLogError);
    173       var description = new[] { "A", "B", "C", "D", "E", "F" };
    174       confusionMatrixView.Content = new IntMatrix(confMatrix) { ColumnNames = description, RowNames = description };
    175       kendallsTauView.Content = new DoubleValue(tau);
    176 
    177       progress.Finish();
     222        absErr /= absErrCnt;
     223        absLogErr /= absLogErrCnt;
     224        tau /= tauCnt;
     225        ndcg /= ndcgCnt;
     226
     227        absoluteErrorView.Content = new DoubleValue(absErr);
     228        absoluteLogErrorView.Content = new DoubleValue(absLogErr);
     229        var description = new[] {"A", "B", "C", "D", "E", "F"};
     230        confusionMatrixView.Content = new IntMatrix(confMatrix) {ColumnNames = description};
     231        kendallsTauView.Content = new DoubleValue(tau);
     232        ncdgView.Content = new DoubleValue(ndcg);
     233      } finally { progress.Finish(); }
    178234    }
    179235
    180236    private static double AbsoluteError(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
    181237      var error = 0.0;
     238      var count = 0;
    182239      foreach (var tuple in ranking) {
    183240        double actual;
    184241        if (!performance.TryGetValue(tuple.Key, out actual)) continue;
    185         if (double.IsNaN(actual)) actual = int.MaxValue;
     242        if (double.IsInfinity(actual)) actual = int.MaxValue;
    186243        error += Math.Abs(actual - tuple.Value);
    187       }
    188       return error;
     244        count++;
     245      }
     246      return error / count;
    189247    }
    190248
    191249    private static double AbsoluteLogError(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
    192250      var error = 0.0;
     251      var count = 0;
    193252      foreach (var tuple in ranking) {
    194253        double actual;
    195254        if (!performance.TryGetValue(tuple.Key, out actual)) continue;
    196         if (double.IsNaN(actual)) actual = int.MaxValue;
     255        if (double.IsInfinity(actual)) actual = int.MaxValue;
    197256        error += Math.Abs(Math.Log10(actual) - Math.Log10(tuple.Value));
    198       }
    199       return error;
    200     }
    201 
    202     private static int[,] ConfusionMatrix(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
    203       var confMatrix = new int[6,6];
    204       var clusteredPerformance = ClusteringHelper<IAlgorithm>.Cluster(5, performance, a => double.IsNaN(a.Value)).GetByInstance().ToDictionary(x => x.Key, x => x.Value.Item2);
    205       var clusteredRanks = ClusteringHelper<IAlgorithm>.Cluster(5, ranking, x => double.IsNaN(x.Value) || x.Value >= int.MaxValue).GetByInstance().ToDictionary(x => x.Key, x => x.Value.Item2);
    206       foreach (var cr in clusteredRanks) {
     257        count++;
     258      }
     259      return error / count;
     260    }
     261
     262    private static int[] ConfusionMatrix(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
     263      var confMatrix = new int[6];
     264      var clusteredPerformance = ClusteringHelper<IAlgorithm>.Cluster(5, performance, a => double.IsInfinity(a.Value)).GetByInstance().ToDictionary(x => x.Key, x => x.Value.Item2);
     265     
     266      foreach (var cr in ranking) {
    207267        int realRank;
    208268        if (!clusteredPerformance.TryGetValue(cr.Key, out realRank)) continue;
    209         confMatrix[realRank, cr.Value]++;
     269        confMatrix[realRank]++;
    210270      }
    211271      return confMatrix;
    … …  
    215275      var commonKeys = performance.Keys.Intersect(ranking.Keys).ToList();
    216276      var n = commonKeys.Count;
    217       if (n == 0) return 0.0;
     277      if (n == 0) return double.NaN;
    218278
    219279      var actualRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = performance[x] })
    … …  
    223283                                     .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = i })
    224284                                     .OrderBy(x => x.Index).Select(x => x.Rank).ToList();
    225      
     285
    226286      var paired = actualRanks.Zip(predictedRanks, (a, p) => new { Actual = a, Predicted = p }).ToList();
    227287      var concordant = 0;
    228288      var discordant = 0;
    229289      for (var i = 0; i < paired.Count - 1; i++)
    230         for (var j = 0; j < paired.Count; j++) {
     290        for (var j = i + 1; j < paired.Count; j++) {
    231291          if (paired[i].Actual > paired[j].Actual && paired[i].Predicted > paired[j].Predicted
    232292            || paired[i].Actual < paired[j].Actual && paired[i].Predicted < paired[j].Predicted)
    … …  
    236296      return (2.0 * (concordant - discordant)) / (n * (n - 1));
    237297    }
    238     #endregion
    239 
    240     #region Other Event Handlers
    241     private void CharacteristicsOnCheckedItemsChanged(object sender, EventArgs e) {
    242       SetEnabledStateOfControls();
    243     }
    244     #endregion
     298
     299    private static double NDCG(Dictionary<IAlgorithm, double> performance, List<IAlgorithm> ranking) {
     300      var k = 5;
     301      var relevance = ClusteringHelper<IAlgorithm>.Cluster(k, performance, a => double.IsInfinity(a.Value)).GetByInstance().ToDictionary(x => x.Key, x => k - x.Value.Item2);
     302     
     303      var i = 0;
     304      var dcgp = 0.0;
     305      for (; i < ranking.Count; i++) {
     306        int rel;
     307        if (!relevance.TryGetValue(ranking[i], out rel))
     308          continue;
     309        dcgp = rel;
     310        i++;
     311        break;
     312      }
     313      for (; i < ranking.Count; i++) {
     314        int rel;
     315        if (!relevance.TryGetValue(ranking[i], out rel))
     316          continue;
     317        dcgp += rel / Math.Log(i + 1, 2);
     318      }
     319      var ideal = relevance.Select(x => x.Value).OrderByDescending(x => x).Take(ranking.Count).ToArray();
     320      double idcgp = ideal[0];
     321      for (i = 1; i < ideal.Length; i++)
     322        idcgp += ideal[i] / Math.Log(i + 1, 2);
     323
     324      return dcgp / idcgp;
     325    }
    245326  }
    246327}
Note: See TracChangeset for help on using the changeset viewer.