一、项目概述

这个项目的核心目标是从零实现经典机器学习算法，不调用sklearn的fit/predict接口，仅用NumPy完成矩阵运算、优化求解和模型推理。scikit-learn仅用于数据生成和最终的精度对比验证。

实现的算法覆盖三大类：

类别	算法	核心技术
监督学习-回归	线性回归	正规方程 / 批量梯度下降
监督学习-分类	逻辑回归	Sigmoid + 交叉熵 + 梯度下降
监督学习-分类	决策树	CART算法，Gini/熵分裂，后剪枝
监督学习-分类	随机森林	Bagging + 特征随机子空间 + OOB估计
监督学习-分类	SVM	SMO算法，线性核/RBF核，软间隔
监督学习-分类	KNN	距离加权投票，KD树优化
监督学习-分类	朴素贝叶斯	高斯分布假设，拉普拉斯平滑
监督学习-集成	GBDT	加法模型，负梯度拟合残差，回归树
无监督学习	K-Means	K-Means++初始化，肘部法则
降维	PCA	协方差矩阵特征值分解，贡献率

二、核心算法实现深度解析

2.1 SVM：SMO算法实现

支持向量机的核心是求解一个凸二次规划问题。对于线性可分情况，原始问题是最大化分类间隔，等价于最小化权重向量的 L2 范数：

通过拉格朗日对偶变换，将原始问题转化为对偶问题。对偶问题的优势在于：变量从 d+1 个（w 的维度 d 加 b）变成了 n 个（每个样本对应一个拉格朗日乘子 α），且核技巧可以自然地引入对偶问题中：

其中 C 是软间隔惩罚参数，控制间隔大小与误分类惩罚之间的权衡。C 越大，对误分类的惩罚越重，间隔越小；C 越小，间隔越大，但可能允许更多误分类。

SMO 算法核心思想：由于对偶问题是凸二次规划，理论上可以用通用的 QP 求解器解决，但当样本量 n 很大时（如 n=10000），通用 QP 求解器的时间复杂度太高。SMO（Sequential Minimal Optimization）由 Platt 于 1998 年提出，其核心思想是：每次只优化两个拉格朗日乘子 αi, αj，将其他乘子视为常数。由于等式约束 Σαi y_i = 0 的存在，固定其他乘子后，两个乘子的变化是线性相关的（α1 y_1 + α_2 y_2 = 常数），因此二次规划问题退化为单变量问题，有解析解。

两个乘子的更新公式：

其中：

E_i 是第 i 个样本的预测误差（预测值减真实标签），η 是核函数组合，本质上是两个样本在核空间中的距离平方。当 η ≤ 0 时（核函数不满足 Mercer 条件），需要跳过本次更新。

更新后需要裁剪到 [L, H] 区间以满足 box 约束 0 ≤ α_i ≤ C：

当 y1 = y2 时，L = max(0, α1 + α2 - C)，H = min(C, α1 + α2)。裁剪是 SMO 算法中最容易出错的步骤之一，必须根据 y1 和 y2 是否相等选择正确的 L 和 H 公式。

实现中的关键细节：

• KKT 条件检查：每次迭代优先选择违反 KKT 条件最严重的样本作为第一个乘子。KKT 条件是：αi = 0 ⇔ y_i f(x_i) ≥ 1；0 < αi < C ⇔ y_i f(x_i) = 1；α_i = C ⇔ y_i f(x_i) ≤ 1。

• 第二个乘子选择：选择使 |E1 - E2| 最大的样本，这样 α2 的更新步长最大，收敛最快。这是启发式策略，理论上不保证收敛最快，但实践中效果很好。

• 偏差 b 更新：更新两个乘子后，需要重新计算 b。如果更新后的 α1 在 (0, C) 之间，则 b 由第一个样本的 KKT 条件确定；同理 α2。如果两个都在边界上，则取两者的平均值。

