并行密度聚类算法在河流数字化并行提取中的应用研究

赵 静

（辽宁省鞍山市岫岩县水利局，辽宁鞍山114300）

并行密度聚类算法在河流数字化并行提取中的应用研究

赵 静

（辽宁省鞍山市岫岩县水利局，辽宁鞍山114300）

本文采用并行密度聚类算法，对辽宁东部某区域河流进行数字化进行并行提取，并结合区域实地调查河流数据，对比分析河流数字化提取的精度。研究结果表明：并行密度聚类算法可实现河流数字化提取的并行计算，相比于传统算法（串行计算），该算法可提高计算效率48%，和区域实地调查河流特征数据对比，其河流长度提取误差可在20%以内，河长比降提取误差可在30%以内。研究成果对于区域河流数字化提取方法提供参考价值。关键词:并行密度聚类算法；河流数字化提取；并行计算；河流提取精度验证

1 前言

当前，地理信息技术以及计算能力的快速发展，河流的数字化提取已经逐步成为区域河流调查和评价的主要方法，许多学者在河流数字化提取中进行相关研究，取得一定研究成果［1-5］，但是这些河流提取往往研究区域面积较小，河流提取数量较少，而对于大尺度区域河流的数字化提取，计算量较大，提取一次计算速率较慢，且精度不高，为此有学者引入并行算法对河流数字化进行并行提取［6-10］，大大提高了河流数字化提取的速率和精度，但是传统的并行算法未能考虑河流提取高维的复杂性，在计算时间尺度上存在差异，为此有学者引入基于密度的并行聚类算法，对传统的并行算法进行改进，并行密度聚类算法将时间复杂度引入模型计算值，可大大提高模型求解的速率和精度。但并行密度聚类算法还未在河流数字化提取中得到应用，为此本文引入并行密度聚类算法，以辽宁鞍山为研究区域，对区域内的河流进行数字化提取，并结合区域实地调查的河流特征数据，对比分析河流提取的精度。研究成果对于区域河流数字化提取方法提供参考价值。

2 并行密度聚类算法原理

河流数字化提取的方法，已有许多成熟的研究成果，本文则是针对河流并行提取计算的主要原理进行介绍。并行密度聚类算法通过计算距离与密度函数之间的时间复杂度来进行密度聚类的并行计算，对于N唯空间的S个样本的数据集合｛x1，x2，….xn｝，定义样本Xi处的计算势度函数为：

式中，pi（0）表示为势度计算函数，n表示为样本的个数，a表示为相邻区域的搜索半径，在通常一般被设定为常数，但是这样很难反映样本数据在空间上的分布特征，为此并行密度聚类算法设置有效相邻半径来计算搜索半径，计算公式为：

在公式（2）中势度计算函数主要以指数运算为基础，在样本数据量较大的情况下难以保证计算速度，为此，并行密度聚类算法设定样本并行计算的密度函数，计算公式为：

式中，D为计算的密度函数，fd为密度系数，其中i =1，2….n。对于密度函数需要进行样本初始密度函数的计算，初始密度计算函数的公式为：

在样本空间密度函数计算完成后，并行密度聚类算法运用欧几距离矩阵方程进行并行计算，距离并行计算的方程为：

在完成距离并行计算后，需要对并行计算的综合复杂度进行计算，计算公式为：

在并行计算综合复杂度完成后，并行密度聚类算法采用聚类指数对综合复杂度进行修正计算，修正后的综合复杂度的表达式为：

式中，K表示为聚类指数。

3 实例应用

3.1 不同算法的试验结果对比

为对比并行聚类算法和传统算法的计算收敛速度，分别采用试验的方式，对比不同算法的计算收敛速度。试验的样本数为4000，横向维数为20，分别采用并行聚类算法和传统算法进行计算，并对比不同算法的耗费时间，对比试验结果见表1。

表1 不同算法的计算收敛速度对比

表1为不同算法计算收敛速度对比，从表中可以看出，在相同的试验样本数和横向维数下，基于并行密度聚类算法的计算时间为15.3分钟，而传统算法的计算时间为38.7分钟，两种算法之间的时间差为23.4分钟，两中算法时间的相对值为48%，说明并行密度聚类算法可将传统算法河流提取的效率提高48%，主要原因是传统算法采用串行算法进行逐个进行计算，而并行密度聚类算法可实现所有样本的并行计算，因而可提高河流提取的效率。

3.2 基于并行密度聚类算法的河流数字化提取

