KNN（最近邻算法）

浏览数：225 / 时间：2015年06月08日

KNN是最简单的机器学习算法之一。

在模式识别中，K-近邻算法（或近邻的简称）是一种用于分类和回归的非参数方法。[ 1 ]在这两种情况下，输入包含k个最近的训练样本在特征空间中。输出取决于近邻是用于分类或回归：

l 在kNN分类中，输出的是一个分类的关系。一个对象是由其邻居投票进行分类，被分类到最近的K个最近邻对象（k是一个正整数，通常小的）。如果k = 1，那么对象只是分配到单个最近邻。

l 在KNN回归中, 输出该对象的属性值，这个值是k个邻居的平均值。

K-NN是一种基于实例的学习，或懒惰的学习，其中函数是近似的局部和所有计算递延至分类。K-NN算法是其中最简单的机器学习算法。 K-NN算法是最简单的机器学习算法之一。

用于分类和回归，它可以根据分类贡献权重到最近的邻居，所以，附近的邻居有助于平均比更遥远的。例如，一个普通的加权方案是给每个邻居重1 / D，其中D是邻居的距离。

邻居是从一组对象的类（k-NN分类）或对象的属性值（k-NN回归）是已知的。这可以看作是对算法的训练，虽然没有明确的训练步骤是必需的。

一个缺点是K-NN算法是对数据的局部结构敏感。不能与k-均值混为一谈，另一种流行的机器学习技术。

算法

一个KNN分类的示例，测试样本（绿色的园）应该分类到哪一个类别，蓝色的正方形或者红色的三角形。如果k=3，(实线圈) 他会被分到第二类中，因为有两个三角形但是只有一个方形在这个圈里面。如果k=5，（虚线圈）他会被分到类别1（在圈里面有3个正方形，2个三角形）。

训练样本是在多维空间中的一组向量。每个样本有一个分类类别。在算法训练阶段值包括特征向量和训练样本的分类类别。在分类阶段，K是用户自定义的一个常数，和一组未标示的向量（查询或者测试点）指定标签在离查询点最近的K个样本中出现频率最高的那个类，

一种常用的连续变量距离度量是欧氏距离。对于离散变量，如文本分类，另一个度量可以使用，如重叠度量（或汉明距离）。在微阵列基因表达数据的上下文中，例如，在微阵列基因表达数据中，k-近邻还应用Pearson 和 spearman 提出的相关系数。通常情况下，使用距离度量学或者专门的算法k-近邻分类精度可以显著提高，如大边缘最近邻或邻里成分分析。最基本的一个缺点"多数表决"分类时发生类分布不均衡。那就是，更频繁的类的例子倾向于统治预测的新示例中，因为他们往往是常见的 k 个最近邻居，因为他们的数量很多。一种方法来克服这一问题是重量的分类，考虑到测试距离指向每个其 k近邻。类（或回归问题中的值）的每个 k 个最近点乘以正比从那点到测试点距离的逆的重量。另一种方式来克服不均衡是由抽象数据的表示形式。例如在自组织映射（SOM）中，每个节点是群集的相似点的代表（中心），不管他们在原始的训练数据中的密度。K-NN可应用于SOM。

参数选择

K 的最佳选择取决于数据；一般来说，k 值越大降低噪声对分类的影响，但使类之间的界限不明显。一个好的 k 可以选择通过各种启发式技术（请参见参数优化）。将预计选择为最靠近的训练样本的类的特殊情况下（即当 k = 1）称为的最近邻居算法。

属性

k-近邻是用一个统一的核函数的可变带宽，核密度"气球"估计的一个特殊情况。[8][9]

原始版本的算法很容易实现通过计算对所有存储的例子来计算测试用例之间的距离，但对于大量训练样本却是计算密集型操作。使用适当的最近邻搜索算法使 k-近邻在计算上更适用于大型数据集。多年来；提出了很多最近的近邻搜索算法，这些算法通常设法减少距离评价实际执行的数目。

k-近邻有一些强一致性的结果。随着数据量趋于无穷，该算法保证产量错误率没有两次贝叶斯错误率更糟（给出的数据分布可实现的误差最小率）。k-近邻在一些k值下被保证接近贝叶斯错误率 (k增加通过一个数据点条目的函数)。通过使用接近图，对 k-近邻的各种改进是可能的。

度量学习

K-近邻邻居分类性能往往可以通过（监督）的度量学习显著改善。流行的算法是Neighbourhood components analysis 和 Large margin nearest neighbor 。监督度量学习算法使用的标签信息来学习一种新的度量或伪度量。

特征提取

当对输入的数据和算法是太大，无法进行处理，它被怀疑是出现了冗余（例如使用英尺和米同时测量）然后输入的数据将变为一个精简的特征的集合（也称为特征矢量）。将输入的数据转换为特征的集合称为特征提取。如果提取的特征都经过精心挑选预期功能集将从输入数据提取相关信息，以执行所需的任务，使用这减少的特征的集合而不使用全尺寸输入。应用 k-近邻算法在特征空间中的变换数据之前进行原始数据进行特征提取。

