K近邻法（k

K近邻法（k

introduction

给定训练数据集，对于新输入的实例，在训练数据集中寻找与该实例最近邻的k个实例，采用投票法分类
没有显式学习过程

k近邻算法

输入： T = ( x 1 , y 1 ) , ⋯ , ( x n , y n ) T= {(x_1,y_1),cdots,(x_n,y_n)} T=(x1​,y1​),⋯,(xn​,yn​)
x ∈ R n xin R^n x∈Rn特征向量
y ∈ C K yin C_K y∈CK​分类
输出：x属于的类别
(1)根据给定的距离度量，在训练集 T T T中，找到和 x x x临近的 k k k个点，涵盖这k个点的x的邻域为 N k ( x ) N_k(x) Nk​(x)
(2)根据分类决策规则，确定x的类别
y = a r g m a x c j ∑ x i ∈ N k ( x ) I （ y i = c j ） y=argmax_{c_j} sum_{x_i in N_k(x)}I（y_i=c_j） y=argmaxcj​​∑xi​∈Nk​(x)​I（yi​=cj​）

k近邻模型

构成要素：k，距离度量，分类决策规则

模型

将特征空间划分为一定子空间，确定每个空间所属的类
最近邻算法：子空间➡️单元

距离度量

L P L_P LP​：曼哈顿距离，欧式距离

k值的选择

近似误差：对现有训练集的训练误差
估计误差：对测试集的测试误差
k较小：overfitting a小e大
k较大：a大e小，例如 k=N 时，相当于整个数据集求平均值
一般采取交叉验证法选取k值

分类决策规则

多数表决法
等价于经验风险最小化
假设涵盖 N k ( x ) N_k(x) Nk​(x)的类别为 c j c_j cj​
那么误分类率为：
1 k ∑ x i ∈ N K ( X ) I ( y i ≠ c j ) = 1 − 1 k ∑ x i ∈ N K ( X ) I ( y i = c j ) frac{1}{k}sum_{x_iin N_K(X)}I(y_ineq c_j)=1-frac{1}{k}sum_{x_iin N_K(X)}I(y_i=c_j) k1​∑xi​∈NK​(X)​I(yi​​=cj​)=1−k1​∑xi​∈NK​(X)​I(yi​=cj​)
采用0-1损失函数，误分类率最小等价于经验风险最小，所以 ∑ x i ∈ N K ( X ) I ( y i = c j ) sum_{x_iin N_K(X)}I(y_i=c_j) ∑xi​∈NK​(X)​I(yi​=cj​)最大，多数表决法等价于经验风险最小