机器学习算法之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）