NP-hard Approximation Problems in Overlapping Clustering

L_p -norm (p < ∞). These problems also correspond to the approximation by a strongly Robinson dissimilarity or by a dissimilarity fulfilling the four-point inequality (Bandelt 1992; Diatta and Fichet 1994). The results are extended to circular strongly Robinson dissimilarities, indexed k-hierarchies (Jardine and Sibson 1971, pp. 65-71), and to proper dissimilarities satisfying the Bertrand and Janowitz (k + 2)-point inequality (Bertrand and Janowitz 1999). Unidimensional scaling (linear or circular) is reinterpreted as a clustering problem and its hardness is established, but only for the L ₁ norm.     

Unidimensional scaling: A linear programming approach minimizing absolute deviations

A Mixed Integer Programming formulation can be developed for the classical unidimensional scaling problem when the measure of goodness-of-fit is thel ₁ norm of the discrepancies rather than the sum of the squares of the discrepancies.The author wishes to thank the editor and the three anonymous referees for their helpful and constructive comments.     

A New Formulation of the Nonmetric Strain Problem in Multidimensional Scaling

A natural extension of classical metric multidimensional scaling is proposed. The result is a new formulation of nonmetric multidimensional scaling in which the strain criterion is minimized subject to order constraints on the disparity variables. Innovative features of the new formulation include: the parametrization of the p-dimensional distance matrices by the positive semidefinite matrices of rank ≤p; optimization of the (squared) disparity variables, rather than the configuration coordinate variables; and a new nondegeneracy constraint, which restricts the set of (squared) disparities rather than the set of distances. Solutions are obtained using an easily implemented gradient projection method for numerical optimization. The method is applied to two published data sets.     

Distance Models for Three-Way Tables and Three-Way Association

p similarity function, the L _p -transform and the Minkowski-p distance. For triadic distance models defined by the L _p -transform we will prove that they do not model three-way association. Moreover, triadic distance models defined by the L _p -transform are restricted multiple dyadic distances, where each dyadic distance is defined for a two-way margin of the three-way table. Distance models for three-way two-mode data, called three-way distance models, do succeed in modeling three-way association.     

Classification Based on Depth Transvariations

Suppose y, a d-dimensional (d ≥ 1) vector, is drawn from a mixture of k (k ≥ 2) populations, given by ∏₁, ∏₂,…,∏ _k . We wish to identify the population that is the most likely source of the point y. To solve this classification problem many classification rules have been proposed in the literature. In this study, a new nonparametric classifier based on the transvariation probabilities of data depth is proposed. We compare the performance of the newly proposed nonparametric classifier with classical and maximum depth classifiers using some benchmark and simulated data sets. The authors thank the editor and referees for comments that led to an improvement of this paper. This work is partially supported by the National Science Foundation under Grant No. DMS-0604726. Published online xx, xx, xxxx.     

Integer Programming Methods for Seriation and Unidemensional Scaling of Proximity Matrices: A Review and Some Extensions

L ₁-norm are also presented. I conclude that the computational scaling problems depends largely on the criterion of interest, with unidimensional scaling problems depends largely on the criterion of interest, with unidimensional scaling in the L ₁-norm being especially challenging.     

One-Mode Classification of a Three-Way Data Matrix

X is the automatic hierarchical classification of one mode (units or variables or occasions) of X on the basis of the other two. In this paper the case of OMC of units according to variables and occasions is discussed. OMC is the synthesis of a set of hierarchical classifications Delta obtained from X; e.g., the OMC of units is the consensus (synthesis) among the set of dendograms individually defined by clustering units on the basis of variables, separately for each given occasion of X. However, because Delta is often formed by a large number of classifications, it may be unrealistic that a single synthesis is representative of the entire set. In this case, subsets of similar (homegeneous) dendograms may be found in Delta so that a consensus representative of each subset may be identified. This paper proposes, PARtition and Least Squares Consensus cLassifications Analysis (PARLSCLA) of a set of r hierarchical classifications Delta. PARLSCLA identifies the best least-squares partition of Delta into m (1 <= m <= r) subsets of homogeneous dendograms and simultaneously detects the closest consensus classification (a median classification called Least Squares Consensus Dendogram (LSCD) for each subset. PARLSCLA is a generalization of the problem to find a least-squares consensus dendogram for Delta. PARLSCLA is formalized as a mixed-integer programming problem and solved with an iterative, two-step algorithm. The method proposed is applied to an empirical data set.     

Constructing Ultrametric and Additive Trees Based on the L 1 Norm

L ₁) criterion. Examples of ultrametric and additive trees fitted to two extant data sets are given, plus a Monte Carlo analysis to assess the impact of both typical data error and extreme values on fitted trees. Solutions are compared to the least-squares (L ₂) approach of Hubert and Arabie (1995a), with results indicating that (with these data) the L ₁ and L ₂ optimization strategies perform very similarly. A number of observations are made concerning possible uses of an L ₁ approach, the nature and number of identified locally optimal solutions, and metric recovery differences between ultrametrics and additive trees.     

