陳驍，宋安軍

（上海海事大學(xué)信息工程學(xué)院，上海 201306）

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

0 引言

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

1 算法實(shí)現(xiàn)

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

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

2 核K-means算法的應(yīng)用

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

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

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

②For i=1→m

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

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

End for

③For j=i→k

End if

End for

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

3 RVM分類回歸算法

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

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

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

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

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

再由貝葉斯理論可得：

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

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

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

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

4 實(shí)驗(yàn)場景和結(jié)果分析

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

圖2 實(shí)驗(yàn)環(huán)境平面圖

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

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

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

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

表1 兩種算法的各項(xiàng)數(shù)據(jù)

5 結(jié)語

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