多节点布局规划.ppt

多节点布局规划——聚类法&穷举法小组成员:杜高飞廖程铖漆光辉谢宏娟熊燕黄珊 3/8/2017 2聚类分析( Cluster Analysis ) ?聚类分析( Cluster Analysis )又称群分析,是根据“物以类聚”的道理,对样品或指标进行分类的一种多元统计分析方法,它们讨论的对象是大量的样品,要求能合理地按各自的特性来进行合理的分类,没有任何模式可供参考或依循,即是在没有先验知识的情况下进行的。聚类分析起源于分类学,在古老的分类学中,人们主要依靠经验和专业知识来实现分类,很少利用数学工具进行定量的分类。随着人类科学技术的发展,对分类的要求越来越高,以致有时仅凭经验和专业知识难以确切地进行分类,于是人们逐渐地把数学工具引用到了分类学中,形成了数值分类学,之后又将多元分析的技术引入到数值分类学形成了聚类分析。?聚类是将数据分类到不同的类或者簇这样的一个过程,所以同一个簇中的对象有很大的相似性,而不同簇间的对象有很大的相异性。聚类分析的目标就是在相似的基础上收集数据来分类。聚类源于很多领域,包括数学,计算机科学, 统计学,生物学和经济学。在不同的应用领域,很多聚类技术都得到了发展,这些技术方法被用作描述数据,衡量不同数据源间的相似性,以及把数据源分类到不同的簇中。 3/8/2017 3聚类分析的计算方法?分裂法(partitioning methods) ?层次法(hierarchical methods) ?基于密度的方法(density-based methods) ?基于网格的方法(grid-basedmethods) ?基于模型的方法(model-based methods) 3/8/2017 4分裂法?分裂法又称划分方法(PAM:PArtitioning method) 首先创建 k个划分, k为要创建的划分个数;然后利用一个循环定位技术通过将对象从一个划分移到另一个划分来帮助改善划分质量。?典型的划分方法包括: ? k-means,k-medoids,CLARA(Clustering LARge Application), ? CLARANS(Clustering Large Application based upon RANdomized Search). ? FCM 3/8/2017 5层次法?层次法(hierarchical method) 创建一个层次以分解给定的数据集。该方法可以分为自上而下(分解)和自下而上(合并)两种操作方式。为弥补分解与合并的不足,层次合并经常要与其它聚类方法相结合,如循环定位。?典型的这类方法包括: ? BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies) 方法,它首先利用树的结构对对象集进行划分;然后再利用其它聚类方法对这些聚类进行优化。? CURE(Clustering Using REprisentatives) 方法,它利用固定数目代表对象来表示相应聚类;然后对各聚类按照指定量(向聚类中心)进行收缩。? ROCK 方法,它利用聚类间的连接进行聚类合并。? CHEMALOEN 方法,它则是在层次聚类时构动态模型。 3/8/2017 6基于密度的方法?基于密度的方法,根据密度完成对象的聚类。它根据对象周围的密度(如 DBSCAN )不断增长聚类。?典型的基于密度方法包括: ? DBSCAN(Densit-based Spatial Clustering of Application with Noise): 该算法通过不断生长足够高密度区域来进行聚类;它能从含有噪声的空间数据库中发现任意形状的聚类。此方法将一个聚类定义为一组“密度连接”的点集。? OPTICS(Ordering Points To Identify the Clustering Structure): 并不明确产生一个聚类,而是为自动交互的聚类分析计算出一个增强聚类顺序。 3/8/2017 7基于网格的方法?首先将对象空间划分为有限个单元以构成网格结构;然后利用网格结构完成聚类。?典型的基于网格的方法包括: ? STING(STatistical INformation Grid) 就是一个利用网格单元保存的统计信息进行基于网格聚类的方法。? CLIQUE(Clustering In QUEst) 和 Wave-Cluster 则是一个将基于网格与基于密度相结合的方法。 3/8/2017 8基于模型的方法?典型的基于模型方法包括: ?统计方法 COBWEB: 是一个常用的且简单的增量式概念聚类方法。它的输入对象是采用符号量(属性-值)对来加以描述的。采用分类树的形式来创建一个层次聚类