基于KNN算法的MRR數(shù)據(jù)分類研究

徐承亮+陳三龍

【摘 要】提出一種基于KNN算法的MRR的數(shù)據(jù)分類方法，用于LTE網(wǎng)絡(luò)深度覆蓋評估，根據(jù)室內(nèi)室外MRR數(shù)據(jù)衰減不同的特點，經(jīng)過訓(xùn)練獲取最佳K值，利用KNN算法進(jìn)行分類，并在此基礎(chǔ)上提出加權(quán)KNN算法，提高分類準(zhǔn)確率，有助于準(zhǔn)確定位網(wǎng)絡(luò)覆蓋問題，為網(wǎng)絡(luò)規(guī)劃優(yōu)化提供支撐。

【關(guān)鍵詞】MRR KNN 數(shù)據(jù)分類

Research on MRR Data Classification Based on KNN Algorithm

[Abstract] In this paper， a MRR data classification method based on KNN algorithm was proposed to evaluate the in-depth coverage for LTE networks. According to the different attenuation between the indoor and outdoor MRR data， the K value was gotten by training. KNN algorithm was used to classify data， and the weighted KNN algorithm was put forward which not only enhances the accuracy of classification， but also precisely locates the trouble of network coverage. It can provide a powerful support to the network planning and optimization.

[Key words]MRR KNN data classification

1 引言

隨著TD-LTE基站的大規(guī)模建設(shè)，站點選擇、室內(nèi)室外投資比例分配策略將決定未來網(wǎng)絡(luò)投資回報。同時4G網(wǎng)絡(luò)覆蓋優(yōu)化將是一個非常重要的課題，直接影響客戶感知，如何真實地反應(yīng)網(wǎng)絡(luò)的覆蓋情況與用戶的需求至關(guān)重要。傳統(tǒng)網(wǎng)絡(luò)覆蓋的評估主要是通過DT、CQT及ATU測試方式進(jìn)行，同時結(jié)合用戶的投訴信息被動獲取網(wǎng)絡(luò)的覆蓋情況。這些方式都無法準(zhǔn)確了解整個網(wǎng)絡(luò)的覆蓋情況及用戶需求，因此迫切需要一種可以主動準(zhǔn)確獲取網(wǎng)絡(luò)質(zhì)量的方式及平臺，以用戶需求為導(dǎo)向，能夠指導(dǎo)TD-LTE網(wǎng)絡(luò)設(shè)計及站點精確規(guī)劃，為4G網(wǎng)絡(luò)室分、室內(nèi)建設(shè)投資提供依據(jù)，同時可以對3G、4G網(wǎng)絡(luò)覆蓋效果進(jìn)行評估，為覆蓋優(yōu)化提供指導(dǎo)。

在無線通訊網(wǎng)絡(luò)中，測量報告MRR（Measure-ment Result Recording，測量結(jié)果記錄）數(shù)據(jù)是終端將所在位置基站的下行覆蓋信號強(qiáng)度及干擾情況上報給基站側(cè)，在MRR數(shù)據(jù)中同時會包含所處位置多個小區(qū)的信號情況。MRR分為兩種：

（1）事件觸發(fā)的MRR測量報告：對于連接態(tài)終端，網(wǎng)絡(luò)下發(fā)測量事件給終端，主要用于切換判決及特定算法需求（如LTE中的ICIC算法），滿足事件條件要求，終端將上報MRR，報告中包含主服務(wù)小區(qū)及滿足切換條件的目標(biāo)切換小區(qū)信號強(qiáng)度及質(zhì)量信息。

（2）周期性測量報告：對于連接態(tài)終端，網(wǎng)絡(luò)下發(fā)測量事件，終端啟動測量，按照測量報告要求，周期性將測量到的服務(wù)小區(qū)及鄰區(qū)的下行信號強(qiáng)度及質(zhì)量上報給基站。

通過周期性MRR，可以掌握用戶進(jìn)行業(yè)務(wù)時所處位置網(wǎng)絡(luò)下行準(zhǔn)確覆蓋情況，這些MRR能夠真實反映用戶活動區(qū)域網(wǎng)絡(luò)覆蓋及用戶體驗，如果對全網(wǎng)周期性MRR進(jìn)行分析，可以了解整個網(wǎng)絡(luò)的覆蓋情況，分析全網(wǎng)覆蓋問題小區(qū)。在以前網(wǎng)絡(luò)覆蓋分析時也會分析MRR數(shù)據(jù)，分析網(wǎng)絡(luò)室分及室外弱覆蓋小區(qū)，但是無法真正了解室外弱覆蓋是來自宏站覆蓋的室外區(qū)域還是室內(nèi)區(qū)域以及MRR的地理位置信息，使得MRR數(shù)據(jù)的應(yīng)用分析受到限制，無法充分挖掘MRR數(shù)據(jù)的價值。因此MRR數(shù)據(jù)精確分類，成為MRR信息進(jìn)一步挖掘分析的前提。

