基于自適應(yīng)譜聚類算法的供水管網(wǎng)DMA分區(qū)

楊浩志，周 艷，王晨婉，孫 韜

（1.天津理工大學(xué)環(huán)境科學(xué)與安全工程學(xué)院,天津 300350；2.天津市生態(tài)環(huán)境科學(xué)研究院,天津 300191）

供水管網(wǎng)系統(tǒng)是維系人們生產(chǎn)生活的重要基礎(chǔ)設(shè)施。隨著城市的發(fā)展,管道老化、管線連接冗余等問題嚴(yán)重影響供水安全,同時伴隨供水需求和供水面積的增加,管網(wǎng)漏損和水質(zhì)惡化越來越引起人們的重視。為科學(xué)合理的管理供水管網(wǎng),人們提出了區(qū)域計量分區(qū)（District Metered Areas,DMA分區(qū)）的概念[1]。

在對DMA分區(qū)的已有研究中,可分為兩種：人工經(jīng)驗法分區(qū)和算法分區(qū)。人工經(jīng)驗法分區(qū)是根據(jù)自然地理條件或人為屏障作為區(qū)域邊界,通過在供水管網(wǎng)配水干管上設(shè)置閥門或流量計,將管網(wǎng)劃為多個區(qū)域。如朱子朋、孫偉等[2]以投資少、方便實施為分區(qū)目標(biāo),通過設(shè)置河流、鐵路干線和供水管網(wǎng)的加壓站等為分區(qū)邊界,將廣州市的供水管網(wǎng)劃分為18個獨立供水區(qū)域。目前我國對城市供水管網(wǎng)的分區(qū)研究大多采用人工經(jīng)驗法[3],雖然該方法操作簡單,但往往需要實施者具備大量工作經(jīng)驗,隨機性較強,因此收到一定的條件限制。而算法分區(qū)多數(shù)是將供水管網(wǎng)的節(jié)點和管道轉(zhuǎn)化為圖,基于圖論和復(fù)雜網(wǎng)絡(luò)等理論將管網(wǎng)劃分為多個區(qū)域。如Gomes等[4]提出了一種基于決策支持系統(tǒng)的分區(qū)方法。該方法應(yīng)用圖論中最小路徑的原理,搜索供水管網(wǎng)最大用水時刻的水源供水范圍,初步劃分管網(wǎng)的DMA。然后,以經(jīng)濟最大化為目標(biāo),應(yīng)用模擬退化算法確定DMA進(jìn)水口的位置,完成DMA分區(qū)。算法分區(qū)避免了由于人的主觀經(jīng)驗造成分區(qū)的隨機性,使分區(qū)更加科學(xué)合理。

因此,本文在k近鄰算法的基礎(chǔ)上引入共享最近鄰的概念,構(gòu)建供水管網(wǎng)節(jié)點的相似度矩陣,同時對聚類中心的選擇進(jìn)行優(yōu)化?；谧赃m應(yīng)譜聚類算法,以經(jīng)濟性和管網(wǎng)穩(wěn)定性為主要目標(biāo),選取合適分區(qū)數(shù)目,完成對管網(wǎng)的DMA分區(qū)。該方法引入共享最近鄰構(gòu)建節(jié)點的相似度矩陣,實現(xiàn)了自動設(shè)定相似度矩陣的參數(shù),解決了人為設(shè)定的弊端,提高了聚類精確度,使分區(qū)更加合理。

1 自適應(yīng)譜聚類算法

1.1 相似矩陣和拉普拉斯矩陣

自適應(yīng)譜聚類算法是一種基于圖論將圖劃分求解的聚類算法。一般對所求問題采取連續(xù)松弛的方式,將圖劃分問題轉(zhuǎn)化為劃分圖的拉普拉斯矩陣。圖的拉普拉斯矩陣一般是由圖的相似矩陣和度矩陣轉(zhuǎn)化而來。

相似矩陣反映供水管網(wǎng)元素所構(gòu)成的圖中元素之間的相似度,其組成的數(shù)據(jù)集以矩陣形式表達(dá),用Wij表示,見式（1）。

