K近邻法｜KNN

KNN分类基本思路

KNN分类算法特点

• 是一种 lazy-learning 算法，分类器不需要使用训练集进行训练，训练时间复杂度为0；

• KNN 分类的计算复杂度和训练集中的文档数目成正比，如果训练集中文档总数为 n，那么 KNN 的分类时间复杂度为O(n)。

KNN分类算法的三个基本要素

• K 值的选择
K 值的选择会对算法的结果产生重大影响：
• K值较小，学习的近似误差小，但估计误差大，对噪音敏感；k值小意味着模型复杂，容易发生过拟合；
• 如果 K 值较大，优点是可以减少学习的估计误差，但缺点是学习的近似误差增大，这时与输入实例较远的训练实例也会对预测起作用，使预测发生错误；K值大意味着模型简单。
在实际应用中，K 值一般选择一个较小的数值，通常采用交叉验证的方法来选择最优的 K 值。

交叉验证

将原始数据(dataset)进行分组，一部分做为训练集(train set)，另一部分做为验证集(validation set or test set)，首先用训练集对分类器进行训练，再利用验证集来测试训练得到的模型(model)，以此来做为评价分类器的性能指标。

• 距离度量
一般采用 Lp 距离，当p=2时，即为欧氏距离，在度量之前，应该将每个属性的值规范化，这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。

特征缩放

将特征的取值控制在某一范围内，保证每个特征占据的权重一致。常用的是归一化和标准化。

• 分类决策规则
往往是多数表决，即由输入实例的 K 个最临近的训练实例中的多数类决定输入实例的类别。

多数表决等价于经验风险（误分类率）最小化

分类的损失函数：0-1损失

误分类率：

$$\frac{1}{k}\sum_{x_i\in N_k(x)}I(y_i\neq c_j)=1-\frac{1}{k}\sum_{x_i\in N_k(x)}I(y_i=c_j)$$

其中实例$$x\in \mathcal{X}$$，$$N_k(x)$$为最近邻的k个训练实例点的集合，$$c_j$$为该集合区域的类。

要是误分类率最小化，即经验损失最小，就要使$$\sum_{x_i\in N_k(x)}I(y_i=c_j)$$最大，故多数表决等价于经验风险最小化。

KNN分类算法存在的不足

• 当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。由于算法使用多数表决规则，即使该样本不属于大容量类，也被分为了大容量类。该问题可以采用权值的方法（样本距离小的邻居权值大）来改进。

• 该方法的另一个不足之处是计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本。

KNN回归算法

• 通过找出一个样本的k个最近邻居，将这些邻居的属性的平均值赋给该样本，就可以得到该样本的属性。

• 更有用的方法是将不同距离的邻居对该样本产生的影响给予不同的权值，如权值与距离成反比。

KNN的实现-kd树

• 最简单的方法——线性扫描：要计算输入与每一个训练实例的距离，当训练量很大时，计算非常耗时。

• kd树方法：使用特殊的结构存储训练数据，以减少计算距离的次数。kd树是一颗二叉树，表示对k维空间的一个划分。

构造kd树

相当于不断地用垂直于坐标轴的超平面将k维空间切分（通常是选择训练实例点在选定坐标轴上的中位数作为切分点，这样得到的kd树为平衡树）构成一系列的k维超矩形区域。

构造kd树算法流程

输入：k维空间训练数据集$$T=\{x_1,x_2,\ldots,x_N|x_i\in\mathbb{R}^k\}$$

输出：kd二叉树

① 初始：构造根节点（根节点深度为0，对应于包含k个实例点的超矩形区域）

选择$$x^{(1)}$$为坐标轴，以T中所有实例的$$x^{(1)}$$坐标的中位数为切分点，通过该切分点且与$$x^{(1)}$$坐标轴垂直的超平面作为切分超平面，将根节点对应的超矩形区域切分为两个子区域，即由根节点生成深度为1的左、右子节点。

将落在切分面上的实例点保存在根节点。

②重复：构造子节点

对深度为j的节点，选择$$x^{(l)}(l=j\mod k +1)$$为切分的坐标轴，以该结点对应的超矩形区域中的所有实例的$$x^{(l)}$$坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域，即深度为j+1的子节点。

将落在切分面上的实例点保存在深度为j的节点上。

③直到两个子区域没有实例点时停止。

用kd树搜索最近邻

用kd树搜索最近邻算法流程

输入：kd树，目标点x

输出：x的最近邻

① 从根节点出发，递归地向下访问kd树，在kd树中找到包含x的叶节点：若x当前维的坐标小于切分点的坐标，则移动到左子树，否则移动到右子树，直到子节点为叶节点。

②以此叶节点为“当前最近点”。

③递归地向上回退，在每个节点进行以下操作：

ⓐ如果该节点保存的实例点比“当前最近点”距离目标点更近，则以该实例点为“当前最近点”；

ⓑ检查该子节点其父节点的另一个子节点区域中是否有更近的点。如果有，移动到另一个子节点，接着递归地进行最近邻搜索；如果没有，向上回退。

④当回退到根节点时，算法停止，输出“当前最近点”。

利用kd树可以省去大部分数据点的搜素，从而减少搜索的计算量。

最近邻算法（kNN）详解 - 飞桨AI Studio星河社区

不啰嗦！快速读懂kNN原理及其代码实现！ - 飞桨AI Studio星河社区

https://aistudio.baidu.com/projectdetail/1200366?ad-from=1514