零基础掌ML(2) — k-NN算法

lizhengxing 2021-09-07 09:25

k-NN简介

k-NN 是一种监督学习算法，全称 K-Nearest Neighbor，中文称之为 K近邻算法。

k-NN 是一种分类算法。（例如：我们可以用k-NN来预测某人是否有患糖尿病的风险。）

注：k-NN 不是只能用于分类，它也可以用来回归，这一点我将放到后面讲。

k-NN思想

下面我将通过一个小例子，带大家直观了解一下 k-NN 算法是如何工作的：

如图所示，我们想预测蓝色圆点属于哪个类别（即：是红方块？还是绿三角？）

注意：在这个例子中，其实有个前提，即图中的红方块和绿三角不是毫无规律胡乱分布的，它们的分布是有一定内在联系的，只不过我们不知道是一种怎样的联系，所以我们能期望通过 k-NN 这种机器学习算法帮我们找到这种内在的联系。

分析：

首先，预测蓝色圆点所属的类别（是红方块还是绿三角），是典型的分类问题，所以可以选用 k-NN 算法来帮助我们完成这个任务。

然后，k-NN 是一个监督学习算法，我们需要收集训练数据供 k-NN 算法学习，期望它能自动学习到数据中存在的某种内在的联系（或知识）。在这个任务中，我们的训练数据就是图中那些已知的、分布在不同位置上的红方块和绿三角。

最后，当我们拿到一个蓝色圆点，我们知道它所处位置，但不知道它所属的类别。k-NN 要做的是，利用它从训练数据中学习到的某种内在联系（或知识）来推断这个蓝色圆点所属的类别。

k：

k-NN 的 k，就是k个最近的邻居的意思。k-NN 的思想很朴素，当 k-NN 要对一个未知元素类别进行推断时，它会找从训练数据中找出距离这个未知元素最近的 k 个邻居，而这个未知元素所属的类别，将由这 k 个邻居投票决定（少数服从多数）。

如果 k=1（如下图），此时找到蓝圆点的 1 个最近的邻居是绿三角，所以 k-NN 的推断结果是绿三角。

如果 k=3（如下图），此时蓝圆点最近的3个邻居是2个绿三角和1个红方块，所以 k-NN 的推断结果还是绿三角。

如果 k=5（如下图），此时蓝圆点最近的5个邻居是2个绿三角和3个红方块，所以 k-NN 的推断结果是红方块。

如果 k=7（如下图），此时蓝圆点最近的7个邻居是4个绿三角和3个红方块，所以 k-NN 的推断结果又是绿三角。

以上就是 k-NN 算法的工作原理，有没有很简单😄 。

注：可能大家注意到了，k 的选择可能会影响到推断结果，那么我们该如何选择 k 值？这个问题我也把它放到后面来讲。

k-NN实战

前面我们用一个“虚拟”的例子，初步了解了 k-NN 机器学习算法的工作原理。

下面我再通过一个“真实”案例（Pima Indians Diabetes Database），从应用角度认识一下 k-NN 算法。

数据集介绍：

Pima Indians Diabetes Database 数据集来自 University of California，研究对象是亚利桑那凤凰城附近的皮马印第安人。该数据集共有 768 条数据，每条数据包含 8 个医学预测变量和 1 个结果变量：

• 8 个医学预测变量
  • 怀孕次数 (Pregnancies)
  • 血糖浓度(Glucose)
  • 血压(BloodPressure)
  • 肱三头肌皮脂厚度 (SkinThickness)
  • 胰岛素含量 (Insulin)
  • 身体质量指数 (BMI)
  • 糖尿病遗传系数 (Diabetes Pedigree Function)
  • 年龄(Age)
• 1 个结果变量
  • 结果(Outcome：1代表患糖尿病，0代表未患糖尿病)

数据集中，糖尿病患者（Outcome=1）有268例；未患糖尿病（Outcome=0）的人数为50。

目标

我们的目标是为这个数据集构建一个机器学习模型，这个模型可以用来预测患者是否患有糖尿病。

工具

我们将在 Kaggle 平台中的 Python 环境下，使用 sklearn 机器学习库，完成模型的构建。

实战

• 第一步：获取数据集在 Kaggle 平台上的存储位置

• 第二步：读取数据集，并分离出样本数据（X）和样本标签（Y）

• 第三步：将数据集按比例切割为训练数据集和测试数据集。

• 第四步：使用训练数据集训练k-NN模型

• 第五步：使用测试数据集测试模型的准确性。

可以看到，这个模型在测试数据集上的准确率是 72.7%。

• 第六步：使用训练出的模型，对未知的数据进行推断。

可以看出，预测是准确的。

完整代码

k-NN原理

距离的度量

k-NN 算法的核心是找出与待推断样本距离最近的 k 个邻居。

那么距离如何度量？

其实有很多距离度量方法，常用的有以下几种：

• 欧式距离
• 曼哈顿距离
• 切比雪夫距离
• 闵可夫斯基距离
• 标准欧式距离
• 马氏距离
• 汉明距离
• 夹角余弦
• 杰卡德相似系数

本文简要介绍以下几种。

欧几里得距离

欧式距离也称欧几里得距离，是最常见的距离度量，衡量的是多维空间中两个点之间的绝对距离 。

曼哈顿距离

曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离。对于一个具有正南正北、正东正西方向规则布局的城镇街道，从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离，因此，曼哈顿距离又称为出租车距离。

闵可夫斯基距离

闵可夫斯基距离 (Minkowski Distance)，也被称为 闵氏距离。闵可夫斯基距离是欧几里得和曼哈顿距离度量的广义形式。

k的选择

从前面“k-NN思想”中可以看出，k 的选择会影响算法的预测结果。那么我们该如何选择合适的 k 值？

