柳景青，郭東進，葉 萍

（1.浙江大學 建筑工程學院市政工程研究所 浙江 杭州310058；2.嘉源給排水有限公司 浙江 嘉興314000）

城市給水管網由水廠、泵站、節(jié)點、閘閥、監(jiān)測設備等組成，是一個十分復雜的系統(tǒng).給水管網節(jié)點指的是給水管網中，主干管、干管、支管之間，相互交叉連接的節(jié)點，目前給水管網模型一般考慮管徑200 mm 以上的管道，管徑200 mm 以下管道由于流量較小，一般不考慮.一個中等城市，管徑在200 mm以上的管網系統(tǒng)可能有上千個節(jié)點，因此，從計算分析的角度，需要以聚類為基礎的簡化.數量之外，城市給水管網節(jié)點系統(tǒng)同時又是一個復雜的關聯體系，節(jié)點與節(jié)點之間既相對獨立又相互影響.因此，它們不是簡單空間位置、空間距離劃分的聚類，需要綜合考慮節(jié)點屬性功能的響應及重要性，問題復雜.

在K 均值聚類法之前，處理類似的給水管網節(jié)點空間聚類問題，常用系統(tǒng)聚類法.王旭冕等［1］利用三步分析法篩選水質指標，利用系統(tǒng)聚類方法，對管網節(jié)點進行聚類，實現水質分區(qū).李雅潔等［2］采用系統(tǒng)聚類中的類平均法對給水管網節(jié)點聚類，并利用離均差從各類中篩選出代表點.程廣河等［3］計算了管網壓力敏感矩陣，利用系統(tǒng)聚類的方法，建立城市給水管網水量漏失點定位模型.Lina 等［4］利用深度優(yōu)先搜索算法（DFS）和寬度優(yōu)先搜索算法（BFS）搜索的方法進行給水管網聚類，實現給水管網簡化.上述給水管網節(jié)點聚類的研究是基于簡單的管網中試模型，以管網模型的節(jié)點壓力敏感矩陣作為聚類的指標.在實際給水管網中，由于管網結構復雜，壓力受到多種原因影響，無法得到可靠的節(jié)點壓力敏感矩陣［5］.賈新強等［6-7］的研究證明，給水管網節(jié)點相似性除受到壓力變化規(guī)律影響外，還受到地理位置的影響.因此，在選擇節(jié)點聚類方法時，應能同時考慮空間的相近性和非空間屬性的相似性.

相比于系統(tǒng)聚類，K 均值空間聚類因為能夠同時反映地理位置與壓力的相似性，更適合用于實際給水管網節(jié)點的聚類分析.戴一明等［8］在管網水壓監(jiān)測點優(yōu)化布置研究中對監(jiān)測點進行了K 均值空間聚類嘗試，選取離聚類中心最近的點作為水壓監(jiān)測點.在實際應用研究過程中，研究者發(fā)現普通K均值空間聚類方法結果往往很大程度上依賴于初始聚類中心的選取和屬性權重的選取，存在類內誤差過大和聚類結果不穩(wěn)定等諸多問題［9］，本文引入信息熵和改進遺傳算法，試圖克服以上K 均值空間聚類方法的不足.

1 改進的K 均值空間聚類算法

1.1 管網節(jié)點K 均值空間聚類算法

在K 均值聚類分析中，表示兩點之間的差距一般采用歐氏距離，距離越近，相似度越大.普通K 均值聚類分析一般有一個屬性，或者有幾個屬性但類型、量綱相同，因此在計算聚類簇內距離的時候無需設置權重，簡單疊加即可.

對于同時包含空間屬性和非空間屬性的給水管網節(jié)點的類問題，2個節(jié)點之間的“距離”需要能夠同時反映出空間距離和壓力變化規(guī)律的相似性，因此需要設置屬性權重，建立新的節(jié)點距離計算公式.本文在李新運等［10］提出的坐標與屬性一體化的空間聚類方法的基礎上，考慮非空間屬性中實際節(jié)點壓力與模擬節(jié)點壓力在誤差精度上的差異（一般相差5倍以上），引入節(jié)點置信系數，定義了給水管網節(jié)點距離.

假設給水管網中存在i，j2個節(jié)點：

