从头开始构建 K 最近邻算法

文摘 2024-07-10 19:54 辽宁

点击上方“进修编程”，选择“星标”公众号

超级无敌干货，第一时间送达！！！

金属质感分割线

介绍

一位聪明人曾经说过：“你是你身边五个人的平均值”。K 近邻算法也同样暗示了这一点——数据点 x 是数据集中与其相关的 K 个数据点的平均值。是的——算法就是这么简单直接。

KNN 是一种监督式机器学习模型，可用于分类和回归。对于分类任务，该算法通过计算数据点与数据集中每个其他数据点的距离并选择 k 个最近的数据点来预测新数据点 Xi 的标签。K 是一个超参数——由模型用户确定而不是由模型计算的参数。此外，KNN 是一种高度可解释的算法。

本文讨论了 KNN 如何用于分类和回归。本文的目的是探索算法内部发生的事情。

重点介绍 KNN 算法如何进行回归和分类
突出算法的优缺点以及最佳用例
仅使用numpy实现自定义 KNN 模型
将分类和回归的自定义实现与标准sklearn实现进行比较

KNN 的工作原理

KNN 可用于标记数据集的分类和回归。该算法仅在训练阶段存储数据。模型的输出取决于超参数K——可以是模型用户选择的任意数字。

KNN 用于分类

当使用 KNN 进行分类时，数据集首先存储在训练阶段。在新数据点 x 的预测阶段，算法：

计算新数据点与所有训练数据点之间的距离。
选择 K 个最近的训练数据点（邻居）——如果 K 为 3，则根据距离选择 3 个最近的训练数据点。
分配所选 K 个邻居中最常见的类标签。

KNN 回归

与分类类似，该算法仅在训练阶段存储数据集。为了预测新数据点 x 的 y，算法：

计算新数据点与所有训练数据点之间的距离。
选择 K 个最近的训练数据点（邻居）——如果 K 为 3，则根据距离选择 3 个最近的训练数据点。
计算选定的 K 个邻居的目标值的平均值（或加权平均值）来预测新数据点的值

何时使用 KNN

KNN 与其他 ML 浅层模型一样，具有最适合的用例。它最适合小型到中等规模的数据集，因为 KNN 算法对于单个预测查询的时间复杂度为 O(nd)。其中 n 是训练实例的数量，d 是特征的数量。因此，算法时间往往会随着特征和训练实例的增加而扩展。

优点：

简单、直观。
该算法没有训练阶段，因此可以快速部署。
它可以很好地处理少量数据。

缺点：

由于需要计算所有数据点的距离，因此该算法在预测过程中的计算成本可能很高。
高维数据会导致性能下降——维数灾难。
它对不相关的特征和特征缩放很敏感。
它需要选择最佳 K，这可能很有挑战性。可以使用网格搜索和交叉验证等方法来选择最佳 K（这超出了本文的讨论范围）。

何时使用：

当数据集较小且维数较低时。
当你需要一个简单的算法而不需要模型训练时间时。
当您预计决策边界是非线性的时候。
当您需要一个基线模型来与更复杂的模型进行比较时。

算法步骤

选择 K 的值：确定要考虑的邻居数量。
计算欧几里得距离：对于给定的测试数据点，计算到所有训练数据点的距离。欧几里得距离通常用于 KNN，因为它模拟向量空间中两点之间的直线距离。
按距离排序：按升序对距离进行排序。
选择最近邻居：选择前 K 个邻居。
对于分类：在 K 个邻居中使用多数投票。
对于回归：计算 K 个邻居的目标值的平均值（或加权平均值）。

代码实现——Python

该实现利用面向对象编程；将 KNN 模型表示为具有方法（表示为函数）的类，例如predict、fit、calculate_prediction和euclidean_distance。

