陳驍，宋安軍

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

Wi-Fi指紋；室內(nèi)定位；核K-means；RVM；聚類

0 引言

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

1 算法實現(xiàn)

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

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

2 核K-means算法的應用

K-means算法是一種無監(jiān)督的聚類算法，一般是依據(jù)歐氏距離的大小來自動聚類的，但只能處理線性可分的數(shù)據(jù)集。核K-means是在此基礎上引入核函數(shù)[3]，能夠?qū)崿F(xiàn)非線性可分數(shù)據(jù)集的聚類。在本文算法的實現(xiàn)中，核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算法對參考點聚類的過程基本如下：

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

②For i=1→m

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

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

End for

③For j=i→k

End if

End for

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

3 RVM分類回歸算法

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

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

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

其中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。樣本訓練過程中隨著參數(shù)的大量使用，對ωi和σ2進行最大似然估計時，會產(chǎn)生過擬合現(xiàn)象。為了避免產(chǎn)生這種現(xiàn)象，需要對一些參數(shù)加入一定的強制附加條件，這種做法在SVM中已有大量十分有效的應用[5]。RVM為每一個權(quán)值都定義了高斯先驗分布來約束參數(shù)，我們引入N+1維超參數(shù)α=[α0,α1,…,αN]T，并假設α服從Gamma先驗概率分布可得：

再由貝葉斯理論可得：

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

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

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

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

4 實驗場景和結(jié)果分析

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

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

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

實驗結(jié)果如圖3所示，實驗對比了兩種算法在本實驗條件下的定位誤差數(shù)據(jù)，在相同參數(shù)設置下，訓練樣本為180時，同樣經(jīng)過核K-means算法處理的RSS數(shù)據(jù)，使用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 兩種算法的各項數(shù)據(jù)

5 結(jié)語

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