我们用 “k-NN实战”中的例子来观察一下，不同 k 值对 k-NN 算法准确度的影响。

下面的程序将统计出 k 值从 1 到训练数据量变化时，k-NN 算法的准确度变化。

import pandas as pd
data = pd.read_csv('/kaggle/input/pima-indians-diabetes-database/diabetes.csv')
X = data.iloc[:, 0:8]
Y = data.iloc[:, -1]

from sklearn.model_selection import train_test_split
X_train, X_test, Y_train, Y_test = train_test_split(X, Y, test_size=0.3)

import numpy as np
neighbors = np.arange(1,len(Y_train))
train_accuracy =np.empty(len(neighbors))
test_accuracy = np.empty(len(neighbors))
print(pd.DataFrame(Y_train).groupby('Outcome').value_counts())

from sklearn.neighbors import KNeighborsClassifier
for i,k in enumerate(neighbors):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, Y_train)
    train_accuracy[i] = knn.score(X_train, Y_train) 
    test_accuracy[i] = knn.score(X_test, Y_test)

import matplotlib.pyplot as plt
plt.title('k-NN Varying number of neighbors')
plt.plot(neighbors, test_accuracy, label='Testing Accuracy')
plt.plot(neighbors, train_accuracy, label='Training accuracy')
plt.legend()
plt.xlabel('Number of neighbors')
plt.ylabel('Accuracy')
plt.show()

从图中可以看出：

• 如果当 K 的取值过小时，一旦有噪声的成分存在们，将会对预测产生比较大影响。例如取 K 值为1时，一旦最近的一个点是噪声，那么就会出现偏差，容易发生过拟合。
• 如果 K 的值取的过大时，就相当于用较大邻域中的训练实例进行预测，这时与输入目标点较远实例也会对预测起作用，使预测发生错误。
• 如果K=N 时，那么就是取全部的实例，即为取实例中某分类下最多的点，就对预测没有什么实际的意义了；

一般规则：

• K的取值尽量要取奇数，以保证在计算结果最后会产生一个较多的类别，如果取偶数可能会产生相等的情况，不利于预测。
• 一般 k 的取值不超过20，上限是 n 的开方，随着数据集的增大，K的值也要增大。

实际操作：

• 我们可以采用交叉验证方式（例如：K折交叉验证(K-fold Cross Validation)），我们可以得出最合适的K值。
• 使用 skleran 中的 GridSearchCV 即可完成这个操作。

import pandas as pd
data = pd.read_csv('/kaggle/input/pima-indians-diabetes-database/diabetes.csv')
X = data.iloc[:, 0:8]
Y = data.iloc[:, -1]

from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import GridSearchCV

parameters = {'n_neighbors': [1,3,5,7,9,11,13,15]}
knn = KNeighborsClassifier()

clf = GridSearchCV(knn, parameters, cv=5)
clf.fit(X,Y)

print("最终最佳准确率: %.2f" % clf.best_score_)
print("最终的最佳K值: ", clf.best_params_)

k-NN应用

k-NN 算法已在各种应用中得到运用，主要是在分类中，例如：

• 数据预处理：数据集经常有缺失值，但 KNN 算法可以在称为缺失数据插补的过程中估计这些值。
• 医疗保健：KNN 还应用于医疗保健行业，预测心脏病发作和前列腺癌的风险。该算法用于计算最有可能的基因表达。
• 金融：该算法也被用于各种金融和经济用例。例如，一篇论文展示了如何通过对信用数据使用 KNN 算法来帮助银行评估向组织或个人提供贷款的风险。它用于确定贷款申请人的信用状况。另一份期刊重点介绍了它在股票市场预测、货币汇率、交易期货和洗钱分析中的用途。
• 模式识别：KNN 还有助于识别模式，例如文本和数字分类。这对于识别表格或邮寄信封上的手写数字特别有用。

k-NN优缺点

优势：

• 易于实现：鉴于算法的简单性和准确性，它是新数据科学家将学习的首批分类器之一。
• 很少的超参数：k-NN 只需要 k 值和距离度量，与其他机器学习算法相比，所需的超参数很少。
• 对于低纬数据,具有准确度高的优势

缺点：

• 不能很好地扩展：由于 KNN 是一种惰性算法（用于生成预测的计算推迟到分类时进行），因此与其他分类器相比，它占用了更多的内存和数据存储，而更多的数据可能需要更长的时间来计算。虽然已经有不同的数据结构（例如 Ball-Tree）来解决计算效率低下的问题，但分类器是否理想可能取决于业务问题。
• 维度的诅咒：KNN 算法容易成为维度诅咒的受害者，这意味着它在高维数据输入时表现不佳。这有时也称为峰值现象，在算法达到最佳特征数量后，额外的特征会增加分类错误的数量，尤其是当样本尺寸较小时。对于高纬数据，时间消耗很高，而且容易出现过拟合.
• 容易过拟合：由于"维度的诅咒"，KNN 也更容易过拟合。虽然利用特征选择和降维技术来防止这种情况发生，但 k 的值也会影响模型的行为。较小的 k 值可能会过度拟合数据，而较大的 k 值往往会"平滑"预测值，因为它是对更大区域或邻域的值进行平均。但是，如果 k 的值太高，那么可能会欠拟合数据。

参考

• https://sebastianraschka.com/pdf/lecture-notes/stat479fs18/02_knn_notes.pdf
• https://www.ibm.com/docs/zh/ias?topic=procedures-k-nearest-neighbors-knn
• https://www.kaggle.com/code/iambca/ml101-k-nn/notebook
• https://www.kaggle.com/datasets/uciml/pima-indians-diabetes-database