机器学习系列（一）—

1. 算法定义

KNN 算法属于基于实例的机器学习方法。在对未知数据进行分类或回归之前，我们不需要对数据进行显式的训练或建立复杂的模型。它的核心思想是：对一个新的样本点，寻找在特征空间上与其最相似的 K 个已知数据点，采取“投票”或加权平均的方式，来决定新样本点的类别或数值预测结果。

2. 工作流程概括

KNN 算法的工作流程可以概括为以下几个步骤：

计算距离：对要预测的新样本点，分别与训练数据集中每一个样本计算距离（如欧几里得距离、曼哈顿距离等）。
选择 K 个近邻：根据计算的距离进行排序，选取距离最近的 K 个样本。
投票（分类）或加权平均（回归）：
- 分类：以 K 个近邻中出现频次最高的类别作为预测结果；
- 回归：以 K 个近邻目标值的平均或加权平均作为预测结果。
输出结果：得到新样本的类别标签或回归值。

3. 距离度量

KNN 中最常见的距离度量是欧几里得距离（Euclidean Distance），也可以根据实际需求采用其他方法，比如曼哈顿距离（Manhattan Distance）、切比雪夫距离（Chebyshev Distance）或者余弦相似度（Cosine Similarity）等。具体选择与数据分布以及业务需求相关。

常见欧几里得距离的计算公式如下（假设两个样本点分别为 $(x_1, x_2, \ldots, x_n)$ 和 $(y_1, y_2, \ldots, y_n)$ ）：

$\sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2 + \ldots + (x_n - y_n)^2}$

三、KNN 的特点

优点
- 简单易理解：原理十分直观，不需要复杂的建模过程；
- 对数据分布无强假设：无需像线性回归等算法一样假设数据线性可分；
- 可同时进行分类和回归：只要合理选取距离和投票/加权方式，都可以运用于分类与回归场景。
缺点
- 预测阶段开销大：每次预测都需要对新数据与训练数据集中所有样本计算距离，若训练数据集非常大，计算量将非常可观；
- K 的选择敏感：选择过大或过小的 K 都可能导致预测效果下降，需要结合实际数据或交叉验证确定；
- 易受数据分布不均影响：若某些类别在训练集中占比过大，或者不同维度特征间量纲差别大，会影响距离的计算效果；
- 缺乏可解释的模型结构：KNN 算法并不会“学习”到一个可泛化的模型，无法像决策树或神经网络一样给出可视化的结构。

四、KNN 算法使用要点与优化

归一化或标准化
当各特征量纲差异较大时，直接计算距离可能会导致某些特征对结果的影响过于突出。为了消除量纲影响，建议在使用 KNN 之前先对数据进行标准化或归一化处理。
距离加权
如果要进行回归，或者想让距离更近的邻居对分类决策权重更大，可以对距离进行一定的加权。常见的做法是对每个邻居设置权重 $\frac{1}{d}$ $(d$ 为距离），距离越近，权重越大。
数据降维或特征选择
当维度过高时（即“维度灾难”），距离的计算会变得难以区分。如果数据维度过高或有大量无关特征，可以尝试使用特征选择或降维方法（例如 PCA、LDA 等），以提升 KNN 的效果和效率。
索引结构（加速检索）
为了降低查询时间成本，可以建立诸如 k-d 树或 Ball Tree 等数据结构。对大规模数据集，还可以考虑使用近似最近邻搜索（Approximate Nearest Neighbor，ANN）算法加速检索。

numpy 实现如下：

import numpy as np
from collections import Counter

def euclidean_distance(x1, x2):
    """计算欧氏距离"""
    return np.sqrt(np.sum((x1 - x2) ** 2))

def knn(X_train, y_train, X_test, k=3):
    """
    K-NN分类函数
    
    参数:
    X_train (ndarray): 训练数据集特征，形状为 (n_samples, n_features)
    y_train (ndarray): 训练数据集标签，形状为 (n_samples,)
    X_test (ndarray): 测试数据集特征，形状为 (m_samples, n_features)
    k (int): 邻居个数
    
    返回:
    y_pred (ndarray): 预测的标签，形状为 (m_samples,)
    """
    y_pred = []
    
    for test_point in X_test:
        # 计算每个训练数据点与测试点的欧氏距离
        distances = [euclidean_distance(test_point, x_train) for x_train in X_train]
        
        # 找到距离最小的k个点的索引
        k_indices = np.argsort(distances)[:k]
        
        # 找到这k个点对应的标签
        k_nearest_labels = [y_train[i] for i in k_indices]
        
        # 使用多数表决来决定预测的标签
        most_common = Counter(k_nearest_labels).most_common(1)
        y_pred.append(most_common[0][0])
    
    return np.array(y_pred)