5.1 K近邻算法概述

“橘生淮南则为橘,生于淮北则为枳”出自《晏子春秋·内篇杂下》。原文为“橘生淮南则为橘,生于淮北则为枳,叶徒相似,其实味不同。所以然者何?水土异也。”完整的典故是:齐国的晏子出使楚国,楚王想戏弄他,故意将一个犯人从堂下押过。楚王问:此人犯了什么罪?回答:一个齐国人犯了偷窃罪。楚王就对晏子说,你们齐国人是不是都很喜欢偷东西?晏子回答:淮南有橘又大又甜,一移栽到淮北,就变成了枳,又酸又小,为什么呢?因为土壤不同(见图5-1)。

图5-1 晏子使楚

同样的道理,我们可以理解距离接近的事物具有相同属性的可能性要大于距离相对较远的,这个也是K近邻算法的核心思想。

K近邻(K-Nearest Neighbor,KNN)算法是机器学习领域使用最广泛的算法之一,所谓KNN,就是K个最近的邻居的意思,说的是每个样本都可以用它最接近的K个邻居来代表。KNN算法的核心思想是:如果一个样本在特征空间中的K个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性,KNN原理如图5-2所示。该方法在确定分类决策时,只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。KNN方法在类别决策时,只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别,因此对于类域交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。

图5-2 KNN原理图

KNN常用的算法为:

·Brute Force;

·K-D Tree;

·Ball Tree。