基于核K-means與RVM分類回歸的Wi-Fi指紋室內定位算法

陳驍，宋安軍

（上海海事大學信息工程學院，上海 201306）

Wi-Fi指紋；室內定位；核K-means；RVM；聚類

0 引言

隨著互聯(lián)網以及物聯(lián)網技術的高速發(fā)展，越來越多的新型科技得以服務大眾。人們對基于位置服務（Location Based Service，LBS）的需求也趨于廣泛化以及多樣化。由于全球定位系統(tǒng)（Global Positioning Sys?tem，GPS）的局限性以及室內定位需求的增加，室內定位技術越來越引起人們的關注。目前，室內定位技術主要有：ZigBee室內定位、紅外室內定位、藍牙室內定位、超聲波室內定位、RFID室內定位、超寬帶室內定位和WLAN室內定位等技術。相比較而言，WLAN室內定位由于其無需額外的硬件設備，定位速度較快，總體定位精度較高等特性，得到了廣泛的關注與研究應用。WLAN室內定位主要分為兩種，其一是基于時間的到達定位技術，主要通過信號接收的時間差，通過算法的計算，獲得詳細的定位數據。第二種是基于位置指紋的定位技術，該技術通過將接收信號強度（Re?ceived Signal Strength，RSS）與物理位置的綁定而進行定位。根據文獻[1]所述，基于時間的定位技術，由于受到額外成本或者自身定位精度的限制，無法適用于大量的室內場景?；赪i-Fi位置指紋的定位技術，主要分為離線與在線兩個階段。離線階段首先在定位區(qū)域內設置若干個距離相等的參考點，在每一個參考節(jié)點處測試各個AP的RSS數據，將數據組成n維（n=AP個數）特征向量，再將每個參考點的特征向量存入數據庫。這樣就如同人類指紋一樣，對每一個參考點有各自不同的唯一特征向量，我們把這些數據形成的數據庫稱為位置指紋數據庫。在線階段，終端設備在參考點覆蓋區(qū)域內某個位置該點采集RSS數據，再通過與指紋數據庫的對比得到定位結果。許多室內定位的研究也引入了SVM方法。但是SVM對于多分類問題的性能不佳，并且需要使用較為準確的超參數來獲取更好的性能。文獻[2]將KNN算法與SVM融合，使用KNN算法對輸入數據進行預處理，再對數據應用SVM算法。但是由于該算法的復雜性等因素，影響定位的實時性。為了提升定位精度與實時性，本文提出了一種融合核K-means與RVM分類回歸的室內定位算法。核K-means算法對預處理過的輸入RSS特征向量進行無監(jiān)督聚類，對指紋數據庫中的指紋進行區(qū)域劃分。RVM分類回歸算法將終端收集到的RSS數據進行分類，訓練出強擬合的回歸函數。實驗結果表明，該算法相較SVM相關算法，提升了定位效率與定位精度。

1 算法實現

本文算法實現過程如圖1，離線階段通過對建立定位空間中對每個AP的參考點，經過核K-means算法對每個參考點進行聚類，來構建該空間的位置指紋數據庫。再使用指紋數據庫中的數據訓練RVM回歸算法，得到數學模型。在線階段使用RVM分類函數先對在線RSS特征向量進行分類。確定區(qū)域后，通過RVM回歸函數模型，估算最終的定位坐標。

圖1 核K-means和RVM分類回歸算法的工作流程圖

2 核K-means算法的應用

K-means算法是一種無監(jiān)督的聚類算法，一般是依據歐氏距離的大小來自動聚類的，但只能處理線性可分的數據集。核K-means是在此基礎上引入核函數[3]，能夠實現非線性可分數據集的聚類。在本文算法的實現中，核K-means算法應用過程如下：

設有參考節(jié)點集合P=(p1,p2,p3...pn)，則有n個RSS特征向量rss={rss1,rss2,rss3...,rssi...rssn} ，并建立m個AP（Access Point）的定位模型，則每個參考節(jié)點可以收到m個RSS值,其中rssi={rssi1,rssi2,rssi3...rssim}來表示第i個參考點所接收到的各AP信號強度（下標m表示在第i個參考節(jié)點處所接收到的第m個AP的RSS值，記為rssim）。用D={D1,D2,D3...Dk}來表示各參考節(jié)點所屬類別的集合。Kernel k-means算法對參考點聚類的過程基本如下：

①根據K均值算法的取值K，選取K個參考點p的特征向量作為起始均值向量。v={v1,v2,v3...vk}。

②For i=1→m

計算RSS中每一個特征向量與步驟①中選出各均值向量的距離vj（1≤j≤k）的距離，這一步根據文獻[2]引入算法的kernel函數，將樣本空間中的第i個參考點樣本映射到高維空間中。

得出dij（表示當前rssi與均值向量距離最小的類別），再將該參考點歸入相應類別中DLi=DLi?{rssi}。

End for

③For j=i→k

End if

End for

④重復迭代執(zhí)行步驟②、③，直到均值向量不再更新為止。由以上的四個步驟，可將獲得的數據構造出空間對應的Wi-Fi指紋空間向量數據庫。

3 RVM分類回歸算法

RVM是2001年Tipping在文獻[4]中提出的一種基于貝葉斯框架下的稀疏概率模型。相較于SVM而言RVM可以直接獲得后驗概率。RVM分類本文中RVM的分類任務，就是判定在線階段獲取的（rssi,yi）數據，屬于D中的哪個區(qū)域。RVM的分類模型與SVM類似，根據Tipping的文獻[1]中所述，相關向量機的模型定義為：