• 核函数缓存：预计算 n×n 的核矩阵避免重复计算，对于 RBF 核尤其重要。当 n 很大时（如 n>5000），核矩阵内存占用大，可以用缓存策略只存储频繁访问的核值。

2.2 GBDT：负梯度拟合

梯度提升决策树（GBDT，Gradient Boosting Decision Tree）是一种加法模型，由 Friedman 于 2001 年系统提出。其核心思想是：通过迭代训练弱学习器（通常是回归树），每一轮拟合当前模型的损失函数的负梯度（伪残差），从而逐步降低训练损失。

算法框架：

Step 1：初始化。用一个常数初始化模型，该常数使训练损失最小：

对于平方损失，初始值就是训练集标签的均值；对于对数损失（分类），初始值是对数几率的均值。

Step 2：迭代训练。对于第 m 轮：

(a) 计算负梯度（伪残差）：对每个样本计算损失函数关于当前模型预测值的负梯度：

这是 GBDT 最核心的一步。负梯度可以理解为"当前模型还没拟合好的方向"，下一棵树就沿着这个方向去拟合。对于平方损失，负梯度就是残差 y - F(x)；但对于其他损失函数（如 Huber 损失、对数损失），负梯度不等于残差，这是 GBDT 能适配任意可微损失函数的关键。

(b) 拟合回归树：用回归树拟合伪残差 r_im，得到叶节点区域 R_jm（j=1,2,...,J）。注意这里用的是回归树而不是分类树，因为伪残差是连续值。

(c) 计算叶节点最优输出：对每个叶节点，计算使该区域损失最小的输出 γ_jm：

对于平方损失，最优输出就是该区域伪残差的均值；对于其他损失，需要一维搜索（牛顿法或二分法）求最优。

(d) 更新模型：将当前树的输出乘以学习率 ν 后加到模型上：

其中 ν 是学习率（shrinkage），ν ∈ (0, 1]。学习率的作用是防止过拟合——每棵树只学习一部分，多棵树累加。实践中通常取 ν=0.01 或 0.1，同时相应增加迭代次数。Friedman 的实验表明，小学习率 + 多迭代次数 通常比 大学习率 + 少迭代次数 泛化性能更好。

平方损失的特例：

对于平方损失，负梯度恰好等于残差 r = y - F，这就是为什么很多资料说"GBDT 每轮拟合残差"。但这只是平方损失的特例，不能推广到一般损失函数。理解"负梯度"而非"残差"，是掌握 GBDT 本质的关键——XGBoost、LightGBM 等改进算法都是在损失函数的二阶泰勒展开上做文章，本质上还是梯度提升框架。

实现中的关键：

• 回归树分裂准则：使用 MSE（均方误差）作为分裂准则，选择使分裂后 MSE 下降最大的特征和阈值。注意这里拟合的是伪残差而不是原始标签。

• 叶节点输出：对于平方损失，叶节点输出就是该区域伪残差的均值；对于其他损失，需要一维搜索求最优。这是 GBDT 适配任意损失函数的关键步骤。

• 早期停止：监控验证集损失，连续 N 轮不提升则停止，防止过拟合。GBDT 对迭代次数很敏感，迭代太少欠拟合，太多过拟合，早期停止是必要的。

2.3 决策树：CART 算法

分类与回归树（CART，Classification and Regression Tree）由 Breiman 等人于 1984 年提出，是一种二叉树结构，每个内部节点做二元分裂（是/否，大于/小于等于）。CART 既可以做分类（分类树），也可以做回归（回归树），是随机森林和 GBDT 的基础组件。

分类树分裂准则——Gini 不纯度：

Gini 不纯度衡量一个节点的"混乱程度"。如果节点中所有样本都属于同一类，Gini = 0（最纯）；如果各类样本均匀分布，Gini 最大。

其中 p_k 是节点中第 k 类样本的比例。分裂后的 Gini 指数是两个子节点 Gini 的加权平均（按样本数加权）：

