基于机器学习的室内定位方法综述

徐龙阳

摘要：针对现有的室内定位方法存在高成本、低精度、鲁棒性低等问题。一些学者尝试将机器学习（Machine Learning，ML）引入室内定位中，用机器学习思想解决上述问题，旨在提高定位方法的性能。文章首先详细综述了五种基于K-最近邻、人工神经网络、支持向量机、决策树以及贝叶斯的定位方法，然后对这些方法的定位性能进行了比较分析，结果表明合适的机器学习算法能够提高定位精度、增强系统鲁棒性和降低成本，最后总结了基于机器学习的室内定位方法未来的一些研究热点问题。

关键词：室内定位；机器学习；神经网络

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2018）01-0217-03

Abstract：In some indoor positioning methods that there are existing some problems of a high cost， low accuracy and low robustness. Some scholars try to introduce Machine Learning （ML） into indoor positioning， and use machine learning to solve the problems mentioned above， aiming at improving the performance of positioning method. Firstly， the five kinds of localization methods Based on k-NN， ANN，SVM， decision tree and Bayesian are summarized. Then the positioning performance of these methods is compared and analyzed. The results show that the appropriate machine learning algorithm can improve the positioning accuracy， enhance the robustness of the system and reduce the cost. Finally， some research hotspots in the future of the indoor learning method Based on machine learning are summarized.

Key words： Indoor positioning； machine learning； neural network

1 概述

隨着人类社会快速发展，在高度城市化的现代社会，人们对空间位置信息的需求不断提高，定位技术也越来越多受到人们的重视[1]。尤其是近些年，基于GPS定位系统、移动互联网、智能手机等技术提供的位置信息服务，给人们日常生活带来极大的便利。人们可以利用其提供的位置服务来进行打车、叫外卖、寻找银行甚至交友等。除此之外，在一些大型商场、工厂、医院、写字楼以及地下煤矿等复杂的室内环境下的位置信息需求也很迫切。但由于在室内环境下无法有效感测到卫星信号，因此GPS定位系统并不能提供足够精度的位置信息来满足人们在该环境下的定位需求[2]。基于此，一些国内外学者对解决室内环境下的定位问题做了广泛而深入的研究。

目前，现有的室内定位方法主要有基于测距和非测距定位两大类，基于测距定位具体的方法有到达时间TOA ，到达时间差TDOA，到达角AOA等。基于非测距定位主要有接受信号强度指示RSSI，一般又分为距离路径衰减模型法和位置指纹匹配法 。根据在室内定位中采用的介质不同，主要有移动传感器 、可见光、红外线、射频识别RFID 、超宽带 、Zigbee 、无线局域网WLAN以及无线传感器网WSN等多种室内定位技术。这些技术有些需要专门设备，成本较大，难以大规模推广应用。有些易受环境、信号等干扰影响定位效果。因此，如何低成本高精度普适性好地实现复杂的室内环境下的定位，已成为当前室内定位技术中的研究热点、难点之一。

近些年，一些学者将机器学习引入室内定位中，利用机器学习思想来解决室内定位问题。本文首先详细综述了五种基于机器学习的定位方法，然后对定位方法的定位性能进行比较分析，最后总结了基于机器学习的定位方法未来的一些研究热点问题。

2 主要的机器学习定位方法

本节五种主要的算法分别是K-最近邻、人工神经网络、支持向量机、决策树以及贝叶斯等。

2.1KNN算法

K最近邻算法KNN是一种简单成熟的分类技术。通过计算距离的度量作为相似性度量。常用于指纹匹配阶段，在定位时利用KNN算法计算目标值与指纹库里的样本值之间的欧式距离，按距离大小进行排序，选取前K个最小距离的参考点，然后以这K个参考点的平均位置作为目标估计的位置。

利用KNN算法作为指纹匹配算法，定位精度受选取的K值影响较大，K值太大太小都会造成较大误差，因此优化K值提高定位效果如Liu Chunyan等人[3]的几何聚类指纹库的约束加权KNN定位模型。

加权k最近邻算法Weighted-KNN是一种改进的KNN算法，一般根据K个参考点与样本点之间距离大小赋予不同的权值，距离越近权值越大。定位时将加权后的几何质心作为目标估计的位置。WKNN算法可以通过调整权值来优化分类结果，所以在性能上优于传统的KNN算法。

KNN算法理论简单，K值对KNN算法定位性能影响很大，大部分优化的KNN算法都是对K值进行优化。因为算法需要遍历数据库里所有样本数据，因此对于数据量过大的数据库使用KNN算法会有较大的计算量。endprint

2.2 人工神经网络方法

人工神经网络ANN是一种模仿人脑神经网络结构进行学习、处理问题的网络模型。

