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.