Linear Unidimensional Scaling in the L 2 -Norm: Basic Optimization Methods Using MATLAB

L₂ -norm: (1) dynamic programming; (2) an iterative quadratic assignment improvement heuristic; (3) the Guttman update strategy as modified by Pliner's technique of smoothing; (4) a nonlinear programming reformulation by Lau, Leung, and Tse. The methods are all implemented through (freely downloadable) MATLAB m-files; their use is illustrated by a common data set carried throughout. For the computationally intensive dynamic programming formulation that can a globally optimal solution, several possible computational improvements are discussed and evaluated using (a) a transformation of a given m-function with the MATLAB Compiler into C code and compiling the latter; (b) rewriting an m-function and a mandatory MATLAB gateway directly in Fortran and compiling into a MATLAB callable file; (c) comparisons of the acceleration of raw m-files implemented under the most recent release of MATLAB Version 6.5 (and compared to the absence of such acceleration under the previous MATLAB Version 6.1). Finally, and in contrast to the combinatorial optimization task of identifying a best unidimensional scaling for a given proximity matrix, an approach is given for the confirmatory fitting of a given unidimensional scaling based only on a fixed object ordering, and to nonmetric unidensional scaling that incorporates an additional optimal monotonic transformation of the proximities.     

Data Model and Classification by Trees: The Minimum Variance Reduction (MVR) Method

O (n ⁴), where n is the number of objects. We describe the application of the MVR method to two data models: the weighted least-squares (WLS) model (V is diagonal), where the MVR method can be reduced to an O(n ³) time complexity; a model arising from the study of biological sequences, which involves a complex non-diagonal V matrix that is estimated from the dissimilarity matrix Δ. For both models, we provide simulation results that show a significant error reduction in the reconstruction of T, relative to classical agglomerative algorithms.     

The Metric Bridge Partition Problem: Partitioning of a Metric Space into Two Subspaces Linked by an Edge in Any Optimal Realization

Let G = (V,E,w) be a graph with vertex and edge sets V and E, respectively, and w:E → R ⁺ a function which assigns a positive weight or length to each edge of G. G is called a realization of a finite metric space (M,d), with M = { 1,...,n} if and only if { 1,...,n} ⫅ V and d(i,j) is equal to the length of the shortest chain linking i and j in G ∀ i,j = 1,...,n. A realization G of (M,d), is said optimal if the sum of its weights is minimal among all the realizations of (M,d). Consider a partition of M into two nonempty subsets K and L, and let e be an edge in a realization G of (M,d); we say that e is a bridge linking K with L if e belongs to all chains in G linking a vertex of K with a vertex of L. The Metric Bridge Partition Problem is to determine if the elements of a finite metric space (M,d) can be partitioned into two nonempty subsets K and L such that all optimal realizations of (M,d) contain a bridge linking K with L. We prove in this paper that this problem is polynomially solvable. We also describe an algorithm that constructs an optimal realization of (M,d) from optimal realizations of (K,d|_K) and (L,d|_L).     

On the Performance of Simulated Annealing for Large-Scale L2 Unidimensional Scaling

In this research note, I present a modified version of G. De Soete, L. Hubert, and P. Arabie’s (1988) simulated annealing approach for the problem of L₂ unidimensional scaling via maximization of the Defays criterion. The modifications include efficient storage and computation methods that facilitate rapid evaluation of trial solutions. The results of two experimental studies indicate that the enhanced simulated annealing algorithm is competitive with A. Murillo, J.F. Vera, and W.J. Heiser’s (2005) recently published pertsaus2 procedure in terms of solution quality and computation time. Both Fortran and MatLab versions of this modified simulated annealing implementation are available from the author.     

L 1 Optimization under Linear Inequality Constraints

1 optimization under linear inequality constraints based upon iteratively reweighted iterative projection (or IRIP). IRIP is compared to a linear programming (LP) strategy for L₁ minimization (Sp?th 1987, Chapter 5.3) using the ultrametric condition as an exemlar class of constraints to be fitted. Coded for general constraints, the LP approach proves to be faster. Both methods, however, suffer from a serious limitation in being unable to process reasonably-sized data sets because of storage requirements for the constraints. When the simplicity of vector projections is used to allow IRIP to be coded for specific (in this case, ultrametric) constraints, we obtain a fast and efficient algorithm capable of handling large data sets. It is also possible to extend IRIP to operate as a heuristic search strategy that simultaneously identifies both a reasonable set of constraints to impose and the optimally-estimated parameters satisfying these constraints. A few noteworthy characteristics of L₁ optimal ultrametrics are discussed, including other strategies for reformulating the ultrametric optimization problem.     

Minimum Sum of Squares Clustering in a Low Dimensional Space