2 基于KNN算法的MRR數(shù)據(jù)分類

2.1 KNN算法指導(dǎo)思想

KNN（K-Nearest Neighbor，K最鄰近）算法是著名的模式識別統(tǒng)計學(xué)方法，是最好的文本分類算法之一，在機(jī)器學(xué)習(xí)分類算法中占有相當(dāng)大的地位。KNN算法的指導(dǎo)思想是“近朱者赤，近墨者黑”，該方法的思路是：如果一個樣本在特征空間中的K個最相似即特征空間中最鄰近的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。KNN算法中，所選擇的鄰居都是已經(jīng)正確分類的對象。該方法在分類決策上只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分樣本所屬的類別。

如圖1所示，綠色圓要被決定賦予哪個類，是紅色三角形還是藍(lán)色四方形？如果K=3，由于紅色三角形所占比例為2/3，綠色圓將被賦予紅色三角形的類；如果K=5，由于藍(lán)色四方形比例為3/5，因此綠色圓被賦予藍(lán)色四方形類，這就是KNN算法的思想。

算法計算步驟：

（1）算距離：給定測試對象，計算它與訓(xùn)練集中的每個對象的距離；

（2）找鄰居：圈定距離最近的K個訓(xùn)練對象，作為測試對象的近鄰；

（3）做分類：根據(jù)這K個近鄰歸屬的主要類別，來對測試對象分類。

算法流程：

（1）準(zhǔn)備數(shù)據(jù)，對數(shù)據(jù)進(jìn)行預(yù)處理。

（2）選用合適的數(shù)據(jù)結(jié)構(gòu)存儲訓(xùn)練數(shù)據(jù)和測試元組。

（3）設(shè)定參數(shù)，如K。

（4）維護(hù)一個大小為K的按距離由大到小的優(yōu)先級隊列，用于存儲最近鄰訓(xùn)練元組。隨機(jī)從訓(xùn)練元組中選取K個元組作為初始的最近鄰元組，分別計算測試元組到這K個元組的距離，將訓(xùn)練元組標(biāo)號和距離存入優(yōu)先級隊列。

（5）遍歷訓(xùn)練元組集，計算當(dāng)前訓(xùn)練元組與測試元組的距離，將所得距離L與優(yōu)先級隊列中的最大距離Lmax進(jìn)行比較。若L≥Lmax，則舍棄該元組，遍歷下一個元組。若L

（6）遍歷完畢，計算優(yōu)先級隊列中K個元組的多數(shù)類，并將其作為測試元組的類別。

（7）測試元組集測試完畢后計算誤差率，繼續(xù)設(shè)定不同的K值重新進(jìn)行訓(xùn)練，最后取誤差率最小的K值。

2.2 基于KNN算法的MRR數(shù)據(jù)分類系統(tǒng)架構(gòu)

MRR（Measurement Result Recording）數(shù)據(jù)分類模塊核心功能是利用KNN分類算法，區(qū)分宏站MRR來自覆蓋區(qū)域室內(nèi)還是室外，數(shù)據(jù)處理流程如圖2所示：

（1）數(shù)據(jù)輸入：站點工程參數(shù)（包括站點類型及鄰區(qū)信息）、待分類MRR數(shù)據(jù)、算法訓(xùn)練數(shù)據(jù)。

（2）室分站點MRR數(shù)據(jù)分離：根據(jù)MRR數(shù)據(jù)中的小區(qū)名稱區(qū)分MRR數(shù)據(jù)為室分還是宏站MRR數(shù)據(jù)。

（3）宏站小區(qū)MRR數(shù)據(jù)分類：使用KNN算法分類器對宏站MRR數(shù)據(jù)進(jìn)行分類，區(qū)分MRR數(shù)據(jù)是室內(nèi)區(qū)域還是室外區(qū)域。根據(jù)預(yù)先設(shè)置的信號強(qiáng)度閾值，預(yù)判MRR來自小區(qū)中心還是邊緣位置，輸出分類結(jié)果及位置信息。

（4）數(shù)據(jù)輸出：輸出MRR分類結(jié)果及初始位置信息，并存儲到MRR數(shù)據(jù)庫中，方便后續(xù)統(tǒng)計分析處理。

2.3 KNN分類算法訓(xùn)練

為了能夠準(zhǔn)確地對MRR數(shù)據(jù)進(jìn)行分類，需要首先對KNN分類算法進(jìn)行訓(xùn)練，選擇歐式距離（如公式1）作為KNN算法相似度判定，找到能夠獲取最佳分類精確度的K值，主要步驟如圖3所示。