式中：Dij為兩節(jié)點之間的距離；x、y 為節(jié)點平面坐標，坐標值由自來水公司提供；wx、wy為平面坐標權重，權重值由信息熵方法計算求得；a 為非空間屬性值，本文選擇壓力均值和峰度系數表示非空間屬性；wk為第k 個非空間屬性權重，權重值由信息熵方法計算求得；?為節(jié)點的置信系數，置信系數根據經驗取值.實際監(jiān)測節(jié)點壓力值誤差在2%以內，而水力模擬節(jié)點的壓力值誤差在10%以內.因此，本文設置當節(jié)點為實際監(jiān)測節(jié)點時，?＝1當節(jié)點為水力模擬節(jié)點時?＝0.5.

K 均值空間聚類過程為：首先隨機選擇聚類中心，計算得到點與聚類中心的之間的聚類距離后，逐個將需分類的樣本按最近距離分配給某一個聚類中心Ci，所有樣本分成k 個聚類簇，每一個聚類簇中至少有一個以上的樣本.重新計算各個聚類簇的聚類中心，以各聚類域中所包含樣本的均值向量作為新的聚類中心.直到每個聚類簇不再發(fā)生變化.

1.2 基于自適應遺傳算法的初始聚類中心尋優(yōu)模型

K 均值聚類方法的初始聚類中心對于聚類結果有很大影響，普通K 均值聚類的初始聚類中心是隨機生成的，因此聚類結果隨機性很強.對于給水管網而言，節(jié)點數量眾多，因此需要選擇合適的優(yōu)化方法來確定最優(yōu)的初始聚類中心.

遺傳算法的優(yōu)點是全局搜索能力強，計算時間少，魯棒性高.武兆慧等［11］將遺傳算法引入K 均值聚類，尋找最優(yōu)初始聚類中心，證明遺傳算法能夠較好的實現尋優(yōu)功能.本文利用自適應遺傳算子和精英保留策略的遺傳算法優(yōu)化一體化K 均值聚類，同時將其與采用經典遺傳算法、模擬退火遺傳算法優(yōu)化的K 均值空間聚類結果進行對比.

將遺傳算法應用于K 均值空間聚類優(yōu)化，需要根據聚類結果評價指標，構造合適的目標函數.本文選擇聚類簇類內距離之和作為目標函數值.

式中：k為聚類簇個數，n為類內節(jié)點個數，Dij為第i類第j 個個體與聚類中心的距離.

為了保證每個聚類簇中節(jié)點個數處于相同水平，需要在目標函數中增加懲罰項.新構造的目標函數為

式中：r為懲罰因子；σn為聚類簇個數均方差.

K 均值聚類需要設置聚類簇個數，至少為1；同時，任一聚類簇中至少有1個個體，所以，目標函數約束條件為

為了區(qū)分每個初始聚類中心的優(yōu)劣程度，需要在目標函數的基礎上構造適應度函數，計算得到每一個聚類中心的適應度函數值，以此作為評價標準.本文采用目標函數值的倒數構造適應度函數：

式中：F 為構造適應度函數常數，本文根據經驗，取100；Dis為目標函數值，即所有聚類簇內距離之和.

1.3 權重確定的信息熵算法

K 均值空間聚類屬于加權聚類.加權聚類的關鍵是權重的確定.目前常用的權重確定方法是經驗法或專家評分法［12］.2種方法的主觀性很強，不能準確反應屬性之間的真實權重.并且給水管網節(jié)點數量多，采用經驗法或專家評分法操作復雜，在實際管網分析中難以實施.

自1948年shannon等［13］提出信息理論以來，信息熵理論得到了得到了廣泛應用，是確定權重的重要手段之一［14-16］.信息熵法是基于客觀數據的確定權重方法.

本文利用信息熵原理，確定給水管網節(jié)點空間與非空間屬性權重，以克服權重確定主觀性強、操作性差的缺陷，信息熵方法計算權重的過程為

計算歸一化屬性矩陣：

式中：aij為第i個屬性第j 個對象的屬性值；a′ij為歸一化后屬性值.

計算第i個屬性的信息熵：

式中：Ej為第j個屬性信息熵值；g為聚類對象個數.定義屬性j對于方案的區(qū)分度：

式中：Fj為屬性j 的區(qū)分度.

式中：wj為屬性j 的權重.

1.4 管網節(jié)點空間聚類的改進算法步驟

結合自適應-精英保留策略遺傳算法和信息熵的K 均值空間聚類計算過程如圖1所示.

圖1 改進的K 均值空間聚類模型框架Fig.1 Framework of K-means spatial clustering combined with adaptive-elitist genetic algorithm and entropy model

2 實例分析

2.1 指標選擇