传统的基于RSSI的距离路径衰减模型定位方法依赖于模型参数的选取，这些参数没有统一标准化的准则来度量，只能靠拟合或人工经验去估计，不准确的估计会大大影响模型的性能。因此，张会清等人[4]通过训练BP神经网络拟合模型参数A和n，A为收发距离为1m的路径损耗值，n为路径衰减系数，避免了传统的复杂拟合或经验估计。

在位置指纹匹配法中，刘侃等人[5]采用四层的深度神经网络进行RSSI指纹定位。通过堆叠去躁自编码器对网络结构进行预训练，并用反向传播进行全局微调。自动地从具有波动性的无线信号里提取特征并进行线性变换计算目标的位置坐标。该方法实现较高的定位准确率和增强了系统鲁棒性。

利用人工神经网络模型定位，能适应噪声数据训练，具有较强的非线性映射能力和良好的数据拟合能力。通过网络的学习能力能减少指纹构建更新成本和自适应环境变化。但前期需要大量数据训练网络模型来调整其权值、阈值等参数，增加了训练成本。

2.3 支持向量机方法

支持向量机SVM是一种通过搜寻最大边缘超平面来确定最优决策边界的分类回归算法。通过核函数将非线性问题映射到高维特征空间中进行线性分类。并用松弛系数或惩罚系数来调整分类结果。因此，在解决高维、非线性分类问题有优势。可以将SVM良好的分类、回归能力应用到室内定位。

利用SVM分类模型定位，将定位问题看作是分类问题。前期通过数据训练分类模型，然后将目标样本数据输入训练好的分类模型，对应输出一个最优分类结果，再利用具体的估计方法得出目标的位置。在位置指纹定位法中，朱宇佳等人[6]将指纹匹配過程设计成多分类问题。根据室内建筑结构，划分合适的网格区域。每个网格代表一个类别，然后用各个网格接受到的RSSI值和信标节点编号信息训练SVM分类模型。

据上述介绍，基于SVM定位方法，凭借SVM出色的分类回归能力，可以很好地解决多分类，高维、非线性分类问题。但也带来较大的分类计算成本，且训练过程时间较长。

2.4 决策树方法

决策树（Decision Tree）是一个以树结构形式构建的分类模型。用决策树算法进行室内定位先利用训练的数据，构造一颗决策树模型。再通过该模型对输入的数据特征判别进行分类，依据分类结果确定目标的位置。

行人航迹推算PDR的定位系统，常需要外部定位系统来保持精度和初始化。该算法存在传感器漂移导致的累积误差。因此，针对降低计算复杂度，减少累积误差等问题。Liao J K等人[7]在室内地图信息辅助下引入低复杂度的模糊决策树以减少对硬件设备依赖提高系统的准确性和稳定性。通过移动步长、候选区域选择、方向估计三部分来构造模糊决策树中的三个内部节点进行特征判别定位。为进一步提高模糊决策树定位精度。

通过决策树算法进行定位，分类准确率较高，自上而下的建树分类过程具有较好的可视化效果，易于理解。利用决策树分类模型不需要太多训练数据，算法计算成本较低，能耗较少，适合应用到对能耗有限制要求的定位系统中。但当建树过深，分支过多易发生过拟合问题和最优化问题。

2.5 贝叶斯方法

贝叶斯分类（Bayesian）算法是一种基于概率统计学知识的分类算法。朴素贝叶斯分类（Naive Bayes）是基于贝叶斯定理和假设特征条件相互独立的分类方法。

在基于RSSI的距离路径衰减模型法中，由于室内环境复杂导致同一参考点RSSI值分布不同，因此可以多次测量RSSI值，从中选取优质的值作为采集的数据，从而减少噪声的RSSI值使用。如Liu Huan等人[8]基于贝叶斯概率模型提出一种优化RSSI的无线传感网络定位系统。通过多次测量RSSI值并把测量的RSSI值看成符合正态分布概率事件。利用贝叶斯概率模型只筛选出现“大概率事件”的RSSI值，再利用三边测量技术和最小二乘法来估计未知节点的位置。该方法通过筛选出优质RSSI值，降低了平均定位误差。

在位置指纹定位中，利用贝叶斯算法进行定位在离线阶段将在每个参考点采集的无线信号特征值作为指纹数据，计算每个参考点的指纹数据概率分布并存储，即已知位置的指纹概率分布的先验概率。在线阶段利用存储的先验概率计算目标指纹在各个参考点的后验概率，选取最大的后验概率所在的参考点位置作为目标指纹的估计位置。

