公園內(nèi)道路設(shè)計(jì)問(wèn)題

1、目錄 TOC o 1-5 h z HYPERLINK l bookmark17 o Current Document 問(wèn)題提出1 HYPERLINK l bookmark33 o Current Document 模型假設(shè)2 HYPERLINK l bookmark39 o Current Document 符號(hào)說(shuō)明2 HYPERLINK l bookmark58 o Current Document 模型建立與求解34.1基于Prim算法和 Dijkstra 算法的模型34.1.1模型建立34.1.2模型的求解與優(yōu)化44.2基于改進(jìn)K means 聚類算法的模型74.2.1模型建立74.2.

2、2模型求解94.3回歸優(yōu)化模型104.3.1模型建立104.3.2回歸模型的求解與檢驗(yàn)11 HYPERLINK l bookmark150 o Current Document 模型優(yōu)化125.1距離代價(jià)函數(shù)和距離代價(jià)最小準(zhǔn)則125.2基于距離代價(jià)函數(shù)的空間聚類k值優(yōu)化算法135.3用K - means算法求解聚類中心135.4模型優(yōu)化處理13 HYPERLINK l bookmark181 o Current Document 模型分析與評(píng)價(jià)14 HYPERLINK l bookmark185 o Current Document 參考文獻(xiàn)14附錄1 15附錄2 16附錄3 18問(wèn)題提出西安

3、某大學(xué)計(jì)劃建一個(gè)形狀為矩形或其他不規(guī)則圖形的公園，不僅為了美 化校園環(huán)境，也是想為其學(xué)生提供更好的生活和學(xué)習(xí)條件。在綜合考慮了校園 各地方平均人流量后，公園計(jì)劃有若十個(gè)入口，為了保證公園里人員不過(guò)于擁 擠和出入快捷方便，現(xiàn)在需建立一個(gè)模型去設(shè)計(jì)園內(nèi)道路(可以利用公園四周 的邊，即默認(rèn)矩形的四條邊上存在已經(jīng)建好的道路，此道路不計(jì)入道路總長(zhǎng))， 使任意兩個(gè)入口相連，且總的道路長(zhǎng)度和(這一總長(zhǎng)度可能與成本成正比)最 小，同時(shí)還要滿足任意的兩個(gè)入口間的最短道路長(zhǎng)不大于兩點(diǎn)連線的1.4倍。考慮到不規(guī)則圖形的復(fù)雜性、矩形的特殊性和普適性以及實(shí)際中的公園面 積一般不會(huì)太小等因素，本題主要設(shè)計(jì)對(duì)象可假設(shè)為如圖

4、一所示的矩形公園， 其相關(guān)數(shù)據(jù)為：長(zhǎng)200米，寬100米，1至8號(hào)各入口的坐標(biāo)分別為P1(20,0), P2(50,0), P3(160,0), P4(200,50), P5(120,100),P6(35,100),P7(10,100), P8(0,25)現(xiàn)完成以下問(wèn)題：假定公園內(nèi)確定要使用的4個(gè)道路交叉點(diǎn)為4(50,75), B(40,40), C(120,40), D(115,70).圖二所示即是一種滿足要求的設(shè)計(jì)，但并不是最優(yōu)的，問(wèn)如何設(shè)計(jì)道路可使公園內(nèi)道路的總路程最短。建立數(shù)學(xué)模 型并給出算法。畫出道路設(shè)計(jì)，計(jì)算新修路的總路程。現(xiàn)在公園內(nèi)可以任意修建道路，如何在滿足條件下使總路程最短？

5、建 立模型并給出算法。給出道路交叉點(diǎn)的坐標(biāo)，畫出道路設(shè)計(jì)，計(jì)算新修路的總 路程。若公園內(nèi)有一條矩形的湖，如圖三所示，新修的道路不能通過(guò)，但可 以到達(dá)湖四周的邊，重復(fù)完成問(wèn)題二的任務(wù)。其中矩形湖位置坐標(biāo)為夫1(140,70), R2(140,45), R3(165,45), R4(165,70).注：以上問(wèn)題中都要求公園內(nèi)新修的道路與四周的連接只能與8個(gè)路口相 通，而不能連到四周的其他點(diǎn)。圖二一種可能的道路設(shè)計(jì)圖圖一公園及入口示意圖圖三有湖的示意圖模型假設(shè)設(shè)計(jì)道路只考慮路徑長(zhǎng)短，道路寬度處處相同且不考慮美觀效果。經(jīng)驗(yàn)值具有一定的科學(xué)規(guī)律，可實(shí)施。符號(hào)說(shuō)明C1:記矩形邊框網(wǎng)格線最小距離不大于連線距

