KNN是一种基本分类与回归方法,本篇只总结分类问题中的KNN。
- 输入:样本的特征向量,对应于特征空间中的点
- 输出:样本的类别,可取多类
- 算法思想:给定一个样本类别已知的训练数据集,对于新样本,根据其K个最近邻训练样本的类别,通过多数表决等方式进行类别预测。(不具有显式的学习过程) 实际是利用训练数据集对特征向量空间划分,并将其作为其分类的“模型”
- 三个基本要素(当三个要素确定后,结果唯一确定):
- K值的选择(交叉验证法):K太小,整体模型会变得复杂,易过拟合;K太大,模型太简单。
- 距离度量(常用欧氏距离、常用Lp、曼哈顿距离、Minkowski):特征空间中两个样本的距离是两个样本相似程度的反映
- 分类决策规则【多数表决规则,(加权)投票法】; 回归问题【(加权)平均法】
- kd树(kd tree)
- 存储K维空间数据的结构,以便快速检索
- 二叉树,表示对k维空间的一个划分,每个结点对应于k维空间划分中的一个超矩形区域
- 更适用于训练样本远大于空间维数时的K近邻搜索,当空间维数接近训练样本数时,效率迅速下降,几乎接近线性扫描
- N为训练样本数时,复杂度O(logN)