其中K(x,xi)是核函數，ωi是模型權值。在本文中將使用常用的徑向基函數（Radial Basis Function，簡稱RBF）作為核函數，該函數定義：

其中σ2表示該核函數的寬度參數。對于核函數的寬度設置非常重要，如果寬度太小，將會導致分類器的過擬合，反之則會造成分類器訓練不足。這兩種情況都會導致分類的性能受到影響。

其中W=[ω0,ω1,???,ωN]T，展開可得：

式中的W和Φ都是大小為N×(N+1)的預先設計的矩陣，并且 Φ=[φ(x1),φ(x2),???,φ(xN)]T，其中φ(xn)的值為φ(xn)=[1K(xn,x1)K(xn,x2)???K(xn,xN)]T。樣本訓練過程中隨著參數的大量使用，對ωi和σ2進行最大似然估計時，會產生過擬合現象。為了避免產生這種現象，需要對一些參數加入一定的強制附加條件，這種做法在SVM中已有大量十分有效的應用[5]。RVM為每一個權值都定義了高斯先驗分布來約束參數，我們引入N+1維超參數α=[α0,α1,…,αN]T，并假設α服從Gamma先驗概率分布可得：

再由貝葉斯理論可得：

因為p(ω|t,α)與p(t|ω)p(ω|α)成正比，將關于ω的最大后驗概率估計等價為最大化：

其 中 ，A=diag(α0,α1,???,αN) ，yn=σ{y(xn;ω)} 。又因為p(a|t)與p(t|a)p(a)成正比，求解p(a|t)的問題就可以被轉化為超參數的后驗分布p(a|t)關于α的最大化問題，可以將p(t|a)最大化：

此時再利用拉普拉斯逼近方法不斷迭代上兩個公式，優(yōu)化超參數α和參數ω，大部分的ωi最終都將趨近于0，少部分的ωi會趨近于穩(wěn)定。此時，對應的xi被Tipping稱為關聯(lián)向量（Relevance Vectors），同時模型也完成了稀疏化。

RVM算法由于獲得了目標的概率值，在進行二分類的時候，yi需要經過sigmoid函數的處理后，獲得樣本的類別信息。在室內定位中，RVM模型所遇到的是多分類問題，本文將采用一對一方法將多分類問題分解為二分類問題，這種方法將會產生k（k-1）/2個決策函數。讓決策函數對每個分類兩兩投票，統(tǒng)計所有分類的勝出次數，勝出票數加一，得票最多的那個即最后的預測類。

4 實驗場景和結果分析

實驗場景如圖2所示，在上海海事大學信息與工程學院一樓140大實驗室，實驗區(qū)域總共可以搜索到3個AP熱點，數據采集設備為安裝有RSS采集軟件的小米6手機。（為了展示更為精確的數據，以下實驗結果中的數據，不包含無線信號的傳輸與傳播時延。）

圖2 實驗環(huán)境平面圖

離線階段的實驗中，將實際的試驗區(qū)域均勻地布置間隔為1米的參考點，共計25個。每個參考點處采集20次各AP所產生的RSS數據，總共有500個樣本作為訓練樣本，在算法中進行訓練。而定位性能的檢測階段，在實驗區(qū)域內隨機選擇20個點作為測試點，獲取總計400個RSS數據作為測試樣本。為了保證模型訓練的穩(wěn)定，以及避免過擬合現象的發(fā)生，實驗使用10次10折交叉檢驗法，且盡可能保持數據分布一致。實驗中RVM與SVM均選用RBF函數，SVM核參數設置C=8，γ=2，RVM核參數設置為γ=2。其中SVM算法基于 LIBSVM[6]工具箱，RVM算法基于 Tipping的Sparse Bayes程序RVM工具箱[7]。實驗中所使用的核K-means與SVM算法，參照文獻[8]中的實驗方法，最后對比實驗數據。

實驗結果如圖3所示，實驗對比了兩種算法在本實驗條件下的定位誤差數據，在相同參數設置下，訓練樣本為180時，同樣經過核K-means算法處理的RSS數據，使用RVM算法的最大誤差要小于SVM算法，在1m-2.5m的定位精度中，RVM算法略微低于SVM算法。

圖3 不同算法在定位誤差中的累計概率分布

如表1所示，兩個算法的定位誤差圖。在訓練樣本為500時，核k-means-SVM和核k-means-RVM最大誤差分別為3.83m、3.53m。最小誤差分別為0.49m、0.52m。平均誤差分別為1.86m、1.79m。

表1 兩種算法的各項數據

5 結語

對基于Wi-Fi指紋的室內定位過程中RSS的時效性與定位精度問題，及其衍生的對于指紋數據庫的，提出一種基于核k均值與RVM分類回歸的定位算法解決方案。在離線階段，采用核k均值算法對定位參考點進行劃分，利用在小區(qū)域內進行回歸模型的優(yōu)勢提高了對未知數據的泛化能力，并且將相關向量的需求量降低，訓練樣本個數的需求降低。同時降低了計算復雜度，并且將定位實時性提高。并且省略了SVM算法需要的參數尋優(yōu)步驟，降低了算法設計成本。實驗結果表明，在以1米為間隔布置的參考點和定位區(qū)域AP數目穩(wěn)定的情況下，該算法的測試時間為0.013秒，具有實用價值。