6、離1.4倍的無(wú)序點(diǎn)對(duì)為C1類無(wú) 序點(diǎn)對(duì)C2 : P,P,.,P構(gòu)成的所有無(wú)序點(diǎn)對(duì)中除C1類之外的無(wú)序點(diǎn)對(duì)記為C2類無(wú) 128序點(diǎn)對(duì)C :以公園8個(gè)入口 P,P,.,P為頂點(diǎn)的連通圖的鄰接矩陣 128B : P，P,.,4 8個(gè)點(diǎn)中任意兩點(diǎn)沿矩形邊框的最短距離構(gòu)成的矩陣G :有n個(gè)頂點(diǎn)的連通圖T :連通圖的最小生成樹l(i, j):在確定路徑中P,P (i, j = 1,2, .,8)兩點(diǎn)間的道路長(zhǎng)d(i, j):用Dijkstra算法求得的P,P (i, j = 1,2, .,8)兩點(diǎn)最短路徑的道路長(zhǎng) i jw(i, j): P,P (i, j = 1,2,.,8)兩點(diǎn)間的直線距離x :將8個(gè)

7、入口點(diǎn)兩兩相連得到的交點(diǎn)(端點(diǎn)不算)記作X = x , X., x k :將X = %,X2 .,x 中的n個(gè)空間對(duì)象聚類為k類(簇)Q : X = x1, %., xn 的所有聚類結(jié)果構(gòu)成的集合p :空間中的任意一點(diǎn)，即X = x1, %., xn 中的樣本點(diǎn)Ct : K-means算法求得的聚類數(shù)k下的類(簇)m :簇Ct,所含樣本的均值 m :全部樣本的均值模型建立與求解4. 1基于Pr im算法和 Dijkstra 算法的模型4. 1.1模型建立因?yàn)楣珗@四周邊上已經(jīng)建好的道路不計(jì)入道路總長(zhǎng)，要想園內(nèi)道路總路程 最短，應(yīng)盡可能利用矩形邊框道路。由于C1類無(wú)序點(diǎn)對(duì)滿足邊框最短距離不大 于1

8、.4倍連線距離，所以C1無(wú)序點(diǎn)對(duì)對(duì)應(yīng)的入口可以通過(guò)公園邊上道路連通， 在進(jìn)行道路設(shè)計(jì)時(shí)不予考慮；對(duì)C 2類無(wú)序點(diǎn)對(duì)，可以將相關(guān)點(diǎn)連成連通圖，通 過(guò)Prim算法得出相應(yīng)的最小生成樹，再通過(guò)Dijkstra算法得到這些無(wú)序點(diǎn)對(duì)的 最短路徑，最后檢驗(yàn)驗(yàn)證方案設(shè)計(jì)是否符合要求，若方案不合理，則需修改優(yōu) 化模型，直到得到符合條件的最佳道路設(shè)計(jì)方案為止。（I）確定C1,C2類無(wú)序點(diǎn)對(duì)根據(jù)圖一坐標(biāo)得到以公園8個(gè)入口 P,P, ,P為頂點(diǎn)的連通圖的鄰接矩陣 TOC o 1-5 h z 128C以及這8個(gè)點(diǎn)中任意兩點(diǎn)沿矩形邊框的最短距離構(gòu)成的矩陣B。進(jìn)行矩陣運(yùn)M = 1.4C - B對(duì)矩陣元素進(jìn)行分析，當(dāng)m 0

