最通俗易懂的KNN算法讲解
KNN，也称K最近邻（K-nearest neighbour），是一种监督学习算法，可用于分类和回归问题，是最简单的机器学习算法之一。K最近邻是非参数的，即不对基础数据做出任何假设，也被称为惰性算法，因为它在训练阶段不学习，而是存储数据点，在测试阶段进行学习，它是一种基于距离的算法。
KNN算法原理
K最近邻是一种用于回归和分类的监督学习算法。它试图通过计算测试数据与所有训练点之间的距离，选择与测试数据最接近的K个点来预测测试数据的正确类别。
在分类情况下，KNN算法计算测试数据属于K个训练数据类别的概率，并选择具有最高概率的类别。在回归的情况下，值是所选K个训练点的平均值。
算法流程：
- 设定K值
- 计算所有训练点与新测试数据点之间的距离
- 将距离按升序排序
- 选择前K个距离的训练点，若是分类任务，则新测试点的类别是K个训练点最高概率的类别（出现次数最多的类）；若是回归任务，则新测试点的值是K个训练点的平均值。
让我们可视化上述算法流程，如下图训练数据集有3个不同颜色的类别，我们开始用KNN预测灰色点的类别。
设置K等于3，计算灰色点与所有训练数据集的距离：
根据距离升序进行排序：
统计前3个距离的类别分布，有2个黄色点和1个绿色点，因此灰色点预测为黄色类。
距离定义
KNN算法需要计算新点与每个训练点之间的距离。有多种计算距离的方法，其中最常见的方法是欧几里得距离、曼哈顿距离（用于连续数据），以及汉明距离（用于分类数据）。假设两个点分别为，维度是k。
- 欧几里得距离（Euclidean Distance）等于两个点差的平方和的平方根，也常用于计算回归模型的损失，距离定义：
- 曼哈顿距离（Manhattan Distance）等于两个点各维度之差的绝对值平方和。距离定义：
- 汉明距离（Hamming Distance）用于分类变量，等于两个点的维度分量值不相等的个数。距离定义：
如1001和1111的汉明距离等于2.
如何选择K值
K值是KNN算法中最重要的参数，如下图，设置K=3，距离预测点（ID11）最近的点是ID1、ID5和ID6。
已知ID1、ID5和ID6的信息（如下表），求ID11的体重。
| ID | 身高 | 年龄 | 体重 |
|---|---|---|---|
| 1 | 5 | 45 | 77 |
| 5 | 4.8 | 40 | 72 |
| 6 | 45 | 36 | 60 |
根据KNN算法，ID11的预测体重：
若设置K=5，距离ID11最近的点是ID1,ID4,ID5,ID6,ID10。
| ID | 身高 | 年龄 | 体重 |
|---|---|---|---|
| 1 | 5 | 45 | 77 |
| 4 | 5.9 | 34 | 59 |
| 5 | 4.8 | 40 | 72 |
| 6 | 5.8 | 36 | 60 |
| 10 | 5.6 | 32 | 58 |
KD11的预测体重：
我们注意到，不同的K值有不同的预测结果。那么如何找出最佳的K值呢？我们根据训练集误差和验证集误差来决定（毕竟，最小化错误是我们的最终目标！）
下图分别表示不同K值下的训练误差（蓝色线）和验证误差（红色线）：
当k值很低（假设k=1）时，模型会对训练数据过度拟合，导致验证集上的错误率很高。另一方面，对于较高的k值，模型在训练集和验证集上表现不佳。如果您仔细观察，您会发现验证误差曲线在k = 9时达到最小值。这个k值是模型的最佳值（对于不同的数据集，它会有所不同）。研究人员通常使用肘部曲线来确定k值，这个名字来源于它类似于手肘的形状。
回归预测实战
到目前为止，你一定已经对算法有了清晰的理解。如果你对此有任何疑问，我很乐意回答你的文章评论，现在我们在一个 Big Mart 数据集上逐步的实现KNN算法。（数据集下载链接: https://pan.baidu.com/s/1_YC1M3Zhd1ulL73BbihNRw?pwd=qt6p 提取码: qt6p）
1.加载数据
import pandas as pd
df = pd.read_csv('train.csv')
df.head()
显示前5行数据：
2.缺失值补全
我们首先统计特征项的缺失情况：
df.isnull().sum()
输出：
根据统计情况，Item_Weight特征和Outlet_Size特征有缺失值。
Item_Weight特征项的缺失值，通过平均值进行补全。
mean = df['Item_Weight'].mean() # 该特征项的平均值
df['Item_Weight'].fillna(mean, inplace =True) # 缺失值补全
Outlet_Size特征项的缺失值，通过众数进行补全，众数的含义是出现次数最多的值。
mode = df['Outlet_Size'].mode() # 众数
df['Outlet_Size'].fillna(mode[0], inplace =True) # 补全
3.去掉不需要的特征：
df.drop(['Item_Identifier', 'Outlet_Identifier'], axis=1, inplace=True)
df = pd.get_dummies(df)
4.数据集划分
训练数据集和测试数据集以7:3的比例划分，并将特征项"Item_Outlet_Sales"作为预测变量。
from sklearn.model_selection import train_test_split
train , test = train_test_split(df, test_size = 0.3)
x_train = train.drop('Item_Outlet_Sales', axis=1)
y_train = train['Item_Outlet_Sales']
x_test = test.drop('Item_Outlet_Sales', axis = 1)
y_test = test['Item_Outlet_Sales']
5.特征预处理之归一化
将每个特征项的尺度都归一化再0~1的范围。
from sklearn.preprocessing import MinMaxScaler
scaler = MinMaxScaler(feature_range=(0, 1))
x_train_scaled = scaler.fit_transform(x_train)
x_train = pd.DataFrame(x_train_scaled)
x_test_scaled = scaler.fit_transform(x_test)
x_test = pd.DataFrame(x_test_scaled)
6.计算不同K值下的损失函数
由于预测值是连续属性，损失函数采用均方根误差表示。
rmse_val = [] #to store rmse values for different k
for K in range(20):
K = K+1
model = neighbors.KNeighborsRegressor(n_neighbors = K)
model.fit(x_train, y_train) #fit the model
pred=model.predict(x_test) #make prediction on test set
error = sqrt(mean_squared_error(y_test,pred)) #calculate rmse
rmse_val.append(error) #store rmse values
print('RMSE value for k= ' , K , 'is:', error)
输出不同K值下的损失值：
7.绘制损失曲线图
# 绘制不同k值下的均方根损失
curve = pd.DataFrame(rmse_val) #elbow curve
curve.plot()
效果图：
根据曲线可知，当我们取 k=1 时，得到了一个非常高的 RMSE 值。随着 k 值的增加，RMSE 值逐渐减小。当 k=7 时，RMSE 约为1219.06，在进一步增加 k 值时 RMSE 值会急剧增加。我们可以负责任地说，在这种情况下 k=7 将给我们最好的结果。
8.网格搜索法确定K值
为了确定最优K值，每次都绘制肘部曲线是一项繁琐且乏味的过程，你可以简单地使用网格搜索来找到最佳的参数值。
from sklearn.model_selection import GridSearchCV
params = {'n_neighbors':[2,3,4,5,6,7,8,9]}
knn = neighbors.KNeighborsRegressor()
model = GridSearchCV(knn, params, cv=6)
model.fit(x_train,y_train)
model.best_params_
输出结果：
{'n_neighbors': 7}
因此肘部曲线和网格搜索的最优参数一致，都是7.
可视化KNN分类模型的决策边界
为了更直观的理解KNN模型效果，我们可视化KNN分类模型的决策边界。
1. 加载包
import matplotlib.pyplot as plt
import pandas as pd
from sklearn import datasets, neighbors
from mlxtend.plotting import plot_decision_regions
2.绘制不同K参数下的模型决策边界函数
def knn_comparison(data, k):
x = data[['X','Y']].values
y = data['class'].astype(int).values
clf = neighbors.KNeighborsClassifier(n_neighbors=k)
clf.fit(x, y)
# 绘制决策边界
plot_decision_regions(x, y, clf=clf, legend=2)
# 增加标注
plt.xlabel('X')
plt.ylabel('Y')
plt.title('Knn with K='+ str(k))
plt.show()
入口函数：
data1 = pd.read_csv(‘ushape.csv’)
for i in [1,5,20,30,40,80]:
knn_comparison(data1, i)
不同K下的决策边界函数：
优点和缺点
优点：
- 我们可以轻松地实现该算法。
- 通过对 k 个最近邻进行平均，它对噪声数据非常有效。
- 在处理大数据时表现良好。
- 形成的决策边界可以是任意形状的。
缺点：
- 维度灾难，且可能被无关属性主导距离。
- 有时找到正确的 k 值可能会耗费时间。
- 由于其距离度量，计算成本非常高。
欢迎扫码关注：