K近邻法(KNN)
k近邻实际上利用训练数据集对特征向量空间进行划分,并作为其分类的”模型”
KNN的三个基本要素:
- k值的选择
- 距离度量
- 分类决策规则
KNN算法
输入:训练数据集
其中$x_i$为实例的特征向量,$y_i$为其输入为实例的类别
输出:实例x所属的类y
(1)根据给定的距离度量,在数据集T中找出与x最近邻的k个点,涵盖这k个点x的邻域记作$N_k(x)$
(2)在$N_k(x)$根据分类决策规则(如多数表决)决定x的类别y：
其中I为指示函数,及当$y_i=c_j$时I为1,否则为0
k近邻没有显式的学习过程.
选择k的技巧:
1)当我们将k值降低到1时,我们的预测会变得不稳定,相反随着k的值的增加,由于多数投票/平均,我们的预测变得更加稳定,因此更有可能做出更准确的预测(直到某一点)。
2)如果标签中进行多数投票,通常会将k设为奇数
算法优缺点:
+算法简单易行
+对异常值不敏感
+适合多分类,KNN要比SVM表现要好
+算法通用,可用于分类、回归和搜索
-随着数据量的增加变得非常慢,这使得在需要快速做出预测的环境中,变成乐意个不切实际的选择.
-可解释性差，无法告诉逆哪个变量更重要
-k值的选择,当数据不平衡时,一个类的样本容量很大,而其他样本容量很小时,该样本的K个邻居中大容量类的样本占多数.
-KNN是一种消极学习方法、懒惰算法
-为获得K近邻,KNN需要暴力搜索,扫描全部训练样本并计算其与待分类样本之间的距离,系统开销很大
Kd树——k近邻算法的实现
Kd树是为了降低KNN的时间复杂度,提升其性能的一种数据结构,是一种二叉树.
构造kd树
kd树是一种对k维空间中的实例点进行存储以便对其进行快速检索的树形结构.kd树是二叉树,表示对k维空间的一个划分.构造kd树相当于不断地用垂直于坐标轴的超平面将k维空间切分,构成一系列的k维超矩形区域.kd树的每个结点对应于一个k维超矩形区域.
构造kd树的方法如下：构造根节点,使根结点对应于k维空间中包含所有实例点的超矩形区域;通过下面的递归方法,不断地对k维空间进行切分,生成子结点.在超矩形区域(结点)上选择一个坐标轴和次坐标轴上地一个切分点,确定一个超平面。这个超平面通过选定地切分点,并垂直于选定地坐标轴,将当前超矩形区域划分为左右两个子区域(子结点);这时实例被分到两个子区域.这个过程直到子区域内没有实例时终止(终止时地结点为叶结点)
通常,依次选择坐标轴对空间切分,选择训练实例点在选定坐标轴上的中位数为切分点,这样得到的kd树是平衡的，平衡地kd树搜索时地效率未必是最优的.
构造平衡kd树
输入:k维空间数据集$T=\{x_1,x_2,…,x_N\}$
其中$x_i=(x_i^{(1)},x_i^{(2)},…,x_i^{(k)})^T$,i=1,2,…,N
(1)开始：构造根节点,根节点对应于含T的k维空间的超矩形区域.选$x^{(1)}$作为坐标轴,以T中所有实例的$x^{(1)}$坐标的中位数为切分点,将根节点对应的超矩形区域划分为两个子区域.切分由通过切分点并与$x^{(1)}$坐标轴垂直的超平面实现,由此分割出的左右两区域分别对应于根节点的左右两个子结点
(2)重复:对深度为j的结点,选择$x^{l}$为切分的坐标轴,l=j(mod k)+1,以该结点的区域中的所有实例的$x^{(l)}$坐标的中位数为切分点,将该结点对应的超矩形区域切分成左右两个子区域分别表示深度为j的该结点的左右子结点
(3)直到两个子区域内没有实例存在时停止,从而形成kd树的区域划分
搜索kd树
可以看到利用kd树可以省去大部分数据点的搜索,从而减少搜索的计算量.
用kd树最近邻搜索
输入:已构造的kd树;目标点x
输出:x的最近邻
(1)在kd树种找出包含目标点x的叶结点:从根节点出发,递归地向下访问kd树.若目标点x当前维的坐标小于切分点的坐标,则移动到左结点否则移动到右结点,直到子结点为叶结点为止
(2)以此结点为”当前最近点”
(3)递归地向上回退,在每个结点进行以下操作:
(a)如果该结点保存地实例点比当前最近点距离目标点更近,则以该实例点为当前最近点
(b)当前最近点一定存在于该结点一个子结点对应的区域.检查该子结点的父结点的另一子结点对应的区域是否有更近的点.即检查另一子结点对应区域是否与以目标点为球心,以目标点与”当前最近点”间的距离为半径的超球体相交;如果相交,可能另一个子结点对用的区域内存在距目标点更近的点,移动到另一个子结点.接着递归地最近邻搜索l;如果不相交，向上回退
(4)当回退到根节点,搜索结束.最后的”当前最近点”即为x的最近邻点.
Kd树搜索的平均计算复杂度是O(logN),这里N是训练实例数,kd树更实用于训练实例数远大于空间维数时的k近邻搜索。当空间维数接近训练实例数时,它的效率会迅速下降,几乎接近线性扫描.