并行密度聚類算法在河流數(shù)字化并行提取中的應(yīng)用研究

趙 靜

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

并行密度聚類算法在河流數(shù)字化并行提取中的應(yīng)用研究

趙 靜

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

本文采用并行密度聚類算法，對遼寧東部某區(qū)域河流進(jìn)行數(shù)字化進(jìn)行并行提取，并結(jié)合區(qū)域?qū)嵉卣{(diào)查河流數(shù)據(jù)，對比分析河流數(shù)字化提取的精度。研究結(jié)果表明：并行密度聚類算法可實(shí)現(xiàn)河流數(shù)字化提取的并行計(jì)算，相比于傳統(tǒng)算法（串行計(jì)算），該算法可提高計(jì)算效率48%，和區(qū)域?qū)嵉卣{(diào)查河流特征數(shù)據(jù)對比，其河流長度提取誤差可在20%以內(nèi)，河長比降提取誤差可在30%以內(nèi)。研究成果對于區(qū)域河流數(shù)字化提取方法提供參考價值。關(guān)鍵詞:并行密度聚類算法；河流數(shù)字化提?。徊⑿杏?jì)算；河流提取精度驗(yàn)證

1 前言

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

2 并行密度聚類算法原理

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

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

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

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

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

在完成距離并行計(jì)算后，需要對并行計(jì)算的綜合復(fù)雜度進(jìn)行計(jì)算，計(jì)算公式為：

在并行計(jì)算綜合復(fù)雜度完成后，并行密度聚類算法采用聚類指數(shù)對綜合復(fù)雜度進(jìn)行修正計(jì)算，修正后的綜合復(fù)雜度的表達(dá)式為：

式中，K表示為聚類指數(shù)。

3 實(shí)例應(yīng)用

3.1 不同算法的試驗(yàn)結(jié)果對比

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

表1 不同算法的計(jì)算收斂速度對比

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

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

以遼寧東部某區(qū)域?yàn)檠芯繉?shí)例，采用地理信息技術(shù)對河流進(jìn)行數(shù)字化提取，并基于并行密度聚類算法對河流提取進(jìn)行并行計(jì)算，其中在河流數(shù)字化提取時，基于區(qū)域數(shù)字高程網(wǎng)格數(shù)據(jù)（圖1（a）），采用D8算法對河流的流向進(jìn)行判定，判定結(jié)果見圖1（b），在完成區(qū)域內(nèi)各網(wǎng)格河流流向判定后，采用柵格匯流累計(jì)模型結(jié)合并行密度聚類算法對區(qū)域內(nèi)所有網(wǎng)格的匯流累計(jì)量進(jìn)行并行計(jì)算，計(jì)算結(jié)果見圖1（c），在完成區(qū)域內(nèi)所有網(wǎng)格的匯流累計(jì)量計(jì)算后，對河流進(jìn)行數(shù)字化提取，部分河流數(shù)字化提取結(jié)果見圖1（d）。

3.3 河流數(shù)字化提取精度驗(yàn)證

為對河流數(shù)字化提取的精度進(jìn)行驗(yàn)證，結(jié)合實(shí)地勘察的10條河流數(shù)據(jù)，對比分析河流數(shù)字化提取的精度，對其提取結(jié)果進(jìn)行驗(yàn)證，驗(yàn)證結(jié)果見表2和圖2。

表2 基于并行密度聚類算法的河流數(shù)字化提取精度驗(yàn)證

圖1 河流數(shù)字化提取結(jié)果

圖2 河流數(shù)字化與調(diào)查河段數(shù)據(jù)對比分析結(jié)果

從表2中可以看出，數(shù)字化提取的10條河流的河長和實(shí)地調(diào)查的河長之間的相對誤差在8.20%～19.64%之間，相對誤差在20%以內(nèi)，絕對誤差在0.9～2.9km之間，絕對誤差小于3.0km。從河長比降提取值可以看出，10條實(shí)地調(diào)查的河流的比降在5.4‰～12.5‰之間，其和數(shù)字化提取的河流比降之間的相對誤差在13.59%～29.33%之間，河段比降相對誤差在30%以內(nèi)。從河段比降的絕對誤差可以看出，數(shù)字化提取的河段比降和實(shí)地調(diào)查的河段比降之間的絕對誤差1‰～2.3‰，雖然絕對誤差值較小，但是由于調(diào)查河段的比降較小，在5.4‰～12.5‰之間，因此數(shù)字化提取的河段比降和實(shí)地調(diào)查的河段比降之間絕對誤差也相對較大。圖2為河流數(shù)字化提取的河長和河段比降與調(diào)查的河段河長和比降之間的對比結(jié)果，從圖中可以看出，數(shù)字化提取的河長與調(diào)查河段河長之間的確定系數(shù)可達(dá)到0.7842，表明兩個河長之間有較好的正相關(guān)性。而河段比降之間的確定性系數(shù)達(dá)到0.5948，也具有一定的正相關(guān)性。綜上所述，基于并行密度聚類算法提取的河長和河段比降和實(shí)地調(diào)查的河段河長和河段比降之間具有一定相關(guān)度，河長的提取精度要好于河段比降的提取精度。

4 結(jié)論

本文采用并行密度聚類算法，對河流進(jìn)行數(shù)字化的并行提取，并驗(yàn)證河流數(shù)字化提取的精度，結(jié)論如下。

（1）并行密度聚類算法，可以實(shí)現(xiàn)大尺度區(qū)域河流數(shù)字化的并行提取，相比于傳統(tǒng)算法（串行計(jì)算），可以提高大區(qū)域尺度河流提取計(jì)算的效率；

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

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

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

［3］李紀(jì)人，黃詩峰.空間信息技術(shù)與防洪減災(zāi)現(xiàn)代化［J］.中國水利水電科學(xué)院學(xué)報(bào)，2004（03）.

［4］聞?wù)缀?，謝忠.基于多級網(wǎng)格模型的LiDAR數(shù)據(jù)河流邊緣提取算法［J］.地理空間信息，2016（07）：17-19.

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

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

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

［8］王春，江嶺，陳泰生，楊燦燦.基于Pfafstetter規(guī)則的流域編碼算法并行化方法［J］.地球信息科學(xué)學(xué)報(bào)，2015（05）：556-561.

［9］劉永和，馮錦明，徐文鵬.分布式水文模型的GPU并行化及快速模擬技術(shù)［J］.水文，2015（04）：20-26.

［10］王玉著，劉修國，張唯.并行化多流向策略的柵格河網(wǎng)提取算法［J］.武漢大學(xué)學(xué)報(bào)（信息科學(xué)版），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年—），女，工程師。