Changeset 8437 for branches/NCA/HeuristicLab.Algorithms.NCA/3.3/NeighborhoodComponentsAnalysis.cs

Timestamp:

08/08/12 16:46:53 (12 years ago)

Author:

abeham

Message:

#1913:

• Improved speed of NCA
• Reorganized things

File:

• branches/NCA/HeuristicLab.Algorithms.NCA/3.3/NeighborhoodComponentsAnalysis.cs (modified) (2 diffs)

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

@@ -1 @@
-#region License Information
+#region License Information
 /* HeuristicLab
  * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
@@ -20 +20 @@
 #endregion
 
-using System;
-using System.Collections.Generic;
 using System.Linq;
+using HeuristicLab.Algorithms.DataAnalysis;
 using HeuristicLab.Common;
+using HeuristicLab.Core;
+using HeuristicLab.Data;
+using HeuristicLab.Optimization;
+using HeuristicLab.Parameters;
+using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.PluginInfrastructure;
 using HeuristicLab.Problems.DataAnalysis;
 
 namespace HeuristicLab.Algorithms.NCA {
-  public class NeighborhoodComponentsAnalysis {
+  /// <summary>
+  /// Neighborhood Components Analysis
+  /// </summary>
+  [Item("Neighborhood Components Analysis", "NCA is described in J. Goldberger, S. Roweis, G. Hinton, R. Salakhutdinov. 2005. Neighbourhood Component Analysis. Advances in Neural Information Processing Systems, 17. pp. 513-520.")]
+  [Creatable("Data Analysis")]
+  [StorableClass]
+  public sealed class NeighborhoodComponentsAnalysis : FixedDataAnalysisAlgorithm<IClassificationProblem> {
+    #region Parameter Properties
+    public IValueLookupParameter<IntValue> KParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["k"]; }
+    }
+    public IValueLookupParameter<IntValue> ReduceDimensionsParameter {
+      get { return (IValueLookupParameter<IntValue>)Parameters["ReduceDimensions"]; }
+    }
+    private IConstrainedValueParameter<INCAInitializer> InitializationParameter {
+      get { return (IConstrainedValueParameter<INCAInitializer>)Parameters["Initialization"]; }
+    }
+    #endregion
 
-    public static INCAModel Train(IClassificationProblemData data, int k, int reduceDimensions, INCAInitializer initializer) {
-      var instances = data.TrainingIndices.Count();
-      var attributes = data.AllowedInputVariables.Count();
+    #region Properties
+    public IntValue K {
+      get { return KParameter.Value; }
+    }
+    public IntValue ReduceDimensions {
+      get { return ReduceDimensionsParameter.Value; }
+    }
+    #endregion
 
-      double[] matrix = initializer.Initialize(data, reduceDimensions);
+    [StorableConstructor]
+    private NeighborhoodComponentsAnalysis(bool deserializing) : base(deserializing) { }
+    private NeighborhoodComponentsAnalysis(NeighborhoodComponentsAnalysis original, Cloner cloner) : base(original, cloner) { }
+    public NeighborhoodComponentsAnalysis()
+      : base() {
+      Parameters.Add(new ValueLookupParameter<IntValue>("k", "The k for the nearest neighbor.", new IntValue(1)));
+      Parameters.Add(new ValueLookupParameter<IntValue>("ReduceDimensions", "The number of dimensions that NCA should reduce the data to.", new IntValue(2)));
+      Parameters.Add(new ConstrainedValueParameter<INCAInitializer>("Initialization", "Which method should be used to initialize the matrix. Typically LDA (linear discriminant analysis) should provide a good estimate."));
 
-      alglib.mincgstate state;
-      alglib.mincgreport rep;
+      INCAInitializer defaultInitializer = null;
+      foreach (var initializer in ApplicationManager.Manager.GetInstances<INCAInitializer>().OrderBy(x => x.ItemName)) {
+        if (initializer is LDAInitializer) defaultInitializer = initializer;
+        InitializationParameter.ValidValues.Add(initializer);
+      }
+      if (defaultInitializer != null) InitializationParameter.Value = defaultInitializer;
 
-      // first run
-      alglib.mincgcreate(matrix, out state);
-      alglib.mincgsetcond(state, 0.0000000001, 0, 0, 0);
-      alglib.mincgoptimize(state, Gradient, null, new OptimizationInfo(data, reduceDimensions));
-      alglib.mincgresults(state, out matrix, out rep);
-
-      var transformationMatrix = new double[attributes, reduceDimensions];
-      var counter = 0;
-      for (var i = 0; i < attributes; i++)
-        for (var j = 0; j < reduceDimensions; j++)
-          transformationMatrix[i, j] = matrix[counter++];
-
-      var transformedTrainingset = new double[instances, reduceDimensions];
-      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 < reduceDimensions; j++)
-            transformedTrainingset[rowCount, j] += val * transformationMatrix[i, j];
-          i++;
-        }
-        rowCount++;
-      }
-
-      return new NCAModel(transformedTrainingset, transformationMatrix, k, data.TargetVariable, data.AllowedInputVariables,
-        data.Dataset.GetDoubleValues(data.TargetVariable)
-          .Select((v, i) => new { I = i, V = v })
-          .Where(x => x.I >= data.TrainingPartition.Start && x.I < data.TrainingPartition.End
-              && !(x.I >= data.TestPartition.Start && x.I < data.TestPartition.End))
-          .Select(x => x.V).ToArray());
+      Problem = new ClassificationProblem();
     }
 
-    private static void Gradient(double[] A, ref double func, double[] grad, object obj) {
-      var info = (OptimizationInfo)obj;
-      var instances = info.ProblemData.TrainingIndices.ToArray();
-      var attributes = info.ProblemData.AllowedInputVariables.Count();
-      var AMatrix = new Matrix(A, A.Length / info.ReduceDimensions, info.ReduceDimensions);
-
-      alglib.sparsematrix probabilities;
-      alglib.sparsecreate(instances.Length, instances.Length, out probabilities);
-      var distances = new double[instances.Length];
-      for (int i = 0; i < instances.Length - 1; i++) {
-        var iVector = new Matrix(GetRow(info.ProblemData, instances[i]));
-        var denom = 0.0;
-        for (int k = 0; k < instances.Length; k++) {
-          if (k == i) continue;
-          var kVector = new Matrix(GetRow(info.ProblemData, instances[k]));
-          distances[k] = iVector.Multiply(AMatrix).Subtract(kVector.Multiply(AMatrix)).Length();
-          denom += Math.Exp(-(distances[k] * distances[k]));
-        }
-        if (denom > 0) {
-          for (int j = i + 1; j < instances.Length; j++) {
-            if (i == j) continue;
-            var v = Math.Exp(-(distances[j] * distances[j])) / denom;
-            alglib.sparseset(probabilities, i, j, v);
-            alglib.sparseset(probabilities, j, i, v);
-          }
-        }
-      }
-      alglib.sparseconverttocrs(probabilities); // needed to enumerate in order (top-down and left-right)
-
-      int t0 = 0, t1 = 0, r, c;
-      double val;
-      var classes = info.ProblemData.Dataset.GetDoubleValues(info.ProblemData.TargetVariable, instances).ToArray();
-      var pi = new double[instances.Length];
-      while (alglib.sparseenumerate(probabilities, ref t0, ref t1, out r, out c, out val)) {
-        if (classes[r].IsAlmost(classes[c]))
-          pi[r] += val;
-      }
-
-      var innerSum = new double[attributes, attributes];
-      while (alglib.sparseenumerate(probabilities, ref t0, ref t1, out r, out c, out val)) {
-        var vector = new Matrix(GetRow(info.ProblemData, instances[r])).Subtract(new Matrix(GetRow(info.ProblemData, instances[c]))).Apply();
-        vector.OuterProduct(vector).Multiply(val * pi[r]).AddTo(innerSum);
-
-        if (classes[r].IsAlmost(classes[c])) {
-          vector.OuterProduct(vector).Multiply(-val).AddTo(innerSum);
-        }
-      }
-
-      func = -pi.Sum();
-
-      grad = AMatrix.Multiply(-2.0).Transpose().Multiply(new Matrix(innerSum)).Transpose().ToArray();
+    public override IDeepCloneable Clone(Cloner cloner) {
+      return new NeighborhoodComponentsAnalysis(this, cloner);
     }
 
-    private static IEnumerable<double> GetRow(IClassificationProblemData data, int row) {
-      return data.AllowedInputVariables.Select(v => data.Dataset.GetDoubleValue(v, row));
+    public override void Prepare() {
+      if (Problem != null) base.Prepare();
     }
 
-    public static NCAClassificationSolution CreateNCASolution(IClassificationProblemData problemData, int k, int reduceDimensions, INCAInitializer initializer) {
-      return new NCAClassificationSolution(problemData, Train(problemData, k, reduceDimensions, initializer));
-    }
+    protected override void Run() {
+      var k = K.Value;
+      var dimensions = ReduceDimensions.Value;
+      var initializer = InitializationParameter.Value;
 
-    private class OptimizationInfo {
-      public IClassificationProblemData ProblemData { get; set; }
-      public int ReduceDimensions { get; set; }
-      public OptimizationInfo(IClassificationProblemData problem, int reduceDimensions) {
-        this.ProblemData = problem;
-        this.ReduceDimensions = reduceDimensions;
-      }
+      var clonedProblem = (IClassificationProblemData)Problem.ProblemData.Clone();
+      var classification = new NCAClassificationSolution(clonedProblem, Auxiliary.Train(clonedProblem, k, dimensions, initializer));
+      Results.Add(new Result("ClassificationSolution", "The classification solution.", classification));
+      // TODO: result that shows the LOO performance
     }
   }