K近邻算法

K近邻算法全名为k-nearest neighbor,简称KNN，是一种思想非常简单的监督学习方法。 其核心思想就是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性。

也就是说给定有label的训练样本，新的待分类样本需要计算与所有训练样本的距离，然后排序选择最近的K个样本，这K个样本属于哪个类别的多，那么此待分类样本就属于哪个类别。如果用公式表示的话，就如下所示：

y=argmaxcj∑xi∈Nk(x)I(yi=cj)i=1,2,...N;j=1,2,K y = a r g m a x c j ∑ x i ∈ N k ( x ) I ( y i = c j ) i = 1 , 2 , . . . N ; j = 1 , 2 , K 。其中 Nk(x) N k ( x ) 表示x的邻域

优缺点

优点： 简单，简单，简单

缺点：计算量大，需要计算与所有训练数据的距离；K值的选取需要根据经验判断

KNN算法的3个要素

K值的选择

距离度量函数的选择

分类决策规则

其中K值的选择需要根据经验来判断，如果为1的话，就是最近邻算法。而距离函数一般选择的是欧氏距离。而决策规则一般是多数表决，也就是K个样本属于哪个类别的多，那么此待分类样本就属于哪个类别。

后续发展

因为KNN算法存在比较多的问题，所以后续人们对其进行了一些优化，主要有：

kd树，这个是为了提高搜索效率的

为了优化分类效果，提出了距离加权值（和该样本距离小的邻居权值大）的算法以及针对不同的相邻样本，动态选择不同的k值的算法。