基于AP-SVM混合分類的指紋定位算法優(yōu)化*

毛永毅, 呂 丹

(西安郵電大學(xué) 電子工程學(xué)院，陜西 西安 712000)

0 引 言

近年來，隨著人類生活方式和需求的不斷更新，室內(nèi)已成為人們工作活動的主要場所，室內(nèi)精確定位的需求也愈來愈強烈。當(dāng)前主流的室內(nèi)定位技術(shù)包括有：紅外線[1]、藍牙[2]、超寬帶(ultra wideband，UWB)[3]、射頻識別(radio frequency identification,RFID)[4]、無線保真技術(shù)(wireless fidelity,WiFi)[5]等。WiFi定位技術(shù)是一種在辦公室和家庭中使用的短間隔無線技術(shù)，使用2.4 GHz左右的頻段[6]，具有傳輸速度快、傳播穩(wěn)定等優(yōu)勢，并且價格低廉,方便搭建，能夠在日常生活中廣泛使用，因此該項技術(shù)一直是室內(nèi)定位技術(shù)研究中的熱點[7,8]，眾多學(xué)者對其進行了深入研究，進一步促進了WiFi室內(nèi)定位技術(shù)的發(fā)展。

文獻[9]提出一種基于指紋數(shù)據(jù)物理位置關(guān)系對指紋數(shù)據(jù)分級的方法,通過數(shù)據(jù)分級縮小數(shù)據(jù)匹配范圍提高匹配效率,同時提高定位精度。文獻[10]提出基于支持向量機(support vector machine,SVM)的混合相似度加權(quán)K最近鄰(mixed similarity weighted K nearest neighbor,MWKNN)算法，即SVM-MWKNN通過建立多相似度指標(biāo),可以有效提高數(shù)據(jù)利用率,減少定位誤差,定位精度提高達45 %。文獻[11]提出一種基于奇異值檢測和親和力傳播(affinity propagation,AP)聚類的無線局域網(wǎng)指紋定位算法，通過AP聚類粗檢測和基于加權(quán)K近鄰算法的細檢測評估得到用戶位置,完成定位。

本文提出了基于黃金分割法掃描AP聚類算法中的偏向參數(shù)P的范圍的方法—GAP-SVM混合分類算法。首先應(yīng)用優(yōu)化后的AP聚類算法即GP-AP聚類算法優(yōu)化樣本數(shù)據(jù)集，得到具有代表性的高質(zhì)量的數(shù)據(jù)作為SVM分類器的訓(xùn)練集，然后結(jié)合SVM模型，提高分類精度，進而提高了WiFi位置指紋定位技術(shù)的準(zhǔn)確度和穩(wěn)定性。

1 AP-SVM相關(guān)

1.1 AP聚類算法

AP聚類算法是由Frey和Dueck提出的一種新的無監(jiān)督學(xué)習(xí)方法[12]。AP聚類不需要預(yù)先指定聚類數(shù)，所有數(shù)據(jù)點在啟動時都視為機會均等的候選聚類中心點，通過節(jié)點之間的通信找到最合適的聚類中心和相應(yīng)的聚類數(shù)，與此同時也會淘汰質(zhì)量低的候選聚類中心。經(jīng)過對數(shù)據(jù)信息進行綜合判斷，將非聚類中心點歸屬到相應(yīng)的類別中進行聚類。AP聚類算法通過反復(fù)迭代不斷調(diào)整每個點的吸引度和歸屬度值，直到產(chǎn)生高質(zhì)量的簇中心，并將其他的數(shù)據(jù)點分配到相應(yīng)的簇。AP聚類算法使用S(i,k)來表示數(shù)據(jù)點Xk在類代表點中適合數(shù)據(jù)點Xi的程度，為每個數(shù)據(jù)點k設(shè)置偏移參數(shù)S(k,k)值，S(k,k)值越大，越有可能選擇對應(yīng)的點k作為類代表點。AP聚類算法的初始假設(shè)是選擇所有數(shù)據(jù)點成為類代表點的可能性相同，即所有S(k,k)值與P值相同，同樣，P值的大小也會影響最終聚類的類數(shù)。這是AP聚類算法的一個重要參數(shù)。

AP聚類算法兩個重要的信息內(nèi)容參數(shù)：吸引矩陣R=[R(i,k)]n×n和歸屬矩陣A=[A(i,k)]n×n。R(i,k)為數(shù)據(jù)對象Xk適合作為數(shù)據(jù)對象Xi的聚類中心的程度，A(i,k)描述了數(shù)據(jù)對象Xi選擇數(shù)據(jù)對象Xk作為其聚類中心的適合程度。AP聚類算法的迭代過程是交替更新兩個信息內(nèi)容的過程，兩種信息內(nèi)容代表不同的競爭目的。更新公式如下

R(i,k)←S(i,k)-maxk′s,t,k′≠k{A(i,k′)+s(i,k′)}

(1)

(2)

(3)

通過迭代，樣本點競爭得到具有代表性的點，即聚類中心。最后，可以確定集群中心的數(shù)量是否滿足要求，如果不是，再次調(diào)整P和集群的大小，直到集群的數(shù)量滿足要求。

