Pairwise data clustering by deterministic annealing
IEEE Transactions on Pattern Analysis and Machine IntelligencePublished 1 January 1997
Thomas Hofmann, Joachim M. Buhmann
Citations461
SJR quartileQ1
SJR score3.91
SNIP5.99
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 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.
Abstract
Partitioning a data set and extracting hidden structure from the data arises in different application areas of pattern recognition, speech and image processing. Pairwise data clustering is a combinatorial optimization method for data grouping which extracts hidden structure from proximity data. We describe a deterministic annealing approach to pairwise clustering which shares the robustness properties of maximum entropy inference. The resulting Gibbs probability distributions are estimated by mean-field approximation. A new structure-preserving algorithm to cluster dissimilarity data and to simultaneously embed these data in a Euclidian vector space is discussed which can be used for dimensionality reduction and data visualization. The suggested embedding algorithm which outperforms conventional approaches has been implemented to analyze dissimilarity data from protein analysis and from linguistics. The algorithm for pairwise data clustering is used to segment textured images.
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.
Elements of Information Theory
37,533 Citations2001Thomas M. Cover, Joy A. Thomas
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
Springer series in information sciencesSelf-Organization and Associative Memory
8,770 Citations1989Teuvo Kohonen
Vector Quantization and Signal Compression
7,039 Citations1992A. Gersho, Robert M. Gray
The author explains the design and implementation of the Levinson-Durbin Algorithm, which automates the very labor-intensive and therefore time-heavy and expensive process of designing and implementing a Quantizer.
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.
Digital Access to Scholarship at Harvard (DASH) (Harvard University)Maximum Likelihood from Incomplete Data via the EM Algorithm
4,523 Citations1977Dempster, Arthur P., Laird, Nan M. +1 more
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.
Journal of Optimization Theory and ApplicationsThermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
3,357 Citations1985V. Černý
It is conjecture that the analogy with thermodynamics can offer a new insight into optimization problems and can suggest efficient algorithms for solving them.
Journal of the Optical Society of America AUncertainty relation for resolution in space, spatial frequency, and orientation optimized by two-dimensional visual cortical filters
3,165 Citations1985John Daugman
Evidence is presented that the 2D receptive-field profiles of simple cells in mammalian visual cortex are well described by members of this optimal 2D filter family, and thus such visual neurons could be said to optimize the general uncertainty relations for joint 2D-spatial-2D-spectral information resolution.
Physics Today<i>Spin Glass Theory and Beyond</i>
2,668 Citations1988Marc Mézard, Giorgio Parisi +2 more
This book contains a detailed and self-contained presentation of the replica theory of infinite range spin glasses, paying particular attention to new applications in the study of optimization theory and neural networks.
Proceedings of the IEEEOn the rationale of maximum-entropy methods
1,648 Citations1982E. T. Jaynes
The relations between maximum-entropy (MAXENT) and other methods of spectral analysis such as the Schuster, Blackman-Tukey, maximum-likelihood, Bayesian, and Autoregressive models are discussed, emphasizing that they are not in conflict, but rather are appropriate in different problems.
The Annals of Probability$I$-Divergence Geometry of Probability Distributions and Minimization Problems
1,648 Citations1975Imre Csiszár
Philosophical magazineSolution of 'Solvable model of a spin glass'
1,253 Citations1977D. J. Thouless, Philip W. Anderson +1 more
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.
Journal of the American Statistical AssociationPrincipal Curves
893 Citations1989Trevor Hastie, Werner Stuetzle
IEEE Transactions on Information TheoryVisual Pattern Discrimination
864 Citations1962Béla Julesz
The condition for discrimination was found to be based primarily on clusters or lines formed by proximate points of uniform brightness, and a similar rule of connectivity with hue replacing brightness was obtained by using varicolored dots of equal subjective brightness.
Biological CyberneticsGabor filters as texture discriminator
737 Citations1989I. Fogel, Dov Sagi
The model was found to be in good correlation with known psychophysical characteristics as texton based texture segregation and micropattern density sensitivity, however, this simple model fails to predict human performance in discrimination tasks based on differences in the density of “terminators”.
Cambridge University Press eBooksStatistical Field Theory
590 Citations1989C. Itzykson, Jean-Michel Drouffe
IEEE Transactions on Acoustics Speech and Signal ProcessingEntropy-constrained vector quantization
584 Citations1989Philip A. Chou, T. Lookabaugh +1 more
An iterative descent algorithm based on a Lagrangian formulation for designing vector quantizers having minimum distortion subject to an entropy constraint is discussed and it is shown that for clustering problems involving classes with widely different priors, the ECVQ outperforms the k-means algorithm in both likelihood and probability of error.
IEEE Transactions on Pattern Analysis and Machine IntelligenceBoundary detection by constrained optimization
481 Citations1990Donald Geman, Stuart Geman +2 more
A statistical framework is used for finding boundaries and for partitioning scenes into homogeneous regions and incorporates a measure of disparity between certain spatial features of block pairs of pixel gray levels, using the Kolmogorov-Smirnov nonparametric measures of difference between the distributions of these features.
Physical Review LettersStatistical mechanics and phase transitions in clustering
463 Citations1990Kenneth Rose, E. Gurewitz +1 more
IEEE Transactions on Pattern Analysis and Machine IntelligenceParallel and deterministic algorithms from MRFs: surface reconstruction
449 Citations1991Davi Geiger, Federico Girosi
Deterministic approximations to Markov random field (MRF) models are derived and one of the models is shown to give in a natural way the graduated nonconvexity (GNC) algorithm proposed by A. Blake and A. Zisserman (1987).
Pattern Recognition LettersA deterministic annealing approach to clustering
384 Citations1990Kenneth Rose, E. Gurewitz +1 more
It is shown that as the temperature approaches zero, the algorithm becomes the basic ISODATA algorithm and the method is independent of the initial choice of cluster means.
IEEE Transactions on Information TheoryVector quantization by deterministic annealing
264 Citations1992Kenneth Rose, E. Gurewitz +1 more
A deterministic annealing approach is suggested to search for the optimal vector quantizer given a set of training data and the resulting codebook is independent of the codebook used to initialize the iterations.
Neural ComputationGeneralized Deformable Models, Statistical Physics, and Matching Problems
224 Citations1990Alan Yuille
Techniques from statistical physics are used to exploit the power of statistical techniques to put global constraints on the set of allowable states of the binary matching elements and be preferable to existing methods of imposing such constraints by adding bias terms in the energy functions.
IEEE Transactions on Pattern Analysis and Machine IntelligenceConstrained clustering as an optimization method
169 Citations1993Kenneth Rose, E. Gurewitz +1 more
The traveling salesman problem is reformulated as constrained clustering, yielding the elastic net (EN) approach to the problem, and the open path constraint formulation is shown to relate to dimensionality reduction by self-organization in unsupervised learning.
Network Computation in Neural SystemsStatistical mechanics as the underlying theory of ‘elastic’ and ‘neural’ optimisations
114 Citations1990Petar Simić
There is an interesting connection between two, recently popular, methods for finding good approximate solutions to hard optimisation problems, the ‘neural’ approach of Hopfield and Tank and the elastic-net method of Durbin and Willshaw.
Neural ComputationStatistical Physics, Mixtures of Distributions, and the EM Algorithm
100 Citations1994Alan Yuille, Paul Stolorz +1 more
There are strong relationships between approaches to optmization and learning based on statistical physics or mixtures of experts, and the EM algorithm can be interpreted as converging either to a local maximum of the mixtures model or to a saddle point solution to the statistical physics system.
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.
Surface Learning with Applications to Lipreading
88 Citations1993Christoph Bregler, Stephen M. Omohundro
This paper describes a simple but powerful architecture for learning and manipulating nonlinear surfaces from data and shows its utility in learning the space of lip images in a system for improving speech recognition by lip reading.
Physical review. A, General physicsAlternative approach to maximum-entropy inference
71 Citations1984Yoel Tikochinsky, Naftali Tishby +1 more
The present derivation provides an alternative approach to the inference problem which does not invoke Shannon's notion of missing information or entropy and is more limited in scope than the one proposed by Jaynes, but has the advantage that it is objective.
Neural ComputationComplexity Optimized Data Clustering by Competitive Neural Networks
69 Citations1993Joachim M. Buhmann, H. Kühnel
This work discusses a clustering strategy that explicitly reflects the tradeoff between simplicity and precision of a data representation, and establishes a unifying framework for different clustering methods like K-means clustering, fuzzy clusters, entropy constrained vector quantization, or topological feature maps and competitive neural networks.
Neural ComputationConstrained Nets for Graph Matching and Other Quadratic Assignment Problems
69 Citations1991Petar Simić
The main point of the elastic net algorithm is seen to be in the way one deals with the constraints when evaluating the effective cost function (free energy in the thermodynamic analogy), and not in its geometric foundation emphasized originally by Durbin and Willshaw.
Network Computation in Neural SystemsStatistical mechanics as the underlying theory of ‘elastic’ and ‘neural’ optimisations
64 Citations1990Petar Simić
Unsupervised segmentation of textured images by pairwise data clustering
28 Citations2002Thomas Hofmann, Jan Puzicha +1 more
A novel approach to unsupervised texture segmentation is presented which is formulated as a combinatorial optimization problem known as pairwise data clustering with a sparse neighborhood structure and the adequacy of the proposed segmentation cost function is statistically validated.
Inferring hierarchical clustering structures by deterministic annealing
7 Citations1996Thomas Hofmann, Joachim M. Buhmann
An objective function for tree evaluation and a deterministic annealing algorithm is derived in a meanfield approximation that allows us to canonically superimpose tree structures and to fit parameters to averaged or 'fuzzified' trees.