9、時(shí)，1.4c b，即P,P兩點(diǎn)的矩形邊框距 、 .j 一 j i j .離不大于兩點(diǎn)連線的距離的1.4倍，P,P構(gòu)成的無(wú)序點(diǎn)對(duì)屬于C1類無(wú)序點(diǎn)對(duì)， 在設(shè)計(jì)道路時(shí)，不需考慮這兩點(diǎn)對(duì)應(yīng)入口的道路連接問(wèn)題；當(dāng)m 1.4b礦 i, j = 1,2,3,5,6,7成立，說(shuō)明圖四中相應(yīng)的連線不符合要求，需要將結(jié)果進(jìn)行修改優(yōu)化。綜合考 慮所有無(wú)序點(diǎn)對(duì)間的最短道路長(zhǎng)和最短道路總長(zhǎng)，在已經(jīng)連接好的路線不做太 大改變的前提下，將不合理的路線進(jìn)行適當(dāng)?shù)男薷膬?yōu)化，直到所有路線都滿足 要求且道路總長(zhǎng)最小為止。4.1.2模型的求解與優(yōu)化（I）根據(jù)圖一坐標(biāo)得到以公園8個(gè)入口 P,P,.,P為頂點(diǎn)的連通圖的鄰接 128矩陣-

10、042.0000 196.0000 261.5416 197.9899 141.5662 140.6983 44.8219142.00000154.0000 221.3594 170.8918 141.5662 150.7846 78.2624196.0000 154.0000089.6437 150.7846 224.1093 252.3886 226.7179261.5416 221.3594 89.64370132.0757 241.3732 275.0564 282.179（C=197.9899 170.8918 150.7846 132.07570119.0000 154.0000

11、198.1136141.5662 141.5662 224.1093241.3732119.0000035.0000115.8706140.6983 150.7846 252.3886275.0564154.000035.00000105.929244.8219 78.2624 226.7179282.1790198.1136115.8706105.92920 p, P,., P8這8個(gè)點(diǎn)中任意兩點(diǎn)沿矩形邊框的最短距離構(gòu)成的矩陣一 03014023024015513045 一30011020027018516075140110090220295270185B =2302009001302152

12、402752402702201300851101951551852952158502511013016027024011025085_ 4575185275195110850 _進(jìn)行矩陣運(yùn)算M =1.4C -B后,得到的矩陣一 012.000056.000031.5416 -42.0101 -13.433810.6983-0.178112.0000044.000021.3594 -99.1082 -43.4338-9.21543.262456.000044.00000-0.3563-69.2154 -70.8907 -17.6114 41.717931.541621.3594-0.356302

13、.075726.373235.05647.1790M =-42.0101 -99.1082 -69.21542.0757034.000044.00005.8706-13.4338 -43.4338 -70.8907 26.373234.0000010.00005.870610.6983-9.2154-17.6114 35.056444.000010.0000020.9292-0.17813.262441.71797.17903.11365.870620.92920 _當(dāng)m 0時(shí)，點(diǎn)(i, j)屬于C1類無(wú)序點(diǎn)對(duì)；當(dāng)m 0時(shí)，點(diǎn)(i, j)屬于C2類無(wú)序 點(diǎn)對(duì)。由矩陣M的輸出結(jié)果知，C2類無(wú)序點(diǎn)

14、對(duì)有(1,5),(1,6),(1,8),(2,5),(2,6),(2,7),(3,4),(3,5),(3,6),(3,7)，其他無(wú)序點(diǎn)對(duì)均為 C1 類無(wú)序點(diǎn)對(duì)。用Prim算法和Dijkstra算法對(duì)C2類無(wú)序點(diǎn)對(duì)進(jìn)行處理 TOC o 1-5 h z 經(jīng)觀察分析，在所有C2類無(wú)序點(diǎn)對(duì)中，p,P均只在一對(duì)無(wú)序點(diǎn)對(duì)中出現(xiàn)， 所以優(yōu)先單獨(dú)分析(1，8)和(3, 4)。4 8在圖二所示的道路設(shè)計(jì)坐標(biāo)圖中可以看出，P, P經(jīng)過(guò)其他任意點(diǎn)間接連接起來(lái)的路程l (1,8)滿足不等關(guān)系1 8l(1,8) 、 1.4%同理有，l(3,4) 、 1.4c34所以，P,P和P,P對(duì)應(yīng)的兩對(duì)入口必須分別直接連通。 18

