改進(jìn)AdaBoost 算法的WiFi 室內(nèi)定位

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

（上海工程技術(shù)大學(xué) 電子電氣工程學(xué)院，上海 201620）

0 引言

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

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

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

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

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

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

1 AdaBoost 算法

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

其主要流程如下：

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

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

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

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

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

2 改進(jìn)AdaBoost 算法

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

2.1 判決式因子選取

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

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

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

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

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

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

2.2 改進(jìn)決策機(jī)制

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

圖1 區(qū)域5 實(shí)驗(yàn)場(chǎng)地

為了更好地對(duì)定位效果進(jìn)行量化評(píng)判，引入評(píng)判誤差函數(shù)

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

3.2 結(jié)果分析

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

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

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

圖2 定位誤差分析

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

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

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

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

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

4 結(jié)束語

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