《统计学习方法》—— K近邻法
前言
k近邻法是一种特别好理解的算法。但是即便如此，学完这一章也接触到了很多新的东西。
关键知识点
k近邻法的三个基本要素
- 模型
- 距离度量
- k值的选择
Lp距离，又叫Minkowski距离
- 有趣的一点是，允许p<1，则有如下图示，在p取各种不同值时，与原点的Lp距离为1的点的图形
kd树
- 平衡kd树的构造
- 书中提到使用中位数来构造平衡kd树。有一点没有说清楚的是：是先算中位数，然后取大于且最靠近中位数的实例点，作为切分点。
- kd树的搜索
- 书中提到的搜索算法是从根节点出来，定位到包含目标点的区域对应的叶子节点，然后再从下往上依次判断。实际上有另一种方法，就是直接从根节点开始判断，具体算法参考[#1]
- 书中提到的搜索算法是从根节点出来，定位到包含目标点的区域对应的叶子节点，然后再从下往上依次判断。实际上有另一种方法，就是直接从根节点开始判断，具体算法参考[#1]
TODO
#1 如何理解？
Lp距离中，p取无穷大时的情况。
#2 如何理解？
平衡的kd树搜索时的效率未必是最优的。
参考材料
#1 K-D TREE算法原理及实现
https://leileiluoluo.com/posts/kdtree-algorithm-and-implementation.html/