Data visualization by multidimensional scaling: a deterministic annealing approach
Pattern RecognitionPublished 1 April 2000
Hansjörg Klock, Joachim M. Buhmann
Citations56
SJR quartileQ1
SJR score2.06
SNIP2.67
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A novel deterministic annealing algorithm is presented for SSTRESS and Sammon mapping, derived in the framework of maximum entropy estimation, and the superiority of this optimization technique compared to conventional gradient descent methods is demonstrated.
Abstract
Multidimensional scaling addresses the problem how proximity data can be faithfully visualized as points in a low-dimensional Euclidean space. The quality of a data embedding is measured by a stress function which compares proximity values with Euclidean distances of the respective points. The corresponding minimization problem is non-convex and sensitive to local minima. We present a novel deterministic annealing algorithm for the frequently used objective SSTRESS and for Sammon mapping, derived in the framework of maximum entropy estimation. Experimental results demonstrate the superiority of our optimization technique compared to conventional gradient descent methods.
Keywords
Computer Science
Journal of the Royal Statistical Society Series B (Statistical Methodology)Maximum Likelihood from Incomplete Data Via the <i>EM</i> Algorithm
49,657 Citations1977A. P. Dempster, N. M. Laird +1 more
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
IEEE Transactions on Pattern Analysis and Machine IntelligenceStochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
17,980 Citations1984Stuart Geman, Donald Geman
The analogy between images and statistical mechanics systems is made and the analogous operation under the posterior distribution yields the maximum a posteriori (MAP) estimate of the image given the degraded observations, creating a highly parallel ``relaxation'' algorithm for MAP estimation.
Annals of EugenicsTHE USE OF MULTIPLE MEASUREMENTS IN TAXONOMIC PROBLEMS
14,727 Citations1936Ronald Aylmer Fisher
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
PsychometrikaMultidimensional Scaling by Optimizing Goodness of Fit to a Nonmetric Hypothesis
7,398 Citations1964Joseph B. Kruskal
The fundamental hypothesis is that dissimilarities and distances are monotonically related, and a quantitative, intuitively satisfying measure of goodness of fit is defined to this hypothesis.
Cambridge University Press eBooksPattern Recognition and Neural Networks
6,468 Citations1996B. D. Ripley
PsychometrikaNonmetric Multidimensional Scaling: A Numerical Method
4,882 Citations1964Joseph B. Kruskal
The numerical methods required in the approach to multi-dimensional scaling are described and the rationale of this approach has appeared previously.
IEEE Transactions on ComputersA Nonlinear Mapping for Data Structure Analysis
3,381 Citations1969John W. Sammon
An algorithm for the analysis of multivariate data is presented along with some experimental results that is based upon a point mapping of N L-dimensional vectors from the L-space to a lower-dimensional space such that the inherent data "structure" is approximately preserved.
PsychometrikaThe Analysis of Proximities: Multidimensional Scaling with an Unknown Distance Function. I.
2,553 Citations1962Roger N. Shepard
The program is proposed as a tool for reductively analyzing several types of psychological data, particularly measures of interstimulus similarity or confusability, by making explicit the multidimensional structure underlying such data.
A View of the Em Algorithm that Justifies Incremental, Sparse, and other Variants
2,187 Citations1998Radford M. Neal, Geoffrey E. Hinton
An incremental variant of the EM algorithm in which the distribution for only one of the unobserved variables is recalculated in each E step is shown empirically to give faster convergence in a mixture estimation problem.
IEEE Transactions on ComputersDistortion invariant object recognition in the dynamic link architecture
1,810 Citations1993Martin Lades, Jan C. Vorbrüggen +5 more
An object recognition system based on the dynamic link architecture, an extension to classical artificial neural networks (ANNs), is presented and the implementation on a transputer network achieved recognition of human faces and office objects from gray-level camera images.
IEEE Transactions on Pattern Analysis and Machine IntelligenceA graduated assignment algorithm for graph matching
1,098 Citations1996Steven Gold, Anand Rangarajan
A graduated assignment algorithm for graph matching is presented which is fast and accurate even in the presence of high noise, and not restricted to any special class of graph, is applied to subgraph isomorphism, weighted graph matching, and attributed relational graph matching.
PsychometrikaNonmetric Individual Differences Multidimensional Scaling: An Alternating Least Squares Method with Optimal Scaling Features
960 Citations1977Yoshio Takane, Forrest W. Young +1 more
IEEE Transactions on Neural NetworksArtificial neural networks for feature extraction and multivariate data projection
659 Citations1995Jianchang Mao, Anil K. Jain
The SAMANN network offers the generalization ability of projecting new data, which is not present in the original Sammon's projection algorithm; the NDA method and NP-SOM network provide new powerful approaches for visualizing high dimensional data.
Physical Review LettersStatistical mechanics and phase transitions in clustering
463 Citations1990Kenneth Rose, E. Gurewitz +1 more
IEEE Transactions on Pattern Analysis and Machine IntelligencePairwise data clustering by deterministic annealing
461 Citations1997Thomas Hofmann, Joachim M. Buhmann
A deterministic annealing approach to pairwise clustering is described which shares the robustness properties of maximum entropy inference and the resulting Gibbs probability distributions are estimated by mean-field approximation.
Journal of the American Statistical AssociationRepresentation of Similarity Matrices by Trees
223 Citations1967John Hartigan
The construction technique is applied to voting behaviour of the 50 United States in the last 13 presidential elections, giving a tree clustering of the states.
Journal of ClassificationConvergence of the majorization method for multidimensional scaling
195 Citations1988Jan de Leeuw
It turns out that in almost all cases convergence is linear, with a convergence rate close to unity, which has the practical consequence that convergence will usually be very slow, and this makes techniques to speed up convergence very important.
Pattern RecognitionExperiments in projection and clustering by simulated annealing
178 Citations1989Raymond W. Klein, Richard C. Dubes
The simulated annealing algorithm when applied to the minimization of functions from two common problems encountered in exploratory pattern analysis, projection and clustering yields a better optimization and better retained structure for large data sets containing tight gaussian clusters.
A new view of the EM algorithm that justifies incremental and other variants
165 Citations1993Radford M. Neal
IEEE Transactions on Information TheoryVector quantization with complexity costs
98 Citations1993Joachim M. Buhmann, H. Kühnel
The approach establishes a unifying framework for different quantization methods like K-means clustering and its fuzzy version, entropy constrained vector quantization or topological feature maps, and competitive neural networks.
Pattern RecognitionMultidimensional scaling by iterative majorization using radial basis functions
72 Citations1995Andrew R. Webb
This paper considers the use of radial basis functions for modelling the non-linear transformation of a data set obtained by a multidimensional scaling analysis and a scheme based on iterative majorization is proposed for obtaining the parameters of the network.
Journal of ClassificationThe majorization approach to multidimensional scaling for Minkowski distances
65 Citations1995Patrick J. F. Groenen, Rudolf Mathar +1 more
Neural NetworksAlgebraic transformations of objective functions
60 Citations1990Eric Mjolsness, Charles Garrett
This work exhibits a collection of algebraic transformations which reduce network cost and increase the set of objective functions that are neurally implementable, and applies them to simplify a number of structured neural networks.
IEEE Transactions on Neural NetworksA Lagrangian relaxation network for graph matching
50 Citations1996Anand Rangarajan, Eric Mjolsness
Lecture notes in computer scienceMultidimensional scaling by deterministic annealing
34 Citations1997Hansjörg Klock, Joachim M. Buhmann
A novel deterministic annealing algorithm is presented to efficiently determine embedding coordinates for this continuous optimization problem and a transformation of dissimilarities is proposed to reduce the mismatch between a high-dimensional data space and a low-dimensional embedding space.
Aston Publications Explorer (Aston University)Topographic mappings and feed-forward neural networks
29 Citations1996Michael E. Tipping
It is shown that neural network models can be less sensitive to entrapment in the sub-optimal global minima that badly affect the standard Sammon algorithm, and tend to exhibit good generalisation as a result of implicit weight decay in the training process.
IEEE Transactions on ComputersA Fast-Converging Algorithm for Nonlinear Mapping of High-Dimensional Data to a Plane
28 Citations1979Niemann, Weiss
An iterative algorithm for nonlinear mapping of high-dimensional data is developed and the step size of the descent algorithm is chosen to assure convergence.
PsychometrikaA Generalized Majorization Method for Least Squares Multidimensional Scaling of Pseudodistances that may be Negative
27 Citations1991Willem J. Heiser
A generalization of the SMACOF method is proposed to resolve the difficulty that is based on the same rationale frequently involved in robust fitting with least absolute residuals.
Journal of Global OptimizationA class of test functions for global optimization
23 Citations1994Rudolf Mathar, Antanas Žilinskas
It is suggested that weighted least squares scaling, a basic method in multidimensional scaling, as a class of test functions for global optimization, are easy to code, cheap to calculate, and have important applications in data analysis.
Neural ComputationConvex Potentials and their Conjugates in Analog Mean-Field Optimization
11 Citations1995Ibrahim M. Elfadel
The saddle-point paradigm of mean-field methods in statistical physics provides a systematic procedure for finding a mapping of constrained optimization problems onto analog networks via the notion of effective energy, and it is shown that within this paradigm, to each closed bounded constraint set is associated a smooth convex potential function.
Neural Information Processing SystemsCentral and Pairwise Data Clustering by Competitive Neural Networks
9 Citations1993Joachim M. Buhmann, Thomas Hofmann
A selfconsistent solution to multidimensional scaling and pairwise clustering is derived which yields an optimal embedding and clustering of data points in a d-dimensional Euclidian space.