基于加權K-近鄰分類的非視距識別方法研究

韋子輝 解云龍 王世昭 葉興躍 張要發 方立德*

①(河北大學質量技術監督學院 保定 071002)

②(計量儀器與系統國家地方聯合工程研究中心 保定 071002)

③(保定市產業計量工程技術研究中心 保定 071002)

1 引言

近年來，室內定位在技術手段、定位精度、適用范圍方面取得了長足的進步，也逐漸滲透到人們的日常生活中，例如養老院中對老人的看護、辦公區域對工作人員的管理、火災救援等。在無線定位技術中，超寬帶定位技術具有時域分辨率高、抗多徑干擾能力強、穿透能力強的特點[1，2]，相比于超聲波定位、紅外線定位、射頻識別定位(Radio Frequency IDentification， RFID)等定位技術可實現更高精度定位，在精確定位應用中具有極大潛力。

由于脈沖超寬帶(Impulsive Radio Ultra-Wide-Band， IR-UWB)具有一系列的優良特性，越來越多的研究人員投身于超寬帶定位技術的研究，國外多家公司進行超寬帶定位芯片的研究，其中脫穎而出的是愛爾蘭DecaWave公司生產的DW1000定位射頻芯片，具有較高的精確度。在定位系統中，視距情況下，直達信號被準確識別，定位精度較高，但在實際應用中，室內環境復雜，會產生較大的定位誤差，而誤差的主要來源是遮擋造成時延引起的誤差和信號反射引起直達信號的錯誤判斷[3]。如果采用錯誤的直達信號，嚴重影響定位性能，故需要提前進行非視距(Non-Line-Of-Sight， NLOS)的判斷，對NLOS信道進行剔除，使用視距(Line-Of-Sight， LOS)環境信道計算，得到更高精度的位置估計。因此，NLOS環境的識別一直是超寬帶定位領域的一個重要研究方向。

NLOS識別算法對IR-UWB定位意義重大，是解決NLOS干擾的最直接手段，其中傳統的識別技術可以分為3類，即基于距離估計的方法、基于信道沖擊響應的方法和基于位置估計的方法。基于距離估計的方法主要使用概率密度函數或范圍估計的方法來區分LOS和NLOS。Yan等人[4]利用測量距離的貝葉斯先驗概率，用貝葉斯序貫檢驗來區分NLOS。王長強等人[5]將卡爾曼濾波與測距殘差相結合，通過計算觀測值與卡爾曼濾波預測值之間的差，與設定閾值比較后識別有無NLOS存在。基于距離估計的方法在坐標計算之前識別NLOS，而基于位置估計的方法則在位置估計過程中識別NLOS，甚至會依次使用計算得到的位置坐標進行NLOS識別。Casas等人[6]在存在可用冗余距離測量值的情況下，通過比較距離值的不同子集產生的位置來識別NLOS，當沒有冗余距離測量值或多個距離測量值屬于NLOS時，該方法無效。Gustafson等人[7]通過利用間接路徑測量所包含的地理位置信息來判斷NLOS，不需要先驗知識是此類方法的優點，但由于附加約束條件并不總是存在，因此很難確保有效識別NLOS。過去幾年，基于信道沖激響應(Channel Impulse Response， CIR)進行NLOS識別發展迅速，沖激響應波形受傳輸路徑影響明顯，不同的傳播路徑有不同沖激響應，故可以從沖激響應波形中提取特征參量進行NLOS識別。孫希延等人[8]以此為根據建立均方根時延擴展和平均超量延遲的概率分布模型作為標準，將信道瞬時分布與標準分布間的KL散度(Kullback-Leibler Distance)做似然比檢驗進行NLOS識別。隨著機器學習技術在無線通信中的應用，支持向量機[9](Support Vector Machine，SVM)、支持向量數據描述算法[10](Support Vector Data Description， SVDD)、導入向量機[11](Import Vector Machine， IVM)、決策樹[12]等方法被應用到NLOS識別中，并顯示出較好的識別效果，但實際應用中，這些算法訓練比較困難，設計高效、輕量級的識別方案非常困難。

本文以構建一個識別準確率較高、環境適用性較強、計算復雜度較低的實時NLOS識別方法為目的，從接收信號中截取有用信號段，對有用信號段進行特征提取，選取合理特征參量集進行信號分類。本文提出一種新型特征參量–飽和度，并與前人提出的特征參量結合，利用Relief算法和互信息特征選擇(Mutual Information Feature Selection，MIFS)算法選擇最優特征子集，根據特征與分類標簽的相關性確定特征權重，提出了一種基于加權K-近鄰(Weighted K-Nearest Neighbor， WKNN)分類的多特征參量NLOS識別方法，建立NLOS識別系統模型。實驗分析了訓練樣本數和K值的選取對WKNN分類性能的影響，綜合確定了優選方案。實驗表明：本算法在一些復雜環境中仍能獲得較高的識別準確率。本系統流程如圖1所示。

