机器学习算法系列(17)k 近邻

k 近邻(knn)是一种很简单的分类算法,它的基本原理是:给定一个实例点,然后在所有的数据中找到与该实例点距离最近的 k 个样本,最后选择 k 个样本中出现最多的分类标记作为实例点的分类预测结果。

下面这个视频比较清晰地说明了 knn 是如何工作的:How kNN algorithm works - YouTube

基本的原理很简单,所以它很“懒”,是“懒惰学习”代表,它遗留了两个问题给我们思考:

  1. k 值如何选择?
    • k 值的选择不能过小,否则实例点会对自己周边的点异常敏感,容易过拟合
    • k 值的选取也不能过大,容易产生较大的误差
    • 一般选择一个合适的 k 值,用交叉验证法择优选取
  2. 如何定义实例点与样本点之间的距离
    • 欧式距离
    • $L_p$距离,p=1时为曼哈顿距离
    • 闵可夫斯基(Minkowski) 距离
  3. 如何快速找到实例点距离最近的 k 个样本?

关于问题 3 的回答,kd 树是 knn 的实现算法之一,参考【数学】kd 树算法之详细篇

kd树搜索过程

觉得还不错?赞助一下~
0%