k近邻法

k-nearest neighbor, k-NN

k近邻法：假设给定一个训练数据集，其中的实例类别已定，分类时，对新的实例，根据其k个最近邻的训练实例的类别，通过多数表决等方式进行预测。

模型三要素：距离度量、k值的选择、分类决策规则决定

距离度量

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

$L_p$距离：

设特征空间$\chi$是n维实数向量空间$R^n$，$x_i,x_j \in \chi$，$x_i = (x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^\top$,$x_j = (x_j^{(1)},x_j^{(2)},...,x_j^{(n)})^\top$,$x_i,x_j$的$L_p$距离定义为： $$ L_p{(x_i,x_j)} = (\sum_{l=1}^n {|x_i^{(l)}-x_j^{(l)}|^p})^{\frac{1}{p}} , p \ge 1 $$ $p=2$时，称为欧氏距离(Euclidean distance)，即 $$ L_2{(x_i,x_j)} = (\sum_{l=1}^n {|x_i^{(l)}-x_j^{(l)}|^2})^{\frac{1}{2}} $$ $p=1$时，称为曼哈顿距离(Manhattan distance)，即 $$ L_1{(x_i,x_j)} = \sum_{l=1}^n {|x_i^{(l)}-x_j^{(l)}|} $$ $p=\infin$ 时，是各个坐标距离的最大值，即 $$ L_{\infin}(x_i,x_j) = \max_l |x_i^{(l)} - x_j^{(l)}| $$

k值选择

k值的减小意味着整体模型变得复杂，容易发生过拟合

实际应用中：k值取一个比较小的树枝，然后采用交叉验证法来选取最优的k值

分类决策规则

多数表决，即由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。

分类函数： $$ f:R^n \to {c_1,c_2,...,c_K} $$ 误分类概率： $$ P(Y \ne f(X)) = 1-P(Y=f(X)) $$ 对给定的实例$x \in \chi$，其最近邻的k个训练实例点构成集合$N_k(x)$。如果涵盖$N_k(x)$的区域的类别是$c_j$，那么误分类率是： $$ \frac{1}{k} \sum_{x_i \in N_k(x)} I(y_i \ne 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)$最大，所以多数表决规则等价于经验风险最小化。

kd树

参考链接