k近邻算法
k近邻算法
k近邻算法是一个基本的分类回归方法,其没有显式的学习过程,而是完全取决于数据,因此k近邻是基于数据的学习算法,其只有唯一的一个参数 。
1、k近邻算法
给定一组已知数据 ,其中 表示样本的特征向量, 是对应的标签。通过这组数据可以构建一个k近邻模型。在测试阶段,给定一个样本 ,计算其与所有其他训练样本的距离,并得到最近的k个样本,这k个样本中类标最多的作为当前样本 的预测结果。
值的选择是该算法唯一的一个超参数。其表示在判断所给定样本的类时,所挑选附近点的个数。如果 值过大,说明周围的点数量越多,距离越远的点也会起到分类的作用,模型变得简单,容易产生欠拟合;如果 值过小,则所选的点数量少,模型过于复杂, 容易产生过拟合。当 时,则表示为最近邻,其最近的样本点的类作为预测的类;当 时,则整个训练集的样本最多的类作为预测值,此时不具有分类效果了,模型变得非常简单。
2、距离函数
距离度量函数常用的是 距离,即:
当 时即为曼哈顿距离(绝对值的差);当 时表示欧氏距离(平方和的根式)。
对分类的结果的评价是指所有误分类点的概率,即该点没有被预测为正确类的概率。因此学习的目标则是最小化误分类点的概率,其等价于经验风险最小化。
3、Kd树
给定一组训练集,首先构建kd树,构建方法可描述为:
(1)假设训练集每个样本只有三个维度的特征,记做。首先选择第一个维度的特征,其有诸多取值,取出对应的中位数作为分界线。将所有样本分为两类。因此可以构建一个二叉树;
(2)相当于缩小了训练集的空间,将训练集分到两个孩子结点上。对于每个孩子结点,选择第二个特征,并将对应所有样本在该特征的中位数作为分界线,继续往下划分,以此类推;
(3)直到所有的样本都被划分到独立的一个叶子结点(即每个叶子结点只有一个样本点),构建结束。
kd树将搜索空间缩小,避免计算每个样本点的距离。如何根据kd树来选择最近邻?
(1)给定一个测试集样本 ,首先其根据构建的规则,从根结点向下进行搜索,最终落到对应的一个叶子结点。此时叶子结点所在的样本 可以认为是与当前 的最近邻结点;
(2)显然, 与 的距离是一个阈值,最近邻一定在这个范围内。因此向上递归,计算 与父亲结点的距离,并计算对应兄弟结点的距离,根据距离的比较,选择最近的样本作为最近邻;
(3)以此类推,逐个递归到根结点。
注意的是,如果当前最近邻的范围与kd树划分的区域不重叠时,则不需要进行计算,因此大大降低了计算和搜索空间。
例如,给定一组训练集 , 其可以构建kd树如下所示:
对应的空间划分是:
在搜索过程中,给定一个样本点 ,首先可以判断其落在 对应的叶子结点,计算其与该样本的距离为 。其次向上递归,计算样本 与 的距离为 , 发现距离表小,所以最近邻变为点 。其次在与其另一个孩子结点进行比较,距离为 , 距离再次变小,所以最近邻为 。继续向上递归,发现点 以及不在以 为圆心,为半径的圆范围内,所以根结点的右子树不需要搜索了。