圖1 NLOS識別方法流程

2 基于CIR波形的NLOS特征量構建

IR-UWB信道沖激響應波形易受傳播路徑影響，在NLOS傳播環境下，障礙物對信號的吸收和反射都會投射到波形中，故可以利用數據挖掘在波形中提取特征參量，從頻域和時域方面進行分析。在NLOS信道傳播下，信號穿過障礙物，信號衰減會造成最大振幅和總能量的減小，信號阻塞會造成上升時間、平均附加時延和均方根時延的增大，信號發散會造成偏度和峭度的變化，故可以將這些特征參量作為NLOS狀態識別的依據。數據挖掘是一種有效的工具，它可以執行復雜的計算過程，如大數據集中確定模式，從而可以成功地檢測脈沖信號分類所需的有意義的信息和模式。Mucchi等人[13]提出利用峭度(kurtosis，k)對NLOS和LOS信道進行區分，并且對接收信號的質量進行排序，但成功率僅達到了74%。張浩等人[14]提出一種基于偏度的NLOS區分算法，該算法在室內辦公環境中識別率較高，但在室內其他環境或者室外環境中識別率比較低。利用單一特征參量進行NLOS識別性能不是很好，故很多學者提出多種特征參量融合進行識別。紀元法等人[15]提出一種基于峭度和均方根時延擴展聯合似然比檢驗區分NLOS狀態的算法，獲得較高的準確率。Guvenc等人[16]提出了一種新的基于峭度、平均附加時延和均方根時延擴展等多徑信道統計量融合的非視距識別技術，正確識別率可達90%以上。上述特征參量的數學模型如表1所示。其 中h(t) 為 信 道 沖 激 響 應 函 數，μ|h|，σ|h|分 別 為|h(t)|的平均值和標準差。

表1 各特征參量的數學模型

以上特征參量是針對整個CIR波形的特征參量，沒有針對某一傳播路徑進行分析，而傳播中的定位信號第1路徑的判斷對定位精度有較大影響，故在識別NLOS信號中可以將第1路徑的衰減程度作為一種識別特征。

在LOS傳播環境下，第1條識別路徑即為直射路徑，也是最強路徑，在NLOS傳播環境下，直射路徑在傳播過程中要穿過1個或多個障礙物，由于障礙物的相對介電常數大于1，所以會造成一定程度的衰減，為減少接收信號中噪聲部分對NLOS識別的干擾，設置噪聲閾值，如圖2所示，藍色線即噪聲閾值，該閾值的設定既考慮了噪聲影響，也考慮了第1路徑嚴重衰減低于閾值而不能識別的可能。本文考慮在NLOS環境傳播下障礙物對第1路徑的吸收，對第1路徑的衰減程度做一個量化，故提出飽和度S。表達式如式(1)所示

圖2 CIR波形閾值設置示意圖

3 特征選擇與分類算法

3.1 特征選擇

如圖3所示為室內特征參量箱線圖，可以看出在室內傳播信道下，上升時間和飽和度箱圖重合部分很少，區分傳播信道的效果較好；最大振幅、總能量、平均附加時延只能部分區分，效果不明顯；偏度、峭度、均方根時延箱圖重合部分很多，基本無法區分。但不同的信道會產生不同的特征分布，而且僅憑直觀的對各參數值的分布觀察，不能有力地判斷使用哪幾個特征參量作為分類的基礎。并且，在提出的特征參量中，不可避免地會存在無關、冗余的特征，需要進行特征選擇[17]。特征選擇階段選用多信道特征參數數據，采用Relief特征選擇法[18]和MIFS[19]方法進行篩選，首先利用Relief特征選擇法衡量特征與分類標簽間的相關性，進而選擇對分類效果影響顯著的特征量，然后利用MIFS方法過濾掉冗余性較大的特征，挑選出分類效果最佳的特征子集進行分類。

圖3 室內特征參量箱線圖

3.2 Relief特征選擇法

Relief算法是過濾型特征選擇算法中性能較好的一種，應用于數據預處理階段，運行效率高、適用性強[20]。該算法是根據每個特征與類別標簽的相關性確定不同權值，選取權值較大的特征參量作為降維后的特征子集。主要思想為：在訓練樣本集中隨機選取m個樣本，對每個樣本R找到同類近鄰樣本H和不同類近鄰樣本M，根據式(2)求出樣本各特征與類別標簽的相關性，并求得各特征的平均權重。相關性越大表示該特征參量對樣本的區分能力越強

其中，R(A)為 第A個特征的權重，d iff(A，R，H)和diff(A，R，M)分 別為選取樣本R與同類近鄰樣本H和不同類近鄰樣本M在特征A上的差值。

