kNN算法总结

雨点打透心脏的1/2处 2022-05-16 14:34 307阅读 0赞

一直接触KNN近邻算法，但是一直没有机会系统的总结一下，现在做一下总结，希望加深一下自己对近邻算法的理解。

定义：K-近邻算法采用测量不同特征值之间的距离方法进行分类

优缺点：

优点：精度高、对异常值不敏感（个别的异常值不会影响分析结果）、无数据输入假定

缺点：计算复杂度高（需要计算新的数据点与样本集中每个数据的“距离”，以判断是否是前k个邻居），空间复杂度高（巨大的矩阵）；

使用数据范围：

数值型（目标变量可以从无限的数值集合中取值）

标称型（标称型目标变量的结果只在有限目标集中取值，如真与假(标称型目标变量主要用于分类)）

算法原理：

官方解释：存在一个样本数据集，也称作训练样本集，并且样本中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系，输入没有标签的新数据后，将新数据的每个特征与样本集中的数据对应的特征进行比较，然后算法提取样本集中特征最相似的数据（最近邻）的分类标签。一般来说，我们只选择样本集中前k个最相似的数据，这就是k-近邻算法中k的出处，通常k是不大于20的整数，最后，选择k个最相似的数据中出现次数最多的分类，作为新数据的分类。

我的理解：k-近邻算法就是根据“新数据的分类取决于它的邻居”进行的，比如邻居中大多数都是退伍军人，那么这个人也极有可能是退伍军人。而算法的目的就是先找出它的邻居，然后分析这几位邻居大多数的分类，极有可能就是它本省的分类

KNN算法适用最近邻分类和最近邻回归两种情况。但是实现原理基本上是相通的。

首先运用KNN算法做分类处理：

找到最近邻：

from sklearn.neighbors import NearestNeighbors
    import numpy as np
    X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
    nbrs = NearestNeighbors(n_neighbors=2, algorithm='ball_tree').fit(X)
    distances, indices = nbrs.kneighbors(X)
    distances
    
    
    array([[0.        , 1.        ],
           [0.        , 1.        ],
           [0.        , 1.41421356],
           [0.        , 1.        ],
           [0.        , 1.        ],
           [0.        , 1.41421356]])

分类：

最近邻分类属于 *基于实例的学习* 或 *非泛化学习* ：它不会去构造一个泛化的内部模型，而是简单地存储训练数据的实例。 分类是由每个点的最近邻的简单多数投票中计算得到的：一个查询点的数据类型是由它最近邻点中最具代表性的数据类型来决定的。

scikit-learn 实现了两种不同的最近邻分类器：[`KNeighborsClassifier`][KNeighborsClassifier] 基于每个查询点的 ![k][] 个最近邻实现，

其中 ![k][] 是用户指定的整数值。[`RadiusNeighborsClassifier`][RadiusNeighborsClassifier] 基于每个查询点的固定半径 ![r][] 内的邻居数量实现， 其中 ![r][] 是用户指定的浮点数值。

![k][] -邻居分类是 [`KNeighborsClassifier`][KNeighborsClassifier] 下的两种技术中比较常用的一种。![k][] 值的最佳选择是高度依赖数据的：

通常较大的 ![k][] 是会抑制噪声的影响，但是使得分类界限不明显。

如果数据是不均匀采样的，那么 [`RadiusNeighborsClassifier`][RadiusNeighborsClassifier] 中的基于半径的近邻分类可能是更好的选择。

用户指定一个固定半径 ![r][]，使得稀疏邻居中的点使用较少的最近邻来分类。

对于高维参数空间，这个方法会由于所谓的 “维度灾难” 而变得不那么有效。

基本的最近邻分类使用统一的权重：分配给查询点的值是从最近邻的简单多数投票中计算出来的。 在某些环境下，最好对邻居进行加权，使得更近邻更有利于拟合。可以通过 `weights` 关键字来实现。

默认值 `weights = 'uniform'` 为每个近邻分配统一的权重。而 `weights = 'distance'` 分配权重与查询点的距离成反比。 或者，用户可以自定义一个距离函数用来计算权重。

回归：

