多節(jié)點(diǎn)布局規(guī)劃.ppt

《多節(jié)點(diǎn)布局規(guī)劃.ppt》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、多節(jié)點(diǎn)布局規(guī)劃——聚類(lèi)法&窮舉法小組成員：杜高飛廖程鋮漆光輝謝宏娟熊燕黃珊聚類(lèi)分析（ClusterAnalysis）聚類(lèi)分析（ClusterAnalysis）又稱(chēng)群分析，是根據(jù)“物以類(lèi)聚”的道理，對(duì)樣品或指標(biāo)進(jìn)行分類(lèi)的一種多元統(tǒng)計(jì)分析方法，它們討論的對(duì)象是大量的樣品，要求能合理地按各自的特性來(lái)進(jìn)行合理的分類(lèi)，沒(méi)有任何模式可供參考或依循，即是在沒(méi)有先驗(yàn)知識(shí)的情況下進(jìn)行的。聚類(lèi)分析起源于分類(lèi)學(xué)，在古老的分類(lèi)學(xué)中，人們主要依靠經(jīng)驗(yàn)和專(zhuān)業(yè)知識(shí)來(lái)實(shí)現(xiàn)分類(lèi)，很少利用數(shù)學(xué)工具進(jìn)行定量的分類(lèi)。隨著人類(lèi)科學(xué)技術(shù)的發(fā)展，對(duì)分類(lèi)的要求越來(lái)越高，以致有時(shí)僅憑經(jīng)驗(yàn)和

2、專(zhuān)業(yè)知識(shí)難以確切地進(jìn)行分類(lèi)，于是人們逐漸地把數(shù)學(xué)工具引用到了分類(lèi)學(xué)中，形成了數(shù)值分類(lèi)學(xué)，之后又將多元分析的技術(shù)引入到數(shù)值分類(lèi)學(xué)形成了聚類(lèi)分析。聚類(lèi)是將數(shù)據(jù)分類(lèi)到不同的類(lèi)或者簇這樣的一個(gè)過(guò)程，所以同一個(gè)簇中的對(duì)象有很大的相似性，而不同簇間的對(duì)象有很大的相異性。聚類(lèi)分析的目標(biāo)就是在相似的基礎(chǔ)上收集數(shù)據(jù)來(lái)分類(lèi)。聚類(lèi)源于很多領(lǐng)域，包括數(shù)學(xué)，計(jì)算機(jī)科學(xué)，統(tǒng)計(jì)學(xué)，生物學(xué)和經(jīng)濟(jì)學(xué)。在不同的應(yīng)用領(lǐng)域，很多聚類(lèi)技術(shù)都得到了發(fā)展，這些技術(shù)方法被用作描述數(shù)據(jù)，衡量不同數(shù)據(jù)源間的相似性，以及把數(shù)據(jù)源分類(lèi)到不同的簇中。2021/7/172聚類(lèi)分析的計(jì)算方法分裂法(p

3、artitioningmethods)層次法(hierarchicalmethods)基于密度的方法(density-basedmethods)基于網(wǎng)格的方法(grid-basedmethods)基于模型的方法(model-basedmethods)2021/7/173分裂法分裂法又稱(chēng)劃分方法(PAM:PArtitioningmethod)首先創(chuàng)建k個(gè)劃分，k為要?jiǎng)?chuàng)建的劃分個(gè)數(shù)；然后利用一個(gè)循環(huán)定位技術(shù)通過(guò)將對(duì)象從一個(gè)劃分移到另一個(gè)劃分來(lái)幫助改善劃分質(zhì)量。典型的劃分方法包括：k-means,k-medoids,CLARA(Clusterin

4、gLARgeApplication),CLARANS(ClusteringLargeApplicationbaseduponRANdomizedSearch).FCM2021/7/174層次法層次法(hierarchicalmethod)創(chuàng)建一個(gè)層次以分解給定的數(shù)據(jù)集。該方法可以分為自上而下（分解）和自下而上（合并）兩種操作方式。為彌補(bǔ)分解與合并的不足，層次合并經(jīng)常要與其它聚類(lèi)方法相結(jié)合，如循環(huán)定位。典型的這類(lèi)方法包括：BIRCH(BalancedIterativeReducingandClusteringusingHierarchies)

5、方法，它首先利用樹(shù)的結(jié)構(gòu)對(duì)對(duì)象集進(jìn)行劃分；然后再利用其它聚類(lèi)方法對(duì)這些聚類(lèi)進(jìn)行優(yōu)化。CURE(ClusteringUsingREprisentatives)方法，它利用固定數(shù)目代表對(duì)象來(lái)表示相應(yīng)聚類(lèi)；然后對(duì)各聚類(lèi)按照指定量（向聚類(lèi)中心）進(jìn)行收縮。ROCK方法，它利用聚類(lèi)間的連接進(jìn)行聚類(lèi)合并。CHEMALOEN方法，它則是在層次聚類(lèi)時(shí)構(gòu)動(dòng)態(tài)模型。2021/7/175基于密度的方法基于密度的方法，根據(jù)密度完成對(duì)象的聚類(lèi)。它根據(jù)對(duì)象周?chē)拿芏龋ㄈ鏒BSCAN）不斷增長(zhǎng)聚類(lèi)。典型的基于密度方法包括：DBSCAN(Densit-basedSpatia

6、lClusteringofApplicationwithNoise):該算法通過(guò)不斷生長(zhǎng)足夠高密度區(qū)域來(lái)進(jìn)行聚類(lèi)；它能從含有噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類(lèi)。此方法將一個(gè)聚類(lèi)定義為一組“密度連接”的點(diǎn)集。OPTICS(OrderingPointsToIdentifytheClusteringStructure):并不明確產(chǎn)生一個(gè)聚類(lèi)，而是為自動(dòng)交互的聚類(lèi)分析計(jì)算出一個(gè)增強(qiáng)聚類(lèi)順序。2021/7/176基于網(wǎng)格的方法首先將對(duì)象空間劃分為有限個(gè)單元以構(gòu)成網(wǎng)格結(jié)構(gòu)；然后利用網(wǎng)格結(jié)構(gòu)完成聚類(lèi)。典型的基于網(wǎng)格的方法包括：STING(STatist

7、icalINformationGrid)就是一個(gè)利用網(wǎng)格單元保存的統(tǒng)計(jì)信息進(jìn)行基于網(wǎng)格聚類(lèi)的方法。CLIQUE(ClusteringInQUEst)和Wave-Cluster則是一個(gè)將基于網(wǎng)格與基于密度相結(jié)合的方法。2021/7/177基于模型的方法典型的基于模型方法包括：統(tǒng)計(jì)方法COBWEB:是一個(gè)常用的且簡(jiǎn)單的增量式概念聚類(lèi)方法。它的輸入對(duì)象是采用符號(hào)量（屬性-值）對(duì)來(lái)加以描述的。采用分類(lèi)樹(shù)的形式來(lái)創(chuàng)建一個(gè)層次聚類(lèi)。CLASSIT是COBWEB的另一個(gè)版本.。它可以對(duì)連續(xù)取值屬性進(jìn)行增量式聚類(lèi)。它為每個(gè)結(jié)點(diǎn)中的每個(gè)屬性保存相應(yīng)的連續(xù)正態(tài)

8、分布（均值與方差）；并利用一個(gè)改進(jìn)的分類(lèi)能力描述方法，即不象COBWEB那樣計(jì)算離散屬性（取值）和而是對(duì)連續(xù)屬性求積分。但是CLASSIT方法也存在與COBWEB類(lèi)似的問(wèn)題。因此