Changeset 8454 for branches/NCA

Timestamp:

08/09/12 02:17:57 (12 years ago)

Author:

abeham

Message:

#1913:

• Refactored NCAModel and NeighborhoodComponentsAnalysis algorithm
• Model now includes NearestNeighborModel
• Algorithm has ability to be canceled (basically recreated the optimization loop of mincgoptimize)
• Scaling should work properly now

Location:

branches/NCA/HeuristicLab.Algorithms.NCA/3.3

Files:

• NCAModel.cs (modified) (5 diffs)
• NeighborhoodComponentsAnalysis.cs (modified) (6 diffs)

branches/NCA/HeuristicLab.Algorithms.NCA/3.3/NCAModel.cs

@@ -20 +20 @@
 #endregion
 
-using System;
 using System.Collections.Generic;
 using System.Linq;
@@ -35 +34 @@
 
     [Storable]
-    private string targetVariable;
-    [Storable]
-    private string[] allowedInputVariables;
-    [Storable]
-    private double[] classValues;
-    /// <summary>
-    /// Get a clone of the class values
-    /// </summary>
-    public double[] ClassValues {
-      get { return (double[])classValues.Clone(); }
-    }
-    [Storable]
-    private int k;
+    private Scaling scaling;
     [Storable]
     private double[,] transformationMatrix;
-    /// <summary>
-    /// Get a clone of the transformation matrix
-    /// </summary>
     public double[,] TransformationMatrix {
       get { return (double[,])transformationMatrix.Clone(); }
     }
     [Storable]
-    private double[,] transformedTrainingset;
-    /// <summary>
-    /// Get a clone of the transformed trainingset
-    /// </summary>
-    public double[,] TransformedTrainingset {
-      get { return (double[,])transformedTrainingset.Clone(); }
-    }
+    private string[] allowedInputVariables;
     [Storable]
-    private Scaling scaling;
+    private string targetVariable;
+    [Storable]
+    private INearestNeighbourModel nnModel;
+    [Storable]
+    private Dictionary<double, double> nn2ncaClassMapping;
+    [Storable]
+    private Dictionary<double, double> nca2nnClassMapping;
 
     [StorableConstructor]
@@ -71 +55 @@
     protected NCAModel(NCAModel original, Cloner cloner)
       : base(original, cloner) {
-      k = original.k;
-      targetVariable = original.targetVariable;
-      allowedInputVariables = (string[])original.allowedInputVariables.Clone();
-      if (original.classValues != null)
-        this.classValues = (double[])original.classValues.Clone();
-      if (original.transformationMatrix != null)
-        this.transformationMatrix = (double[,])original.transformationMatrix.Clone();
-      if (original.transformedTrainingset != null)
-        this.transformedTrainingset = (double[,])original.transformedTrainingset.Clone();
       this.scaling = cloner.Clone(original.scaling);
+      this.transformationMatrix = (double[,])original.transformationMatrix.Clone();
+      this.allowedInputVariables = (string[])original.allowedInputVariables.Clone();
+      this.targetVariable = original.targetVariable;
+      this.nnModel = cloner.Clone(original.nnModel);
+      this.nn2ncaClassMapping = original.nn2ncaClassMapping.ToDictionary(x => x.Key, y => y.Value);
+      this.nca2nnClassMapping = original.nca2nnClassMapping.ToDictionary(x => x.Key, y => y.Value);
     }
