k-近邻算法

算法简介

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

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

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

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

To be continued…