式中：d2（xi-xj）為元素之間的歐氏距離； σ為人為選取的尺度參數(shù)。

由管網(wǎng)拓?fù)浣Y(jié)構(gòu)可得節(jié)點相似矩陣,見式（2）。

式中：E為管網(wǎng)的邊的集合；ij為管網(wǎng)節(jié)點。

由管網(wǎng)拓?fù)潢P(guān)系可知,若兩點由管段連接,則這兩點互為鄰居關(guān)系。節(jié)點自然鄰居越多,說明節(jié)點與周圍節(jié)點聯(lián)系越緊密。當(dāng)對管網(wǎng)進(jìn)行DMA分區(qū)時,聯(lián)系緊密的節(jié)點易被分到一個分區(qū)中。由式1,傳統(tǒng)節(jié)點近鄰算法在計算相似矩陣時,對σ參數(shù)的選取一般為人工經(jīng)驗選取,且對于不同數(shù)據(jù)對應(yīng)參數(shù)不同[5]。本文引入共享最近鄰算法改進(jìn)相似矩陣,見式（3）。

式中：max（ N）為節(jié)點集合中的最大鄰居數(shù)；N（i）為節(jié)點i的鄰居數(shù)。

度矩陣是一個對角矩陣,其對角元素分別是相似矩陣Wij中對應(yīng)的行向量或者列向量,以Dii來表示,見式（4）。

由圖的相似矩陣和度矩陣建立圖的拉普拉斯矩陣,目前圖的拉普拉斯矩陣分為兩種：非規(guī)范化和規(guī)范化。非規(guī)范化的拉普拉斯矩陣Lij表達(dá)式見式（5）。式中：Lij為非規(guī)范化拉普拉斯矩陣；Dii為度矩陣；Wij為相似矩陣。

規(guī)范化的拉普拉斯矩陣有兩種形式,見式（6）、式（7）。

1.2 圖劃分準(zhǔn)則

由于不同形式的拉普拉斯矩陣對應(yīng)的圖劃分準(zhǔn)則不同,非規(guī)范化拉普拉斯矩陣對應(yīng)圖劃分準(zhǔn)則為最小分割準(zhǔn)則,見式（8）。規(guī)范化拉普拉斯矩陣對應(yīng)圖劃分準(zhǔn)則為規(guī)范分割準(zhǔn)則（式（9））和比例分割準(zhǔn)則（式（10））。

式中：|A| 為子圖A的頂點數(shù)目；|B|為子圖B的頂點數(shù)目。

由于最小分割準(zhǔn)則只考慮劃分子圖之間的連接權(quán)重,未能考慮子圖內(nèi)部密度分布,在劃分過程中易出現(xiàn)分割歪斜現(xiàn)象,同時比例分割準(zhǔn)則在運行速度和效率上不如另外兩種劃分準(zhǔn)則,因此本文選取規(guī)范分割準(zhǔn)則對圖進(jìn)行劃分,對應(yīng)的拉普拉斯矩陣,見式（6）。

1.3 算法步驟

本文的自適應(yīng)譜聚類算法以NJW算法為基礎(chǔ),其本質(zhì)是通過計算拉普拉斯矩陣的前k個最大特征值和相對應(yīng)的特征向量,并與節(jié)點構(gòu)成相對應(yīng)的關(guān)系,然后在空間中進(jìn)行聚類。算法步驟如下：

（1）計算相似矩陣Aij∈ln×n,其中Aij為相似矩陣的鄰接矩

（3）計算拉普拉斯矩陣的前K個最大特征值,記為1…k,并計算特征值對應(yīng)的特征向量a1…ak,構(gòu)建特征向量矩陣[a]n×k=[a1,a2,a3,…ak] ∈I,k即為聚類數(shù)目。

（4）將矩陣[a]n×k中的行向量與原數(shù)據(jù)集中的節(jié)點相對應(yīng),應(yīng)用K-means聚類算法對節(jié)點進(jìn)行聚類,引入center參數(shù)矯正聚類中心,得到K個聚類結(jié)果,完成管網(wǎng)分區(qū)。

2 案例分析