15、34余下未處理的 C2 類無(wú)序點(diǎn)對(duì)有(1,5), (1,6), (2, 5), (2, 6), (2, 7), (3, 5),印6 7)，將與上述無(wú)序點(diǎn)對(duì)的連接有關(guān)的點(diǎn)(P,P,P,P,P,P,P,&B,C,D)兩兩連接，1235678對(duì)得到的連通圖G用Prim算法得到相應(yīng)的最小生成樹T。算法運(yùn)行后輸出的最小生成樹T如下圖四所示：圖四最小生成樹由于最小生成樹只保證了 C2類無(wú)序點(diǎn)對(duì)連接總路程最短，并不一定滿足無(wú) 序點(diǎn)對(duì)對(duì)應(yīng)的入口之間的道路長(zhǎng)不大于兩點(diǎn)連線距離的1.4倍，所以需要檢驗(yàn)。用Dijkstra算法對(duì)模型進(jìn)行修改優(yōu)化并檢驗(yàn)?zāi)Ｐ偷目尚行詢?yōu)化一：經(jīng)Dijkstra算法計(jì)算得到，p,P5兩點(diǎn)間

16、的最短路徑為P IP IBIAIDIP，但最短道路長(zhǎng)d(1,5)1.4。，所以該路徑不可取。 TOC o 1-5 h z 18515在道路總長(zhǎng)最小的前提下，為減少入口2和入口5間的道路長(zhǎng)，可以將上述路徑優(yōu)化為P IP IBIAIP。125優(yōu)化二：通過(guò)觀察，在連通入口 7的道路中，AIP段可以優(yōu)化，可以先7假設(shè)優(yōu)化模型再驗(yàn)證檢驗(yàn)假設(shè)的合理性。假設(shè)該段道路可以用AIP IP優(yōu) 化代替，即在優(yōu)化模型中去掉A I P段，用Dijkstra算法可以求出：點(diǎn)到其他 各點(diǎn)的最短路徑和最短距離，計(jì)算結(jié)7果均滿足不等關(guān)系7d (7, j) 8 d ,（8go.5,1），則x.（i = s或t）為第三個(gè)聚類中心，

17、類別數(shù)K = K +1 ;否則算法結(jié)束（6）重復(fù)（3）（5）根據(jù)已經(jīng)設(shè)定的聚類數(shù)k = 2，運(yùn)用K - means算法求出聚類數(shù)2下的聚類 中心。（III）以聚類中心為道路交叉點(diǎn)設(shè)計(jì)最佳道路空間聚類一般使用距離作為劃分準(zhǔn)則，即任一空間對(duì)象與該對(duì)象所屬簇的 幾何中心之間的距離比該對(duì)象到任何其他簇的幾何中心的距離都小，所以，上步中得到的聚類中心可以作為公園道路規(guī)劃時(shí)園內(nèi)交叉路口。在確定了道路交 叉點(diǎn)的個(gè)數(shù)和位置后，我們可以套用問(wèn)題一的模型來(lái)設(shè)計(jì)最優(yōu)道路方案。4.2.2模型求解輸入P,P,.,P各點(diǎn)的坐標(biāo)，運(yùn)用算法1得到兩兩連線交點(diǎn)，輸出結(jié)果128如下圖六所示：10090807060 50 40 3

18、0 20 10020406080100120140160180200圖六入口兩兩連線示意圖重合的交點(diǎn)不計(jì)算在內(nèi)，一共得到68個(gè)交點(diǎn)，用x (i = 1,2, .,68)表示各交 點(diǎn)，交點(diǎn)坐標(biāo)的輸出結(jié)果見附錄2ik -means算法求解聚類中心記A = x ,x，,x,.,x (i = 1,2,.,68)為樣本空間，由經(jīng)驗(yàn)準(zhǔn)則給定聚類12 i 68數(shù)k = 2,用K -means算法求出聚類數(shù)k = 2下的聚類空間。運(yùn)行結(jié)束時(shí)輸出k = 2時(shí)的聚類空間，將求得的兩個(gè)中心分別記為S，計(jì)算結(jié)果為S1 = (172,42), S2 = (60,77)以聚類中心為道路交叉點(diǎn)設(shè)計(jì)最佳道路以S = (172

19、,42),S = (60,77)為道路交叉點(diǎn)設(shè)計(jì)道路使道路總長(zhǎng)最短，可以 套用問(wèn)題一中的模型，2最后輸出結(jié)果如下圖六所示：圖六以聚類中心為交叉點(diǎn)的道路設(shè)計(jì)經(jīng)計(jì)算，新修道路總長(zhǎng)為358.6米。4.3回歸優(yōu)化模型4.3.1模型建立問(wèn)題三相對(duì)于問(wèn)題二只是多了矩形湖的限制，可以在做盡量少的改變的前 提下優(yōu)先優(yōu)化經(jīng)過(guò)湖面區(qū)域的路徑，再對(duì)優(yōu)化后的模型進(jìn)行檢驗(yàn)驗(yàn)證。(I)回歸模型建立由問(wèn)題二的設(shè)計(jì)方案知，只有路徑S1P5經(jīng)過(guò)了湖面區(qū)域，所以首先對(duì) 該路徑進(jìn)行優(yōu)化，另外找一合適的點(diǎn) ,使得路徑S 一P不經(jīng)過(guò)湖面區(qū)域且改 變的路徑P 一 S 一P最短，為尋找這一S點(diǎn)建立如下回歸模型：3353設(shè)S;= (a,b)