選擇華東某中等城市給水管網作為研究對象，給水管網給水服務范圍30km2.其中在線壓力監(jiān)測節(jié)點40個，在線壓力監(jiān)測數據來自于自來水公司的管網綜合管理系統(tǒng)，可以得到120h的節(jié)點壓力歷史數據，數據采樣間隔為5min，壓力監(jiān)測設備采樣精度2%以內.其他管網節(jié)點的壓力值，通過自來水公司已建立的在線管網水力模型模擬得到，誤差精度在10%以內.在線壓力監(jiān)測節(jié)點空間屬性由坐標表示，坐標由自來水管公司提供.簡化后的管網系統(tǒng)圖如圖2所示.

圖2 給水管網模型Fig.2 Water distribution system model

給水管網的節(jié)點壓力值分布在一均值附近，需要利用統(tǒng)計分析的手段描述壓力的變化規(guī)律.常用的分布統(tǒng)計指標有均值、標準差、偏態(tài)系數、峰度等.

壓力均值代表每個節(jié)點壓力的平均水平，但僅靠均值無法描述管網節(jié)點的壓力變化規(guī)律，所以還需要選擇其他的統(tǒng)計指標.

峰度是表征概率密度分布曲線在平均值處峰值高低的特征數.在相同的標準差下，峰度越大，其分布就更加陡峭.根據節(jié)點壓力的變化規(guī)律，2個節(jié)點壓力的均值、標準差、偏態(tài)系數有可能很接近，峰度反映節(jié)點壓力頂端尖峭或扁平程度的指標，能夠反映征節(jié)點壓力分布的獨特特征，所以選擇峰度系數作為管網節(jié)點.

選擇管網節(jié)點的X、Y 坐標值，壓力均值pZ與峰度系數Kc（Kurtosis Coefficient）作為管網節(jié)點屬性；選擇算法消耗時間te（Elapsed Time）、迭代次數S、類內距離Dc（Class Distance）以及各算法迭代結果類內距離的均值AVG、標準差SD（Means、Standard Deviation of 5Iterations Results）作為聚類結果的評價指標，如表1所示為部分節(jié)點屬性.

表1 節(jié)點坐標與非空間屬性Tab.1 nodes’coordinates and non-spatial attributes

2.2 實驗結果

本文設計了4種算法，分別為：1）普通K 均值空間聚類（K average spatial clustering）；2）GAK 均值 空 間 聚 類（genetic algorithm k average spatial clustering），經典遺傳算法K 均值空間聚類（3）AEGAKK 均 值 空 間 聚 類（adaptive elitist genetic algorithm k average spatial clustering），自適應精英保留策略遺傳算法K 均值空間聚類；4）SAGAK 均值空間聚類（simulated annealing genetic algorithm k average spatial clustering），模擬退火遺傳算法K均值空間聚類.

經過實例驗證，從聚類精度、消耗時間、迭代次數3 個方面對比分析4 種算法的性能，結果表明AEGAK 均值空間聚類性能較其他3種方法更優(yōu).

另外，為了證明信息熵確定權重的可行性，將AEGAK 均值空間聚類方法中，經過信息熵方法計算得到的權重替換為平均權重，并將2種權重確定方法進行對比.

圖3 AEGAK 均值空間聚類過程Fig.3 AEGAK-average spatial clustering

表2 4種空間聚類方法性能對比Tab.2 Contradistinction of four spatial clustering methods'performance

如圖3所示為AEGAK 均值空間聚類計算過程.如表2所示為4種聚類算法的結果，類內距離表示所有聚類簇的類內距離之和.如表3所示為信息熵方法主觀確定權重方法計算得到的屬性權重值.如圖4、5 所示分別為2 種權重計算方法下，AEGAK 均值空間聚類得到的聚類結果，聚類簇分為8類，數字1-8表示節(jié)點所屬類別.

表3 2種方法權重對比Tab.3 Contradistinction of weights determined by two different methods

圖4 信息熵確定權重的AEGAK 均值空間聚類結果Fig.4 Results of AEGAK-means spatial clustering with entropy-defined weights

圖5 平均權重的AEGAK 均值空間聚類結果Fig.5 Results of AEGAK-means spatial clustering with average weights

1）比較初始聚類中心優(yōu)化方法.

4種聚類方法的類內距離：普通空間K 均值聚類方法類內距離均值最大，效果最差，其他3種經過優(yōu)化后的聚類方法得到的結果基本保持在同一水平.

4種聚類方法的穩(wěn)定性：AEGAK 均值空間聚類類內距離標準差最小為0，相對其他3種方法最穩(wěn)定.其他3種方法，SAGAK均值空間聚類優(yōu)于GA K 均值空間聚類，普通均值空間聚類穩(wěn)定性最差.

