PRTools Contents

PRTools User Guide

mds

MDS

Trainable mapping for multidimensional scaling, a variant of Sammon mapping

    [W,J,STRESS] = MDS(DT,Y,OPTIONS)
    [W,J,STRESS] = MDS(DT,K,OPTIONS)
    [W,J,STRESS] = DT*MDS([],K,OPTIONS)
    [W,J,STRESS] = DT*MDS(K,OPTIONS)
               X = DS*W

Input
 DT Square (M x M) dissimilarity matrix used for training
 DS N x M dissimilarity matrix between testset and trainset
 Y M x K matrix containing starting target configuration, or
 K Desired output dimensionality (default 2)
 OPTIONS Various parameters of the minimisation 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 = 100 
                OPTIONS.isratio = 0 
                OPTIONS.itmap   = 'yes' 
                OPTIONS.st      = 1 
                OPTIONS.inspect = 2).

Output
 W Multidimensional scaling mapping
 J Index of points removed before optimisation
 STRESS Vector of stress values
 X N x K dataset with output configuration

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 K or the initial configuration Y. This is done  in an iterative manner by minimizing the Sammon stress between the given  dissimilarities D (DT or DS) and the distances DY in the K-dimensional  target space

     E = 1/(sum_{i<j} D_{ij}^(Q+2)) sum_{i<j} (D_{ij} - DY_{ij})^2 * D_{ij}^Q

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.

There is a simplified interface to MDS, called SAMMONM. The main  differences are that SAMMONM operates on feature based datasets, while MDS expects dissimilarity matrices; MDS maps new objects by a second  optimisation procedures minimizing the stress for the test objects, while  SAMMONM uses a linear mapping between dissimilarities and the target  space. See also PREX_MDS for examples.

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    Minimisation procedure to use: 'pn' for Pseudo-Newton or
              'scg' for Scaled Conjugate Gradients.
     ETOL     Tolerance of the minimisation procedure. Usually, it should be 
     MAXITER  in the order of 1e-6. If MAXITER is given (see below), then the 
              optimisation 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 %gt 0, 
              ST = 1 and the mapping is onto 2D or larger, then the progress 
              is plotted during the minimisation every INSPECT iterations.

Important

  • 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).
  • 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,  % optimised 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

Reference(s)

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

datasets, mappings, prex_mds, mds_cs, sammonm, tsnem,

PRTools Contents

PRTools User Guide

This file has been automatically generated. If badly readable, use the help-command in Matlab.