1 K近邻算法

给定训练数据集和测试样本，根据给定的距离度量方法，在训练数据集中找出距离该样本最近的k个样本，然后根据这k个样本的类别和某种决策规则（如多数表决）来确定测试样本的类别。当k=1时，算法变成最近邻算法。

可见，K近邻算法涉及3个要素，k值的选择、距离度量、决策规则。

这种模型具有很高的容量，在训练数据集很大的时候效果很好；在训练阶段开销为0，即”惰性学习“。但其计算量很高（特别是在训练集很大的时候），训练集较小时泛化能力较差，且无法判别特征的重要程度。

2 K值的选择

当k=1时，该算法为最近邻算法。
当k值较小时，相当于使用较小邻域内的训练样本进行预测，此时的模型预测结果具有较小的bias和较大的variance。
当k值较大时，模型具有较大的bias和较小的variance。
一般k会取一个较小的值，使用交叉验证来确定合适的k值。

3 距离度量

这里的距离用来表示两个样本点的相似程度。k近邻算法的输入样本的特征空间一般是n维实数向量空间。对于距离的度量一般采用欧式距离，也可以采用其他距离。

以下$P(x_1, x_2, \dots, x_n),Q(y_1, y_2, \dots, y_n), \mathbf x = (x_1,x_2,\dots,x_n)^T, \mathbf y = (y_1, y_2, \dots, y_n)^T$

3.1 闵可夫斯基距离欧式距离曼哈顿距离切比雪夫距离

闵可夫斯基距离：
$$
dist = (\sum_{i=1}^n |x_i - y_i|^p)^{1/p}
$$
当$p=1$时，该距离为曼哈顿距离：
$$
dist = \sum_{i=1}^n |x_i - y_i|
$$

当$p=2$时，该距离为欧氏距离：
$$
dist = \sqrt {\sum_{i=1}^n (x_i - y_i)^2}
$$

当$p$趋于无穷大时，该距离为切比雪夫距离：
$$
dist = \lim \limits_{p \to \infty} \left( \sum_{i=1}^n |x_i - y_i |^p \right)^{1/p} = \max \limits_{i=1}^n |x_i - y_i|
$$
在使用闵可夫斯基距离度量之前，可能需要对数据进行标准化处理。

闵可夫斯基距离比较直观，但是不能反映数据的分布和各个维度之间的相关性。

3.2 马氏距离 (Mahalanobis Distance)

假设有$m$个$n$维的样本$ x_1, \dots, x_m,x_i\in R^n$，协方差矩阵为$S$，均值为$\mu$，则样本$x$到均值$\mu$的马氏距离为：
$$
dist = \sqrt {(x - \mu)^T S^{-1} (x - \mu)}
$$
样本$x_i,x_j$之间的距离为：
$$
dist = \sqrt {(x_i - x_j)^T S^{-1} (x_i - x_j)}
$$
当协方差矩阵$S$为单位阵时，马氏距离相当于欧氏距离。

马氏距离与量纲无关，可以排除变量之间的相关性的干扰。

3.3 向量内积

$$
<\mathbf x,\mathbf y> = \sum_{i=1}^n x_i y_i
$$

3.4 余弦相似度

$$
CosSim(\mathbf x, \mathbf y) = \frac {<\mathbf x, \mathbf y >} {||\mathbf x|| ||\mathbf y||} = \frac {\sum_{i=1}^n x_iy_i} {\sqrt {\sum_{i=1}^n x_i^2} \sqrt {\sum_{i=1}^n y_i^2}}
$$

余弦相似度与向量的幅度无关，只与向量的方向有关。

3.5 皮尔逊相关系数

$$
\begin {align}
Corr (\mathbf x, \mathbf y)& = CosSim(\mathbf x - \bar x, \mathbf y - \bar y) \\
& = \frac {<\mathbf x - \bar x, \mathbf y - \bar y>} {||\mathbf x - \bar x|| || \mathbf y - \bar y ||} \\
& = \frac {\sum_i (x_i - \bar x)(y_i - \bar y)} {\sqrt {\sum_i (x_i - \bar x)^2} \sqrt {\sum_i (y_i - \bar y)^2}}
\end {align}
$$

皮尔逊相关系数具有平易近人不变性和尺度不变性。

