机器学习--k近邻法理论知识（一）
机器学习 | k近邻法理论知识（一）
各位读者大家好，这周我们将要一起开始k近邻法的学习。这篇文章中我们主要说明k近邻法的模型、算法以及基本要素。下周的文章中我们将说明k近邻法的实现方式-kd树。
k近邻法（k-nearest neighbor，k-NN）是一种基本分类与回归方法。这里我们将要学习分类问题中的k近邻法。k近邻法概述一下就是：给定一个训练集后，对于新的实例，只需要根据其k个最近邻的训练实例的类别，通过多数表决等方式进行分类预测即可。k近邻法不具有显式的学习过程，它利用训练集对特征向量空间进行划分，并将其作为分类模型。k近邻法的三个基本要素是k值的选择、距离度量及分类决策规则。
k近邻算法
输入：训练数据集 \[ T = \lbrace(x_1, y_1),(x_2,y_2), ...,(x_N,y_N)\rbrace \] 其中，xi为实例的特征向量，yi ∈ Y = {\(c_1,c_2,...,c_K\)}为实例的类别，i = 1, 2, ... , N；待预测的实例特征向量x。
输出：实例x所属的类别y。
步骤：
根据给定的距离度量方法（欧氏距离，马氏距离等等），在训练集T中找出与x最邻近的k个点，涵盖这k个点的x的邻域记作\(N_k(x)\)；
在\(N_k(x)\)中根据分类决策规则（如多数表决）决定x的类别y：遍历\(N_k(x)\)中的数据点，将他们的类别分别累加，找出点数最多的类别，则输入的实例x的类别y即为次类别。
k近邻法的特殊情况是k=1的情形，成为最近邻算法，对于输入的实例x，它的类别y即为离它最近的训练集点的类别。
K近邻模型
在这一部分我们将说明k近邻模型和它的三个基本要素如何确定。
模型
当k近邻法的三个基本要素确定之后，对于任何一个新输入的实例点，它的类别是唯一确定的。这相当于根据三要素去划分特征空间，确定子空间里的每个点所属分类。
以最近邻算法为例：对于每个训练集中的点，距离该点比其他点更近的所有点组成一个区域，叫做单元（cell）。这样，对于最近邻算法来说，每个单元中的实例点的类别都是唯一确定的，即为这个单元中的训练集实例点的类别。
三要素
距离度量
我们要选取最近邻，则首要关注的就是计算距离的方式。为了后续表达，我们首先定义两个点\(x_i,x_j\)，\(x_i=(x^{(1)},x^{(2)},...,x^{(n)},)^T\)，\(x_j=(x^{(1)},x^{(2)},...,x^{(n)},)^T\)。
最直观的方法就是计算我们最常使用的欧式距离，也就是： \[ L = (\sum_{l = 1}^n|x_i^{(l)}-x_j^{(l)}|^2)^{\frac{1}{2} } \] 我们也可以用更加一般的明式距离（明考夫斯基Minkowski距离），即为： \[ L_p = (\sum_{l = 1}^n|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}{p} } \] 其中的p是可变的，当p为2的时候即为欧氏距离，当p为1时，即为曼哈顿距离： \[ L_1 = \sum_{l = 1}^n|x_i^{(l)}-x_j^{(l)}| \] 当p = ∞时，即为切比雪夫距离： \[ L_∞ = max_l|x_i^{(l)}-x_j^{(l)}| \] 根据不同的距离度量得到的k近邻点也不同，要根据不同维度之间的关系选取适当的距离度量。
k值选择
k值选择对于结果至关重要。
选择较小的k时，相当于用较小邻域中的训练实例进行预测。优点是“学习”的近似误差会减少，但是缺点是“学习”的估计误差会增大，预测结果会对近邻的实例点非常敏感，如果恰巧近邻的实力点是噪点则预测便会出错。总结来说就是k的减小会让整体模型变复杂，容易发生过拟合。
选择较大的k值时，相当于相用较大邻域中的训练实例进行预测。优点是可以减少估计误差，缺点是近似误差会增大。与输入实例不相似的训练实例也会对其结果产生影响，这是不合理的。k值得增大意味着模型变得简单。
在应用中，k一般取一个比较小的数值。通常采用交叉验证法来选取最优的k值。
分类决策规则
k近邻法的决策规则一般都是多数表决规则。
多数表决规则（majority voting rule）解释如下：若分类的损失函数为0-1损失函数，分类函数为： \[ f:R^n\rightarrow \lbrace c_1,c_2,...,c_K \rbrace \] 误分类的概率即为： \[ P(Y\neq f(X)) = 1- P(Y = f(X)) \] 对给定的实例\(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) \] 要是误分类率最小即经验风险最小，就要使\(\sum_{x_i\in N_k(x)}I(y_i = c_j)\)最大，所以多数表决规则等价于经验风险最小化。
今天的内容就到此结束啦，谢谢大家的观看！