机器学习笔记（九）K近邻法

MachineLearning

1. K近邻模型

1.1 距离度量

距离的计算可以参考机器学习笔记（一）聚类

1.2 K值选择

K值得选取影响着模型的最终效果。如果K值过大，模型过于简单，一个极端，K取整个数据集大小，那么分类决策规则采取多数表决的话，预测结果就是数据集中的大多数类，完全忽略了数据集中的有用信息；如果K取值过小，模型过于复杂，另一个极端，K取1，那么此时模型变成最近邻，容易发生过拟合。

1.3 分类决策规则

一般次用多数表决规则。

2. kd树

2.1 构造kd-tree

对于数据集为$X = \{x_1,x_2,...,x_n\}$,其中$x_i$是k维向量，即$x_i = (x_i^1,x_i^2,...,x_i^K)$，那么对该数据建立kd-tree的过程如下：
1. 选取切分维度
对深度为j的节点，切分维度的计算方法为：$l = j( mod k) + 1$
2. 选取切分值
对切分维度为$x^l$，选取所有实例点的$x^l$维度的中位数作为切分值，对应生成左右子节点。
重复1,2两个步骤，直到没有实例点存在

2.2 搜索kd-tree

kd-tree的搜索时间复杂度为：$o(logn)$
1. 查找包含目标点x的叶结点
2. 由查找到的叶结点向上查找父节点，在父节点的另一个子节点查找最近邻，如果没有则继续转到回退到上一个节点进行查找。

3. 局部敏感哈希（LSH）

LSH的思想就是利用原来距离较近的实例点，在经过hash后也很有可能相似，那么将原来的数据进行一次hash，相似的hash进一个bucket中。在进行近邻搜索时，只需要将该实例进行hash到目标bucket，然后在目标bucket中搜索即可，从而大大降低了时间复杂度。