KNN 算法

1, 关于 KNN

KNN (K-Nearest Neighbor), 即 K 近邻算法, K 个最近的邻居. 当需要预测一个未知样本的时候, 就由与该样本最近的 K 个邻居来决定

KNN 既可以用于分类, 也可用于回归. 用来分类时, 使用 K 个邻居中, 类别数量最多(或加权最多)者, 作为预测结果; 当用来回归分析时, 使用 K 个邻居的均值(或加权均值), 作为预测结果

KNN 算法的原理是: 样本映射到多维空间时, 相似度较高的样本, 距离也会较接近, “近朱者赤近墨者黑”

2, K 值

KNN 算法的 K 值是一个模型训练前就要人为指定的参数 超参数 , 不同于模型内部通过训练数据计算得到的参数. KNN 的超参数, 需要通常通过 交叉验证 的方式来选择最合适的参数组合

K 值的选择非常重要, K 值较小时, 模型预测依赖附近的邻居, 敏感性高, 稳定性低, 容易导致过拟合; 反之, K 值较大, 敏感性低, 稳定性高, 容易欠拟合

K 值在数据量小时, 可以通过遍历所有样本(穷举)的方式找出最近的 K 个邻居, 当数据量庞大时, 穷举耗费大量时间, 此时可以采用 KD树 来找 K 个邻居

3, 交叉验证

KNN 的网格搜索交叉验证: 取不同的 K, 选择不同的距离或权重计算方式等, 将数据分为多个组, 一个组作为测试集, 其他部分作为训练集, 不断循环训练和测试, 对模型进行循环验证, 找出最佳参数组合

4, 距离的度量方式

闵可夫斯基距离:

设 n 维空间中两个点位 X 和 Y:

$X=\left(x_{1}, x_{2}, \ldots \ldots, x_{n}\right)$ $Y=\left(y_{1}, y_{2}, \ldots \ldots, y_{n}\right)$

则阁可夫斯基距离为:

$D(X, Y)=\left(\sum_{i=1}^{n}\left|x_{i}-y_{i}\right|^{p}\right)^{1 / p}$

当 p 为 1 时, 又称 曼哈顿距离 ; 当 p 为 2 时, 称 欧几里得距离

5, 权重

统一权重: K 个邻居权重相同, 不管近远都是 1/K

距离加权权重: K 个邻居的权重, 与他们各自和待测样本的距离成反比, 同时要保证权重之和为 1. 例如 3 个邻居 a, b, c 距离待测样本的距离分别为 a, b 和 c, 则 a 的权重为:

$$\frac{\frac{1}{a}}{\frac{1}{a}+\frac{1}{b}+\frac{1}{c}}=\frac{b c}{b c+a c+a b}$$

b 和 c 同理

6, 数据标准化

样本中的特征通常非常多，由于各特征的性质不同，通常具有不同的量纲(数量级). 当各特征间的量纲相差很大时，如果直接用原始特征值进行分析，就会突出数值较高的特征在综合分析中的作用，相对削弱数值较低特征的作用, 因此需要通过数据标准化, 将量纲统一, 才能客观地描述各个特征对模型的影响程度

线性回归和逻辑回归, 都是通过每个特征与其权重的乘积相加来进行计算, 不进行数据标准化(不考虑正则化), 对每个特征的权重影响较大, 但对结果不会造成影响, 而 KNN 是基于距离计算的, 如果特征的量纲不同, 量纲较大的特征会占据主导地位, 导致忽略量纲较小的特征, 从而对模型性能造成较大影响

7, 算法实现步骤

a, 确定超参数
确定 K
确定距离度量方式
确定权重计算方式
其他超参数

b, 从训练集中选择距离待测样本最近的 K 个样本

c, 根据 K 个样本对待测样本进行预测, 如果遇到多个样本距离相同的情况, 默认选取训练集中靠前的

8, 流水线 Pipline

流水线可以将每个评估器视为一个步骤, 然后将多个步骤作为整体依次执行. 例如数据处理工作较多时, 可能涉及更多步骤, 例如多项式扩展, One-Hot 编码, 特征选择, 数据标准化, 交叉验证等, 分别执行过于繁琐, 我们可以将数据处理与模型训练各个步骤作为一个整体来执行

流水线具有最后一个评估器的所有方法:

a, 当流水线对象调用 fit 方法时, 会从第一个评估器依次调用 fit_transform 方法, 然后到最后一个评估器调用 fit 方法

b, 当流水线对象调用其他方法时, 会从第一个评估器依次调用 transform 方法, 然后到最后一个评估器调用其他方法

9, 以鸢尾花为例, 对逻辑回归和 KNN 进行比较:

from sklearn.model_selection import train_test_split  
from sklearn.neighbors import KNeighborsClassifier  
from sklearn.metrics import classification_report  
from sklearn.datasets import load_iris  
from sklearn.preprocessing import StandardScaler  
from sklearn.linear_model import LogisticRegression  
import matplotlib as mpl  
import matplotlib.pyplot as plt  
import warnings  
warnings.filterwarnings("ignore")  
import numpy as np  

