数据挖掘笔记技术篇- Chapter5 分类算法 KNN-一一网

根据相对距离测量构建分类器

其中，最具代表性的就是KNN算法

参考：《统计学习原理李航》

1.KNN算法简介

数据集:
$T={[(x_1,y_1),(x_2,y_2),…,(x_n,y_n)]}$

其中
$x_i \in \mathcal{X} \in \mathbb{R}^n$
为实例的特征向量，
$y_i \in \mathcal{Y}=[c_1,c_2,…,c_N]$ 为实例的类别， $i=1,2,…,N$

输出: 实例 $x$ 所属的类 $y$ .

根据给定的距离矢量，在训练集 $T$ 中找到与 $x$ 最邻近的k个点，涵盖这 $k$ 个点的 $x$ 的邻域记做 $N_k(x)$ ；
在 $N_k(x)$ 中根据分类决策规则决定 $x$ 的类别 $y$ ;

模型

在k近邻法中，当训练集、距离度量(如欧氏距离〉、k值及分类决策规则(如多数表决〕确定后，对于任何一个新的输入实例，它所属的类唯一地确定。这相当于根据上述要素将特征空间划分为一些子空间，确定于空间里的每个点所属的类，这一事实从最近邻算法中可以看得很清楚。

特征空间中，对每个训练实例点 $x$ ，距离该点比其他点更近的所有点组成一个区域，叫作单元(ce11)。每个训练实例点拥有一个单元，所有训练实例点的单元构成对特征空间的个划分。最近邻法将实例 $x_i$ 的类 $y$ ，作为其单元中所有点
的类标记(class label)。这样，每个单元的实例点的类别是确定的。

距离度量

对于一个特征空间，两个实例点的距离是两个实例点相似程度的反映。

一般使用的是欧式距离，当然也有 $L_p$ 距离及Minkowski距离。

k值的选择

k值的选择会对k近邻法的结果产生重大影响。

如果选择较小的k值，就相当于用较小的邻域中的训练实例进行预测，”学习”的近似误差会减小，只有与输入实例较近的(相似的)训练实例才会对预测结果起作用。但缺点是”学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感，如果邻近的实例点恰巧是噪声，预测就会出错。换句话说，k值的减小就意味着整体模型变得复杂，容易发生过拟合.