K邻近算法

引言

K邻近算法的总结,内容主要来自于《统计学习方法》和《机器学习实战》两本书。


K邻近

概念

K邻近算法很近单,可以作为分类器和回归。

作为分类器用介绍起来就是:根据给定输入和已有样本计算一个距离,再根据距离的大小排序,取前K个的已有样本的最多种类,作为输入的预测值。

作为回归的用法日后补充。

数学表达

距离度量

距离的度量方式有很多种,常见的对应坐标差平方的和叫做欧氏距离,还有很多,曼哈顿距离等等,统称为L<sub>p</sub>距离或者Minkowski距离

K值的选择

K值的选择会严重影响模型的结果。K越小意味着越容易过拟合,模型复杂度越高,对噪声越敏感。通常通过交叉验证来选K值

分类决策规则

多数表决,这个简单粗暴,很好。从数学上讲,多数表决规则等价于经验风险最小化(不懂可忽略)。

kd-Tree

kd树是用来优化K邻近算法中,找K个最近邻居步骤的算法。本质上是一个平衡二叉树。简单讲就是将数据按维度依次分开。

构建流程

  1. 计算输入数据每个维度的方差,然后按照降序排列维度,记为W
  2. W中的第一个维度的数据,取中位数。
  3. 然后按照中位数将数据分为两个部分,中位数所在的数据点为节点。
  4. 然后对分开的两个部分,分别按照W中第二个维度的中位数分成两个部分,再对分开的部分按第三个维度等等等,直到最后一个维度,如果被分开的部分还有数据,就回到第一个维度。

按照方差排序是因为,方差越大,表示数据在那个维度越容易分开。

这里的中位数并不是常规意义上的中位数(即统计学习方法中P41下的脚注是错误的),是序列长度除以二加一,也就是说如果数据有8个,那就取第5个。

搜索

写到搜索我才发现,好像都讲得是搜索与给定点最邻近的一个点,但是k邻近算法要的是邻近的k个点,好像有不符合要求,就不写了。


后记

机器学习算法填坑之路,加油加油~~~~