K-nearest Neighbor

概述

K-近邻算法(k-NN)是一个可以用来分类算法（也可以用来回归，本文不讨论）。基本思路是给定一个标记好的数据集，在数据集的特征空间选取一个距离度量标准，对于需要分类的数据点在该数据集中选取距离最近的k个数据实例，然后利用某种分类决策规则(如多数表决)得到实例点的类别。可以看到k-NN没有明显的学习过程(没有可学习的模型参数，k为超参)。对k-NN算法影响较大的元素有三个：k值，距离度量标准，分类决策规则。在实践中当数据集超大时一般用k-d树存储数据集来减少检索时间。

算法

根据给定的距离度量标准，在数据集T中找到与x最近的k个点，记这k个点组成的集合为 $N_k(x)$

在 $N_k{x}$ 中根据分类决策规则决定x的类别

模型理解

在某距离度量标准下，数据集中的每个点在特征空间中将数据集进行了划分：对每个训练实例点 $x_i$ ,距离该点比其他点更近的所有点组成了一个区域（叫做单元，cell），因此整个特征空间被训练数据点进行了划分。在每个cell内，k-NN将 $y_i$ 作为所有点的标签。对于需要分类的点，总能在特征空间将该点放置在某个cell内（有可能在多个cell交界上）。

距离度量

特征空间中两个实例点的距离反映了两个实例点的相似程度。距离度量标准有很多种，比如

实数向量空间距离

$L_p$ 距离，又称明式距离，明可夫斯基距离(Minkowski distance)，定义在n维实数向量空间中

$L_p(x_i, x_j)=\left (\sum_{l=1}^n |x_i^{(l)} - x_j^{(l)}|^p \right )^{\frac{1}{p}}$

p=1时称为曼哈顿距离(Manhattan distance)，形象地也叫做城市街道距离

$L_{1}(x_i, x_j)=\sum_{l=1}^n |x_i^{(l)} - x_j^{(l)}|$

p=2时称为欧氏距离(Euclidean distance)

$L_{2}(x_i, x_j)=\sqrt{\sum_{l=1}^n |x_i^{(l)} - x_j^{(l)}|}$

$p=\infty$ 时称为切比雪夫距离(Chebyshev distance)或 $L_{\infty}$ 度量，为各个坐标距离的最大值

$L_{\infty}(x_i, x_j)=\max_{l} |x_i^{(l)} - x_j^{(l)}|$

字符串距离

李距离(Lee distance):李距离评价两个长度为n，q进制( $q \geq 2$ )字符串之间的距离

$Lee(x, y)=\sum_{i=1}^n min\{|x_i-y_i|, q-|x_i-y_i|\}$

当q=2或q=3时，李距离等价于汉明距离。

假设q=6，字符串3340和2543之间的李距离是1+2+0+3=6

汉明距离(Hamming distance):两个等长字符串对应位置不同字符的个数。对于固定的长度n,汉明距离是该长度字符向量空间上的距离度量。

字符串a12dg和a13og的汉明距离是2

二进制字符串的汉明距离也等于n维超正方体两个顶点之间的曼哈顿距离，其中n是两个字串的长度。

简单匹配系数(simple matching coefficient, SMC)

编辑距离(edit distance):编辑距离有几种不同的定义，差异在可以对字符串进行的处理。

在莱文斯坦距离中，可以删除、加入、取代字符串中的任何一个字元，也是较常用的编辑距离定义，常常提到编辑距离时，指的就是莱文斯坦距离。

Damerau-Levenshtein 距离是一种莱文斯坦距离的变种，但允许以单一操作交换相邻的两个字符（称为字符转置），如 AB→BA 的距离是 1（交换）而非 2（先删除再插入、或者两次替换）。

LCS（最长公共子序列）距离只允许删除、加入字元。

Jaro 距离只允许字符转置。

汉明距离只允许取代字元。

一般使用动态规划算法来计算编辑距离。

雅卡尔指数(Jaccard index)

k值的选择

k值过小时，只有离预测实例较近的训练实例会起作用，近似误差较小。但是预测结果会对近邻的实例点非常敏感，估计误差较大，如果近邻点恰好是噪声，预测就会出错。k值越小，表示整体模型越复杂，容易发生过拟合。

k值过大时，表示用较大邻域的实例进行预测，估计误差较小。但是离预测实例较远的点(不相似)也会对预测起作用，近似误差变大使预测错误。k值越大，表示模型越简单，欠拟合。

实践中通常用交叉验证法选择最优的k值

分类决策规则

一般使用多数表决分类规则

kd树

kd树是一种对k维空间中的数据进行存储以便于快速搜索的数据结构。kd树是一个二叉树，表示对k维空间中的一个划分，其每个节点对应于k维空间划分中的一个超矩形区域。这里的k表示维度，不是k-NN的k。

构造kd树

构造kd树相当于不断用垂直于坐标轴的超平面将k维空间切分。具体步骤为：

将所有实例所在的超矩形区域作为根节点，选择 $x^{(1)}$ 为坐标轴，取所有实例在 $x^{(1)}$ 上的中位数作为切分点，通过垂直 $x^{(1)}$ 过切分点的超平面划分超矩形区域。根节点生成深度为1的左右节点：维度 $x^{(1)}$ 小于切分点区域的实例点划分到根节点的左子树，大于切分点区域的实例划分到右子树,等于切分点的的实例点划分到根节点

重复：对深度为j的节点，选择 $x^{(l)}$ 作为坐标轴， $l=(j\ mod\ k) + 1$ ,以该节点对应区域的实例点上 $x^{(l)}$ 的中位数为切分点，过该切分点且垂直于该坐标轴的超平面将该节点所在区域划分。该节点生成深度为j+1的左右节点：维度 $x^{(l)}$ 小于切分点区域的实例点划分到该节点的左子树，大于切分点区域的实例划分到右子树,等于切分点的的实例点划分到该节点

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

搜索kd树