Clustering with a criterion which minimizes the sum of squared distances to cluster centroids is usually done in a heuristic way. An exact polynomial algorithm, with a complexity in O(N ^p+1 logN), is proposed for minimum sum of squares hierarchical divisive clustering of points in a p-dimensional space with small p. Empirical complexity is one order of magnitude lower. Data sets with N = 20000 for p = 2, N = 1000 for p = 3, and N = 200 for p = 4 are clustered in a reasonable computing time.     

Seriation in the Presence of Errors: NP-Hardness of <Emphasis Type="Italic">l</Emphasis><Subscript><Emphasis Type="Italic">∞</Emphasis></Subscript> -Fitting Robinson Structures to Dissimilarity Matrices

In this paper, we establish that the following fitting problem is NP-hard: given a finite set X and a dissimilarity measure d on X (d is a symmetric function from X ² to the nonnegative real numbers and vanishing on the diagonal), we wish to find a Robinsonian dissimilarity d _R on X minimizing the l _∞ -error ||d − d _R || _∞ = max_x,y ∈X{|d(x, y) − d _R (x, y)|} between d and d _R . Recall that a dissimilarity d _R on X is called monotone (or Robinsonian) if there exists a total order ≺ on X such that x ≺ z ≺ y implies that d(x, y) ≥ max{d(x, z), d(z, y)}. The Robinsonian dissimilarities appear in seriation and clustering problems, in sparse matrix ordering and DNA sequencing.     

Radial basis functions for exploratory data analysis: An iterative majorisation approach for Minkowski distances based on multidimensional scaling

This paper considers the use of radial basis functions for exploratory data analysis. These are used to model a transformation from a high-dimensional observation space to a low-dimensional one. The parameters of the model are determined by optimising a loss function defined to be the stress function in multidimensional scaling. The metric for the low-dimensional space is taken to be the Minkowski metric with order parameter 1<-p<-2. A scheme based on iterative majorisation is proposed.     

A Binary Integer Program to Maximize the Agreement Between Partitions

This research note focuses on a problem where the cluster sizes for two partitions of the same object set are assumed known; however, the actual assignments of objects to clusters are unknown for one or both partitions. The objective is to find a contingency table that produces maximum possible agreement between the two partitions, subject to constraints that the row and column marginal frequencies for the table correspond exactly to the cluster sizes for the partitions. This problem was described by H. Messatfa (Journal of Classification, 1992, pp. 5–15), who provided a heuristic procedure based on the linear transportation problem. We present an exact solution procedure using binary integer programming. We demonstrate that our proposed method efficiently obtains optimal solutions for problems of practical size. We would like to thank the Editor, Willem Heiser, and an anonymous reviewer for helpful comments that resulted in improvements of this article.     

An Unsupervised and Nonparametric Classification Procedure Based on Mixtures with Known Weights

I consider a new problem of classification into n(n ≥ 2) disjoint classes based on features of unclassified data. It is assumed that the data are grouped into m(M ≥ n) disjoint sets and within each set the distribution of features is a mixture of distributions corresponding to particular classes. Moreover, the mixing proportions should be known and form a matrix of rank n. The idea of solution is, first, to estimate feature densities in all the groups, then to solve the linear system for component densities. The proposed classification method is asymptotically optimal, provided a consistent method of density estimation is used. For illustration, the method is applied to determining perfusion status in myocardial infarction patients, using creatine kinase measurements.     

The Metric Cutpoint Partition Problem

Let G = (V, E,w) be a graph with vertex and edge sets V and E, respectively, and w: E → a function which assigns a positive weight or length to each edge of G. G is called a realization of a finite metric space (M, d), with M = {1, ..., n} if and only if {1, ..., n} ⊆ V and d(i, j) is equal to the length of the shortest chain linking i and j in G ∀i, j = 1, ..., n. A realization G of (M, d), is called optimal if the sum of its weights is minimal among all the realizations of (M, d). A cutpoint in a graph G is a vertex whose removal strictly increases the number of connected components of G. The Metric Cutpoint Partition Problem is to determine if a finite metric space (M, d) has an optimal realization containing a cutpoint. We prove in this paper that this problem is polynomially solvable. We also describe an algorithm that constructs an optimal realization of (M, d) from optimal realizations of subspaces that do not contain any cutpoint. Supported by grant PA002-104974/2 from the Swiss National Science Foundation. Published online xx, xx, xxxx.     

K-modes Clustering

0 norm (defined as the limit of an L_p norm as p approaches zero). In Monte Carlo simulations, both K-modes and the latent class procedures (e.g., Goodman 1974) performed with equal efficiency in recovering a known underlying cluster structure. However, K-modes is an order of magnitude faster than the latent class procedure in speed and suffers from fewer problems of local optima than do the latent class procedures. For data sets involving a large number of categorical variables, latent class procedures become computationally extremly slow and hence infeasible. We conjecture that, although in some cases latent class procedures might perform better than K-modes, it could out-perform latent class procedures in other cases. Hence, we recommend that these two approaches be used as "complementary" procedures in performing cluster analysis. We also present an empirical comparison of K-modes and latent class, where the former method prevails.