机器学习 -- 简析KNN(k近邻算法)
3. 分类规则(Classification decision rule)
一、引入
可用于分类(二分类/多分类)或者回归,属于监督学习方法
1. 思想
给定测试样本,基于某种距离度量找出训练集中与其最靠近的k个训练样本,然后基于这k个“邻居”的信息采用“投票”的方法对测试样本进行预测。
由于该算法没有显示的学习过程,它是一种“懒惰学习”,即在学习阶段仅仅是把样本保存起来,训练时间的开销为零,待收到测试样本后再进行处理。
因此该算法没有显示的学习过程,大多时间都花在测试阶段。
过程描述:加入一个新样例?需要找距离?最近的一个样本,上图显示了k=1以及k=7的情况。
因此可见本方法重要的有三点:1.距离distance 2.k的选 3.决策规则
二、KNN算法
1. 文字描述
给定一个带标签的训练集,对于没有标签的新数据:
比较新数据与样本集数据的每个特征;
提取样本集中最相似数据(最近邻)的类标签;
一般情况下,只选择样本数据集中最相似的前k个数据,并且选择k中出现次数最多的类别作为新数据的类。
2. 算法过程
输入:有标签的样例
输出:新样例的预测标签
(1)对于给定的距离,找到预测样本的k个最近的邻居,放入到Nk(x)中
(2)在Nk(x)中依据分类规则(如投票)判断新样例的预测类型
3. 算法优缺点
优点:
(1)算法简单,理论成熟,可用于分类和回归。
(2)对异常值不敏感。
(3)可用于非线性分类。
(4)比较适用于容量较大的训练数据,容量较小的训练数据则很容易出现误分类情况。
(5)KNN算法原理是根据邻域的K个样本来确定输出类别,因此对于不同类的样本集有交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为合适。
(6)对数据类型(图片,文本,视频)不做限制
缺点:
(1)时间复杂度和空间复杂度高。(训练复杂度为0,但测试耗时,需要计算很多距离,还要相应存储,再选出最小的k个距离)
(2)训练样本不平衡,对稀有类别的预测准确率低。
(3)相比决策树模型,KNN模型可解释性不强。
三、KNN模型
k近邻模型对应一个特征空间划分。每个样例是最小的单元,对应一个类别。
要点:
(1)距离度量Distance metric
(2)k值的选择Choice of k value
(3)分类规则Classification decision rule
1. 距离度量(Distance metric)
Lp距离: xi是n维空间向量,其距离就是对应分量相减的p次方之和再开平方。
当p=2 欧几里得距离
当p=1 曼哈顿距离
当p=无穷大 切比雪夫距离
三者之间的关系
2. k值的选择(Choice of k value)
如果选择较小的k值: “学习”的近似误差减小,而“学习”的估计误差增大。噪声敏感,k值的降低意味着整个模型变得复杂,容易出现过拟合。
如果选择较大的K值: 减少学习的估计误差,但缺点是学习的近似误差会增大.K值的增大 就意味着整体的模型变得简单.
选择方法:交叉验证法
3. 分类规则(Classification decision rule)
多数投票规则
四、总结
1.KNN算法分类是由附近某种数量最多的样本类别决定的
2.KNN算法属于监督学习
3.KNN算法中k大小需要选择(交叉验证法)
4.KNN算法是有缺陷的