多節(jié)點布局規(guī)劃

——聚類法&窮舉法小組成員：杜高飛廖程鋮漆光輝謝宏娟熊燕黃珊聚類分析（ClusterAnalysis）

聚類分析（ClusterAnalysis）又稱群分析，是根據(jù)“物以類聚”的道理，對樣品或指標(biāo)進(jìn)行分類的一種多元統(tǒng)計分析方法，它們討論的對象是大量的樣品，要求能合理地按各自的特性來進(jìn)行合理的分類，沒有任何模式可供參考或依循，即是在沒有先驗知識的情況下進(jìn)行的。聚類分析起源于分類學(xué)，在古老的分類學(xué)中，人們主要依靠經(jīng)驗和專業(yè)知識來實現(xiàn)分類，很少利用數(shù)學(xué)工具進(jìn)行定量的分類。隨著人類科學(xué)技術(shù)的發(fā)展，對分類的要求越來越高，以致有時僅憑經(jīng)驗和專業(yè)知識難以確切地進(jìn)行分類，于是人們逐漸地把數(shù)學(xué)工具引用到了分類學(xué)中，形成了數(shù)值分類學(xué)，之后又將多元分析的技術(shù)引入到數(shù)值分類學(xué)形成了聚類分析。聚類是將數(shù)據(jù)分類到不同的類或者簇這樣的一個過程，所以同一個簇中的對象有很大的相似性，而不同簇間的對象有很大的相異性。聚類分析的目標(biāo)就是在相似的基礎(chǔ)上收集數(shù)據(jù)來分類。聚類源于很多領(lǐng)域，包括數(shù)學(xué)，計算機(jī)科學(xué)，統(tǒng)計學(xué)，生物學(xué)和經(jīng)濟(jì)學(xué)。在不同的應(yīng)用領(lǐng)域，很多聚類技術(shù)都得到了發(fā)展，這些技術(shù)方法被用作描述數(shù)據(jù)，衡量不同數(shù)據(jù)源間的相似性，以及把數(shù)據(jù)源分類到不同的簇中。

2023/6/162聚類分析的計算方法分裂法(partitioningmethods)層次法(hierarchicalmethods)基于密度的方法(density-basedmethods)基于網(wǎng)格的方法(grid-basedmethods)基于模型的方法(model-basedmethods)

2023/6/163分裂法分裂法又稱劃分方法(PAM:PArtitioningmethod)首先創(chuàng)建k個劃分，k為要創(chuàng)建的劃分個數(shù)；然后利用一個循環(huán)定位技術(shù)通過將對象從一個劃分移到另一個劃分來幫助改善劃分質(zhì)量。典型的劃分方法包括：k-means,k-medoids,CLARA(ClusteringLARgeApplication),CLARANS(ClusteringLargeApplicationbaseduponRANdomizedSearch).FCM2023/6/164層次法層次法(hierarchicalmethod)創(chuàng)建一個層次以分解給定的數(shù)據(jù)集。該方法可以分為自上而下（分解）和自下而上（合并）兩種操作方式。為彌補(bǔ)分解與合并的不足，層次合并經(jīng)常要與其它聚類方法相結(jié)合，如循環(huán)定位。典型的這類方法包括：BIRCH(BalancedIterativeReducingandClusteringusingHierarchies)方法，它首先利用樹的結(jié)構(gòu)對對象集進(jìn)行劃分；然后再利用其它聚類方法對這些聚類進(jìn)行優(yōu)化。CURE(ClusteringUsingREprisentatives)方法，它利用固定數(shù)目代表對象來表示相應(yīng)聚類；然后對各聚類按照指定量（向聚類中心）進(jìn)行收縮。ROCK方法，它利用聚類間的連接進(jìn)行聚類合并。CHEMALOEN方法，它則是在層次聚類時構(gòu)動態(tài)模型。

2023/6/165基于密度的方法