4種聚類方法消耗的時間：普通空間K 均值聚類方法基本不需要消耗時間，AEGAK 均值空間聚類消耗時間比GAK 均值空間聚類少，SAGAK 均值空間聚類消耗時間最長.

分別分析4個程序本身的特點，造成以上結果的原因是：

1）普通空間K 均值聚類結果受到初始聚類中心的選取影響較大，空間K 均值聚類結果具有一定的隨機性，難以得到最優(yōu)的聚類結果.相反，經過優(yōu)化后的聚類算法得到了“最優(yōu)”初始聚類中心，因此能夠得到較好的聚類結果.2）經典GA 算法整體搜索性強，但是容易陷入局部最優(yōu)解，因此，在相同的終止條件下，得到的最終結果隨機型強，并且可能需要消耗大量的時間跳出局部最優(yōu)解.3）SAGAK 均值空間聚類中，模擬退火部分雖然能夠保證算法可以跳出局部最優(yōu)解，但是卻增加了計算的復雜度.4）AEGAK 均值空間聚類方法在迭代初始，設置較大的變異概率比，從而能夠保證算法跳出局部最優(yōu)解，同時采用精英保留策略，可以保證算法的收斂性，并且AEGA 算法沒有增加計算量，因而消耗時間比SAGA 少.

2）比較確定權重的方法.

從圖4-5可以看出，利用信息熵確定權重，得到的聚類結果是位置相近的節(jié)點聚合在一起；而主觀將4個屬性權重設置成相同值的聚類結果，幾個聚類簇包含的節(jié)點分布在不同的位置，這是由于非空間屬性權重過大造成的.根據經驗知道，空間距離越遠，節(jié)點之間相互影響越小.在同一個聚類簇中，2個距離較遠的節(jié)點僅僅是壓力表現相似，但是造成兩者相似的原因可能相同，也可能不同，因此不能真正作為同一類節(jié)點.由此可知，利用信息熵確定權重的方法，要優(yōu)于主權確定權重的方法.

3 結 論

提出利用管網節(jié)點的壓力均值、壓力峰度值2個指標作為給水管網節(jié)點的屬性，基于管網的空間、非空間屬性，對管網節(jié)點進行聚類，將多種改進方法應用空間聚類的優(yōu)化，相對于傳統(tǒng)的空間聚類算法，在指標與權重選取、聚類穩(wěn)定性、聚類精度、等方面都有一定的創(chuàng)新性.

在空間K 均值方法的基礎上，進行了以下的工作：（1）利用改進的遺傳算法，對一體化空間K 均值聚類方法進行改進，得到優(yōu)化的初始聚類中心；（2）引入信息熵的方法，得到屬性之間的權重；比較了普通GAK 均值空間聚類、AEGAK 均值空間聚類、SAGAK 均值空間聚類法、普通一體化K 均值空間聚類4種聚類方法，認為其中AEGAK 均值空間聚類花費較少的時間，可以得到最好的聚類結果；（3）比較了信息熵確定權重與主觀確定權重的方法對于AEGAK 均值空間聚類的影響，認為信息熵確定權重要優(yōu)于主觀確定權重的方法.

給水管網空間聚類應用廣泛：在進行管網建模時，需要根據管網節(jié)點空間聚類進行簡化；開發(fā)給水管網調度決策系統(tǒng)時，需對給水管網數百個節(jié)點的壓力變化及相互間關系進行分析；在管網診斷分析時，需要將管網節(jié)點聚為一類，進行信息的融合，提高判斷結果的可靠性等.

空間聚類是空間數據挖掘和知識發(fā)現的主要途徑之一，目前空間聚類方法種類繁多，對于不同問題需要通過比較選擇合適的優(yōu)化與聚類方法.

（

）：

［1］王旭冕，黃廷林，劉勇，等.給水管網水質分區(qū)聚類分析中的指標三步篩選法［J］.西安建筑大學學報：自然科學版.2009，41（5）：709-714.WANG Xu-mian，HUANG Ting-lin，LIU Yong，et al.The three-step screening method of indexes for cluster analysis in water supply system's subregion［J］.Journal of Xi’an University of Architeture ＆Technology，2009，41（5）：709-714.

［2］李雅潔，王景成，趙平偉.聚類算法在給水管網節(jié)點選擇中的應用［J］.計算機工程，2010，36（8）：245-250.LI Ya-jie，WANG Jing-cheng，ZHAO Ping-wei.Application of clustering algorithm in choosing nodes from water supply network［J］.Computer Engineering，2010，36（8）：245-250.

