总结机器学习中的K近邻算法模型。
kNN算法：
输入：训练数据集$T = \left{ \left( x_{1}, y_{1} \right), \left( x_{2}, y_{2} \right), \cdots, \left( x_{N}, y_{N} \right) \right}$，其中$x_{i} \in \mathcal{X} \subseteq R^{n}$是实例的特征向量，$ y_{i} \in \mathcal{Y} = \left{ c_{1}, c_{2}, \cdots, c_{K} \right}$是实例的类别，$ i = 1, 2, \cdots, N$；实例特征向量$x$
输出：实例$x$所属的类$y$
- 根据给定的距离度量，在训练集$T$中找出与$x$最近邻的$k$个点，涵盖这$k$点的$x$的邻域记作$N_{k} \left( x \right)$；
- 在$N_{k} \left( x \right)$中根据分类决策规则决定$x$的类别$y$： \begin{align} \ & y = \arg \max_{c_{j}} \sum_{x_{i} \in N_{k} \left( x \right)} I \left( y_{i} = c_{j} \right), \quad i=1,2, \cdots, N; \quad j=1,2,\cdots,K \end{align}
设特征空间$\mathcal{X}$是$n$维实数向量空间$R^{n}$，$x_{i},x_{j} \in \mathcal{X},x_{i} = \left( x_{i}^{\left( 1 \right)},x_{i}^{\left( 2 \right) },\cdots,x_{i}^{\left( n \right) } \right)^{T},x_{j} = \left( x_{j}^{\left( 1 \right)},x_{j}^{\left( 2 \right) },\cdots,x_{j}^{\left( n \right) } \right)^{T}$，$x_{i},x_{j}$的$L_{p}$距离
\begin{align} \ & L_{p} \left( x_{i},x_{j} \right) = \left( \sum_{l=1}^{N} \left| x_{i}^{\left(l\right)} - x_{j}^{\left( l \right)} \right|^{p} \right)^{\dfrac{1}{p}}\end{align}
其中，$p \geq 1$。当$p=2$时，称为欧氏距离，即
\begin{align} \ & L_{2} \left( x_{i},x_{j} \right) = \left( \sum_{l=1}^{N} \left| x_{i}^{\left(l\right)} - x_{j}^{\left( l \right)} \right|^{2} \right)^{\dfrac{1}{2}}\end{align}
当$p=1$时，称为曼哈顿距离，即
\begin{align} \ & L_{1} \left( x_{i},x_{j} \right) = \sum_{l=1}^{N} \left| x_{i}^{\left(l\right)} - x_{j}^{\left( l \right)} \right| \end{align}
当$p=\infty$时，是各个坐标距离的最大值，即
\begin{align} \ & L_{\infty} \left( x_{i},x_{j} \right) = \max_{l} \left| x_{i}^{\left(l\right)} - x_{j}^{\left( l \right)} \right| \end{align}
多数表决规则：如果分类的损失函数为0-1损失函数，分类函数
\begin{align} \ & f: R^{n} \to \left{ c_{1}, c_{2}, \cdots, c_{K} \right} \end{align}
则误分类的概率
\begin{align} \ & P \left( Y \neq f \left( X \right) \right) = 1 - P \left( Y = f\left( X \right) \right) \end{align}
对给定的实例$x \in \mathcal{X}$，其最近邻的$k$个训练实例点构成的集合$N_{k} \left( x \right)$。如果涵盖$N_{k} \left( x \right)$的区域的类别是$c_{j}$，则误分类率
\begin{align} \ & \dfrac{1}{k} \sum_{x_{i} \in N_{k} \left( x \right)} I \left( y_{i} \neq c_{j}\right) = 1 -\dfrac{1}{k} \sum_{x_{i} \in N_{k} \left( x \right)} I \left( y_{i} = c_{j}\right) \end{align}
即经验风险最小化等价于多数表决规则。
平衡kd树构造算法：
输入：$k$维空间数据集$T = \left{ x_{1}, x_{2}, \cdots, x_{N} \right}$，其中$x_{i} = \left( x_{i}^{\left(1\right)}, x_{i}^{\left(1\right)},\cdots,x_{i}^{\left(k\right)} \right)^{T}, i = 1, 2, \cdots, N$；
输出：kd树
- 开始：构造根结点，根结点对应于包涵$T$的$k$维空间的超矩形区域。
选择$x^{\left( 1 \right)}$为坐标轴，以$T$中所欲实例的$x^{\left( 1 \right)}$坐标的中位数为切分点，将根结点对应的超矩形区域切分成两个子区域。切分由通过切分点并与坐标轴$x^{\left( 1 \right)}$垂直的超平面实现。
由根结点生成深度为1的左、右子结点：坐子结点对应坐标$x^{\left( 1 \right)}$小于切分点的子区域，右子结点对应于坐标$x^{\left( 1 \right)}$大与切分点的子区域。
将落在切分超平面上的实例点保存在跟结点。 - 重复：对深度为j的结点，选择$x^{\left( l \right)}$为切分坐标轴，$l = j \left(\bmod k \right) + 1 $，以该结点的区域中所由实例的$x^{\left( l \right)}$坐标的中位数为切分点，将该结点对应的超矩形区域切分为两个子区域。切分由通过切分点并与坐标轴$x^{\left( l \right)}$垂直的超平面实现。
由根结点生成深度为$j+1$的左、右子结点：坐子结点对应坐标$x^{\left( l \right)}$小于切分点的子区域，右子结点对应于坐标$x^{\left( l \right)}$大与切分点的子区域。
将落在切分超平面上的实例点保存在跟结点。 - 直到两个子区域没有实例存在时停止。
kd树的最近邻搜索算法：
输入：kd树；目标点$x$
输出：$x$的最近邻
- 在kd树中找出包含目标点$x$的叶结点：从跟结点出发，递归地向下访问kd树。若目标点$x$当前维的坐标小于切分点的坐标，则移动到左子结点，否则移动到右子结点。直到子结点为叶结点为止。
- 以此叶结点为“当前最近点”。
- 递归地向上回退，在每个结点进行以下操作：
3.1 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例点为“当前最近点”。
3.2 当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。
如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着，递归地进行最近邻搜索；
如果不相交，向上回退。 - 当回退到根结点时，搜索结束。最后的“当前最近点”即为$x$的当前最近邻点。