一、算法原理

算法是一种基于实例的监督学习算法，其核心原理是“物以类聚”——通过测量新样本与已知样本之间的距离，找到最近的K个邻居，并根据这些邻居的类别或数值来预测新样本的属性。

1、 基本思想

分类任务：给定一个新样本，找到训练集中距离最近的K个样本，统计这K个样本中类别出现次数最多的类别，作为新样本的预测类别。
回归任务：找到最近的K个样本，取这些样本目标值的平均值（或加权平均）作为新样本的预测值。

2、关键步骤

(1) 计算距离

常用距离度量：
欧氏距离（Euclidean Distance）：适用于连续特征，公式为：
$d(x,y)=\sqrt{\sum _{i=1}^n（x_i-y_i{）}^2}$
曼哈顿距离（Manhattan Distance）：适用于网格状数据（如城市街区），公式为：
$d(x,y)=\sum _{i=1}^n|x_i-y_i|$
余弦相似度：适用于文本或高维稀疏数据，衡量方向相似性。
闵可夫斯基距离（Minkowski Distance）：欧氏和曼哈顿距离的泛化形式。

(2) 选择K值

K值的影响：
K过小：模型对噪声敏感，容易过拟合（如K=1时，预测完全依赖最近的一个样本）。
K过大：模型可能忽略局部特征，导致欠拟合（如K=训练集大小时，预测结果为所有样本的平均值）。
选择方法：
通过交叉验证（Cross-Validation）尝试不同K值，选择验证集上表现最好的K。
经验法则：K通常取奇数（避免平票），且远小于训练集大小。

(3) 投票/平均

分类任务：对K个邻居的类别进行多数投票，选择票数最多的类别。
回归任务：取K个邻居目标值的平均值（或加权平均，距离越近权重越大）。

(4) 距离加权（可选）

对邻居的贡献进行加权，距离越近的样本权重越大（如反距离加权、高斯核加权等），以提升模型对局部特征的敏感性。

二、参考代码

import numpy as np
from collections import Counter
from sklearn.datasets import  make_blobs,make_circles
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap

