最邻近规则分类KNN（K-Nearest Neighbor）

如果一个样本在特征空间中的K个最相似（即特征空间中最邻近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。

• 分类算法
• lazy learning

准备知识

距离计算方式

欧几里得距离（Euclidean Distance）

$$E(x,y)=\sqrt{\sum_{i=0}^n(x_i-y_i)^2}$$

余弦值（cos）

相关度（correlation）

曼哈顿距离（Manhattan Distance）

算法流程

总体来说，KNN分类算法包括以下4个步骤：

1. 准备数据，对数据进行预处理 。

2. 计算测试样本点（也就是待分类点）到其他每个样本点的距离 。

3. 对每个距离进行排序，然后选择出距离最小的K个点 。

4. 对K个点所属的类别进行比较，根据少数服从多数的原则，将测试样本点归入在K个点中占比最高的那一类 。

关键问题

K的取值

KNN的优势

• 简单易于理解
• lazy learning，无需参数估计，无需训练

KNN的劣势

• 需要大量的空间存储所有已知实例；
• 算法复杂度高，需要在内存中计算并比较所有的距离；
• 当样本分布不平衡式，某一类样本数量占主导时，容易被误归类；

改进算法

目前对KNN算法改进的方向主要可以分为4类：

1. 是寻求更接近于实际的距离函数以取代标准的欧氏距离，典型的工作包括 WAKNN、VDM ；

2. 是搜索更加合理的K值以取代指定大小的K值典型的工作包括SNNB、 DKNAW ；

3. 是运用更加精确的概率估测方法去取代简单的投票机制，典型的工作包括 KNNDW、LWNB、 ICLNB ；

4. 是建立高效的索引，以提高KNN算法的运行效率，代表性的研究工作包括 KDTree、 NBTree。还有部分研究工作综合了以上的多种改进方法 。

Sklearn应用