A test for spatial homogeneity in cluster analysis

This paper proposes a measure of spatial homogeneity for sets of d-dimensional points based on nearest neighbor distances. Tests for spatial uniformity are examined which assess the tendency of the entire data set to aggregate and evaluate the character of individual clusters. The sizes and powers of three statistical tests of uniformity against aggregation, regularity, and unimodality are studied to determine robustness. The paper also studies the effects of normalization and incorrect prior information. A percentile frame sampling procedure is proposed that does not require a sampling window but is superior to a toroidal frame and to buffer zone sampling in particular situations. Examples test two data sets for homogeneity and search the results of a hierarchical clustering for homogeneous clusters.This work was partially supported by NSF Grant ECS-8300204.     

Weighting and selection of variables for cluster analysis

One of the thorniest aspects of cluster analysis continues to be the weighting and selection of variables. This paper reports on the performance of nine methods on eight leading case simulated and real sets of data. The results demonstrate shortcomings of weighting based on the standard deviation or range as well as other more complex schemes in the literature. Weighting schemes based upon carefully chosen estimates of within-cluster and between-cluster variability are generally more effective. These estimates do not require knowledge of the cluster structure. Additional research is essential: worry-free approaches do not yet exist.     

A validation study of a variable weighting algorithm for cluster analysis

De Soete (1986, 1988) proposed a variable weighting procedure when Euclidean distance is used as the dissimilarity measure with an ultrametric hierarchical clustering method. The algorithm produces weighted distances which approximate ultrametric distances as closely as possible in a least squares sense. The present simulation study examined the effectiveness of the De Soete procedure for an applications problem for which it was not originally intended. That is, to determine whether or not the algorithm can be used to reduce the influence of variables which are irrelevant to the clustering present in the data. The simulation study examined the ability of the procedure to recover a variety of known underlying cluster structures. The results indicate that the algorithm is effective in identifying extraneous variables which do not contribute information about the true cluster structure. Weights near 0.0 were typically assigned to such extraneous variables. Furthermore, the variable weighting procedure was not adversely effected by the presence of other forms of error in the data. In general, it is recommended that the variable weighting procedure be used for applied analyses when Euclidean distance is employed with ultrametric hierarchical clustering methods.     

The analysis of free-sorting data: Beyond pairwise cooccurrences

Free-sorting data are obtained when subjects are given a set of objects and are asked to divide them into subsets. Such data are usually reduced by counting for each pair of objects, how many subjects placed both of them into the same subset. The present study examines the utility of a group of additional statistics. the cooccurrences of sets of three objects. Because there are dependencies among the pair and triple cooccurrences, adjusted triple similarity statistics are developed. Multidimensional scaling and cluster analysis — which usually use pair similarities as their input data — can be modified to operate on three-way similarities to create representations of the set of objects. Such methods are applied to a set of empirical sorting data: Rosenberg and Kim's (1975) fifteen kinship terms.The author thanks Phipps Arabie, Lawrence Hubert, Lawrence Jones, Ed Shoben, and Stanley Wasserman for their considerable contributions to this paper.     

A latent class procedure for the structural analysis of two-way compositional data

This paper develops a new procedure for simultaneously performing multidimensional scaling and cluster analysis on two-way compositional data of proportions. The objective of the proposed procedure is to delineate patterns of variability in compositions across subjects by simultaneously clustering subjects into latent classes or groups and estimating a joint space of stimulus coordinates and class-specific vectors in a multidimensional space. We use a conditional mixture, maximum likelihood framework with an E-M algorithm for parameter estimation. The proposed procedure is illustrated using a compositional data set reflecting proportions of viewing time across television networks for an area sample of households.     

Buyer similarity measures in conjoint analysis: Some alternative proposals

In the commercial application of conjoint analysis, it is not unusual to compute pairwise similarity measures for buyers based on their commonality across part-worth utilities. The resulting similarity matrix may then be processed by various clustering techniques. This paper considers other ways to measure buyer similarity in conjoint analysis and compares the resulting measures to the traditional use of part-worth commonalities. An empirical example is used to illustrate the approaches and compare their results.The authors express their appreciation to Mr. Yong-Tai Tsai, of the University of Pennsylvania, who carried out the various computer computations reported in this paper.     