mpl.rcParams["font.family"] = "SimHei"  
mpl.rcParams["axes.unicode_minus"] = False  

iris = load_iris()  
X = iris.data[:, :2]  
y = iris.target  
X_train, X_test, y_train, y_test = train_test_split(X, y,   
                        test_size=0.25, random_state=0)  

# 数据标准化: StandardScaler 均值标准差标准化, MinMaxScaler 最大最小值标准化  
ss = StandardScaler()  
X_train = ss.fit_transform(X_train)  
X_test = ss.transform(X_test)  

# 逻辑回归训练  
lr = LogisticRegression()  
lr.fit(X_train,y_train)  

# KNN 训练  
# n_neighbors: 邻居的数量  
# weights：权重计算方式, 可选值为 uniform 统一权重, 与 distance 加权权重  
knn = KNeighborsClassifier(n_neighbors=3, weights="uniform")  
knn.fit(X_train, y_train)  

# 比较 AUC  
from sklearn.metrics import roc_curve, auc,roc_auc_score  

lr_fpr, lr_tpr, lr_thresholds = roc_curve(y_test,  
                lr.predict_proba(X_test)[:,1], pos_label=1)  
lr_auc = auc(lr_fpr, lr_tpr)  
print('Logistic 算法: AUC = %.3f' % lr_auc)  

knn_fpr, knn_tpr, knn_thresholds = roc_curve(y_test,  
                knn.predict_proba(X_test)[:,1], pos_label=1)  
knn_auc = auc(knn_fpr, knn_tpr)  
print('KNN 算法: AUC = %.3f' % knn_auc)

Logistic 算法: AUC = 0.835
KNN 算法: AUC = 0.794

# 将 KNN 算法参数进行调优再来比较  
from sklearn.model_selection import GridSearchCV  

# K 值取 1~10, 并定义需要的参数组合  
knn = KNeighborsClassifier()  
grid = {'n_neighbors': range(1,11,1), 'weights': ['uniform','distance']}  

# 网格搜索交叉验证  
# param_grid：需要检验的超参数组合  
# scoring：模型评估标准, accuracy 正确率  
# n_jobs：并发数量  
# cv：交叉验证折数  
# verbose：输出冗余信息  
gs = GridSearchCV(estimator=knn, param_grid=grid, scoring='accuracy',  
                  n_jobs=-1, cv=5, verbose=0)  
gs.fit(X_train, y_train)  
gs_fpr, gs_tpr, gs_thresholds = roc_curve(y_test,  
                gs.predict_proba(X_test)[:,1], pos_label=1)  
gs_auc = auc(gs_fpr, gs_tpr)  
print('KNN 算法: AUC = %.3f' % gs_auc)

KNN 算法: AUC = 0.855

10, 以波士顿房价为例, 对线性回归和 KNN 进行比较:

from sklearn.datasets import load_boston  
from sklearn.neighbors import KNeighborsRegressor   
from sklearn.linear_model import LinearRegression  

X, y = load_boston(return_X_y=True)  
X_train, X_test, y_train, y_test = train_test_split(X, y,  
                        test_size=0.25, random_state=0)  
knn = KNeighborsRegressor(n_neighbors=3, weights="distance")   
knn.fit(X_train, y_train)  
print("KNN 算法 R²：", knn.score(X_test, y_test))  
lr = LinearRegression()  
lr.fit(X_train, y_train)  
print("线性回归算法 R²：", lr.score(X_test, y_test))

KNN 算法 R²： 0.5158073940789912
线性回归算法 R²： 0.6354638433202129

# 对 KNN 数据标准化和参数调优之后再来比较  
knn = KNeighborsRegressor()  
grid = {'n_neighbors': range(1,11,1), 'weights': ['uniform','distance']}  
gs = GridSearchCV(estimator=knn, param_grid=grid, scoring='r2',  
                  n_jobs=-1, cv=5, verbose=0)   

# 利用流水线处理  
from sklearn.pipeline import Pipeline  

# 定义流水线的步骤: 类型为一个列表, 列表中的每个元素是元组类型  
# 格式为：[(步骤名1，评估器1), (步骤名2， 评估器2), ……, (步骤名n, 评估器n)  
knn_steps = [("scaler", StandardScaler()), ("knn", gs)]  
knn_p = Pipeline(knn_steps)  

# 可以设置流水线的参数. 所有可用的参数可以通过 get_params 获取  
# 设置格式如下: (步骤名__参数)  
# p.set_params(knn__n_neighbors=3, knn__weights="uniform")  
knn_p.fit(X_train, y_train)  
print("KNN 算法 R²：", knn_p.score(X_test, y_test))  

# 线性回归数据标准化  
lr_steps = [("scaler", StandardScaler()), ("lr", LinearRegression())]  
lr_p = Pipeline(lr_steps)  
lr_p.fit(X_train, y_train)  
print("线性回归算法 R²：", lr_p.score(X_test, y_test))

KNN 算法 R²： 0.6441485149216897
线性回归算法 R²： 0.6354638433202131