基于GBDT的Wi-Fi室内定位算法研究

刘付杰，冯 涛*，高秀敏

（1.杭州电子科技大学电子信息学院，杭州 310000；2.上海理工大学光电信息与计算机工程学院，上海 200000）

室内定位技术是近些年研究的一个热点。常见的全球定位系统GPS在户外拥有非常好的定位效果，但是却无法应用于室内。户外的定位系统的可接受误差在几十米，而室内定位的预期误差则远远小于这个值，通常在几米范围之内，甚至更小。当前Wi-Fi指纹是用于室内定位的一种流行方法，该方法建立将RSS向量回归映射到水平坐标上的模型。KNN和 RandomForest算法常被用于基于指纹的室内定位中。但是由于墙壁的反射以及终端接入点位置环境的随机性都可能引起信号强度的变化，这些变化意味着变量之间的高度非线性交互作用，基于决策树的方法恰能很好地处理这种交互作用。考虑到这一点，本文决定将GBDT算法用于Wi-Fi指纹定位中，并测试它是否能够改进RandomForest算法获得的定位结果。根据现有已知信息，该算法还未被用在室内定位任务中。该算法将通过真实数据进行定位测试，并与典型的室内指纹定位算法KNN和RandomForest进行对比。实验结果表明：在有限的AP集中，GBDT算法拥有比KNN和Random-Forest更好的定位结果，具有一定的研究意义。

1 GBDT算法介绍

1.1 GBDT算法原理

GBDT是一种以Gradient Boosting框架结合决策树作为基学习器而构成的可用于回归和分类的机器学习算法。GBDT算法采用了一种贪心策略[1]，每次只训练一个基学习器，在训练基学习器的过程中，一种常用的方法叫做拟合残差。假设算法模型F(x;P)表示如下[2]：

式中β表示每个基学习器模型的权重；α表示每个基学习器模型的参数，模型参数可用如下公式表示：

式（2）表示对于M个样本点(xi, yi)，计算其在模型F(x;P)下的损失函数，最优解P可以使得损失函数最小。写成梯度下降形式的表示如下：

式（3）计算的参数βn,αn，用于确保模型Fn(x)的方向是前一个模型Fn-1(x)损失函数下降最快的方向。对于每一个数据点xi，都可以得到一个gn(xi)，最终可以得到一个完整的梯度下降方向：

为了确保Fn(x)能够在gn(x)的方向上，可以使用最小二乘法优化上面的公式得到：

计算得到αn的值后，可以计算得到βn，公式如下

最终合并的算法模型为：

上述介绍了GBDT算法的基本原理及框架，在后面的实验试验证中就将使用基于这一框架的算法模型。

2 实验设计与结果分析

2.1 数据采集与处理

室内定位的Wi-Fi指纹识别方法需要依靠测量的AP信号强度（RSS）建立的模型，定位过程中根据当前接受AP信号强度结合建立的模型来确定当前位置。为了确保实验数据的真实可靠以及最接近实际的工程应用，实验数据选择了某商场中的一个区域进行采集。该区域为一个长12m，宽9.6m，高3m的长方体，实验采集的AP信号强度数据全部来源于周边商铺提供的免费AP热点，AP热点的位置分布是未知的。实验环境中人员的移动，周围建筑的不规性以及AP热点位置的无规律性，都使得实验具有高度的泛化能力，更容易在实际工程中进行应用。

AP信号的收集使用的是型号为LeMax2的手机作为无线终端硬件，使用自己编写的软件对周围的13个AP信号进行采集。测试区域被划分为80个1.2×1.2m的小正方形块，共得到了99个采集点，考虑到Wi-Fi信号的易变性，每个点都采集了300组数据，其中79个点采集的23700组数据将作为训练集用于模型的学习，剩余的20个点采集的6000组数据作为测试集用于对模型性能进行测试评估。这里的每一条数据都由13个AP信号强度值和一个水平坐标组成，存放形式如｛[rss1，rss2，…，rss13][x，y]｝，rssi（i∈[1,13]）表示在坐标点（x，y）测得的第i个AP的信号强度值。

数据采集完成后，统计数据时发现每一个采集点所采集的AP信号数据都存在一定程度的缺失，周围环境的短暂变化以及某些AP信号在传播过程中过多衰减都会引起采集过程中信号强度值的丢失，采集点AP信号强度弱是导致数据缺失的主要原因，统计数据得到信号强度的变化区间是[-93，-30]，因此决定对缺失值采用补值处理，将数据集中的缺失值统一取值-100dbm。

2.2 实验设计

实验数据在前面已经做了说明，23700组数据作为训练集，6000组数据作为测试集。下面将使用这些数据对KNN、Random-Forest以及上述的GBDT算法进行仿真实验。实验中会使用控制变量法测试AP热点个数对三种算法最终定位结果的影响。文章将使用平均定位结果，以及80%位定位结果来比较三种算法在指纹定位任务中的优劣，仿真中使用的编程语言为Python3.6。

2.3 结果分析

首先，重复了KNN和RandomForest算法，并结合工程调参经验，使KNN和RandomForest在采集的数据集中达到最优定位结果。根据上面描述的GBDT算法模型，并对GBDT模型进行了参数调优。当KNN、RandomForest和GBDT在除AP个数参数外，其他参数固定的情况下，三种算法定位误差的均值和80%位值分别都随着AP个数的增加而降低，即AP个数越多，定位结果越好，但是当AP个数等于13时，三种算法的定位结果都比AP个数等于11时要差，以前面的结论相悖，在仔细分析了数据集之后，发现第13个AP采集数据的缺失值的个数要远远多于其他AP缺失值的个数。为了探究缺失值数量对定位结果的影响，决定选取一个缺失值只有7%的AP信号，通过增加其缺失值数量观察定位误差均值的变化，结果表明，当AP缺失值占比超过30%时，对定位结果产生较大影响。即信号质量差的AP并不会减小定位误差，并且还会起得相反的作用。因此，可以总结为有限的AP集中，AP数量的增加可以减小定位误差。这里的有限AP集包含的是AP信号缺失值占比不超过30%的AP。

三种算法在各自最优参数下20个点的定位误差的均值分别为KNN：2.299m、RF：2.15m和GBDT：1.8m，结果可以分析出，GBDT算法的定位结果在大多数情况下都要优于KNN和Random-Forest算法，并且在三种算法定位结果都在各自最优的情况下，GBDT定位误差的均值1.89m分别比KNN的2.30m和Random-Forest的2.17m减小了17%和13%，GBDT定位误差的80%位值能有效地控制在2.8m之内，分别比KNN的3.4m和RandomForest的3.1m的减小了18%和10%。

3 结束语

本文提出将GBDT算法应用于室内定位中，并且与KNN和RandomForest算法进行了相比。结果表明，在有限的AP集中，GBDT算法能够比KNN和RandomForest算法明显的减小室内定位的误差，具有一定的研究价值。后续将把该算法用于实际的工程中，探索其在工程中的应用价值。