歐式距離公式：

2.4 MRR數(shù)據(jù)種類及要求

MRR數(shù)據(jù)分為室分站點MRR數(shù)據(jù)和室外宏站MRR數(shù)據(jù)，MRR數(shù)據(jù)格式如圖4所示。

圖4為LTE周期性MRR文件格式：eNB id=******，MRR報告中綠色為測量報告中測量量LteScRSRP：服務(wù)小區(qū)RSRP，LteNcRSRP：鄰小區(qū)RSRP。黃色第一列為一條MRR中服務(wù)小區(qū)RSRP：40，第二列為多個鄰區(qū)的RSRP：36、34、32、31、30、19，實際信號強(qiáng)度為上報值減去140，即服務(wù)小區(qū)RSRP=40-140=-100 dBm。

為了能夠準(zhǔn)確地對MRR數(shù)據(jù)進(jìn)行分類，需要在定制MRR上報規(guī)則時至少上報6個及以上鄰區(qū)信號強(qiáng)度，上報鄰區(qū)信號數(shù)目多少將決定MRR分類的準(zhǔn)確性。對收集的MRR數(shù)據(jù)先進(jìn)行預(yù)處理，每條MRR記錄格式要求如下：

[服務(wù)小區(qū)：CGI（小區(qū)全球標(biāo)識），小區(qū)名稱，PCI，RSRP，

鄰區(qū)1：CGI（小區(qū)全球標(biāo)識），小區(qū)名稱，PCI，RSRP，

鄰區(qū)2：CGI（小區(qū)全球標(biāo)識），小區(qū)名稱，PCI，RSRP，

…]

2.5 MRR數(shù)據(jù)KNN分類器訓(xùn)練及測試

由于路測時可以獲取主服務(wù)小區(qū)與鄰區(qū)的信號強(qiáng)度，數(shù)據(jù)格式與MRR數(shù)據(jù)一致，因此為了對分類算法進(jìn)行訓(xùn)練測試，可以從ATU路測數(shù)據(jù)中獲取宏站覆蓋室外樣本數(shù)據(jù)，同時針對無室內(nèi)分布系統(tǒng)的場景進(jìn)行大量測試，獲取室外宏站覆蓋室內(nèi)時信號樣本，使用Matlab對算法進(jìn)行測試仿真。

（1）分類器訓(xùn)練階段輸入

由室內(nèi)信號樣本與室外信號樣本構(gòu)成的7345個訓(xùn)練樣本，每個樣本有7個維度，分別為：主服務(wù)小區(qū)PCCPCH RSCP及6個最強(qiáng)鄰區(qū)RSCP，訓(xùn)練樣本類別，與訓(xùn)練樣本一一對應(yīng)。

（2）訓(xùn)練結(jié)果分析

利用KNN算法直接對測試數(shù)據(jù)進(jìn)行分類，訓(xùn)練數(shù)據(jù)1000個，仿真K不同取值時算法準(zhǔn)確度。從室內(nèi)測試樣本點中取500個樣點作為訓(xùn)練數(shù)據(jù)；從室外測試樣本點中取500個樣點作為訓(xùn)練數(shù)據(jù)；設(shè)置訓(xùn)練樣本的類別；將剩余的室內(nèi)外測試樣本作為待測數(shù)據(jù)，使用基礎(chǔ)KNN算法進(jìn)行分類，分類準(zhǔn)確率如表1所示。

（3）分類結(jié)果分析

K取不同值時，算法的準(zhǔn)確率會有變化，K值越大，計算復(fù)雜度越高。由于室內(nèi)樣點數(shù)目太少，因此分類結(jié)果存在誤差，增加室內(nèi)樣點數(shù)再進(jìn)行訓(xùn)練。

利用KNN算法直接對測試數(shù)據(jù)進(jìn)行分類，訓(xùn)練數(shù)據(jù)800個，仿真K不同取值時算法準(zhǔn)確度。從室內(nèi)測試樣本點中取400個樣點作為訓(xùn)練數(shù)據(jù)；從室外測試樣本點中取400個樣點作為訓(xùn)練數(shù)據(jù)；設(shè)置訓(xùn)練樣本的類別；將剩余的室內(nèi)外測試樣本作為待測數(shù)據(jù)，使用基礎(chǔ)KNN算法進(jìn)行分類，分類準(zhǔn)確率如表2所示。

本次仿真減少了訓(xùn)練樣本數(shù)目，同時與第一次仿真相比修改了樣本內(nèi)容，導(dǎo)致對室內(nèi)測試數(shù)據(jù)分類的準(zhǔn)確率沒有第一次仿真結(jié)果好，因此算法分類準(zhǔn)確度受K值及樣本的影響較大，針對此問題提出改進(jìn)的KNN算法。

