Lowdimensional Additive Overlapping Clustering

To reveal the structure underlying two-way two-mode object by variable data, Mirkin (1987) has proposed an additive overlapping clustering model. This model implies an overlapping clustering of the objects and a reconstruction of the data, with the reconstructed variable profile of an object being a summation of the variable profiles of the clusters it belongs to. Grasping the additive (overlapping) clustering structure of object by variable data may, however, be seriously hampered in case the data include a very large number of variables. To deal with this problem, we propose a new model that simultaneously clusters the objects in overlapping clusters and reduces the variable space; as such, the model implies that the cluster profiles and, hence, the reconstructed data profiles are constrained to lie in a lowdimensional space. An alternating least squares (ALS) algorithm to fit the new model to a given data set will be presented, along with a simulation study and an illustrative example that makes use of empirical data.     

CLUSCALE ("CLUstering and multidimensional SCAL[E]ing"): A Three-Way Hybrid Model Incorporating Overlapping Clustering and Multidimensional Scaling Structure

Traditional techniques of perceptual mapping hypothesize that stimuli are differentiated in a common perceptual space of quantitative attributes. This paper enhances traditional perceptual mapping techniques such as multidimensional scaling (MDS) which assume only continuously valued dimensions by presenting a model and methodology called CLUSCALE for capturing stimulus differentiation due to perceptions that are qualitative, in addition to quantitative or continuously varying perceptual attributes or dimensions. It provides models and OLS parameter estimation procedures for both a two-way and a three-way version of this general model. Since the two-way version of the model and method has already been discussed by Chaturvedi and Carroll (2000), and a stochastic variant discussed by Navarro and Lee (2003), we shall deal in this paper almost entirely with the three-way version of this model. We recommend the use of the three-way approach over the two-way approach, since the three-way approach both accounts for and takes advantage of the heterogeneity in subjects’ perceptions of stimuli to provide maximal information; i.e., it explicitly deals with individual differences among subjects.     

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.     

Model-Based Clustering

The notion of defining a cluster as a component in a mixture model was put forth by Tiedeman in 1955; since then, the use of mixture models for clustering has grown into an important subfield of classification. Considering the volume of work within this field over the past decade, which seems equal to all of that which went before, a review of work to date is timely. First, the definition of a cluster is discussed and some historical context for model-based clustering is provided. Then, starting with Gaussian mixtures, the evolution of model-based clustering is traced, from the famous paper by Wolfe in 1965 to work that is currently available only in preprint form. This review ends with a look ahead to the next decade or so.     

地理学同相邻学科部分交叉名词的协调

