k-近邻算法

算法简介

翻阅过不少机器学习相关书籍的目录，基本上都会将「分类」作为前一两章进行介绍。而分类算法中，最成熟也是最容易上手的算法当属 k - 近邻算法（kNN）。

它的工作原理是：存在一个样本数据集合，也称作训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前 k 个最相似的数据，这就是 k- 近邻算法中 k 的出处，通常 k 是不大于 20 的整数。最后，选择 k 个最相似数据中出现次数最多的分类，作为新数据的分类。

一般情况下，数据间的相似程度通常使用欧氏距离进行度量，但这只适用于连续变量，在文本分类这种离散变量情况下，海明距离会更加常用。针对不同的场景设计度量算法，可以显著提高 kNN 的精度。

可能看了上面的描述，还是对这个算法不够清晰，举个例子：在一个三维空间中，有分类为 A 和 B 的两堆数据点，现在要采用 kNN 算法对一个新的数据点 X（坐标已知）进行分类，那么需要先依次计算原有数据点和 X 的空间距离，距离越小则表明相似程度越大，将计算出来的数据按相似程度降序排序，统计前 k 个数据点中分类出现次数最多的，作为 X 的分类。

To be continued…