选择使 Gini_split 最小的特征和分裂点。注意 CART 用 Gini 而不是信息增益/信息增益率（ID3/C4.5 用的），Gini 的计算不需要对数，速度更快，且与信息熵在多数情况下结果一致。

回归树分裂准则——MSE：

其中 ȳ 是节点中所有样本标签的均值。选择使分裂后 MSE 下降最大的特征和阈值。回归树的叶节点输出是该区域样本标签的均值。

实现细节：

• 连续特征处理：对特征值排序，尝试所有相邻值的中点作为分裂阈值。时间复杂度 O(n log n)（排序）+ O(n)（遍历阈值），可以用预排序优化。

• 离散特征处理：尝试所有二元划分（子集 vs 补集）。对于有 m 个取值的离散特征，有 2^(m-1) - 1 种划分，m 大时计算量大，可以用启发式策略。

• 预剪枝：限制最大深度、最小样本分裂数、最小叶节点样本数、最小不纯度下降。预剪枝在分裂前就阻止不必要的分裂，计算效率高，但可能欠拟合。

• 后剪枝：先生成完整的树，再基于验证集的代价复杂度剪枝（CCP，Cost-Complexity Pruning）。后剪枝通常比预剪枝效果好，但计算开销大。

三、精度验证：与sklearn对比

所有算法都通过了与scikit-learn的精度对比验证。验证脚本使用相同的数据集和随机种子，分别训练自定义实现和sklearn实现，对比核心指标。

核心算法验证结果（7/7全部通过）：

============================================================
  Algorithm Correctness Test (vs sklearn)
============================================================
1. Linear Regression   | Ours R2=0.9904 | SK R2=0.9904 | PASS
2. Logistic Regression | Ours Acc=0.9600 | SK Acc=0.9600 | PASS
3. Decision Tree       | Ours Acc=0.9500 | SK Acc=0.9200 | PASS
4. KNN                 | Ours Acc=0.8900 | SK Acc=0.8900 | PASS
5. Naive Bayes         | Ours Acc=0.9100 | SK Acc=0.9100 | PASS
6. K-Means             | Ours inertia=2460.4 | SK inertia=2460.4 | ratio=1.000 | PASS
7. PCA                 | Ours var_sum=0.9855 | SK var_sum=0.9855 | PASS
============================================================
Results: 7/7 tests passed

SVM & GBDT 验证（精度差异0.0000）：

--- SVM (Linear Kernel) ---
SVM trained: 43 support vectors, 95 iterations
  Ours accuracy: 0.8750 | SKlearn accuracy: 0.8750 | Difference: 0.0000 | PASS
​
--- SVM (RBF Kernel) ---
SVM trained: 64 support vectors, 112 iterations
  Ours accuracy: 0.8250 | SKlearn accuracy: 0.8250 | Difference: 0.0000 | PASS
​
--- GBDT ---
  Iter 20/50, train acc: 0.9437
  Iter 40/50, train acc: 0.9500
  Ours accuracy: 0.9000 | SKlearn accuracy: 0.9000 | Difference: 0.0000 | PASS

K-Means的inertia（簇内平方和）与sklearn完全一致，说明聚类中心收敛到了同一个最优解。

四、算法可视化

4.1 SVM：决策边界与支持向量

线性SVM在二维数据上的决策边界、间隔边界和支持向量可视化：

图中实线是决策边界 w^T x + b = 0，虚线是间隔边界 w^T x + b = ±1，红色圆圈标注的是支持向量（α_i > 0 的样本）。可以看到，决策边界完全由支持向量决定，非支持向量的移除不会改变决策边界。

4.2 K-Means：聚类过程

K-Means从随机初始化到收敛的完整过程：

• Step 1：随机选择3个初始中心（K-Means++会选择相距较远的点）

• Step 2：第一次迭代——将每个样本分配到最近的中心，然后更新中心为簇内均值

• Step 3：收敛——中心不再移动，inertia（簇内平方和）达到局部最优

K-Means的收敛性是有保证的：每次分配和更新都会使inertia单调不增，而inertia有下界，因此必然收敛。

