基于LIDAR點(diǎn)云回光強(qiáng)度信息的KNN算法與BP神經(jīng)網(wǎng)絡(luò)算法分類對比研究

梁宇乾 袁希平 甘淑

摘 要：機(jī)載LIDA點(diǎn)云數(shù)據(jù)中的回光強(qiáng)度信息可對地物進(jìn)行精細(xì)分類。KNN算法和BP神經(jīng)網(wǎng)絡(luò)算法是目前比較熱門的分類算法，在數(shù)據(jù)分類方面應(yīng)用廣泛，對這兩種算法進(jìn)行了分類比較研究。將回光強(qiáng)度信息作為訓(xùn)練樣本，利用兩種不同的方法進(jìn)行分類。實(shí)驗(yàn)結(jié)果表明，BP神經(jīng)網(wǎng)絡(luò)在地物的精細(xì)分類以及邊界線提取方面要優(yōu)于KNN算法。

關(guān)鍵詞：機(jī)載LIDAR；回光強(qiáng)度；KNN算法；BP神經(jīng)網(wǎng)絡(luò)；分類

DOI：10.11907/rjdk.172941

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2018）004-0077-05

Abstract：The light intensity information of airborne LIDA point cloud data can be classified on the ground objects.At present， there are many classification methods of intensity information.In this paper， two popular algorithms are classified and compared.KNN algorithm and BP neural network algorithm are popular classification algorithms， especially in data classification.This paper use light intensity information as the training samples for classification by two different methods.The experimental results show that BP neural network is better than KNN algorithm in fine classification of ground objects and extraction of boundary lines.

Key Words：airborne LIDAR； intensity； KNN algorithm； BP neural network algorithm； classification

0 引言

機(jī)載LIDAR即激光探測與測量，是集全球定位系統(tǒng)和慣性導(dǎo)航系統(tǒng)為一體的機(jī)載激光掃描，其所測數(shù)據(jù)為數(shù)字表面模型的離散點(diǎn)表示，數(shù)據(jù)中不僅含空間三維信息，還有入射角、GPS時(shí)、激光回光強(qiáng)度等信息。其中，回光強(qiáng)度大小與目標(biāo)表面材質(zhì)、入射光角度以及反射光角度都有關(guān)系。目前，LIDAR回光強(qiáng)度等信息越來越被重視，用回光強(qiáng)度提取空間信息的應(yīng)用研究較多[1]。不同地物的反射強(qiáng)度不同，根據(jù)這一特性，可以利用回光強(qiáng)度對地物進(jìn)行分類[2-3]。

分類是數(shù)據(jù)挖掘的核心和基礎(chǔ)技術(shù)，在經(jīng)營、決策、管理、科學(xué)研究等多個(gè)領(lǐng)域有著廣泛應(yīng)用。目前熱門的分類技術(shù)有人工神經(jīng)網(wǎng)絡(luò)分類法、決策樹分類法、KNN算法分類法等。KNN分類經(jīng)過多年發(fā)展，已經(jīng)成為一種簡單、便捷、成熟、非參數(shù)的方法，廣泛應(yīng)用于文本分類、圖像分類等多個(gè)領(lǐng)域，如沈泓等[4]學(xué)者通過K聚類的方法對數(shù)據(jù)進(jìn)行整合。BP人工神經(jīng)網(wǎng)絡(luò)不僅具有自我學(xué)習(xí)能力，而且具有聯(lián)想儲(chǔ)存能力和尋找最優(yōu)解能力，是時(shí)下最熱門的一種分類方法，如顧亞風(fēng)等[5]通過神經(jīng)網(wǎng)絡(luò)對古玩圖片進(jìn)行分類；茅千千[6]利用神經(jīng)網(wǎng)絡(luò)對石油項(xiàng)目進(jìn)行綜合評價(jià)。

1 KNN算法

最近鄰算法是根據(jù)實(shí)例學(xué)習(xí)然后進(jìn)行數(shù)據(jù)分類的一種最常用的方法。

