走进高维空间之“维度魔咒”，所有的“邻居”都去哪了？( 三 ) 欢迎来到

文章图片

文章图片
正如我们上面所学到的， K-近邻算法的一般想法是确定在预测器空间中与索引点最接近的训练数据点，然后利用这些训练点的响应值来估计索引点的响应值。重要的是，我们只使用预测器空间中靠近的训练点来为估值提供信息。如果使用在预测空间中很远的训练数据点，那么它们可能不能很好地代表索引点的响应值，而我们的最终估计值可能与事实相差甚远。
在这个例子中，假设使用最接近索引点的10%的训练数据点，从索引点出发，需要在预测器空间中达到多远才能捕获10%的训练数据？更具体地说，需要在邻域中包括多大比例的预测值范围？
单预测器的情况实际上很简单。因为训练数据点是沿着单一维度均匀分布的，而预测器的范围是[-0.5,0.5] ，为了捕获10%的训练数据点，只需要包含预测器范围的10% 。如下图所示：

文章图片

文章图片
看上去很合理，对吗？我们不需要离索引点太远，就可以把10%的训练数据纳入，只需要在两个方向上取0.05个单位。目前看起来没什么特别，也许还有点无聊。让我们看看当入一个更高的维度时会发生什么。
邻居的秘密
假设我们有两个预测器，每个预测器的范围是-0.5到0.5 ，训练数据点沿两个维度均匀分布。

文章图片

文章图片
这是我们的索引点：

文章图片

文章图片
同样，我们希望捕捉10%的训练数据点。要做到这一点，每个预测器的范围中必须包括多少比例的邻居？也许我们可以把上面看到的扩展一个维度，我们将需要第一个预测器的10%和第二个预测器的10% 。让我们来看看（我把训练点淡化了一些，以便更好地观察）：

文章图片

文章图片
这是高维空间的奥秘中的另一个转折点！在单维空间中，我们只需要在索引空间的任何一个方向上取0.05个单位就可以捕获10%的训练数据。而现在，我们似乎必须从索引点的任何一个方向取0.16个单位，才能捕获10%的训练数据！就其预测值而言，邻域外围的训练点真的与索引点那么相似吗？答案最终将取决于数据的性质，但必须承认，当我们的目标是包括预测值与索引点尽可能相似的点时，包括每个预测器的近三分之一的范围似乎有点宽泛了。
我们继续，向三维预测器空间迈进! 下面是我们沿三个维度均匀分布的训练数据点云（左），以及索引点（右）。

文章图片

文章图片
也许你已经知答案，但我再次提出问题：为了获得10%的训练点，应该怎样取值？

文章图片

文章图片
将近50%!让我们消化一下：
在单维中，只需要包括单个预测器范围的10% ，就可以定义一个包括10%的均匀分布的训练数据的邻居。
在两个维度上，需要两个预测器的范围各占32% 。
在三个维度上，需要三个预测器范围中的每一个的46%!