賀 超，吳 飛，張玉金，朱 海

（上海工程技術大學 電子電氣工程學院，上海 201620）

0 引言

隨著社會的進步和科技研發(fā)能力的迅速發(fā)展，基于位置的服務（location based service， LBS）業(yè)務需求也在不斷增長。文獻[1-3]借助太空中的衛(wèi)星和地面基站的組合方式對室外場景進行定位與導航，為室外出行提供方便快捷的定位導航服務。但是，由于電磁信號的干擾與屏蔽，在室內(nèi)無法通過此種方式進行室內(nèi)導航。伴隨著移動互聯(lián)網(wǎng)的高速發(fā)展以及智能終端設備的普及，無線路由器廣泛地應用在人們的室內(nèi)生活場景中。因此，如文獻[4-7]研究的利用無線保真（wireless fidelity， WiFi）指紋庫的室內(nèi)定位方式受到了研究人員的廣泛關注。

國內(nèi)外已經(jīng)提出了很多基于WiFi 指紋庫定位算法。常見的單一分類器算法的WiFi 指紋庫定位算法有很多，如k 最近鄰(k-nearest neighbor，KNN)、支持向量機（support vector machine， SVM）等。文獻[8]中通過建立WiFi 離線位置指紋庫，并利用KNN 算法實現(xiàn)室內(nèi)定位，但是由于KNN 算法基于距離相似性準則進行判別，多輪的計算容易產(chǎn)生累計誤差并降低定位時效性；文獻[9]利用SVM算法進行WiFi 室內(nèi)定位，但SVM 算法復雜度高，對于大規(guī)模數(shù)據(jù)的計算有一定的困難。

相比于單一分類器的決策分類過程，文獻[10]采取自適應增強（adaptive boosting， AdaBoost）算法這種增強學習過程，對WiFi 定位數(shù)據(jù)進行有監(jiān)督的學習分類，能夠取得較好結(jié)果。但是，在實際的室內(nèi)定位應用中，真實數(shù)據(jù)常常因為環(huán)境因素而夾雜較多難以處理的噪聲和異常值。傳統(tǒng)的AdaBoost 算法存在對于異常值較為敏感以及算子分類器的決策權重對定位結(jié)果影響大的問題。

基于此，本文提出基于改進AdaBoost 算法的WiFi 室內(nèi)定位方法。主要過程如下：

1）通過1 種判決式特征選擇機制，保證基分類器間的多樣性，優(yōu)化特征屬性的權重，以提高算法整體的魯棒性。

2）采用1 種聯(lián)合投票決策方法，該投票決策結(jié)合子分類器自身的精度和特征屬性權重信息，在提高預測結(jié)果的精確度的同時，更加切合不確定且多變的指紋庫數(shù)據(jù)，可以提高模型的魯棒性。

1 AdaBoost 算法

AdaBoost 算法[11]的主要思想是對于所搜集到的WiFi 接收信號強度信息（received signal strength， RSS）樣本進行有監(jiān)督的增強學習。訓練集合為D = {( x1， y1) ， ( x2， y2) ，… ， ( xi， yi) ，… ， ( xN，yN)}，其 中 xi為RSS 樣本的因子屬性特征， yi表示定位所在空間坐標信息，作為標簽變量，N為樣本個數(shù)。在選定好弱分類器后，初始狀態(tài)下，所有樣本權重相等，根據(jù)AdaBoost 思想，不斷串行迭代訓練，并且在訓練過程中，后1 個弱分類器將會著重訓練被前 1 個弱分類器錯分的樣本，最終得到加權后的最終結(jié)果。

其主要流程如下：

1）輸 入。( x1， y1) ， ( x2， y2) ，… ， ( xi， yi) ，… ， ( xN，yN)，其中 xi∈ X，且 yi∈ Y。

3）訓練過程。for m in range(M)：

②通過 hm( X )在訓練集上的效果，計算分類誤差率，可表示為

若分類誤差率 em≥ 1/2，則算法提前停止，整體構(gòu)建失敗。

③為基分類器分配相應的構(gòu)建權重系數(shù)，可表示為

2 改進AdaBoost 算法

為了保留隨機采樣階段基分類器的多樣性，減少異常值對模型決策權重的影響，本文算法分別對特征因子選擇方式與投票決策集成機制進行了改進。

2.1 判決式因子選取

