k 近邻法

k近邻算法

k近邻算法：对于新的输入实例，在训练数据集中寻找最接近的k个实例，这k个实例的多数属于某个类，则将输入实例分到某个类中。

k近邻法没有显式的学习过程

k近邻模型

k近邻法中，当训练集，距离度量，k值以及分类决策规则确定后，对于每个新的输入实例，其所属实例唯一确定

距离度量

我们可以选用Lp距离，其定义如下：
$L_P(x_i,x_j)=(\Sigma_{l=1}^n|x_i^{(l)}-x_j^{(l)}|^p)^{\frac{1}p}$LP​(xi​,xj​)=(Σl=1n​∣xi(l)​−xj(l)​∣p)p1​
p=1，为曼哈顿距离；p=2，为欧氏距离；p=∞，为各个坐标距离的最大值。

k值的选择

k值的选择对k近邻法的结果会产生很大影响，k值较小会使模型变得复杂，容易过拟合；较大会使模型变得简单，容易欠拟合；我们一般选择较小的k值，使用交叉验证的方法来选取最优的k值

分类决策规则

分类决策规则：多数表决规则

对于给定的实例x，其最近邻的k个训练实例点构成集合N_k(x)。如果涵盖N_k(x)的区域类别是c_j，那么误分类率是
$\frac{1}{k}\Sigma_{x_i\in N_k(x)}I(y_i\ne c_j) = 1-\frac{1}k \Sigma_{x_i\in N_k(x)}I(y_i= c_j)$k1​Σxi​∈Nk​(x)​I(yi​​=cj​)=1−k1​Σxi​∈Nk​(x)​I(yi​=cj​)
要使误分类率最小即经验风险最小，只需使
$\Sigma_{x_i\in N_k(x)}I(y_i= c_j)$Σxi​∈Nk​(x)​I(yi​=cj​)
最大，因此多数表决规则等价于经验风险最小化

k近邻算法的实现：kd树

k近邻法最简单的实现方法使线性扫描，但这样时间复杂度为线性，使用树结构可以将时间复杂度降低至O(log n)

kd树的构造

构造kd树的算法：

kd树的搜索