基于距离的分类算法
- 监督学习
我们已经了解了两类问题：回归问题和分类问题，实际上这两类问题都属于监督学习问题。一般课本里对监督学习定义是指从标注数据中学习预测模型的机器学习问题，那什么是标注数据呢？我们回忆一下之前将的回归问题，我们本身就有一些自变量，我们也已知一些自变量对应的因变量。这些因变量就是它的标签。同样在分类问题中，我们本身也已知一些变量对应的类别，类别也是标签。监督学习中，输入与输出所有可能的集合称为输入\输出空间。输入通常用特征向量表示，所有特征向量存在的空间称为特征空间(feature space)。因此监督学习往往有训练数据(training data)和测试数据(test data)之分。我们首先利用训练数据中得到一个学习模型。在监督学习领域中，假设输入变量X与输出变量Y满足某个联合概率分布P(X,Y)。最后得到的模型往往用条件概率分布P(Y|X)或者决策函数(decision function)Y = f(x)表示。无论是条件概率分布还是决策函数，都可以看做输入到输出的一个映射。映射可以有多个，我们把所有可能的映射所组成的集合称为假设空间(hypothesis space)。
监督学习步骤可以简单概括成学习与预测，分别由学习系统与预测系统完成。学习系统即是前面讲的利用已有标签的训练数据集得到一个模型。预测系统则对测试样本集由模型或者给出相应的输出。
- 分类算法的另一种思路
我们继续讨论分类问题。在分类问题中，有一个经常用到的数据集就是鸢尾花数据集。鸢尾花数据集是一类多重变量分析的数据集。数据集包含150个数据集，分为3类，每类50个数据，每个数据包含4个属性。可通过花萼长度，花萼宽度，花瓣长度，花瓣宽度4个属性预测鸢尾花卉属于(Setosa，Versicolour，Virginica)三个种类中的哪一类。我们可以以花瓣长度为横轴，花瓣宽度为纵轴，得到如图1所示的散点图。
图 1 花瓣长度宽度散点图
如图1所示，Setosa鸢尾花基本分布在左下角，而Versicolour鸢尾花大约分布于中间，Virginica鸢尾花则大约分布于右上侧。这样看起来，似乎存在某种"天然边界"将各个类别分离，形成某种"同类相吸"的现象。我们由此想到另一种分类方法，就是找到这个"边界"，直接得到测试数据的类别。
我们之前提到，监督学习的输入变量可以分为训练数据和测试数据。训练数据中已经给数据做好了标签，也就是我们想得到的类别。如果把各种类别看做一个个盒子，我们要做的就是把测试数据放入到那个正确的盒子中。怎么放呢，自然是看看这个类别有哪些特点了。而这个特点自然是从训练数据中来。我们要做的就是利用训练数据找到与各个类别的相似点，哪个相似点最多自然就是哪个类别了，我们一般把这种原则称为"多数表决"。这是一个新的分类思路。
- 距离度量
特征空间中两个点的距离是一种度量相似点的重要方法。我们一般采用距离或者Minkowski距离来定义。
设特征空间是n维向量空间，，，，的距离定义为：
如果p = 1，该距离就是曼哈顿距离。如果p = 2，该距离就成了曼哈顿距离。如果p = ，该距离就是各个坐标距离的最大值。
- KNN算法
KNN算法就是一种采用距离度量分类的经典算法。KNN的全称为K-Nearest Neighbor，即选取K个最相近的邻居。这K个最近点中，哪个类别占比最多，待分类点就属于哪个类别。
自然，我们就需要考虑K的选取问题。K如果取小了，估计误差会增大。估计误差关注测试集，估计误差小了说明对未知数据的预测能力好且模型本身最接近最佳模型。估计误差的过大会让结果对临近的点过于敏感，容易产生过拟合现象。K如果取大了，近似误差会增大，对未知的测试样本将会出现较大偏差的预测且模型本身不是最接近最佳模型。K一般在现实中采用交叉验证等实验方法得到。
选好K之后，则就要面对如何快速搜索近邻点的距离。我们首先想到的肯定是线性扫描(linear scean)，即一个个计算输入示例与每一个示例的距离，但当训练集很大时，肯定还是不大现实。这就要用到一个很有用的数据结构——kd树了。
-
kd树
图 2 特征空间的分割
如图2所示，假如我们想找到距离五角星最近的两个点，可以一个个分别计算距离。但假如点的数量足够多，就不能这么做了。在现实中，我们凭直觉，先找到五角星附近的几个点再分别量一下，可惜计算机并没有这种直觉。这个时候，就可以利用二叉树来进行表征这种"直觉"。我们可以尝试把特征空间不断切割放到左右两个子树，找到蕴藏五角星的叶子结点再向上回溯寻找。
我们更具体得讲讲这种算法。刚刚讲的的情况，需要用一个一维平面来切割成两半。如果对于，就需要一个n – 1维的平面来切割。我们一般把这个负责分割的平面称为超平面。既然知道了要分，那就要解决如何分的问题。我们在数据结构中已经学过了二叉排序树利用左小右大的原则依次排序，但面对多维数据，显然不能直接这样排。既然如此，就先一个维度来进行排序好了。一般对于二维空间的情况，采取奇数层按照x层划分，偶数层按照y层进行划分。其他情况也是按照关键字依次划分。既然知道了划分的维度，那么又以什么标准划分呢。在kd树中，一般取所有点该维度坐标的中位数作为切分点(实际上也有利用方差最大的一维做切割点)。这样，左子树就保存了对应维度小于切分点的子区域，右子树保存了对应维度大于切分点的子区域。之后继续这样切割下去。假设现在到了j层，则选择第l个维度为坐标轴，这里，这里的k指的是总共维度的大小。于是这样一直切割，直到没有实例存在时停止。
构造好了kd树，下面就要解决如何利用kd树解决寻找最近点的问题了。和二叉搜索树一样，我们先佯装要在kd树中找到我们要找到点，按照维度依次沿左右移动，直至找到一个叶节点，然后标记其已经访问过(可以用一个固定大小为k的数据结构存储该结点的信息，假设该数据结构记为L)。如果L满了，我们就要看看待加入的结点是否与L中距离最长的点相比距离要小，如果是的话就替换掉距离最长的结点。接下来我们可以回溯到叶子结点的父亲结点，如果父亲结点也被访问过了，就继续回溯下一个父亲结点。如果父亲结点没有访问过就标记并进行上次同样的操作。然后比较一下父亲结点切分线的距离是否比L中最大距离大，如果大了且刚好L已满就无需访问父亲结点其他叶子结点。如果小了或者L未满，就访问另一个叶子结点。就这样不断循环，直到访问到根节点为止。
如果训练的实例远大于空间维数，kd树复杂度是O(logN)。但如果二者接近，则搜索效率会无限仅仅线性模型的搜索效率。所以kd树更适合训练实例远大于空间维数的情况。