KNN算法基础

KNN算法是机器学习中最好理解的算法之一，属于惰性学习算法的典例。惰性指模型仅通过对训练数据集的记忆功能进行预测，而不产生判别函数。

引申：参数化模型和非参数化模型

机器学习算法可以划分为参数化模型和非参数化模型两大类。使用参数化模型时，需要通过训练估计参数，得到一个模式。常见的参数化模型诸如感知器、逻辑斯蒂回归、SVM等。
非参数化模型无法通过一组固定的参数对样本进行表征，参数的数量会随着训练集样本数量的增加而增加。常见的非参数化模型有决策树、Kernal SVM等。
KNN属于非参数化模型的一个子类，可以被描述为基于实例的学习。这类模型的特点是对训练数据进行记忆，KNN所属的惰性学习是基于实例学习的一个特例。

sklearn中的KNN实现

KNN算法本身很简单，归纳为如下几步：
①选择近邻数量k和距离度量的方法
②找到待分类样本的k个最近邻
③根据最近邻类标进行多数投票
sklearn中已经很好的实现了KNN算法分类器，位于sklearn.neighbors包下的KNeighborsClassifier类中。给出最基本的实现。

from sklearn.model_selection import train_test_split
import sklearn.datasets as dataset
from sklearn.neighbors import KNeighborsClassifier

'''加载数据'''
data = dataset.load_digits()
X = data.data
y = data.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25, random_state=666)

knn_clf = KNeighborsClassifier(n_neighbors=5)
knn_clf.fit(X_train, y_train)
score = knn_clf.score(X_test, y_test)
print('when k chose 5, fit score is : %s' % score)

选用sklearn.datasets的digits数据集，分类器的k近邻数量选用5，这也是默认值，算是经验上分类效果最佳的一个k值。获得如下输出：

when k chose 5, fit score is : 0.9866666666666667

在k选5的情况下，分类器的准确度为98%。

KNN算法的超参数

上面的实现属于最简单的实现，KNN算法因为不生成一个固定参数的模型，因此，在训练过程中的调参的要求非常高。

（一）k值的选择

k值的选择是第一项，一般的根据经验k=5是最能得到最佳效果的点，但在实际开发过程中需要进行验证。

'''最好的k值'''
best_k = -1
best_score = 0.0
for k in range(1, 11):
    knn_clf = KNeighborsClassifier(n_neighbors=k)
    knn_clf.fit(X_train, y_train)
    score = knn_clf.score(X_test, y_test)
    if score > best_score:
        best_score = score
        best_k = k
print("best k is : %s, best_score is : %s\n" % (best_k, best_score))

在之前代码中增加如下代码，使用best_k、best_score记录最佳的k和分类效果，k从1到10中进行选择，使用for循环依次测试。获得结果：

best k is : 5, best_score is : 0.9866666666666667

似乎和刚才是一样的。强调一点，如果在1到10中求得最佳k值为10，那么有必要对10以上的值选择区间再进行测试，因为可能含有效果更好的k值。

（二）考虑距离权重

之前的分类中，仅仅通过找到待分类样本最近的k个样本进行多数投票，但可能存在如下情况

如果按照投票的方式，应该分为蓝色类别，但从距离上看，样本距离红色类别更近，划为红色似乎更加合理，这里就需要引入距离权重的概念。
在KNeighborsClassifier中有一个参数weight，不指定该参数的情况下默认为uniform也就是多数投票，也可以指定weight为distance，即可采用距离权重的方式进行分类。

'''考虑距离权重'''
best_method = ''
best_k = -1
best_score = 0.0
for method in ['uniform', 'distance']:
    for k in range(1, 11):
        knn_clf = KNeighborsClassifier(n_neighbors=k, weights=method)
        knn_clf.fit(X_train, y_train)
        score = knn_clf.score(X_test, y_test)
        if score > best_score:
            best_score = score
            best_k = k
            best_method = method
print('best method is : %s, best k is : %s, best score is : %s\n' % (best_method, best_k, best_score))

增加使用best_method对最佳分类采用的权重方法进行记录。得到输出：

best method is : uniform, best k is : 5, best score is : 0.9866666666666667

似乎又没变。

（三）距离系数p

分类时候使用的距离是什么距离？距离的种类有很多，最常见的有欧氏距离ρ(A，B) =√ [ ∑( a[i] - b[i] )^2 ] (i = 1，2，…，n)，此外还有曼哈顿距离ρ(A，B) =[ ∑( a[i] - b[i] ) ] (i = 1，2，…，n)

如图给出的绿色的直线就是欧式距离，其他的线虽然走法不同但距离是一样的，都是曼哈顿距离。仔细观察下两种距离的公式，可以进一步合并为ρ(A，B) =[ ∑( a[i] - b[i] )^p ]^(1/p) (i = 1，2，…，n)
当p为1时，代入发现是曼哈顿距离，p=2时则是欧氏距离。在sklearn的KNN分类器中，也有p参数，默认值为2即采用欧式距离，这个公式被称为闵可夫斯基距离。训练过程中，还可以实验不同p值的分类效果

