何立新，范一飛，雷曉輝，王 琦

（1.河北工程大學水利水電學院，河北 邯鄲 056000；2.河北工程大學河北省智慧水利重點實驗室，河北 邯鄲 056038；3.廣東工業(yè)大學土木與交通工程學院，廣東 廣州 510006）

隨著城鎮(zhèn)供水管網(wǎng)規(guī)模越來越大，城鎮(zhèn)供水壓力導致的漏損問題也在逐步惡化。供水管網(wǎng)壓力分區(qū)是解決管網(wǎng)漏損的前提之一，其根據(jù)節(jié)點坐標及節(jié)點壓力，將管網(wǎng)劃分成多個區(qū)域，劃分后各分區(qū)內(nèi)節(jié)點相近，壓力相似。對各壓力分區(qū)進行不同的調(diào)控，可以有效降低整個管網(wǎng)壓力，從而達到減少漏損目的[1]。

國內(nèi)外許多學者也都基于各種目的，選取了不同數(shù)據(jù)集（如節(jié)點坐標、節(jié)點壓力等）與方法對管網(wǎng)進行了分區(qū)。張偉倩[2]運用Canopy 算法確定分區(qū)個數(shù)后選擇K 均值聚類算法對管網(wǎng)進行壓力分區(qū)，將管網(wǎng)分成多個區(qū)域，并成功降低了整體壓力。唐鵬翔[3]則利用廣度優(yōu)先鄰居聚類算法，通過節(jié)點坐標與節(jié)點壓力對管網(wǎng)進行分區(qū)，在壓力調(diào)控中取得了較好的壓力控制效果。Herrera 等[4]將管網(wǎng)的拓撲結構和水力平衡作為約束條件，通過譜聚類算法對管網(wǎng)進行分區(qū)，實現(xiàn)了管網(wǎng)漏損控制。Paola 等[5]在分區(qū)時以壓力、流量和運行費用為數(shù)據(jù)集，利用K均值聚類算法制定了DMA分區(qū)方案。劉俊等[6]則證明了譜聚類算法在供水管網(wǎng)中的有效性。

本文選取K均值聚類算法、層次聚類算法、譜聚類算法3 種常用的分區(qū)方法在Anytown 和KY3 2 個典型管網(wǎng)案例中進行了應用，通過輪廓系數(shù)來選取各方法在各管網(wǎng)案例中的最佳分區(qū)方案。通過對結果的比較分析，確定適應度較廣的聚類分區(qū)方法，為供水管網(wǎng)壓力分區(qū)提供參考。

1 計算分區(qū)方法

1.1 K均值聚類算法（K-means）

K均值聚類算法是一種矢量量化方法，也是無監(jiān)督學習領域最為經(jīng)典的算法之一。其起源于信號處理，是數(shù)據(jù)挖掘中常用的聚類分析方法。K均值聚類算法將n個數(shù)據(jù)點進行聚類分析，得到k個聚類，使得每個數(shù)據(jù)點到聚類中心的距離最小。具體步驟如下。

（1）給定數(shù)據(jù)集X={x1,x2,···,xn}。

（2）從數(shù)據(jù)集中任意選取k個對象作為初始聚類中心，并從X中將其取出。

（3）采用下式分別求出各元素到初始聚類中心的距離，并將元素分配至最靠近的初始聚類中心，將數(shù)據(jù)分為k類。

式中：dist()Xi,Cj為樣本Xi到聚類中心Cj的距離；Xi為樣本數(shù)據(jù)（i=1，2，3，…，n），Xi,t為第i個樣本數(shù)據(jù)的第t個要素；Cj為聚類中心（j=1，2，3，…，n），Cj,t為第j個聚類中心的第t個要素；m為數(shù)據(jù)維度；t為數(shù)據(jù)的第t個要素。

（4）根據(jù)下式重新計算k個新聚類中心點，并重復步驟（2）：

式中：Centerk為新聚類中心；| |Cj為第j個聚類中所包含的樣本個數(shù)；xi為屬于Cj聚類中心的樣本。

（5）直到更新后的聚類中心和上一次的無變化或誤差平方和最小停止迭代。

1.2 層次聚類算法（Hierarchical clustering）

層次聚類算法是從N個簇開始，將每一個對象作為一個簇，然后在每個步驟中合并2 個最相似的簇，直到形成一個包含所有數(shù)據(jù)的簇。具體步驟如下。