最近邻回归是用在数据标签为连续变量，而不是离散变量的情况下。分配给查询点的标签是由它的最近邻标签的均值计算而来的。

scikit-learn 实现了两种不同的最近邻回归：[`KNeighborsRegressor`][KNeighborsRegressor] 基于每个查询点的 ![k][] 个最近邻实现， 其中 ![k][] 是用户指定的整数值。[`RadiusNeighborsRegressor`][RadiusNeighborsRegressor] 基于每个查询点的固定半径 ![r][] 内的邻点数量实现， 其中 ![r][] 是用户指定的浮点数值。

基本的最近邻回归使用统一的权重：即，本地邻域内的每个邻点对查询点的分类贡献一致。 在某些环境下，对邻点加权可能是有利的，使得附近点对于回归所作出的贡献多于远处点。 这可以通过 `weights` 关键字来实现。默认值 `weights = 'uniform'` 为所有点分配同等权重。 而 `weights = 'distance'` 分配的权重与查询点距离呈反比。 或者，用户可以自定义一个距离函数用来计算权重。

## 最近邻算法 ##

### 1. 暴力计算 ###

最近邻的快速计算是机器学习中一个活跃的研究领域。最简单的近邻搜索的实现涉及数据集中所有成对点之间距离的暴力计算： 对于 ![D][] 维度中的 ![N][] 个样本来说, 这个方法的复杂度是 ![O\[D N^2\]][O_D N_2]。 对于小数据样本，高效的暴力近邻搜索是非常有竞争力的。 然而，随着样本数 ![N][] 的增长，暴力方法很快变得不切实际了。在 [`sklearn.neighbors`][sklearn.neighbors] 类中， 暴力近邻搜索通过关键字 `algorithm = 'brute'` 美\[ˈælɡəˌrɪðəm\]来指定，并通过 [`sklearn.metrics.pairwise`][sklearn.metrics.pairwise] 中的例程来进行计算。

### 2. K-D 树 ###

为了解决效率低下的暴力计算方法，已经发明了大量的基于树的数据结构。总的来说， 这些结构试图通过有效地编码样本的 aggregate distance (聚合距离) 信息来减少所需的距离计算量。 基本思想是，若 ![A][]点距离 ![B][] 点非常远，![B][] 点距离 ![C][] 点非常近， 可知 ![A][] 点与 ![C][] 点很遥远，*不需要明确计算它们的距离*。 通过这样的方式，近邻搜索的计算成本可以降低为 ![O\[D N \\log(N)\]][O_D N _log_N] 或更低。 这是对于暴力搜索在大样本数 ![N][] 中表现的显著改善。

利用这种聚合信息的早期方法是 *KD tree* 数据结构（\* K-dimensional tree\* 的简写）, 它将二维 *Quad-trees* 和三维 *Oct-trees* 推广到任意数量的维度. KD 树是一个二叉树结构，它沿着数据轴递归地划分参数空间，将其划分为嵌入数据点的嵌套的各向异性区域。 KD 树的构造非常快：因为只需沿数据轴执行分区, 无需计算 ![D][]\-dimensional 距离。 一旦构建完成, 查询点的最近邻距离计算复杂度仅为 ![O\[\\log(N)\]][O_log_N] 。 虽然 KD 树的方法对于低维度 (![D < 20][D _ 20]) 近邻搜索非常快, 当 ![D][] 增长到很大时, 效率变低: 这就是所谓的 “维度灾难” 的一种体现。 在 scikit-learn 中, KD 树近邻搜索可以使用关键字 `algorithm = 'kd_tree'` 来指定, 并且使用类 [`KDTree`][KDTree] 来计算。

References:

*  [“Multidimensional binary search trees used for associative searching”][Multidimensional binary search trees used for associative searching], Bentley, J.L., Communications of the ACM (1975)

### 3. Ball 树 ###

为了解决 KD 树在高维上效率低下的问题, *ball 树* 数据结构就被研发出来了. 其中 KD 树沿卡迪尔轴（即坐标轴）分割数据, ball 树在沿着一系列的 hyper-spheres （多维球）来分割数据. 通过这种方法构建的树要比 KD 树消耗更多的时间, 但是这种数据结构对于高结构化的数据是非常有效的, 即使在高维度上也是一样.