20、， S1= (S3 ,S3 ) = (172,42),目標(biāo)函數(shù)為y =、；(a -120)2 + (b -100)2 ;(a - S3)2 + (b - S3)2代入數(shù)據(jù)，于是，目標(biāo)函數(shù)可簡(jiǎn)化為y =、J(a -120)2 + (b -100)2 + (a -172)2 + (b - 42)2 其中a,b滿足以下約束條件：kS3 R3 -七 R kS3 S1S3 S1a 200, b 4a 200, b 100于是，求解路徑P3s S3 -弓的最短路徑問(wèn)題轉(zhuǎn)化為求目標(biāo)函數(shù) y =、：(a 120)2 +(b 100)2 +、a -172)2 +(b - 42)2在上述約束條件確定的可行域里何處

21、取最小值的問(wèn)題，該回歸模型通過(guò)Lingo 求解，結(jié)果輸出就是我們要找的點(diǎn)S3。(II)模型檢驗(yàn)在確定S3點(diǎn)后，我們還需要進(jìn)行檢驗(yàn)，驗(yàn)證優(yōu)化模型中任意兩點(diǎn)間的最短 道路距離是否都不大于兩點(diǎn)連線距離的1.4倍，用Dijkstra算法(算法說(shuō)明問(wèn)題 一中已經(jīng)給出)可完成檢驗(yàn)過(guò)程。若經(jīng)驗(yàn)證模型符合1.4倍的要求，則模型可取; 若經(jīng)驗(yàn)證模型不符合1.4倍的要求，則需進(jìn)一步優(yōu)化，此時(shí)，需綜合考慮路徑最 短距離和道路總路程最短，在盡量少地改動(dòng)符合條件的路線的前提下，將不符 合條件的路線修改優(yōu)化，直到模型檢驗(yàn)結(jié)果符合要求為止。4.3.2回歸模型求解與檢驗(yàn)將上述建立的回歸模型在Lingo中運(yùn)行，運(yùn)行結(jié)果為a =

22、 165,b = 70，即R4 點(diǎn)，此時(shí)道路設(shè)計(jì)如下圖七所示：對(duì)圖七所示連通圖用Dijkstra算法求得任意兩點(diǎn)間的最短路徑和最短距離， 經(jīng)計(jì)算，任意兩點(diǎn)間的最短路徑距離均不大于連線距離的L4倍，這說(shuō)明該設(shè)計(jì) 方案是合理的。又由于在回歸模型中，求解的是最小值且其他路線的連接情況 并未改變，所以該設(shè)計(jì)方案也是最佳的。經(jīng)計(jì)算，新修道路總長(zhǎng)為361.7米。模型優(yōu)化由于典型的K - means算法是在k準(zhǔn)確給定的條件下實(shí)現(xiàn)的，所以要先算出 最優(yōu)的聚類k值，本題借用距離代價(jià)函數(shù)和距離代價(jià)最小準(zhǔn)則求解最佳聚類數(shù)k， 該方法對(duì)實(shí)際問(wèn)題具有一定的合理性。5.1距離代價(jià)函數(shù)和距離代價(jià)最小準(zhǔn)則一個(gè)好的聚類應(yīng)該使聚

