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 |
|
---|
22 | using System;
|
---|
23 | using System.Collections.Generic;
|
---|
24 | using System.Linq;
|
---|
25 | using System.Threading;
|
---|
26 | using HeuristicLab.Common;
|
---|
27 | using HeuristicLab.Core;
|
---|
28 | using HeuristicLab.Data;
|
---|
29 | using HeuristicLab.Optimization;
|
---|
30 | using HeuristicLab.Parameters;
|
---|
31 | using HEAL.Fossil;
|
---|
32 | using HeuristicLab.Problems.DataAnalysis;
|
---|
33 | using HeuristicLab.Persistence;
|
---|
34 |
|
---|
35 | namespace 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 | }
|
---|