（1）每個數(shù)據(jù)點被指定為單個簇。

（2）確定距離測量值并計算距離矩陣，一般采用歐幾里得距離，公式如下：

式中：ρ為歐幾里得距離；x1、y1、z1為第一個點內(nèi)要素；x2、y2、z2為第二個點內(nèi)要素。

（3）確定合并簇的鏈接條件。鏈接條件有以下4 種：①最遠鄰聚類，計算簇與簇之間各元素距離，將最遠距離作為簇與簇的距離；②最近鄰聚類，計算簇與簇之間各元素距離，將最近距離作為簇與簇的距離；③平均鏈接聚類，計算簇與簇之間各元素距離，將平均距離作為簇與簇的距離；④最小化所有簇內(nèi)的平方差總和。

（4）更新距離。

（5）重復這個過程，直到形成包含所有數(shù)據(jù)的N個簇（N為需要的簇的個數(shù)）。

1.3 譜聚類算法（Spectral clustering）

譜聚類算法是基于圖論的算法，是將樣本點兩兩相連構成圖這一數(shù)據(jù)結構。譜聚類是通過切圖的方式來劃分不同的簇，其原理是使得子簇內(nèi)部邊的權重之和盡可能高，而不同子簇之間邊的權重之和盡可能低。具體步驟如下。

（1）給定數(shù)據(jù)集X={x1,x2,···,xn}。

（2）使用下式計算n×n的相似度矩陣W：

式中：wij為相似矩陣W中第i行第j列元素；xi為數(shù)據(jù)集X 中第i個元素；xj為數(shù)據(jù)集X 中第j個元素；σ為高斯濾波器寬度；n為數(shù)據(jù)集中數(shù)據(jù)個數(shù)。

（3）將相似矩陣W 中的每行元素之和構成n×n對角陣，也就是度矩陣D，由下式計算：

式中：di為度矩陣D第i行第i列的元素；wij為相似矩陣W的第i行第j列元素。

（4）計算拉普拉斯矩陣L=D-W。

（5）計算L 的特征值，并將特征值由小到大排列，計算前k個特征值的特征向量，組成矩陣U={u1,u2,···,uk}，U ∈Rn*k。

（6）令yi∈Rk是第i行向量，其中i=1，2，···，n。

（7）使用K-means算法將新樣本點Y={y1,y2,···,yk}聚類成簇C1,C2,···,Ck。

2 評價指標

由于K均值聚類算法、層次聚類算法、譜聚類算法均需要提供簇的個數(shù)，為確定最優(yōu)的簇的個數(shù)，采用輪廓系數(shù)對2到n個分區(qū)進行評價，從中選出最優(yōu)簇的個數(shù)。

輪廓系數(shù)是評價聚類算法性能的一個指標。使用單個簇的緊湊性（簇內(nèi)距離）和簇間的分離（簇間距離）來衡量聚類算法執(zhí)行情況的得分，其范圍在[-1，1]。S值越大，越合理。其計算公式為：

式中：S(i)為每個點的輪廓系數(shù)；a(i)為點i到簇內(nèi)其他點的距離的平均值，體現(xiàn)凝聚度；b(i)為點i到其他簇中所有點的距離的平均值中的最小值，體現(xiàn)分離度；S為該聚類的輪廓系數(shù)；n為點的個數(shù)。

3 結果與分析

3.1 管網(wǎng)案例分析

選取了2 個管網(wǎng)進行分區(qū)方法比較，其中Anytown 是一個節(jié)點較少、拓撲結構相對簡單的供水管網(wǎng)，而KY3 則是一個節(jié)點數(shù)較多、拓撲結構相比于Anytown復雜的供水管網(wǎng)。

Anytown 來自一個假設的社區(qū)供水系統(tǒng)。供水系統(tǒng)如圖1（a）所示，該系統(tǒng)為環(huán)形管網(wǎng)，擁有1個水源、2 個水池、3 個水泵、16 個節(jié)點。管網(wǎng)高程東高西低。

圖1 管網(wǎng)案例

KY3來自一個位于肯塔基州供水系統(tǒng)。供水系統(tǒng)如圖1（b）所示，該系統(tǒng)為環(huán)形管網(wǎng)，擁有3 個水源、3 個水池、5 個水泵、269 個節(jié)點。管網(wǎng)高程西邊部分呈南高北低，東邊部分呈南低北高。

