Approximation algorithm for the problem of partitioning a sequence into clusters

We consider the problem of partitioning a finite sequence of Euclidean points into a given number of clusters (subsequences) using the criterion of the minimal sum (over all clusters) of intercluster sums of squared distances from the elements of the clusters to their centers. It is assumed that the center of one of the desired clusters is at the origin, while the center of each of the other clusters is unknown and determined as the mean value over all elements in this cluster. Additionally, the partition obeys two structural constraints on the indices of sequence elements contained in the clusters with unknown centers: (1) the concatenation of the indices of elements in these clusters is an increasing sequence, and (2) the difference between an index and the preceding one is bounded above and below by prescribed constants. It is shown that this problem is strongly NP-hard. A 2-approximation algorithm is constructed that is polynomial-time for a fixed number of clusters.     

A divisive clustering method for functional data with special consideration of outliers

This paper presents DivClusFD, a new divisive hierarchical method for the non-supervised classification of functional data. Data of this type present the peculiarity that the differences among clusters may be caused by changes as well in level as in shape. Different clusters can be separated in different subregion and there may be no subregion in which all clusters are separated. In each step of division, the DivClusFD method explores the functions and their derivatives at several fixed points, seeking the subregion in which the highest number of clusters can be separated. The number of clusters is estimated via the gap statistic. The functions are assigned to the new clusters by combining the k-means algorithm with the use of functional boxplots to identify functions that have been incorrectly classified because of their atypical local behavior. The DivClusFD method provides the number of clusters, the classification of the observed functions into the clusters and guidelines that may be for interpreting the clusters. A simulation study using synthetic data and tests of the performance of the DivClusFD method on real data sets indicate that this method is able to classify functions accurately.     

Clustered flow shop models

This paper deals with flow-shop models where n items are grouped in fixed sequences, called clusters. The clusters are to be processed on m machines in the same technological order. Each machine handles the clusters in the same order. Each completed item is available for processing on the next machine. The question is how to arrange the clusters to minimize the completion time. Models that include setup times for clusters with identical items are also examined. Approximate solutions along with new lower bounds are presented. Those solutions are optimal for the two machine case.     

Visualizing high density clusters in multidimensional data using optimized star coordinates

Multidimensional multivariate data have been studied in different areas for quite some time. Commonly, the analysis goal is not to look into individual records but to understand the distribution of the records at large and to find clusters of records that exhibit correlations between dimensions or variables. We propose a visualization method that operates on density rather than individual records. To not restrict our search for clusters, we compute density in the given multidimensional space. Clusters are formed by areas of high density. We present an approach that automatically computes a hierarchical tree of high density clusters. For visualization purposes, we propose a method to project the multidimensional clusters to a 2D or 3D layout. The projection method uses an optimized star coordinates layout. The optimization procedure minimizes the overlap of projected clusters and maximally maintains the cluster shapes, compactness, and distribution. The star coordinate visualization allows for an interactive analysis of the distribution of clusters and comprehension of the relations between clusters and the original dimensions. Clusters are being visualized using nested sequences of density level sets leading to a quantitative understanding of information content, patterns, and relationships.     

Modeling of Phase Transitions in Weakly Bound Molecular Clusters

The method of molecular dynamics was used for modeling the isomerization of a hydrogen bonding network in small water clusters (hexamer and octamer). The collective modes of the particles moving in the clusters were determined by applying principal component analysis. An entropy criterion for phase transitions in water clusters was suggested. This criterion can be used to study phase transitions in weakly bound atomic and molecular clusters.     

Surface magnetism of ferromagnetic ultrafine particles

The electronic structures and atomic magnetic moments of Ni_n clusters (n= 2—6) have been studied. Compared with crystalline nickel, some clusters increase obviously in magnetism; some decrease obviously; and some show ferrimagnetism. The symmetry of clusters has great effect on magnetic moment. If they are similar in symmetry, the clusters are similar in magnetic moment. The magnetic moment for small clusters does not seem to increase or decrease monotonically with the change in their size, because adding or removing one atom may fully change the symmetry of small clusters. As the surface layer of ultrafine particles is made of many different polyhedrons with low symmetry and the alignment of the polyhedrons is complicated, the whole surface layer presents short-range order. The calculated results explain the abnormal phenomena about surface magnetism that have been in existence for a long time.     