令樣本集D={x1`````xn}，在集合X中的每個(gè)樣本xi類別已知?，F(xiàn)有一個(gè)未知樣本x，在集合X中有已知樣本點(diǎn)x1，且x與x1距離最近，那么x的樣本類型就與x1相同。

K最近鄰算法（K-NearestNeighbor）是最近鄰算法的變形應(yīng)用。該算法將一個(gè)未知數(shù)據(jù)點(diǎn)n分類為與它距離最近的K個(gè)近鄰點(diǎn)中個(gè)數(shù)最多且最近的那個(gè)類別。K最近鄰算法從未知樣本點(diǎn)n開始計(jì)算，不斷擴(kuò)大分類范圍，直到包含進(jìn)K個(gè)訓(xùn)練樣本點(diǎn)結(jié)束，并把未知樣本點(diǎn)n歸為距離最近的K個(gè)訓(xùn)練樣本點(diǎn)中出現(xiàn)頻率最大的類別。一般測試樣本與訓(xùn)練樣本的距離使用歐式距離測量。圖1和圖2分別是KNN算法的一般流程和KNN算法使用步驟。

1.1 KNN中距離度量

在對數(shù)據(jù)進(jìn)行挖掘和分析過程中需要知道數(shù)據(jù)間的差異，從而判斷數(shù)據(jù)的相似性和類別。最常見的數(shù)據(jù)分析和挖掘方法是相關(guān)分析和分類、聚類算法。衡量個(gè)體差異的方法有很多，在KNN中分析數(shù)據(jù)相關(guān)性一般采取距離度量和相似度度量方法。

1.1.1 距離度量

在KNN算法中，未知數(shù)據(jù)與已知數(shù)據(jù)的相似性用距離判別，距離越大表示兩個(gè)點(diǎn)越不相似。在KNN算法中基本的距離度量有3類：明可夫斯基距離、曼哈頓距離和歐式距離。

p值是一個(gè)變量，當(dāng)p=2時(shí)就得到上述歐氏距離。

曼哈頓距離（Manhattan Distance）源于曼哈頓城市區(qū)塊距離，是將不同維度上的距離進(jìn)行求和后得到的結(jié)果。曼哈頓距離是明式距離的一種變形應(yīng)用，當(dāng)明氏距離p=1時(shí)得到距離度量公式：

切比雪夫距離（Chebyshev Distance）起源于國際象棋中國王的走法。我們知道國王每次只能往周圍的8格中走一步，如果要從棋盤中A格（x1， y1）走到B格（x2， y2）最少需要走幾步？擴(kuò)展到多個(gè)維度空間，切比雪夫距離就是明式距離的一種變形應(yīng)用，當(dāng)明氏距離中p趨向無窮大時(shí)，有公式：

由此可見歐氏距離、曼哈頓距離和切比雪夫距離都是由明可夫斯基距離變形的另一種應(yīng)用。

1.2 K值確定

在KNN算法中，所有的計(jì)算幾乎都發(fā)生在分類階段，而且分類效果的優(yōu)劣主要體現(xiàn)在K值的選取上，所以取到合適的K值至關(guān)重要。如果K值數(shù)值偏小，得到的近鄰數(shù)就會(huì)減少從而降低分類精度，同時(shí)提高了噪聲對數(shù)據(jù)干擾；如果K值數(shù)值偏大，并且未知數(shù)據(jù)樣本類型屬于訓(xùn)練數(shù)據(jù)中包含數(shù)據(jù)較少的那一類，那么在用K值進(jìn)行分類時(shí)，通常會(huì)把一些并不相似的數(shù)據(jù)包含進(jìn)來，這樣會(huì)使得噪聲增加以及分類準(zhǔn)確性降低。選取合適的K值一直是KNN的研究熱點(diǎn)。

從圖3可以看到有兩個(gè)類型的樣本數(shù)據(jù)，一類是正方形，另一類是三角形，而圓形是待分類的數(shù)據(jù)。如果K=3，離圓形距離最近的包含了2個(gè)三角形以及1個(gè)正方形，由于K值為3，于是圓形這個(gè)待分類點(diǎn)就屬于三角形。如果K=5，那么圓形最近的有2個(gè)三角形和3個(gè)正方形，于是待分類點(diǎn)屬于正方形。

K取值經(jīng)驗(yàn)規(guī)則：

（1）K一般低于訓(xùn)練樣本數(shù)的平方根。

（2）K是通過大量的樣本數(shù)據(jù)進(jìn)行測試、不同模型進(jìn)行驗(yàn)證作出的最佳選擇。

（3）當(dāng)采用固定距離指標(biāo)，那么K值可以提前確定，或者采用動(dòng)態(tài)K值[10]。樣本間類別不平衡時(shí)K值相對來說難以確定，朱響斌等[7]提供了K值的選擇方法：當(dāng)最近鄰使用歐氏距離而且樣本數(shù)據(jù)較大時(shí)，K的選擇應(yīng)當(dāng)遵從：K→：∞，K/N→0[8-9]。普遍采取交叉驗(yàn)證法，評估最小錯(cuò)誤率的K值作為最優(yōu)K值[10-11]。

（4）如果給定訓(xùn)練樣本中的類別個(gè)數(shù)是偶數(shù)，一般K會(huì)設(shè)置為一個(gè)奇數(shù)；如果類別個(gè)數(shù)為奇數(shù)，K通常設(shè)置為偶數(shù)。

2 BP神經(jīng)網(wǎng)絡(luò)

BP神經(jīng)網(wǎng)絡(luò)（Back Propagation）由以Rumelhart和McCelland為首的科學(xué)家小組于1986年提出，是一種逆向傳播誤差算法訓(xùn)練的多層前饋網(wǎng)絡(luò)，也是目前應(yīng)用最廣泛的神經(jīng)網(wǎng)絡(luò)模型之一。

BP神經(jīng)網(wǎng)絡(luò)是多層前饋神經(jīng)網(wǎng)絡(luò)，該網(wǎng)絡(luò)的主要特點(diǎn)是信號向前傳遞，誤差逆向傳播。在信號的前向傳播中，輸入的信號從輸入層開始，經(jīng)過隱含層逐層處理，直到輸出層輸出數(shù)據(jù)。每一層中的神經(jīng)元（閾值大小）只影響下一層神經(jīng)元。如果輸出層得不到理想輸出結(jié)果則進(jìn)入逆向傳播，根據(jù)所預(yù)測的誤差調(diào)整網(wǎng)絡(luò)的權(quán)值和閾值，從而使BP神經(jīng)網(wǎng)絡(luò)的預(yù)測輸出不斷向期望輸出靠近。如圖4所示，BP神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)模型包括輸入層（input）、隱層（hide layer）和輸出層（output layer）。

2.1 神經(jīng)網(wǎng)絡(luò)算法建立

基于機(jī)載LIDAR點(diǎn)云分類的BP神經(jīng)網(wǎng)絡(luò)算法建模包括BP神經(jīng)網(wǎng)絡(luò)構(gòu)建、BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練和BP神經(jīng)網(wǎng)絡(luò)分類，算法流程如圖5所示。

2.2 神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程

設(shè)X2，…，Xn是BP神經(jīng)網(wǎng)絡(luò)的輸入值，Y1，Y2，…，Yn ωjk是BP神經(jīng)網(wǎng)絡(luò)的預(yù)測值， ωij和ωjk為BP神經(jīng)網(wǎng)絡(luò)權(quán)值。當(dāng)神經(jīng)網(wǎng)絡(luò)輸入節(jié)點(diǎn)數(shù)為n、輸出節(jié)點(diǎn)數(shù)為m時(shí)，整個(gè)網(wǎng)絡(luò)就表示一個(gè)從n個(gè)自變量到m個(gè)因變量的函數(shù)關(guān)系。

BP神經(jīng)網(wǎng)絡(luò)在做分類預(yù)測前首先要訓(xùn)練主動(dòng)學(xué)習(xí)能力。BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練步驟：

（1）網(wǎng)絡(luò)初始化。根據(jù)分類所需類別以及輸出結(jié)果種類，確定網(wǎng)絡(luò)輸入層節(jié)點(diǎn)數(shù)n、隱含層節(jié)點(diǎn)數(shù)1、輸出層節(jié)點(diǎn)數(shù)m，對輸入層、隱含層和輸出層進(jìn)行初始化處理，各個(gè)神經(jīng)元之間的連接權(quán)值ωij，ωjk，初始化隱含層閾值a，輸出層閾值b，給定神經(jīng)元激勵(lì)函數(shù)以及學(xué)習(xí)速率。

（2）隱含層輸出計(jì)算。根據(jù)輸入向量X、輸入層和隱含層間連接權(quán)值ωij以及隱含層閾值a，計(jì)算隱含層輸出H：

（7）判斷算法迭代是否結(jié)束，若沒有結(jié)束，返回步驟（2）。

3 分類結(jié)果與對比研究

試驗(yàn)區(qū)為云南某湖泊的灘涂機(jī)載LIDAR點(diǎn)云數(shù)據(jù)，圖6是該區(qū)域的平面點(diǎn)云圖。由這幅點(diǎn)云圖把該區(qū)域大致分為兩類：水域點(diǎn)和陸地點(diǎn)。圖中藍(lán)色點(diǎn)為已知水域點(diǎn)，棕色點(diǎn)為陸地點(diǎn)，灰色點(diǎn)代表未分類的點(diǎn)云數(shù)據(jù)（如需看彩圖，請與編輯部聯(lián)系）。

3.1 KNN分類

首先，該區(qū)域的點(diǎn)云數(shù)量約為10萬個(gè)，選取已知類型的8 000個(gè)點(diǎn)為訓(xùn)練數(shù)據(jù)。其次，通過多次實(shí)驗(yàn)取K值。表1是K值大小與測試集準(zhǔn)確率間的關(guān)系。由表1可以看出，K值取15時(shí)測試集的準(zhǔn)確率最高。隨著K值的增加，測試集的準(zhǔn)確率逐步下降。圖7為該實(shí)驗(yàn)區(qū)KNN算法分類效果。

3.2 BP神經(jīng)網(wǎng)絡(luò)分類

用已知分類點(diǎn)進(jìn)行訓(xùn)練并且進(jìn)行數(shù)據(jù)測試，圖8是神經(jīng)網(wǎng)絡(luò)在訓(xùn)練數(shù)據(jù)過程中迭代次數(shù)和訓(xùn)練誤差的關(guān)系。由圖8可以看出，隨著迭代次數(shù)的增加，訓(xùn)練誤差迅速下降，在第6次迭代趨于平穩(wěn)，但仍有下降趨勢，誤差無限趨近于0.1。

圖9是通過BP神經(jīng)網(wǎng)絡(luò)分類后得到的點(diǎn)云分類效果。從圖中可以看到，通過BP網(wǎng)絡(luò)分類可以有效區(qū)分陸地點(diǎn)和水域點(diǎn)。在水域點(diǎn)中有部分點(diǎn)云數(shù)據(jù)是算法中認(rèn)為的陸地點(diǎn)，造成這種情況原因的是因?yàn)樗蜉^淺，機(jī)載LIDAR的激光束穿透能力很強(qiáng)，激光束穿透水面打到水面底部巖石或土地上，造成分類錯(cuò)誤。

3.3 對比研究

通過圖10和圖11對比發(fā)現(xiàn)，KNN算法和BP神經(jīng)網(wǎng)絡(luò)算法都能較好地將點(diǎn)云絕大部分的地面點(diǎn)和水域點(diǎn)分開，但是通過對比發(fā)現(xiàn)有以下3點(diǎn)可以看出KNN算法和BP神經(jīng)網(wǎng)絡(luò)算法的不同[9-10]：

（1）兩幅圖中紅框所標(biāo)注出的1區(qū)、3區(qū)、4區(qū)，KNN算法不能很好判別，把一些地面點(diǎn)判別為水域點(diǎn)。雖然神經(jīng)網(wǎng)絡(luò)也出現(xiàn)類似情況，但是通過比較發(fā)現(xiàn)，BP神經(jīng)網(wǎng)絡(luò)的分類更為精細(xì)。

（2）對于2區(qū)來說，KNN算法的分類效果好于BP神經(jīng)網(wǎng)絡(luò)，BP神經(jīng)網(wǎng)絡(luò)會(huì)把一些明顯的水域點(diǎn)判別為地面點(diǎn)。這里有兩個(gè)原因：①KNN算法是通過近鄰點(diǎn)分類；②由于機(jī)載LIDAR的激光束穿過水面，直接打在了水底造成了誤分類。

（3）在區(qū)分地物邊界方面，BP神經(jīng)網(wǎng)絡(luò)顯然比KNN算法更出色。通過對比不難看出，KNN算法對明顯的邊界不能很好地區(qū)分。

4 結(jié)語

通過該實(shí)驗(yàn)對比發(fā)現(xiàn)，BP神經(jīng)網(wǎng)絡(luò)算法在分類方面比KNN算法更為精細(xì)，尤其表現(xiàn)在對邊界線的提取方面。這取決于BP神經(jīng)網(wǎng)絡(luò)利用積極學(xué)習(xí)的方法，擁有自動(dòng)學(xué)習(xí)能力，并且能充分逼近復(fù)雜的非線性關(guān)系。反觀KNN算法，其采用懶惰學(xué)習(xí)方法，導(dǎo)致對擁有海量數(shù)據(jù)和類別多的數(shù)據(jù)不能實(shí)現(xiàn)很好的分類。

參考文獻(xiàn)：

[1] ACKERMANN F. Airborne laser scanning-present status and future expectation[J].ISPRS Journal of Photogrammetry & Remote Sensing，1999（54）：64-67.

[2] 左志權(quán).顧及點(diǎn)云類別屬性與地形結(jié)構(gòu)特征的機(jī)載LiDAR數(shù)據(jù)濾波方法[D].武漢：武漢大學(xué)， 2011.

[3] 賈廣帥.機(jī)載激光雷達(dá)數(shù)據(jù)特點(diǎn)和濾波方法研究[D].青島：山東科技大學(xué)，2007.

[4] 沈泓，劉順.基于K-means聚類算法的數(shù)據(jù)分析模型應(yīng)用研究[J].軟件導(dǎo)刊，2017，16（3）：103-107.

[5] 顧亞風(fēng)，葉學(xué)義.基于卷積神經(jīng)網(wǎng)絡(luò)的古玩圖片分類方法[J].軟件導(dǎo)刊，2017，16（5）：174-178.

[6] 茅茜茜.BP神經(jīng)網(wǎng)絡(luò)在石油項(xiàng)目經(jīng)濟(jì)效益綜合評價(jià)中的應(yīng)用[J].軟件導(dǎo)刊，2017，16（4）：145-148.

[7] 朱響斌.一種基于八叉樹的三維實(shí)體內(nèi)部可視化技術(shù)[J].中國圖象圖形學(xué)報(bào)，2002，7（3）：229-233.

[8] LOFTSGAARDEN D O， QUESENBERRY C P.A nonparametric estimate of multivariate density function[J].Ann Math Statist，1965，36（3）：1049-1051.

[9] COVER T M，HART P E.Nearest neighbor pattern classification[J].IEEE Trans Inform Theory，1968，13（1）：21-27.

[10] LACHENBRUCH P A，MICKEY M R.Estimation of error rates in discriminant analysis[J].Technometrics，1968，10（1）：1-11.

[11] STONE M. Cross validation： a review， math operationsforschung und statist[J].Series Statistics，1978，9（1）：127-139.

（責(zé)任編輯：杜能鋼）