全国自然科学名词审定委员会名词术语审定的原则及方法第2.3.2则要求：“不易分清主、副科关系的一部分交叉词,几个学科要互相协调,统一订名。”地学各分支学科之间部分交叉词长期未能统一。现趁各学科名词审定的机会,在全国自然科学名词审定委员会的领导下,地学各分支学科,包括地理学、地质学、地球物理学、海洋学、土壤学、气象学、测绘学等七个学科的分委员会,于1987年和1988年召开了多次学科间的协调会,本着各抒己见、民主协商、着眼于长远,要统一订正的名词尽可能统一的精神,对各学科共同使用的一些名词术语进行协调,使部分术语得到统一;部分名词作了订正;另有少部分因种种原因未能取得一致意见,有关学科仍保留其习用的称谓。一、经过协商,使大部分交叉词得到统一。属于这类词的有喀斯特、判读、大陆架、海拔、地貌学等20余个名词。例如喀斯特原系Karst的音译,指石灰岩等岩石被溶蚀而形成的一种地貌类型,因南斯拉夫的Karst山得名,并被国际地理学界所接受,我国亦一直采用此词的音译。我国地质界倾向于采用意译为“岩溶”,并在1966年召开的一次岩溶学术会议上被广泛接受。此后在广西建立的研究机构也采用了“岩溶研究所”的名称。这次审定过程中地理界提出采用原先的音译较好,既照顾到国际上的习惯用法,又可包括黄土和冰川地区类似的现象。例如用“热喀斯特”就比“热岩溶”恰当。协调会上多数委员同意这个意见。但地质学名词审定工作仍在进行中,如果将来多数委员坚持称岩溶,则以“喀斯特,又称岩溶”处理。又如对遥感图象的判读(Interpretation),曾先后采用过判读、解译、解释、识别等多种称谓。现经地理与测绘分委员会协商,拟采用“判读”。二、纠正了过去的讹误：典型的例子是许多人长期以来将“潟(音细)湖”误作“泻湖”。原来的繁体“瀉”字与“潟”字形同音近而歧义。据查,“泻”系液体快流之意,如“一泻千里”;而“潟”则是咸水浸渍的土地。近海地区海水浸漫之湖理当称“潟湖”,而且中小学地理教科书中已正确使用此词。这次审定过程中,地理分委员会坚持去讹从正,并在协调会上一致通过。三、对各分支学科用法不一,但因长期习用,暂时尚无法统一的,则暂且存异。典型的例子是地理名词中的“亚热带”与气象名词中的“副热带”,同是对应是英文Subtropical Zone。尽管“亚”与“副”在中文中含义有所区别：“亚”有等级的差别,如冠军高于亚军;而“副”有主从之别,如正业、副业,正主席、副主席等。协调会多数人同意称“亚热带”,但气象界长期使用“副热带”一词,并且“副热带高压”在气象预报上常简称为“副高”;一旦改为“亚高”很难被接受。因此在这两个学科的名词中分别采用各自的习惯用法,而加注“又称”。又如地质界地理界习用“大气圈”、“岩石圈”,而气象界、地球物理界习用“大气层”、“岩石层”;地质界习用“亚粘土”,地理界、土壤界习用“壤土”;地理界习用“地图学”,测绘界习用“地图制图学”(或简称为“制图学”)。这些名词,虽经协商,一时尚难统一,有待将来经过更长时间的使用方能逐步取得一致意见。总之,通过学科间的协调,使不少同义异名的词得到统一,并纠正了少数误用的词。也还有一些名词各有关学科未能取得一致的意见,有待将来逐步统一。通过这项工作,我们觉得协调会是一种很好的形式,使相关的学科有机会相互交流,增进彼此的了解,解决了不少问题。而全国自然科学名词审定委员会恰是这种协调会最恰当的组织者和领导者。同时,我们认为协调工作仍需加强,力求做到协调统一,不再存异。这一方面要求有关学科克服困难,放弃习用多年的称谓;另一方面需要加强领导,有些意见不一致的交叉词可由全国自然科学名词审定委员会裁定,强行统一。个别学科的同志在几年内可能存在一些困难,但对后来者将是莫大的方便。事实上国务院于1984年2月27日发布了《关于在我国统一实行法定计量单位的命令》中废除了我们习用多年的“达因”、“尔格”、“埃()”、“巴”、“卡”、“克当量”等许多单位,我们这一代人虽然不习惯,但也在写作、出版时遵照这个规定执行了。难道上述地学名词稍作改变的难度比这些单位的彻底废除还要大吗？现在各持己见沿用下去,多少年以后还是要统一,与其让将来更多的人感到困难,不如由我们这一代人来克服它。因此,我们建议交叉词的协调在充分讨论协商的基础上如仍有分歧,则应由全国名委会予以裁定,有关学科应遵照统一裁定的称谓使用。做到现在就统一,不再等到将来。     

Solving Non-Uniqueness in Agglomerative Hierarchical Clustering Using Multidendrograms

In agglomerative hierarchical clustering, pair-group methods suffer from a problem of non-uniqueness when two or more distances between different clusters coincide during the amalgamation process. The traditional approach for solving this drawback has been to take any arbitrary criterion in order to break ties between distances, which results in different hierarchical classifications depending on the criterion followed. In this article we propose a variable-group algorithm that consists in grouping more than two clusters at the same time when ties occur. We give a tree representation for the results of the algorithm, which we call a multidendrogram, as well as a generalization of the Lance andWilliams’ formula which enables the implementation of the algorithm in a recursive way. The authors thank A. Arenas for discussion and helpful comments. This work was partially supported by DGES of the Spanish Government Project No. FIS2006–13321–C02–02 and by a grant of Universitat Rovira i Virgili.     

