《统计学习方法》（第三章）—— K邻近机器学习

K邻近算法

定义:给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分为这个类。
算法：
??输入：训练数据集：
???? T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . . , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),....,(x_N,y_N)\} T={(x1?,y1?),(x2?,y2?),....,(xN?,yN?)}其中 x i ∈ χ ? R n x_i \in\chi\subseteq R^n xi?∈χ?Rn，为实例的特征向量， y i ∈ γ = { c 1 , c 2 , . . . , c k } y_i \in\gamma=\{c_1,c_2,...,c_k\} yi?∈γ={c1?,c2?,...,ck?}为实例的类别， i = 1 , 2 , . . . . , N ; i=1,2,....,N; i=1,2,....,N; 实例特征向量 x x x;
??输出：实例 x x x所属类别 y y y
- ( 1 ) (1) (1)根据给定的距离度量，在训练集 T T T中找出与 x x x最邻近的 k k k个点，涵盖这个 k k k个点的 x x x的邻域记作 N k ( x ) ; N_k(x); Nk?(x);
- ( 2 ) (2) (2)在 N k ( x ) N_k(x) Nk?(x)中根据分类决策规则（如多数表决）决定 x x x的类别 y ; y; y;
  ???? y = a r g m a x c j ∑ x i ∈ N k ( x ) I ( y i = c j ) y=argmax_{c_j}\sum\limits_{x_i \in N_k(x)}I(y_i=c_j) y=argmaxcj??xi?∈Nk?(x)∑?I(yi?=cj?) ??i = 1 , 2 , . . . . , N ; j = 1 , 2 , . . . , K i=1,2,....,N; j=1,2,...,K i=1,2,....,N; j=1,2,...,K
  ???? I I I为指示函数，如果条件成立则是 1 1 1，否则是 0 0 0, K = 1 K=1 K=1称为最邻近， K K K邻近没有显式的学习过程

K邻近模型

模型
??训练集，距离度量， k k k值和分类决策规则确定后，就可以对任何一个新的输入实例进行预测
距离度量
- L p ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) ? x j ( l ) ∣ ) 1 p L_p(x_i,x_j)=(\sum\limits_{l=1}^n|x_i^{(l)}-x_j^{(l)}|)^{\frac{1}{p}} Lp?(xi?,xj?)=(l=1∑n?∣xi(l)??xj(l)?∣)p1?
- p = 2 p=2 p=2时为欧式距离
- p = 1 p=1 p=1时为曼哈顿距离
- p = ∞ p=\infty p=∞时 L ∞ ( x i , x j ) = max ? l ∣ x i ( l ) ? x j ( l ) ∣ L_\infty(x_i,x_j)=\max_l|x_i^{(l)}-x_j^{(l)}| L∞?(xi?,xj?)=maxl?∣xi(l)??xj(l)?∣
K值的选择
- K值大则模型简单，近似误差大，估计误差小
- K值小则模型复杂，近似误差小，估计误差大
分类决策规则
- 多数表示规则：
  ???如果分类的损失函数为 0 ? 1 0-1 0?1损失函数,分类函数 f : R n → { c 1 , c 2 , . . . , c k } f:R^n\to\{c_1,c_2,...,c_k\} f:Rn→{c1?,c2?,...,ck?}那么误分类的概率是
  ?? P ( Y ≠ f ( X ) ) = 1 ? P ( Y = f ( X ) ) P({Y} \neq {f(X)})=1-P(Y=f(X)) P(Y?=f(X))=1?P(Y=f(X))对给定区域经验损失函数
  ?? L o s s = 1 k ∑ x i ∈ N k ( x ) I ( y i ≠ c i ) = 1 ? 1 k ∑ x i ∈ N k ( x ) I ( y i = c i ) Loss=\Large\frac{1}{k}\normalsize\sum\limits_{x_i \in N_k(x)}I(y_i\ne c_i)=1-\Large\frac{1}{k}\normalsize\sum\limits_{x_i \in N_k(x)}I(y_i=c_i) Loss=k1?xi?∈Nk?(x)∑?I(yi??=ci?)=1?k1?xi?∈Nk?(x)∑?I(yi?=ci?)
  ??要使 L o s s Loss Loss最小，就要使 ∑ x i ∈ N k ( x ) I ( y i = c i ) \sum\limits_{x_i \in N_k(x)}I(y_i=c_i) xi?∈Nk?(x)∑?I(yi?=ci?),最大，所以得证

KD树

构造KD树
- 算法：
  ??输入： k k k维空间数据集合 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . . , ( x N , y N ) } T=\{(x_1,y_1),(x_2,y_2),....,(x_N,y_N)\} T={(x1?,y1?),(x2?,y2?),....,(xN?,yN?)},其中 x i = ( x i ( 1 ) , x i ( 2 ) , . . . , x i ( k ) ) T x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(k)})^T xi?=(xi(1)?,xi(2)?,...,xi(k)?)T
  ? i = 1 , 2 , . . . , N ; i=1,2,...,N; i=1,2,...,N;
  ??输出： k d kd kd树
  - ( 1 ) (1) (1)开始，构造根节点，根节点对应于包含 T T T的 k k k维空间的超矩形区域，选择 x ( 1 ) x^{(1)} x(1)为坐标轴，以 T T T中的所以实例对 x ( 1 ) x^{(1)} x(1)为中位数，分类左右两个子集，左子集小于 x ( 1 ) x^{(1)} x(1),右子集大于 x ( 1 ) x^{(1)} x(1)，等于 x ( 1 ) x^{(1)} x(1)则存在根节点，形成一个二叉树结构
  - ( 2 ) (2) (2)重复:以上一次划分为起点，设上一次划分为 j j j维，则重新选 j = j ( m o d k ) + 1 , j=j\pmod{k}+1, j=j(modk)+1,重新按照 ( 1 ) (1) (1)进行操作
  - ( 3 ) (3) (3)直到两个子区域没有实例存在时停止。从而形成 k d kd kd树
KD树的搜索：
- 算法：
  ??输入：测试点 ( x , y ) (x,y) (x,y)
  ??输出：类别
  - ( 1 ) (1) (1)按照最初划分规则递归的寻找包含测试点的最小子区域，先把它定位最近点
  - ( 2 ) (2) (2)返回父亲节点，如果此时选中节点集合个数小于 k k k，则加入父亲节点，如果选中节点集合个数还小于 k k k则加入另一个子节点,如果等于 k k k则判断里面最远点和要加入点的距离，如小于最远点的化则更新，选择点的集合，同时如果最远集合的点的圆与子节点区域相交，也需要去判断一下。
  - ( 3 ) (3) (3)直到所有递归完成，最后集合里面就是k个最近的点，根据决策规则进行统计答案输出
    我们这里集合可以用优先队列来维护