[10569] | 1 | #region License Information
|
---|
| 2 | /* HeuristicLab
|
---|
[16453] | 3 | * Copyright (C) 2002-2019 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
|
---|
[10569] | 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 |
|
---|
[14826] | 22 | using System;
|
---|
[10569] | 23 | using System.Collections.Generic;
|
---|
| 24 | using System.Linq;
|
---|
[14523] | 25 | using System.Threading;
|
---|
[10569] | 26 | using HeuristicLab.Common;
|
---|
| 27 | using HeuristicLab.Core;
|
---|
| 28 | using HeuristicLab.Data;
|
---|
| 29 | using HeuristicLab.Optimization;
|
---|
| 30 | using HeuristicLab.Parameters;
|
---|
[16462] | 31 | using HEAL.Fossil;
|
---|
[10569] | 32 | using HeuristicLab.Problems.DataAnalysis;
|
---|
[16468] | 33 | using HeuristicLab.Persistence;
|
---|
[10569] | 34 |
|
---|
| 35 | namespace HeuristicLab.Algorithms.DataAnalysis {
|
---|
| 36 | /// <summary>
|
---|
| 37 | /// 1R classification algorithm.
|
---|
| 38 | /// </summary>
|
---|
[13090] | 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.")]
|
---|
[16462] | 40 | [StorableType("22D1C518-CEDA-413C-8997-D34BC06B6267")]
|
---|
[13090] | 41 | public sealed class OneR : FixedDataAnalysisAlgorithm<IClassificationProblem> {
|
---|
[10569] | 42 |
|
---|
| 43 | public IValueParameter<IntValue> MinBucketSizeParameter {
|
---|
| 44 | get { return (IValueParameter<IntValue>)Parameters["MinBucketSize"]; }
|
---|
| 45 | }
|
---|
| 46 |
|
---|
| 47 | [StorableConstructor]
|
---|
[16462] | 48 | private OneR(StorableConstructorFlag _) : base(_) { }
|
---|
[10569] | 49 |
|
---|
[13090] | 50 | private OneR(OneR original, Cloner cloner)
|
---|
[10569] | 51 | : base(original, cloner) { }
|
---|
| 52 |
|
---|
[13090] | 53 | public OneR()
|
---|
[10569] | 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) {
|
---|
[13090] | 60 | return new OneR(this, cloner);
|
---|
[10569] | 61 | }
|
---|
| 62 |
|
---|
[14523] | 63 | protected override void Run(CancellationToken cancellationToken) {
|
---|
[10569] | 64 | var solution = CreateOneRSolution(Problem.ProblemData, MinBucketSizeParameter.Value.Value);
|
---|
| 65 | Results.Add(new Result("OneR solution", "The 1R classifier.", solution));
|
---|
| 66 | }
|
---|
| 67 |
|
---|
[13089] | 68 | public static IClassificationSolution CreateOneRSolution(IClassificationProblemData problemData, int minBucketSize = 6) {
|
---|
[14826] | 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) {
|
---|
[10569] | 92 | var bestClassified = 0;
|
---|
| 93 | List<Split> bestSplits = null;
|
---|
| 94 | string bestVariable = string.Empty;
|
---|
[10570] | 95 | double bestMissingValuesClass = double.NaN;
|
---|
| 96 | var classValues = problemData.Dataset.GetDoubleValues(problemData.TargetVariable, problemData.TrainingIndices);
|
---|
[10569] | 97 |
|
---|
[14826] | 98 | var allowedInputVariables = problemData.AllowedInputVariables.Where(problemData.Dataset.VariableHasType<double>);
|
---|
| 99 |
|
---|
| 100 | if (!allowedInputVariables.Any()) return null;
|
---|
| 101 |
|
---|
| 102 | foreach (var variable in allowedInputVariables) {
|
---|
[10569] | 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 |
|
---|
[14826] | 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();
|
---|
[10570] | 111 |
|
---|
[10569] | 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;
|
---|
[10570] | 116 | foreach (var sample in samples.Where(s => !double.IsNaN(s.inputValue))) {
|
---|
[10569] | 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);
|
---|
[10570] | 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
|
---|
[10569] | 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;
|
---|
[10570] | 152 | foreach (var sample in samples.Where(s => !double.IsNaN(s.inputValue))) {
|
---|
[10569] | 153 | while (sample.inputValue >= splits[splitIndex].thresholdValue)
|
---|
| 154 | splitIndex++;
|
---|
[14826] | 155 | correctClassified += sample.classValue.IsAlmost(splits[splitIndex].classValue) ? 1 : 0;
|
---|
[10569] | 156 | }
|
---|
[10570] | 157 | correctClassified += missingValuesDistribution.Value;
|
---|
[10569] | 158 |
|
---|
| 159 | if (correctClassified > bestClassified) {
|
---|
| 160 | bestClassified = correctClassified;
|
---|
| 161 | bestSplits = splits;
|
---|
| 162 | bestVariable = variable;
|
---|
[10570] | 163 | bestMissingValuesClass = missingValuesDistribution.Value == 0 ? double.NaN : missingValuesDistribution.Key;
|
---|
[10569] | 164 | }
|
---|
| 165 | }
|
---|
| 166 |
|
---|
| 167 | //remove neighboring splits with the same class value
|
---|
| 168 | for (int i = 0; i < bestSplits.Count - 1; i++) {
|
---|
[14826] | 169 | if (bestSplits[i].classValue.IsAlmost(bestSplits[i + 1].classValue)) {
|
---|
[10569] | 170 | bestSplits.Remove(bestSplits[i]);
|
---|
| 171 | i--;
|
---|
| 172 | }
|
---|
| 173 | }
|
---|
| 174 |
|
---|
[14826] | 175 | var model = new OneRClassificationModel(problemData.TargetVariable, bestVariable,
|
---|
| 176 | bestSplits.Select(s => s.thresholdValue).ToArray(),
|
---|
| 177 | bestSplits.Select(s => s.classValue).ToArray(), bestMissingValuesClass);
|
---|
[10569] | 178 |
|
---|
[14826] | 179 | return model;
|
---|
[10569] | 180 | }
|
---|
[14826] | 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>);
|
---|
[10569] | 186 |
|
---|
[14826] | 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 |
|
---|
[10569] | 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 | }
|
---|