基于贝叶斯分类算法定位具有处理多分类问题的优势，因为计算量大不适用于大规模数据库。朴素贝叶斯算法易于实现，但它是建立在条件相互独立假设基础上的，实际应用中特征之间不可能绝对的独立，因此影响了实际的定位效果。

3 定位方法的比较分析

本节对上文详细介绍的一些基于机器学习的室内定位方法进行比较分析，从精度、准确度、成本、鲁棒性以及优缺点等方面给出比较结果。经过分析总结，在室内定位中使用的机器学习主要有提高定位精度、增强系统鲁棒性以及降低系统成本等三大优点。

（1） 提高定位精度

通过使用的机器学习算法可以在三个方面来提高定位精度。具体如下：

1） 优化模型参数：通过优化模型参数，提高模型定位精度。Zhang等人通过训练BP神经网络拟合模型参数A和n，达到优化参数的目的[4]。

2） 抗环境变化：利用一些算法的学习能力、提取有效特征的能力来适应环境变化。降低误差：通过一些回归模型来估计校正测量、匹配误差来提高精度。

3） 数据预处理：通过对数据进行除噪、除冗余来提高精度。如利用贝叶斯概率模型筛选出优质的RSSI值[8]。

（2） 增强系统鲁棒性

基于无线信号的室内定位方法易受到环境变化、信号干扰、衰减以及非视距等因素影响。利用合适的机器学习算法能有效降低这些变化影响。可以通过一些神经网络模型的在线学习、更新能力不断调整模型参数适应环境的变化，增强系统鲁棒性。endprint

（3） 降低系统成本

降低成本主要表现在通过使用一些机器学习算法来降低指纹库构建更新、计算分类以及能耗等三个方面成本。具体如下：

1） 指纹库构建：在指纹定位中，通过一些算法自学习能力构建、更新指纹库来降低建造维护成本。

2） 减少计算分类成本：通过定位区域划分若干子区域进行粗定位等来减少分类和计算成本[6]。

3） 降低能耗：可以选择一些低计算复杂度、低能耗的算法来节省能耗，如决策树[7]。

4 结束语

本文主要对五种基于机器学习算法的定位方法进行综述并对其定位性能进行归纳比较。最后总结出使用合适的机器学习算法具有提高定位精度，增强系统鲁棒性以及降低系统成本等优点。目前，室内定位技术仍有一些问题没有得到令人满意的解决。

通过对基于机器学习的室内定位方法学习研究，未来有一些值得深入研究的热点问题。

1） 指纹库构建、更新。传统的指纹库构建、更新成本较大，严重影响指纹定位方法的推广应用。因此，国内外一些学者提出一种基于CrowdSensing的定位方法[9]。该方法无需专门人员采集指纹数据就可建库。这是一种利用群智感知的思想并结合机器学习与数据挖掘技术来完成指纹库构建与更新。

2） 设备异质性。在指纹采集阶段，使用不同的硬件设备在同一参考点采集到的指纹地图是不同的。一种解决方法是通过使用其他比较稳健的位置特征如RSSI的信号强度差异SSD作为位置指纹，然而该方法增加了指纹的维度和计算复杂度。如果从减少校准成本和降低计算复杂度角度出发，尝試利用机器学习解决设备异质性问题是个不错的选择。

参考文献：

[1] 邓中亮. 室内外无线定位与导航[M].北京邮电大学出版社，2013.

[2] 席瑞， 李玉军， 侯孟书. 室内定位方法综述[J]. 计算机科学，2016，43（4）：1-6.

[3] 刘春燕， 王坚. 基于几何聚类指纹库的约束KNN室内定位模型[J]. 武汉大学学报：信息科学版，2014， 39（11）：1287-1292.

[4] 张会清， 石晓伟， 邓贵华，等. 基于BP神经网络和泰勒级数的室内定位算法研究[J].电子学报，2012， 40（9）：1876-1879.

[5] 刘侃， 张伟， 张伟东，等. 一种基于深度神经网络的无线定位方法[J].计算机工程，2016，42（7）：82-85.

[6] 朱宇佳， 邓中亮， 刘文龙，等. 基于支持向量机多分类的室内定位系统[J].计算机科学， 2012，39（4）：32-35.

[7] Liao J K， Chiang K W， Tsai G J， et al. A low complexity map-aided Fuzzy Decision Tree for pedestrian indoor/outdoor navigation using smartphone[C]// International Conference on Indoor Positioning and Indoor Navigation. 2016：1-8.

[8] 刘欢，黄丽，杨晓，等.一种贝叶斯优化RSSI和ILS的室内定位算法[J].中国科技论文，2015（20）：2377-2381.

[9] 吴陈沭.基于群智感知的无线室内定位[D].清华大学，2015.endprint