k近邻(KNN)复习总结

时间:2023-06-30 09:19:38

摘要:

  1.算法概述

  2.算法推导

  3.算法特性及优缺点

  4.注意事项

  5.实现和具体例子

  6.适用场合
内容:

1.算法概述

  K近邻算法是一种基本分类和回归方法;分类时,根据其K个最近邻的训练实例的类别,通过多数表决等方式进行预测;k近邻法实际上利用训练数据集对特征向量空间进行划分,并作为其分类的"模型"(Cover和Hart 在1968)--参考自《统计学习方法》

  回归是根据k个最近邻预测值计算的平均值--参考自scikit-learn官网

2.算法推导

2.1 kNN三要素

  k值的选择:当k值较小时,预测结果对近邻的实例点非常敏感,容易发生过拟合;如果k值过大模型会倾向大类,容易欠拟合;通常k是不大于20的整数(参考《机器学习实战》)

  距离度量:不同距离度量所确定的最近邻点是不同的

  分类决策规则:多数表决(majority voting)规则是在损失函数是0-1损失函数时的经验风险最小化

2.2 KD树:解决对k近邻进行快速搜索的一种二叉树,构造kd树相当于不断用垂直于坐标轴的超平面对特征空间进行划分,最终构成一系列的K维超矩阵区域;每一个节点对应于一个k维超矩形区域。一般情况下顺序选择坐标轴及坐标轴的中位数(下图中取的最中间两个数较大的一个数)进行切分。kd树是平衡的但效率未必最优--参考自《统计学习方法》

KD树只在小于等于20维的数据集上可以快速搜索,但是当维数增长时效率降低  

如下图对T = {(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}建立kd树的结果:

  k近邻(KNN)复习总结

2.3 ball tree:解决高维空间下kd树失效的一种树形结构;Ball树根据质心C和半径r对数据进行递归的划分,每一个数据点都会被划分到一个特定的质心C和半径r的的超球体里面,在搜索的时候,候选的点会使用|x+y| <= |x| + |y|进行筛选(papers:“Five balltree construction algorithms” 

  如下图是显示了一个2维平面包含16个观测实例的图(参考自):

  k近邻(KNN)复习总结

3.算法特性及优缺点

  优点:精度高,对异常值不敏感

  缺点:k值敏感,空间复杂度高(需要保存全部数据),时间复杂度高(平均O(logM),M是训练集样本数)

4.注意事项

  归一化:基于距离的函数,要进行归一化;否则可能造成距离计算失效

5.实现和具体例子

  构建KD树并使用KD树进行最近邻搜索(《统计学习方法》算法3.2和3.3)

  机器学习实战中的提高约会网站配对指数和手写识别的例子(numpy实现,未使用KD树)

  scikit-learn使用KNN进行分类的例子(分类决策上可以加大邻近点的权重);

  ball tree 实现的例子(有时间研究下)

6.适用场合

  是否支持大规模数据:单机下时间和空间消耗大,不过可以通过分布式解决(github上找到的一个spark knn实现,有时间研究下)

  特征维度

  是否有 Online 算法:有

  特征处理:支持数值型数据,类别型类型需要进行0-1编码