A sequential fitting procedure for linear data analysis models

A particular factor analysis model with parameter constraints is generalized to include classification problems definable within a framework of fitting linear models. The sequential fitting (SEFIT) approach of principal component analysis is extended to include several nonstandard data analysis and classification tasks. SEFIT methods attempt to explain the variability in the initial data (commonly defined by a sum of squares) through an additive decomposition attributable to the various terms in the model. New methods are developed for both traditional and fuzzy clustering that have useful theoretic and computational properties (principal cluster analysis, additive clustering, and so on). Connections to several known classification strategies are also stated.The author is grateful to P. Arabie and L. J. Hubert for editorial assistance and reviewing going well beyond traditional levels.     

On some significance tests in cluster analysis

We investigate the properties of several significance tests for distinguishing between the hypothesisH of a homogeneous population and an alternativeA involving clustering or heterogeneity, with emphasis on the case of multidimensional observationsx ₁, ...,x _n ^p . Four types of test statistics are considered: the (s-th) largest gap between observations, their mean distance (or similarity), the minimum within-cluster sum of squares resulting from a k-means algorithm, and the resulting maximum F statistic. The asymptotic distributions underH are given forn and the asymptotic power of the tests is derived for neighboring alternatives.     

On the classification of recall strings using lattice-theoretic measures

Lattice theory is used to develop techniques for classifying groups of subjects on the basis of their recall strategies or multiple recall strategies within individual subjects. Using the ordered tree algorithm to represent sets of recall orders, it is shown how both trees and single recall strings can be represented as points within a nonsemimodular, graded lattice. Distances within the lattice structure are used to construct a dissimilarity measure,S, which can then be used to partition the individual recall strings. The measureS between strings is compared to Kendall's tau in three empirical tests, examining differences between individual subjects, differences between groups of subjects, and differences within a subject. It was shown that onlyS could recover the original differences. Differences between comparing chunks versus comparing orders are discussed.The author would like to thank Henry Rueter, Judith Olson, John Jonides, and James Jaccard for many inspiring comments during several stages of this project, two anonymous reviewers for several important insights, and Malhee Lee for her assistance with data collection. This work was supported by NIMH Grant MH 39912. Portions of this work were presented at the annual meeting of the Classification Society in St. John's, Newfoundland, July 1985, and the annual meeting of the Society for Mathematical Psychology in Boston, MA, August 1986.     

Fitting a distance model to homogeneous subsets of variables: Points of view analysis of categorical data

An approach is presented for analyzing a heterogeneous set of categorical variables assumed to form a limited number of homogeneous subsets. The variables generate a particular set of proximities between the objects in the data matrix, and the objective of the analysis is to represent the objects in lowdimensional Euclidean spaces, where the distances approximate these proximities. A least squares loss function is minimized that involves three major components: a) the partitioning of the heterogeneous variables into homogeneous subsets; b) the optimal quantification of the categories of the variables, and c) the representation of the objects through multiple multidimensional scaling tasks performed simultaneously. An important aspect from an algorithmic point of view is in the use of majorization. The use of the procedure is demonstrated by a typical example of possible application, i.e., the analysis of categorical data obtained in a free-sort task. The results of points of view analysis are contrasted with a standard homogeneity analysis, and the stability is studied through a Jackknife analysis.     

An entropy criterion for assessing the number of clusters in a mixture model

In this paper, we consider an entropy criterion to estimate the number of clusters arising from a mixture model. This criterion is derived from a relation linking the likelihood and the classification likelihood of a mixture. Its performance is investigated through Monte Carlo experiments, and it shows favorable results compared to other classical criteria.

---

Résumé Nous proposons un critère d'entropie pour évaluer le nombre de classes d'une partition en nous fondant sur un modèle de mélange de lois de probabilité. Ce critère se déduit d'une relation liant la vraisemblance et la vraisemblance classifiante d'un mélange. Des simulations de Monte Carlo illustrent ses qualités par rapport à des critères plus classiques.

     

Measuring the influence of individual data points in a cluster analysis