'''距离p值'''
best_score = 0.0
best_k = -1
best_p = -1
for k in range(1, 11):
    for p in range(1, 6):
        knn_clf = KNeighborsClassifier(n_neighbors=k, weight='distance', p=p)
        knn_clf.fit(X_train, y_train)
        score = knn_clf.score(X_test, y_test)
        if score > best_score:
            best_score = score
            best_k = k
            best_p = p
print('best k is : %s, best p is : %s, best score is : %s\n' % (best_k, best_p, best_score))

得到结果

best k is : 5, best p is : 2, best score is : 0.9866666666666667

好像欧式距离的效果最好。

网格搜索与KNN超参数

上面的部分中，我们不断通过for循环和定义变量的方式记录最佳分类效果的相应的超参数，sklearn中提供了更简单的实现，位于sklearn.model_selection包下的GridSearchCV类就是对网格搜索的封装，还是刚刚的寻找最佳分类的参数，使用GridSearchCV的方式就变为：

from sklearn.model_selection import train_test_split
import sklearn.datasets as dataset
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import GridSearchCV

'''加载数据'''
data = dataset.load_digits()
X = data.data
y = data.target
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25, random_state=666)

'''网格搜索获取最佳参数'''
grid_params = [
    {
        'weights' : ['uniform'],
        'n_neighbors' : [i for i in range(1, 11)]
    },{
        'weights' : ['distance'],
        'n_neighbors' : [i for i in range(1, 11)],
        'p' : [p for p in range(1, 6)]
    }
]

通过对参数进行封装，装入到grid_params中，作为参数传入到网格当中

'''创建一个KNN分类器，作为网格搜索使用的分类器参数'''
knn_clf = KNeighborsClassifier()
grid_search = GridSearchCV(knn_clf, param_grid=grid_params, n_jobs=-1, verbose=2)
grid_search.fit(X_train, y_train)

创建一个KNN分类器，作为网格搜索使用的分类器参数，再指定之前创建的grid_params，GridSearchCV就可以自动的寻找最佳分类方式。n_jobs是进行搜索时的任务数，可以指定为电脑的核数，-1就是使用全部的核进行搜索，verbose是在搜索过程中打印相关信息，值越高信息越详细，一般2比较常用。

Fitting 3 folds for each of 60 candidates, totalling 180 fits
[CV] n_neighbors=1, weights=uniform ..................................
[CV] n_neighbors=1, weights=uniform ..................................
[CV] n_neighbors=1, weights=uniform ..................................
[CV] n_neighbors=2, weights=uniform ..................................
[CV] ................... n_neighbors=1, weights=uniform, total=   0.0s
[CV] ................... n_neighbors=1, weights=uniform, total=   0.1s
[CV] n_neighbors=2, weights=uniform ..................................
[CV] ................... n_neighbors=1, weights=uniform, total=   0.1s
......

verbose的作用就是在搜索过程中打印如下信息，注意第一行60 candidates，回头看grid_params中weight选用uniform时，需要对k从1到10进行测试，而weights选用distance时，对k从1到10和p从1到5进行测试，一共需要进行110 + 510 = 60项测试，对应了candidates的值。
打印得到的最佳分类模式

print('best estimator is :')
print(grid_search.best_estimator_)
print('best score is %s:' % grid_search.best_score_)
# knn_clf = grid_search.best_estimator_
# score = knn_clf.score(X_test, y_test)
print("test by KNN Classifier's score() function, the score is : %s" % score)

输出

best estimator is :
KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
           metric_params=None, n_jobs=1, n_neighbors=5, p=3,
           weights='distance')
best score is 0.9866369710467706:
test by KNN Classifier's score() function, the score is : 0.9822222222222222

可以看到best_estimator_其实是一个KNeighborsClassifier对象，这里得到的是使用距离权重，p值为3和n_neighbors为5的分类器，通过网格搜索测试的best_score_为0.9866369710467706，不如之前自己实现的0.9866666666666667，原因是使用GridSearchCV的打分机制和分类器的机制不一样，更为复杂，因此分数也就不同。之后使用X_test和y_test测试待预测样本的准确度为0.9822222222222222。
获得的最佳KNeighborsClassifier中还有个属性是metric，目前对应的值是minkowski就是之前讲过的闵可夫斯基距离。此外还有些距离，作为扩展给出，可以参考sklearn手册sklearn.neighbors包下的DistanceMetric。

KNN解回归问题

在sklearn.neighbors包下还有KNeighborsRegressor用KNN算法解决回归问题，其思路基本上和解分类问题一样，但回归问题是需要求出一个具体的值，求值可能采用最近k个点的值的均值、或者考虑上距离的权重等方式。API和KNeighborsClassifier非常相似，这里不做讲解。

KNN算法的缺点

最大的缺点就是效率低，假如一个数据集有m个样本n中特征，则预测一个样本的时间复杂度为O(mn)，即需要和m个样本求距离并挑选前k个，每个特征维度都需要计算距离，故需要O(mn)。可以使用树结构优化，如KD-Tree、Ball-Tree等。
缺点二：高度数据相关
缺点三：预测不具有可解释性
缺点四：维数灾难
随着维数增加，看似很近的两个点距离越来越大。

维数    坐标1    坐标2    距离
1        0        1       1
2      （0,0）  (1, 1)   1.414
3       (0,0,0) (1,1,1)  1.73
...               

维数灾难可以用降维的方式进行优化。