初步学习k-NN算法以及使用GridSearchCV进行调参

墨蓝 2022-11-27 00:55 173阅读 0赞

## k最近邻算法 (k-NN) ##

k最近邻 (k-Nearst Neighbor, k-NN) 算法是一种比较简单易懂的机器学习算法，1968年由Cover和Hart提出，常应用于字符识别、文本分类、图像识别等领域。该算法的思想是：一个样本与数据集中的`k`个样本最相似，如果这`k`个样本中的大多数属于某一个类别，则该样本也属于这个类别。  
  在`sklearn`库中，k-NN包含在`sklearn.neighbors`中，有k最近邻分类`KNeighborsClassifier`和k最近邻回归`KNeighborsRegressor`。本文以k-NN分类器为例进行学习。  
  `sklearn`库中的k-NN方法有很多超参数，常用的超参数如下：  
  1. `weights`：用于分配权重。基本的最近邻回归使用统一的权重，即本地邻域内的每个邻点对查询点的分类贡献一致。在某些环境下，对邻点加权可能是有利的，使得附近点对于回归所作出的贡献多于远处点。默认为`weights = 'uniform'`，表示为所有点分配同等权重。`weights = 'distance'`表示分配的权重与查询点距离呈反比。此外，我们还可以自定义一个距离函数用来计算权重。  
  2. `n_neighbors`：邻居个数。  
  3. `p`：`p`参数只有在`weights = 'distance'`时才有。`p`是一个大于或等于1的值。`p = 1`表示曼哈顿距离 (Manhattan Distance)，`p = 2`表示欧式距离 (Euclidean Distance)，`p = ∞`表示它是各个坐标距离的最大值。  
  下面介绍一下三种距离计算公式。设特征空间 X \\mathcal\{X\} X是 n n n维实数向量空间 R n R\_\{n\} Rn， x i , x j ∈ X x\_\{i\},x\_\{j\}\\in\\mathcal\{X\} xi,xj∈X， x i = ( x i ( 1 ) , x i ( 2 ) , . . . , x i ( n ) ) T x\_\{i\}=(x\_\{i\}^\{(1)\},x\_\{i\}^\{(2)\},...,x\_\{i\}^\{(n)\})^\{T\} xi=(xi(1),xi(2),...,xi(n))T， x j = ( x j ( 1 ) , x j ( 2 ) , . . . , x j ( n ) ) T x\_\{j\}=(x\_\{j\}^\{(1)\},x\_\{j\}^\{(2)\},...,x\_\{j\}^\{(n)\})^\{T\} xj=(xj(1),xj(2),...,xj(n))T， x i , x j x\_\{i\},x\_\{j\} xi,xj的 L p L\_\{p\} Lp距离定义为 L p ( x i , x j ) = ( ∑ l = 1 n    ∣ x i ( l ) − x j ( l ) ∣ p ) 1 p . L\_p(x\_i,x\_j) = (\\sum\_\{l=1\}^\{n\} \\; |x\_i^\{(l)\}-x\_j^\{(l)\}|^p)^\{\\frac\{1\}\{p\}\}. Lp(xi,xj)=(l=1∑n∣xi(l)−xj(l)∣p)p1.上式中 p ≥ 1 p\\geq1 p≥1. 当 p = 1 p=1 p=1时，称为曼哈顿距离，此时 L 1 ( x i , x j ) = ∑ l = 1 n ∣ x i ( l ) − x j ( l ) ∣ . L\_1(x\_i,x\_j)= \\sum\_\{l=1\}^\{n\} |x\_i^\{(l)\}-x\_j^\{(l)\}|. L1(xi,xj)=l=1∑n∣xi(l)−xj(l)∣.当 p = 2 p=2 p=2时，称为欧式距离，此时 L 2 ( x i , x j ) = ( ∑ l = 1 n    ∣ x i ( l ) − x j ( l ) ∣ 2 ) 1 2 . L\_2(x\_i,x\_j) = (\\sum\_\{l=1\}^\{n\} \\; |x\_i^\{(l)\}-x\_j^\{(l)\}|^\{2\})^\{\\frac\{1\}\{2\}\}. L2(xi,xj)=(l=1∑n∣xi(l)−xj(l)∣2)21.当 p = ∞ p=\\infty p=∞时，表示各个坐标距离的最大值，此时 L ∞ ( x i , x j ) = m a x l    ∣ x i ( l ) − x j ( l ) ∣ . L\_\{\\infty\}(x\_i,x\_j)= \\mathop\{max\}\_l \\; |x\_i^\{(l)\}-x\_j^\{(l)\}|. L∞(xi,xj)=maxl∣xi(l)−xj(l)∣.  
  接下来简单说明一下k-NN的算法流程。输入训练数据集 T = ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) , T=(x\_\{1\},y\_\{1\}),(x\_\{2\},y\_\{2\}),...,(x\_\{N\},y\_\{N\}), T=(x1,y1),(x2,y2),...,(xN,yN),其中 x i ∈ X ⊆ R n x\_\{i\}\\in\\mathcal\{X\}\\subseteq R^\{n\} xi∈X⊆Rn为实例的特征向量， y i ∈ Y = \{ c 1 , c 2 , . . . , c k \} y\_\{i\}\\in\\mathcal\{Y\}=\\\{c\_1,c\_2,...,c\_k\\\} yi∈Y=\{ c1,c2,...,ck\}为实例的类别， i = 1 , 2 , . . . , N i=1,2,...,N i=1,2,...,N；实例特征向量 x x x.  
  1. 根据给点的距离度量，在训练集 T T T中找出与 x x x最近邻的 k k k个点，涵盖着 k k k个点的领域，记为 N k ( x ) N\_k(x) Nk(x).  
  2. 在 N k ( x ) N\_k(x) Nk(x)中根据分类决策规则（如多数表决），决定 x x x的类别 y y y： y = a r g    m a x c j ∑ x i ∈ N k ( x )    I ( y i = c j ) , i = 1 , 2 , . . . , N ; y=arg \\mathop\{\\; max\}\_\{c\_j\} \{\\sum\}\_\{x\_i \\in N\_k(x)\} \\; I(y\_i=c\_j) , i=1,2,...,N; y=argmaxcj∑xi∈Nk(x)I(yi=cj),i=1,2,...,N;在上式中， I I I为指示函数，即当 y i = c j y\_i=c\_j yi=cj时， I I I为 1 1 1，否则 I I I为 0 0 0.  
  最后输出实例 x x x所属的类 y y y.  
  k-NN的特殊情况是`k=1`的情形，称为最近邻算法。对于输入的实例点（特征向量） x x x，最近邻算法将训练数据集中与 x x x最近邻点的类作为 x x x的类。