［3］程廣河，任緒才，張讓勇.城市給水管網水量漏失監(jiān)測機制研究［J］.給水排水，2007，33（zl）：355-357.CHENG Guang-he，REN Xu-cai，ZHANG Rang-yong.Monitoring mechanisms for leakage of urban water distribution system［J］.Water ＆ Wastewater Engineering，2007，33（zl）：355-357.

［4］PERELMAN L，OSTFELD A.Water-distribution systems simplificationsthrough clustering ［J］.Journal of Water Resources Planning andManagement，2012，18（3）：218-228.

［5］黃璐，李樹平，周巍巍，等.基于原有測壓點的給水管網壓力監(jiān)測點優(yōu)化布置研究［J］.給水排水.2013，39（2）：119-122.HUANG Lu，LI Shu-ping，ZHOU Wei-wei.Study on optimized layout of pressure monitoring points in water supply network based on existing pressure monitoring points［J］.Water ＆ Wastewater Engineering，2013，39（2）：119-122.

［6］賈新強.基于趨勢面分析的城市給水管網系統(tǒng)漏損區(qū)判定的研究［D］.太原：太原理工大學.2007：25-28.JIA Xin-qang.Research on network leakage region determination based on the analysis method of trend surface［D］.Taiyuan：Taiyuan University of Technology.2007：25-28.

［7］邰明明.基于kriging 的給水管網節(jié)點壓力插值研究［J］.中國建筑金屬結構.2013，（6）：210-211.Tai Ming-ming.Study on node pressure interpolation based on kriging［J］.China Construction Metal Structure，2013（6）：210-211.

［8］戴一明.基于Kmeans聚類法的給水管網水壓監(jiān)測點優(yōu)化布置［J］.建筑安全.2014，29（8）：74-77 DAI Yi-ming.Optimal placement of water distribution system pressure monitors based on k-means clustering［J］.Construction Safety，2014，29（8）：74-77.

［9］李光強，鄧敏，程濤，等.一種基于雙重距離的空間聚類方法［J］測繪學報.2008，37（4）：482-483.LI Guang-qian，DENG Min，CHENG Tao.et al.A dual distance based spatial clustering method［J］.Acta Geodaetica et Cartographica Sinica，2008，37（4）：482-483.

［10］李新運，鄭新奇，閆弘文.坐標與屬性一體化的空間聚類方法研究［J］.地理與地理信息科學.2004，20（03）：38-40.LI Xin-yun，ZHENG Xin-gi，YAN Hong-wen.On spatial clustering of combination of coordinate and attribute［J］.Geography and Geo-Information Science，2004，20（03）：38-40.

［11］武兆慧，張桂娟，劉希玉.基于模擬退火遺傳算法的聚類分析［J］.計算機應用研究.2005，22（12）：24-26.WU Zhao-hui，ZHANG Gui-juan，LIU Xi-yu.Clustering based on simulated annealing genetic algorithm［J］.Application Research of Computers，2005，22（12）：24-26.

［12］桂云苗，朱金福.一種用信息熵確定聚類權重的方法［J］.統(tǒng)計與決策.2005（16）：29-30.GUI Yun-miao，ZHU Jin-fu.A method of determining clustering weights with entropy information［J］.Statistics and Decision.2005（16）：29-30.

［13］ZHANG Jun，CHUNG H S H，HU B J.Adaptive probabilities of crossover and mutation in genetic algorithms［J］.IEEE Trans Syst Man and Cybernetics，1994，24（4）：656-667.

［14］魏書堤，姜小奇.一種利用信息熵確定屬性權重的模糊單因素評價方法［J］.計算機工程與科學.2010，7（32）：93-94.WEI Shu-di，JIANG Xiao-qi.A single-factor fuzzy evaluation method of using information entropy to determine the property weights［J］.Computer Engineering and Science，2010，7（32）：93-94.

［15］朱紅燦，陳能華.粗糙集條件信息熵權重確定方法的改進［J］.統(tǒng)計與決策.2011（08）：154-156.ZHU Hong-can，CHEN Neng-hua.Improved rough set information entropy method for weight determining［J］.Statistics and Decision，2011（08）：154-156.

［16］劉冀，王本德.基于組合權重的模糊可變模型及在防洪風險評價中應用［J］.大連理工大學學報.2009，49（02）：272-275 LIU Ji，WANG Ben-de.Variable fuzzy model based on combined weights and its application to risk assessment for flood control engineering［J］.Journal of Dalian University of Technology，2009，49（02）：272-275.