Hierarchical Model-Based Clustering for Large Datasets

In recent years, hierarchical model-based clustering has provided promising results in a variety of applications. However, its use with large datasets has been hindered by a time and memory complexity that are at least quadratic in the number of observations. To overcome this difficulty, this article proposes to start the hierarchical agglomeration from an efficient classification of the data in many classes rather than from the usual set of singleton clusters. This initial partition is derived from a subgraph of the minimum spanning tree associated with the data. To this end, we develop graphical tools that assess the presence of clusters in the data and uncover observations difficult to classify. We use this approach to analyze two large, real datasets: a multiband MRI image of the human brain and data on global precipitation climatology. We use the real datasets to discuss ways of integrating the spatial information in the clustering analysis. We focus on two-stage methods, in which a second stage of processing using established methods is applied to the output from the algorithm presented in this article, viewed as a first stage.     

Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition

We present efficient (parallel) algorithms for two hierarchical clustering heuristics. We point out that these heuristics can also be applied to solving some algorithmic problems in graphs, including split decomposition. We show that efficient parallel split decomposition induces an efficient parallel parity graph recognition algorithm. This is a consequence of the result of S. Cicerone and D. Di Stefano [[7]] that parity graphs are exactly those graphs that can be split decomposed into cliques and bipartite graphs.     

网络聚类算法及其生物信息学应用

介绍一些网络聚类算法及其基本原理,简述了其在生物信息学的应用。本文不是一个网络聚类算法的全面综述,只介绍这些网络聚类算法的基本思路,体会其数学建模的基本思想。     

Computational Tools for Evaluating Phylogenetic and Hierarchical Clustering Trees

This article presents an alternative derivation of the generalized approximate crossvalidation (GACV) score of Xiang and Wahba (1996) for smoothing parameter selection in penalized likelihood regression. The new derivation suggests a simple numerical solution that is stable for all sample sizes. Also suggested is a variant of the score that can be computationally more convenient. Simple simulations are presented to illustrate the effectiveness of the scores.     

基于聚类技术的股市基本趋势规律挖掘

提出采用技术指标构造特征空间,在特征空间上用模糊核聚类算法寻找股市规律的股市技术分析方法。对1997年以来的沪深大盘指数进行了实证分析检验,识别出了市场基本趋势的演化规律,显示出该方法具有长期预测市场发展方向的能力。     

土壤分类的模糊集成算法与应用

土壤是一个多性状的连续体,其分类的首选方法是模糊聚类分析.但是模糊聚类分析中现有的基于模糊等价关系的动态聚类法和模糊c-均值法各有利弊,采用其中一种方法聚类肯定存在不足.为此集成两种聚类方法的优点,避其缺点,提出了用基于模糊等价关系的动态聚类方法和方差分析方法确定聚类数目和初始聚类中心,再用模糊c-均值法决定最终分类结果的集成算法,并将其应用到松花江流域土壤分类中,得到了较为切合实际的分类结果.     

一种稳健的聚类方法

本文讨论一种新的聚类方法 :属性均值聚类 .通过理论分析 ,属性均值聚类是比模糊均值聚类更稳健的聚类方法 .数值实验说明了该方法的有效性     

A Structured Family of Clustering and Tree Construction Methods

A cluster A is an Apresjan cluster if every pair of objects within A is more similar than either is to any object outside A. The criterion is intuitive, compelling, but often too restrictive for applications in classification. We therefore explore extensions of Apresjan clustering to a family of related hierarchical clustering methods. The extensions are shown to be closely connected with the well-known single and average linkage tree constructions. A dual family of methods for classification by splits is also presented. Splits are partitions of the set of objects into two disjoint blocks and are widely used in domains such as phylogenetics. Both the cluster and split methods give rise to progressively refined tree representations. We exploit dualities and connections between the various methods, giving polynomial time construction algorithms for most of the constructions and NP-hardness results for the rest.     

模糊集IF-THEN规则的蚁群空间聚类分析

将蚂蚁的拾起和放下对象的行为表示为模糊集.通过模糊集的IF-THEN规则计算蚂蚁执行任务的激励和反应阈值,得到蚂蚁拾起或放下项目的概率,对蚂蚁的行为做出决策,实现对空间数据的聚类.以矿山实际测量数据为空间数据源,采用基本的蚁群聚类算法和模糊蚁群空间聚类算法分别对其进行聚类.通过对这两种算法的实验结果进行分析比较,证明改进后的算法提高了聚类效果.     

一种新城市气温模式分类的聚类算法

城市气温是对城市气候特性评价的一个重要指标.提出核概率聚类算法并将其应用于城市气温的模式分类中,以此寻找城市发展上的共同点.该算法在概率聚类算法上引入了核学习方法的思想,能够很好地处理噪音和孤立点,实现更为准确的聚类.实验结果表明,与相关聚类算法相比,核概率聚类算法聚类效果好,且算法能够很快地收敛.     

模糊聚类分析的新算法