Genetic algorithm-tuned entropy-based fuzzy C-means algorithm for obtaining distinct and compact clusters

A modified approach had been developed in this study by combining two well-known algorithms of clustering, namely fuzzy c-means algorithm and entropy-based algorithm. Fuzzy c-means algorithm is one of the most popular algorithms for fuzzy clustering. It could yield compact clusters but might not be able to generate distinct clusters. On the other hand, entropy-based algorithm could obtain distinct clusters, which might not be compact. However, the clusters need to be both distinct as well as compact. The present paper proposes a modified approach of clustering by combining the above two algorithms. A genetic algorithm was utilized for tuning of all three clustering algorithms separately. The proposed approach was found to yield both distinct as well as compact clusters on two data sets.     

Subcritical, Critical and Supercritical Size Distributions in Random Coagulation-Fragmentation Processes

We consider the asymptotic probability distribution coagula-tion-fragmentation process in the thermodynamic limit of the size of a reversible random We prove that the distributions of small, medium and the largest clusters converge to Gaussian, Poisson and 0-1 distributions in the supercritical stage （post-gelation）, respectively. We show also that the mutually dependent distributions of clusters will become independent after the occurrence of a gelation transition. Furthermore, it is proved that all the number distributions of clusters are mutually independent at the critical stage （gelation）, but the distributions of medium and the largest clusters are mutually dependent with positive correlation coefficient in the supercritical stage. When the fragmentation strength goes to zero, there will exist only two types of clusters in the process, one type consists of the smallest clusters, the other is the largest one which has a size nearly equal to the volume （total number of units）.     

产业集群的分形结构—基于演化的观点

以宏观的视角来研究企业的地理分布,并在地理空间与社会网络结构的基础上建立一个产业集群模型;该模型显示出产业集群的分形结构进而揭示出产业集群是一种自组织系统,即在生产交易过程中自发形成有序的结构或状态的现象.根据该模型,运输成本或者禀赋只是形成产业集群的所有充分条件中的一个;影响产业集群的最重要指标是关系网络空间的分形维度,它显示了经济系统的层次结构性.网络密度很大的集群的关系网络可能是接近紊乱的,即分形维度接近于零;而紊乱将会导致这个集群效益下降,甚至促使集群崩溃.     

Microscopical investigation of wave propagation phenomena in residual saturated porous media

Wave propagation is used in many fields for measurement and characterization. Corresponding multiphase models usually use a continuous approach. Nevertheless, systems like wetted rocks may be saturated residually in certain situations. In such cases, one fluid is distributed as clusters, each different in size and shape. One single, continuous phase cannot account for a variety of fluid clusters, either disconnected from each other or connected only about thin liquid films. Therefore, we present a model that considers a heterogeneous distribution of disconnected fluid clusters in the form of harmonic oscillators. These oscillators are described and distinguished by their mass, damping and eigenfrequency. Hence, the model allows to characterize different clusters and includes an additional damping mechanism due to oscillations of the fluid clusters. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

基于模糊数学和层次分析法的内生型产业集群创新能力的评价研究——以江苏省三个产业集群为例

面临突发的金融海啸,内生型产业集群的创新能力尤显重要.以综合运用了层次分析法和模糊数学等理论方法,提出了内生型产业集群创新能力的指标体系,对内生型产业集群的创新能力进行了模糊综合评价,最后以江苏省三个产业集群为例,给出了应用实例,验证了所提出的评价方法及指标体系的可行性.     

Topological and metric properties of infinite clusters in stationary two-dimensional site percolation

