PRTools contents

PRTools manual

mds

MDS

- Multidimensional Scaling - a variant of Sammon mapping

    [W,J,stress] = MDS(D,Y,OPTIONS)
    [W,J,stress] = MDS(D,N,OPTIONS)

Input
 D Square (M x M) dissimilarity matrix
 Y M x N matrix containing starting configuration, or
 N Desired output dimensionality
 OPTIONS Various parameters of the minimization procedure put into  a structure consisting of the following fields: 'q', 'optim',  'init','etol','maxiter', 'isratio', 'itmap', 'st' and 'inspect'  (default:  OPTIONS.q = 0 OPTIONS.optim = 'pn'  OPTIONS.init = 'cs'  OPTIONS.etol = 1e-6 (the precise value depends on q)  OPTIONS.maxiter = inf  OPTIONS.isratio = 0 OPTIONS.itmap = 'yes'  OPTIONS.st = 1 OPTIONS.inspect = 2).

Output
 W Multidimensional scaling mapping
 J Index of points removed before optimization  stress Vector of stress values

Description

Finds a nonlinear MDS map (a variant of the Sammon map) of objects  represented by a symmetric distance matrix D with zero diagonal, given  either the dimensionality N or the initial configuration Y. This is done  in an iterative manner by minimizing the Sammon stress

     e = 1/(sum_{i

where DY is the distance matrix of Y, which should approximate D. If D(i,j)  = 0 for any different points i and j, then one of them is superfluous. The  indices of these points are returned in J.

OPTIONS is an optional variable, using which the parameters for the mapping  can be controlled. It may contain the following fields

     Q        Stress measure to use (see above): -2,-1,0,1 or 2. 
     INIT     Initialisation method for Y: 'randp', 'randnp', 'maxv', 'cs' 
              or 'kl'. See MDS_INIT for an explanation.
     OPTIM    Minimization procedure to use: 'pn' for Pseudo-Newton or
              'scg' for Scaled Conjugate Gradients.
     ETOL     Tolerance of the minimization procedure. Usually, it should be 
     MAXITER  in the order of 1e-6. If MAXITER is given (see below), then the 
              optimization is stopped either when the error drops below ETOL or 
              MAXITER iterations are reached.
     ISRATIO  Indicates whether a ratio MDS should be performed (1) or not (0).
              If ISRATIO is 1, then instead of fitting the dissimilarities 
              D_{ij}, A*D_{ij} is fitted in the stress function. The value A 
              is estimated analytically in each iteration.
     ITMAP    Determines the way new points are mapped, either in an iterative 
              manner ('yes') by minimizing the stress; or by a linear projection 
              ('no').
     ST       Status, determines whether after each iteration the stress should 
     INSPECT  be printed on the screen (1) or not (0). When INSPECT > 0, 
              ST = 1 and the mapping is onto 2D or larger, then the progress 
              is plotted during the minimization every INSPECT iterations.

Important
1. It is assumed that D either is or approximates a Euclidean distance  matrix, i.e. D_{ij} = sqrt (sum_k(x_i - x_j)^2).  2. Missing values can be handled; they should be marked by 'NaN' in D.

EXAMPLES
opt.optim = 'scg';

opt.init = 'cs';
 D = sqrt(distm(a)); % Compute the Euclidean distance dataset of A
w1 = mds(D,2,opt); % An MDS map onto 2D initialized by Classical Scaling,  % optimized by a Scaled Conjugate Gradients algorithm
n = size(D,1);
y = rand(n,2);
w2 = mds(D,y,opt); % An MDS map onto 2D initialized by random vectors
z = rand(n,n); % Set around 40% of the random distances to NaN, i.e.
z = (z+z')/2; % not used in the MDS mapping
z = find(z <= 0.6);
D(z) = NaN;
D(1:n+1:n^2) = 0; % Set the diagonal to zero
opt.optim = 'pn';
opt.init = 'randnp';
opt.etol = 1e-8; % Should be high, as only some distances are used
w3 = mds(D,2,opt); % An MDS map onto 2D initialized by a random projection

 REFERENCES   1. M.F. Moler, A Scaled Conjugate Gradient Algorithm for Fast Supervised  Learning', Neural Networks, vol. 6, 525-533, 1993 2. W.H. Press, S.A. Teukolsky, W.T. Vetterling and B.P. Flannery,  Numerical Recipes in C, Cambridge University Press, Cambridge, 1992 3. I. Borg and P. Groenen, Modern Multidimensional Scaling, Springer  Verlag, Berlin, 1997 4. T.F. Cox and M.A.A. Cox, Multidimensional Scaling, Chapman and Hall,  London, 1994.

See also

mappings, mds_stress, mds_init, mds_cs,

PRTools contents

PRTools manual