4.3 PCA：降维可视化

三维数据降到二维的PCA过程，红色箭头是主成分方向：

左图是原始三维数据，红色箭头是协方差矩阵的特征向量方向（主成分），箭头长度对应特征值大小。右图是投影到前两个主成分后的二维数据，PC1和PC2的方差贡献率分别为67.3%和27.6%，累计贡献率94.9%，说明用两个维度就能保留绝大部分信息。

PCA 的核心步骤：

1. 数据中心化：X_centered = X - μ（减去每列均值）

2. 计算协方差矩阵：

1. 特征值分解：

1. 选择 Top-k 特征向量组成投影矩阵 W（按特征值从大到小排序）

2. 投影：X_reduced = X_centered W

五、配套工具链

除了核心算法，还实现了完整的机器学习工具链：

5.1 特征工程

• 缺失值处理：数值型用中位数填充，类别型用众数填充

• 编码：OneHot编码、Label编码、Target编码（带平滑）

• 缩放：StandardScaler、MinMaxScaler、RobustScaler（对异常值鲁棒）

• 特征构造：多项式特征、交叉特征、分箱（等宽/等频/卡方分箱）

5.2 模型评估

• 分类指标：准确率、精确率、召回率、F1、ROC-AUC、混淆矩阵、分类报告

• 回归指标：MSE、RMSE、MAE、R²、MAPE

• 交叉验证：K折交叉验证、分层K折、时间序列分割

• 学习曲线：训练集vs验证集的学习曲线，诊断偏差-方差

5.3 超参优化

• 网格搜索：遍历所有参数组合

• 随机搜索：从参数分布中随机采样，效率更高

• 贝叶斯优化：高斯过程代理模型 + 采集函数（EI/UCB），用更少的评估找到更优解

5.4 模型解释

• 置换重要性：打乱某个特征后模型性能下降程度

• 部分依赖图（PDP）：特征变化对预测结果的边际影响

• SHAP-like值：基于博弈论的特征贡献度分配

5.5 AutoML

自动模型选择 + 超参优化流水线，自动尝试多种算法和参数组合，输出最优模型。

六、工程实现细节

6.1 数值稳定性

• Sigmoid 溢出：Sigmoid 函数定义为：

直接计算时，z 很大（如 z=1000）会下溢为 0，z 很小（z=-1000）时 e^(-z) 会溢出为 inf。实现中使用 np.clip(z, -500, 500) 限制输入范围，或者用 log-sum-exp 技巧稳定计算交叉熵损失。

• Softmax：减去最大值后再计算指数，避免溢出。

• 矩阵求逆：优先使用np.linalg.solve而非np.linalg.inv，数值更稳定。

6.2 向量化优化

• 避免Python循环，用NumPy广播和矩阵运算替代

• KNN的距离计算用np.sum(X**2, axis=1)[:, None] + np.sum(Y**2, axis=1) - 2*X@Y.T一次计算所有距离

• 决策树分裂用预排序和向量化的MSE计算，避免逐样本循环

6.3 内存效率

• SVM的核矩阵用float32存储，必要时用分块计算

• 随机森林的每棵树独立训练，用生成器逐棵预测避免同时存储所有树的中间结果

七、CI自动化测试

项目配置了GitHub Actions CI，每次提交自动运行：

1. flake8代码规范检查：行长度≤120，忽略E203（切片前空格）和W503（换行符前运算符）

2. 算法正确性验证：运行verify_algorithms.py，7个核心算法vs sklearn

3. SVM & GBDT验证：运行verify_svm_gbdt.py，SVM线性核/RBF核 + GBDT

4. 全量单元测试：运行test_all.py，覆盖所有算法和工具链

5. 多版本兼容：Python 3.9 / 3.10 / 3.11 三个版本全部测试

八、项目地址

📦 GitHub：https://github.com/CodeHearth-hub/ml-from-scratch

包含完整源码、测试脚本、示例代码和文档。欢迎Star，有问题欢迎提Issue。