class KNN:
    def __init__(self, k=3):
        """
        初始化KNN分类器
        :param k: 邻居数量，默认为3
        """
        self.k = k
        self.X_train = None
        self.y_train = None
    
    def fit(self, X, y):
        """
        训练模型（KNN实际上是记忆训练数据）
        :param X: 训练特征，形状为[n_samples, n_features]
        :param y: 训练标签，形状为[n_samples]
        """
        self.X_train = X
        self.y_train = y
    
    def predict(self, X):
        """
        预测新样本的类别
        :param X: 测试样本，形状为[n_samples, n_features]
        :return: 预测类别，形状为[n_samples]
        """
        predictions = [self._predict(x) for x in X]
        return np.array(predictions)
    
    def _predict(self, x):
        """
        预测单个样本的类别
        :param x: 单个样本，形状为[n_features]
        :return: 预测类别
        """
        # 计算距离（欧氏距离）
        distances = [np.linalg.norm(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]
        
        # 多数投票
        most_common = Counter(k_nearest_labels).most_common(1)
        return most_common[0][0]
    def generate_data(self,n_samples=100, n_features=2, databaset="linear",noise=None,n_classes=2, random_state=None):
        """
        生成分类数据
        :param n_samples: 样本数量
        :param n_features: 特征数量（最多2个，便于可视化）
        :param databaset: 生成数据类型
        :param n_classes: 类别数量
        :param random_state: 随机种子
        :param noise: 噪声水平
        :return: X, y 特征和标签
        """
        if n_features > 2:
            print("警告：为了可视化，建议使用不超过2个特征。将仅使用前2个特征。")
            n_features = 2
        
        # 生成数据
        if databaset == "linear":
            X, y = make_blobs(n_samples=n_samples, 
                        n_features=n_features, 
                        centers=n_classes, 
                        random_state=random_state)
        if databaset =="circular":
            X, y = make_circles(n_samples=n_samples, 
                       noise=noise, 
                       factor=0.4, 
                       random_state=random_state)
        
        return X[:, :2], y  # 确保只返回2个特征
    def plot_knn_decision_boundary(self, X_train, y_train, X_test=None, y_test=None, title="KNN Decision Boundary", grid_resolution=50):
        """
        可视化 KNN 决策边界，并标注训练集和测试集样本
        
        参数:
            X_train, y_train: 训练数据
            X_test, y_test: 测试数据（可选）
            title: 图表标题
            grid_resolution: 网格分辨率（默认50x50）
        """
        # 1. 创建网格
        X_all = np.vstack([X_train, X_test]) if X_test is not None else X_train
        x_min, x_max = X_all[:, 0].min() - 0.5, X_all[:, 0].max() + 0.5
        y_min, y_max = X_all[:, 1].min() - 0.5, X_all[:, 1].max() + 0.5
        xx, yy = np.meshgrid(
            np.linspace(x_min, x_max, grid_resolution),
            np.linspace(y_min, y_max, grid_resolution)
        )
        
        # 2. 预测网格点
        grid_points = np.c_[xx.ravel(), yy.ravel()]
        Z = self.predict(grid_points)
        Z = Z.reshape(xx.shape)
        
        # 3. 绘制决策边界
        plt.figure(figsize=(10, 6))
        plt.contourf(xx, yy, Z, cmap='coolwarm', alpha=0.3)
        
        # 4. 绘制训练集样本
        plt.scatter(
            X_train[:, 0], X_train[:, 1], 
            c=y_train, cmap='viridis', 
            edgecolors='k', s=80, 
            label='Train', marker='o'
        )
        
        # 5. 绘制测试集样本（如果存在）
        if X_test is not None and y_test is not None:
            plt.scatter(
                X_test[:, 0], X_test[:, 1], 
                c=y_test, cmap='viridis', 
                edgecolors='r', s=120, 
                label='Test', marker='s'
            )
            # 计算并显示测试准确率
            y_pred = self.predict(X_test)
            accuracy = np.sum(y_test==y_pred)/len(y_test)
            plt.title(f"{title} (Test Accuracy: {accuracy:.2f})", fontsize=12)
        else:
            plt.title(title, fontsize=12)
        
        # 6. 添加图例和标签
        plt.xlabel('Feature 1', fontsize=10)
        plt.ylabel('Feature 2', fontsize=10)
        plt.legend(fontsize=10)
        plt.grid(True, linestyle='--', alpha=0.5)
        plt.show()

三、算法评价

1、应用场景：

分类：如医疗诊断（根据症状预测疾病）、图像识别（根据像素特征分类）。
回归：如房价预测（根据面积、位置等特征预测价格）。
推荐系统：根据用户历史行为推荐相似商品或内容。

2、优点：

简单直观，无需训练阶段（惰性学习，Lazy Learning）。
适用于多分类问题，且对数据分布无假设。
通过调整K值可平衡过拟合与欠拟合。

3、缺点：

计算复杂度高（需存储所有训练数据，预测时计算所有距离）。
对高维数据效果差（维度灾难，距离度量失去意义）。
对特征尺度敏感（需标准化或归一化处理）。
类别不平衡时，少数类可能被忽略（可通过加权投票缓解）。

四、线性和非线性数据集应用

1、线性数据

数据生成参数：databaset=“linear”,noise=2.0,n_samples=400, n_classes=3, random_state=42
准确率较高，但从结果图上可以看出，部分训练集存在误差。

2、非线性数据

数据生成函数databaset=“circular”,noise=0.2,n_samples=400, n_classes=2, random_state=42

同心圆生成数据的函数不能指定标签数量，故只生成了两个标签，可以看出，对于非线性数据尽管准确率下降，但却很好地忽略了数据集中的噪声。