如文獻[12]所述，隨機子空間（random subspace method， RSM）樹結(jié)構(gòu)采樣方法是在建立子分類器的過程中，從整個數(shù)據(jù)集中隨機采樣得到每個子樹空間樣本集的方法。實驗表明，當數(shù)據(jù)樣本數(shù)量足夠大時，此種采樣策略最終得到的分類結(jié)果精度要高于傳統(tǒng)的AdaBoost 算法。但是，上述隨機采樣過程在多次采樣的過程中，會出現(xiàn)有的樣本被多次重復提取，而有的樣本僅有少量的機會甚至未被在建模階段采樣，進而制約基分類器的多樣性的問題。

受上述現(xiàn)象的啟發(fā)，本算法采用判決式因子選擇方式，力爭在保證基分類器間的多樣的同時，優(yōu)化特征屬性的權重。假設給定的數(shù)據(jù)集D 中有N個樣本，如果在缺少特征ia 的狀態(tài)下，導致本輪基分類器的錯誤分類個數(shù)為n，則認為本輪數(shù)據(jù)集屬性判決iJ n= 。相反，如果因為缺少特征屬性ia ，錯誤分類個數(shù)為n，本輪數(shù)據(jù)集屬性判決為iJ n=- 。此種現(xiàn)象表明，某個屬性的判決值的絕對值越大，則該屬性對于整個數(shù)據(jù)集的重要程度越高。因此，為了提高子樹之間的多樣性，從所有特征屬性中選擇前T 個屬性作為數(shù)據(jù)集 kD 用于創(chuàng)建子樹kC ，并且所有屬性的權重初始化為1/ac，其中ac 表示對于訓練集的特征屬性個數(shù)，并且T由經(jīng)驗可啟發(fā)式地設置為ar/2。進一步聚焦至單個節(jié)點d的屬性劃分選擇，隨機選取 ( )ar ar T＜ 個特征屬性用于計算其基尼系數(shù)，其中ar 可表示為

并不是利用整個數(shù)據(jù)集的所有特征進行計算，而是選擇基尼系數(shù)小的特征屬性計算分割點，可表示為

式中： gini (d )為為該節(jié)點分割前的基尼系數(shù)，對應的 gini ( aj( d ))為在節(jié)點d 中以最佳特征屬性 aj分割后的基尼系數(shù)。由于采取特征屬性隨機采樣的機制，因此在構(gòu)建基分類器的過程中會出現(xiàn)某些特征屬性被多次采取的情況，這樣在樣本個數(shù)相同的情況下，從特征屬性采樣的角度分析，必然造成了數(shù)據(jù)的不均衡?；诖?，在基分類器建成后，對于被多次選擇的特征屬性 aj，可進行處理

式 中： ns ( aj)為 選 擇 特 征 屬 性 aj的 次 數(shù)；μ G g ( aj( d ))為其均值，在子決策樹中選擇所有 的 G g ( aj( d))和 其 對 應 的 m 個 特 征 屬 性( m ≤ T)，可推導計算出整體對應的均值 μ ( G(g))和標準差 σ ( G ( g ))，當 μ ( G ( g ))和 σ ( G ( g ))之間的差值是正數(shù)時，提高特征屬性 aj的權重，反之減少其對應的權重。

通過對于樣本特征屬性進行隨機采樣的方法，提高了各子分類器之間的多樣性，更貼近真實數(shù)據(jù)多變的情況。

2.2 改進決策機制

改進AdaBoost 算法采用包外估計的方法，采用2/3 的訓練數(shù)據(jù)用于構(gòu)建子樹基分類器，1/3 的數(shù)據(jù)用于模型構(gòu)建完后的驗證和相關學習權重的驗證。利用訓練數(shù)據(jù)集 Dk去構(gòu)建子樹基分類器Ck，將測試數(shù)據(jù)作為輸入時，由上述切割原理可知，通過計算特征屬性的基尼系數(shù)得到最佳切割屬性 aj，并且將測試數(shù)據(jù)通過基分類器得到分類結(jié)果的平均精度作為子樹基分類器 Ck的屬性 aj的決策權重 wk，j。在線使用階段，對于任何1 個未知的樣本屬性，改進后的算法綜合考慮屬性分割點 aj的決策權重 wk，j和子分類器的自身精度去計算最終的聯(lián)合投票權重，最終分類預測結(jié)果可表示為

式中：I-AdaBoost（χ）為改進算法的預測結(jié)果；y 表示真實的分類標簽； Ci( x )表示子樹基分類器的預測結(jié)果；acci為子樹 Ci的精確度； wij即為切割屬性 aj的決策權重。

