数据挖掘与机器学习DMML（part 8）K近邻（KNN）

 K Nearest Neighbours

KNN Definition

KNN 是一种简单的算法，它存储所有可用案例，并根据相似度量对新案例进行分类。

KNN 不同名称：

K-Nearest Neighbors • Memory-Based Reasoning基于记忆的推理 • Example-Based Reasoning基于实例的推理 • Instance-Based Learning基于实例的学习 • Case-Based Reasoning基于案例的推理 • Lazy Learning懒惰学习

KNN 简史

knn早在 20 世纪 70 年代初就已用于统计估计和模式识别（非参数技术）
动态记忆：  计算机和人的记忆与学习理论》（Schank，1982 年）
人们通过记忆进行推理，通过实践进行学习。 思维就是提醒、类比

KNN主要步骤：

1. 选择参数K：K是一个正整数，表示在进行决策时将考虑的最近邻居的数量。

2. 距离度量：选择一个距离度量方法来计算未知样本与已知样本之间的距离，常见的距离度量包括欧氏距离、曼哈顿距离等。

3. 寻找最近邻：对于一个新的未知样本，计算它与训练集中每个样本的距离，并找出距离最近的K个样本。

4. 投票决策：根据这K个最近邻样本的类别，通过多数投票的方式来预测新样本的类别。

5. 分类决策：将获得最高票数的类别指定为新样本的类别。

特点：

• 懒惰学习：KNN是一种懒惰学习算法，它在训练阶段不需要构建模型，所有的计算都推迟到分类阶段进行。

• 对数据敏感：KNN对数据的分布非常敏感，特别是当数据集的规模和特征空间的维度变化时。

• 特征缩放：由于KNN是基于距离的算法，特征的缩放会直接影响距离的计算，因此在应用KNN之前通常需要对特征进行标准化或归一化。

• 局部结构：KNN可以捕捉到数据的局部结构，这使得它在某些情况下比全局模型（如线性模型）更灵活。

• 参数选择：K的选择对KNN的性能有很大影响。K太小容易受到噪声的影响，K太大则可能包含太多不相关的邻居，影响分类精度

KNN 邻居数

如果 K=1，选择最近的邻居

如果 K>1，对于分类，选择最频繁的邻居；对于回归，计算 K 个邻居的平均值。

距离加权近邻算法

根据邻居与查询点的 "距离 "分配权重

权重 "可能 "是距离的倒平方

所有训练点都可能影响特定实例：谢泼德方法

距离 ：分类变量

基于实例的推理
IB1 基于标准 KNN
IB2 是增量 KNN 学习器，只将错误分类的实例纳入分类器。
IB3通过保留成功记录来剔除表现不佳的实例。 

 基于案例的推理

 

总结

KNN 概念简单，却能解决复杂问题

能在信息相对较少的情况下工作

学习简单（根本无需学习！）

内存和 CPU 成本-特征选择问题

对表示敏感

受维度诅咒的困扰