本文采用管網(wǎng)校核競賽的Ctown案例來驗證所提出DMA分區(qū)方法。管網(wǎng)共包含388 個節(jié)點,1 個水庫,7 個水池,429 根管段,總管長56.177 km。各個節(jié)點位置參數(shù)可基于EPANET建立的水力模型得到。由于DMA分區(qū)之間是以在邊界連接管段上安裝閥門或流量計來劃分,且流量計和閥門設(shè)備費用較高,因此在對DMA分區(qū)時應(yīng)盡可能使邊界連接管段數(shù)量較少。同時為保證分區(qū)合理,本文以模塊度M（式11）、節(jié)點均衡性B（式12）和邊界連接管段數(shù)量評價分區(qū)是否可行。

式中：Aij為網(wǎng)絡(luò)鄰接矩陣,若節(jié)點i與j相連,則Aij=1,若不相連, Aij=0；i和j為節(jié)點；e為網(wǎng)絡(luò)邊數(shù)；ki為節(jié)點i的度；kj為節(jié)點j的度；Ci為節(jié)點i所在分區(qū)；Cj為節(jié)點j所在分區(qū)。若節(jié)點i和節(jié)點j分區(qū)一致,則 =1,否則 =0。

根據(jù)式（11）可知,分區(qū)越合理對應(yīng)模塊度的數(shù)值越高,其取值范圍為[0,1]。

式中：Cd為分區(qū)數(shù)；nd為第d個分區(qū)的節(jié)點數(shù),n為各分區(qū)的平均節(jié)點數(shù)。

節(jié)點均衡性反應(yīng)了分區(qū)規(guī)模是否趨近一致,其數(shù)值越小證明分區(qū)越合理。

通過已有文獻(xiàn)可知[6],相關(guān)學(xué)者將Ctown劃分為5 個DMA分區(qū)。本文為比較不同分區(qū)數(shù)目的管網(wǎng)聚類效果,分別選取分區(qū)個數(shù)為4、5、6。該管網(wǎng)樹狀結(jié)構(gòu)和管網(wǎng)控制元件較多,且水池分布均勻,因此管網(wǎng)區(qū)域特征較為明顯,管網(wǎng)拓?fù)浣Y(jié)構(gòu)見圖1。

圖1 Ctown拓?fù)浣Y(jié)構(gòu)圖

分別輸入分區(qū)個數(shù)4、5、6,基于自適應(yīng)譜聚類算法利用MATLAB對案例管網(wǎng)進(jìn)行DMA分區(qū),分區(qū)結(jié)果見圖2。

圖2 DMA分區(qū)結(jié)果

根據(jù)圖2劃分結(jié)果,分別計算管網(wǎng)的模塊度、節(jié)點均衡性和邊界連接管段數(shù)量,計算結(jié)果見表1。

表1 DMA分區(qū)的評價結(jié)果

根據(jù)表1的計算結(jié)果,三次分區(qū)的模塊度數(shù)值接近,但將管網(wǎng)劃分為4個DMA分區(qū)的節(jié)點均衡性數(shù)值較高,分區(qū)效果不理想,因此不宜作為DMA分區(qū)方案。以5個DMA分區(qū)數(shù)和6個DMA分區(qū)數(shù)對管網(wǎng)進(jìn)行劃分,模塊度和邊界連接管段數(shù)量接近,但節(jié)點均衡性差別明顯,且節(jié)點均衡性數(shù)值越小分區(qū)越合理。因此,本文選取分區(qū)方案為6個DMA分區(qū)。

3 結(jié)論

本文提出了基于自適應(yīng)譜聚類算法的DMA分區(qū)方法,并矯正聚類中心。該算法有效減少了分區(qū)邊界連接管的數(shù)量,從而使安裝閥門和流量計的費用降低。通過模塊度和節(jié)點均衡性指標(biāo)評價分區(qū)結(jié)果,使分區(qū)更加合理,完成了分區(qū)合理經(jīng)濟的目標(biāo)。并基于Ctown案例管網(wǎng)驗證了該分區(qū)方法的可行性。該算法經(jīng)濟有效,能夠合理地對管網(wǎng)進(jìn)行DMA分區(qū),提高對管網(wǎng)的科學(xué)管理能力。