The problem of measuring the impact of individual data points in a cluster analysis is examined. The purpose is to identify those data points that have an influence on the resulting cluster partitions. Influence of a single data point is considered present when different cluster partitions result from the removal of the element from the data set. The Hubert and Arabie (1985) corrected Rand index was used to provide numerical measures of influence of a data point. Simulated data sets consisting of a variety of cluster structures and error conditions were generated to validate the influence measures. The results showed that the measure of internal influence was 100% accurate in identifying those data elements exhibiting an influential effect. The nature of the influence, whether beneficial or detrimental to the clustering, can be evaluated with the use of the gamma and point-biserial statistics.     

Unclassed matrix shading and optimal ordering in hierarchical cluster analysis

A method is presented for the graphic display of proximity matrices as a complement to the common data analysis techniques of hierarchical clustering. The procedure involves the use of computer generated shaded matrices based on unclassed choropleth mapping in conjunction with a strategy for matrix reorganization. The latter incorporates a combination of techniques for seriation and the ordering of binary trees.Partial support for this research was provided by NIJ Grant #82-IJ-CX-0019 and NSF Grant #SES82-06067. The authors wish to acknowledge the assistance of Professors L.J. Hubert, R.G. Golledge, and W.R. Tobler.     

A maximum likelihood methodology for clusterwise linear regression

This paper presents a conditional mixture, maximum likelihood methodology for performing clusterwise linear regression. This new methodology simultaneously estimates separate regression functions and membership inK clusters or groups. A review of related procedures is discussed with an associated critique. The conditional mixture, maximum likelihood methodology is introduced together with the E-M algorithm utilized for parameter estimation. A Monte Carlo analysis is performed via a fractional factorial design to examine the performance of the procedure. Next, a marketing application is presented concerning the evaluations of trade show performance by senior marketing executives. Finally, other potential applications and directions for future research are identified.     

Statistical tests on two characteristics of the shapes of cluster diagrams

A cluster diagram is a rooted planar tree that depicts the hierarchical agglomeration of objects into groups of increasing size. On the null hypothesis that at each stage of the clustering procedure all possible joins are equally probable, we derive the probability distributions for two properties of these diagrams: (1)S, the number of single objects previously ungrouped that are joined in the final stages of clustering, and (2)m _k, the number of groups ofk+1 objects that are formed during the process. Ecological applications of statistical tests for these properties are described and illustrated with data from weed communities of Saskatchewan fields.This work was supported by the Natural Sciences and Engineering Research Council of Canada.     

Variable selection in clustering

Standard clustering algorithms can completely fail to identify clear cluster structure if that structure is confined to a subset of the variables. A forward selection procedure for identifying the subset is proposed and studied in the context of complete linkage hierarchical clustering. The basic approach can be applied to other clustering methods, too.     

Clustering the rows and columns of a contingency table

A number of ways of investigating heterogeneity in a two-way contingency table are reviewed. In particular, we consider chi-square decompositions of the Pearson chi-square statistic with respect to the nodes of a hierarchical clustering of the rows and/or the columns of the table. A cut-off point which indicates significant clustering may be defined on the binary trees associated with the respective row and column cluster analyses. This approach provides a simple graphical procedure which is useful in interpreting a significant chi-square statistic of a contingency table.The author gratefully acknowledges the constructive comments of the referees and the editor.     

An alternating combinatorial optimization approach to fitting the INDCLUS and generalized INDCLUS models

This paper presents a general approach for fitting the ADCLUS (Shepard and Arabie 1979; Arabie, Carroll, DeSarbo, and Wind 1981), INDCLUS (Carroll and Arabie 1983), and potentially a special case of the GENNCLUS (DeSarbo 1982) models. The proposed approach, based largely on a separability property observed for the least squares loss function being optimized, offers increased efficiency and other advantages over existing approaches like MAPCLUS (Arabie and Carroll 1980) for fitting the ADCLUS model, and the INDCLUS method for fitting the INDCLUS model. The new procedure (called SINDCLUS) is applied to three sets of empirical data to demonstrate the effectiveness of the SINDCLUS methodology. Finally, some potentially useful extensions are discussed.