Cover定理：粗略地说，它说给定任何随机的有限点集（带有任意标签），然后通过将它们映射到更高维度[2]，这些点很可能是线性可分的[1]。

启示：很好，这个定理告诉我的是，如果我把我的数据集和这些点映射到更高的维度，那么我可以很容易地找到一个线性分类器。然而，大多数分类器需要计算某种相似度，如点积，这意味着分类算法的时间复杂度与数据点的维度成正比。因此，更高的维度意味着更大的时间复杂度（更不用说存储那些大维度点的空间复杂度了）。

内核技巧：设是数据点的原始维度，是将这些点映射到维度为的空间的映射。现在，如果有一个函数从原始空间获取输入和，那么我能够计算点积在更高维空间中，但复杂度而不是。$n$$f$$N (>> n)$$K$$x$$y$$K(x, y) = \langle f(x), f(y) \rangle$$O(n)$$O(N)$

启示：所以，如果分类算法只依赖于点积而不依赖于实际的映射，我可以使用核技巧在高维空间中运行算法，几乎没有额外的成本。$f$

线性可分性是否意味着来自同一类的点会比来自不同类的点更接近？ 不，没有这样的保证。线性可分性并不真正意味着来自同一类的点变得更近了，或者来自两个不同类的点变得更远了。

那么为什么 kNN 会起作用呢？ 它不需要！但是，如果确实如此，那纯粹是因为内核。

这意味着什么？ 考虑布尔特征向量。当您使用二次多项式内核时，特征向量被映射到向量$x = (x_1, x_2)$$x$$(x_1^2, \sqrt{2} x_1x_2, x_2^2)$. 从一个布尔特征向量中，只需使用二次多项式，我们就得到了一个“连词”的特征向量。因此，内核本身会产生一些出色的特征图。如果您的数据具有良好的原始特征，并且您的数据是否可以从这些内核创建的特征映射中受益。所谓好处，我的意思是这些特征图产生的特征可以使来自同一类的点彼此靠近，并将来自不同类的点推开，然后 kNN 将从使用内核中受益。否则，结果与在原始数据上运行 kNN 得到的结果没有什么不同。

那为什么要使用内核kNN？ 我们展示了使用内核的计算复杂度仅比通常的 kNN 略高，如果数据从使用内核中受益，那么为什么不使用它们呢？

是否有任何论文研究过哪类数据可以从 kNN 中的内核中受益？ 据我所知，没有。

[1] http://en.wikipedia.org/wiki/Linear_separability
[2] http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4038449&tag=1