Changeset 6338

Timestamp:

05/30/11 17:21:30 (13 years ago)

Author:

abeham

Message:

#1539

• changed MDS optimization algorithm to Levenberg-Marquardt

Location:

branches/histogram/HeuristicLab.Analysis/3.3

Files:

• MultidimensionalScaling/MultidimensionalScaling.cs (modified) (4 diffs)
• Tests/MultidimensionalScalingTest.cs (modified) (2 diffs)

branches/histogram/HeuristicLab.Analysis/3.3/MultidimensionalScaling/MultidimensionalScaling.cs

@@ -68 +68 @@
     /// In every iteration it tries to find the best location for every item.</param>
     /// <returns>A Nx2 matrix where the first column represents the x- and the second column the y coordinates.</returns>
-    public static DoubleMatrix KruskalShepard(DoubleMatrix dissimilarities, DoubleMatrix coordinates, int maximumIterations = 20) {
+    public static DoubleMatrix KruskalShepard(DoubleMatrix dissimilarities, DoubleMatrix coordinates, int maximumIterations = 10) {
       int dimension = dissimilarities.Rows;
       if (dimension != dissimilarities.Columns || coordinates.Rows != dimension) throw new ArgumentException("The number of coordinates and the number of rows and columns in the dissimilarities matrix do not match.");
@@ -75 +75 @@
       double epsf = 0;
       double epsx = 0;
-      int maxits = 100;
-      alglib.mincgstate state = null;
-      alglib.mincgreport rep;
+      int maxits = 0;
 
+      alglib.minlmstate state;
+      alglib.minlmreport rep;
       for (int iterations = 0; iterations < maximumIterations; iterations++) {
         bool changed = false;
@@ -85 +85 @@
 
           try {
-            if ((iterations == 0 && i == 0)) {
-              alglib.mincgcreate(c, out state);
-              alglib.mincgsetcond(state, epsg, epsf, epsx, maxits);
-            } else {
-              alglib.mincgrestartfrom(state, c);
-            }
-            alglib.mincgoptimize(state, StressGradient, null, new Info(coordinates, dissimilarities, i));
-            alglib.mincgresults(state, out c, out rep);
+            alglib.minlmcreatevj(dimension - 1, c, out state);
+            alglib.minlmsetcond(state, epsg, epsf, epsx, maxits);
+            alglib.minlmoptimize(state, StressFitness, StressJacobian, null, new Info(coordinates, dissimilarities, i));
+            alglib.minlmresults(state, out c, out rep);
           } catch (alglib.alglibexception) { }
           if (!double.IsNaN(c[0]) && !double.IsNaN(c[1])) {
@@ -105 +101 @@
     }
 
-    // computes the function and the gradient of the raw stress function.
-    private static void StressGradient(double[] x, ref double func, double[] grad, object obj) {
-      func = 0; grad[0] = 0; grad[1] = 0;
+    private static void StressFitness(double[] x, double[] fi, object obj) {
       Info info = (obj as Info);
       for (int i = 0; i < info.Coordinates.Rows; i++) {
-        double c = info.Dissimilarities[info.Row, i];
+        double f = Stress(x, info.Dissimilarities[info.Row, i], info.Coordinates[i, 0], info.Coordinates[i, 1]);
+        if (i < info.Row) fi[i] = f;
+        else if (i > info.Row) fi[i - 1] = f;
+      }
+    }
+
+    private static void StressJacobian(double[] x, double[] fi, double[,] jac, object obj) {
+      Info info = (obj as Info);
+      int idx = 0;
+      for (int i = 0; i < info.Coordinates.Rows; i++) {
         if (i != info.Row) {
+          double c = info.Dissimilarities[info.Row, i];
           double a = info.Coordinates[i, 0];
           double b = info.Coordinates[i, 1];
-          func += Stress(x, c, a, b);
-          grad[0] += ((2 * x[0] - 2 * a) * Math.Sqrt(x[1] * x[1] - 2 * b * x[1] + x[0] * x[0] - 2 * a * x[0] + b * b + a * a) - 2 * c * x[0] + 2 * a * c) / Math.Sqrt(x[1] * x[1] - 2 * b * x[1] + x[0] * x[0] - 2 * a * x[0] + b * b + a * a);
-          grad[1] += ((2 * x[1] - 2 * b) * Math.Sqrt(x[1] * x[1] - 2 * b * x[1] + x[0] * x[0] - 2 * a * x[0] + b * b + a * a) - 2 * c * x[1] + 2 * b * c) / Math.Sqrt(x[1] * x[1] - 2 * b * x[1] + x[0] * x[0] - 2 * a * x[0] + b * b + a * a);
+          double f = Stress(x, c, a, b);
+          fi[idx] = f;
+          jac[idx, 0] = 2 * (x[0] - a) * (Math.Sqrt((a - x[0]) * (a - x[0]) + (b - x[1]) * (b - x[1])) - c) / Math.Sqrt((a - x[0]) * (a - x[0]) + (b - x[1]) * (b - x[1]));
+          jac[idx, 1] = 2 * (x[1] - b) * (Math.Sqrt((a - x[0]) * (a - x[0]) + (b - x[1]) * (b - x[1])) - c) / Math.Sqrt((a - x[0]) * (a - x[0]) + (b - x[1]) * (b - x[1]));
+          idx++;
         }
       }

branches/histogram/HeuristicLab.Analysis/3.3/Tests/MultidimensionalScalingTest.cs

@@ -21 +21 @@
 
 using System;
+using System.Globalization;
 using HeuristicLab.Data;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
@@ -42 +43 @@
       distances3[0, 2] = distances3[2, 0] = 6.4;
       distances3[1, 2] = distances3[2, 1] = 5;
-      stress = MultidimensionalScaling.CalculateNormalizedStress(distances3,
-        MultidimensionalScaling.KruskalShepard(distances3));
+      DoubleMatrix coords3 = MultidimensionalScaling.KruskalShepard(distances3);
+      Console.WriteLine("Coordinates: ");
+      Console.WriteLine("A = ({0}, {1}), B = ({2}, {3}), C = ({4}, {5})", coords3[0, 0], coords3[0, 1], coords3[1, 0], coords3[1, 1], coords3[2, 0], coords3[2, 1]);
+      stress = MultidimensionalScaling.CalculateNormalizedStress(distances3, coords3);
+      Console.WriteLine("Stress = " + stress.ToString(CultureInfo.InvariantCulture.NumberFormat));
       Assert.IsTrue(stress < 0.1);
       DoubleMatrix distances4 = new DoubleMatrix(4, 4);