基于密度的方法，根據(jù)密度完成對象的聚類。它根據(jù)對象周圍的密度（如DBSCAN）不斷增長聚類。典型的基于密度方法包括：DBSCAN(Densit-basedSpatialClusteringofApplicationwithNoise):該算法通過不斷生長足夠高密度區(qū)域來進(jìn)行聚類；它能從含有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。此方法將一個聚類定義為一組“密度連接”的點集。OPTICS(OrderingPointsToIdentifytheClusteringStructure):并不明確產(chǎn)生一個聚類，而是為自動交互的聚類分析計算出一個增強(qiáng)聚類順序。2023/6/166基于網(wǎng)格的方法

首先將對象空間劃分為有限個單元以構(gòu)成網(wǎng)格結(jié)構(gòu)；然后利用網(wǎng)格結(jié)構(gòu)完成聚類。典型的基于網(wǎng)格的方法包括：STING(STatisticalINformationGrid)就是一個利用網(wǎng)格單元保存的統(tǒng)計信息進(jìn)行基于網(wǎng)格聚類的方法。CLIQUE(ClusteringInQUEst)和Wave-Cluster則是一個將基于網(wǎng)格與基于密度相結(jié)合的方法。2023/6/167基于模型的方法

典型的基于模型方法包括：統(tǒng)計方法COBWEB:是一個常用的且簡單的增量式概念聚類方法。它的輸入對象是采用符號量（屬性-值）對來加以描述的。采用分類樹的形式來創(chuàng)建一個層次聚類。CLASSIT是COBWEB的另一個版本.。它可以對連續(xù)取值屬性進(jìn)行增量式聚類。它為每個結(jié)點中的每個屬性保存相應(yīng)的連續(xù)正態(tài)分布（均值與方差）；并利用一個改進(jìn)的分類能力描述方法，即不象COBWEB那樣計算離散屬性（取值）和而是對連續(xù)屬性求積分。但是CLASSIT方法也存在與COBWEB類似的問題。因此它們都不適合對大數(shù)據(jù)庫進(jìn)行聚類處理.2023/6/168聚類分析的特征適用于沒有先驗知識的分類可以處理多個變量決定的分類聚類分析法是一種探索性分析方法，是數(shù)據(jù)挖掘中常用的一種技術(shù)2023/6/169例題分析某公司要建兩個配送中心以滿足市場需求，客戶位置分4個地區(qū)。地區(qū)位置及需求量客戶區(qū)域坐標(biāo)位置需求量運輸費用1（3、8）50000.042（8、2）70000.043（2、5）35000.0954（0、4）30000.0952023/6/1610距離相似矩陣2023/6/1611窮舉法基本思想是首先根據(jù)問題的部分條件預(yù)估答案的范圍，然后在此范圍內(nèi)對所有可能的情況進(jìn)行逐一驗證，直到全部情況通過了驗證為止。若某個情況使驗證符合題目的全部條件，則該情況為本題的一個答案；若全部情況驗證結(jié)果均不符合題目的全部條件，則說明該題無答案。2023/6/1612窮舉理論窮舉法，或者稱為蠻力法，是一種直接、簡單的用計算機(jī)解決問題的方法計算機(jī)的產(chǎn)生使得窮舉法有了更多的用武之地。例如，4色問題的證明窮舉法的計算時間性能往往是最低下的窮舉法是基礎(chǔ)；窮舉法可以用于解決某個問題的一個或幾個階段或部分；窮舉法的設(shè)計能夠加深對問題的了解2023/6/1613例題1女兒的年齡三個女兒，年齡之和為13，相乘起來等于你的編號。（只有大女兒上學(xué)）1+1+11(11)1+2+101+3+91+4+81+5+71+6+6(36)2+2+9(36)2+3+8

2+4+72+5+6

3+3+7

3+4+6

3+5+54+4+52023/6/1614例題2新節(jié)點分配方案分配新節(jié)點1新節(jié)點2分配新節(jié)點1新節(jié)點21區(qū)域1區(qū)域2、3、43區(qū)域3區(qū)域1、2、41區(qū)域2區(qū)域1、3、44區(qū)域4