Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Algorithms.DataAnalysis/3.4/BaselineClassifiers/OneR.cs @ 15061

Last change on this file since 15061 was 15061, checked in by gkronber, 7 years ago

#2524: merged r14517, r14523, r14527 from trunk to branch

File size: 7.4 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 System.Collections.Generic;
23using System.Linq;
24using System.Threading;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Data;
28using HeuristicLab.Optimization;
29using HeuristicLab.Parameters;
30using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
31using HeuristicLab.Problems.DataAnalysis;
32
33namespace HeuristicLab.Algorithms.DataAnalysis {
34  /// <summary>
35  /// 1R classification algorithm.
36  /// </summary>
37  [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.")]
38  [StorableClass]
39  public sealed class OneR : FixedDataAnalysisAlgorithm<IClassificationProblem> {
40
41    public IValueParameter<IntValue> MinBucketSizeParameter {
42      get { return (IValueParameter<IntValue>)Parameters["MinBucketSize"]; }
43    }
44
45    [StorableConstructor]
46    private OneR(bool deserializing) : base(deserializing) { }
47
48    private OneR(OneR original, Cloner cloner)
49      : base(original, cloner) { }
50
51    public OneR()
52      : base() {
53      Parameters.Add(new ValueParameter<IntValue>("MinBucketSize", "Minimum size of a bucket for numerical values. (Except for the rightmost bucket)", new IntValue(6)));
54      Problem = new ClassificationProblem();
55    }
56
57    public override IDeepCloneable Clone(Cloner cloner) {
58      return new OneR(this, cloner);
59    }
60
61    protected override void Run(CancellationToken cancellationToken) {
62      var solution = CreateOneRSolution(Problem.ProblemData, MinBucketSizeParameter.Value.Value);
63      Results.Add(new Result("OneR solution", "The 1R classifier.", solution));
64    }
65
66    public static IClassificationSolution CreateOneRSolution(IClassificationProblemData problemData, int minBucketSize = 6) {
67      var bestClassified = 0;
68      List<Split> bestSplits = null;
69      string bestVariable = string.Empty;
70      double bestMissingValuesClass = double.NaN;
71      var classValues = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TrainingIndices);
72
73      foreach (var variable in problemData.AllowedInputVariables) {
74        var inputValues = problemData.Dataset.GetDoubleValues(variable, problemData.TrainingIndices);
75        var samples = inputValues.Zip(classValues, (i, v) => new Sample(i, v)).OrderBy(s => s.inputValue);
76
77        var missingValuesDistribution = samples.Where(s => double.IsNaN(s.inputValue)).GroupBy(s => s.classValue).ToDictionary(s => s.Key, s => s.Count()).MaxItems(s => s.Value).FirstOrDefault();
78
79        //calculate class distributions for all distinct inputValues
80        List<Dictionary<double, int>> classDistributions = new List<Dictionary<double, int>>();
81        List<double> thresholds = new List<double>();
82        double lastValue = double.NaN;
83        foreach (var sample in samples.Where(s => !double.IsNaN(s.inputValue))) {
84          if (sample.inputValue > lastValue || double.IsNaN(lastValue)) {
85            if (!double.IsNaN(lastValue)) thresholds.Add((lastValue + sample.inputValue) / 2);
86            lastValue = sample.inputValue;
87            classDistributions.Add(new Dictionary<double, int>());
88            foreach (var classValue in problemData.ClassValues)
89              classDistributions[classDistributions.Count - 1][classValue] = 0;
90
91          }
92          classDistributions[classDistributions.Count - 1][sample.classValue]++;
93        }
94        thresholds.Add(double.PositiveInfinity);
95
96        var distribution = classDistributions[0];
97        var threshold = thresholds[0];
98        var splits = new List<Split>();
99
100        for (int i = 1; i < classDistributions.Count; i++) {
101          var samplesInSplit = distribution.Max(d => d.Value);
102          //join splits if there are too few samples in the split or the distributions has the same maximum class value as the current split
103          if (samplesInSplit < minBucketSize ||
104            classDistributions[i].MaxItems(d => d.Value).Select(d => d.Key).Contains(
105              distribution.MaxItems(d => d.Value).Select(d => d.Key).First())) {
106            foreach (var classValue in classDistributions[i])
107              distribution[classValue.Key] += classValue.Value;
108            threshold = thresholds[i];
109          } else {
110            splits.Add(new Split(threshold, distribution.MaxItems(d => d.Value).Select(d => d.Key).First()));
111            distribution = classDistributions[i];
112            threshold = thresholds[i];
113          }
114        }
115        splits.Add(new Split(double.PositiveInfinity, distribution.MaxItems(d => d.Value).Select(d => d.Key).First()));
116
117        int correctClassified = 0;
118        int splitIndex = 0;
119        foreach (var sample in samples.Where(s => !double.IsNaN(s.inputValue))) {
120          while (sample.inputValue >= splits[splitIndex].thresholdValue)
121            splitIndex++;
122          correctClassified += sample.classValue == splits[splitIndex].classValue ? 1 : 0;
123        }
124        correctClassified += missingValuesDistribution.Value;
125
126        if (correctClassified > bestClassified) {
127          bestClassified = correctClassified;
128          bestSplits = splits;
129          bestVariable = variable;
130          bestMissingValuesClass = missingValuesDistribution.Value == 0 ? double.NaN : missingValuesDistribution.Key;
131        }
132      }
133
134      //remove neighboring splits with the same class value
135      for (int i = 0; i < bestSplits.Count - 1; i++) {
136        if (bestSplits[i].classValue == bestSplits[i + 1].classValue) {
137          bestSplits.Remove(bestSplits[i]);
138          i--;
139        }
140      }
141
142      var model = new OneRClassificationModel(problemData.TargetVariable, bestVariable, bestSplits.Select(s => s.thresholdValue).ToArray(), bestSplits.Select(s => s.classValue).ToArray(), bestMissingValuesClass);
143      var solution = new OneRClassificationSolution(model, (IClassificationProblemData)problemData.Clone());
144
145      return solution;
146    }
147
148    #region helper classes
149    private class Split {
150      public double thresholdValue;
151      public double classValue;
152
153      public Split(double thresholdValue, double classValue) {
154        this.thresholdValue = thresholdValue;
155        this.classValue = classValue;
156      }
157    }
158
159    private class Sample {
160      public double inputValue;
161      public double classValue;
162
163      public Sample(double inputValue, double classValue) {
164        this.inputValue = inputValue;
165        this.classValue = classValue;
166      }
167    }
168    #endregion
169  }
170}
Note: See TracBrowser for help on using the repository browser.