人工智能之K近邻算法(KNN)
前言:人工智能机器学习有关算法内容,请参见公众号“科技优化生活”之前相关文章。人工智能之机器学习主要有三大类:1)分类;2)回归;3)聚类。今天我们重点探讨一下K近邻(KNN)算法。 ^_^
K近邻KNN(k-Nearest Neighbor)算法,也叫K最近邻算法,1968年由 Cover 和 Hart 提出,是机器学习算法中比较成熟的算法之一。K近邻算法使用的模型实际上对应于对特征空间的划分。KNN算法不仅可以用于分类,还可以用于回归。
KNN概念:
K近邻算法KNN就是给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的K个实例(K个邻居),这K个实例的多数属于某个类,就把该输入实例分类到这个类中。
如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。K近邻算法使用的模型实际上对应于对特征空间的划分。
通俗地讲,就是“物以类聚,人以群分”。
分类策略,就是“少数从属于多数”。
算法描述:
KNN没有显示的训练过程,在测试时,计算测试样本和所有训练样本的距离,根据最近的K个训练样本的类别,通过多数投票的方式进行预测。具体算法描述如下:
输入:训练数据集T={(x1,y1),(x2,y2),...,(xn,yn)},其中xi∈Rn,yi∈{c1,c2,...,cK}和测试数据x
输出:实例x所属的类别
1) 根据给定的距离度量,在训练集T中找到与x距离最近的k个样本,涵盖这k个点的x的邻域记作Nk(x)。
2)在Nk(x)中根据分类规则(如多数表决)确定x的类别y:
核心思想:
当无法判定当前待分类点是从属于已知分类中的哪一类时,依据统计学的理论看它所处的位置特征,衡量它周围邻居的权重,而把它归为到权重更大的那一类中。
kNN的输入是测试数据和训练样本数据集,输出是测试样本的类别。
KNN算法中,所选择的邻居都是已经正确分类的对象。KNN算法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
算法要素:
KNN 算法有3个基本要素:
1)K值的选择:K值的选择会对算法的结果产生重大影响。K值较小意味着只有与输入实例较近的训练实例才会对预测结果起作用,但容易发生过拟合;如果 K 值较大,优点是可以减少学习的估计误差,但缺点是学习的近似误差增大,这时与输入实例较远的训练实例也会对预测起作用,使预测发生错误。在实际应用中,K 值一般选择一个较小的数值,通常采用交叉验证的方法来选择最优的 K 值。随着训练实例数目趋向于无穷和 K=1 时,误差率不会超过贝叶斯误差率的2倍,如果K也趋向于无穷,则误差率趋向于贝叶斯误差率。
2)距离度量:距离度量一般采用 Lp 距离,当p=2时,即为欧氏距离,在度量之前,应该将每个属性的值规范化,这样有助于防止具有较大初始值域的属性比具有较小初始值域的属性的权重过大。
对于文本分类来说,使用余弦(cosine)来计算相似度就比欧式(Euclidean)距离更合适。
3)分类决策规则:该算法中的分类决策规则往往是多数表决,即由输入实例的K个最临近的训练实例中的多数类决定输入实例的类别。
算法流程:
1)准备数据,对数据进行预处理。
2)选用合适的数据结构存储训练数据和测试元组。
3)设定参数,如K。
4)维护一个距离由大到小的优先级队列(长度为K),用于存储最近邻训练元组。随机从训练元组中选取K个元组作为初始的最近邻元组,分别计算测试元组到这K个元组的距离,将训练元组标号和距离存入优先级队列。
5)遍历训练元组集,计算当前训练元组与测试元组的距离,将所得距离L与优先级队列中的最大距离Lmax。
6)进行比较。若L>=Lmax,则舍弃该元组,遍历下一个元组。若L
7)遍历完毕,计算优先级队列中K个元组的多数类,并将其作为测试元组的类别。
8)测试元组集测试完毕后计算误差率,继续设定不同的K值重新进行训练,最后取误差率最小的K值。
算法优点:
1)KNN从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关。
2)由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。
3)算法本身简单有效,精度高,对异常值不敏感,易于实现,无需估计参数,分类器不需要使用训练集进行训练,训练时间复杂度为0。
4)KNN 分类的计算复杂度和训练集中的文档数目成正比,即,如果训练集中文档总数为n,那么KNN的分类时间复杂度为O(n)。
5)适合对稀有事件进行分类。
6)特别适合于多分类问题(multi-modal),对象具有多个类别标签,kNN比SVM的表现要好。
算法缺点:
1)当样本不平衡时,样本数量并不能影响运行结果。
2)算法计算量较大;
3)可理解性差,无法给出像决策树那样的规则。
改进策略:
KNN算法因其提出时间较早,随着其他技术的不断更新和完善,KNN算法逐渐显示出诸多不足之处,因此许多KNN算法的改进算法也应运而生。算法改进目标主要朝着分类效率和分类效果两个方向。
改进1:通过找出一个样本的k个最近邻居,将这些邻居的属性的平均值赋给该样本,就可以得到该样本的属性。
改进2:将不同距离的邻居对该样本产生的影响给予不同的权值(weight),如权值与距离成反比(1/d),即和该样本距离小的邻居权值大,称为可调整权重的K最近邻居法WAKNN(weighted adjusted K nearestneighbor)。但WAKNN会造成计算量增大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。
改进3:事先对已知样本点进行剪辑(editing技术),事先去除(condensing技术)对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。
考虑因素:
实现 K 近邻算法时,主要考虑的因素是如何对训练数据进行快速 K 近邻搜索,这在特征空间维数大及训练数据容量大时是非常必要的。
应用场景:
K 近邻算法应用场景包括机器学习、字符识别、文本分类、图像识别等领域。
结语:
K近邻算法KNN,也叫K最近邻算法,是机器学习研究的一个活跃领域。最简单的暴力算法,比较适合小数据样本。K近邻算法使用的模型实际上对应于对特征空间的划分。KNN算法不仅可以用于分类,还可以用于回归。KNN算法在人工智能之机器学习、字符识别、文本分类、图像识别等领域有着广泛应用。
关键词: 人工智能
您可能也感兴趣:
为您推荐
保险业协会将围绕七方面加强消保工作力度 提升行业整体水平
保险公司推出“电信诈骗险” 市民仍须提高防骗意识
天津:做好失业保险稳岗返还工作 实行“免申即享”经办模式
排行
最近更新
- 人工智能之K近邻算法(KNN)
- 傅里叶红外光谱仪基本原理和特点
- 重庆交巡警发布2022年清明节出行安全指南
- 无证驾驶未年检车 细查之下“一身毛病”
- 周溪乡“清明踏青”特色文化体验路线出炉!快去打卡吧!
- 渝中警方发布清明假期出行提示 市民请注意规划路线
- 渝北交巡警发布清明期间道路交通出行预测
- 走进内蒙扎赉特旗兴华嘎查村
- 党建引领助推安全生产
- 官宣:容声冰箱入驻国内顶流综艺《向往的生活》
- “金三银四”变“铜三铁四”?长三角楼市“小阳春”或迟到
- 大众汽车采取更加聚焦中国的采购战略 全球转型再添新动能
- 四部委拟修改规定 支持企业依法依规赴境外上市
- 百强房企盈利能力续降,告别“举债扩张”后如何寻找新模式?
- 安徽建工拟发行5亿元超短期融资券,用于偿债
- 太原国有投资拟发行10亿元中期票据,期限为5年
- 厦门安居集团30亿元私募债项目获上交所受理
- 澎湃新闻发行首款原创动画视频数字藏品
- 用炼油残渣造车?新工艺将其转化为轻质碳纤维 成本更低
- 神经性皮炎怎么治疗 4种治疗方法将皮炎拒之门外
- 乳腺炎怎么治疗 5种消炎方法让乳房恢复健康
- 胃胀气怎么调理 这3种消气方法快速击退胃胀气
- 嘴唇起皮怎么缓解 用这几招能轻松解决嘴唇起皮
- 中药材一体化产业链优势凸显 振东制药2021年归母净利同比大增899%
- 世界自闭症关注日 正确拥抱来自星星的孩子
- 巴斯夫预警天然气减供影响,国内供需均受疫情扰动
- 餐饮业发展机遇在于数字化 杨伟琳:或可让跨界玩家引领
- 伍家医保管好用好省好群众治病钱
- 「食品安全与标准」清明节健康提示:清明期间谨防食源性疾病...
- 商洛市医保慢特病服务平台正式上线