A Note on K-modes Clustering

Recently, Chaturvedi, Green and Carroll (2001) presented a nonparametric approach to deriving clusters from categorical data using a new clustering procedure called K-modes. Huang (1998) proposed the K-modes clustering algorithm. In this note, we demonstrate the equivalence of the two K-modes procedures.     

Clustering and isolation in the consensus problem for partitions

We examine the problem of aggregating several partitions of a finite set into a single consensus partition We note that the dual concepts of clustering and isolation are especially significant in this connection. The hypothesis that a consensus partition should respect unanimity with respect to either concept leads us to stress a consensus interval rather than a single partition. The extremes of this interval are characterized axiomatically. If a sufficient totality of traits has been measured, and if measurement errors are independent, then a true classifying partition can be expected to lie in the consensus interval. The structure of the partitions in the interval lends itself to partial solutions of the consensus problem Conditional entropy may be used to quantify the uncertainty inherent in the interval as a whole     

On the Complexity of Ordinal Clustering

Given a set of pairwise distances on a set of n points, constructing an edgeweighted tree whose leaves are these n points such that the tree distances would mimic the original distances under some criteria is a fundamental problem. One such criterion is to preserve the ordinal relation between the pairwise distances. The ordinal relation can be of the form of total order on the distances or it can be some partial order specified on the pairwise distances. We show that the problem of finding a weighted tree, if it exists, which would preserve the total order on pairwise distances is NP-hard. We also show the NP-hardness of the problem of finding a weighted tree which would preserve a particular kind of partial order called a triangle order, one of the most fundamental partial orders considered in computational biology.     

Variable Selection for Clustering and Classification

As data sets continue to grow in size and complexity, effective and efficient techniques are needed to target important features in the variable space. Many of the variable selection techniques that are commonly used alongside clustering algorithms are based upon determining the best variable subspace according to model fitting in a stepwise manner. These techniques are often computationally intensive and can require extended periods of time to run; in fact, some are prohibitively computationally expensive for high-dimensional data. In this paper, a novel variable selection technique is introduced for use in clustering and classification analyses that is both intuitive and computationally efficient. We focus largely on applications in mixture model-based learning, but the technique could be adapted for use with various other clustering/classification methods. Our approach is illustrated on both simulated and real data, highlighted by contrasting its performance with that of other comparable variable selection techniques on the real data sets.     

A Proposal for Robust Curve Clustering

Functional data sets appear in many areas of science. Although each data point may be seen as a large finite-dimensional vector it is preferable to think of them as functions, and many classical multivariate techniques have been generalized for this kind of data. A widely used technique for dealing with functional data is to choose a finite-dimensional basis and find the best projection of each curve onto this basis. Therefore, given a functional basis, an approach for doing curve clustering relies on applying the k-means methodology to the fitted basis coefficients corresponding to all the curves in the data set. Unfortunately, a serious drawback follows from the lack of robustness of k-means. Trimmed k-means clustering (Cuesta-Albertos, Gordaliza, and Matran 1997) provides a robust alternative to the use of k-means and, consequently, it may be successfully used in this functional framework. The proposed approach will be exemplified by considering cubic B-splines bases, but other bases can be applied analogously depending on the application at hand.     

Wavelet-based Fuzzy Clustering of Time Series

Traditional procedures for clustering time series are based mostly on crisp hierarchical or partitioning methods. Given that the dynamics of a time series may change over time, a time series might display patterns that may enable it to belong to one cluster over one period while over another period, its pattern may be more consistent with those in another cluster. The traditional clustering procedures are unable to identify the changing patterns over time. However, clustering based on fuzzy logic will be able to detect the switching patterns from one time period to another thus enabling some time series to simultaneously belong to more than one cluster. In particular, this paper proposes a fuzzy approach to the clustering of time series based on their variances through wavelet decomposition. We will show that this approach will distinguish between time series with different patterns in variability as well identifying time series with switching patterns in variability.     

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.