示例使用 k-近邻包括人脸识别典型的计算机视觉计算中特征提取和尺寸减少的处理步骤（通常使用 OpenCV 实现）：

Haar face detection 小波人脸检测
Mean-shift tracking analysis 均值漂移跟踪分析
PCA 或 Fisher 线性判别分析投影到特征空间，其次是 k-近邻分类

降维

对于高维数据（例如，用 10 多个维度数目）通常是采用降维来避免维数灾难对k-近邻算法的影响。

在 k-近邻上下文中的维数灾难基本上意味着欧几里德距离是高维度是无益的，因为所有向量都是几乎等距搜索查询向量（想象更多或更少躺在一个圆上，查询点为中心的多个点；从查询到的搜索空间中的所有数据点的距离是几乎相同）。

特征提取和维数约简可以组合使用主成分分析（PCA）、线性判别分析（LDA）或典型相关分析（CCA）技术作为一个预处理步骤，紧接着由 k-NN处理降维后的特征向量。在机器学习这一过程也称为低维嵌入。

非常高维数据集（例如当执行相似性搜索视频直播、 DNA 数据或高维时间序列上），从 VLDB 工具箱运行使用局部性敏感散列算法（ locality sensitive hashing ）的快速近似 k-近邻搜索，"随机投影"（random projection ），"草图" （sketches ）或其他高维相似性搜索技术可能是唯一可行的方案。

聚类边界

最近邻规则实际上隐式计算决定边界。它还有可能来显式地计算决定边界，这样的计算复杂度是边界复杂度。

数据约简

数据约简是处理庞大的数据集工作的最重要问题之一。通常情况下，要准确的分类只需要部分数据点。这些数据被称为原型，可以通过如下方法找到：

1.类-异常值的选择，训练按 k-近邻（对于给定的 k）分类的不正确的数据

2.将其余的数据分成两组： (i) 用于决定分类的一些原型点 (ii) 通过K-NN原型分类正确的点，然后删除这些点。

类-异常值的选择

训练示例包围其他类的实例被称为类异常。类异常的原因包括：

随机误差

l 此类（一个孤立的例子，而不是群集）的训练示例很少

l 缺少重要特征（类分隔在其他方面，我们不知道）

l 对于小数据量的类会打不过数据量很大的类（不平衡）

异常点对于K-近邻类产生噪声。他们可以检测到并分离供将来分析。给定两个自然数、 k > r > 0，训练的例子称为（ k- r） NN 类异常，如果其 k 近邻包含超过r个其他类的例子。

CNN用于数据约简

凝聚最近邻（CNN，哈特算法）是设计来减少 k-近邻分类算法数据集的。它在训练数据中选择数据集原型 U ，这样 1NN 使用U可以与 1NN使用整个数据集一样准确地分类。

对于训练集 X，CNN 以迭代方式工作：

扫描 X中的元素，从 U 中寻找其最近的原型，具有一个和x不同的标签
从 X中删除 x 并将其添加到 U
重复扫描，直到没有更多的原型添加到U。

使用U分类而不是X。不是原型的点被称为"吸收"点。

它是有效扫描依次降低训练示例的边界比率。训练示例的边界比率 x 被定义为

a(x) = | |x‘-y||/ ||x-y||

| |x-y||是x到最近的拥有不同颜色示例 y的距离， | |x‘-y||是从 y 到其最近标签为x的最近的一点节点的距离。

计算边界比例

技术分享

边界比是在 [0，1] 区间，因为 | |x‘-y||永远不会超过 | |x-y||。这种排序优先考虑到类的边界列入 prototypes U 集合中。不同的标签比 x 点被称为 x 的外部。计算边界比率是右图所示。数据点标签的颜色：初始点是 x 和它的标签是红色的。外部点是蓝色和绿色。接近外部点 x 是 y。最接近 y 红点是 x‘。边框比 (x) = | |x‘-y||/||x-y||是属性的初始点 x。

下面是 CNN 在一系列的数字说明。有三类（红色、绿色和蓝色）。图 1：最初有 60 个点中的每个类。图 2 显示了 1NN 分类图：按 1NN 分类的每个像素使用的所有数据。图 3 显示了 5NN 分类图。白色区域对应的非机密的地区，那里 5NN 投票绑（例如，如果有两个绿色，两个红色和 5 最近邻之间的一个蓝点）。图 4 显示了减少的数据集。十字架是类离群值选定的（3，2）的神经网络规则（所有这些实例三近邻属于其他类）；正方形是原型，并吸收的点的空圆圈。左下角显示的类异常、原型和所有三类吸收的点的数量。原型数目变化从15%到 20%在此示例中的不同类别。图 5 显示了与原型 1NN 分类图是非常相似，与初始数据集。