Python基础算法解析：K最近邻算法

K最近邻（K-Nearest Neighbors，简称KNN）是一种简单而有效的监督学习算法，常用于分类和回归问题。本文将介绍KNN算法的原理、实现步骤以及如何使用Python进行KNN的编程实践。

什么是K最近邻算法？

K最近邻算法是一种基于实例的学习方法，其核心思想是：如果一个样本在特征空间中的k个最相似（即最近）的样本中的大多数属于某一个类别，则该样本也属于这个类别。KNN算法不需要训练模型，而是利用训练集中的数据进行预测。

KNN的原理

KNN算法的原理非常简单，主要包括以下几个步骤：

• 计算距离：计算测试样本与训练样本之间的距离，通常使用欧氏距离或曼哈顿距离。
• 选择最近邻：选取与测试样本距离最近的k个训练样本。
• 进行分类（或回归）：对于分类问题，通过投票机制确定测试样本的类别；对于回归问题，通过求取k个最近邻样本的平均值确定测试样本的输出。

KNN的实现步骤

• 计算距离：对于每个测试样本，计算其与所有训练样本的距离。
• 选择最近邻：选取与测试样本距离最近的k个训练样本。
• 进行分类（或回归）：对于分类问题，采用多数表决法确定测试样本的类别；对于回归问题，采用平均值确定测试样本的输出。

Python实现KNN算法

下面通过Python代码演示如何实现KNN算法：

import numpy as np

class KNN:
    def __init__(self, k=3):
        self.k = k

    def euclidean_distance(self, x1, x2):
        return np.sqrt(np.sum((x1 - x2) ** 2))

    def predict_classification(self, X_test, X_train, y_train):
        y_pred = [self._predict_single_classification(x, X_train, y_train) for x in X_test]
        return np.array(y_pred)

    def _predict_single_classification(self, x, X_train, y_train):
        distances = [self.euclidean_distance(x, x_train) for x_train in X_train]
        k_indices = np.argsort(distances)[:self.k]
        k_nearest_labels = [y_train[i] for i in k_indices]
        most_common = np.argmax(np.bincount(k_nearest_labels))
        return most_common

    def predict_regression(self, X_test, X_train, y_train):
        y_pred = [self._predict_single_regression(x, X_train, y_train) for x in X_test]
        return np.array(y_pred)

    def _predict_single_regression(self, x, X_train, y_train):
        distances = [self.euclidean_distance(x, x_train) for x_train in X_train]
        k_indices = np.argsort(distances)[:self.k]
        k_nearest_labels = [y_train[i] for i in k_indices]
        return np.mean(k_nearest_labels)

在上述代码中，我们定义了一个名为KNN的类，包括了初始化方法、欧氏距离计算方法、分类预测方法和回归预测方法。其中，predict_classification方法用于进行分类预测，predict_regression方法用于进行回归预测。

使用KNN进行分类和回归

接下来，让我们使用KNN算法对一个简单的分类和回归问题进行预测：

from sklearn.datasets import load_iris, load_boston
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, mean_squared_error

# 分类问题示例
iris = load_iris()
X = iris.data
y = iris.target

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

knn_classifier = KNN(k=3)
y_pred_classification = knn_classifier.predict_classification(X_test, X_train, y_train)
accuracy = accuracy_score(y_test, y_pred_classification)
print("Classification Accuracy:", accuracy)

# 回归问题示例
boston = load_boston()
X = boston.data
y = boston.target

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

knn_regressor = KNN(k=3)
y_pred_regression = knn_regressor.predict_regression(X_test, X_train, y_train)
mse = mean_squared_error(y_test, y_pred_regression)
print("Mean Squared Error:", mse)

总结

K最近邻算法是一种简单而强大的监督学习算法，适用于分类和回归问题。通过本文的介绍，你已经了解了KNN算法的原理、实现步骤以及如何使用Python进行编程实践。希望本文能够帮助你更好地理解和应用KNN算法。