ball 树将数据递归地划分为由质心 ![C][] 和半径 ![r][] 定义的节点,

使得节点中的每个点位于由 ![r][] 和 ![C][] 定义的 hyper-sphere 内. 通过使用 *triangle inequality（三角不等式）* 减少近邻搜索的候选点数:

![|x+y| \\leq |x| + |y|][x_y_ _leq _x_ _ _y]

通过这种设置, 测试点和质心之间的单一距离计算足以确定距节点内所有点的距离的下限和上限. 由于 ball 树节点的球形几何, 它在高维度上的性能超出 *KD-tree*, 尽管实际的性能高度依赖于训练数据的结构. 在 scikit-learn 中, 基于 ball 树的近邻搜索可以使用关键字 `algorithm = 'ball_tree'` 来指定, 并且使用类 [`sklearn.neighbors.BallTree`][sklearn.neighbors.BallTree] 来计算. 或者, 用户可以直接使用 [`BallTree`][sklearn.neighbors.BallTree] 类.

参考:

*  [“Five balltree construction algorithms”][Five balltree construction algorithms], Omohundro, S.M., International Computer Science Institute Technical Report (1989)

### 4. 最近邻算法的选择 ###

对于给定数据集的最优算法是一个复杂的选择, 并且取决于多个因素:

*  样本数量 ![N][] (i.e. `n_samples`) 和维度 ![D][] (例如. `n_features`).
    
     *  *Brute force* 查询时间以 ![O\[D N\]][O_D N] 增长
     *  *Ball tree* 查询时间大约以 ![O\[D \\log(N)\]][O_D _log_N] 增长
     *  *KD tree* 的查询时间 ![D][] 的变化是很难精确描述的.
        
        对于较小的 ![D][] (小于20) 的成本大约是 ![O\[D\\log(N)\]][O_D_log_N], 并且 KD 树更加有效.
        
        对于较大的 ![D][] 成本的增加接近 ![O\[DN\]][O_DN], 由于树结构引起的开销会导致查询效率比暴力还要低.
    
    对于小数据集 (![N][] 小于30), ![\\log(N)][log_N] 相当于 ![N][], 暴力算法比基于树的算法更加有效.
    
    [`KDTree`][KDTree] 和 [`BallTree`][sklearn.neighbors.BallTree] 通过提供一个 *leaf size*参数来解决这个问题:
    
    这控制了查询切换到暴力计算样本数量. 使得两种算法的效率都能接近于对较小的 ![N][] 的暴力计算的效率.
 *  数据结构: 数据的 *intrinsic dimensionality* (本征维数) 和/或数据的 *sparsity* (稀疏度). 本征维数是指数据所在的流形的维数 ![d \\le D][d _le D], 在参数空间可以是线性或非线性的. 稀疏度指的是数据填充参数空间的程度(这与“稀疏”矩阵中使用的概念不同, 数据矩阵可能没有零项, 但是从这个意义上来讲,它的 **structure** 仍然是 “稀疏” 的)。
    
     *  *Brute force* (暴力查询)时间不受数据结构的影响。
     *  *Ball tree* 和 *KD tree* 的数据结构对查询时间影响很大. 一般地, 小维度的 sparser (稀疏) 数据会使查询更快. 因为 KD 树的内部表现形式是与参数轴对齐的, 对于任意的结构化数据它通常不会表现的像 ball tree 那样好.
    
    在机器学习中往往使用的数据集是非常结构化的, 而且非常适合基于树结构的查询。
 *  query point（查询点）所需的近邻数 ![k][] 。
    
    >  *  *Brute force* 查询时间几乎不受 ![k][]值的影响.
    >  *  *Ball tree* 和 *KD tree* 的查询时间会随着 ![k][] 的增加而变慢. 这是由于两个影响: 首先, ![k][] 的值越大在参数空间中搜索的部分就越大. 其次, 使用 ![k > 1][k _ 1] 进行树的遍历时, 需要对内部结果进行排序.
    
    当 ![k][] 相比 ![N][] 变大时, 在基于树的查询中修剪树枝的能力是减弱的. 在这种情况下, 暴力查询会更加有效.
 *  query points（查询点）数. ball tree 和 KD Tree 都需要一个构建阶段. 在许多查询中分摊时，这种结构的成本可以忽略不计。 如果只执行少量的查询, 可是构建成本却占总成本的很大一部分. 如果仅需查询很少的点, 暴力方法会比基于树的方法更好.

