机器学习算法之K近邻算法(KNN)

 机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有的知识结构使之不断改善自身的性能。它是人工智能的核心,是使计算机具有智能的根本途径,其应用遍及人工智能的各个领域,它主要使用归纳、综合而不是演绎。人工智能之机器学习主要有三大类:1)分类;2)回归;3)聚类。今天我们重点探讨一下K近邻(KNN)算法。

 
K近邻KNN(k-Nearest Neighbor)算法,也叫K最近邻算法,1968年由 Cover 和 Hart 提出,是机器学习算法中比较成熟的算法之一。K近邻算法使用的模型实际上对应于对特征空间的划分。KNN算法不仅可以用于分类,还可以用于回归。
机器学习算法之K近邻算法(KNN)
KNN概念:
 
K近邻算法KNN就是给定一个训练数据集,对新的输入实例,在训练数据集中找到与该实例最邻近的K个实例(K个邻居),这K个实例的多数属于某个类,就把该输入实例分类到这个类中。
 
如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。K近邻算法使用的模型实际上对应于对特征空间的划分。
 
通俗地讲,就是“物以类聚,人以群分”。
 
分类策略,就是“少数从属于多数”。
机器学习算法之K近邻算法(KNN)
算法描述:
 
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:
 
人工智能之K近邻算法(KNN)
机器学习算法之K近邻算法(KNN)