基于KNN算法的MRR数据分类研究

徐承亮+陈三龙

【摘 要】提出一种基于KNN算法的MRR的数据分类方法，用于LTE网络深度覆盖评估，根据室内室外MRR数据衰减不同的特点，经过训练获取最佳K值，利用KNN算法进行分类，并在此基础上提出加权KNN算法，提高分类准确率，有助于准确定位网络覆盖问题，为网络规划优化提供支撑。

【关键词】MRR KNN 数据分类

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基站的大规模建设，站点选择、室内室外投资比例分配策略将决定未来网络投资回报。同时4G网络覆盖优化将是一个非常重要的课题，直接影响客户感知，如何真实地反应网络的覆盖情况与用户的需求至关重要。传统网络覆盖的评估主要是通过DT、CQT及ATU测试方式进行，同时结合用户的投诉信息被动获取网络的覆盖情况。这些方式都无法准确了解整个网络的覆盖情况及用户需求，因此迫切需要一种可以主动准确获取网络质量的方式及平台，以用户需求为导向，能够指导TD-LTE网络设计及站点精确规划，为4G网络室分、室内建设投资提供依据，同时可以对3G、4G网络覆盖效果进行评估，为覆盖优化提供指导。

在无线通讯网络中，测量报告MRR（Measure-ment Result Recording，测量结果记录）数据是终端将所在位置基站的下行覆盖信号强度及干扰情况上报给基站侧，在MRR数据中同时会包含所处位置多个小区的信号情况。MRR分为两种：

（1）事件触发的MRR测量报告：对于连接态终端，网络下发测量事件给终端，主要用于切换判决及特定算法需求（如LTE中的ICIC算法），满足事件条件要求，终端将上报MRR，报告中包含主服务小区及满足切换条件的目标切换小区信号强度及质量信息。

（2）周期性测量报告：对于连接态终端，网络下发测量事件，终端启动测量，按照测量报告要求，周期性将测量到的服务小区及邻区的下行信号强度及质量上报给基站。

通过周期性MRR，可以掌握用户进行业务时所处位置网络下行准确覆盖情况，这些MRR能够真实反映用户活动区域网络覆盖及用户体验，如果对全网周期性MRR进行分析，可以了解整个网络的覆盖情况，分析全网覆盖问题小区。在以前网络覆盖分析时也会分析MRR数据，分析网络室分及室外弱覆盖小区，但是无法真正了解室外弱覆盖是来自宏站覆盖的室外区域还是室内区域以及MRR的地理位置信息，使得MRR数据的应用分析受到限制，无法充分挖掘MRR数据的价值。因此MRR数据精确分类，成为MRR信息进一步挖掘分析的前提。

2 基于KNN算法的MRR数据分类

2.1 KNN算法指导思想

KNN（K-Nearest Neighbor，K最邻近）算法是著名的模式识别统计学方法，是最好的文本分类算法之一，在机器学习分类算法中占有相当大的地位。KNN算法的指导思想是“近朱者赤，近墨者黑”，该方法的思路是：如果一个样本在特征空间中的K个最相似即特征空间中最邻近的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法中，所选择的邻居都是已经正确分类的对象。该方法在分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

如图1所示，绿色圆要被决定赋予哪个类，是红色三角形还是蓝色四方形？如果K=3，由于红色三角形所占比例为2/3，绿色圆将被赋予红色三角形的类；如果K=5，由于蓝色四方形比例为3/5，因此绿色圆被赋予藍色四方形类，这就是KNN算法的思想。

算法计算步骤：

（1）算距离：给定测试对象，计算它与训练集中的每个对象的距离；

（2）找邻居：圈定距离最近的K个训练对象，作为测试对象的近邻；

（3）做分类：根据这K个近邻归属的主要类别，来对测试对象分类。

算法流程：

（1）准备数据，对数据进行预处理。

（2）选用合适的数据结构存储训练数据和测试元组。

（3）设定参数，如K。

（4）维护一个大小为K的按距离由大到小的优先级队列，用于存储最近邻训练元组。随机从训练元组中选取K个元组作为初始的最近邻元组，分别计算测试元组到这K个元组的距离，将训练元组标号和距离存入优先级队列。

（5）遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离L与优先级队列中的最大距离Lmax进行比较。若L≥Lmax，则舍弃该元组，遍历下一个元组。若L

（6）遍历完毕，计算优先级队列中K个元组的多数类，并将其作为测试元组的类别。

（7）测试元组集测试完毕后计算误差率，继续设定不同的K值重新进行训练，最后取误差率最小的K值。

2.2 基于KNN算法的MRR数据分类系统架构

MRR（Measurement Result Recording）数据分类模块核心功能是利用KNN分类算法，区分宏站MRR来自覆盖区域室内还是室外，数据处理流程如图2所示：

（1）数据输入：站点工程参数（包括站点类型及邻区信息）、待分类MRR数据、算法训练数据。

（2）室分站点MRR数据分离：根据MRR数据中的小区名称区分MRR数据为室分还是宏站MRR数据。

（3）宏站小区MRR数据分类：使用KNN算法分类器对宏站MRR数据进行分类，区分MRR数据是室内区域还是室外区域。根据预先设置的信号强度阈值，预判MRR来自小区中心还是边缘位置，输出分类结果及位置信息。

（4）数据输出：输出MRR分类结果及初始位置信息，并存储到MRR数据库中，方便后续统计分析处理。

2.3 KNN分类算法训练

为了能够准确地对MRR数据进行分类，需要首先对KNN分类算法进行训练，选择欧式距离（如公式1）作为KNN算法相似度判定，找到能够获取最佳分类精确度的K值，主要步骤如图3所示。

