本节书摘来自华章计算机《数据科学R语言实践：面向计算推理与问题求解的案例研究法》一书中的第1章，第1.5节,作者：[美]　德博拉·诺兰（Deborah Nolan）　　邓肯·坦普·朗（Duncan Temple Lang）　 更多章节内容可以访问云栖社区“华章计算机”公众号查看。

1.5　预测位置的最近邻方法

通过探测设备和若干个接入点之间的信号强度，我们可以使用很多种不同的统计技术来估计设备所处的位置。这里，我们使用一种相对简单、直观的方法，称为k-最近邻方法，或者简称为k-NN。最近邻方法（k=1）背后的思想为：我们已经拥有从遍布在大楼的已知位置上的多个接入点测量到的训练数据，这样，当我们拿到一个新的观测记录时，即一个未知位置上的一组信号强度值，我们从训练数据中找出与这个新观测记录最接近的观测记录。所谓“最接近”的意思是，在接入点与这个以前未观测的新位置之间记录到的信号强度，接近于在该接入点与训练数据中已观测到的位置之间的信号强度。然后，我们可简单地预测出，新观测点的位置就是与它最接近的训练观测点的位置。对k大于1的k-最近邻，我们找出k个最近的训练点（在信号强度范围内），通过聚合k个训练点的位置估算出新的观测点的位置。
我们自然想到用欧氏距离计算两组信号强度之间的距离，即

其中，Si是在手持设备与第i个接入点之间检测到的信号，属于在一些特定位置上观测到的训练数据；Si*是在新观测点与同一个接入点之间检测到的信号，该观测点的位置（x，y）正是我们所要预测的。
1.5.1　测试数据的准备
在线数据保存在online.final.trace.txt文件中，这些观测记录构成了我们的测试数据。我们使用1.2节里的readData()函数处理原始数据，执行如下：

有了这些测量记录所在的位置，就可以评估我们所做预测的精度。如同对待离线数据，我们也为在线数据创建唯一的位置标识符，执行如下：

使用这个新变量，可以确定出我们有60个唯一的测试位置，即

我们还要计算出在每个位置上所记录的信号强度的个数，执行：

这个输出结果说明，对于每个位置，只在一个方向上记录到了信号强度。
现在我们要计算由6个信号强度构成的向量之间的距离，可能需要将数据组织成不同于本章一直在使用的结构。特别是，不是将来自所有接入点的信号强度都作为一个数据框中的一列。我们按照6列信号强度来组织数据，即每个接入点对应于一列。我们将online数据汇总成如下格式，在每个位置上提供平均信号强度。

在数据框中，我们只保留了用于预测和评估的那些变量。这个新数据框应该有60行和11个变量，包括对应于MAC地址的6个平均信号强度。我们确认如下：

1.5.2　方向的选择
在最近邻模型中，我们想要从离线数据（即训练数据集）中找出与新观测点具有相似方向的记录，因为我们在1.3节中看到，方向可影响信号的强度。为此，我们可考虑使用某个方向上的所有记录，只要该方向在新观测点方向的指定范围之内。由于观测值是按照45霸隽拷屑锹迹虼宋颐强梢约虻サ刂付ㄔ谘盗肥葜兴Π牧诰咏嵌鹊母鍪＠纾绻颐侵灰桓龇较颍蛑话胄鹿鄄獾愕慕品较蛑灯ヅ涞慕嵌鹊难盗肥荨Ｈ绻颐且礁龇较颍蜓≡裎挥谛鹿鄄獾惴较蛄讲嗟母?5敖堑氖荩欢杂谌龇较颍颐茄≡裼胄鹿鄄獾惴较蜃罱咏?5霸隽康牧礁鼋嵌龋约霸谌我庖徊嗟牧硗庖桓鼋嵌龋灰来卫嗤啤Ｒ簿褪撬担菀慕嵌雀鍪齧和新观测点的角度angleNewObs，我们要从训练数据中找出所要包含的角度，执行如下：

注意，我们分别处理m为奇数和偶数的情况。我们也必须将角度映射为refs中的值，例如，-45映射为335，405映射为45，这样我们调整angles如下：

当我们有了所需要角度的数据子集之后，就可从offlineSummary中选择观测记录进行分析：

然后，我们从这些角度数据中聚集信号强度，创建一个类似于onlineSummary的数据结构。为了避免重复代码，我们将这些计算转化成一个辅助函数，称为reshapeSS():