1.2 SVM

SVM是一種有監(jiān)督的分類識別方法[13]。在D維空間中輸入兩類數(shù)據(jù)，選取i個訓(xùn)練樣本，(xi,yi),i=1,…,l，x∈Rn，y∈{+1,-1}，利用SVM在空間中構(gòu)造一個超平面wx+b=0來區(qū)分兩類數(shù)據(jù)(w表示超平面法向量，b表示超平面的偏置)，使得超平面與兩類數(shù)據(jù)邊界的距離最遠。所有的訓(xùn)練樣本都滿足以下條件

yi(wix+b)-1+ε≥0,εi≥0,i=1,…,l

(4)

非線性情況下，SVM的基本思想：通過一定的非線性函數(shù)將訓(xùn)練樣本從原始輸入空間映射到高維特征空間，在高維特征空間中構(gòu)造最優(yōu)分類超平面，使訓(xùn)練樣本在高維空間中按線性維函數(shù)進行分類。線性不可分的情況下，有一些樣本不能被最優(yōu)分類面正確分類，因此,可以引入松弛變量ε來允許誤分類，εi≥0,i=1,…,l。在非線性可分的情況下，利用映射函數(shù)φ將輸入向量x映射到高維特征空間Z，在該空間找到一個最優(yōu)的分類器。最大化SVM邊界等價于求解如下優(yōu)化問題

(5)

約束條件為

yi[(w·xi)+b]-1+ε≥0,εi≥0,i=1,…,l

(6)

優(yōu)化問題可以轉(zhuǎn)換為

(7)

約束條件為

∑yiαi=0,0<αi

(8)

1.3 AP-SVM

該模型由兩部分組成，分別為AP聚類算法和SVM，基本思路：利用AP聚類算法對數(shù)據(jù)集進行初始聚類，并從聚類結(jié)果中選擇具有代表性的樣本訓(xùn)練SVM分類器，然后將所有數(shù)據(jù)交給SVM分類器。因此，如何選擇合適的訓(xùn)練樣本，將會直接影響SVM分類器的生成和最終的分類結(jié)果。

混合分類過程包括以下三個部分:1)AP聚類算法初始聚類:輸入采集到的數(shù)據(jù)后，AP聚類算法在開始時默認所有數(shù)據(jù)點均是聚類中心，根據(jù)N個數(shù)據(jù)點之間的相似度進行聚類；2)訓(xùn)練樣本的選擇:AP聚類后，得到初始類，然后選擇類別中心及相似度較大的數(shù)據(jù)點作為訓(xùn)練樣本;3)訓(xùn)練SVM分類器。

2 GAP-SVM相關(guān)

2.1 GAP-SVM算法

AP聚類算法中，偏向參數(shù)P值直接影響聚類數(shù)目，P值增大，聚類數(shù)目增多。傳統(tǒng)的AP聚類算法中，P值選擇N個樣本點相似度的均值Pm。本文提出一種黃金分割法掃描AP聚類算法中的偏向參數(shù)P的范圍的方法—GAP，以期得到更好的聚類效果，產(chǎn)生更高質(zhì)量的訓(xùn)練樣本，再將GAP與SVM結(jié)合，形成GAP-SVM算法。

算法思路如下：第一次，確定偏向參數(shù)P的掃描范圍[PminPmax]，在區(qū)間內(nèi)取兩個點P1,P2，將[PminPmax]分為3段。P1=Pmin+0.382(Pmax-Pmin)，P2=Pmin+0.618(Pmax-Pmin)，通過計算對應(yīng)的Silhouetter指標(biāo)S1和S2，來決定去掉一部分區(qū)間，若S1

GAP的具體步驟如下：

1)取N個樣本點相似度的最小值和平均值，分別為Pmin和Pm，經(jīng)驗證，偏向參數(shù)初值取Pm/2，可以得到不錯的聚類效果。因此，偏向參數(shù)P的范圍取[PminPmax]，初值取Pm/2。變量參數(shù)說明如表1;

2)AP聚類算法進行一次循環(huán)，產(chǎn)生K個聚類；

3)判斷AP聚類算法是否收斂，(收斂條件是聚類數(shù)目K，滿足預(yù)先設(shè)定的連續(xù)不變次數(shù))，若收斂，則轉(zhuǎn)至步驟(5)，否則，執(zhí)行步驟(3);

4)計算P1,P2對應(yīng)的Silhouette指標(biāo)，分別為S1，S2，若S1S2，則令Pmin=P1，P1=P2，P2=Pmin+0.618(Pmax-Pmin)；若Pmax-Pmin

5)輸出最后一次迭代的聚類結(jié)果和P*及對應(yīng)的S*，P*=(Pmin+Pmax)/2。

表1 變量參數(shù)說明

2.2 基于GAP-SVM位置匹配定位模型

位置指紋庫定位是基于信號接收強度指示(RSSI)的定位方法，利用信號強度特征數(shù)據(jù)來推斷待定位點的物理位置坐標(biāo)。定位過程包括兩個階段，分別是離線階段和在線階段。

