KNN 实现 iris 数据集分类

本文从软件工程的角度，详细介绍如何手写实现 KNN 分类算法对 iris 数据集进行分类，包括完整的代码实现和详细的原理讲解。

1. 环境准备

1.1 依赖库

Python 3.7.0+
NumPy 1.21.6+
Pandas 1.3.5+

1.2 数据集获取

Iris 数据集是机器学习领域的经典数据集，可以从 Kaggle 下载：

curl -L -o iris.zip https://www.kaggle.com/api/v1/datasets/download/uciml/iris
unzip iris.zip

2. 核心算法原理

2.1 KNN 算法简介

KNN（K-最近邻）算法是一种基于距离的监督学习算法，其核心思想是： 1. 计算测试样本与所有训练样本的距离 2. 选取距离最近的 K 个训练样本 3. 根据这 K 个样本的类别进行投票，确定测试样本的类别

2.2 距离计算

本文使用欧氏距离（L2 距离）作为度量标准：

\[d(x, y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}\]

为了提高计算效率，我们使用向量化方法实现距离计算，避免显式循环。

3. 完整代码实现

3.1 导入依赖

import numpy as np
import pandas as pd

3.2 距离计算函数

def l2_distance(x, y):
    """
    计算两个矩阵之间的欧氏距离

    参数:
        x: 形状为 (m, p) 的矩阵
        y: 形状为 (n, p) 的矩阵

    返回:
        dists: 形状为 (m, n) 的距离矩阵，其中 dists[i][j] 表示 x[i] 与 y[j] 的距离
    """
    # 计算每个样本的平方和
    x_square_sum = np.sum(np.square(x), axis=1)
    y_square_sum = np.sum(np.square(y), axis=1)

    # 扩展维度并计算平方和矩阵
    x_y_square_sum = x_square_sum[:, np.newaxis] + y_square_sum[np.newaxis, :]

    # 计算点积
    x_y_dot = np.dot(x, y.T)

    # 计算距离矩阵
    dists = np.sqrt(x_y_square_sum - 2 * x_y_dot)

    return dists

3.3 KNN 分类器类

class KNNClassifier:
    """
    KNN 分类器实现
    """
    def __init__(self, k=3):
        """
        初始化分类器

        参数:
            k: 最近邻的数量
        """
        self.k = k
        self.X_train = None
        self.y_train = None

    def train(self, X_train, y_train):
        """
        训练分类器

        参数:
            X_train: 训练特征矩阵
            y_train: 训练标签
        """
        self.X_train = X_train
        self.y_train = y_train

    def predict(self, X_test):
        """
        预测测试样本的类别

        参数:
            X_test: 测试特征矩阵

        返回:
            y_pred: 预测标签
        """
        if self.X_train is None or self.y_train is None:
            raise ValueError("Classifier not trained. Call train() first.")

        N = X_test.shape[0]
        y_pred = np.zeros(N, dtype=self.y_train.dtype)

        # 计算距离矩阵
        dists = l2_distance(X_test, self.X_train)

        # 对每个测试样本进行预测
        for i in range(N):
            # 获取距离最近的 k 个训练样本的索引
            k_indices = np.argsort(dists[i])[:self.k]
            # 获取这些样本的标签
            k_nearest_labels = self.y_train[k_indices]
            # 投票确定预测标签
            values, counts = np.unique(k_nearest_labels, return_counts=True)
            y_pred[i] = values[np.argmax(counts)]

        return y_pred

3.4 数据预处理函数

def shuffle_data(X, y):
    """
    打乱数据顺序

    参数:
        X: 特征矩阵
        y: 标签

    返回:
        打乱后的特征矩阵和标签
    """
    idx = np.random.permutation(len(X))
    return X[idx], y[idx]


def split_data(X, y, test_size=0.2):
    """
    分割数据为训练集和测试集

    参数:
        X: 特征矩阵
        y: 标签
        test_size: 测试集比例

    返回:
        X_train, y_train, X_test, y_test: 训练集和测试集
    """
    test_size = int(len(X) * test_size)

    X_train = X[test_size:]
    y_train = y[test_size:]
    X_test = X[:test_size]
    y_test = y[:test_size]

    return X_train, y_train, X_test, y_test

def calc_accuracy(y_pred, y_true):
    """
    计算准确率

    参数:
        y_pred: 预测标签
        y_true: 真实标签

    返回:
        准确率
    """
    return np.mean(y_pred == y_true)


def preprocess():
    """
    数据预处理

    返回:
        X_train, y_train, X_test, y_test: 处理后的训练集和测试集
    """
    # 读取数据
    df = pd.read_csv('iris.csv')

    # 分离特征和标签
    X_df = df.iloc[:, :-1]  # 特征列
    y_df = df.iloc[:, -1]    # 标签列

    # 转换为 numpy 数组
    X = X_df.values
    y_label = y_df.values

    # 标签编码
    label_to_int = {label: idx for idx, label in enumerate(sorted(set(y_label)))} 
    y = np.array([label_to_int[label] for label in y_label])

    # 打乱数据
    X, y = shuffle_data(X, y)

    # 分割训练测试集
    return split_data(X, y, test_size=0.2)

3.5 主函数

def main():
    """
    主函数
    """
    # 数据预处理
    X_train, y_train, X_test, y_test = preprocess()

    # 初始化并训练分类器
    model = KNNClassifier(k=3)
    model.train(X_train, y_train)

    # 预测
    y_pred = model.predict(X_test)

    # 计算准确率
    accuracy = calc_accuracy(y_pred, y_test)

    print(f"Accuracy: {accuracy:.4f}")


if __name__ == "__main__":
    main()

4. 代码优化与性能分析

4.1 性能优化

向量化计算: 使用 NumPy 的向量化操作代替显式循环，显著提高计算效率
距离计算优化: 使用矩阵运算公式，避免了高维空间中的重复计算

4.2 时间复杂度分析

训练阶段: O(1)，仅存储训练数据
预测阶段: O(mnp)，其中 m 是测试样本数，n 是训练样本数，p 是特征维度

5. 运行结果与分析

5.1 预期输出

运行上述代码，预期输出类似：

Accuracy: 0.9667

5.2 结果分析

KNN 算法在 iris 数据集上表现良好，通常准确率在 95% 以上
对于小数据集，KNN 是一种简单有效的分类方法
对于大规模数据集，可考虑使用 KD 树等数据结构优化距离计算

6. 总结

本文实现了一个完整的 KNN 分类器，用于对 iris 数据集进行分类。主要特点包括：

完整的代码实现：包含数据预处理、模型训练、预测和评估的完整流程
向量化计算：使用 NumPy 实现高效的距离计算
详细的文档：每个函数都有清晰的文档字符串和参数说明
良好的代码结构：模块化设计，易于理解和扩展

通过本文的实现，读者可以深入理解 KNN 算法的原理和实现细节，为进一步学习机器学习算法打下基础。