23、類中心的間距盡可能大，而樣本中心間距盡可能地，小。令K = X,耕為空間聚類的聚類空間，其中X = %,x2,x ，假設(shè)n個(gè) 空間對(duì)象被聚類為k個(gè)簇，現(xiàn)做如下定義：1 2，n（1）類際距離為所有聚類中心（簇內(nèi)樣本的均值）到全域中心（全體樣本 的均值）的距離之和L =丈 m - mi=1式中，L為類際距離，m為全部樣本的均值，m,為簇。，所含樣本的均值， k值為所要聚類的個(gè)數(shù)。（2）類內(nèi)距離為所有聚類簇內(nèi)部距離的總和，其中，每個(gè)簇的內(nèi)部距離為 該簇內(nèi)所有樣本到其中心的距離之和D = |p m|ii=1 pcCt.式中，D為類內(nèi)距離，p為任意空間對(duì)象及樣本點(diǎn)，1,m,Ct,k含義與上 式含義相同。

24、（3）距離代價(jià)函數(shù)為類際距離與類內(nèi)距離之和F (S, k) = L + D = |i = 1|m.-m| + i=1 peCt i式中，F(xiàn)（S,k）為距離代價(jià)函數(shù)，其他符號(hào)含義與上二式相同。在運(yùn)用距離代價(jià)函數(shù)作為空間聚類有效性檢驗(yàn)函數(shù)時(shí)，我們運(yùn)用距離代價(jià) 最小準(zhǔn)則，即當(dāng)距離代價(jià)函數(shù)取得最小值時(shí)，空間聚類結(jié)果為最優(yōu)，k的最優(yōu) 選擇由下式給出：min（F （S, k）, k = 1,2,., n5.2基于距離代價(jià)函數(shù)的空間聚類k值優(yōu)化算法距離代價(jià)最小準(zhǔn)則雖然能夠求出最優(yōu)聚類數(shù)，但在樣本點(diǎn)偏多時(shí)k的取值 范圍偏大，計(jì)算量過(guò)大。我們可以通過(guò)經(jīng)驗(yàn)規(guī)則k Jn （n為所有樣本點(diǎn)個(gè)數(shù)）縮小最優(yōu)解范圍，這樣便

25、能大大降低計(jì)算量。于是，空間聚類k值優(yōu)化算法過(guò) 程如下：k值優(yōu)化算法:在K -means算法基礎(chǔ)上，通過(guò)距離代價(jià)函數(shù)優(yōu)化k值輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫(kù)輸出：距離代價(jià)函數(shù)最小條件下的k*個(gè)簇步驟：（1）根據(jù)經(jīng)驗(yàn)規(guī)則計(jì)算和確定最優(yōu)解的上界k 品。（2）用K-means算法實(shí)現(xiàn)k 卻所有數(shù)目下的空間聚類。（3）根據(jù)距離代價(jià)函數(shù)分別計(jì)算不同聚類數(shù)目k下的F（S,k）值。（4）搜尋距離代價(jià)函數(shù)最小的F（S,k），并記下相應(yīng)的k*值。（5）結(jié)束。5.3用K-means算法求解聚類中心上一步中已經(jīng)得出最優(yōu)聚類數(shù)k*，從全體樣本點(diǎn)中隨機(jī)選擇k*個(gè)對(duì)象（樣本），每個(gè)對(duì)象成為一個(gè)種子，代表一個(gè)簇（類）的均值或中心

26、，對(duì)剩余的每 個(gè)對(duì)象，根據(jù)其與各簇中心的距離將它賦給最近的簇，然后重新計(jì)算每個(gè)簇內(nèi) 對(duì)象的平均值形成的新的聚類中心，將這個(gè)過(guò)程重復(fù)進(jìn)行，直到準(zhǔn)則函數(shù)E = |p - m |2i=1 pCtj收斂為止。式中，E是所有研究對(duì)象的平方誤差和，p為空間任意一點(diǎn)，即數(shù)據(jù)對(duì)象，m,為簇Ct,所含樣本的均值，按照這個(gè)準(zhǔn)則生成的結(jié)果簇趨向于獨(dú)立和緊湊。5.4模型優(yōu)化處理記A = x ,x，,心,x （i = 1,2, .,68）為樣本空間，由經(jīng)驗(yàn)準(zhǔn)則知，聚類12 i 68數(shù)k滿足不等關(guān)系k n（n = 68），因?yàn)閗為整數(shù)，所以其可能取值為1,2,.,8，記k = i（i = 1,2,.,8），用K-mean