以辽宁东部某区域为研究实例，采用地理信息技术对河流进行数字化提取，并基于并行密度聚类算法对河流提取进行并行计算，其中在河流数字化提取时，基于区域数字高程网格数据（图1（a）），采用D8算法对河流的流向进行判定，判定结果见图1（b），在完成区域内各网格河流流向判定后，采用栅格汇流累计模型结合并行密度聚类算法对区域内所有网格的汇流累计量进行并行计算，计算结果见图1（c），在完成区域内所有网格的汇流累计量计算后，对河流进行数字化提取，部分河流数字化提取结果见图1（d）。

3.3 河流数字化提取精度验证

为对河流数字化提取的精度进行验证，结合实地勘察的10条河流数据，对比分析河流数字化提取的精度，对其提取结果进行验证，验证结果见表2和图2。

表2 基于并行密度聚类算法的河流数字化提取精度验证

图1 河流数字化提取结果

图2 河流数字化与调查河段数据对比分析结果

从表2中可以看出，数字化提取的10条河流的河长和实地调查的河长之间的相对误差在8.20%～19.64%之间，相对误差在20%以内，绝对误差在0.9～2.9km之间，绝对误差小于3.0km。从河长比降提取值可以看出，10条实地调查的河流的比降在5.4‰～12.5‰之间，其和数字化提取的河流比降之间的相对误差在13.59%～29.33%之间，河段比降相对误差在30%以内。从河段比降的绝对误差可以看出，数字化提取的河段比降和实地调查的河段比降之间的绝对误差1‰～2.3‰，虽然绝对误差值较小，但是由于调查河段的比降较小，在5.4‰～12.5‰之间，因此数字化提取的河段比降和实地调查的河段比降之间绝对误差也相对较大。图2为河流数字化提取的河长和河段比降与调查的河段河长和比降之间的对比结果，从图中可以看出，数字化提取的河长与调查河段河长之间的确定系数可达到0.7842，表明两个河长之间有较好的正相关性。而河段比降之间的确定性系数达到0.5948，也具有一定的正相关性。综上所述，基于并行密度聚类算法提取的河长和河段比降和实地调查的河段河长和河段比降之间具有一定相关度，河长的提取精度要好于河段比降的提取精度。

4 结论

本文采用并行密度聚类算法，对河流进行数字化的并行提取，并验证河流数字化提取的精度，结论如下。

（1）并行密度聚类算法，可以实现大尺度区域河流数字化的并行提取，相比于传统算法（串行计算），可以提高大区域尺度河流提取计算的效率；

（2）基于并行密度聚类算法的河流数字化并行提取的河长相对误差小于比降提取的误差，河长提取误差在20%以内，但河长比降误差较大，在30%以内，在具体应用时，还应该进行比降修正。

［1］董婷婷.辽宁省小型河流空间分布及属性信息研究［J］.水利规划与设计，2015（03）：23-25+38.

［2］王鑫.大凌河农村段河道生态治理模式研究［J］.水利技术监督，2015（03）：34-36.

［3］李纪人，黄诗峰.空间信息技术与防洪减灾现代化［J］.中国水利水电科学院学报，2004（03）.

［4］闻兆海，谢忠.基于多级网格模型的LiDAR数据河流边缘提取算法［J］.地理空间信息，2016（07）：17-19.

［5］陆丁滒，吴虹，郭琪，陈梦杰.基于GoogleEarth影像的漓江水系形态特征提取与分析［J］.国土资源遥感，2016（02）：161-167.

［6］江岭，刘学军，阳建逸，刘凯，宋效东.格网DEM水系提取并行算法研究［J］.地理与地理信息科学，2013（04）：62-66.

［7］王玉着，刘修国，张唯.统一设备计算架构下的栅格河网提取并行算法［J］.计算机应用，2015（04）：960-963+967.

［8］王春，江岭，陈泰生，杨灿灿.基于Pfafstetter规则的流域编码算法并行化方法［J］.地球信息科学学报，2015（05）：556-561.

［9］刘永和，冯锦明，徐文鹏.分布式水文模型的GPU并行化及快速模拟技术［J］.水文，2015（04）：20-26.

［10］王玉着，刘修国，张唯.并行化多流向策略的栅格河网提取算法［J］.武汉大学学报（信息科学版），2015（12）：1646-1652+1682.

TP301

A

1008-1305（2017）01-0039-03

DO I:10.3969/j.issn.1008-1305.2017.01.013

2016-08-05

赵 静（1982年—），女，工程师。