通過新的決策集成機制，充分保留了對特征屬性隨機采樣而導致的子樹之間的多樣性。算法結(jié)合傳統(tǒng)的投票決策方式，提高了預測結(jié)果的精確度，更切合真實數(shù)據(jù)的不確定性和多變性，提高了模型的魯棒性。

3 實驗與結(jié)果分析

3.1 實驗設計

實驗場地選用上海工程技術大學現(xiàn)代工程實訓樓4 樓，實驗場有5 個區(qū)域，共計738 個采樣點，實驗采用50 Hz 的采樣頻率，場地采用1.25 m×1.25 m的網(wǎng)格劃分，圖1 為區(qū)域5 的實驗場地圖，區(qū)域5 共140 個采樣點。

圖1 區(qū)域5 實驗場地

為了更好地對定位效果進行量化評判，引入評判誤差函數(shù)

式中：( Xt， Yt)為真實位置坐標；( Xi， Yi)為算法所輸出的位置坐標。根據(jù)均方誤差求得誤差函數(shù)error，如圖1 所示，上述坐標均為2 維空間的相對O點位置坐標。

3.2 結(jié)果分析

在實驗階段，選用改進AdaBoost 算法、SVM算法以及KNN 算法和傳統(tǒng)AdaBoost 算法進行定位效果對比，表1 為原始采集數(shù)據(jù)經(jīng)填補缺失值處理后的數(shù)據(jù)。

表1 部分真實定位數(shù)據(jù)

圖2 為KNN、SVM、AdaBoost 以及I-Adaboost 4 類算法定位誤差分析后的結(jié)果折線統(tǒng)計圖。

圖2 定位誤差分析

由于KNN僅考慮了所采集到的RSSI 特征因子的距離相似度，其算法思想較為簡單，因此實際定位效果不佳，在1.5 m 范圍內(nèi)的誤差為47%。對于SVM 而言，由于其基于最大化分類邊緣信息，擁有更好的分類性能，但是模型對于大規(guī)模數(shù)據(jù)的處理仍然存在問題。相比于上述2 種單分類器算法，AdaBoost 算法集成多個分類與回歸樹的弱分類器，能夠較為全面地考慮數(shù)據(jù)特征每次迭代分類中的誤差，有利于分類錯誤的矯正。

由于傳統(tǒng)的AdaBoost 算法對于數(shù)據(jù)中存在的異常值較為敏感，容易引起模型較大的波動，從而影響最終的定位效果。因此，針對上述存在的隱患，加入了判決式因子選擇，以保證模型的多樣性，充分利用設備端所采集到的特征數(shù)據(jù)。同時，算法對于最終的聯(lián)合分類器投票過程做了改進，在分 析特征因子對精度影響的基礎上，考慮了分類器自身給出的判決結(jié)果，最終提高了定位效果。實驗結(jié)果表明，改進后的AdaBoost 算法在1.5 m 誤差范圍內(nèi)的概率提高至 91%，相比于傳統(tǒng)的AdaBoost 算法提高了12%。

然后選取實驗范圍內(nèi)的5 個區(qū)域?qū)ι鲜鏊惴ㄟM行定位準確率評測。表2 為KNN、SVM、AdaBoost， 以及I-AdaBoost 算法在上述5 個區(qū)域的定位準確率結(jié)果。

表2 4 類算法在5 個定位區(qū)域定位準確率結(jié)果

改進后的AdaBoost 算法運用新的判決式因子選擇機制，保證了基分類器間的多樣性，提高了算法整體的魯棒性，因此算法在5 個定位區(qū)域均有較高的定位準確率，在區(qū)域5 定位準確率甚至達到96.1%。實驗結(jié)果表明，相對于SVM 算法與傳統(tǒng)的AdaBoost 算法，改進后的AdaBoost 算法自身性能上較為穩(wěn)定，且有好的定位效果。

4 結(jié)束語

隨著室內(nèi)定位應用的不斷發(fā)展和研究的深入， 室內(nèi)定位技術將在各種實際生活場景發(fā)揮重要作用。改進AdaBoost 算法的WiFi 室內(nèi)定位技術，利用新的判決式屬性選擇機制保持基分類器的多樣性，更加符合實際的定位數(shù)據(jù)情況，增強了整體的魯棒性；新的投票機制中融合了特征因子自身的精確度與基分類器的精確度評分，提高了算法最終的決策性能，從整體上增強了定位準確率。在今后工作中，針對大規(guī)模的定位數(shù)據(jù)運算，可引入大數(shù)據(jù)領域技術要點，采用分布式原理，對大體量的數(shù)據(jù)進行并行處理和模型部署，從而進一步提高定位業(yè)務整體性能。