基于自适应谱聚类算法的供水管网DMA分区

杨浩志，周 艳，王晨婉，孙 韬

（1.天津理工大学环境科学与安全工程学院,天津 300350；2.天津市生态环境科学研究院,天津 300191）

供水管网系统是维系人们生产生活的重要基础设施。随着城市的发展,管道老化、管线连接冗余等问题严重影响供水安全,同时伴随供水需求和供水面积的增加,管网漏损和水质恶化越来越引起人们的重视。为科学合理的管理供水管网,人们提出了区域计量分区（District Metered Areas,DMA分区）的概念[1]。

在对DMA分区的已有研究中,可分为两种：人工经验法分区和算法分区。人工经验法分区是根据自然地理条件或人为屏障作为区域边界,通过在供水管网配水干管上设置阀门或流量计,将管网划为多个区域。如朱子朋、孙伟等[2]以投资少、方便实施为分区目标,通过设置河流、铁路干线和供水管网的加压站等为分区边界,将广州市的供水管网划分为18个独立供水区域。目前我国对城市供水管网的分区研究大多采用人工经验法[3],虽然该方法操作简单,但往往需要实施者具备大量工作经验,随机性较强,因此收到一定的条件限制。而算法分区多数是将供水管网的节点和管道转化为图,基于图论和复杂网络等理论将管网划分为多个区域。如Gomes等[4]提出了一种基于决策支持系统的分区方法。该方法应用图论中最小路径的原理,搜索供水管网最大用水时刻的水源供水范围,初步划分管网的DMA。然后,以经济最大化为目标,应用模拟退化算法确定DMA进水口的位置,完成DMA分区。算法分区避免了由于人的主观经验造成分区的随机性,使分区更加科学合理。

因此,本文在k近邻算法的基础上引入共享最近邻的概念,构建供水管网节点的相似度矩阵,同时对聚类中心的选择进行优化。基于自适应谱聚类算法,以经济性和管网稳定性为主要目标,选取合适分区数目,完成对管网的DMA分区。该方法引入共享最近邻构建节点的相似度矩阵,实现了自动设定相似度矩阵的参数,解决了人为设定的弊端,提高了聚类精确度,使分区更加合理。

1 自适应谱聚类算法

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

自适应谱聚类算法是一种基于图论将图划分求解的聚类算法。一般对所求问题采取连续松弛的方式,将图划分问题转化为划分图的拉普拉斯矩阵。图的拉普拉斯矩阵一般是由图的相似矩阵和度矩阵转化而来。

相似矩阵反映供水管网元素所构成的图中元素之间的相似度,其组成的数据集以矩阵形式表达,用Wij表示,见式（1）。

式中：d2（xi-xj）为元素之间的欧氏距离； σ为人为选取的尺度参数。

由管网拓扑结构可得节点相似矩阵,见式（2）。

式中：E为管网的边的集合；ij为管网节点。

由管网拓扑关系可知,若两点由管段连接,则这两点互为邻居关系。节点自然邻居越多,说明节点与周围节点联系越紧密。当对管网进行DMA分区时,联系紧密的节点易被分到一个分区中。由式1,传统节点近邻算法在计算相似矩阵时,对σ参数的选取一般为人工经验选取,且对于不同数据对应参数不同[5]。本文引入共享最近邻算法改进相似矩阵,见式（3）。

式中：max（ N）为节点集合中的最大邻居数；N（i）为节点i的邻居数。

度矩阵是一个对角矩阵,其对角元素分别是相似矩阵Wij中对应的行向量或者列向量,以Dii来表示,见式（4）。

由图的相似矩阵和度矩阵建立图的拉普拉斯矩阵,目前图的拉普拉斯矩阵分为两种：非规范化和规范化。非规范化的拉普拉斯矩阵Lij表达式见式（5）。式中：Lij为非规范化拉普拉斯矩阵；Dii为度矩阵；Wij为相似矩阵。

规范化的拉普拉斯矩阵有两种形式,见式（6）、式（7）。

1.2 图划分准则

