- 一、简介
- 二、k近邻模型
- 模型
- 距离度量
- k值的选择
- 分类决策规则
- 三、K近邻方法的实现：kd树
- 简介
- 构造kd树
- KNN算法（k近邻算法）
- 四、参考代码
一、简介
给定一个训练集，对新输入的实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分到这个类。
- 输入：
训练数据集 T T T T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯ , ( x N , y N ) } T={(x_1,y_1),(x_2,y_2),cdots,(x_N,y_N)} T={(x1,y1),(x2,y2),⋯,(xN,yN)} 实例的特征向量 : x i ∈ χ ⊆ R n , ( i = 1 , 2 , ⋯ , N ) 实例的特征向量:x_iinchisubseteqR^n,(i=1,2,cdots,N) 实例的特征向量:xi∈χ⊆Rn,(i=1,2,⋯,N)
实例的类别： y i ∈ γ = { c 1 , c 2 , ⋯ , c k } , ( i = 1 , 2 , ⋯ , N ) 实例的类别：y_iingamma={c_1,c_2,cdots,c_k},(i=1,2,cdots,N) 实例的类别：yi∈γ={c1,c2,⋯,ck},(i=1,2,⋯,N)
实例的特征向量 x x x - 输出：
实例特征向量 x x x所属的类 y y y - 过程：
（1）根据给定的距离度量，在训练集 T T T中找出与 x x x最邻近的k个点，涵盖这 k k k个点的 x x x的邻域记为 N k ( x ) N_k(x) Nk(x)
（2）在 N k ( x ) N_k(x) Nk(x)中根据分类决策规则决定 x x x的类别 y y y
最近邻算法：k=1时，对输入的实例点的（特征向量x），该算法将训练集T中与x最邻近点的类作为x的类
二、k近邻模型 模型k近邻法没有显式的学习过程。（也就是说没有模型）
- 模型本质：根据三个基本要素——距离度量、k值选择、分类决策规则——对特征空间划分为一些子空间，并确定每个子空间里每个点所属的类。
- 单元（子空间）：特征空间中，对每个训练实例点 x i x_i xi，距离该点最近的所有点组成的一个区域。
- 类标记：将每个训练实例点
x
i
x_i
xi的类
y
i
y_i
yi作为其单元所有点的类标记。
- L p 距离的定义 L_p距离的定义 Lp距离的定义： 特征空间 χ ⊆ R n , x i , x j ∈ χ , x i = ( x i ( 1 ) , x i ( 2 ) , ⋯ , x i ( n ) ) T , x j = ( x j ( 1 ) , x j ( 2 ) , ⋯ , x j ( n ) ) T 特征空间chisubseteqR^n,x_i,x_jinchi,x_i=(x_{i}^{(1)},x_{i}^{(2)},cdots,x_{i}^{(n)})^T,x_j=(x_{j}^{(1)},x_{j}^{(2)},cdots,x_{j}^{(n)})^T 特征空间χ⊆Rn,xi,xj∈χ,xi=(xi(1),xi(2),⋯,xi(n))T,xj=(xj(1),xj(2),⋯,xj(n))T L p ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ p ) 1 p L_p(x_i,x_j)=(sum_{l = 1} ^n |x_i^{(l)}- x_j^{(l)}|^p)^{frac{1}{p}} Lp(xi,xj)=(l=1∑n∣xi(l)−xj(l)∣p)p1 p ≥ 1 pgeq1 p≥1
- 欧式距离： 当 p = 2 时 , L 2 ( x i , x j ) = ( ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ 2 ) 1 2 当p=2时,L_2(x_i,x_j)=(sum_{l = 1} ^n |x_i^{(l)}- x_j^{(l)}|^2)^{frac{1}{2}} 当p=2时,L2(xi,xj)=(l=1∑n∣xi(l)−xj(l)∣2)21
- 曼哈顿距离： 当 p = 1 时 , L 1 ( x i , x j ) = ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ 当p=1时,L_1(x_i,x_j)=sum_{l = 1} ^n |x_i^{(l)}- x_j^{(l)}| 当p=1时,L1(xi,xj)=l=1∑n∣xi(l)−xj(l)∣
- 各个维度坐标之差的最大值： 当 p = ∞ 时 , L ∞ ( x i , x j ) = max i ∣ x i ( l ) − x j ( l ) ∣ 当p=infty时,L_infty(x_i,x_j)=max_i |x_i^{(l)}- x_j^{(l)}| 当p=∞时,L∞(xi,xj)=imax∣xi(l)−xj(l)∣
下图为二维空间中p取不同的值时，与原点的
L
p
L_p
Lp距离为1（
L
p
=
1
L_p=1
Lp=1）的点围成的图形。
k值的选择由不同距离度量所确定的最邻近点是不同的。
- K值选小：意味着用很小的邻域的训练实例去预测，只有与输入实例很近的训练实例才会对预测结果起作用。这一点表面上看起来是好的，但是如果邻近的实例点恰巧是噪声，预测就会出错。
K值减小意味着整体模型变复杂，容易发生过拟合。
- K值选大：意味着用很大的邻域的训练实例去预测，只有与输入实例很远的训练实例才会对预测结果起作用。虽然解决了噪声问题，但是与输入实例很远的（不相似）的训练实例也会对预测起作用，预测也会出错。
K值增大意味着整体模型变得简单
- K值选择：应用中一般取一个较小的数值，通常采用交叉验证法来选取最优的K值.
- 多数表决：由输入实例x的k个邻近的训练实例点中的多数类决定输入实例x的类。
y = arg max c j ∑ x i ∈ N k ( x ) I ( y i = c j ) ， i = 1 , 2 , ⋯ , N ; j = 1 , 2 , ⋯ , K y=argmax_{c_j}sum_{x_iin N_k(x)} I(y_i= c_j)，i=1,2,cdots,N;j=1,2,cdots,K y=cjargmaxxi∈Nk(x)∑I(yi=cj)，i=1,2,⋯,N;j=1,2,⋯,K I 为指示函数，当 y i = c j 时 I 为 1 ，否则 I 为 0 I为指示函数，当y_i=c_j时I为1，否则I为0 I为指示函数，当yi=cj时I为1，否则I为0 - 多数表决等价于经验风险最小化：对给定的实例
x
∈
χ
xinchi
x∈χ,其最邻近的k个训练实例点构成集合
N
k
(
x
)
N_k(x)
Nk(x),如果涵盖
N
k
(
x
)
N_k(x)
Nk(x)的区域的类别为
c
j
c_j
cj，那么误分类率为：
P
(
Y
≠
f
(
x
)
)
=
1
−
P
(
Y
=
f
(
x
)
)
P(Yneq f(x))=1-P(Y=f(x))
P(Y=f(x))=1−P(Y=f(x))
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)
k1xi∈Nk(x)∑I(yi=cj)=1−k1xi∈Nk(x)∑I(yi=cj)
I
为指示函数，当
y
i
=
c
j
时
I
为
1
，否则
I
为
0
I为指示函数，当y_i=c_j时I为1，否则I为0
I为指示函数，当yi=cj时I为1，否则I为0
要使误分类率最小即经验风险最小，就要使 ∑ 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)最大，所以多数表决等价于经验风险最小化。
要实现K近邻法，最简单的方法是计算出每一个训练实例和输入实例的距离，然后找到最近的K个，但是，当训练集很大的时候，我们这样挨个计算就会非常耗时，这种方法不可行。
为了提高K近邻的效率，可以考虑使用特殊的结构存储训练数据，以减少计算距离的次数。kd tree is one method.
- 实质：kd树是个二叉树。构造kd树相当于不断用垂直于选定坐标轴的超平面，构造一系列的k维超矩形区域。
kd树是存储k维空间数据的树结构，这里的k和k近邻法的k意义不同。
下面我举一个例子，并对例子中每一步解法和与之对应kd树构造算法的每一步结合讲解（只看概念去理解kd树构造算法有些抽象。）
2. 构造平衡kd树
输入： k 维空间训练集 T = { x 1 , x 2 , ⋯ , x N } ，其中 x i = ( x i ( 1 ) , x i ( 2 ) , ⋯ , x i ( k ) ) T , i = 1 , 2 , ⋯ , N ； 输入：k维空间训练集T={x_1,x_2,cdots,x_N}，其中x_i=(x_i^{(1)},x_i^{(2)},cdots,x_i^{(k)})^T,i=1,2,cdots,N； 输入：k维空间训练集T={x1,x2,⋯,xN}，其中xi=(xi(1),xi(2),⋯,xi(k))T,i=1,2,⋯,N；
输出： k d 树 输出：kd树 输出：kd树
（1）找到根结点的坐标：选择所有训练实例中 x ( 1 ) x^{(1)} x(1)坐标的中位数为切分点，该切分点坐标就是根结点坐标。根结点对应于包含T的k维空间的超矩形区域。
（2）切分：由通过切分点并与坐标轴
x
(
1
)
x^{(1)}
x(1)垂直的超平面将根结点对应的超矩形区域切分为2个子区域。
kd树由根结点生成深度为1的左、右子结点：左子结点对应坐标
x
(
1
)
x^{(1)}
x(1)小于切分点的子区域，右子结点对应坐标
x
(
1
)
x^{(1)}
x(1)大于切分点的子区域。
（3）重复：对深度为
j
j
j的结点，选
x
(
l
)
x^{(l)}
x(l)为切分的坐标轴，选择所有训练实例中
x
(
l
)
x^{(l)}
x(l)坐标的中位数为切分点，
l
=
j
(
m
o
d
k
)
+
1
l=j(mod k)+1
l=j(mod k)+1该切分点的坐标就是深度为
j
j
j的结点的坐标。
由通过切分点并与坐标轴
x
(
l
)
x^{(l)}
x(l)垂直的超平面，将深度为
j
j
j的结点对应的超矩形区域切分为2个子区域。
kd树由该深度为
j
j
j的结点生成深度为
j
+
1
j+1
j+1的左、右子结点：左子节点对应坐标
x
(
l
)
x^{(l)}
x(l)小于切分点的子区域，右子结点对应坐标
x
(
l
)
x^{(l)}
x(l)大于切分点的子区域。
（4）直到两个子区域没有实例存在时停止。
最终的这个树就是 平衡kd树
输入：已经构造好的 k d 树，目标点 p ，近邻数 k 输入：已经构造好的kd树，目标点p，近邻数k 输入：已经构造好的kd树，目标点p，近邻数k
输出：
p
的
k
近邻
输出：p的k近邻
输出：p的k近邻
一、切分向下搜索
P结点与各深度下的结点的对应
x
(
l
)
x^{(l)}
x(l)坐标相比较
左枝：
x
p
(
l
)
<
x
(
l
)
x_p^{(l)}
最后找到最底部结点
二、达到底部结点，将其标记为访问过
- 若L中不足K个点，则将其当前结点加入L
- 若L中已满K个点，并且当前结点与P的距离小于L中最长的距离，则用当前结点替换L中离P最远的点
三、当前结点是否为最顶端的结点
以上图片为第三步手写算法，观看性不太好，后期会电脑补个电子版流程图，以便大家理解算法
这一步为该算法最繁琐的地方，我用例子和概念结合写的，方便理解
四、参考代码对于以上这个例子，个人感觉自己举得不是很典型，当时只是拿书中例题作为例子写下来。此例虽然用到kNN的所有算法步骤，但是所有实例点都有扫描到，平均计算复杂度还是很高，并未体现出KNN比线性扫描的效率高，后面我有时间会重新补一个例子说明KNN算法的高效率。
本文参考代码都可以在我博客主页资源下载上找到。
文章有些地方条理可能不清楚也难免有错误，希望大佬可以指正。