import numpy as np 
class  KNN :     def  __init__ ( self, k= 5 , task= 'classification' ):         self.k = k         self.task = task 
    def  fit ( self, X_train, y_train ): #训练函数        self.X_train = X_train         self.y_train = y_train 
    def  euclidean_distance ( self, x1, x2 ):         return np.sqrt(np. sum ((x1 - x2) ** 2 )) 
    def  predict ( self, X_test ): #预测函数        predictions = [self.calculate_prediction(x) for x in X_test]         return np.array(predictions) 
    def  calculate_prediction ( self, x ):         # 计算 x 与训练集中所有示例之间的距离 distances         = [self.euclidean_distance(x, x_train) for x_train in self.X_train]         # 按距离排序并返回前 k 个邻居的索引        k_indices = np.argsort(distances)[:self.k]         # 提取 k 个最近邻训练样本的标签        k_nearest_labels = [self.y_train[i] for i in k_indices] 
        if self.task == 'classification' :            # 返回最常见的类标签            unique, counts = np.unique(k_nearest_labels, return_counts= True )             return unique[np.argmax(counts)] 
        elif self.task == 'regression' :             # 返回 k 个最近标签的平均值            return np.mean(k_nearest_labels) 
        else :             raise ValueError( "Task must be either 'classification' or 'regression'" )

分类数据集

用于分类的数据集是葡萄酒数据集。该数据集包含 178 个样本，具有 13 个连续特征和三个类别，分别对应三种不同的葡萄酒品种。以下代码使用数据集 API 将其导入并拆分为训练集和测试集。

import pandas as pdfrom sklearn.model_selection import train_test_split
# URL to the Wine dataset in CSV formaturl = "https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data"
# Column names as per the dataset descriptioncolumns = [    'Alcohol', 'Malic_Acid', 'Ash', 'Alcalinity_of_Ash', 'Magnesium',    'Total_phenols', 'Flavanoids', 'Nonflavanoid_phenols', 'Proanthocyanins',    'Color_intensity', 'Hue', 'OD280/OD315_of_diluted_wines', 'Proline']
# Load the dataset into a pandas DataFramedf = pd.read_csv(url, header=None, names=['Class'] + columns)
# Separate features and labelsX = df[columns].valuesy = df['Class'].values
# Split the dataset into training and testing setsX_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)
print("Training features shape:", X_train.shape)print("Training labels shape:", y_train.shape)print("Testing features shape:", X_test.shape)print("Testing labels shape:", y_test.shape)

分类测试模型实现

下面的代码使用自定义实现构建了一个 KNN 分类器，选择K为 3。然后，它将模型拟合到之前创建的训练和测试集上并生成预测。这里调用了之前在类实现中创建的fit和predict方法。

knn = KNN(k=3, task='classification')knn.fit(X_train, y_train)y_pred = knn.predict(X_test)

以下代码使用sklearn的默认准确度函数为自定义模型生成准确度分数

# Calculate accuracy
from sklearn.metrics import accuracy_score
accuracy_custom = accuracy_score(y_test, y_pred)print("Custom Accuracy:", accuracy_custom)

Sklearn 实现——分类

以下代码使用与Sklearn实现相同的数据集构建 KNN 分类器和预测

# Create and train the KNN modelfrom sklearn.neighbors import KNeighborsClassifierknn = KNeighborsClassifier(n_neighbors=5)knn.fit(X_train, y_train)
# Make predictions on the test sety_pred = knn.predict(X_test)
# Calculate accuracyaccuracy_sklearn = accuracy_score(y_test, y_pred)print("Sklearn Accuracy:", accuracy_sklearn)

比较自定义 KNN 和 Sklearn KNN——分类

下面的代码构建了一个条形图，以比较自定义和 Sklearn KNN 模型实现在 Wine 数据集上的准确度。