2.6 基于加權(quán)KNN算法

為了使算法收斂，保持穩(wěn)定，提出改進(jìn)的基于加權(quán)KNN分類算法的MRR數(shù)據(jù)分類。

最終種類權(quán)值Y=W1×X1+W2×X2+W3×X3

（1）

X1：使用KNN算法對MRR數(shù)據(jù)中的RSRP直接進(jìn)行分類，分類結(jié)果中屬于類1的比例；

W1：直接分類所占權(quán)值；

X2：使用KNN算法對每條MRR數(shù)據(jù)服務(wù)小區(qū)RSRP與所有鄰區(qū)RSRP求差值，對差值結(jié)果進(jìn)行分類，分類結(jié)果中屬于類1的比例；

W2：按照差值分類所占權(quán)值；

X3：使用KNN算法對MRR數(shù)據(jù)中服務(wù)小區(qū)RSRP與所有鄰區(qū)RSRP取比值，對比值進(jìn)行分類，分類結(jié)果中屬于類1的比例；

W3：按照比值分類所占權(quán)值。

主要處理步驟：

（1）直接用KNN算法對預(yù)處理后的MRR數(shù)據(jù)進(jìn)行分類，獲取分類結(jié)果X1。

（2）對預(yù)處理之后的MRR數(shù)據(jù)進(jìn)行差值處理，使用KNN算法對每條MRR數(shù)據(jù)服務(wù)小區(qū)RSRP與所有鄰區(qū)RSRP求差值，對差值結(jié)果進(jìn)行分類，獲取分類結(jié)果X2。

（3）對預(yù)處理之后的MRR數(shù)據(jù)進(jìn)行求比值處理，使用KNN算法對每條MRR數(shù)據(jù)服務(wù)小區(qū)RSRP與所有鄰區(qū)RSRP求比值，對比值結(jié)果進(jìn)行分類，獲取分類結(jié)果X3。

（4）根據(jù)最終種類權(quán)值

Y=W1×X1+W2×X2+W3×X3獲取最后分類結(jié)果。

經(jīng)過多次訓(xùn)練，獲取最佳權(quán)值W1=0.3，W2=0.5，

W3=0.2，然后再訓(xùn)練確定最優(yōu)K值，選擇K=401作為分類器最佳取值，不同K值時分類精確度如表3所示：

3 結(jié)論

本文利用KNN算法對MRR數(shù)據(jù)進(jìn)行分類，基于KNN算法分類準(zhǔn)確率可達(dá)99.36%，分類準(zhǔn)確率受樣本量機(jī)及K值影響較大，因此提出基于加權(quán)KNN算法的MRR分類方法，改善K值對分類正確率的影響，分類準(zhǔn)確率達(dá)90%以上。

參考文獻(xiàn)：

[1] 陳源惠.OSS系統(tǒng)中MRR和NCS進(jìn)行無線覆蓋評估的研究[J]. 移動通信， 2009，33（24）： 57-62.

[2] 侯士江，劉車華，余靖，等. 空間網(wǎng)絡(luò)數(shù)據(jù)庫中的K個最近鄰查詢算法[J]. 計算機(jī)科學(xué)， 2006，33（8）： 360-362.

[3] 周靖，劉晉勝. 一種采用類相關(guān)度優(yōu)化距離的KNN算法[J]. 微計算機(jī)應(yīng)用， 2010（11）： 7-12.

[4] Hall P， Samworth B U P A R J. Choice of Neighbor Order in Nearest-Neighbor Classification[J]. The Annals of Statistics， 2008（5）： 2135-2152.

[5] Pan J， Manocha D. Bi-level Locality Sensitive Hashing for k-Nearest Neighbor Computation[A]. ACM Sigspatial International Symposium on Advances in Geographic Information Systems[C]. 2012： 378-389.

[6] Michel M Deza， Elena Deza. Encyclopedia of Distances[Z]. Springer， 2009.

[7] 孫秋月. 基于SNN相似度的KNN算法研究[D]. 昆明： 云南大學(xué)， 2008.

[8] H Wang. Nearest Neighbors without k： A Classification Formalism Based on Probability， Technical Report， Faculty of Informatics[Z]. University of Ulster， 2002.

[9] 楊靜，張祖凡. 移動通信無線覆蓋均勻性分析[J]. 電訊技術(shù)， 2004，44（6）： 97-100.

[10] 黃賢英，李沁東，劉英濤. 結(jié)合詞性的短文本相似度算法及其在文本分類中的應(yīng)用[J]. 電訊技術(shù)， 2017，57（1）.