Changeset 13794


Ignore:
Timestamp:
04/26/16 00:02:05 (5 years ago)
Author:
abeham
Message:

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

Location:
branches/PerformanceComparison
Files:
3 added
9 edited

Legend:

Unmodified
Added
Removed
  • branches/PerformanceComparison/HeuristicLab.Analysis/3.3/HeuristicLab.Analysis-3.3.csproj

    r13750 r13794  
    187187    <Compile Include="BestNScopesSolutionAnalyzer.cs" />
    188188    <Compile Include="BestScopeSolutionAnalyzer.cs" />
     189    <Compile Include="Clustering\CkMeans1D.cs">
     190      <SubType>Code</SubType>
     191    </Compile>
     192    <Compile Include="Clustering\ClusterHelper.cs" />
    189193    <Compile Include="DataVisualization\IndexedDataRow.cs" />
    190194    <Compile Include="DataVisualization\IndexedDataTable.cs" />
  • branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Interfaces/IRecommendationModel.cs

    r13791 r13794  
    2222using HeuristicLab.Common;
    2323using HeuristicLab.Optimization;
    24 using System;
    2524using System.Collections.Generic;
    2625
    2726namespace HeuristicLab.OptimizationExpertSystem.Common {
    2827  public interface IRecommendationModel : IContent {
    29     IEnumerable<Tuple<IAlgorithm, double>> GetRanking(IRun problemInstance);
     28    IEnumerable<KeyValuePair<IAlgorithm, double>> GetRanking(IRun problemInstance);
    3029  }
    3130}
  • branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/KnowledgeCenter.cs

    r13791 r13794  
    718718        result[problemMap[pr.Key]] = new Dictionary<long, int>();
    719719
    720         var indexMap = new BidirectionalDictionary<long, int>();
    721         var perf = new Dictionary<long, double>();
    722         var idx = 0;
    723         foreach (var kvp in pr.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())) {
    724           var ert = ExpectedRuntimeHelper.CalculateErt(kvp.ToList(), "QualityPerEvaluations", GetTarget(bkq, max), max).ExpectedRuntime;
    725           if (double.IsNaN(ert)) {
    726             // algorithm can't solve that instance with the given target
    727             // these are put into their own additional class
    728             result[problemMap[pr.Key]][kvp.Key] = nClasses;
    729             continue;
    730           }
    731           indexMap.Add(kvp.Key, idx);
    732           perf[kvp.Key] = Math.Log10(ert);
    733           idx++;
    734         }
    735         if (perf.Count == 0) continue;
    736        
    737         var points = perf.OrderBy(x => indexMap.GetByFirst(x.Key)).Select(x => x.Value).ToArray();
    738         int[] clusters;
    739         Ckmeans1dClusters(points, nClasses, out clusters);
    740         var ranks = clusters.Select((c, i) => new { Cluster = c, Perf = perf[indexMap.GetBySecond(i)] })
    741                             .GroupBy(x => x.Cluster, x => x.Perf)
    742                             .Select(x => new { Cluster = x.Key, AvgPerf = x.Average() })
    743                             .OrderBy(x => x.AvgPerf)
    744                             .Select((c, i) => new { Cluster = c.Cluster, Rank = i })
    745                             .ToDictionary(x => x.Cluster, x => x.Rank);
    746         for (var i = 0; i < clusters.Length; i++)
    747           result[problemMap[pr.Key]][indexMap.GetBySecond(i)] = ranks[clusters[i]];
     720        var values = pr.GroupBy(x => algorithmId2RunMapping.GetBySecond(x).Single())
     721                       .ToDictionary(x => x.Key, x => ExpectedRuntimeHelper.CalculateErt(x.ToList(), "QualityPerEvaluations", GetTarget(bkq, max), max).ExpectedRuntime);
     722        var ranks = ClusteringHelper<long>.Cluster(nClasses, values, x => double.IsNaN(x.Value))
     723          .GetByCluster().ToList();
     724        var minRank = ranks.Min(x => x.Key);
     725        foreach (var c in ranks) {
     726          foreach (var a in c.Value)
     727            result[problemMap[pr.Key]][a.Key] = c.Key == nClasses ? c.Key : c.Key - minRank;
     728        }
    748729      }
    749730      return result;
     
    772753    }
    773754
    774     // implement further classes and methods
    775     private static SortedList<double, int> Ckmeans1dClusters(double[] estimations, int k, out int[] clusterValues) {
    776       int nPoints = estimations.Length;
    777       var distinct = estimations.Distinct().OrderBy(x => x).ToArray();
    778       var max = distinct.Max();
    779       if (distinct.Length <= k) {
    780         var dict = distinct.Select((v, i) => new { Index = i, Value = v }).ToDictionary(x => x.Value, y => y.Index);
    781         for (int i = distinct.Length; i < k; i++)
    782           dict.Add(max + i - distinct.Length + 1, i);
    783 
    784         clusterValues = new int[nPoints];
    785         for (int i = 0; i < nPoints; i++)
    786           if (!dict.ContainsKey(estimations[i])) clusterValues[i] = 0;
    787           else clusterValues[i] = dict[estimations[i]];
    788 
    789         return new SortedList<double, int>(dict);
    790       }
    791 
    792       var n = distinct.Length;
    793       var D = new double[n, k];
    794       var B = new int[n, k];
    795 
    796       for (int m = 0; m < k; m++) {
    797         for (int j = m; j <= n - k + m; j++) {
    798           if (m == 0)
    799             D[j, m] = SumOfSquaredDistances(distinct, 0, j + 1);
    800           else {
    801             var minD = double.MaxValue;
    802             var minI = 0;
    803             for (int i = 1; i <= j; i++) {
    804               var d = D[i - 1, m - 1] + SumOfSquaredDistances(distinct, i, j + 1);
    805               if (d < minD) {
    806                 minD = d;
    807                 minI = i;
    808               }
    809             }
    810             D[j, m] = minD;
    811             B[j, m] = minI;
    812           }
    813         }
    814       }
    815 
    816       var centers = new SortedList<double, int>();
    817       var upper = B[n - 1, k - 1];
    818       var c = Mean(distinct, upper, n);
    819       centers.Add(c, k - 1);
    820       for (int i = k - 2; i >= 0; i--) {
    821         var lower = B[upper - 1, i];
    822         var c2 = Mean(distinct, lower, upper);
    823         centers.Add(c2, i);
    824         upper = lower;
    825       }
    826 
    827       clusterValues = new int[nPoints];
    828       for (int i = 0; i < estimations.Length; i++) {
    829         clusterValues[i] = centers.MinItems(x => Math.Abs(estimations[i] - x.Key)).First().Value;
    830       }
    831 
    832       return centers;
    833     }
    834 
    835     private static double SumOfSquaredDistances(double[] x, int start, int end) {
    836       if (start == end) throw new InvalidOperationException();
    837       if (start + 1 == end) return 0.0;
    838       double mean = 0.0;
    839       for (int i = start; i < end; i++) {
    840         mean += x[i];
    841       }
    842       mean /= (end - start);
    843       var sum = 0.0;
    844       for (int i = start; i < end; i++) {
    845         sum += (x[i] - mean) * (x[i] - mean);
    846       }
    847       return sum;
    848     }
    849 
    850     private static double Mean(double[] x, int start, int end) {
    851       if (start == end) throw new InvalidOperationException();
    852       double mean = 0.0;
    853       for (int i = start; i < end; i++) {
    854         mean += x[i];
    855       }
    856       mean /= (end - start);
    857       return mean;
    858     }
    859 
    860     public IEnumerable<Tuple<IAlgorithm, double>> GetAlgorithmInstanceRanking() {
     755    public IEnumerable<KeyValuePair<IAlgorithm, double>> GetAlgorithmInstanceRanking() {
    861756      return RecommendationModel.GetRanking(ProblemInstances.Single(IsCurrentInstance));
    862757    }
  • branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/FixedRankModel.cs

    r13791 r13794  
    2121
    2222using HeuristicLab.Optimization;
    23 using System;
    2423using System.Collections.Generic;
    2524
    2625namespace HeuristicLab.OptimizationExpertSystem.Common {
    2726  public class FixedRankModel : IRecommendationModel {
    28     private readonly List<Tuple<IAlgorithm, double>> ranking;
     27    private readonly List<KeyValuePair<IAlgorithm, double>> ranking;
    2928
    30     public FixedRankModel(IEnumerable<Tuple<IAlgorithm, double>> ranking) {
    31       this.ranking = new List<Tuple<IAlgorithm, double>>();
     29    public FixedRankModel(IEnumerable<KeyValuePair<IAlgorithm, double>> ranking) {
     30      this.ranking = new List<KeyValuePair<IAlgorithm, double>>();
    3231      foreach (var r in ranking) this.ranking.Add(r);
    3332    }
    3433 
    35     public IEnumerable<Tuple<IAlgorithm, double>> GetRanking(IRun problemInstance) {
     34    public IEnumerable<KeyValuePair<IAlgorithm, double>> GetRanking(IRun problemInstance) {
    3635      return ranking;
    3736    }
    3837
    3938    public static FixedRankModel GetEmpty() {
    40       return new FixedRankModel(new Tuple<IAlgorithm, double>[0]);
     39      return new FixedRankModel(new KeyValuePair<IAlgorithm, double>[0]);
    4140    }
    4241  }
  • branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/KNearestNeighborModel.cs

    r13791 r13794  
    2222using HeuristicLab.Collections;
    2323using HeuristicLab.Optimization;
    24 using System;
    2524using System.Collections.Generic;
    2625using System.Linq;
     
    4645    }
    4746
    48     public IEnumerable<Tuple<IAlgorithm, double>> GetRanking(IRun problemInstance) {
     47    public IEnumerable<KeyValuePair<IAlgorithm, double>> GetRanking(IRun problemInstance) {
    4948      var features = KnowledgeCenter.GetFeatures(performance.Keys.OrderBy(problemInstanceMap.GetBySecond).ToArray(), characteristics, medianValues);
    5049      var feature = KnowledgeCenter.GetFeatures(new [] { problemInstance }, characteristics, medianValues)[0];
     
    7069      return performances.Select(x => new { Alg = x.Key, Perf = x.Value.Average() })
    7170                         .OrderBy(x => x.Perf)
    72                          .Select(x => Tuple.Create(x.Alg, x.Perf));
     71                         .Select(x => new KeyValuePair<IAlgorithm, double>(x.Alg, x.Perf));
    7372    }
    7473  }
  • branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem.Common/3.3/Recommenders/OverallBestRecommender.cs

    r13791 r13794  
    4949
    5050    public IRecommendationModel TrainModel(IRun[] problemInstances, KnowledgeCenter kc, string[] characteristics) {
    51       var instances = new List<Tuple<IAlgorithm, double>>();
     51      var instances = new List<KeyValuePair<IAlgorithm, double>>();
    5252      foreach (var relevantRuns in kc.GetKnowledgeBaseByAlgorithm()) {
    5353        var algorithm = relevantRuns.Key;
     
    6060        var count = 0;
    6161        foreach (var problemRuns in relevantRuns.Value.GroupBy(x => ((StringValue)x.Parameters["Problem Name"]).Value)) {
    62           var bkq = pis[problemRuns.Key];
     62          double bkq;
     63          if (!pis.TryGetValue(problemRuns.Key, out bkq)) continue;
    6364          var ert = ExpectedRuntimeHelper.CalculateErt(problemRuns.ToList(), "QualityPerEvaluations", kc.GetTarget(bkq, kc.Maximization), kc.Maximization).ExpectedRuntime;
    6465          if (double.IsNaN(ert)) ert = int.MaxValue;
     
    6768        }
    6869        avgERT /= count;
    69         instances.Add(Tuple.Create((IAlgorithm)algorithm.Clone(), avgERT));
     70        instances.Add(new KeyValuePair<IAlgorithm, double>(algorithm, avgERT));
    7071      }
    7172
    72       return new FixedRankModel(instances.OrderBy(x => x.Item2));
     73      return new FixedRankModel(instances.OrderBy(x => x.Value));
    7374    }
    7475  }
  • branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/PerformanceModelingView.Designer.cs

    r13791 r13794  
    5555      this.parameterCollectionView = new HeuristicLab.Core.Views.ParameterCollectionView();
    5656      this.crossvalidationTabPage = new System.Windows.Forms.TabPage();
     57      this.kendallsTauLabel = new System.Windows.Forms.Label();
     58      this.absoluteErrorLabel = new System.Windows.Forms.Label();
     59      this.kendallsTauView = new HeuristicLab.Data.Views.StringConvertibleValueView();
     60      this.absoluteErrorView = new HeuristicLab.Data.Views.StringConvertibleValueView();
     61      this.confusionMatrixView = new HeuristicLab.Data.Views.StringConvertibleMatrixView();
    5762      this.xValidateButton = new System.Windows.Forms.Button();
    5863      this.minTargetView = new HeuristicLab.Data.Views.StringConvertibleValueView();
    5964      this.minimumTargetLabel = new System.Windows.Forms.Label();
     65      this.actualLabel = new System.Windows.Forms.Label();
     66      this.predictedLabel = new System.Windows.Forms.Label();
    6067      this.tabControl.SuspendLayout();
    6168      this.characteristicsTabPage.SuspendLayout();
     
    7582      // recommenderComboBox
    7683      //
    77       this.recommenderComboBox.Anchor = ((System.Windows.Forms.AnchorStyles)(((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Left)
    78             | System.Windows.Forms.AnchorStyles.Right)));
    7984      this.recommenderComboBox.DropDownStyle = System.Windows.Forms.ComboBoxStyle.DropDownList;
    8085      this.recommenderComboBox.FormattingEnabled = true;
     
    8792      // recommendStartButton
    8893      //
    89       this.recommendStartButton.Anchor = ((System.Windows.Forms.AnchorStyles)((System.Windows.Forms.AnchorStyles.Top | System.Windows.Forms.AnchorStyles.Right)));
    9094      this.recommendStartButton.Location = new System.Drawing.Point(442, 1);
    9195      this.recommendStartButton.Name = "recommendStartButton";
     
    107111      this.tabControl.Name = "tabControl";
    108112      this.tabControl.SelectedIndex = 0;
    109       this.tabControl.Size = new System.Drawing.Size(700, 350);
     113      this.tabControl.Size = new System.Drawing.Size(817, 509);
    110114      this.tabControl.TabIndex = 14;
    111115      //
     
    174178      // crossvalidationTabPage
    175179      //
     180      this.crossvalidationTabPage.Controls.Add(this.kendallsTauLabel);
     181      this.crossvalidationTabPage.Controls.Add(this.predictedLabel);
     182      this.crossvalidationTabPage.Controls.Add(this.actualLabel);
     183      this.crossvalidationTabPage.Controls.Add(this.absoluteErrorLabel);
     184      this.crossvalidationTabPage.Controls.Add(this.kendallsTauView);
     185      this.crossvalidationTabPage.Controls.Add(this.absoluteErrorView);
     186      this.crossvalidationTabPage.Controls.Add(this.confusionMatrixView);
    176187      this.crossvalidationTabPage.Controls.Add(this.xValidateButton);
    177188      this.crossvalidationTabPage.Location = new System.Drawing.Point(4, 22);
    178189      this.crossvalidationTabPage.Name = "crossvalidationTabPage";
    179190      this.crossvalidationTabPage.Padding = new System.Windows.Forms.Padding(3);
    180       this.crossvalidationTabPage.Size = new System.Drawing.Size(692, 324);
     191      this.crossvalidationTabPage.Size = new System.Drawing.Size(809, 483);
    181192      this.crossvalidationTabPage.TabIndex = 1;
    182193      this.crossvalidationTabPage.Text = "Crossvalidation";
    183194      this.crossvalidationTabPage.UseVisualStyleBackColor = true;
     195      //
     196      // kendallsTauLabel
     197      //
     198      this.kendallsTauLabel.AutoSize = true;
     199      this.kendallsTauLabel.Location = new System.Drawing.Point(536, 110);
     200      this.kendallsTauLabel.Margin = new System.Windows.Forms.Padding(3);
     201      this.kendallsTauLabel.Name = "kendallsTauLabel";
     202      this.kendallsTauLabel.Size = new System.Drawing.Size(104, 13);
     203      this.kendallsTauLabel.TabIndex = 3;
     204      this.kendallsTauLabel.Text = "Mean Kendall\'s Tau:";
     205      //
     206      // absoluteErrorLabel
     207      //
     208      this.absoluteErrorLabel.AutoSize = true;
     209      this.absoluteErrorLabel.Location = new System.Drawing.Point(536, 52);
     210      this.absoluteErrorLabel.Margin = new System.Windows.Forms.Padding(3);
     211      this.absoluteErrorLabel.Name = "absoluteErrorLabel";
     212      this.absoluteErrorLabel.Size = new System.Drawing.Size(106, 13);
     213      this.absoluteErrorLabel.TabIndex = 3;
     214      this.absoluteErrorLabel.Text = "Mean Absolute Error:";
     215      //
     216      // kendallsTauView
     217      //
     218      this.kendallsTauView.Caption = "StringConvertibleValue View";
     219      this.kendallsTauView.Content = null;
     220      this.kendallsTauView.LabelVisible = false;
     221      this.kendallsTauView.Location = new System.Drawing.Point(520, 129);
     222      this.kendallsTauView.Name = "kendallsTauView";
     223      this.kendallsTauView.ReadOnly = true;
     224      this.kendallsTauView.Size = new System.Drawing.Size(194, 21);
     225      this.kendallsTauView.TabIndex = 2;
     226      //
     227      // absoluteErrorView
     228      //
     229      this.absoluteErrorView.Caption = "StringConvertibleValue View";
     230      this.absoluteErrorView.Content = null;
     231      this.absoluteErrorView.LabelVisible = false;
     232      this.absoluteErrorView.Location = new System.Drawing.Point(520, 71);
     233      this.absoluteErrorView.Name = "absoluteErrorView";
     234      this.absoluteErrorView.ReadOnly = true;
     235      this.absoluteErrorView.Size = new System.Drawing.Size(194, 21);
     236      this.absoluteErrorView.TabIndex = 2;
     237      //
     238      // confusionMatrixView
     239      //
     240      this.confusionMatrixView.Caption = "StringConvertibleMatrix View";
     241      this.confusionMatrixView.Content = null;
     242      this.confusionMatrixView.Location = new System.Drawing.Point(37, 71);
     243      this.confusionMatrixView.Name = "confusionMatrixView";
     244      this.confusionMatrixView.ReadOnly = true;
     245      this.confusionMatrixView.ShowRowsAndColumnsTextBox = false;
     246      this.confusionMatrixView.ShowStatisticalInformation = false;
     247      this.confusionMatrixView.Size = new System.Drawing.Size(477, 363);
     248      this.confusionMatrixView.TabIndex = 1;
    184249      //
    185250      // xValidateButton
     
    212277      this.minimumTargetLabel.TabIndex = 17;
    213278      this.minimumTargetLabel.Text = "Target:";
     279      //
     280      // actualLabel
     281      //
     282      this.actualLabel.AutoSize = true;
     283      this.actualLabel.Font = new System.Drawing.Font("Microsoft Sans Serif", 8.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
     284      this.actualLabel.Location = new System.Drawing.Point(16, 210);
     285      this.actualLabel.Margin = new System.Windows.Forms.Padding(3);
     286      this.actualLabel.Name = "actualLabel";
     287      this.actualLabel.Size = new System.Drawing.Size(15, 78);
     288      this.actualLabel.TabIndex = 3;
     289      this.actualLabel.Text = "A\r\nC\r\nT\r\nU\r\nA\r\nL";
     290      //
     291      // predictedLabel
     292      //
     293      this.predictedLabel.AutoSize = true;
     294      this.predictedLabel.Font = new System.Drawing.Font("Microsoft Sans Serif", 8.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point, ((byte)(0)));
     295      this.predictedLabel.Location = new System.Drawing.Point(241, 52);
     296      this.predictedLabel.Margin = new System.Windows.Forms.Padding(3);
     297      this.predictedLabel.Name = "predictedLabel";
     298      this.predictedLabel.Size = new System.Drawing.Size(69, 13);
     299      this.predictedLabel.TabIndex = 3;
     300      this.predictedLabel.Text = "PREDICTED";
    214301      //
    215302      // PerformanceModelingView
     
    224311      this.Controls.Add(this.recommendStartButton);
    225312      this.Name = "PerformanceModelingView";
     313      this.Size = new System.Drawing.Size(817, 539);
    226314      this.tabControl.ResumeLayout(false);
    227315      this.characteristicsTabPage.ResumeLayout(false);
    228316      this.parametersTabPage.ResumeLayout(false);
    229317      this.crossvalidationTabPage.ResumeLayout(false);
     318      this.crossvalidationTabPage.PerformLayout();
    230319      this.ResumeLayout(false);
    231320      this.PerformLayout();
     
    248337    private Data.Views.StringConvertibleValueView minTargetView;
    249338    private System.Windows.Forms.Label minimumTargetLabel;
     339    private System.Windows.Forms.Label kendallsTauLabel;
     340    private System.Windows.Forms.Label absoluteErrorLabel;
     341    private Data.Views.StringConvertibleValueView kendallsTauView;
     342    private Data.Views.StringConvertibleValueView absoluteErrorView;
     343    private Data.Views.StringConvertibleMatrixView confusionMatrixView;
     344    private System.Windows.Forms.Label predictedLabel;
     345    private System.Windows.Forms.Label actualLabel;
    250346  }
    251347}
  • branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/PerformanceModelingView.cs

    r13791 r13794  
    2020#endregion
    2121
     22using HeuristicLab.Analysis;
    2223using HeuristicLab.Common.Resources;
    2324using HeuristicLab.Core;
     
    134135      var trainingSet = Content.ProblemInstances.Where(x => !Content.IsCurrentInstance(x)).ToArray();
    135136
     137      var absErr = 0.0;
     138      var confMatrix = new int[6, 6];
     139      var tau = 0.0;
    136140      // leave one out crossvalidation
    137141      foreach (var pi in trainingSet) {
    138142        var model = recommender.TrainModel(trainingSet.Where(x => x != pi).ToArray(), Content, features);
    139         var ranking = model.GetRanking(pi).ToList();
    140         var realPerformance = Content.GetAlgorithmPerformance(pi);
    141         // absolute error predicting ert
    142         // confusion matrix predicting class
    143         // Kendall's tau
     143        var predicted = model.GetRanking(pi).ToDictionary(x => x.Key, x => x.Value);
     144        var observed = Content.GetAlgorithmPerformance(pi);
     145        absErr += AbsoluteError(observed, predicted);
     146        var confMat = ConfusionMatrix(observed, predicted);
     147        for (var i = 0; i < confMat.GetLength(0); i++)
     148          for (var j = 0; j < confMat.GetLength(1); j++)
     149            confMatrix[i, j] += confMat[i, j];
     150        tau += KendallsTau(observed, predicted);
    144151        // average NCDG ... relevance determined by clustering (unsuccessful algorithms being penalized with negative relevance)
    145152        // mean reciprocal rank
    146153        // optional: expected reciprocal rank
    147154      }
    148     }
    149 
    150     private static double AbsoluteError(Dictionary<IAlgorithm, double> performance, List<Tuple<IAlgorithm, double>> ranking) {
     155      absErr /= trainingSet.Length;
     156      tau /= trainingSet.Length;
     157
     158      confusionMatrixView.Content = new IntMatrix(confMatrix);
     159      absoluteErrorView.Content = new DoubleValue(absErr);
     160      kendallsTauView.Content = new DoubleValue(tau);
     161    }
     162
     163    private static double AbsoluteError(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
    151164      var error = 0.0;
    152165      foreach (var tuple in ranking) {
    153166        double actual;
    154         if (!performance.TryGetValue(tuple.Item1, out actual)) continue;
    155         error += Math.Abs(actual - tuple.Item2);
     167        if (!performance.TryGetValue(tuple.Key, out actual)) continue;
     168        if (double.IsNaN(actual)) actual = int.MaxValue;
     169        error += Math.Abs(actual - tuple.Value);
    156170      }
    157171      return error;
    158172    }
    159173
    160     private static int[,] ConfusionMatrix(Dictionary<IAlgorithm, double> performance, List<Tuple<IAlgorithm, double>> ranking) {
    161       var confMatrix = new int[5,5];
     174    private static int[,] ConfusionMatrix(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
     175      var confMatrix = new int[6,6];
     176      var clusteredPerformance = ClusteringHelper<IAlgorithm>.Cluster(5, performance, a => double.IsNaN(a.Value)).GetByInstance().ToDictionary(x => x.Key, x => x.Value.Item2);
     177      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);
     178      foreach (var cr in clusteredRanks) {
     179        int realRank;
     180        if (!clusteredPerformance.TryGetValue(cr.Key, out realRank)) continue;
     181        confMatrix[realRank, cr.Value]++;
     182      }
    162183      return confMatrix;
     184    }
     185
     186    private static double KendallsTau(Dictionary<IAlgorithm, double> performance, Dictionary<IAlgorithm, double> ranking) {
     187      var commonKeys = performance.Keys.Intersect(ranking.Keys).ToList();
     188      var n = commonKeys.Count;
     189      if (n == 0) return 0.0;
     190
     191      var actualRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = performance[x] })
     192                                  .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = i })
     193                                  .OrderBy(x => x.Index).Select(x => x.Rank).ToList();
     194      var predictedRanks = commonKeys.Select((x, i) => new { Alg = x, Index = i, Perf = ranking[x] })
     195                                     .OrderBy(x => x.Perf).Select((x, i) => new { Index = x.Index, Rank = i })
     196                                     .OrderBy(x => x.Index).Select(x => x.Rank).ToList();
     197     
     198      var paired = actualRanks.Zip(predictedRanks, (a, p) => new { Actual = a, Predicted = p }).ToList();
     199      var concordant = 0;
     200      var discordant = 0;
     201      for (var i = 0; i < paired.Count - 1; i++)
     202        for (var j = 0; j < paired.Count; j++) {
     203          if (paired[i].Actual > paired[j].Actual && paired[i].Predicted > paired[j].Predicted
     204            || paired[i].Actual < paired[j].Actual && paired[i].Predicted < paired[j].Predicted)
     205            concordant++;
     206          else discordant++;
     207        }
     208      return (2.0 * (concordant - discordant)) / (n * (n - 1));
    163209    }
    164210    #endregion
  • branches/PerformanceComparison/HeuristicLab.OptimizationExpertSystem/3.3/Views/SolverView.cs

    r13791 r13794  
    2828using HeuristicLab.OptimizationExpertSystem.Common;
    2929using System;
     30using System.Collections.Generic;
    3031using System.Linq;
    3132using System.Windows.Forms;
     
    9697      for (var i = 0; i < ranking.Count; i++) {
    9798        suggestedInstancesComboBox.Items.Add(new AlgorithmInstanceItem(ranking[i]));
    98         if (prevSelection == null || ranking[i].Item1.Name == prevSelection.Item.Item1.Name)
     99        if (prevSelection == null || ranking[i].Key.Name == prevSelection.Item.Key.Name)
    99100          prevNewIndex = prevSelection == null ? 0 : i;
    100101      }
     
    119120    private void AlgorithmStartButtonOnClick(object sender, EventArgs e) {
    120121      if (suggestedInstancesComboBox.SelectedIndex >= 0)
    121         Content.StartAlgorithmAsync(Content.AlgorithmInstances.Select((a, i) => new { Alg = a, Index = i}).Single(x => x.Alg.Name == ((AlgorithmInstanceItem)suggestedInstancesComboBox.SelectedItem).Item.Item1.Name).Index);
     122        Content.StartAlgorithmAsync(Content.AlgorithmInstances.Select((a, i) => new { Alg = a, Index = i}).Single(x => x.Alg.Name == ((AlgorithmInstanceItem)suggestedInstancesComboBox.SelectedItem).Item.Key.Name).Index);
    122123    }
    123124
    124125    private void AlgorithmCloneButtonOnClick(object sender, EventArgs e) {
    125126      if (suggestedInstancesComboBox.SelectedIndex >= 0)
    126         MainForm.ShowContent((IAlgorithm)Content.AlgorithmInstances[Content.AlgorithmInstances.Select((a, i) => new { Alg = a, Index = i }).Single(x => x.Alg.Name == ((AlgorithmInstanceItem)suggestedInstancesComboBox.SelectedItem).Item.Item1.Name).Index].Clone());
     127        MainForm.ShowContent((IAlgorithm)Content.AlgorithmInstances[Content.AlgorithmInstances.Select((a, i) => new { Alg = a, Index = i }).Single(x => x.Alg.Name == ((AlgorithmInstanceItem)suggestedInstancesComboBox.SelectedItem).Item.Key.Name).Index].Clone());
    127128    }
    128129
     
    130131      if (InvokeRequired) { Invoke((Action<object, EventArgs>)SuggestedInstancesComboBoxOnSelectedIndexChanged, sender, e); return; }
    131132      if (suggestedInstancesComboBox.SelectedIndex >= 0) {
    132         var alg = Content.AlgorithmInstances[Content.AlgorithmInstances.Select((a, i) => new { Alg = a, Index = i }).Single(x => x.Alg.Name == ((AlgorithmInstanceItem)suggestedInstancesComboBox.SelectedItem).Item.Item1.Name).Index];
     133        var alg = Content.AlgorithmInstances[Content.AlgorithmInstances.Select((a, i) => new { Alg = a, Index = i }).Single(x => x.Alg.Name == ((AlgorithmInstanceItem)suggestedInstancesComboBox.SelectedItem).Item.Key.Name).Index];
    133134        solverParametersView.Content = alg.Parameters;
    134135        var engineAlg = alg as EngineAlgorithm;
     
    145146    #region Helper Classes and Methods
    146147    private class AlgorithmInstanceItem {
    147       private readonly Tuple<IAlgorithm, double> item;
    148       public Tuple<IAlgorithm, double> Item { get { return item; } }
     148      private readonly KeyValuePair<IAlgorithm, double> item;
     149      public KeyValuePair<IAlgorithm, double> Item { get { return item; } }
    149150
    150       public AlgorithmInstanceItem(Tuple<IAlgorithm, double> item) {
     151      public AlgorithmInstanceItem(KeyValuePair<IAlgorithm, double> item) {
    151152        this.item = item;
    152153      }
    153154
    154155      public override string ToString() {
    155         return item.Item2.ToString("N0") + ": " + item.Item1.Name;
     156        return item.Value.ToString("N0") + ": " + item.Key.Name;
    156157      }
    157158    }
Note: See TracChangeset for help on using the changeset viewer.