K最近邻(k-nearest neighbors,简写为k-nn)是一种简单而经典的聚类方法.该方法只需查看周围点的类别信息,并且假设所有样本都属于已知的类别.

(1)k-nn算法机制

k-nn有多种实现方式,本章我们会使用半监督(semi supervised)方式,我们有一个训练集,它已经有了类别信息,随后我们猜测非定样本所该具有的类别信息.

我们可以看到算法的步骤分解,可以通过以下步骤概括:

1))设定训练集的数据类别信息

2))然后读取下一个要分类的样本,并计算新样本到训练集每个样本的欧几里得距离

3))同欧几里得距离上最近的样本来确定新样本的类别信息,确定的方式就是最近的k个样本的投票

4))重复以上步骤,直到所有测试样本都确定了类别

2.k-nn的优点和缺点

简单

无训练过程

计算成本高