離線階段：將定位區(qū)域進行合理均勻地劃分，并且合理選擇接入點(AP)的位置和數(shù)目，根據(jù)每個AP無線信號的覆蓋范圍和定位精度的需求，在劃分后的每個區(qū)域進行參考點設(shè)立，參考點的密度通?？刂圃? m以內(nèi)。在每個參考點位置處采集信號的RSS值等特征數(shù)據(jù)。將采集到的數(shù)據(jù)首先利用GP-AP聚類算法進行初始聚類，并從聚類結(jié)果中選擇高質(zhì)量樣本訓(xùn)練SVM分類器，對數(shù)據(jù)進行準(zhǔn)確的分類，建立位置指紋數(shù)據(jù)庫(包括RSSI值及所在區(qū)域的物理位置坐標(biāo))。

在線階段：對待定位點進行信號采集，將實時獲取的RSSI與相對應(yīng)的物理位置坐標(biāo)作為測試集，輸入到GAP-SVM模型中，進而模型對指紋展開合理的分類，最后得到待定位點的物理位置坐標(biāo)。定位模型如圖1所示。

圖1 定位模型

本文利用GAP-SVM分類與預(yù)測來實現(xiàn)室內(nèi)定位，在實驗區(qū)域中采集數(shù)據(jù)并進行訓(xùn)練，得到包含位置信息的指紋庫。在定位過程中，通過對待定位目標(biāo)進行RSSI特征數(shù)據(jù)采集, 將獲得的數(shù)據(jù)信息與指紋信息庫展開匹配，從而完成目標(biāo)位置的估計。

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

實驗環(huán)境如圖2所示。選擇已知位置坐標(biāo)的8個AP進行安裝，采集數(shù)據(jù)過程中，在每個采樣點，使用移動設(shè)備來獲取AP的RSSI值，然后利用迭代法得到設(shè)備的坐標(biāo)。在每個參考點處，采集各個AP在5 min內(nèi)接收到的RSSI值，每5 s進行一次信號采集，一共采集了60次，該參考點指紋信息向量通過計算這60次RSSI值的平均值獲得。為了檢驗本文所提算法的定位效果，選取最近鄰(nearest neighbor，NN)算法,K最近鄰(K-nearest neighbor，KNN)算法，加權(quán)K最近鄰(weighted K-nearest neighbor，WKNN)算法[14,15]以及AP-SVM進行比對。

圖2 實驗環(huán)境

表2 采集到的部分RSSI值 dB

SVM訓(xùn)練模型中的兩個主要參數(shù)：懲罰參數(shù)C和核函數(shù)參數(shù)g[16]，這兩個參數(shù)的取值，通常采用網(wǎng)格搜索的交叉驗證(cross validation,CV)方法進行參數(shù)尋優(yōu)，最終選擇分類準(zhǔn)確率最高的一組參數(shù)。但在實驗過程中，分類準(zhǔn)確率最高的同時可能會存在多組匹配的參數(shù)，因為C太高會產(chǎn)生過學(xué)習(xí)現(xiàn)象，所以通常會選擇懲罰參數(shù)C最小的一組，同時，由于C值不同，也可能會有與C值所對應(yīng)的不同的g值出現(xiàn)，此時一般選擇搜索到的第一組參數(shù)。

圖3、圖4分別為精選范圍內(nèi)參數(shù)網(wǎng)格搜索法尋優(yōu)的等高線圖與3D視圖，得到參數(shù)最優(yōu)組合為0.758和0.027，訓(xùn)練集的正確分類識別率最高近似達91.59 %。

圖3 參數(shù)尋優(yōu)(等高線圖)

圖4 參數(shù)尋優(yōu)(3D視圖)

圖5是利用CV法得到的實際—預(yù)測分類圖，確定了SVM模型中C和g，對測試集數(shù)據(jù)進行預(yù)測，最終將預(yù)測分類結(jié)果正確率提高到92.21 %，提升效果明顯。

圖5 測試集的實際分類和預(yù)測分類

圖6是在不同信號強度下，各個算法的定位準(zhǔn)確率。隨著信號強度增強，GAP-SVM定位準(zhǔn)確率提高明顯，較傳統(tǒng)的NN,KNN,WKNN,AP-SVM效果好，GAP-SVM與AP-SVM相比，定位準(zhǔn)確率提高了46 %。

圖6 不同信號強度下各種算法的定位精度

4 結(jié) 論

本文基于黃金分割法的理論提出了新的算法GP來尋找AP聚類算法最優(yōu)的P值，得到了更好的聚類結(jié)果，從而得到了更高質(zhì)量的SVM的訓(xùn)練集，再將GAP與SVM相結(jié)合，利用設(shè)計出的基于GAP-SVM模型的位置指紋定位整體系統(tǒng)架構(gòu)，通過仿真實驗，驗證了新算法GAP-SVM相較于傳統(tǒng)算法AP-SVM具有更高的定位準(zhǔn)確率。