k-nearest neighbor, k-NN
k近邻法:假设给定一个训练数据集,其中的实例类别已定,分类时,对新的实例,根据其k个最近邻的训练实例的类别,通过多数表决等方式进行预测。
模型三要素: 距离度量、k值的选择、分类决策规则决定
特征空间中两个实例点的距离是两个实例点相似程度的反映。
设特征空间$\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
$$
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)$最大,所以多数表决规则等价于经验风险最小化。