引言
K邻近算法的总结,内容主要来自于《统计学习方法》和《机器学习实战》两本书。
K邻近
概念
K邻近算法很近单,可以作为分类器和回归。
作为分类器用介绍起来就是:根据给定输入和已有样本计算一个距离,再根据距离的大小排序,取前K个的已有样本的最多种类,作为输入的预测值。
作为回归的用法日后补充。
数学表达
距离度量
距离的度量方式有很多种,常见的对应坐标差平方的和
叫做欧氏距离,还有很多,曼哈顿距离等等,统称为L<sub>p</sub>距离
或者Minkowski距离
。
K值的选择
K值的选择会严重影响模型的结果。K越小意味着越容易过拟合,模型复杂度越高,对噪声越敏感。通常通过交叉验证来选K值。
分类决策规则
多数表决,这个简单粗暴,很好。从数学上讲,多数表决规则等价于经验风险最小化(不懂可忽略)。
kd-Tree
kd树是用来优化K邻近算法中,找K个最近邻居步骤的算法。本质上是一个平衡二叉树。简单讲就是将数据按维度依次分开。
构建流程
- 计算输入数据每个维度的方差,然后按照降序排列维度,记为
W
。 - 取
W
中的第一个维度的数据,取中位数。 - 然后按照中位数将数据分为两个部分,中位数所在的数据点为节点。
- 然后对分开的两个部分,分别按照
W
中第二个维度的中位数分成两个部分,再对分开的部分按第三个维度等等等,直到最后一个维度,如果被分开的部分还有数据,就回到第一个维度。
按照方差排序是因为,方差越大,表示数据在那个维度越容易分开。
这里的中位数并不是常规意义上的中位数(即统计学习方法中P41下的脚注是错误的),是序列长度除以二加一,也就是说如果数据有8个,那就取第5个。
搜索
写到搜索我才发现,好像都讲得是搜索与给定点最邻近的一个点,但是k邻近算法要的是邻近的k个点,好像有不符合要求,就不写了。
后记
机器学习算法填坑之路,加油加油~~~~