《统计学习方法》之k近邻法

相似度查询有两种方法:
1. 范围查询,给定阈值。
2. k近邻查询,给定查询点和k。
k近邻法是一种基本分类与回归的方法。其基本思想是:一个样本的k个最相近的样本大多属于某一个类,则该样本也属于这个类。因此,k近邻算法不具有显式的学习过程。k值的选择、距离度量和分类决策规则是k近邻方法的三个基本要素。

k近邻算法

k近邻算法流程
输入:训练数据集$T={(x_1,y_1),(x_2,y_2),…,(x_N,y_N)}$,其中,$x \in X \subseteq R^n$为实例的特征向量,$y_i\in Y={c_1,c_2,…,c_K}$为实例的类别,$i=1,2,…,N$,实例特征向量$x$。
输出:实例$x$所属的类$y$。
(1) 根据给定的距离度量,在训练集$T$中找出与$x$最近的$k$个点,涵盖这$k$个点的$x$邻域记作$N_k(x)$。
(2) 在$N_k(x)$中根据分类决策规则,决定$x$的类别$y$:
$y=\arg \max \limits_{c_j}{\sum \limits_{x_i\in N_k(x)}I(y_i=c_j)}, i=1,2,…,N; j=1,2,…,K $
其中$I$为指示函数,即当$y_i=c_j$时,$I$为1,否则为0。

k近邻的特殊情况是当$k=1$时,此算法被称为最近邻算法。

k近邻模型

模型

特征空间中,对于每个训练实例点$x_i$,距离该点比其他店更近的所有点组成的一个区域,叫做单元。k近邻算法就是利用训练数据集对特征向量空间进行划分。

距离度量

距离度量公式定义为:
$$L_p(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_i^{(l)}|^p)^\frac{1}{p}$$
其中$p\geq 1$
当$p=1$时,可以得到曼哈顿距离:$L_1(x_i,x_j)=\sum_{l=1}^{n}|x_i^{(l)}-x_i^{(l)}|$
当$p=2$时,可以得到欧式距离:$L_2(x_i,x_j)=(\sum_{l=1}^{n}|x_i^{(l)}-x_i^{(l)}|^2)^\frac{1}{2}$

k值的选择

k值的选择对算法有很大的影响。k值的减小意味着整体模型变得复杂,容易发生过拟合。如果选择较大的k值,可以减少学习的估计误差,但是学习的近似误差会增加。在应用中,k值一般取一个比较小的值。通常采用交叉验证法来选取最合适的k值。

分类决策规则

k近邻法中的分类决策规则往往是多数表决,即由输入实例的k个近邻的训练实例中的多数类决定输入实例的类。这种决策规则等价于经验风险最小化。

k近邻法的实现:kd树

我们在进行特征匹配是,通常采用两种方法:线性扫描和构建数据索引,而使用构建数据索引时,在无重叠时可采用kd树,重叠时可采用R树。
kd树的全称是k-dimension tree,可以用于k近邻的寻找。

构造kd树

kd树是一棵二叉树,也是一颗空间划分树(空间划分树:将整个空间划分为几个特定的部分,然后再特定的部分进行搜索)。

构造平衡kd树流程
输入:$k$维空间数据集$T={x_1,x_2,…,x_N}$,其中$x_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(k)})^T,i=1,2,…,N$
输出:kd树
算法流程:
(1) 开始:构造根结点,根结点对应于包含$T$的$k$维空间的超矩形区域。
选择$x^{(1)}$为坐标轴,将$T$中所有实例的$x^{(1)}$的中位数(奇数个:取中间,偶数个:中间偏大)为切分点,将根结点对应的超矩形区域切分成两个子区域。左子结点对应于小于切分点的子区域,有子结点对应于大于切分点的子区域。落在切分超平面上的实例点保存在根节点。
(2) 重复:对深度为$j$的切分点,选择$x^{(l)}$为切分的坐标轴,其中$l=j(modk)+1$(从1到$k$循环取),重复以上操作。
(3) 直到两个子区域没有实例点存在时停止。从而形成kd树的区域划分。