我们对offlineSubset 进行汇总，并调整结构：

用于选择角度和调用reshapeSS()的代码可包装到一个函数里，这留作练习题。该函数有3个参数：angleNewObs为新观测点的角度，signals为训练数据（遵照offlineSummary格式的数据），m为signals中所要包含的角度个数。该函数返回一个与上面trainSS相匹配的数据框。
我们可以用130敖呛蚼为3的设置来测试函数，即对角度为90啊?35啊?80暗睦胂呤萁芯酆稀Ｖ葱腥缦虏僮鳎?

为了提高可读性，我们对执行结果的格式稍微进行了调整：

selectTrain()函数对各个角度取信号强度的平均值，为训练数据中的166个位置中的每一个位置产生一组信号强度，即

当然，我们也可以不对m个角度做信号强度的压缩处理，而是为每个接入点返回一组m×166的信号。我们把这个替代方案留作练习题。
1.5.3　发现最近邻
至此，我们已经拥有了可以用来预测新观测点的位置的训练数据集。我们打算利用信号强度来计算出这些训练数据与新观测点之间的距离。不管我们想要1个最近邻还是3个最近邻，都需要计算从新观测点到训练数据集中所有观测点的距离。为此，可以使用findNN()函数，执行如下：

这个函数的参数是由6个新的信号强度组成的一个数值型向量，以及来自selectTrain()函数的返回结果值。我们的函数将按照与新观测点信号强度接近程度的大小次序，返回训练观测点的位置。
我们可以使用这些排好序的位置子集来估计新观测点的位置。即对某些最近邻的k值，我们可简单地计算前k个位置的平均值。例如，如果closeXY包含从findNN()返回的x和y值（这些是排序过的训练位置），则我们估计新观测点的位置如下：

当然，我们不必只做简单的平均。例如，我们可在平均值计算中使用权重，权重的大小反比于该位置与测试观测点之间的距离（按照信号强度）。在这种情况下，我们需要使用从findNN()函数返回的距离值。这个替代方案允许我们包含k个相近的点，但按照它们与新观测信号的实际接近程度，对它们加以区分。对于观测信号的第i个最近邻，其权重可按如下公式计算：

其中，di是从新观测点到最近参照点（在信号强度空间内）的距离。也可考虑使用不同的度量方法。我们已经用过欧氏距离，但也可以尝试曼哈顿距离。在将邻居组合在一起预测（x，y）时，如果用于求平均的值的分布是非常倾斜的，也可以倾向于使用中位数，而不是平均值。这个替代方案留作练习题。
我们已开发了两个函数transSelect()和findNN()，用以提供训练集中那些与测试观测点具有相近信号强度的位置。下面对这个方法进行形式化，用于对所有的测试数据进行预测。定义predXY()如下：

我们用3个最近邻和3个方向对该函数进行测试：

为了评估该模型的拟合度，我们绘制一张包含实际位置和预测位置的地图。图1-12给出关于该模型和1-NN模型的地图。注意，一般来说，3-NN的误差较小。在3-NN模型中，即使存在大的误差看起来也没有什么问题，因为它们通常发生在走廊里。
除了通过视觉上比较预测位置和实际位置，我们也可以在数值上比较拟合度。例如，我们可以计算每张图中线段的长度，然后加以汇总，得出误差大小的测量值。或者，通过执行如下操作，找出误差平方之和：

我们将这个函数应用到上述两个误差集合上，可以发现：

这个结果证实我们在图中所看到的，3近邻确实比1近邻能够更好地预测位置。但还保留一个疑问：是否还存在有其他的k值，可用于建立更好的预测器。