3.2 不同分區(qū)方法最佳分區(qū)個數(shù)比較

根據(jù)評價指標，分別計算Anytown 和KY3 在3種分區(qū)方法下的最佳分區(qū)，數(shù)據(jù)集為節(jié)點坐標和各節(jié)點壓力?？紤]到管網(wǎng)規(guī)模以及分區(qū)成本，Anytown分區(qū)個數(shù)限制在2～4 個，KY3 分區(qū)個數(shù)限制在4～8個，具體流程如圖2所示。

圖2 分區(qū)方法流程比較

3.2.1 Anytown模型

通過評價指標，得到Anytown在3種分區(qū)方法下各分區(qū)個數(shù)的輪廓系數(shù)，詳見表1。

表1 Anytown分區(qū)結果的輪廓系數(shù)

由表1 可知，3 種方法的最佳分區(qū)個數(shù)均為2個，且K均值聚類算法和層次聚類算法2 種分區(qū)方法的評分高于譜聚類算法。3 種分區(qū)方法的結果及各節(jié)點壓力如圖3 所示，圖3（b）（c）（d）中黑色節(jié)點代表在同一分區(qū)內(nèi)，灰色節(jié)點代表在不同分區(qū)內(nèi)。

圖3 Anytown各節(jié)點壓力與分區(qū)示意

通過圖3可知，K均值聚類算法和層次聚類算法的分區(qū)是相同的，與譜聚類算法僅是“140”節(jié)點不同，通過節(jié)點壓力圖可以發(fā)現(xiàn)該節(jié)點壓力與左側接近，但距離接近“150”節(jié)點。通過水流流向可以發(fā)現(xiàn)“110”節(jié)點是東側分區(qū)的一個入口，無法直接打斷，會在進行分區(qū)時進行適當調(diào)整。對于Anytown 管網(wǎng)來說，K均值聚類算法和層次聚類算法計算效果比譜聚類算法好。

3.2.2 KY3模型

通過評價指標，得到KY3 在3 種分區(qū)方法下各分區(qū)個數(shù)的輪廓系數(shù)，詳見表2。

表2 KY3分區(qū)結果的輪廓系數(shù)

由表2 可知，K 均值聚類算法最佳評分分區(qū)為7，層次聚類算法最佳評分分區(qū)為8，譜聚類算法最佳評分分區(qū)為6。3 種分區(qū)方法的結果及各節(jié)點壓力如圖4 所示，圖4（b）（c）（d）中同一種顏色則代表節(jié)點在同一分區(qū)內(nèi)。

圖4 KY3各節(jié)點壓力與分區(qū)示意

通過圖4 可知，K均值聚類算法不管是在節(jié)點坐標還是在節(jié)點壓力上區(qū)域間都較為分明。層次聚類算法從節(jié)點坐標上看則稍有瑕疵，如3 號區(qū)域節(jié)點相距比較分散。譜聚類算法也在節(jié)點坐標方面存在瑕疵，如2 號區(qū)域節(jié)點有部分被分離在了較遠且沒有管網(wǎng)相鄰的位置。3 種算法均出現(xiàn)了由于距離相近壓力相近卻不鏈接的節(jié)點分在同一區(qū)域，均需要在進行壓力分區(qū)時進行手動修改。

4 結論

（1）層次聚類算法在Anytown 簡單管網(wǎng)下效果較好，但是在KY3 復雜管網(wǎng)中會出現(xiàn)節(jié)點分散。譜聚類算法雖然在Anytown 簡單管網(wǎng)下會出現(xiàn)部分節(jié)點分區(qū)不恰當?shù)膯栴}，但在KY3 復雜管網(wǎng)中的分類效果要優(yōu)于層次聚類算法。

（2）K均值聚類算法在Anytown 簡單管網(wǎng)和KY3 復雜管網(wǎng)中的壓力分區(qū)結果相較于其他2 種算法均具有較好的效果，在壓力分區(qū)內(nèi)沒有較為分散的節(jié)點。

（3）由于3 種算法均無法考慮拓撲結構的問題，會導致距離相近和壓力相近但沒有鏈接的節(jié)點劃分至同一個壓力分區(qū)中，在實際進行壓力分區(qū)時仍需要根據(jù)需要進行調(diào)節(jié)。