K-近邻算法

k-近邻(KNN K-Nearest-Neighbor)
knn的输入为样本的特征向量，对应其在特征空间的点；输出为类别。

KNN原理

  • 1.假设有一个带标签的样本数据集(训练样本集)，其中包含每条数据与所属分类的对应关系。
  • 2.输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较。
    • i.计算新数据与样本数据集中每条数据的距离 计算距离的方式 有很多 这里可以和RAG联系起来 (通常有欧式距离 还可以是minkowski距离或者曼哈顿距离。)
    • ii.对求得的所有距离进行排序(从小到大，越小表示越相似)
    • iii.取前k个样本数据对应的分类标签

KNN算法特点

精度高，对异常值不敏感
缺点：计算复杂度高，空间复杂度高
适用范围：数值型和标称型

小结

  • 如何选择合适对k值？
    • k值小对时候，近似误差小，估计误差大。k值大 近似误差大，估计误差小。
    • 太大太小都不好，可以使用交叉验证(cross validation)来选取合适的k值。(就是挨个试)

实现算法

  • Brute Force 暴力搜索/线性扫描
  • KD Tree 使用二叉树根据数据维度来平分参数空间
  • Ball Tree 使用一系列的超球体来平分训练数据集
  • 树结构的算法都有建树和查询两个过程