一种改进的进化树构建算法

邻接法是最有效的距离建树法的一种,但邻接法的聚类过程总是选择距离最近的进行聚类,容易忽略一些更为合理的拓扑结构,这是邻接法准确性不够理想的一个重要原因。为了提高邻接法的准确性,本文结合最大似然法提出一种改进的进化树构建算法。该算法在邻接法基础上,结合最大似然法搜索最优的拓扑结构,通过模拟实验将改进算法与邻接法等进化树构建算法进行比较,实验结果表明,改进算法的准确性明显优于邻接法。     

A hybrid approach to parallelize a fast non‐dominated sorting genetic algorithm for phylogenetic inference

The field of computational biology encloses a wide range of optimization problems that show non‐deterministic polynomial‐time hard complexities. Nowadays, phylogeneticians are dealing with a growing amount of biological data that must be analyzed to explain the origins of modern species. Evolutionary relationships among organisms are often described by means of tree‐shaped structures known as phylogenetic trees. When inferring phylogenies, two main challenges must be addressed. First, the inference of reliable evolutionary trees on data sets where different optimality principles support conflicting evolutionary hypotheses. Second, the processing of enormous tree searches spaces where traditional sequential strategies cannot be applied. In this sense, phylogenetic inference can benefit from the combination of high performance computing and evolutionary computation to carry out the reconstruction of complex evolutionary histories in reduced execution times. In this paper, we introduce multiobjective phylogenetics, a hybrid OpenMP/MPI approach to parallelize a well‐known multiobjective metaheuristic, the fast non‐dominated sorting genetic algorithm (NSGA‐II). This algorithm has been designed to conduct phylogenetic analyses on multi‐core clusters in accordance with two principles: maximum parsimony and maximum likelihood. The main goal is to combine the benefits of shared‐memory and distributed‐memory programming paradigms to efficiently infer a set of high‐quality Pareto solutions. Experiments on six real nucleotide data sets and comparisons with other hybrid parallel approaches show that multiobjective phylogenetics is able to achieve significant performance in terms of parallel, multiobjective, and biological results. Copyright © 2014 John Wiley & Sons, Ltd.     

Shortest-linkage-based parallel hierarchical clustering on main-belt moving objects of the solar system

Data clustering is an important data preparation process in many scientific analysis researches. In astronomy, although the distributed environments and modern observation techniques enable users to collect and access huge amounts of data, the corresponding clustering process may become very costly. One of the challenges is that the sequential clustering algorithms, that can be applied to cluster hundreds of thousand main-belt asteroids to reason about the origins of the main-belt asteroids, may not be used in the distributed environment directly. Therefore, this study focuses on the problem of parallelizing the traditional hierarchical agglomerative clustering algorithm using shortest-linkage. We propose a new parallel hierarchical agglomerative clustering algorithm based on the master–worker model. The master process divides the whole computation into several small tasks, and distributes the tasks to the worker processes for parallel processing. Then, the master process merges the results from the worker processes to form a hierarchical data structure. The proposed algorithm uses a pruning threshold to reduce the execution time and the storage requirement during the computation. It also supports fast incremental update that merges new data items into a constructed hierarchical tree in seconds, given a tree of about 550,000 data items. To evaluate the performance of our algorithm, this study has conducted several experiments using the MPCORB dataset and a dataset from the DVO database. The results confirm the efficiency of our proposed methodology. Compared with prior similar studies, the proposed algorithm is more flexible and practical in the problem of distributed hierarchical agglomerative clustering.     

面向大规模数据的快速并行聚类划分算法研究

随着聚类分析中处理数据量的急剧增加,面对大规模数据,传统K-Means聚类算法面临着巨大挑战。为了提高传统K-Means聚类算法的效率,针对已有基于MPI的并行K-Means聚类算法和基于Hadoop的分布式K-Means云聚类算法,从聚心初始化和通信模式等入手,提出了改进思路和具体实现。实验结果表明,所提算法能大大减少通信量和计算量,具有较高的执行效率。研究结果可以为以后设计更好的大规模数据快速并行聚类划分算法提供研究依据。     

一种基于网格的改进的K-Means聚类算法

K-Means算法对数据集中的每个数据点进行多次处理,因此对于大数据集时间效率不高.为提高K-Means算法的时间性能并使聚类结果更优,利用网格方法定义了单元密度聚合度概念,提出了一种基于网格的改进的K-Means聚类算法(IKMG).IKMG利用网格连通性原理并借助树形结构,将多个密集网格单元作为初始根节点,周围网格作为它的子节点,以此类推,广度优先扩展树最终得到K个聚类树.实验结果表明,IKMG不但大大缩短了K-Means算法对大数据集的处理时间,而且能有效消除聚类结果对初始聚类中心的敏感性,无需人为指定K值,能找出不同大小、不同形状的聚类.     

