Skip to content

Files

Latest commit

359e4c3 · Oct 11, 2021

History

History

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Oct 11, 2021

README.md

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树

参考链接