3.6 汉明距离

两个等长字符串$s_1$和$s_2$之间的汉明距离定义为将一个变为另一个需要的最小替换次数。

3.7 Jaccard相似系数 Jaccard距离

两个集合$A,B$之间的Jaccard相似系数为：
$$
J(A,B)=\frac {|A \cap B|} {|A \cup B|}
$$
Jaccard距离用于衡量两个集合的区分度，定义为：
$$
J_\delta (A,B) = 1 - J(A,B) = \frac {|A \cup B| - |A \cap B|} {|A \cup B|}
$$

3.8 编辑距离

两个字符串之间的编辑距离定义为将一个转换成另一个所需要的最少编辑操作次数。允许的操作包括对一个字符进行替换、插入、删除。
$$
dist(i,j) =
\begin{cases}
0, & if & i =0,j=0 \\
j, & if & i=0,j\neq 0 \\
i, & if & i \neq 0, j = 0 \\
\min (dist(i-1, j-1), dist(i, j-1)+1, dist(i-1, j) + 1), & if & i\neq 0,j\neq 0,s1[i]=s2[j] \\
\min (dist(i-1, j-1)+1, dist(i, j-1)+1, dist(i-1, j) + 1), & if & i\neq 0,j\neq 0,s1[i]\neq s2[j]
\end{cases}
$$

3.9 KL散度

KL散度即相对熵，衡量两个分布之间的相似度：
$$
D(P||Q) = \sum_{i=1}^n P(i) \log \frac {P(i)} {Q(i)}
$$

4 决策规则

分类决策可以用多数表决，或者根据距离测试样本点的远近、对于邻域内的样本点赋予不同权重。
回归问题可以用求均值的方法，也可以根据距离测试样本的远近进行加权投票。

5 KD树

kd树即k-dimonsion tree，用于在k维空间中对数据进行划分，主要用于k维空间中相似性检索。这是一种平衡二叉树。

一般来说，高维空间中的相似性检索有两种方式，一是范围查询，在数据集中查找所有与目标点的距离低于阈值的样本；另一种是K近邻，只查找与目标点最近的K个样本。查找方式也有两种，一种是线性扫描，对所有样本点计算它到目标点的距离；另一种是构建索引，对特征空间进行层次划分。KD树属于后者的一种，在划分时各个子空间没有重叠。

6 KD树的构建

使用如下的算法构造KD树：

构造根节点，对应于整个k维空间
使用如下的方法生成左孩子和右孩子节点：

a. 维度选择：对于需要构造kd树的样本集，计算每个维度上的方差，选择方差最大的维度作为划分的维度。

b. 在该维度上对样本集进行排序，取中值作为划分点。

c. 使用该划分点，将当前空间划分为左右两个子空间，对应的样本集也划分为左右两个子集，分别对应于左孩子和右孩子。
对左孩子和右孩子，递归的使用第2步生成对应的kd树，直到子空间内无样本。

维度的选择方式，除了使用最大方差的方式，还可以使用顺序、指定优先次序的方式。划分点的选择，除了使用中值，也可以使用中位数。

7 KD树的最近邻搜索

确定初始值：从kd树的根节点出发，递归的访问孩子节点，直到找到目标点x所在的叶子节点。如果目标点x的当前维度的坐标小于当前节点对应的划分坐标，则访问左孩子，否则访问右孩子。以最终叶子节点作为当前最近邻点。
回溯：向上回归，直到到达根节点。对于每一个经过的节点，进行如下的操作：

a. 如果该节点对应的样本点比”当前最近邻点”距离目标点更近，则对”当前最近邻点”进行更新，更新为该节点。

b. 搜索可能存在的解：最近邻点一定存在于该节点的两个子树中。检查该节点的另一个子节点对应的子空间中是否存在更近的点。具体做法是，以目标点x为球心、目标点和”当前最近邻点”之间的距离为半径作球，看这个超球体是否与该节点对应的划分超平面相交，如果相交则说明另一个子节点对应的子空间中可能存在更近的点，如果如此，则移动到另一个子节点，并在另一个子节点中递归的进行最近邻搜索；否则，向上回退。
回退到根节点时，搜索结束，此时的”当前最近邻点”即为离目标点最近的点。