处理不平衡数据的聚类欠采样加权随机森林算法

针对现有欠采样处理算法中存在样本缺少代表性、分类性能差等问题,提出了一种基于聚类欠采样的加权随机森林算法(weighted random forest algorithm based on clustering under-sampling,CUS-WRF)。利用K-means算法对多数类样本聚类,引入欧氏距离作为欠采样时分配样本个数的权重依据,使采样后的多数类样本与少数类样本形成一个平衡的样本集,以CART决策树为基分类器,加权随机森林为整体框架,同时将测试样本的准确率作为每棵树的权值来完成对结果的最终投票,有效提高了整体分类性能。选择八组KEEL数据集进行实验,结果表明,与其余四种基于随机森林的不平衡数据处理算法相比,CUS-WRF算法的分类性能及稳定性更具优势。     

改进的最小生成树自适应分层聚类算法

针对传统最小生成树聚类算法需要事先知道聚类数目和使用静态全局分类依据,导致聚类密度相差较大时,算法有效性下降,计算复杂度大等问题,提出一种改进的最小生成树自适应分层聚类算法,根据最近邻关系,自动为每个聚类簇设定独立的阈值,使之适应分布密度相差较大的情况,并能自动确定聚类数目。实验表明,算法具有较好的性能,尤其对数据密度分布不均匀的情况也能得到较好的聚类结果。     

基于时间序列的AP-NN混合模型聚类

仿射传播算法是一种快速有效的聚类方法,但其聚类结果的不稳定性影响了聚类性能。对此,提出基于近邻的仿射传播算法(AP-NN),通过仿射传播算法产生初始簇,并从中选择代表簇对非代表簇的样本进行近邻聚类。在时间序列数据集上的实验结果表明,AP-NN模型算法能够产生较好的聚类结果,适用于聚类分析。     

高度不平衡数据的代价敏感随机森林分类算法

在处理高度不平衡数据时,代价敏感随机森林算法存在自助法采样导致小类样本学习不充分、大类样本占比较大、容易削弱代价敏感机制等问题.文中通过对大类样本聚类后,多次采用弱平衡准则对每个集群进行降采样,使选择的大类样本与原训练集的小类样本融合生成多个新的不平衡数据集,用于代价敏感决策树的训练.由此提出基于聚类的弱平衡代价敏感随机森林算法,不仅使小类样本得到充分学习,同时通过降低大类样本数量,保证代价敏感机制受其影响较小.实验表明,文中算法在处理高度不平衡数据集时性能较优.     

基于连通距离和连通强度的BIRCH改进算法

为解决利用层次方法的平衡迭代规约和聚类（BIRCH）算法聚类结果依赖于数据对象的添加顺序，且对非球状的簇聚类效果不好以及受簇直径阈值的限制每个簇只能包含数量相近的数据对象的问题，提出一种改进的BIRCH算法。该算法用描述数据对象个体间连通性的连通距离和连通强度阈值替代簇直径阈值，还将簇合并的步骤加入到聚类特征树的生成过程中。在自定义及iris、wine、pendigits数据集上的实验结果表明，该算法比多阈值BIRCH、密度改进BIRCH等现有改进算法的聚类准确率更高，尤其在大数据集上比密度改进BIRCH准确率提高6个百分点，耗时降低61%。说明该算法能够适用于在线实时增量数据，可以识别非球形簇和体积不均匀簇，具有去噪功能，且时间和空间复杂度明显降低。     

Fast global k-means clustering using cluster membership and inequality

In this paper, we present a fast global k-means clustering algorithm by making use of the cluster membership and geometrical information of a data point. This algorithm is referred to as MFGKM. The algorithm uses a set of inequalities developed in this paper to determine a starting point for the jth cluster center of global k-means clustering. Adopting multiple cluster center selection (MCS) for MFGKM, we also develop another clustering algorithm called MFGKM+MCS. MCS determines more than one starting point for each step of cluster split; while the available fast and modified global k-means clustering algorithms select one starting point for each cluster split. Our proposed method MFGKM can obtain the least distortion; while MFGKM+MCS may give the least computing time. Compared to the modified global k-means clustering algorithm, our method MFGKM can reduce the computing time and number of distance calculations by a factor of 3.78-5.55 and 21.13-31.41, respectively, with the average distortion reduction of 5,487 for the Statlog data set. Compared to the fast global k-means clustering algorithm, our method MFGKM+MCS can reduce the computing time by a factor of 5.78-8.70 with the average reduction of distortion of 30,564 using the same data set. The performances of our proposed methods are more remarkable when a data set with higher dimension is divided into more clusters.     

一种基于密度的分布式聚类方法