一般地, `algorithm = 'auto'` 选择 `'kd_tree'` 如果 ![k < N/2][k _ N_2] 并且 `'effective_metric_'` 在 `'kd_tree'`的列表 `'VALID_METRICS'` 中. 它选择 `'ball_tree'` 如果 ![k < N/2][k _ N_2] 并且 `'effective_metric_'` 在 `'ball_tree'` 的列表 `'VALID_METRICS'` 中. 它选择 `'brute'` 如果 ![k < N/2][k _ N_2] 并且 `'effective_metric_'`不在 `'kd_tree'` 或 `'ball_tree'` 的列表 `'VALID_METRICS'` 中. 它选择 `'brute'` 如果 ![k >= N/2][k _ N_2 1].

这种选择基于以下假设: 查询点的数量与训练点的数量至少在相同的数量级, 并且 `leaf_size` 接近其默认值 `30`.

### 5. `leaf_size` 的影响 ###

如上所述, 对于小样本暴力搜索是比基于数的搜索更有效的方法. 这一事实在 ball 树和 KD 树中被解释为在叶节点内部切换到蛮力搜索. 该开关的级别可以使用参数 `leaf_size` 来指定. 这个参数选择有很多的效果:

**构造时间**

更大的 `leaf_size` 会导致更快的树构建时间, 因为需要创建更少的节点.

**查询时间**

一个大或小的 `leaf_size` 可能会导致次优查询成本. 当 `leaf_size` 接近 1 时, 遍历节点所涉及的开销大大减慢了查询时间. 当 `leaf_size`, 接近训练集的大小，查询变得本质上是暴力的. 这些之间的一个很好的妥协是 `leaf_size = 30`, 这是该参数的默认值.

**内存** 随着leaf\_size的增加，存储树结构所需的内存减少。 对于存储每个节点的D维质心的ball tree，这点至关重要。 针对 [`BallTree`][sklearn.neighbors.BallTree] 所需的存储空间近似于 `1 / leaf_size` 乘以训练集的大小.

`leaf_size` 不被 brute force queries（暴力查询）所引用.

## 5. 最近质心分类 ##

该 [`NearestCentroid`][NearestCentroid] 分类器是一个简单的算法, 通过其成员的质心来表示每个类。 实际上, 这使得它类似于 `sklearn.KMeans` 算法的标签更新阶段. 它也没有参数选择, 使其成为良好的基准分类器. 然而，它确实受到非凸类的影响，即当类有显著不同的方差时。所以这个分类器假设所有维度的方差都是相等的。 对于没有做出这个假设的更复杂的方法, 请参阅线性判别分析 ([`sklearn.discriminant_analysis.LinearDiscriminantAnalysis`][sklearn.discriminant_analysis.LinearDiscriminantAnalysis]) 和二次判别分析 ([`sklearn.discriminant_analysis.QuadraticDiscriminantAnalysis`][sklearn.discriminant_analysis.QuadraticDiscriminantAnalysis]). 默认的 [`NearestCentroid`][NearestCentroid] 用法示例如下:

>>>

>>> from sklearn.neighbors.nearest_centroid import NearestCentroid
    >>> import numpy as np
    >>> X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])
    >>> y = np.array([1, 1, 1, 2, 2, 2])
    >>> clf = NearestCentroid()
    >>> clf.fit(X, y)
    NearestCentroid(metric='euclidean', shrink_threshold=None)
    >>> print(clf.predict([[-0.8, -1]]))
    [1]

### 1. 最近缩小质心 ###