-    public NCAModel(double[,] transformedTrainingset, Scaling scaling, double[,] transformationMatrix, int k, string targetVariable, IEnumerable<string> allowedInputVariables, double[] classValues = null)
-      : base() {
-      this.name = ItemName;
-      this.description = ItemDescription;
-      this.transformedTrainingset = transformedTrainingset;
+    public NCAModel(int k, double[,] scaledData, Scaling scaling, double[,] transformationMatrix, string targetVariable, IEnumerable<double> targetVector, IEnumerable<string> allowedInputVariables) {
+      Name = ItemName;
+      Description = ItemDescription;
       this.scaling = scaling;
       this.transformationMatrix = transformationMatrix;
-      this.k = k;
+      this.allowedInputVariables = allowedInputVariables.ToArray();
       this.targetVariable = targetVariable;
-      this.allowedInputVariables = allowedInputVariables.ToArray();
-      if (classValues != null)
-        this.classValues = (double[])classValues.Clone();
+
+      nca2nnClassMapping = targetVector.Distinct().OrderBy(x => x).Select((v, i) => new { Index = (double)i, Class = v }).ToDictionary(x => x.Class, y => y.Index);
+      nn2ncaClassMapping = nca2nnClassMapping.ToDictionary(x => x.Value, y => y.Key);
+
+      var transformedData = ReduceWithTarget(scaledData, targetVector.Select(x => nca2nnClassMapping[x]));
+
+      var kdtree = new alglib.nearestneighbor.kdtree();
+      alglib.nearestneighbor.kdtreebuild(transformedData, transformedData.GetLength(0), transformedData.GetLength(1) - 1, 1, 2, kdtree);
+
+      nnModel = new NearestNeighbourModel(kdtree, k, targetVariable,
+        Enumerable.Range(0, transformationMatrix.GetLength(1)).Select(x => x.ToString()),
+        nn2ncaClassMapping.Keys.ToArray());
     }
 
@@ -101 +89 @@
 
     public IEnumerable<double> GetEstimatedClassValues(Dataset dataset, IEnumerable<int> rows) {
-      var k = Math.Min(this.k, transformedTrainingset.GetLength(0));
-      var transformedRow = new double[transformationMatrix.GetLength(1)];
-      var kVotes = new SortedList<double, double>(k + 1);
-      foreach (var r in rows) {
-        for (int i = 0; i < transformedRow.Length; i++) transformedRow[i] = 0;
-        int j = 0;
-        foreach (var v in allowedInputVariables) {
-          var values = scaling.GetScaledValues(dataset, v, rows);
-          double val = dataset.GetDoubleValue(v, r);
-          for (int i = 0; i < transformedRow.Length; i++)
-            transformedRow[i] += val * transformationMatrix[j, i];
-          j++;
+      var unknownClasses = dataset.GetDoubleValues(targetVariable, rows).Where(x => !nca2nnClassMapping.ContainsKey(x));
+      if (unknownClasses.Any())
+        foreach (var uc in unknownClasses) {
+          nca2nnClassMapping[uc] = nca2nnClassMapping.Count;
+          nn2ncaClassMapping[nca2nnClassMapping[uc]] = uc;
         }
-        kVotes.Clear();
-        for (int a = 0; a < transformedTrainingset.GetLength(0); a++) {
-          double d = 0;
-          for (int y = 0; y < transformedRow.Length; y++) {
-            d += (transformedRow[y] - transformedTrainingset[a, y]) * (transformedRow[y] - transformedTrainingset[a, y]);
-          }
-          while (kVotes.ContainsKey(d)) d += 1e-12;
-          if (kVotes.Count <= k || kVotes.Last().Key > d) {
-            kVotes.Add(d, classValues[a]);
-            if (kVotes.Count > k) kVotes.RemoveAt(kVotes.Count - 1);
-          }
-        }
-        yield return kVotes.Values.ToLookup(x => x).MaxItems(x => x.Count()).First().Key;
-      }
+      var transformedData = ReduceWithTarget(dataset, rows, dataset.GetDoubleValues(targetVariable, rows).Select(x => nca2nnClassMapping[x]));
+      var ds = new Dataset(Enumerable.Range(0, transformationMatrix.GetLength(1)).Select(x => x.ToString()).Concat(targetVariable.ToEnumerable()), transformedData);
+      return nnModel.GetEstimatedClassValues(ds, Enumerable.Range(0, ds.Rows)).Select(x => nn2ncaClassMapping[x]);
     }
+
     public NCAClassificationSolution CreateClassificationSolution(IClassificationProblemData problemData) {
       return new NCAClassificationSolution(problemData, this);
     }
+
     IClassificationSolution IClassificationModel.CreateClassificationSolution(IClassificationProblemData problemData) {
       return CreateClassificationSolution(problemData);
@@ -137 +109 @@
 
     public double[,] Reduce(Dataset dataset, IEnumerable<int> rows) {
-      var result = new double[rows.Count(), transformationMatrix.GetLength(1)];
-      int v = 0;
-      foreach (var r in rows) {
-        int i = 0;
-        foreach (var variable in allowedInputVariables) {
-          double val = dataset.GetDoubleValue(variable, r);
-          for (int j = 0; j < result.GetLength(1); j++)
-            result[v, j] += val * transformationMatrix[i, j];
-          i++;
-        }
-        v++;
-      }
+      var scaledData = AlglibUtil.PrepareAndScaleInputMatrix(dataset, allowedInputVariables, rows, scaling);
+      return Reduce(scaledData);
+    }
+
+    private double[,] Reduce(double[,] scaledData) {
+      var result = new double[scaledData.GetLength(0), transformationMatrix.GetLength(1)];
+      for (int i = 0; i < scaledData.GetLength(0); i++)
+        for (int j = 0; j < scaledData.GetLength(1); j++)
+          for (int x = 0; x < transformationMatrix.GetLength(1); x++) {
+            result[i, x] += scaledData[i, j] * transformationMatrix[j, x];
+          }
+      return result;
+    }
+
+    private double[,] ReduceWithTarget(Dataset dataset, IEnumerable<int> rows, IEnumerable<double> targetValues) {
+      var scaledData = AlglibUtil.PrepareAndScaleInputMatrix(dataset, allowedInputVariables, rows, scaling);
+      return ReduceWithTarget(scaledData, targetValues);
+    }
+
+    private double[,] ReduceWithTarget(double[,] scaledData, IEnumerable<double> targetValues) {
+      var result = new double[scaledData.GetLength(0), transformationMatrix.GetLength(1) + 1];
+      for (int i = 0; i < scaledData.GetLength(0); i++)
+        for (int j = 0; j < scaledData.GetLength(1); j++)
+          for (int x = 0; x < transformationMatrix.GetLength(1); x++) {
+            result[i, x] += scaledData[i, j] * transformationMatrix[j, x];
+          }
+
+      int r = 0;
+      foreach (var d in targetValues) result[r++, transformationMatrix.GetLength(1)] = d;
+
       return result;
     }

branches/NCA/HeuristicLab.Algorithms.NCA/3.3/NeighborhoodComponentsAnalysis.cs

@@ -23 +23 @@
 using System.Collections.Generic;
 using System.Linq;
+using System.Threading;
 using HeuristicLab.Algorithms.DataAnalysis;
 using HeuristicLab.Analysis;
@@ -35 +36 @@
 
 namespace HeuristicLab.Algorithms.NCA {
-  public delegate void Reporter(double quality, double[] coefficients);
+  internal delegate void Reporter(double quality, double[] coefficients);
   /// <summary>
   /// Neighborhood Components Analysis
@@ -97 +98 @@
 
       var clonedProblem = (IClassificationProblemData)Problem.ProblemData.Clone();
-      var model = Train(clonedProblem, k, dimensions, initializer, ReportQuality);
+      var model = Train(clonedProblem, k, dimensions, initializer.Initialize(clonedProblem, dimensions), ReportQuality, CancellationToken.None);
       var classification = new NCAClassificationSolution(clonedProblem, model);
       Results.Add(new Result("ClassificationSolution", "The classification solution.", classification));
@@ -117 +118 @@
     }
 
-    public static INCAModel Train(IClassificationProblemData data, int k, int dimensions, INCAInitializer initializer, Reporter reporter = null) {
-      var instances = data.TrainingIndices.Count();
-      var attributes = data.AllowedInputVariables.Count();
-
-      double[] matrix = initializer.Initialize(data, dimensions);
-
-      var info = new OptimizationInfo(data, dimensions, reporter);
+    public static INCAModel Train(IClassificationProblemData problemData, int k, int dimensions, INCAInitializer initializer) {
+      return Train(problemData, k, dimensions, initializer.Initialize(problemData, dimensions), null, CancellationToken.None);
+    }
+
+    public static INCAModel Train(IClassificationProblemData problemData, int k, int dimensions, double[,] initalMatrix) {
+      var matrix = new double[initalMatrix.Length];
+      for (int i = 0; i < initalMatrix.GetLength(0); i++)
+        for (int j = 0; j < initalMatrix.GetLength(1); j++)
+          matrix[i * initalMatrix.GetLength(1) + j] = initalMatrix[i, j];
+      return Train(problemData, k, dimensions, matrix, null, CancellationToken.None);
+    }
+
+    private static INCAModel Train(IClassificationProblemData data, int k, int dimensions, double[] matrix, Reporter reporter, CancellationToken cancellation) {
+      var scaling = new Scaling(data.Dataset, data.AllowedInputVariables, data.TrainingIndices);
+      var scaledData = AlglibUtil.PrepareAndScaleInputMatrix(data.Dataset, data.AllowedInputVariables, data.TrainingIndices, scaling);
+      var classes = data.Dataset.GetDoubleValues(data.TargetVariable, data.TrainingIndices).ToArray();
+      var instances = scaledData.GetLength(0);
+      var attributes = scaledData.GetLength(1);
+
       alglib.mincgstate state;
       alglib.mincgreport rep;
-
       alglib.mincgcreate(matrix, out state);
-      alglib.mincgsetcond(state, 0, 1e-05, 0, 20);
+      alglib.mincgsetcond(state, 0, 0, 0, 20);
       alglib.mincgsetxrep(state, true);
-      alglib.mincgoptimize(state, Gradient, Report, info);
+      Optimize(state, scaledData, classes, dimensions, cancellation, reporter);
       alglib.mincgresults(state, out matrix, out rep);
 
@@ -139 +151 @@
           transformationMatrix[i, j] = matrix[counter++];
 
-      var transformedTrainingset = new double[instances, dimensions];
-      var rowCount = 0;
-      foreach (var r in data.TrainingIndices) {
-        var i = 0;
-        foreach (var v in data.AllowedInputVariables) {
-          var val = data.Dataset.GetDoubleValue(v, r);
-          for (var j = 0; j < dimensions; j++)
-            transformedTrainingset[rowCount, j] += val * transformationMatrix[i, j];
-          i++;
-        }
-        rowCount++;
-      }
-
-      var ds = data.Dataset;
-      var targetVariable = data.TargetVariable;
-      return new NCAModel(transformedTrainingset, info.Scaling, transformationMatrix, k, data.TargetVariable, data.AllowedInputVariables,
-        data.TrainingIndices.Select(i => ds.GetDoubleValue(targetVariable, i)).ToArray());
-    }
-
-    private static void Report(double[] A, double func, object obj) {
-      var info = (OptimizationInfo)obj;
-      if (info.Reporter != null) info.Reporter(func, A);
-    }
-
-    private static void Gradient(double[] A, ref double func, double[] grad, object obj) {
-      var info = (OptimizationInfo)obj;
-      var data = info.Data;
-      var classes = info.TargetValues;
-      var instances = info.Instances;
-      var attributes = info.Attributes;
-
-      var AMatrix = new Matrix(A, A.Length / info.ReduceDimensions, info.ReduceDimensions);
+      return new NCAModel(k, scaledData, scaling, transformationMatrix, data.TargetVariable, data.Dataset.GetDoubleValues(data.TargetVariable, data.TrainingIndices), data.AllowedInputVariables);
+    }
+
+    private static void Optimize(alglib.mincgstate state, double[,] data, double[] classes, int dimensions, CancellationToken cancellation, Reporter reporter) {
+      while (alglib.mincgiteration(state)) {
+
+        if (cancellation.IsCancellationRequested) break;
+
+        if (state.needfg) {
+          Gradient(state.x, ref state.innerobj.f, state.innerobj.g, data, classes, dimensions);
+          continue;
+        }
+
+        if (state.innerobj.xupdated) {
+          if (reporter != null)
+            reporter(state.innerobj.f, state.innerobj.x);
+          continue;
+        }
+
+        throw new InvalidOperationException("Neighborhood Components Analysis: Error in Optimize() (some derivatives were not provided?)");
+      }
+    }
+
+    private static void Gradient(double[] A, ref double func, double[] grad, double[,] data, double[] classes, int dimensions) {
+      var instances = data.GetLength(0);
+      var attributes = data.GetLength(1);
+
+      var AMatrix = new Matrix(A, A.Length / dimensions, dimensions);
 
       alglib.sparsematrix probabilities;
@@ -222 +230 @@
     }
 
-    #region Helpers
     private static IEnumerable<double> GetRow(double[,] data, int row) {
       for (int i = 0; i < data.GetLength(1); i++)
         yield return data[row, i];
     }
-
-    private class OptimizationInfo {
-      public Scaling Scaling { get; private set; }
-      public double[,] Data { get; private set; }
-      public double[] TargetValues { get; private set; }
-      public int ReduceDimensions { get; private set; }
-      public int Instances { get; private set; }
-      public int Attributes { get; private set; }
-      public Reporter Reporter { get; private set; }
-
-      public OptimizationInfo(IClassificationProblemData data, int reduceDimensions, Reporter reporter) {
-        this.Scaling = new Scaling(data.Dataset, data.AllowedInputVariables, data.TrainingIndices);
-        this.Data = AlglibUtil.PrepareAndScaleInputMatrix(data.Dataset, data.AllowedInputVariables, data.TrainingIndices, Scaling);
-        this.TargetValues = data.Dataset.GetDoubleValues(data.TargetVariable, data.TrainingIndices).ToArray();
-        this.ReduceDimensions = reduceDimensions;
-        this.Instances = data.TrainingIndices.Count();
-        this.Attributes = data.AllowedInputVariables.Count();
-        this.Reporter = reporter;
-      }
-    }
-    #endregion
   }
 }