统计学习方法笔记之k近邻算法（附代码实现）

2019-07-28 本文已影响0人 Aengus_Sun

更多文章可以访问我的博客Aengus | Blog

k近邻法即kNN算法，是假设给定一个训练集，对于每个训练样本的分类已经确认，当对测试样本分类时，根据其k个最近邻的训练样本的类别，通过多数表决的方式进行预测。kNN算法没有显式的学习过程。

kNN算法

假设给定的训练集为 $\{(x_1, y_1), (x_2, y_2), \cdots,(x_N, y_N) \}$ ，其中 $x_i \in R^N$ ， $y_i \in \{c_1, c_2, \cdots, c_K\}$ ，步骤为：

（1）根据给定的距离度量（即距离计算方法），在训练集中找出与测试样本 $x$ 的前 $k$ 个最近邻的点，涵盖这 $k$ 个点的 $x$ 的邻域记作 $N_k(x)$ ；

（2）在 $N_k(x)$ 中根据分类决策规则（如多数表决）决定 $x$ 的类别 $y$ ：
$y = \arg \max_{c_j}\sum_{x_i \in N_k(x)} I(y_i=c_j),i=1,2,\cdots,N;j=1,2,\cdots,K$
其中 $I$ 代表指示函数， $y_i=c_j$ 时 $I=1$ ，否则为0；

当 $k=1$ 的时候称为最近邻算法。

距离度量

特征空间中两个点的距离是两个训练样本相似程度的反映。kNN算法使用的距离一般是欧式距离，但也可以是更一般的 $L_p$ 距离或者Minkowski距离。

设待测距离的两个点 $x_i,x_j \in R^N$ ，且 $x_i=(x_i^{(1)}, x_i^{(2)}, \cdots,x_i^{(N)})^T,x_j=(x_j^{(1)}, x_j^{(2)}, \cdots,x_j^{(N)})^T$ ，那么 $L_p$ 距离定义为：
$L_p(x_i, x_j) = (\sum^N_{k=1}|x_i^{(k)}-x_j^{(k)}|^{p})^{\frac{1}{p}},p \geq 1$
当 $p=2$ 时，称为欧式距离； $p=1$ 时，称为曼哈顿距离；当 $p= \infty$ 时，它是各个坐标的最大值：
$L_{\infty}(x_i, x_j) = \max_{k}|x^{(k)}_i - x^{(k)}_j|$

k值的选择

如果k值选择的比较小，如果最近邻的点恰好是噪点，那么预测就会出错，也就是说，k值的减小会导致模型变复杂，容易发生过拟合；

如果k值选择的比较大，那么模型就比较简单。如果令 $k=N$ ，那么如果输入什么点，预测的分类都会变成训练样本最多的类别，模型丧失了可用性。

分类策略

$k$ 近邻算法常用的决策规则往往是多数表决。

对于给定的测试样本 $x$ ，其最近邻的 $k$ 个训练样本组成的集合为 $N_k(x)$ 。如果涵盖 $N_k(x)$ 的区域类别是 $c_j$ ，那么误分类率是
$\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)$
要使误分类率最小即经验风险最小，就要使 $\sum_{x_i \in N_k(x)}I(y_i= c_j)$ 最大，所以多数表决策略等价于经验风险最小化。

求解实现

kNN算法实现最简单的方法就是“线性扫描”，即计算每个训练点到测试样本的距离，当训练集很大且维度比较高的时候计算量很大。

还有一种方法叫作kd树，利用特殊的数据结构存储训练数据，以减小计算距离的次数。

kd树

kd树是一种对k维空间中的训练样本进行存储以便对其进行快速检索的树形数据结构。kd树是二叉树，表示对k维空间的一个划分。构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分，构造一系列的k维超矩形区域。kd树的每一个结点对应一个k维超矩形结构。

构造算法

假设给定的训练集为 $\{(x_1, y_1), (x_2, y_2), \cdots,(x_N, y_N) \}$ ，其中 $x_i = (x_i^{(1)},x_i^{(2)}, \cdots, x_i^{(k)})^T$ ， $i=1, 2, \cdots,N$ ，则按照以下步骤进行构造：

（1）构造根结点，根结点对应包含训练样本的 $k$ 维空间的超矩形区域。选择以 $x^{(1)}$ 为坐标轴，以所有训练样本的 $x^{(1)}$ 坐标的中位数为切分点，将根结点对应的超矩形区域切分为两个不同区域，切分由通过切分点且与坐标轴 $x^{(1)}$ 垂直的超平面实现；由此得到深度为1的左右子树，左子树是 $x^{(1)}$ 坐标小于根结点 $x^{(1)}$ 坐标的所有训练样本；右子树是 $x^{(1)}$ 坐标大于根结点 $x^{(1)}$ 坐标的所有训练样本；

（2）对于所有深度为 $j$ 的结点，选择 $x^{(l)}$ 为切分的坐标轴， $l=j(\mod{k})+1$ ,然后重复类似上述构造根结点的步骤进行构造；将落在切分超平面上的实例点保存在该结点；

（3）直到两个子区域没有实例存在时停止，从而形成kd树的划分。

如果中位数上没有样本点，可以选择相邻的点作为切分点。

搜索算法

输入为kd树以及测试样本 $x$ ，按照以下步骤进行搜索：

（1）从根结点出发，递归的往下访问，如果测试样本 $x$ 的当前维度的坐标小于切分点坐标，则往左找，否则往右找。直到子结点为叶结点位置。这样就找到了包含测试样本 $x$ 的叶结点；

（2）以此叶结点作为“当前最近点”；

（3）递归的往上回退，再每个结点进行以下操作：

（a）如果该结点包含的训练样本比当前最近点距离测试样本更近，则以该样本作为“当前最近点”；

（b）检查另一子结点对应的区域是否存在与以测试样本为球心、以测试样本与“当前最近点”间距离为半径的超球体相交，如果存在，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点，进行此搜索算法；否则，往上回退；

（4）当回退到根结点时，搜索结束，最后的“当前最近点”即为 $x$ 的最近邻点；

如果训练点是随机分布的，那么kd树的平均复杂度为 $O(\log N)$ ， $N$ 为训练样本的数量。kd树更适用于训练样本树远远大于空间维数时的 $k$ 近邻搜索，当两者相近时，它的效率会大大下降，几乎接近线性扫描。

Python实现

下面是利用“线性扫描”的方法实现kNN算法：

import numpy as np


def knn(x_data, y_label, k, x):
    """
    kNN算法
    :param x_data: 训练集，形如[[1, 2, 3], [2, 3, 4]]
    :param y_label: 标签
    :param k: k值
    :param x: 测试集
    :return: 分类结果
    """
    m, n = x_data.shape
    # dist = [[距离1， 分类1], [距离2， 分类2], [距离3， 分类3], ...]
    dist = np.zeros((m, 2))
    # 计算每个点到测试点的距离
    for i in range(m):
        dist[i, 0] = sum(pow(x_data[i, j]-x[j], 2) for j in range(n))
        dist[i, 1] = y_label[i]
    sorted_dist = sorted(dist, key=lambda first: first[0], reverse=False)
    vote = {}
    for i in range(m):
        vote[y_label[i]] = 0
    for i in range(k):
        vote[sorted_dist[i][1]] += 1
    sorted_vote = sorted(vote, reverse=True)
    return sorted_vote[0]

参考

李航《统计学习方法（第二版）》第三章