该 [`NearestCentroid`][NearestCentroid] 分类器有一个 `shrink_threshold`参数, 它实现了 nearest shrunken centroid 分类器. 实际上, 每个质心的每个特征的值除以该特征的类中的方差. 然后通过 `shrink_threshold` 来减小特征值. 最值得注意的是, 如果特定特征值过0, 则将其设置为0. 实际上，这个方法移除了影响分类器的特征。 这很有用, 例如, 去除噪声特征.

在以下例子中, 使用一个较小的 shrink 阀值将模型的准确度从 0.81 提高到 0.82.

<table> 
 <tbody> 
  <tr> 
   <th>target:</th> 
   <td>../auto_examples/neighbors/plot_nearest_centroid.html</td> 
  </tr> 
  <tr> 
   <th>scale:</th> 
   <td>50</td> 
  </tr> 
 </tbody> 
</table>

**![nearest\_centroid\_1][nearest_centroid_1]![nearest\_centroid\_2][nearest_centroid_2]**

![../\_images/sphx\_glr\_plot\_regression\_0011.png][.._images_sphx_glr_plot_regression_0011.png]

举例说明KNN算法关于分类的简单运用：

鸢尾花的简单分类

from sklearn.datasets import load_iris
    li=load_iris()
    def claffication(point):
        x=li.data
        y=li.target
        knn=KNeighborsClassifier(n_neighbors=3)
        knn.fit(x,y)
        print(knn.predict(point))
    num=np.array([[7.2,3.5,5.7,2.8]])
    claffication(num)
    import  matplotlib.pyplot as plt
    plt.scatter(li.data[:,2],li.data[:,0],c=li.target)

结果显示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU3NTAyMA_size_16_color_FFFFFF_t_70][]

如何评价模型优劣：

在sklearn中包含四种评价尺度，分别为mean\_squared\_error、mean\_absolute\_error、explained\_variance\_score 和 r2\_score。

1、均方差（mean-squared-error）

2、平均绝对值误差（mean\_absolute\_error）

3.可释方差得分（explained\_variance\_score）

explained variation measures the proportion to which a mathematical model accounts for the variation (dispersion) of a given data set

4.中值绝对误差（Median absolute error）

5.R2 决定系数（拟合优度）

模型越好：r2→1

模型越差：r2→0

用法示例

from sklearn.metrics import r2\_score  
   
y\_true = \[1,2,4\]  
y\_pred = \[1.3,2.5,3.7\]  
r2\_score(y\_true,y\_pred)

