source: trunk/sources/HeuristicLab.Algorithms.DataAnalysis/3.4/NearestNeighbour/NearestNeighbourModel.cs @ 14826

Last change on this file since 14826 was 14826, checked in by gkronber, 6 months ago

#2650: merged the factors branch into trunk

File size: 15.2 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;
23using System.Collections.Generic;
24using System.Linq;
25using HeuristicLab.Common;
26using HeuristicLab.Core;
27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
28using HeuristicLab.Problems.DataAnalysis;
29
30namespace HeuristicLab.Algorithms.DataAnalysis {
31  /// <summary>
32  /// Represents a nearest neighbour model for regression and classification
33  /// </summary>
34  [StorableClass]
35  [Item("NearestNeighbourModel", "Represents a nearest neighbour model for regression and classification.")]
36  public sealed class NearestNeighbourModel : ClassificationModel, INearestNeighbourModel {
37
38    private readonly object kdTreeLockObject = new object();
39    private alglib.nearestneighbor.kdtree kdTree;
40    public alglib.nearestneighbor.kdtree KDTree {
41      get { return kdTree; }
42      set {
43        if (value != kdTree) {
44          if (value == null) throw new ArgumentNullException();
45          kdTree = value;
46          OnChanged(EventArgs.Empty);
47        }
48      }
49    }
50
51
52    public override IEnumerable<string> VariablesUsedForPrediction {
53      get { return allowedInputVariables; }
54    }
55
56    [Storable]
57    private string[] allowedInputVariables;
58    [Storable]
59    private double[] classValues;
60    [Storable]
61    private int k;
62    [Storable(DefaultValue = null)]
63    private double[] weights; // not set for old versions loaded from disk
64    [Storable(DefaultValue = null)]
65    private double[] offsets; // not set for old versions loaded from disk
66
67    [StorableConstructor]
68    private NearestNeighbourModel(bool deserializing)
69      : base(deserializing) {
70      if (deserializing)
71        kdTree = new alglib.nearestneighbor.kdtree();
72    }
73    private NearestNeighbourModel(NearestNeighbourModel original, Cloner cloner)
74      : base(original, cloner) {
75      kdTree = new alglib.nearestneighbor.kdtree();
76      kdTree.approxf = original.kdTree.approxf;
77      kdTree.boxmax = (double[])original.kdTree.boxmax.Clone();
78      kdTree.boxmin = (double[])original.kdTree.boxmin.Clone();
79      kdTree.buf = (double[])original.kdTree.buf.Clone();
80      kdTree.curboxmax = (double[])original.kdTree.curboxmax.Clone();
81      kdTree.curboxmin = (double[])original.kdTree.curboxmin.Clone();
82      kdTree.curdist = original.kdTree.curdist;
83      kdTree.debugcounter = original.kdTree.debugcounter;
84      kdTree.idx = (int[])original.kdTree.idx.Clone();
85      kdTree.kcur = original.kdTree.kcur;
86      kdTree.kneeded = original.kdTree.kneeded;
87      kdTree.n = original.kdTree.n;
88      kdTree.nodes = (int[])original.kdTree.nodes.Clone();
89      kdTree.normtype = original.kdTree.normtype;
90      kdTree.nx = original.kdTree.nx;
91      kdTree.ny = original.kdTree.ny;
92      kdTree.r = (double[])original.kdTree.r.Clone();
93      kdTree.rneeded = original.kdTree.rneeded;
94      kdTree.selfmatch = original.kdTree.selfmatch;
95      kdTree.splits = (double[])original.kdTree.splits.Clone();
96      kdTree.tags = (int[])original.kdTree.tags.Clone();
97      kdTree.x = (double[])original.kdTree.x.Clone();
98      kdTree.xy = (double[,])original.kdTree.xy.Clone();
99
100      k = original.k;
101      isCompatibilityLoaded = original.IsCompatibilityLoaded;
102      if (!IsCompatibilityLoaded) {
103        weights = new double[original.weights.Length];
104        Array.Copy(original.weights, weights, weights.Length);
105        offsets = new double[original.offsets.Length];
106        Array.Copy(original.offsets, this.offsets, this.offsets.Length);
107      }
108      allowedInputVariables = (string[])original.allowedInputVariables.Clone();
109      if (original.classValues != null)
110        this.classValues = (double[])original.classValues.Clone();
111    }
112    public NearestNeighbourModel(IDataset dataset, IEnumerable<int> rows, int k, string targetVariable, IEnumerable<string> allowedInputVariables, IEnumerable<double> weights = null, double[] classValues = null)
113      : base(targetVariable) {
114      Name = ItemName;
115      Description = ItemDescription;
116      this.k = k;
117      this.allowedInputVariables = allowedInputVariables.ToArray();
118      double[,] inputMatrix;
119      if (IsCompatibilityLoaded) {
120        // no scaling
121        inputMatrix = AlglibUtil.PrepareInputMatrix(dataset,
122          this.allowedInputVariables.Concat(new string[] { targetVariable }),
123          rows);
124      } else {
125        this.offsets = this.allowedInputVariables
126          .Select(name => dataset.GetDoubleValues(name, rows).Average() * -1)
127          .Concat(new double[] { 0 }) // no offset for target variable
128          .ToArray();
129        if (weights == null) {
130          // automatic determination of weights (all features should have variance = 1)
131          this.weights = this.allowedInputVariables
132            .Select(name => 1.0 / dataset.GetDoubleValues(name, rows).StandardDeviationPop())
133            .Concat(new double[] { 1.0 }) // no scaling for target variable
134            .ToArray();
135        } else {
136          // user specified weights (+ 1 for target)
137          this.weights = weights.Concat(new double[] { 1.0 }).ToArray();
138          if (this.weights.Length - 1 != this.allowedInputVariables.Length)
139            throw new ArgumentException("The number of elements in the weight vector must match the number of input variables");
140        }
141        inputMatrix = CreateScaledData(dataset, this.allowedInputVariables.Concat(new string[] { targetVariable }), rows, this.offsets, this.weights);
142      }
143
144      if (inputMatrix.Cast<double>().Any(x => double.IsNaN(x) || double.IsInfinity(x)))
145        throw new NotSupportedException(
146          "Nearest neighbour model does not support NaN or infinity values in the input dataset.");
147
148      this.kdTree = new alglib.nearestneighbor.kdtree();
149
150      var nRows = inputMatrix.GetLength(0);
151      var nFeatures = inputMatrix.GetLength(1) - 1;
152
153      if (classValues != null) {
154        this.classValues = (double[])classValues.Clone();
155        int nClasses = classValues.Length;
156        // map original class values to values [0..nClasses-1]
157        var classIndices = new Dictionary<double, double>();
158        for (int i = 0; i < nClasses; i++)
159          classIndices[classValues[i]] = i;
160
161        for (int row = 0; row < nRows; row++) {
162          inputMatrix[row, nFeatures] = classIndices[inputMatrix[row, nFeatures]];
163        }
164      }
165      alglib.nearestneighbor.kdtreebuild(inputMatrix, nRows, inputMatrix.GetLength(1) - 1, 1, 2, kdTree);
166    }
167
168    private static double[,] CreateScaledData(IDataset dataset, IEnumerable<string> variables, IEnumerable<int> rows, double[] offsets, double[] factors) {
169      var x = new double[rows.Count(), variables.Count()];
170      var colIdx = 0;
171      foreach (var variableName in variables) {
172        var rowIdx = 0;
173        foreach (var val in dataset.GetDoubleValues(variableName, rows)) {
174          x[rowIdx, colIdx] = (val + offsets[colIdx]) * factors[colIdx];
175          rowIdx++;
176        }
177        colIdx++;
178      }
179      return x;
180    }
181
182    public override IDeepCloneable Clone(Cloner cloner) {
183      return new NearestNeighbourModel(this, cloner);
184    }
185
186    public IEnumerable<double> GetEstimatedValues(IDataset dataset, IEnumerable<int> rows) {
187      double[,] inputData;
188      if (IsCompatibilityLoaded) {
189        inputData = AlglibUtil.PrepareInputMatrix(dataset, allowedInputVariables, rows);
190      } else {
191        inputData = CreateScaledData(dataset, allowedInputVariables, rows, offsets, weights);
192      }
193
194      int n = inputData.GetLength(0);
195      int columns = inputData.GetLength(1);
196      double[] x = new double[columns];
197      double[] dists = new double[k];
198      double[,] neighbours = new double[k, columns + 1];
199
200      for (int row = 0; row < n; row++) {
201        for (int column = 0; column < columns; column++) {
202          x[column] = inputData[row, column];
203        }
204        int numNeighbours;
205        lock (kdTreeLockObject) { // gkronber: the following calls change the kdTree data structure
206          numNeighbours = alglib.nearestneighbor.kdtreequeryknn(kdTree, x, k, false);
207          alglib.nearestneighbor.kdtreequeryresultsdistances(kdTree, ref dists);
208          alglib.nearestneighbor.kdtreequeryresultsxy(kdTree, ref neighbours);
209        }
210
211        double distanceWeightedValue = 0.0;
212        double distsSum = 0.0;
213        for (int i = 0; i < numNeighbours; i++) {
214          distanceWeightedValue += neighbours[i, columns] / dists[i];
215          distsSum += 1.0 / dists[i];
216        }
217        yield return distanceWeightedValue / distsSum;
218      }
219    }
220
221    public override IEnumerable<double> GetEstimatedClassValues(IDataset dataset, IEnumerable<int> rows) {
222      if (classValues == null) throw new InvalidOperationException("No class values are defined.");
223      double[,] inputData;
224      if (IsCompatibilityLoaded) {
225        inputData = AlglibUtil.PrepareInputMatrix(dataset, allowedInputVariables, rows);
226      } else {
227        inputData = CreateScaledData(dataset, allowedInputVariables, rows, offsets, weights);
228      }
229      int n = inputData.GetLength(0);
230      int columns = inputData.GetLength(1);
231      double[] x = new double[columns];
232      int[] y = new int[classValues.Length];
233      double[] dists = new double[k];
234      double[,] neighbours = new double[k, columns + 1];
235
236      for (int row = 0; row < n; row++) {
237        for (int column = 0; column < columns; column++) {
238          x[column] = inputData[row, column];
239        }
240        int numNeighbours;
241        lock (kdTreeLockObject) {
242          // gkronber: the following calls change the kdTree data structure
243          numNeighbours = alglib.nearestneighbor.kdtreequeryknn(kdTree, x, k, false);
244          alglib.nearestneighbor.kdtreequeryresultsdistances(kdTree, ref dists);
245          alglib.nearestneighbor.kdtreequeryresultsxy(kdTree, ref neighbours);
246        }
247        Array.Clear(y, 0, y.Length);
248        for (int i = 0; i < numNeighbours; i++) {
249          int classValue = (int)Math.Round(neighbours[i, columns]);
250          y[classValue]++;
251        }
252
253        // find class for with the largest probability value
254        int maxProbClassIndex = 0;
255        double maxProb = y[0];
256        for (int i = 1; i < y.Length; i++) {
257          if (maxProb < y[i]) {
258            maxProb = y[i];
259            maxProbClassIndex = i;
260          }
261        }
262        yield return classValues[maxProbClassIndex];
263      }
264    }
265
266
267    IRegressionSolution IRegressionModel.CreateRegressionSolution(IRegressionProblemData problemData) {
268      return new NearestNeighbourRegressionSolution(this, new RegressionProblemData(problemData));
269    }
270    public override IClassificationSolution CreateClassificationSolution(IClassificationProblemData problemData) {
271      return new NearestNeighbourClassificationSolution(this, new ClassificationProblemData(problemData));
272    }
273
274    #region events
275    public event EventHandler Changed;
276    private void OnChanged(EventArgs e) {
277      var handlers = Changed;
278      if (handlers != null)
279        handlers(this, e);
280    }
281    #endregion
282
283
284    // BackwardsCompatibility3.3
285    #region Backwards compatible code, remove with 3.4
286
287    private bool isCompatibilityLoaded = false; // new kNN models have the value false, kNN models loaded from disc have the value true
288    [Storable(DefaultValue = true)]
289    public bool IsCompatibilityLoaded {
290      get { return isCompatibilityLoaded; }
291      set { isCompatibilityLoaded = value; }
292    }
293    #endregion
294    #region persistence
295    [Storable]
296    public double KDTreeApproxF {
297      get { return kdTree.approxf; }
298      set { kdTree.approxf = value; }
299    }
300    [Storable]
301    public double[] KDTreeBoxMax {
302      get { return kdTree.boxmax; }
303      set { kdTree.boxmax = value; }
304    }
305    [Storable]
306    public double[] KDTreeBoxMin {
307      get { return kdTree.boxmin; }
308      set { kdTree.boxmin = value; }
309    }
310    [Storable]
311    public double[] KDTreeBuf {
312      get { return kdTree.buf; }
313      set { kdTree.buf = value; }
314    }
315    [Storable]
316    public double[] KDTreeCurBoxMax {
317      get { return kdTree.curboxmax; }
318      set { kdTree.curboxmax = value; }
319    }
320    [Storable]
321    public double[] KDTreeCurBoxMin {
322      get { return kdTree.curboxmin; }
323      set { kdTree.curboxmin = value; }
324    }
325    [Storable]
326    public double KDTreeCurDist {
327      get { return kdTree.curdist; }
328      set { kdTree.curdist = value; }
329    }
330    [Storable]
331    public int KDTreeDebugCounter {
332      get { return kdTree.debugcounter; }
333      set { kdTree.debugcounter = value; }
334    }
335    [Storable]
336    public int[] KDTreeIdx {
337      get { return kdTree.idx; }
338      set { kdTree.idx = value; }
339    }
340    [Storable]
341    public int KDTreeKCur {
342      get { return kdTree.kcur; }
343      set { kdTree.kcur = value; }
344    }
345    [Storable]
346    public int KDTreeKNeeded {
347      get { return kdTree.kneeded; }
348      set { kdTree.kneeded = value; }
349    }
350    [Storable]
351    public int KDTreeN {
352      get { return kdTree.n; }
353      set { kdTree.n = value; }
354    }
355    [Storable]
356    public int[] KDTreeNodes {
357      get { return kdTree.nodes; }
358      set { kdTree.nodes = value; }
359    }
360    [Storable]
361    public int KDTreeNormType {
362      get { return kdTree.normtype; }
363      set { kdTree.normtype = value; }
364    }
365    [Storable]
366    public int KDTreeNX {
367      get { return kdTree.nx; }
368      set { kdTree.nx = value; }
369    }
370    [Storable]
371    public int KDTreeNY {
372      get { return kdTree.ny; }
373      set { kdTree.ny = value; }
374    }
375    [Storable]
376    public double[] KDTreeR {
377      get { return kdTree.r; }
378      set { kdTree.r = value; }
379    }
380    [Storable]
381    public double KDTreeRNeeded {
382      get { return kdTree.rneeded; }
383      set { kdTree.rneeded = value; }
384    }
385    [Storable]
386    public bool KDTreeSelfMatch {
387      get { return kdTree.selfmatch; }
388      set { kdTree.selfmatch = value; }
389    }
390    [Storable]
391    public double[] KDTreeSplits {
392      get { return kdTree.splits; }
393      set { kdTree.splits = value; }
394    }
395    [Storable]
396    public int[] KDTreeTags {
397      get { return kdTree.tags; }
398      set { kdTree.tags = value; }
399    }
400    [Storable]
401    public double[] KDTreeX {
402      get { return kdTree.x; }
403      set { kdTree.x = value; }
404    }
405    [Storable]
406    public double[,] KDTreeXY {
407      get { return kdTree.xy; }
408      set { kdTree.xy = value; }
409    }
410    #endregion
411  }
412}
Note: See TracBrowser for help on using the repository browser.