import matplotlib.pyplot as plt
# Visualize the accuracy scoreslabels = ['Custom KNN', 'Sklearn KNN']accuracies = [accuracy_custom, accuracy_sklearn]
plt.figure(figsize=(8, 6))plt.bar(labels, accuracies, color=['blue', 'green'])plt.xlabel('Model')plt.ylabel('Accuracy')plt.title('Comparison of KNN Model Accuracies')plt.ylim(0, 1)for i, v in enumerate(accuracies):    plt.text(i, v + 0.02, f"{v:.2f}", ha='center', va='bottom')plt.show()

回归数据集 - Auto MPG 数据集

用于回归的数据集是 Auto MPG 数据集。该数据集包含有关汽车燃油效率的信息，有 398 个样本和气缸、排量、马力等特征。以下代码使用数据集 API 将其导入并拆分为训练集和测试集。

# Load the Auto MPG dataseturl = "https://archive.ics.uci.edu/ml/machine-learning-databases/auto-mpg/auto-mpg.data"columns = ['mpg', 'cylinders', 'displacement', 'horsepower', 'weight', 'acceleration', 'model year', 'origin', 'car name']df = pd.read_csv(url, names=columns, delim_whitespace=True, na_values='?', comment='\t')
# Drop rows with missing valuesdf.dropna(inplace=True)
# Separate features and labelsX = df.drop(columns=['mpg', 'car name']).valuesy = df['mpg'].values
# Split the dataset into training and testing setsX_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

回归测试模型实现

下面的代码使用自定义实现构建了一个 KNN 分类器，选择K为 5。任务变量设置为“回归”。然后，它在之前创建的训练和测试集上调用 fit 函数并生成预测。这里调用了之前在类实现中创建的fit和predict方法。

# Create and train the custom KNN modelcustom_knn = KNN(k=5, task='regression')custom_knn.fit(X_train, y_train)

由于这是一个回归任务，以下代码使用sklearn的默认均方误差函数为自定义模型生成均方误差

from sklearn.metrics import mean_squared_error
# Make predictions and calculate MSE for the custom KNN modely_pred_custom = custom_knn.predict(X_test)mse_custom = mean_squared_error(y_test, y_pred_custom)

Sklearn 实现——回归

以下代码使用与Sklearn实现相同的数据集构建 KNN 回归器和预测

from sklearn.neighbors import KNeighborsRegressor
# Create and train the sklearn KNN modelsklearn_knn = KNeighborsRegressor(n_neighbors=5)sklearn_knn.fit(X_train, y_train)
# Make predictions and calculate MSE for the sklearn KNN modely_pred_sklearn = sklearn_knn.predict(X_test)mse_sklearn = mean_squared_error(y_test, y_pred_sklearn)

比较自定义 KNN 和 Sklearn KNN — 回归

下面的代码构建了一个条形图，以比较自定义和Sklearn KNN 模型实现在 Auto MPG 数据集上的均方误差。

# Visualize the resultslabels = ['Custom KNN', 'Sklearn KNN']mse_values = [mse_custom, mse_sklearn]
plt.figure(figsize=(8, 6))plt.bar(labels, mse_values, color=['blue', 'green'])plt.xlabel('Model')plt.ylabel('Mean Squared Error (MSE)')plt.title('Comparison of KNN Model Mean Squared Errors')for i, v in enumerate(mse_values):    plt.text(i, v + 0.5, f"{v:.2f}", ha='center', va='bottom')plt.show()
print("Custom KNN MSE:", mse_custom)print("Sklearn KNN MSE:", mse_sklearn)

结论

KNN 的优势在于其直接实施，无需单独的训练阶段，因此部署速度快且易于解释。然而，它也有局限性，例如预测过程中计算效率低、对不相关特征的敏感性以及选择最佳 K 值的挑战（如前所述）。

本文通过使用真实数据集（用于分类的 Wine 数据集和用于回归的 Auto MPG 数据集）的实际示例说明了如何构建 KNN 模型，并将其与标准 sklearn 的实现进行了比较。结果一点也不差。

matlab\python程序设计找我

— 完 —

进修编程

提升编程技能，学习编程技巧