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

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

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

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

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

1 計(jì)算分區(qū)方法

1.1 K均值聚類(lèi)算法（K-means）

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

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

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

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

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

（4）根據(jù)下式重新計(jì)算k個(gè)新聚類(lèi)中心點(diǎn)，并重復(fù)步驟（2）：

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

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

1.2 層次聚類(lèi)算法（Hierarchical clustering）

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

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

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

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

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

（4）更新距離。

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

1.3 譜聚類(lèi)算法（Spectral clustering）

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

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

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

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

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

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

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

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

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

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

2 評(píng)價(jià)指標(biāo)

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

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

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

3 結(jié)果與分析

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

選取了2 個(gè)管網(wǎng)進(jìn)行分區(qū)方法比較，其中Anytown 是一個(gè)節(jié)點(diǎn)較少、拓?fù)浣Y(jié)構(gòu)相對(duì)簡(jiǎn)單的供水管網(wǎng)，而KY3 則是一個(gè)節(jié)點(diǎn)數(shù)較多、拓?fù)浣Y(jié)構(gòu)相比于Anytown復(fù)雜的供水管網(wǎng)。

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

圖1 管網(wǎng)案例

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

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

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

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

3.2.1 Anytown模型

通過(guò)評(píng)價(jià)指標(biāo)，得到Anytown在3種分區(qū)方法下各分區(qū)個(gè)數(shù)的輪廓系數(shù)，詳見(jiàn)表1。

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

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

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

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

3.2.2 KY3模型

通過(guò)評(píng)價(jià)指標(biāo)，得到KY3 在3 種分區(qū)方法下各分區(qū)個(gè)數(shù)的輪廓系數(shù)，詳見(jiàn)表2。

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

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

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

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

4 結(jié)論

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

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

（3）由于3 種算法均無(wú)法考慮拓?fù)浣Y(jié)構(gòu)的問(wèn)題，會(huì)導(dǎo)致距離相近和壓力相近但沒(méi)有鏈接的節(jié)點(diǎn)劃分至同一個(gè)壓力分區(qū)中，在實(shí)際進(jìn)行壓力分區(qū)時(shí)仍需要根據(jù)需要進(jìn)行調(diào)節(jié)。