[KNeighborsClassifier]: http://sklearn.apachecn.org/cn/0.19.0/modules/generated/sklearn.neighbors.KNeighborsClassifier.html#sklearn.neighbors.KNeighborsClassifier
[k]: /images/20220503/e21a65091b214bc68b1336a524863393.png
[RadiusNeighborsClassifier]: http://sklearn.apachecn.org/cn/0.19.0/modules/generated/sklearn.neighbors.RadiusNeighborsClassifier.html#sklearn.neighbors.RadiusNeighborsClassifier
[r]: /images/20220503/9ac6f74072c1415dbf640df9247ac873.png
[KNeighborsRegressor]: http://sklearn.apachecn.org/cn/0.19.0/modules/generated/sklearn.neighbors.KNeighborsRegressor.html#sklearn.neighbors.KNeighborsRegressor
[RadiusNeighborsRegressor]: http://sklearn.apachecn.org/cn/0.19.0/modules/generated/sklearn.neighbors.RadiusNeighborsRegressor.html#sklearn.neighbors.RadiusNeighborsRegressor
[D]: /images/20220503/bfac08dfe581479e9d5139b3fbb8458f.png
[N]: /images/20220503/8f318dfb5e2c4d7b9694f2202b3c10d4.png
[O_D N_2]: http://sklearn.apachecn.org/cn/0.19.0/_images/math/757e6525671255d8689148b8b5d1fb62403f0d5e.png
[sklearn.neighbors]: http://sklearn.apachecn.org/cn/0.19.0/modules/classes.html#module-sklearn.neighbors
[sklearn.metrics.pairwise]: http://sklearn.apachecn.org/cn/0.19.0/modules/classes.html#module-sklearn.metrics.pairwise
[A]: http://sklearn.apachecn.org/cn/0.19.0/_images/math/0043fe6507e9b1d112e07a2801e24927e267dd50.png
[B]: http://sklearn.apachecn.org/cn/0.19.0/_images/math/9805f44feec6f81d376d09e88b8236635edbb3c8.png
[C]: /images/20220503/52c804b3286c4bdf8f3741d72d9e8a8b.png
[O_D N _log_N]: http://sklearn.apachecn.org/cn/0.19.0/_images/math/b9b92f23dce9bff3b9b0f68f3051f307da0fa7d9.png
[O_log_N]: http://sklearn.apachecn.org/cn/0.19.0/_images/math/d62a221f87954d151fa2c39566f1a243a294e625.png
[D _ 20]: http://sklearn.apachecn.org/cn/0.19.0/_images/math/7842f70bd20e56ab5363a6ae2466b4e9e4af6594.png
[KDTree]: http://sklearn.apachecn.org/cn/0.19.0/modules/generated/sklearn.neighbors.KDTree.html#sklearn.neighbors.KDTree
[Multidimensional binary search trees used for associative searching]: http://dl.acm.org/citation.cfm?doid=361002.361007
[x_y_ _leq _x_ _ _y]: /images/20220503/4eded5f50f0240b785a9ce135357b2e0.png
[sklearn.neighbors.BallTree]: http://sklearn.apachecn.org/cn/0.19.0/modules/generated/sklearn.neighbors.BallTree.html#sklearn.neighbors.BallTree
[Five balltree construction algorithms]: http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.91.8209
[O_D N]: /images/20220503/4a293c23f8ed49579aa84f0e6d232b02.png
[O_D _log_N]: /images/20220503/1448d285d2d7418aa05d9c2d98e6f541.png
[O_D_log_N]: http://sklearn.apachecn.org/cn/0.19.0/_images/math/37e9375fd0210ca33a205eba70c66ba4b41ddc96.png
[O_DN]: http://sklearn.apachecn.org/cn/0.19.0/_images/math/b1b02908acc20145bfec9cde71e0ee5ab4881b69.png
[log_N]: http://sklearn.apachecn.org/cn/0.19.0/_images/math/146255392e86d17d31079c064c2828163cc276f6.png
[d _le D]: /images/20220503/f1386ea8181846deaba702c86738c507.png
[k _ 1]: http://sklearn.apachecn.org/cn/0.19.0/_images/math/06dd4627885a0bebaad0e4d6e0fb5db2e746654a.png
[k _ N_2]: http://sklearn.apachecn.org/cn/0.19.0/_images/math/c13e5702e2e5ad681738f9a435ec8aa018e78d5b.png
[k _ N_2 1]: /images/20220503/e3aaf20dfd904f7896d070877b1c41df.png
[NearestCentroid]: http://sklearn.apachecn.org/cn/0.19.0/modules/generated/sklearn.neighbors.NearestCentroid.html#sklearn.neighbors.NearestCentroid
[sklearn.discriminant_analysis.LinearDiscriminantAnalysis]: http://sklearn.apachecn.org/cn/0.19.0/modules/generated/sklearn.discriminant_analysis.LinearDiscriminantAnalysis.html#sklearn.discriminant_analysis.LinearDiscriminantAnalysis
[sklearn.discriminant_analysis.QuadraticDiscriminantAnalysis]: http://sklearn.apachecn.org/cn/0.19.0/modules/generated/sklearn.discriminant_analysis.QuadraticDiscriminantAnalysis.html#sklearn.discriminant_analysis.QuadraticDiscriminantAnalysis
[nearest_centroid_1]: http://sklearn.apachecn.org/cn/0.19.0/_images/sphx_glr_plot_nearest_centroid_0011.png
[nearest_centroid_2]: /images/20220503/f285e5260bbd4665b6fd4f8d76c1fec4.png
[.._images_sphx_glr_plot_regression_0011.png]: /images/20220503/2efe1d0215b244adb4a20eb156b486e6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjU3NTAyMA_size_16_color_FFFFFF_t_70]: /images/20220503/6686499700e84d7fbb76153758bc9491.png