由于不同形式的拉普拉斯矩阵对应的图划分准则不同,非规范化拉普拉斯矩阵对应图划分准则为最小分割准则,见式（8）。规范化拉普拉斯矩阵对应图划分准则为规范分割准则（式（9））和比例分割准则（式（10））。

式中：|A| 为子图A的顶点数目；|B|为子图B的顶点数目。

由于最小分割准则只考虑划分子图之间的连接权重,未能考虑子图内部密度分布,在划分过程中易出现分割歪斜现象,同时比例分割准则在运行速度和效率上不如另外两种划分准则,因此本文选取规范分割准则对图进行划分,对应的拉普拉斯矩阵,见式（6）。

1.3 算法步骤

本文的自适应谱聚类算法以NJW算法为基础,其本质是通过计算拉普拉斯矩阵的前k个最大特征值和相对应的特征向量,并与节点构成相对应的关系,然后在空间中进行聚类。算法步骤如下：

（1）计算相似矩阵Aij∈ln×n,其中Aij为相似矩阵的邻接矩

（3）计算拉普拉斯矩阵的前K个最大特征值,记为1…k,并计算特征值对应的特征向量a1…ak,构建特征向量矩阵[a]n×k=[a1,a2,a3,…ak] ∈I,k即为聚类数目。

（4）将矩阵[a]n×k中的行向量与原数据集中的节点相对应,应用K-means聚类算法对节点进行聚类,引入center参数矫正聚类中心,得到K个聚类结果,完成管网分区。

2 案例分析

本文采用管网校核竞赛的Ctown案例来验证所提出DMA分区方法。管网共包含388 个节点,1 个水库,7 个水池,429 根管段,总管长56.177 km。各个节点位置参数可基于EPANET建立的水力模型得到。由于DMA分区之间是以在边界连接管段上安装阀门或流量计来划分,且流量计和阀门设备费用较高,因此在对DMA分区时应尽可能使边界连接管段数量较少。同时为保证分区合理,本文以模块度M（式11）、节点均衡性B（式12）和边界连接管段数量评价分区是否可行。

式中：Aij为网络邻接矩阵,若节点i与j相连,则Aij=1,若不相连, Aij=0；i和j为节点；e为网络边数；ki为节点i的度；kj为节点j的度；Ci为节点i所在分区；Cj为节点j所在分区。若节点i和节点j分区一致,则 =1,否则 =0。

根据式（11）可知,分区越合理对应模块度的数值越高,其取值范围为[0,1]。

式中：Cd为分区数；nd为第d个分区的节点数,n为各分区的平均节点数。

节点均衡性反应了分区规模是否趋近一致,其数值越小证明分区越合理。

通过已有文献可知[6],相关学者将Ctown划分为5 个DMA分区。本文为比较不同分区数目的管网聚类效果,分别选取分区个数为4、5、6。该管网树状结构和管网控制元件较多,且水池分布均匀,因此管网区域特征较为明显,管网拓扑结构见图1。

图1 Ctown拓扑结构图

分别输入分区个数4、5、6,基于自适应谱聚类算法利用MATLAB对案例管网进行DMA分区,分区结果见图2。

图2 DMA分区结果

根据图2划分结果,分别计算管网的模块度、节点均衡性和边界连接管段数量,计算结果见表1。

表1 DMA分区的评价结果

根据表1的计算结果,三次分区的模块度数值接近,但将管网划分为4个DMA分区的节点均衡性数值较高,分区效果不理想,因此不宜作为DMA分区方案。以5个DMA分区数和6个DMA分区数对管网进行划分,模块度和边界连接管段数量接近,但节点均衡性差别明显,且节点均衡性数值越小分区越合理。因此,本文选取分区方案为6个DMA分区。

3 结论

本文提出了基于自适应谱聚类算法的DMA分区方法,并矫正聚类中心。该算法有效减少了分区边界连接管的数量,从而使安装阀门和流量计的费用降低。通过模块度和节点均衡性指标评价分区结果,使分区更加合理,完成了分区合理经济的目标。并基于Ctown案例管网验证了该分区方法的可行性。该算法经济有效,能够合理地对管网进行DMA分区,提高对管网的科学管理能力。