A dependent percolation model is a random coloring of the two-lattice. It is assumed that there are a finite number of colors and that the coloring is translation invariant. Each color defines a random subset of the lattice. Connected components of this subset are called clusters. This paper gives a classification of the infinite behavior of these clusters. In particular, it is shown that the lattice is divided into disjoint infinite strips, lying adjacently. Each strip is either composed of an infinite cluster together with isolated finite clusters or else is entirely composed of finite clusters. Examples of the various types of behavior are constructed.     

Classes and clusters in data analysis

We discuss the relation between classes and clusters in datasets with given classes. We examine the distribution of classes within obtained clusters, using different clustering methods which are based on different techniques. We also study the structure of the obtained clusters. One of the main conclusions, obtained in this research is that the notion purity cannot be always used for evaluation of accuracy of clustering techniques.     

一类爆炸凝结过程的数学模型

所建立的数学模型是由可数无穷多个彼此相互关联的非线性常微分方程所组成的自治系统,它刻划了在只有基本粒子与i-粒子(i≥1)进行碰撞反应的系统里,粒子增长过程中密度随时间的变化规律.本文研究了这一自治系统解的性质.     

On the complexity of some Euclidean problems of partitioning a finite set of points

Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (3) norms of the sum of cluster elements. It is proved that all these problems are strongly NP-hard if the number of clusters is a part of the input and are NP-hard in the ordinary sense if the number of clusters is not a part of the input (is fixed). Moreover, the problems are NP-hard even in the case of dimension 1 (on a line).     

NP-Hardness of Some Euclidean Problems of Partitioning a Finite Set of Points

Problems of partitioning a finite set of Euclidean points (vectors) into clusters are considered. The criterion is to minimize the sum, over all clusters, of (1) squared norms of the sums of cluster elements normalized by the cardinality, (2) squared norms of the sums of cluster elements, and (3) norms of the sum of cluster elements. It is proved that all these problems are strongly NP-hard if the number of clusters is a part of the input and are NP-hard in the ordinary sense if the number of clusters is not a part of the input (is fixed). Moreover, the problems are NP-hard even in the case of dimension 1 (on a line).     

Exact pseudopolynomial algorithms for a balanced 2-clustering problem

We consider the strongly NP-hard problem of partitioning a set of Euclidean points into two clusters so as to minimize the sum (over both clusters) of the weighted sum of the squared intracluster distances from the elements of the clusters to their centers. The weights of sums are the sizes of the clusters. The center of one cluster is given as input, while the center of the other cluster is unknown and determined as the average value over all points in the cluster (as the geometric center). Two variants of the problems are analyzed in which the cluster sizes are either given or unknown. We present and prove some exact pseudopolynomial algorithms in the case of integer components of the input points and fixed space dimension.     

带有弹性碰撞的离散的凝结方程

带有弹性碰撞的离散的凝结方程是反映粒子增长动力学的数学模型，它刻划了这样一种粒子反应系统；系统中任意两个粒子碰撞后一定的概率或者凝结成为更大的粒子，或者发生弹性碰撞．本文研究了这一系统发生冻肢的可能性，并给出了一个充分条件．     

Polynomial-Time Approximation Algorithm for the Problem of Cardinality-Weighted Variance-Based 2-Clustering with a Given Center

A strongly NP-hard problem of partitioning a finite set of points of Euclidean space into two clusters is considered. The solution criterion is the minimum of the sum (over both clusters) of weighted sums of squared distances from the elements of each cluster to its geometric center. The weights of the sums are equal to the cardinalities of the desired clusters. The center of one cluster is given as input, while the center of the other is unknown and is determined as the point of space equal to the mean of the cluster elements. A version of the problem is analyzed in which the cardinalities of the clusters are given as input. A polynomial-time 2-approximation algorithm for solving the problem is constructed.     

Failure of Polymer Beams Reinforced with Glass Fibers

Mechanics of Composite Materials - The present paper deals with the four-point bending of polyvinyl chloride beams reinforced with glass fiber clusters. The clusters, treated as orthotropic...