图1-12　显示出预测位置和实际位置的楼层平面图。楼层平面图中的线段将测试位置（黑点）连接到它们的预测位置（星花）上。上方的图给出k=1最近邻的预测结果，下方的图给出k=3最近邻的预测结果。在该模型中，我们使用的训练数据是平均信号强度，这些信号强度来自166个离线位置（灰点）中的每一个位置，每个位置接收到6个接入点（黑方块）的信号，每个接入点上取出3个与测试数据的角度最接近的角度上的信号强度
1.5.4　交叉验证和k的选择
k是用于估计新的观测位置时所需包含的邻居的个数，k的选择属于模型选择问题。理想情况下，我们想选择一个独立于测试数据的k值，这样我们不会使模型过拟合于训练数据。借助于v重交叉检验可完成这个任务。其背后的思想很简单，把训练数据划分成v个相同大小的不重叠子集，然后对每个子集，我们用不属于该子集的数据进行建模，并使用这个留在外面的子集来评估模型的预测能力。对v重子集的每一个子集，我们重复对这个模型进行拟合和评估，然后汇总每重子集的预测误差。
对于最近邻情形，我们使用每个位置上的所有8个方向和6个MAC地址。这意味着我们在166个位置上进行交叉验证。假设，我们取v=11，则每一重具有floor(166/v)，或15个位置。我们用如下操作随机选择这些位置：

我们在调用matrix()时接收到一个警告信息，它指出v不能整除166，所以permuteLocs不能包含全部的166个位置。我们将包含15个位置的每个子集用作“在线”数据或测试数据。例如，第一重在线数据是：

我们需要对这些数据进行汇总，使得该数据结构与onlineSummary相匹配。这包括随机地选择一个方向，因为每个测试观测点只有一个方向（虽然我们也可从8个方向中找出最近邻的一个，但我们这里采用较简单的方式）。
回顾在1.5.1节中，我们将在线数据进行汇总，保存到一个数据结构中，该结构具有6列信号强度值，每列对应一个接入点。我们可以很容易地从offline中创建出全部测试数据，然后将这个数据结构划分成若干重。我们使用reshapeSS()函数完成这个任务。然而，这里有一个重要差别，我们打算为每一个位置随机选择一个角度。我们可以扩充reshapeSS()函数，使其可按条件执行这个选择，例如：

我们将这段代码合并进reshapeSS()函数中，并扩充该函数的定义，使其包含缺省值为FALSE的sampleAngle变量。之后，我们就可以对offline进行汇总和格式化如下：

现在，第一重数据是：

这个数据结构使得我们可以很容易地使用前面的代码来发现最近邻。第一重训练数据为：

这个数据子集也符合我们在前面应用最近邻方法所需要的正确格式。即对于这些在线数据和离线数据的交叉验证版本，我们可以使用predXY()函数：

然后，可以得出所做估计的误差：

对于每一重数据，我们想要对k=1, 2, …, K（K为适当大的值），找出k-NN估计。我们也要汇总所有v重子集中的误差。先简单地把前文中的代码包装进上面关于重数和邻居数的嵌套循环中。令K=20，执行如下：

图1-13给出了作为k的函数的误差平方和。我们看到该误差在开始时大幅度地减小，例如k = 1，2，3时。然后，误差在k = 5，6，7附近时呈平缓状态，之后，误差还是缓慢地增加，这是因为邻居在地理位置上太分散。

图1-13　利用交叉验证选择k。该曲线图显示出，误差平方和是用于预测新观测点位置的邻居个数的函数，它是通过对离线数据的交叉验证而得到的
我们将从交叉验证中得到的5作为最近邻个数，然后，应用到原先的训练集和测试集上，即

然后，我们计算预测中的误差如下：

早先，当k=1和k=3时的误差分别是659和307。选择k=5也许不能最小化在线数据上的误差，因为该值的选择并没有参考在线数据。这就是我们使用交叉验证的原因，即我们在选择k和评估预测时，均不使用在线数据。
对k进行交叉验证的代码的运行需要花费很长时间。我们大概想要检查这些代码，以找到加速执行的方法。例如，考虑函数predXY()，重新生成后如下所示：

我们记得，findNN()返回训练数据中的所有位置，并按照它们与新观测点信号强度的距离进行排序。我们可以使用开始的k个位置，但是，由于我们拥有所有的位置，因此可以计算出感兴趣的所有k值的估计值。cumsum()函数在这里非常有帮助，即cumsum(x[1:K])/(1:K)提供K均值。如果我们修改predXY()，使其返回所有的K估计值，则可以删除k上的内部循环。这将极大地加速代码。我们把对这个问题的探讨留作练习题。
至此，我们终于使用交叉验证方法完成了对邻居个数的选择。但是，还有另外一个参数没有进行探讨：包含在训练数据中的角度的个数。这个参数也可以通过交叉验证来选择。事实上，这两个参数可以通过交叉验证联合选择。我们把这个问题留作进一步探讨的练习题。