聚类是数据挖掘领域中的一种重要的数据分析方法.它根据数据间的相似度,将无标注数据划分为若干聚簇.CSDP是一种基于密度的聚类算法,当数据量较大或数据维数较高时,聚类的效率相对较低.为了提高聚类算法的效率,提出了一种基于密度的分布式聚类方法MRCSDP,利用MapReduce框架对实验数据进行聚类.该方法定义了独立计算单元和独立计算块的概念.首先,将数据拆分为若干数据块,构建独立计算单元和独立计算块,在集群中分配独立计算块的任务;然后进行分布式计算,得到数据块的局部密度,将局部密度合并得到全局密度,根据全局密度计算中心值,由全局密度和中心值得到每个数据块中候选聚簇中心;最后,从候选聚簇中心选举出最终的聚簇中心.MRCSDP在充分降低时间复杂度的基础上得到较好的聚类效果.实验结果表明,分布式环境下的聚类方法MRCSDP相对于CSDP更能快速、有效地处理大规模数据,并使各节点负载均衡.     

滑动窗口模型下的优化数据流聚类算法

为提高对进化数据流的聚类质量及效率,采用聚类特征指数直方图支持数据处理,减少直方图结构的维护数,改进滑动窗口下的流数据聚类算法。实验表明,与传统基于界标模型的聚类算法相比,优化算法可获得较好的工作效率、较小的内存开销和快速的数据处理能力,拓展了流数据挖掘技术的应用领域。     

A Fast Multiclass Classification Algorithm Based on Cooperative Clustering

We present a fast multiclass classification algorithm to address the multiclass problems with a new clustering method, namely cooperative clustering. In the method of cooperative clustering, we iteratively compute the cluster centers of all classes simultaneously. For every cluster center in a class, a cluster center in an adjacent class is selected and the pair of cluster centers is drawn towards the boundary. In this way, the data set around a class is found and the data set plus the data in this class can be trained to form a classifier. With cooperative clustering, one binary classifier in the one-vs-all approach can be trained with far less samples. Furthermore, a kNN method is proposed to accelerate the classifying procedure. With this algorithm, both training and classification efficiency are improved with a slight impact on classification accuracy.     

基于节点数据密度的分布式K-means聚类算法研究*

P2P(peer-to-peer)网络分布式聚类算法是利用P2P网络上各个节点的计算、存储能力以及网络的带宽,将算法的时间复杂度和空间复杂度平摊到各个节点,使处理和分析海量分布式数据成为可能,从而克服传统基于单个服务器的集中式聚类算法在数据处理能力等方面的限制。提出一种基于节点置信半径的分布式K-means聚类算法,该算法通过计算节点上数据分布的密度,找到同一类数据在节点的稠密和稀疏分布,从而确定聚类置信半径并指导下一步的聚类。实验表明,该算法能够有效地减少迭代次数,节省网络带宽;同时聚类结果也接近集中式聚类算法的结果。     

组件树理论和方法研究综述

组件树方法是数学形态学理论及方法的进一步发展，它利用一系列阈值截集产生连通分量，构造其上的层次关系。利用组件树方法发展出的一系列高效的图像处理算法，非常适合图像底层特征的快速提取，在广大的领域，尤其是医学图像处理领域，得到了广泛的应用。对组件树方法的发展和现状进行了系统的回顾，概述了现存的组件树建树算法以及基于组件树的图像处理算法。对组件树在多值（彩色）图像相关领域、树的快速构建、并行化处理算法方面的研究进行了展望。     

时间滑动窗口内基于密度的数据流聚类算法

为了提高数据流的聚类质量和效率,采用等时间跨度滑动窗口技术,然后利用改进的微簇结构保存数据流的概要信息,最后利用微簇删除策略,定期删除过期、孤立微簇。基于真实数据集与人工数据集的实验表明:与传统基于界标模型的聚类算法相比,该算法可获得较好的效率、较小的内存开销和快速的数据处理能力。     

基于滑动窗口的流数据聚类算法研究

为提高对进化数据流的聚类质量及效率,改进了基于滑动窗口的数据流聚类算法,采用聚类特征指数直方图来支持数据处理,减少了直方图结构的维护数,并在复杂度、聚类效果上得到了进一步改善.理论及验证表明,与传统基于界标模型的聚类算法相比,优化算法可获得较好的工作效率、较小的内存开销和快速的数据处理能力,拓展了数据流挖掘技术的应用领域.     

一种适用于短消息文本的聚类算法

针对短消息文本聚类,设计基于频繁词集和Ant-Tree的混合聚类方法。该算法利用基于频繁词集聚类算法处理文本数据的效率优势,生成初始聚簇,计算轮廓系数消除重叠文档,在此基础上再通过Ant-Tree算法继续精化,最终得到高质量的结果输出。而且聚类结果保留了描述信息和树状层级结构,提供了更广阔的应用。