利用Relief算法計算上述8個特征參量的相關性值，如表2所示。相關性越大表示該特征參量對樣本的區分能力越強，故提取最大振幅、上升時間、平均附加時延、飽和度作為新的特征子集，實現降維的目的。

表2 各參量與分類標簽的相關性

3.3 MIFS算法

將得到的最大振幅、總能量、上升時間、平均附加時延、飽和度利用互信息進行冗余度分析如表3所示。通過對上述特征量的分析，冗余度較小的特征量為上升時間、最大振幅、飽和度。

表3 兩特征參量之間的冗余度

通過Relief算法和MIFS算法對CIR特征參量的相關性和冗余性分析，選取相關性較大、冗余性較小的3個特征參量即上升時間、最大振幅、飽和度作為最佳選取特征集。

3.4 分類算法

定位中NLOS信道的鑒別實際也是對信道的二分類過程。從使用單一特征參量鑒別，到使用似然比進行多參量融合鑒別，在提高信道鑒別精度方面有了很大的進展。同時，機器學習在室內定位和信號分類領域的進展也引起了人們極大的關注，這些研究致力于開發一種更好、更魯棒的算法來對數據進行分類和識別，在這些工作中，有一些經典的分類器，如支持向量機、人工神經網絡、決策樹、貝葉斯方法[21，22]，也有一些它們的變體和組合。在NLOS識別中，盡管可以使用許多的分類技術，但一些分類器結構復雜，計算量較高，并不適用在較高頻率的實時定位NLOS識別中，本文選取WKNN分類方法進行實時識別，計算負擔較低，分類耗時較短，且在復雜的分類問題中仍具有較高的靈活性，故該分類器較為適用。

WKNN分類算法是一種較為成熟的機器學習分類算法，多用于信號處理領域[23，24]。該算法的思路是：在訓練數據集中特征向量與類別已知的情況下，對測試樣本進行分類，確定各特征參量的權重，計算測試數據與訓練數據之間的距離，將距離按照從大到小的順序排序，得到距離最小的K個訓練數據，將這K個數據中出現最多的類別作為測試數據的預測類。采用WKNN分類算法需要考慮訓練數據集的數量、特征參量的權重、距離的計算、K值的選取。

在計算距離前，需對訓練數據集及測試數據做歸一化處理，防止特征向量數值差別過大影響權重，并通過使用Relief算法確定的各特征參量與分類標簽的相關性判斷各特征參量的權重。權重計算如式(4)所示

K值的選取對NLOS的識別率有較大的影響。若出現兩個類在測試數據的WKNN算法中具有相同的數量，則會出現該測試數據不能判斷類別的情況，為避免這種情況發生，一般K值選擇奇數。訓練數據集數量不同，最優K值也不同。若K值取得過小，則算法易受信號干擾的影響，容易發生過擬合，使分類結果不穩定；若K值取得過大，則會造成泛化誤差大而近似誤差大的情況，容易發生欠擬合，同時，K值過大也會增大算法的時間開銷。為說明精度與K值的關系，并確定最優K值，繪出了它的K-精度曲線如圖4所示。

從圖4可以看出，對于不同數據集數量，K-精度曲線也不同，但它們都有相同的趨勢：K值較小時，分類精度較低，隨K值增大，分類精度逐漸增大，當K增大到一定程度時，分類精度逐漸減小。由圖可以得到最優K值在10附近，K確定為9。為了保證識別的實時性和識別的正確率，將訓練數據集定為300，包括150組LOS信道和150組NLOS信道，防止因分類數據的不平等導致識別率的降低。

圖4 K-精度曲線

4 實驗及結果分析

4.1 實驗平臺

如圖5所示，本系統由標簽、基站、以太網供電(Power Over Ethernet， POE)交換機、上位機(電腦)構成，采用到達時間差(Time Differences Of Arrival， TDOA)計算距離，每個基站都存在數據采集單元和處理單元，基站與POE交換機之間采用以太網線進行連接，供電的同時進行數據傳輸，標簽采用電池直接供電。為了采集CIR數據，運動的定位標簽不斷地向基站發送定位請求信號，基站和標簽使用的天線均為全向天線。基站利用UDP協議將CIR數據上傳到上位機進行分析。上位機接收到CIR數據包進行處理，顯示波形，每個數據點按接收到的先后順序排列，間隔為15.65 ps。

圖5 NLOS識別系統圖

