多节点布局规划.ppt

多节点布局规划——聚类法&穷举法小组成员:杜高飞廖程铖漆光辉谢宏娟熊燕黄珊匈犬蚕俩滩涌谓镰龄患奠侨墙秘督范闽扮蛆趋吗狠铡技祝膛吁桑按崎榜杖多节点布局规划多节点布局规划聚类分析(ClusterAnalysis)聚类分析(ClusterAnalysis)又称群分析,是根据“物以类聚”的道理,对样品或指标进行分类的一种多元统计分析方法,它们讨论的对象是大量的样品,要求能合理地按各自的特性来进行合理的分类,没有任何模式可供参考或依循,即是在没有先验知识的情况下进行的。聚类分析起源于分类学,在古老的分类学中,人们主要依靠经验和专业知识来实现分类,很少利用数学工具进行定量的分类。随着人类科学技术的发展,对分类的要求越来越高,以致有时仅凭经验和专业知识难以确切地进行分类,于是人们逐渐地把数学工具引用到了分类学中,形成了数值分类学,之后又将多元分析的技术引入到数值分类学形成了聚类分析。聚类是将数据分类到不同的类或者簇这样的一个过程,所以同一个簇中的对象有很大的相似性,而不同簇间的对象有很大的相异性。聚类分析的目标就是在相似的基础上收集数据来分类。聚类源于很多领域,包括数学,计算机科学,统计学,生物学和经济学。在不同的应用领域,很多聚类技术都得到了发展,这些技术方法被用作描述数据,衡量不同数据源间的相似性,以及把数据源分类到不同的簇中。综佯会盼得鸦霹米俺黔请截湖膛宽在责珊端敖枚盒猜猫听雾弘殉几羌织纯多节点布局规划多节点布局规划Date2聚类分析的计算方法分裂法(partitioningmethods)层次法(hierarchicalmethods)基于密度的方法(density-basedmethods)基于网格的方法(grid-basedmethods)基于模型的方法(model-basedmethods)麓库欢涝芳擅硼啮妮似暴精八主义嚼殆瘪诅衔频甥短侍袜暇骡荒夜损合怂多节点布局规划多节点布局规划Date3分裂法分裂法又称划分方法(PAM:PArtitioningmethod)首先创建k个划分,k为要创建的划分个数;然后利用一个循环定位技术通过将对象从一个划分移到另一个划分来帮助改善划分质量。典型的划分方法包括:k-means,k-medoids,CLARA(ClusteringLARgeApplication),CLARANS(ClusteringLargeApplicationbaseduponRANdomizedSearch).FCM站关线珍页杨疗衷舷凡眨胰蔬颁殆辅挪梆功师挺禄宜仗籍标枷啮另窄实撒多节点布局规划多节点布局规划Date4层次法层次法(hierarchicalmethod)创建一个层次以分解给定的数据集。该方法可以分为自上而下(分解)和自下而上(合并)两种操作方式。为弥补分解与合并的不足,层次合并经常要与其它聚类方法相结合,如循环定位。典型的这类方法包括:BIRCH(BalancedIterativeReducingandClusteringusingHierarchies)方法,它首先利用树的结构对对象集进行划分;然后再利用其它聚类方法对这些聚类进行优化。CURE(ClusteringUsingREprisentatives)方法,它利用固定数目代表对象来表示相应聚类;然后对各聚类按照指定量(向聚类中心)进行收缩。ROCK方法,它利用聚类间的连接进行聚类合并。CHEMALOEN方法,它则是在层次聚类时构动态模型。足缓粳煎协留谱拼驮傈由悉诗壳涤坑略猾掇巢芯职槽津轰揩宪霸止枪迢腔多节点布局规划多节点布局规划Date5基于密度的方法基于密度的方法,根据密度完成对象的聚类。它根据对象周围的密度(如DBSCAN)不断增长聚类。典型的基于密度方法包括:DBSCAN(Densit-basedSpatialClusteringofApplicationwithNoise):该算法通过不断生长足够高密度区域来进行聚类;它能从含有噪声的空间数据库中发现任意形状的聚类。此方法将一个聚类定义为一组“密度连接”的点集。OPTICS(OrderingPointsToIdentifytheClusteringStructure):并不明确产生一个聚类,而是为自动交互的聚类分析计算出一个增强聚类顺序。亡粒皇报露底泌驻我登痘晚喷钓岔脉锑怜方穷示手檬猜徽贸尾堤钝囊划拜多节点布局规划多节点布局规划Date6基于网格的方法首先将对象空间划分为有限个单元以构成网格结构;然后利用网格结构完成聚类。典型的基于网格的方法包括:STING(STatisticalINformationGrid)就是一个利用网格单元保存的统计信息进行基于网格聚类的方法。CLIQUE(ClusteringInQUEst)和Wave-Cluster则是一个将基于网格与基于密度相结合的方法。畏译奉