Free cookie consent management tool by TermsFeed Policy Generator

Changeset 5871


Ignore:
Timestamp:
03/29/11 16:54:52 (14 years ago)
Author:
abeham
Message:

#1330

  • Fixed normalized stress value
  • Changed method name and signature of MDS
  • Adapted unit tests
  • Adapted QAP View
Location:
branches/QAP
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • branches/QAP/HeuristicLab.Analysis/3.3/MultidimensionalScaling/MultidimensionalScaling.cs

    r5855 r5871  
    2929    /// Performs the Kruskal-Shepard algorithm and applies a gradient descent method
    3030    /// to fit the coordinates such that the difference between the fit distances
    31     /// and the actual distances is minimal.
     31    /// and the actual distances becomes minimal.
    3232    /// </summary>
    33     /// <param name="distances">A symmetric NxN matrix that specifies the distances between each element i and j. Diagonal elements are ignored.</param>
    34     /// <param name="stress">Returns the stress between the fit distances and the actual distances.</param>
     33    /// <remarks>
     34    /// It will initialize the coordinates in a deterministic fashion such that all initial points are equally spaced on a circle.
     35    /// </remarks>
     36    /// <param name="dissimilarities">A symmetric NxN matrix that specifies the distances between each element i and j. Diagonal elements are ignored.</param>
     37    ///
    3538    /// <returns>A Nx2 matrix where the first column represents the x- and the second column the y coordinates.</returns>
    36     public static DoubleMatrix MetricByDistance(DoubleMatrix distances, out double stress) {
    37       if (distances == null) throw new ArgumentNullException("distances");
    38       if (distances.Rows != distances.Columns) throw new ArgumentException("Distance matrix must be a square matrix.", "distances");
    39       stress = 0.0;
     39    public static DoubleMatrix KruskalShepard(DoubleMatrix dissimilarities) {
     40      if (dissimilarities == null) throw new ArgumentNullException("dissimilarities");
     41      if (dissimilarities.Rows != dissimilarities.Columns) throw new ArgumentException("Dissimilarities must be a square matrix.", "dissimilarities");
    4042
    41       int dimension = distances.Rows;
     43      int dimension = dissimilarities.Rows;
    4244      if (dimension == 1) return new DoubleMatrix(new double[,] { { 0, 0 } });
    43       else if (dimension == 2) return new DoubleMatrix(new double[,] { { 0, distances[0, 1] } });
     45      else if (dimension == 2) return new DoubleMatrix(new double[,] { { 0, dissimilarities[0, 1] } });
    4446
    4547      DoubleMatrix coordinates = new DoubleMatrix(dimension, 2);
    … …  
    5052      }
    5153
    52       return MetricByDistance(distances, out stress, coordinates);
     54      return KruskalShepard(dissimilarities, coordinates);
    5355    }
    5456
    55     public static DoubleMatrix MetricByDistance(DoubleMatrix distances, out double stress, DoubleMatrix coordinates) {
    56       int dimension = distances.Rows;
    57       if (dimension != distances.Columns || coordinates.Rows != dimension) throw new ArgumentException("distances or coordinates");
     57    /// <summary>
     58    /// Performs the Kruskal-Shepard algorithm and applies a gradient descent method
     59    /// to fit the coordinates such that the difference between the fit distances
     60    /// and the actual distances is minimal.
     61    /// </summary>
     62    /// <remarks>
     63    /// It will use a pre-initialized x,y-coordinates matrix as a starting point of the gradient descent.
     64    /// </remarks>
     65    /// <param name="dissimilarities">A symmetric NxN matrix that specifies the distances between each element i and j. Diagonal elements are ignored.</param>
     66    ///
     67    /// <param name="coordinates">The Nx2 matrix of initial coordinates.</param>
     68    /// <returns>A Nx2 matrix where the first column represents the x- and the second column the y coordinates.</returns>
     69    public static DoubleMatrix KruskalShepard(DoubleMatrix dissimilarities, DoubleMatrix coordinates) {
     70      int dimension = dissimilarities.Rows;
     71      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.");
    5872
    59       stress = 0.0;
    6073      double epsg = 1e-7;
    6174      double epsf = 0;
    … …  
    6578      alglib.mincgreport rep;
    6679
    67       for (int iterations = 0; iterations < 20; iterations++) {
     80      for (int iterations = 0; iterations < 10; iterations++) {
    6881        for (int i = 0; i < dimension; i++) {
    6982          double[] c = new double[] { coordinates[i, 0], coordinates[i, 1] };
    … …  
    7689              alglib.mincgrestartfrom(state, c);
    7790            }
    78             alglib.mincgoptimize(state, StressGradient, null, new Info(coordinates, distances, i));
     91            alglib.mincgoptimize(state, StressGradient, null, new Info(coordinates, dissimilarities, i));
    7992            alglib.mincgresults(state, out c, out rep);
    80           } catch (alglib.alglibexception e) { }
     93          } catch (alglib.alglibexception) { }
    8194          if (!double.IsNaN(c[0]) && !double.IsNaN(c[1])) {
    8295            coordinates[i, 0] = c[0];
    … …  
    8598        }
    8699      }
    87       stress = CalculateNormalizedStress(dimension, distances, coordinates);
    88100      return coordinates;
    89101    }
    90102
     103    // computes the function and the gradient of the raw stress function.
    91104    private static void StressGradient(double[] x, ref double func, double[] grad, object obj) {
    92105      func = 0; grad[0] = 0; grad[1] = 0;
    … …  
    114127    }
    115128
    116     public static double CalculateNormalizedStress(int dimension, DoubleMatrix distances, DoubleMatrix coordinates) {
     129    /// <summary>
     130    /// This method computes the normalized raw-stress value according to Groenen and van de Velden 2004. "Multidimensional Scaling". Technical report EI 2004-15.
     131    /// </summary>
     132    /// <remarks>
     133    /// Throws an ArgumentException when the <paramref name="dissimilarities"/> matrix is not symmetric.
     134    /// </remarks>
     135    ///
     136    /// <param name="dissimilarities">The matrix with the dissimilarities.</param>
     137    /// <param name="coordinates">The actual location of the points.</param>
     138    /// <returns>The normalized raw-stress value that describes the goodness-of-fit between the distances in the points and the size of the dissimilarities. If the value is &lt; 0.1 the fit is generally considered good. If between 0.1 and 0.2 it is considered acceptable, but the usefulness of the scaling with higher values is doubtful.</returns>
     139    public static double CalculateNormalizedStress(DoubleMatrix dissimilarities, DoubleMatrix coordinates) {
     140      int dimension = dissimilarities.Rows;
     141      if (dimension != dissimilarities.Columns || dimension != coordinates.Rows) throw new ArgumentException("The number of coordinates and the number of rows and columns in the dissimilarities matrix do not match.");
    117142      double stress = 0, normalization = 0;
    118143      for (int i = 0; i < dimension - 1; i++) {
    119144        for (int j = i + 1; j < dimension; j++) {
    120           if (distances[i, j] != 0) {
    121             stress += Stress(coordinates[i, 0], coordinates[i, 1], distances[i, j], coordinates[j, 0], coordinates[j, 1]);
    122             normalization += (distances[i, j] * distances[i, j]);
     145          if (dissimilarities[i, j] != dissimilarities[j, i]) throw new ArgumentException("Distances is not a symmetric matrix.", "distances");
     146          if (dissimilarities[i, j] != 0) {
     147            stress += Stress(coordinates[i, 0], coordinates[i, 1], dissimilarities[i, j], coordinates[j, 0], coordinates[j, 1]);
     148            normalization += (dissimilarities[i, j] * dissimilarities[i, j]);
    123149          }
    124150        }
    125151      }
    126       return Math.Sqrt(stress / normalization); ;
     152      return stress / normalization;
    127153    }
    128154

  • branches/QAP/HeuristicLab.Analysis/3.3/Tests/HeuristicLab.Analysis.Tests/MultidimensionalScalingTest.cs

    r5723 r5871  
    1414      distances3[0, 2] = distances3[2, 0] = 4;
    1515      distances3[1, 2] = distances3[2, 1] = 5;
    16       MultidimensionalScaling.MetricByDistance(distances3, out stress);
     16      stress = MultidimensionalScaling.CalculateNormalizedStress(distances3,
     17        MultidimensionalScaling.KruskalShepard(distances3));
    1718      Assert.IsTrue(stress < 0.1);
    1819      // Example 2: An arbitrary triangle
    … …  
    2021      distances3[0, 2] = distances3[2, 0] = 6.4;
    2122      distances3[1, 2] = distances3[2, 1] = 5;
    22       MultidimensionalScaling.MetricByDistance(distances3, out stress);
     23      stress = MultidimensionalScaling.CalculateNormalizedStress(distances3,
     24        MultidimensionalScaling.KruskalShepard(distances3));
    2325      Assert.IsTrue(stress < 0.1);
    2426      DoubleMatrix distances4 = new DoubleMatrix(4, 4);
    … …  
    3032      distances4[1, 3] = distances4[3, 1] = Math.Sqrt(2);
    3133      distances4[2, 3] = distances4[3, 2] = 1;
    32       MultidimensionalScaling.MetricByDistance(distances4, out stress);
     34      stress = MultidimensionalScaling.CalculateNormalizedStress(distances4,
     35        MultidimensionalScaling.KruskalShepard(distances4));
    3336      Assert.IsTrue(stress < 0.1);
    3437      // Example 4: A large square
    … …  
    3942      distances4[1, 3] = distances4[3, 1] = Math.Sqrt(2000000);
    4043      distances4[2, 3] = distances4[3, 2] = 1000;
    41       MultidimensionalScaling.MetricByDistance(distances4, out stress);
     44      stress = MultidimensionalScaling.CalculateNormalizedStress(distances4,
     45        MultidimensionalScaling.KruskalShepard(distances4));
    4246      Assert.IsTrue(stress < 0.1);
    4347      // Example 5: An arbitrary cloud of 8 points in a plane
    4448      DoubleMatrix distancesK = GetDistances(new double[,] { { 2, 1 }, { 5, 2 }, { 7, 1 }, { 4, 0 }, { 3, 3 }, { 4, 2 }, { 1, 8 }, { 6, 3 } });
    45       MultidimensionalScaling.MetricByDistance(distancesK, out stress);
     49      stress = MultidimensionalScaling.CalculateNormalizedStress(distancesK,
     50        MultidimensionalScaling.KruskalShepard(distancesK));
    4651      Assert.IsTrue(stress < 0.1);
    4752      // Example 6: A tetrahedron
    4853      distancesK = GetDistances(new double[,] { { 0, 0, 0 }, { 4, 0, 0 }, { 2, 3.4641, 0 }, { 2, 1.1547, 3.2660 } });
    49       MultidimensionalScaling.MetricByDistance(distancesK, out stress);
    50       Assert.IsTrue(stress < 0.2);
     54      stress = MultidimensionalScaling.CalculateNormalizedStress(distancesK,
     55        MultidimensionalScaling.KruskalShepard(distancesK));
     56      Assert.IsTrue(stress < 0.1);
    5157    }
    5258

  • branches/QAP/HeuristicLab.Problems.QuadraticAssignment.Views/3.3/QAPView.cs

    r5855 r5871  
    216216        Bitmap newBitmap = new Bitmap(pictureBox.Width, pictureBox.Height);
    217217
    218         for (int i = 0; i < distances.Rows; i++) {
    219           for (int j = i + 1; j < distances.Rows; j++)
    220             if (distances[i, j] != distances[j, i]) {
    221               WriteCenteredTextToBitmap(ref newBitmap, "Distance matrix is not symmetric");
    222               return newBitmap;
    223             }
    224         }
    225 
    226         double stress;
    227         DoubleMatrix coordinates = MultidimensionalScaling.MetricByDistance(distances, out stress);
    228         stressLabel.Text = stress.ToString("0.00", CultureInfo.CurrentCulture.NumberFormat);
     218        DoubleMatrix coordinates;
     219        double stress = double.NaN;
     220        try {
     221          coordinates = MultidimensionalScaling.KruskalShepard(distances);
     222          stress = MultidimensionalScaling.CalculateNormalizedStress(distances, coordinates);
     223          stressLabel.Text = stress.ToString("0.00", CultureInfo.CurrentCulture.NumberFormat);
     224        } catch {
     225          WriteCenteredTextToBitmap(ref newBitmap, "Distance matrix is not symmetric");
     226          stressLabel.Text = "-";
     227          return newBitmap;
     228        }
    229229        double xMin = double.MaxValue, yMin = double.MaxValue, xMax = double.MinValue, yMax = double.MinValue;
    230230        double maxDistance = double.MinValue;
    … …  
    302302            if (weights[i, j] > maxWeight)
    303303              maxWeight = weights[i, j] + weights[j, i];
    304 
    305             if (weights[i, j] != weights[j, i]) {
    306               WriteCenteredTextToBitmap(ref newBitmap, "Weights matrix is not symmetric");
    307               return newBitmap;
    308             }
    309304          }
    310305
    … …  
    315310          }
    316311
    317         double stress;
    318         DoubleMatrix coordinates = MultidimensionalScaling.MetricByDistance(distances, out stress);
    319         stressLabel.Text = stress.ToString("0.00", CultureInfo.CurrentCulture.NumberFormat);
     312        DoubleMatrix coordinates;
     313        double stress = double.NaN;
     314        try {
     315          coordinates = MultidimensionalScaling.KruskalShepard(distances);
     316          stress = MultidimensionalScaling.CalculateNormalizedStress(distances, coordinates);
     317          stressLabel.Text = stress.ToString("0.00", CultureInfo.CurrentCulture.NumberFormat);
     318        } catch {
     319          WriteCenteredTextToBitmap(ref newBitmap, "Weights matrix is not symmetric");
     320          stressLabel.Text = "-";
     321          return newBitmap;
     322        }
    320323        double xMin = double.MaxValue, yMin = double.MaxValue, xMax = double.MinValue, yMax = double.MinValue;
    321324        for (int i = 0; i < coordinates.Rows; i++) {
    … …  
    382385            if (distances[i, j] != distances[j, i]) {
    383386              WriteCenteredTextToBitmap(ref newBitmap, "Distance matrix is not symmetric");
     387              stressLabel.Text = "-";
    384388              return newBitmap;
    385389            }
    386390            if (weights[i, j] != weights[j, i]) {
    387391              WriteCenteredTextToBitmap(ref newBitmap, "Weights matrix is not symmetric");
     392              stressLabel.Text = "-";
     393              return newBitmap;
    388394            }
    389395          }
    390396        }
    391397
    392         double stress;
    393         DoubleMatrix coordinates = MultidimensionalScaling.MetricByDistance(distances, out stress);
    394         stressLabel.Text = stress.ToString("0.00", CultureInfo.CurrentCulture.NumberFormat);
     398        DoubleMatrix coordinates = null;
     399        double stress = double.NaN;
     400        try {
     401          coordinates = MultidimensionalScaling.KruskalShepard(distances);
     402          stress = MultidimensionalScaling.CalculateNormalizedStress(distances, coordinates);
     403          stressLabel.Text = stress.ToString("0.00", CultureInfo.CurrentCulture.NumberFormat);
     404        } catch {
     405          WriteCenteredTextToBitmap(ref newBitmap, "Unknown error");
     406          stressLabel.Text = "-";
     407          return newBitmap;
     408        }
     409
    395410        double xMin = double.MaxValue, yMin = double.MaxValue, xMax = double.MinValue, yMax = double.MinValue;
    396411        double maxWeight = double.MinValue;
Note: See TracChangeset for help on using the changeset viewer.