## GridSearchCV调参 ##

`GridSearchCV`包含在`sklearn.model_selection`中。它可以拆分为“GridSearch”和“CV”两个部分，即网格搜索和交叉验证。网格搜索用于选取模型的最优超参数。获取最优超参数的方式可以绘制验证曲线，但是验证曲线只能每次获取一个最优超参数。如果多个超参数有很多排列组合的话，就可以使用网格搜索寻求最优超参数的组合。网格搜索针对超参数组合列表中的每一个组合，实例化给定的模型，进行交叉验证，将平均得分最高的超参数组合作为最佳的选择，返回模型对象。

GridSearchCV(estimator, param_grid, scoring=None, fit_params=None, n_jobs=1, iid=True,
                 refit=True, cv=None, verbose=0, pre_dispatch='2*n_jobs', error_score='raise',
                 return_train_score=True)

以下是`GridSearchCV`方法中常用的超参数。  
  1. `estimator`：创建的算法对象。  
  2. `param_grid`：值为字典或者列表，需要最优化的参数的取值。  
  3. `scoring`：准确度评价标准，默认`None`,这时需要使用`score`函数；或者如`scoring='roc_auc'`，根据所选模型不同，评价准则不同。字符串（函数名）或是可调用对象，需要其函数签名，形如`scorer(estimator, X, y)`；如果是`None`，则使用`estimator`的误差估计函数。  
  4. `n_jobs`：并行数，默认为`1`，`n_jobs = -1`表示跟CPU核数一致。  
  5. `cv`：交叉验证参数，默认`None`，使用三折交叉验证。指定`fold`数量，默认为`3`，也可以是`yield`训练或测试数据的生成器。  
  6. `verbose`：日志冗长度。`verbose = 0`表示不输出训练过程，`verbose = 1`表示偶尔输出，`verbose > 1`表示对每个子模型都输出。  
  `GridSearchCV`还内置了一些属性。  
  1. `best_estimator_`：效果最好的分类器。  
  2. `best_score_`：成员提供优化过程期间观察到的最好的评分。  
  3. `best_params_`：描述了已取得最佳结果的参数的组合。  
  4. `best_index_`：对应于最佳候选参数设置的索引（`cv_results_`数组的索引）。

## 优化Titanic生存预测代码 ##

在上一篇博客中，我使用决策树和k-NN两种分类器对处理后的Titanic数据集进行了分类预测，其中k-NN分类器的training set score为0.82，test set score为0.72，还有一部分优化空间。下面用网格搜索和交叉验证进行调参。

# 使用GridSearchCV进行调参
    from sklearn.model_selection import GridSearchCV
    
    knn = KNeighborsClassifier()
    param_grid = [
        { 
            'weights': ['uniform'],
            'n_neighbors': [i for i in range(1, 11)]
        },
        { 
            'weights': ['distance'],
            'n_neighbors': [i for i in range(1, 11)],
            'p': [i for i in range(1, 6)]
        }
    ]
    grid_search = GridSearchCV(knn, param_grid, n_jobs=-1, verbose=2)

%%time
    grid_search.fit(X_train, y_train)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70]  
  接下来查看一下`GridSearchCV`的属性。

# 最优超参数组合对应的分类器
    grid_search.best_estimator_

![在这里插入图片描述][20200813094320266.png]

# 最优超参数组合
    grid_search.best_params_

![在这里插入图片描述][20200813094348781.png]

# 最优超参数组合对应的准确率
    grid_search.best_score_

![在这里插入图片描述][20200813094444403.png]

最后我们使用最优的分类器模型对测试集进行预测。

knn = grid_search.best_estimator_
    y_predict = knn.predict(X_test)
    print(y_predict)
    print('Training set score: {:.2f}'.format(knn.score(X_train, y_train)))
    print('Test set score: {:.2f}'.format(knn.score(X_test, y_test)))

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70 1]  
  可以看出training set score有了明显的提升（从0.82提升到0.98），但是test set score的提升不是很多（从0.72提升到0.73）。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70]: /images/20221124/f567eda4d5734511a0a8ed65de2b2cb2.png
[20200813094320266.png]: /images/20221124/c3b92d5db22c4acb81b08afcbee263c3.png
[20200813094348781.png]: /images/20221124/cc1ad290aa264fc59d315cf1003b3b2c.png
[20200813094444403.png]: /images/20221124/a847e40429b243f2a2b7528ea2931c93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTU0MDEw_size_16_color_FFFFFF_t_70 1]: /images/20221124/ecfefac44f9b41e48b71347affc09404.png