Multidimensional Scaling SIG
SERVICES
Very often scientific data are defined by multidimensional vectors of numerical values. To enable exploratory data analysis involving heuristic abilities of human experts visualization of data is highly desirable: a picture is worth a thousand words. There are different approaches to visualization. We consider one of the most popular approaches known as multidimensional scaling (see for example Borg I, Groenen P (2005) Modern Multidimensional Scaling. 2nd ed. Springer, New York). An essential part of the technique is optimization of a function possessing many optimization adverse properties. By means of this technique a set of multidimensional vectors can be represented as a set of points in a low-dimensional space, and exposed in this way to a human expert for heuristic analysis. Even more general sets of objects can be visualized: it is sufficient to know pairwise similarity/dissimilarity between the objects. Application areas of multidimensional scaling vary from psychometrics and market analysis to mobile communication, data mining, pharmacology and biomedicine.
A set of n objects is considered whose pairwise dissimilarities are given by an (nxn) matrix. It is supposed that dissimilarities are nonnegative and symmetric. An image of a set of objects is sought as a set of points in a low-dimensional metric embedding space with pairwise distances between the image points fitting the corresponding dissimilarities; normally Minkowski distances. The problem of construction of images of the considered objects is reduced to minimization of an accuracy of fit criterion, e.g. of a least squares Stress function. Stress is not everywhere differentiable. The function normally has many local minima. It is invariant with respect to translation, rotation and mirroring. The minimization problem of Stress is high dimensional. Therefore minimization of Stress function is a difficult global optimization problem.
APPLICATIONS
MDS - multidimensional scaling with city-block distances. The application implements a two-level method for multidimensional scaling with city-block distances (see A. Žilinskas, J. Žilinskas (2007) Two level minimization in multidimensional scaling. Journal of Global Optimization, ISSN 0925-5001, 38(4), 581-596). The method consists of combinatorial global search and local minimization employing piecewise quadratic structure of the objective function. Several algorithms for combinatorial search have been implemented:
- explicit enumeration of all feasible solutions,
- branch and bound,
- pure random search,
- multistart,
- evolutionary search.
In order to join this SIG contact the following person:
Julius Žilinskas, julius.zilinskas (at) mii.lt, phone: +370 5 2660396
Institute of Mathematics and Informatics
Lithuania
To subscribe to the mailing list of this SIG please send an empty e-mail with text "SUBSCRIBE" in a subject field to the address:
