并行密度聚類算法在河流數字化并行提取中的應用研究

趙 靜

（遼寧省鞍山市岫巖縣水利局，遼寧鞍山114300）

并行密度聚類算法在河流數字化并行提取中的應用研究

趙 靜

（遼寧省鞍山市岫巖縣水利局，遼寧鞍山114300）

本文采用并行密度聚類算法，對遼寧東部某區(qū)域河流進行數字化進行并行提取，并結合區(qū)域實地調查河流數據，對比分析河流數字化提取的精度。研究結果表明：并行密度聚類算法可實現河流數字化提取的并行計算，相比于傳統(tǒng)算法（串行計算），該算法可提高計算效率48%，和區(qū)域實地調查河流特征數據對比，其河流長度提取誤差可在20%以內，河長比降提取誤差可在30%以內。研究成果對于區(qū)域河流數字化提取方法提供參考價值。關鍵詞:并行密度聚類算法；河流數字化提取；并行計算；河流提取精度驗證

1 前言

當前，地理信息技術以及計算能力的快速發(fā)展，河流的數字化提取已經逐步成為區(qū)域河流調查和評價的主要方法，許多學者在河流數字化提取中進行相關研究，取得一定研究成果［1-5］，但是這些河流提取往往研究區(qū)域面積較小，河流提取數量較少，而對于大尺度區(qū)域河流的數字化提取，計算量較大，提取一次計算速率較慢，且精度不高，為此有學者引入并行算法對河流數字化進行并行提取［6-10］，大大提高了河流數字化提取的速率和精度，但是傳統(tǒng)的并行算法未能考慮河流提取高維的復雜性，在計算時間尺度上存在差異，為此有學者引入基于密度的并行聚類算法，對傳統(tǒng)的并行算法進行改進，并行密度聚類算法將時間復雜度引入模型計算值，可大大提高模型求解的速率和精度。但并行密度聚類算法還未在河流數字化提取中得到應用，為此本文引入并行密度聚類算法，以遼寧鞍山為研究區(qū)域，對區(qū)域內的河流進行數字化提取，并結合區(qū)域實地調查的河流特征數據，對比分析河流提取的精度。研究成果對于區(qū)域河流數字化提取方法提供參考價值。

2 并行密度聚類算法原理

河流數字化提取的方法，已有許多成熟的研究成果，本文則是針對河流并行提取計算的主要原理進行介紹。并行密度聚類算法通過計算距離與密度函數之間的時間復雜度來進行密度聚類的并行計算，對于N唯空間的S個樣本的數據集合｛x1，x2，….xn｝，定義樣本Xi處的計算勢度函數為：

式中，pi（0）表示為勢度計算函數，n表示為樣本的個數，a表示為相鄰區(qū)域的搜索半徑，在通常一般被設定為常數，但是這樣很難反映樣本數據在空間上的分布特征，為此并行密度聚類算法設置有效相鄰半徑來計算搜索半徑，計算公式為：

在公式（2）中勢度計算函數主要以指數運算為基礎，在樣本數據量較大的情況下難以保證計算速度，為此，并行密度聚類算法設定樣本并行計算的密度函數，計算公式為：

式中，D為計算的密度函數，fd為密度系數，其中i =1，2….n。對于密度函數需要進行樣本初始密度函數的計算，初始密度計算函數的公式為：

在樣本空間密度函數計算完成后，并行密度聚類算法運用歐幾距離矩陣方程進行并行計算，距離并行計算的方程為：

在完成距離并行計算后，需要對并行計算的綜合復雜度進行計算，計算公式為：

在并行計算綜合復雜度完成后，并行密度聚類算法采用聚類指數對綜合復雜度進行修正計算，修正后的綜合復雜度的表達式為：

式中，K表示為聚類指數。

3 實例應用

3.1 不同算法的試驗結果對比

為對比并行聚類算法和傳統(tǒng)算法的計算收斂速度，分別采用試驗的方式，對比不同算法的計算收斂速度。試驗的樣本數為4000，橫向維數為20，分別采用并行聚類算法和傳統(tǒng)算法進行計算，并對比不同算法的耗費時間，對比試驗結果見表1。

表1 不同算法的計算收斂速度對比

表1為不同算法計算收斂速度對比，從表中可以看出，在相同的試驗樣本數和橫向維數下，基于并行密度聚類算法的計算時間為15.3分鐘，而傳統(tǒng)算法的計算時間為38.7分鐘，兩種算法之間的時間差為23.4分鐘，兩中算法時間的相對值為48%，說明并行密度聚類算法可將傳統(tǒng)算法河流提取的效率提高48%，主要原因是傳統(tǒng)算法采用串行算法進行逐個進行計算，而并行密度聚類算法可實現所有樣本的并行計算，因而可提高河流提取的效率。

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

以遼寧東部某區(qū)域為研究實例，采用地理信息技術對河流進行數字化提取，并基于并行密度聚類算法對河流提取進行并行計算，其中在河流數字化提取時，基于區(qū)域數字高程網格數據（圖1（a）），采用D8算法對河流的流向進行判定，判定結果見圖1（b），在完成區(qū)域內各網格河流流向判定后，采用柵格匯流累計模型結合并行密度聚類算法對區(qū)域內所有網格的匯流累計量進行并行計算，計算結果見圖1（c），在完成區(qū)域內所有網格的匯流累計量計算后，對河流進行數字化提取，部分河流數字化提取結果見圖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）并行密度聚類算法，可以實現大尺度區(qū)域河流數字化的并行提取，相比于傳統(tǒng)算法（串行計算），可以提高大區(qū)域尺度河流提取計算的效率；

（2）基于并行密度聚類算法的河流數字化并行提取的河長相對誤差小于比降提取的誤差，河長提取誤差在20%以內，但河長比降誤差較大，在30%以內，在具體應用時，還應該進行比降修正。

［1］董婷婷.遼寧省小型河流空間分布及屬性信息研究［J］.水利規(guī)劃與設計，2015（03）：23-25+38.

［2］王鑫.大凌河農村段河道生態(tài)治理模式研究［J］.水利技術監(jiān)督，2015（03）：34-36.

［3］李紀人，黃詩峰.空間信息技術與防洪減災現代化［J］.中國水利水電科學院學報，2004（03）.

［4］聞兆海，謝忠.基于多級網格模型的LiDAR數據河流邊緣提取算法［J］.地理空間信息，2016（07）：17-19.

［5］陸丁滒，吳虹，郭琪，陳夢杰.基于GoogleEarth影像的漓江水系形態(tài)特征提取與分析［J］.國土資源遙感，2016（02）：161-167.

［6］江嶺，劉學軍，陽建逸，劉凱，宋效東.格網DEM水系提取并行算法研究［J］.地理與地理信息科學，2013（04）：62-66.

［7］王玉著，劉修國，張唯.統(tǒng)一設備計算架構下的柵格河網提取并行算法［J］.計算機應用，2015（04）：960-963+967.

［8］王春，江嶺，陳泰生，楊燦燦.基于Pfafstetter規(guī)則的流域編碼算法并行化方法［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年—），女，工程師。