概念：
K近邻法（k-nearest neighbor，k - N N）是一种基本的分类与回归方法。
主要思想： 假定给定一个训练数据集T(包含N个样本)，其中实例标签已定（每个样本都包含输入和输出），当输入新的实例时（x），可以根据其最近的k个训练实例的标签，预测新实例对应的标注信息(y)。
K近邻法算法分类问题：对新的实例，根据与之相邻的k个训练实例的类别，通过多数表决等方式进行预测。（随大溜）
回归问题：对新的实例，根据与之相邻的k个训练实例的标签，通过均值计算进行预测。
模型：距离计算公式不固定，
k：与x距离最近的k个点
K：输出空间的K个类别
k - N N不具有显性的学习过程，实际上利用训练数据集对特征向量空间进行划分，以其作为分类的“模型”。
K近邻法的三要素 距离度量L p L_{p} Lp距离
特征空间
X
mathcal{X}
X 假设为
R
n
,
∀
x
i
,
x
j
∈
X
,
x
i
=
(
x
i
(
1
)
,
x
i
(
2
)
,
⋯
,
x
i
(
n
)
)
T
,
x
j
=
mathrm{R}^{n}, forall x_{i}, x_{j} in mathcal{X}, x_{i}=left(x_{i}^{(1)}, x_{i}^{(2)}, cdots, x_{i}^{(n)}right)^{T}, x_{j}=
Rn,∀xi,xj∈X,xi=(xi(1),xi(2),⋯,xi(n))T,xj=
(
x
j
(
1
)
,
x
j
(
2
)
,
⋯
,
x
j
(
n
)
)
T
left(x_{j}^{(1)}, x_{j}^{(2)}, cdots, x_{j}^{(n)}right)^{T}
(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
,
p
≥
1
L_{p}left(x_{i}, x_{j}right)=left(sum_{l=1}^{n}left|x_{i}^{(l)}-x_{j}^{(l)}right|^{p}right)^{frac{1}{p}}, quad p geq 1
Lp(xi,xj)=(l=1∑n∣∣∣xi(l)−xj(l)∣∣∣p)p1,p≥1
欧氏距离（Euclidean distance）
L
2
(
x
i
,
x
j
)
=
(
∑
l
=
1
n
∣
x
i
(
l
)
−
x
j
(
l
)
∣
2
)
1
2
L_{2}left(x_{i}, x_{j}right)=left(sum_{l=1}^{n}left|x_{i}^{(l)}-x_{j}^{(l)}right|^{2}right)^{frac{1}{2}}
L2(xi,xj)=(l=1∑n∣∣∣xi(l)−xj(l)∣∣∣2)21
曼哈顿距离（Manhattan distance）
L
1
(
x
i
,
x
j
)
=
∑
l
=
1
n
∣
x
i
(
l
)
−
x
j
(
l
)
∣
L_{1}left(x_{i}, x_{j}right)=sum_{l=1}^{n}left|x_{i}^{(l)}-x_{j}^{(l)}right|
L1(xi,xj)=l=1∑n∣∣∣xi(l)−xj(l)∣∣∣
切比雪夫距离（Chebyshev distance）
L
∞
(
x
i
,
x
j
)
=
max
l
∣
x
i
(
l
)
−
x
j
(
l
)
∣
L_{infty}left(x_{i}, x_{j}right)=max _{l}left|x_{i}^{(l)}-x_{j}^{(l)}right|
L∞(xi,xj)=lmax∣∣∣xi(l)−xj(l)∣∣∣
例子：p=1,p=2,p=无穷
- 较小的k值，学习的近似误差减小，但估计误差增大，敏感性增强，而且模型复杂，容易过拟合。
- 较大的k值，减少学习的估计误差，但近似误差增大，而且模型简单。
k的取值可通过交叉验证来选择，一般低于训练集样本量的平方根。
分类决策规则多数表决规则:
由输入实例的k个邻近的训练实例中的多数类决定输入实例的类。
构造 k d 树 什么是 k d 树f(X)：预测出的x所属的类别
Y：输入x真实所属的类别
概念：k d树是一种对k维空间中的实例点进行储存以便对其进行快速检索的树形数据结构。
构造k d 树本质：二叉树，表示对k维空间的一个划分
构造过程：不断地用垂直于坐标轴的超平面将k维空间切分，形成k维超矩形区域
k d树的每一个结点对应于一个k维超矩形区域
输入：k维空间数据集：
T
=
{
x
1
,
x
2
,
⋯
,
x
N
}
T=left{x_{1}, x_{2}, cdots, x_{N}right}
T={x1,x2,⋯,xN}
其中，
x
i
=
(
x
i
(
1
)
,
x
i
(
2
)
,
⋯
,
x
i
(
k
)
)
T
x_{i}=left(x_{i}^{(1)}, x_{i}^{(2)}, cdots, x_{i}^{(k)}right)^{T}
xi=(xi(1),xi(2),⋯,xi(k))T
输出：k d树
搜索 k d 树（1） 开始：构造根节点
- 选取 x ( 1 ) x^{(1)} x(1) 为坐标轴，以训练集中的所有数据 x ( 1 ) x^{(1)} x(1) 坐标中的中位数作为切分点，将超矩形区域切割成两个子区域，将该切分点作为根节点。
- 由根节点生出深度为1的左右子结点，左节点对应坐标小于切分点，右结点对应坐标大于切分点。
（2）重复
- 对深度为 j 的结点，选择 x ( l ) x^(l) x(l) 为切分坐标轴， l = j ( m o d k ) + 1 l=j(mod k)+ 1 l=j(modk)+1 ，以该结点区域中所有实例 x ( l ) x^(l) x(l) 坐标的中位数作为切分点，将区域分为两个子区域。
- 生成深度为了 j+1 的左、右子结点。左节点对应坐标小于切分点，右结点对应坐标大于切分点。
（3）直到两个子区域没有实例时停止。
最近邻搜索：
-
寻找“当前最近点”
寻找最近邻的子结点作为目标，点的“当前最近点”。
-
回溯
以目标点和“当前最近点”的距离沿树根部进行回溯和迭代。
算法：
输入：已构造的 k d 树，目标点 x
输出：x 的最近邻
- 寻找“当前最近点”
从根结点出发，递归访问 k d 树，找出包含 x 的叶结点；
以此叶结点为“当前最近点”；
- 回溯
若该结点比“当前最近点”距离目标点更近，更新“当前最近点”；
当前最近点一定存在于该结点一个子结点对应的区域，检查子结点的父结点的另一子结点对应的区域是否有更近的点。
- 当回退到根结点时，搜索结束，最后的“当前最近点”即为X的最近邻点。
