3. k近邻学习

作者: 楼桑村小秀才 | 来源:发表于2018-08-31 14:04 被阅读0次

简介

给定测试样本,基于某种距离度量找出训练集中与其最
靠近的k个训练样本,然后基于这k个" 邻居"的信息来进行预测.也可基于距离远近进行加权平均/投票, 距离越近的样本权重越大.
分类: 投票法, 选择k个样本中出现最多的类别标记作为预测结果, 可以取多类.
回归: 平均法, 将这k个样本标记值的平均值作为预测结果

懒惰学习: k近邻学习没有显式的训练过程, 此类学习技术在训练阶段仅仅是把样本保存起来, 训练时间开销为0, 待收到测试样本再进行处理.

k近邻法三要素: 距离的度量, k值的选择, 分类决策规则

定义

1.png

距离度量
Minkowski(闵可夫斯基)距离
设特征空间X是n维实数向量空间 $R^n, x_i,x_j\in X, x_i=(x_i^1,x_i^2,...,x_i^n), x_j=(x_j^1,x_j^2,...x_j^n)$
则 $x_i,x_j$ 的 $L_p$ (即闵可夫斯基)距离为:
$L_p(x_i,y_j)=(\sum_{l=1}^n|x_i^l-x_j^l|^p)^\frac{1}{p},\qquad (p\geq 1)$
当p=1时, 称为曼哈顿距离: $L_1(x_i, x_j)=\sum_{l=1}^n|x_i^l-x_j^l|$ , 差的绝对值之和
当p=2时, 称为欧式距离: $L_2(x_i, x_j)=(\sum_{l=1}^n|x_i^l-x_j^l|^2)^\frac{1}{2}$ , 差的绝对值平方和再开方, (均方误差)
当p= $\infty$ 时, 称为切比雪夫距离: $L_\infty(x_i, x_j)=max_l(x_i^l-x_j^l)$ , 各个坐标距离的最大值

2.png

k值选择

较小的k值: 用较小的邻域中的训练数据进行预测, 学习的近似误差减小, 只有与输入实例相近的(相似的)训练实例才会对预测结果起作用. 但学习的估计误差会增大, 预测结果会对邻近的实例点(如噪声)非常敏感. 过小的k值意味着整体模型变得复杂, 容易发生过拟合
较大的k值: 用较大的邻域中的训练数据进行预测, 学习的近似误差增大, 但估计误差会减小. 与输入实例较远的(不相似的)训练实例也会对预测结果起作用.
应用中k值一般取一个比较小的值, 通常采用交叉验证法来选取最优的k值

分类决策

多数表决: 由输入实例的k个近邻的训练实例中的多数类决定输入实例的类
对于给定的实例 $x\in 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)$
$\text{其中: } I(expr) = \begin{cases} 1 & expr == true \\ 0 & expr == false \end{cases}$
所以 $\sum_{x_i\in N_k(x)}I(y_i = c_j)$ 代表集合 $N_k(x)$ 中 $y_i==c_j$ 的元素的数量
$\sum_{x_i\in N_k(x)}I(y_i \neq c_j)$ 代表集合 $N_k(x)$ 中 $y_i\neq c_j$ 的元素的数量
要试误分类率最小, 即使 $\sum_{x_i\in N_k(x)}I(y_i = c_j)$ 最大. (多数表决)