Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2520_PersistenceReintegration/HeuristicLab.Algorithms.DataAnalysis/3.4/BaselineClassifiers/OneR.cs @ 16468

Last change on this file since 16468 was 16468, checked in by gkronber, 5 years ago

#2520: added the necessary StorableType attributes in HeuristicLab.Algorithms.DataAnalysis

File size: 10.9 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2019 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 System;
23using System.Collections.Generic;
24using System.Linq;
25using System.Threading;
26using HeuristicLab.Common;
27using HeuristicLab.Core;
28using HeuristicLab.Data;
29using HeuristicLab.Optimization;
30using HeuristicLab.Parameters;
31using HEAL.Fossil;
32using HeuristicLab.Problems.DataAnalysis;
33using HeuristicLab.Persistence;
34
35namespace HeuristicLab.Algorithms.DataAnalysis {
36  /// <summary>
37  /// 1R classification algorithm.
38  /// </summary>
39  [Item("OneR Classification", "A simple classification algorithm the searches the best single-variable split (does not support categorical features correctly). See R.C. Holte (1993). Very simple classification rules perform well on most commonly used datasets. Machine Learning. 11:63-91.")]
40  [StorableType("22D1C518-CEDA-413C-8997-D34BC06B6267")]
41  public sealed class OneR : FixedDataAnalysisAlgorithm<IClassificationProblem> {
42
43    public IValueParameter<IntValue> MinBucketSizeParameter {
44      get { return (IValueParameter<IntValue>)Parameters["MinBucketSize"]; }
45    }
46
47    [StorableConstructor]
48    private OneR(StorableConstructorFlag _) : base(_) { }
49
50    private OneR(OneR original, Cloner cloner)
51      : base(original, cloner) { }
52
53    public OneR()
54      : base() {
55      Parameters.Add(new ValueParameter<IntValue>("MinBucketSize", "Minimum size of a bucket for numerical values. (Except for the rightmost bucket)", new IntValue(6)));
56      Problem = new ClassificationProblem();
57    }
58
59    public override IDeepCloneable Clone(Cloner cloner) {
60      return new OneR(this, cloner);
61    }
62
63    protected override void Run(CancellationToken cancellationToken) {
64      var solution = CreateOneRSolution(Problem.ProblemData, MinBucketSizeParameter.Value.Value);
65      Results.Add(new Result("OneR solution", "The 1R classifier.", solution));
66    }
67
68    public static IClassificationSolution CreateOneRSolution(IClassificationProblemData problemData, int minBucketSize = 6) {
69      var classValues = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TrainingIndices);
70      var model1 = FindBestDoubleVariableModel(problemData, minBucketSize);
71      var model2 = FindBestFactorModel(problemData);
72
73      if (model1 == null && model2 == null) throw new InvalidProgramException("Could not create OneR solution");
74      else if (model1 == null) return new OneFactorClassificationSolution(model2, (IClassificationProblemData)problemData.Clone());
75      else if (model2 == null) return new OneRClassificationSolution(model1, (IClassificationProblemData)problemData.Clone());
76      else {
77        var model1EstimatedValues = model1.GetEstimatedClassValues(problemData.Dataset, problemData.TrainingIndices);
78        var model1NumCorrect = classValues.Zip(model1EstimatedValues, (a, b) => a.IsAlmost(b)).Count(e => e);
79
80        var model2EstimatedValues = model2.GetEstimatedClassValues(problemData.Dataset, problemData.TrainingIndices);
81        var model2NumCorrect = classValues.Zip(model2EstimatedValues, (a, b) => a.IsAlmost(b)).Count(e => e);
82
83        if (model1NumCorrect > model2NumCorrect) {
84          return new OneRClassificationSolution(model1, (IClassificationProblemData)problemData.Clone());
85        } else {
86          return new OneFactorClassificationSolution(model2, (IClassificationProblemData)problemData.Clone());
87        }
88      }
89    }
90
91    private static OneRClassificationModel FindBestDoubleVariableModel(IClassificationProblemData problemData, int minBucketSize = 6) {
92      var bestClassified = 0;
93      List<Split> bestSplits = null;
94      string bestVariable = string.Empty;
95      double bestMissingValuesClass = double.NaN;
96      var classValues = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TrainingIndices);
97
98      var allowedInputVariables = problemData.AllowedInputVariables.Where(problemData.Dataset.VariableHasType<double>);
99
100      if (!allowedInputVariables.Any()) return null;
101
102      foreach (var variable in allowedInputVariables) {
103        var inputValues = problemData.Dataset.GetDoubleValues(variable, problemData.TrainingIndices);
104        var samples = inputValues.Zip(classValues, (i, v) => new Sample(i, v)).OrderBy(s => s.inputValue);
105
106        var missingValuesDistribution = samples
107          .Where(s => double.IsNaN(s.inputValue)).GroupBy(s => s.classValue)
108          .ToDictionary(s => s.Key, s => s.Count())
109          .MaxItems(s => s.Value)
110          .FirstOrDefault();
111
112        //calculate class distributions for all distinct inputValues
113        List<Dictionary<double, int>> classDistributions = new List<Dictionary<double, int>>();
114        List<double> thresholds = new List<double>();
115        double lastValue = double.NaN;
116        foreach (var sample in samples.Where(s => !double.IsNaN(s.inputValue))) {
117          if (sample.inputValue > lastValue || double.IsNaN(lastValue)) {
118            if (!double.IsNaN(lastValue)) thresholds.Add((lastValue + sample.inputValue) / 2);
119            lastValue = sample.inputValue;
120            classDistributions.Add(new Dictionary<double, int>());
121            foreach (var classValue in problemData.ClassValues)
122              classDistributions[classDistributions.Count - 1][classValue] = 0;
123
124          }
125          classDistributions[classDistributions.Count - 1][sample.classValue]++;
126        }
127        thresholds.Add(double.PositiveInfinity);
128
129        var distribution = classDistributions[0];
130        var threshold = thresholds[0];
131        var splits = new List<Split>();
132
133        for (int i = 1; i < classDistributions.Count; i++) {
134          var samplesInSplit = distribution.Max(d => d.Value);
135          //join splits if there are too few samples in the split or the distributions has the same maximum class value as the current split
136          if (samplesInSplit < minBucketSize ||
137            classDistributions[i].MaxItems(d => d.Value).Select(d => d.Key).Contains(
138              distribution.MaxItems(d => d.Value).Select(d => d.Key).First())) {
139            foreach (var classValue in classDistributions[i])
140              distribution[classValue.Key] += classValue.Value;
141            threshold = thresholds[i];
142          } else {
143            splits.Add(new Split(threshold, distribution.MaxItems(d => d.Value).Select(d => d.Key).First()));
144            distribution = classDistributions[i];
145            threshold = thresholds[i];
146          }
147        }
148        splits.Add(new Split(double.PositiveInfinity, distribution.MaxItems(d => d.Value).Select(d => d.Key).First()));
149
150        int correctClassified = 0;
151        int splitIndex = 0;
152        foreach (var sample in samples.Where(s => !double.IsNaN(s.inputValue))) {
153          while (sample.inputValue >= splits[splitIndex].thresholdValue)
154            splitIndex++;
155          correctClassified += sample.classValue.IsAlmost(splits[splitIndex].classValue) ? 1 : 0;
156        }
157        correctClassified += missingValuesDistribution.Value;
158
159        if (correctClassified > bestClassified) {
160          bestClassified = correctClassified;
161          bestSplits = splits;
162          bestVariable = variable;
163          bestMissingValuesClass = missingValuesDistribution.Value == 0 ? double.NaN : missingValuesDistribution.Key;
164        }
165      }
166
167      //remove neighboring splits with the same class value
168      for (int i = 0; i < bestSplits.Count - 1; i++) {
169        if (bestSplits[i].classValue.IsAlmost(bestSplits[i + 1].classValue)) {
170          bestSplits.Remove(bestSplits[i]);
171          i--;
172        }
173      }
174
175      var model = new OneRClassificationModel(problemData.TargetVariable, bestVariable,
176        bestSplits.Select(s => s.thresholdValue).ToArray(),
177        bestSplits.Select(s => s.classValue).ToArray(), bestMissingValuesClass);
178
179      return model;
180    }
181    private static OneFactorClassificationModel FindBestFactorModel(IClassificationProblemData problemData) {
182      var classValues = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TrainingIndices);
183      var defaultClass = FindMostFrequentClassValue(classValues);
184      // only select string variables
185      var allowedInputVariables = problemData.AllowedInputVariables.Where(problemData.Dataset.VariableHasType<string>);
186
187      if (!allowedInputVariables.Any()) return null;
188
189      OneFactorClassificationModel bestModel = null;
190      var bestModelNumCorrect = 0;
191
192      foreach (var variable in allowedInputVariables) {
193        var variableValues = problemData.Dataset.GetStringValues(variable, problemData.TrainingIndices);
194        var groupedClassValues = variableValues
195          .Zip(classValues, (v, c) => new KeyValuePair<string, double>(v, c))
196          .GroupBy(kvp => kvp.Key)
197          .ToDictionary(g => g.Key, g => FindMostFrequentClassValue(g.Select(kvp => kvp.Value)));
198
199        var model = new OneFactorClassificationModel(problemData.TargetVariable, variable,
200          groupedClassValues.Select(kvp => kvp.Key).ToArray(), groupedClassValues.Select(kvp => kvp.Value).ToArray(), defaultClass);
201
202        var modelEstimatedValues = model.GetEstimatedClassValues(problemData.Dataset, problemData.TrainingIndices);
203        var modelNumCorrect = classValues.Zip(modelEstimatedValues, (a, b) => a.IsAlmost(b)).Count(e => e);
204        if (modelNumCorrect > bestModelNumCorrect) {
205          bestModelNumCorrect = modelNumCorrect;
206          bestModel = model;
207        }
208      }
209
210      return bestModel;
211    }
212
213    private static double FindMostFrequentClassValue(IEnumerable<double> classValues) {
214      return classValues.GroupBy(c => c).OrderByDescending(g => g.Count()).Select(g => g.Key).First();
215    }
216
217    #region helper classes
218    private class Split {
219      public double thresholdValue;
220      public double classValue;
221
222      public Split(double thresholdValue, double classValue) {
223        this.thresholdValue = thresholdValue;
224        this.classValue = classValue;
225      }
226    }
227
228    private class Sample {
229      public double inputValue;
230      public double classValue;
231
232      public Sample(double inputValue, double classValue) {
233        this.inputValue = inputValue;
234        this.classValue = classValue;
235      }
236    }
237    #endregion
238  }
239}
Note: See TracBrowser for help on using the repository browser.