欧式距离公式：

2.4 MRR数据种类及要求

MRR数据分为室分站点MRR数据和室外宏站MRR数据，MRR数据格式如图4所示。

图4为LTE周期性MRR文件格式：eNB id=******，MRR报告中绿色为测量报告中测量量LteScRSRP：服务小区RSRP，LteNcRSRP：邻小区RSRP。黄色第一列为一条MRR中服务小区RSRP：40，第二列为多个邻区的RSRP：36、34、32、31、30、19，实际信号强度为上报值减去140，即服务小区RSRP=40-140=-100 dBm。

为了能够准确地对MRR数据进行分类，需要在定制MRR上报规则时至少上报6个及以上邻区信号强度，上报邻区信号数目多少将决定MRR分类的准确性。对收集的MRR数据先进行预处理，每条MRR记录格式要求如下：

[服务小区：CGI（小区全球标识），小区名称，PCI，RSRP，

邻区1：CGI（小区全球标识），小区名称，PCI，RSRP，

邻区2：CGI（小区全球标识），小区名称，PCI，RSRP，

…]

2.5 MRR数据KNN分类器训练及测试

由于路测时可以获取主服务小区与邻区的信号强度，数据格式与MRR数据一致，因此为了对分类算法进行训练测试，可以从ATU路测数据中获取宏站覆盖室外样本数据，同时针对无室内分布系统的场景进行大量测试，获取室外宏站覆盖室内时信号样本，使用Matlab对算法进行测试仿真。

（1）分类器训练阶段输入

由室内信号样本与室外信号样本构成的7345个训练样本，每个样本有7个维度，分别为：主服务小区PCCPCH RSCP及6个最强邻区RSCP，训练样本类别，与训练样本一一对应。

（2）训练结果分析

利用KNN算法直接对测试数据进行分类，训练数据1000个，仿真K不同取值时算法准确度。从室内测试样本点中取500个样点作为训练数据；从室外测试样本点中取500个样点作为训练数据；设置训练样本的类别；将剩余的室内外测试样本作为待测数据，使用基础KNN算法进行分类，分类准确率如表1所示。

（3）分类结果分析

K取不同值时，算法的准确率会有变化，K值越大，计算复杂度越高。由于室内样点数目太少，因此分类结果存在误差，增加室内样点数再进行训练。

利用KNN算法直接对测试数据进行分类，训练数据800个，仿真K不同取值时算法准确度。从室内测试样本点中取400个样点作为训练数据；从室外测试样本点中取400个样点作为训练数据；设置训练样本的类别；将剩余的室内外測试样本作为待测数据，使用基础KNN算法进行分类，分类准确率如表2所示。

本次仿真减少了训练样本数目，同时与第一次仿真相比修改了样本内容，导致对室内测试数据分类的准确率没有第一次仿真结果好，因此算法分类准确度受K值及样本的影响较大，针对此问题提出改进的KNN算法。

2.6 基于加权KNN算法

为了使算法收敛，保持稳定，提出改进的基于加权KNN分类算法的MRR数据分类。

最终种类权值Y=W1×X1+W2×X2+W3×X3

（1）

X1：使用KNN算法对MRR数据中的RSRP直接进行分类，分类结果中属于类1的比例；

W1：直接分类所占权值；

X2：使用KNN算法对每条MRR数据服务小区RSRP与所有邻区RSRP求差值，对差值结果进行分类，分类结果中属于类1的比例；

W2：按照差值分类所占权值；

X3：使用KNN算法对MRR数据中服务小区RSRP与所有邻区RSRP取比值，对比值进行分类，分类结果中属于类1的比例；

W3：按照比值分类所占权值。

主要处理步骤：

（1）直接用KNN算法对预处理后的MRR数据进行分类，获取分类结果X1。

（2）对预处理之后的MRR数据进行差值处理，使用KNN算法对每条MRR数据服务小区RSRP与所有邻区RSRP求差值，对差值结果进行分类，获取分类结果X2。

（3）对预处理之后的MRR数据进行求比值处理，使用KNN算法对每条MRR数据服务小区RSRP与所有邻区RSRP求比值，对比值结果进行分类，获取分类结果X3。

（4）根据最终种类权值

Y=W1×X1+W2×X2+W3×X3获取最后分类结果。

经过多次训练，获取最佳权值W1=0.3，W2=0.5，

W3=0.2，然后再訓练确定最优K值，选择K=401作为分类器最佳取值，不同K值时分类精确度如表3所示：

3 结论

本文利用KNN算法对MRR数据进行分类，基于KNN算法分类准确率可达99.36%，分类准确率受样本量机及K值影响较大，因此提出基于加权KNN算法的MRR分类方法，改善K值对分类正确率的影响，分类准确率达90%以上。

参考文献：

[1] 陈源惠.OSS系统中MRR和NCS进行无线覆盖评估的研究[J]. 移动通信， 2009，33（24）： 57-62.

[2] 侯士江，刘车华，余靖，等. 空间网络数据库中的K个最近邻查询算法[J]. 计算机科学， 2006，33（8）： 360-362.

[3] 周靖，刘晋胜. 一种采用类相关度优化距离的KNN算法[J]. 微计算机应用， 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]. 昆明： 云南大学， 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]. 电讯技术， 2004，44（6）： 97-100.

[10] 黄贤英，李沁东，刘英涛. 结合词性的短文本相似度算法及其在文本分类中的应用[J]. 电讯技术， 2017，57（1）.