供水管網壓力分區方法的比較分析

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

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

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

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

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

1 計算分區方法

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

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

（1）給定數據集X={x1,x2,···,xn}。

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

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

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

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

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

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

1.2 層次聚類算法（Hierarchical clustering）

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

（1）每個數據點被指定為單個簇。

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

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

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

（4）更新距離。

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

1.3 譜聚類算法（Spectral clustering）

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

（1）給定數據集X={x1,x2,···,xn}。

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

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

（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均值聚類算法、層次聚類算法、譜聚類算法均需要提供簇的個數，為確定最優的簇的個數，采用輪廓系數對2到n個分區進行評價，從中選出最優簇的個數。

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

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

3 結果與分析

3.1 管網案例分析

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

Anytown 來自一個假設的社區供水系統。供水系統如圖1（a）所示，該系統為環形管網，擁有1個水源、2 個水池、3 個水泵、16 個節點。管網高程東高西低。

圖1 管網案例

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

3.2 不同分區方法最佳分區個數比較

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

圖2 分區方法流程比較

3.2.1 Anytown模型

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

表1 Anytown分區結果的輪廓系數

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

圖3 Anytown各節點壓力與分區示意

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

3.2.2 KY3模型

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

表2 KY3分區結果的輪廓系數

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

圖4 KY3各節點壓力與分區示意

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

4 結論

（1）層次聚類算法在Anytown 簡單管網下效果較好，但是在KY3 復雜管網中會出現節點分散。譜聚類算法雖然在Anytown 簡單管網下會出現部分節點分區不恰當的問題，但在KY3 復雜管網中的分類效果要優于層次聚類算法。

（2）K均值聚類算法在Anytown 簡單管網和KY3 復雜管網中的壓力分區結果相較于其他2 種算法均具有較好的效果，在壓力分區內沒有較為分散的節點。

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