K近邻(K-Nearest Neighbors, KNN)算法既可处理分类问题,也可处理回归问题,其中分类和回归的主要区别在于最后做预测时的决策方式不同。KNN做分类预测时一般采用多数表决法,即训练集里和预测样本特征最近的K个样本,预测结果为里面有最多类别数的类别。KNN做回归预测时一般采用平均法,预测结果为最近的K个样本数据的平均值。其中KNN分类方法的思想对回归方法同样适用,因此本文主要讲解KNN分类问题,下面我们通过一个简单例子来了解下KNN算法流程。 如下图所示,我们想要知道绿色点要被决定赋予哪个类,是红色三角形还是蓝色正方形?我们利用KNN思想,如果假设K=3,选取三个距离最近的类别点,由于红色三角形所占比例为2/3,因此绿色点被赋予红色三角形类别。如果假设K=5,由于蓝色正方形所占比例为3/5,因此绿色点被赋予蓝色正方形类别。
从上面实例,我们可以总结下KNN算法过程
从KNN算法流程中,我们也能够看出KNN算法三个重要特征,即距离度量方式、K值的选取和分类决策规则。
KNN要选取前K个最近的距离点,因此我们就要计算预测点与所有点之间的距离。但如果样本点达到几十万,样本特征有上千,那么KNN暴力计算距离的话,时间成本将会很高。因此暴力计算只适合少量样本的简单模型,那么有没有什么方法适用于大样本数据,有效降低距离计算成本呢?那是当然的,我们下面主要介绍KD树和球树方法。
KD树算法没有一开始就尝试对测试样本进行分类,而是先对训练集建模,建立的模型就是KD树,建立好模型之后再对测试集做预测。KD树就是K个特征维度的树,注意KD树中K和KNN中的K意思不同。KD树中的K代表样本特征的维数,为了防止混淆,后面我们称KD树中特征维数为n。KD树可以有效减少最近邻搜索次数,主要分为建树、搜索最近邻、预测步骤,下面我们对KD树进行详细讲解。
下述为KD树构建步骤,包括寻找划分特征、确定划分点、确定左子空间和右子空间、递归构建KD树。
我们举例来说明KD树构建过程,假如有二维样本6个,分别为{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},KD树过程构建过程如下
当我们生成KD树后,就可以预测测试样本集里面的样本目标点。
为方便理解上述过程,我们利用2.1建立的KD树来寻找(2,4.5)的最近邻。
根据KD树搜索最近邻的方法,我们能够得到第一个最近邻数据点,然后把它置为已选。然后忽略置为已选的样本,重新选择最近邻,这样运行K次,就能得到K个最近邻。如果是KNN分类,根据多数表决法,预测结果为K个最近邻类别中有最多类别数的类别。如果是KNN回归,根据平均法,预测结果为K个最近邻样本输出的平均值。
KD树算法能够提高KNN搜索效率,但在某些时候效率并不高,比如处理不均匀分布的数据集时。如下图所示,如果黑色的实例点离目标点(星点)再远一点,那么虚线会像红线那样扩大,导致与左上方矩形的右下角相交。既然相交那就要检查左上方矩形,而实际上最近的点离目标点(星点)很近,检查左上方矩形区域已是多余。因此KD树把二维平面划分成矩形会带来无效搜索的问题。
为优化超矩形体带来的搜索效率问题,我们在此介绍球树算法来进一步提高最近邻搜索效率。
球树的每个分割块都是超球体,而不像KD树中的超矩形体,这样在做最近邻搜索是可以避免无效搜索,下面我们介绍球树构建过程
KD树在搜索路径优化时使用的是两点之间的距离来判断,而球树使用的是两边之和大于第三边来判断。相对来说球树的判断更加复杂,但却避免一些无效的搜索,下述为球树搜索最近邻过程。
根据球树搜索最近邻的方法,我们能够得到第一个最近邻数据点,然后把它置为已选。然后忽略置为已选的样本,重新选择最近邻,这样运行K次,就能得到K个最近邻。如果是KNN分类,根据多数表决法,预测结果为K个最近邻类别中有最多类别数的类别。如果是KNN回归,根据平均法,预测结果为K个最近邻样本输出的平均值。
有时我们会遇到样本中某个类别数的样本非常少,甚至少于我们实现定义的K,这将导致稀有样本在找K个最近邻的时候会把距离较远的无关样本考虑进来,进而导致预测不准确。为解决此类问题,我们先设定最近邻的一个最大距离,也就是说,我们在一定范围内搜索最近邻,这个距离称为限定半径。
下述代码是利用iris数据进行分类,我们经常需要通过改变参数来让模型达到分类结果,具体参数设置可参考sklearn官方教程。
from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
#load iris data
iris=load_iris()
X=iris.data
y=iris.target
X_train,X_test,y_train,y_test=train_test_split(X,y,test_size=0.3,random_state=1)
knn=KNeighborsClassifier(algorithm='kd_tree')
knn.fit(X_train,y_train)
print(knn.predict(X_test))
# [0 1 1 0 2 1 2 0 0 2 1 0 2 1 1 0 1 1 0 0 1 1 1 0 2 1 0 0 1 2 1 2 1 2 2 0 1
# 0 1 2 2 0 1 2 1]
print(y_test)
# [0 1 1 0 2 1 2 0 0 2 1 0 2 1 1 0 1 1 0 0 1 1 1 0 2 1 0 0 1 2 1 2 1 2 2 0 1
# 0 1 2 2 0 2 2 1]
print(knn.score(X_test,y_test))
# 0.977777777778
参考
刘建平Pinard_K近邻法(KNN)原理小结 Yabea_K-近邻(KNN)算法