提出了一种模糊聚类分析的新算法——追踪法 ,解决了以往模糊聚类分析计算量过大以及难于编程实现的问题 .该方法尤其适用于大规模数据的模糊聚类分析 ,对于模糊聚类分析的推广使用有重要意义 .     

基于业绩持续性的证券投资基金聚类与实证研究

目前基金的分类方法大多是从基金的性质特点出发的主观分类方法,没有反映出基金资产的实际运作效果。本文采用聚类的思想,以基金的业绩表现为基础,从业绩持续性的角度提出了一种新的分类方法:基于业绩持续性的基金聚类。通过对基金业绩持续性的研究,构造了一个业绩持续指数,并用该指数对样本进行聚类。实证研究结果表明,该分类方法是可行和有效的。     

Constraint Handling in Genetic Algorithms: The Set Partitioning Problem

In this paper we present a genetic algorithm-based heuristic for solving the set partitioning problem (SPP). The SPP is an important combinatorial optimisation problem used by many airlines as a mathematical model for flight crew scheduling.A key feature of the SPP is that it is a highly constrained problem, all constraints being equalities. New genetic algorithm (GA) components: separate fitness and unfitness scores, adaptive mutation, matching selection and ranking replacement, are introduced to enable a GA to effectively handle such constraints. These components are generalisable to any GA for constrained problems.We present a steady-state GA in conjunction with a specialised heuristic improvement operator for solving the SPP. The performance of our algorithm is evaluated on a large set of real-world problems. Computational results show that the genetic algorithm-based heuristic is capable of producing high-quality solutions.     

Linear Discrimination with Adaptive Ridge Classification Rules

This article considers the use of adaptive ridge classification rules for classifying an observation as coming from one of two multivariate normal distributionsN(μ⁽¹⁾, Σ) andN(μ⁽²⁾, Σ). In particular, the asymptotic expected error rates for a general class of these rules are obtained and are compared with that of the usual linear discriminant rule.     

Partitioning triples and partially ordered sets

We prove that if  is a partial order and , then

(a)

, and

(b)

for each .

Together these results represent the best progress known to us on the following question of P. Erdos and others. If , then does for each and each ?

     

一种基于区间数多指标信息的FCM聚类算法

针对一类具有不确定性区间数多指标信息的聚类分析问题，依据传统的基于数值信息的FCM聚类算法的思路，提出了一种新的聚类分析算法。章首先描述了具有区间数多指标信息的聚类分析问题；其次给出了基于区间数多指标信息的关于最优划分和最优聚类中心确定的两个定理；然后给出了基于区间数多指标信息的FCM聚类算法的计算步骤。该算法的特点是聚类中心的表现形式为精确的数值，给出的两个定理说明了该聚类算法的收敛性。最后，通过给出一个算例说明了本给出的聚类算法。     

运输问题的模糊聚类分析求解

通过对传统模糊聚类经验公式的改进和对最后两类排序的确定,提出了一种基 于模糊聚类分析的运输问题简单快速的求解方法．编出了通用程序,并给除了实例和计算 结果．该算法既是模糊聚类分析应用的扩展,又是对运筹学知识的补充和完善．     

A Global Optimization RLT-based Approach for Solving the Fuzzy Clustering Problem

The field of cluster analysis is primarily concerned with the partitioning of data points into different clusters so as to optimize a certain criterion. Rapid advances in technology have made it possible to address clustering problems via optimization theory. In this paper, we present a global optimization algorithm to solve the fuzzy clustering problem, where each data point is to be assigned to (possibly) several clusters, with a membership grade assigned to each data point that reflects the likelihood of the data point belonging to that cluster. The fuzzy clustering problem is formulated as a nonlinear program, for which a tight linear programming relaxation is constructed via the Reformulation-Linearization Technique (RLT) in concert with additional valid inequalities. This construct is embedded within a specialized branch-and-bound (B&B) algorithm to solve the problem to global optimality. Computational experience is reported using several standard data sets from the literature as well as using synthetically generated larger problem instances. The results validate the robustness of the proposed algorithmic procedure and exhibit its dominance over the popular fuzzy c-means algorithmic technique and the commercial global optimizer BARON.     

基于数据流形结构的聚类方法及其应用研究

随着信息社会的不断发展,人类已经进入了信息爆炸时代,海量的数据使数据处理变得繁琐复杂,因此如何对现有的高维数据降维、聚类,并在一定程度上消除高维数据中存在的噪声是解决该问题的关键.基于相关的理论知识采用先降维后聚类的步骤,把高维数据按照子空间结构和流形结构两种情况分类,运用稀疏子空间聚类、谱多流形聚类、K-manifolds方法进行建模求解,通过对各种方法的对比,得出谱多流形聚类方法运行速度快,聚类准确度高,是最具有一般性特征的模型.     

A Doubly Adaptive Integration Algorithm Using Stratified Rules

A doubly adaptive integration algorithm chooses between a higher order rule applied on the current subinterval or the subdivision of the interval. We describe one such algorithm using a stratified sequence of integration rules. We present a criterion to select the suitable strategy, depending on the type of integrand, using available information.