27、s算法求出聚類數(shù)k下的聚類空間，再求出相應(yīng)的距離代價(jià)函數(shù)F（S,k ），計(jì)算結(jié)果如下：,iK12345F3305.332351.171914.751767.381402.67cluster 1 cluster cluster 3 rlusterd cluster h圖八聚類優(yōu)化分析圖模型分析和評(píng)價(jià)問(wèn)題一中求連通圖的最小生成樹時(shí)既可用Pr im算法也可用Kruskal算法， 但前者具有更高的效率，且算法易拓展，所以本題中用的是Prim算法。問(wèn)題二用到了傳統(tǒng)的K-means算法，它是一種比較簡(jiǎn)潔和快速的聚類算法， 但它是在給定類別數(shù)k的情況下對(duì)樣本實(shí)現(xiàn)類別劃分的一種方法。事實(shí)上，在 很多時(shí)候并不知

28、道事先將數(shù)據(jù)集分成多少個(gè)類別才最合適，所以剛開始的k的 值具有一定的主觀性，模型不是最好的模型，又由于它的優(yōu)化空間不大，可以 大大減少計(jì)算量，所以這個(gè)算法有可取點(diǎn)也有不可取點(diǎn)，應(yīng)視具體問(wèn)題具體分 析使用。參考文獻(xiàn)1楊善林，李永森，胡笑旋，潘若愚，K-means算法中的k值優(yōu)化問(wèn)題， 系統(tǒng)工程理論與研究，2006年2月第2期，1-5楊會(huì)鋒，曹潔，帥立國(guó)，基于改進(jìn)K-均值聚類算法的背景建模方法，電 子測(cè)量與儀器學(xué)報(bào)，2010年12月 第24卷第12期，1115-1116function T c=Primf(a) l=length(a);a(a=0)=inf;k=1:l;listV(k)=0;lis

29、tV(1)=1;e=1;while (ea(i,j) min = a(i,j);b=a(i,j); s=i;d=j;endendendendlistV(d)=1;distance(e)=b;source(e)=s;destination(e)=d;e=e+1;endT=source;destination;for g=1:e-1c(g)=a(T(1,g),T(2,g);endc;sample=0 2510 10014.4117647116.4705882417.2839506217.7777777818.4210526320 021.5384615455.8823529435.29411765

30、27.1604938322.2222222215.78947368 71.1538461522.09302326 13.95348837 23.20610687 21.3740458 24.20382166 28.0254777126.20689655 41.3793103428.18181818 54.54545455 29.06779661 87.28813559 30 1032 4532.265625 94.14062532.72727273 84.8484848534.05063291 93.67088608 35 10036.02739726 93.1506849337.777777

31、78 81.48148148 38.0952381 29.76190476 38.91891892 18.918918925.35714285721.4285714351.4285714342.66666667 18.3333333345.39877301 30.67484663 46.08695652 26.08695652 47 7.547.25490196 90.1960784347.36 17.648.8 850 031.4285714357.24137931 10.3448275960.84507042 15.49295775 63.22580645 64.51612903 70.4

32、 1472.28070175 70.175438673.97260274 34.24657534 76 5682.22222222 62.22222222 85 5085.10638298 11.7021276687.40740741 79.6296296389.48717949 56.4102564192.24489796 82.65306122 97.08333333 77.08333333 100.2325581 80.23255814 102.8888889 75.55555556 103.1578947 37.89473684 105.125 78.75111.3513514 38.

33、91891892118.8235294 27.45098039 120 100123.3333333 24.44444444123.9175258 28.86597938127.6470588 25.88235294131.7241379 70.68965517 132.9411765 67.64705882 142.8571429 42.85714286146 35147.0588235 32.35294118 160 0200 50;%Kmeans聚類函數(shù)function D,L,cluster_center=kmeans(k) load dotdist=;sample=result;dingdian=;% 頂點(diǎn)確定%畫出所有點(diǎn)figure;hold onfor i=1:size(sample,1)plot(sample(i,1),sample(i,2),k*)end%中心點(diǎn)x_mean=mean(result(:,1),mean(result(:,2)d=abs2(sample,x_mean);din