在信號傳播過程中，接收信號強度會隨著傳播距離的增加造成衰減，并且不同障礙物有不同的介電常數，衰減也不同，一些特征參量中隱含這種衰減特性，使用這種距離衰減嚴重的特征參量作為分類標準會使分類精度降低。為了驗證本文NLOS識別算法的性能，利用已有的定位裝置(基站和標簽)開展了不同信道下使用不同特征參量的識別精度對比研究。包括室內辦公環境(CM1)、玻璃阻塞(CM2)、墻體阻塞(CM3)、工況阻塞(CM4)、室外10 m人體阻塞(CM5)、室外30 m人體阻塞(CM6)等不同信道，如圖6所示。

圖6 實驗環境

4.2 識別算法性能評定指標

為了評估本文NLOS識別系統的識別效果及不同環境的泛化能力，選用混淆矩陣(confusion matrix)[25]來度量該識別系統的性能，將預測分類與實際分類劃分為4種情況，真陽性(TP)、偽陽性(FP)、真陰性(TN)、偽陰性(FN)，如表4所示。

表4 混淆矩陣

混淆矩陣統計的是個數，很難衡量模型的優劣，故在混淆矩陣的基礎上使用準確率(Accuracy，A)作為性能度量指標。計算方式如式(7)所示

4.3 單一參量性能分析

本文旨在使用CIR波形中提取的特征參量來進行NLOS識別。盡管之前的工作已經提供了可用于解決此問題的參數，但在實際不同環境信道下可能效果并不好，故在此分析了單一特征參量在不同信道下的識別精度，如表5所示。對比同種環境不同距離CM5和CM6信道識別精度，發現某些特征參量受傳播距離影響嚴重，造成識別率降低，如總能量ε在CM5環境下識別精度可達99.67%，但在CM6環境下僅達到88.67%，故這類特征參量需盡量減少使用。對比不同環境下的識別精度，發現單一特征參量在某一信道下的識別率可以達到90%以上，具有較好的識別效果，但該特征參量在另一信道下識別精度僅為60%。由此可得，使用單一特征參量進行識別僅適用于個別環境信道，對其他環境沒有較好的適用性。

表5 單一參量在不同信道(CM)下的識別精度

4.4 多參量融合性能分析

本文所提算法利用Relief特征選擇法和互信息特征選擇法進行特征篩選，選擇上升時間、最大振幅、飽和度作為最優特征子集進行WKNN分類。WKNN參數設置：每種傳播信道訓練樣本數設置為200，共1200組訓練數據、近鄰數K設置為9、距離計算采用歐氏距離。

在室內辦公環境下進行400次分類實驗，該WKNN分類效果圖如圖7所示，其中，紅色○和藍色△分別為正確識別的LOS和NLOS信道，黑色☆和綠色*分別為錯誤識別的LOS和NLOS信道。WKNN分類識別率達到97.25%，平均單次識別耗時0.024 s，有較好的分類性能。

圖7 WKNN分類效果圖

信號傳播環境的復雜程度不同會造成信道沖激響應差異程度不同，不同特征對環境也有不同的識別能力，并且不同的特征之間存在不一樣的冗余度，故如隨意將之進行融合對識別能力有一定影響。本文提出的識別方法考慮到了特征與分類標簽之間的相關性和特征與特征之間的冗余性，有效地提高了識別精度。為驗證本文提出的識別方法的性能優越性，采用不同特征融合進行了不同信道下的實驗對比，如表6所示。

表6 多參量對不同信道(CM)的識別精度

可以看出本文提出的rmax+trise+S3種參量融合識別方法在不同信道下均達到了95%以上的識別精度，并且對比同一環境下CM5和CM6不同距離信道下，識別精度并不會受到影響。在計算復雜度相當的情況下，其余不同特征參量融合方法可能在某一環境下比本文提出的方法識別精度要高一點，但在別的環境信道下較低，不能達到有效識別的程度。故本文提出的識別方法識別精度較高，環境適用性較強。

5 結論

復雜的室內情況下，人體遮擋、墻體遮擋、鐵制品遮擋等非視距效應嚴重影響信號的傳播時間，這對室內定位精度的提高提出了嚴峻挑戰。本文旨在構建一個識別準確率較高、環境適用性較強、計算復雜度較低的實時NLOS識別系統，提出一種基于CIR的WKNN快速分類算法。在前人使用的CIR特征參量基礎上提出了一種新型特征參量，利用Relief算法討論了特征參量與分類標簽的相關性，利用MIFS算法分析了特征參量間的冗余性，得到新特征子集，最后分析特征參量之間的相關性獲得各特征參量的權重，得到WKNN快速分類算法。

本文討論了WKNN快速分類算法的訓練數據集數量和最優K值。并為了驗證本算法的有效性與適用性，利用該算法在不同環境下開展了實驗研究和結果分析。實驗結果表明，本文的NLOS識別算法在不同環境下仍達到95%，平均單次識別耗時0.024 s，具有較高實時性和環境適用性，保證了復雜室內環境下較高的識別精度。