1.kNN算法的思想:给定一个训练数据集,对新的输入实例,在训练集中找到与该实例最近邻的k个实例,这k个实例的多数属于某类,就把输入实例分为这个类。
2.算法
(1)根据给定的距离度量,在训练集T中找出与实例x最邻近的k个点,涵盖着k个点的邻域记做;
(2)在中根据分类决策规则(如多数表决)决定x的类别y:
其中,I为指示函数,即当yi=cj时I为1,否则为0。
距离度量一般是Lp距离或者是Minkowski距离。
xi,xj的Lp距离定义为:
这里p≥1,当p=2时,称为欧氏距离;当p=1时,称为曼哈顿距离。
3.关于k的选择
若k较小,就相当于用较小的邻域中的训练实例进行预测,容易发生过拟合。
若k较大,就相当于用较大的邻域中的训练实例进行预测,优点是可以减小学习的估计误差,但是学习的近似误差就会增大,而且k较大,较远邻域的不相干点也会起预测作用,使预测发生偏差。
4.KNN模型优缺点
优点:(1)思想简单,可分类可回归
(2)可用于非线性分类
(3)精度高,对异常值不敏感
缺点:(1)计算复杂度高
(2)需要大量内存
(3)样本非平衡问题
5.一些要注意的地方
在求距离度量的时候,可能会遇到其中某一项数据远大于另外一项数据,到时候可以按归一化处理。