碎碎念念

小学期的大作业（为什么暑假要上课），再也不想写这种令人心情不愉快的作业了口牙！

本文结合小规模示例介绍以下内容：

  • 最小二乘线性回归
  • 决策树回归
  • 决策树分类
  • K-Means 聚类与 K-Means++ 初始化

图形界面使用 EasyX 完成。EasyX 在项目中主要负责绘制散点、曲线、聚类中心和处理按钮点击，本文不对其接口展开介绍。

回归、分类和聚类有什么区别

机器学习任务可以先从“有没有标签”和“要预测什么”两个角度理解。

任务 数据特点 输出结果 简单例子
回归 有标签 连续数值 根据学习时间预测成绩
分类 有标签 离散类别 判断鸢尾花属于哪个品种
聚类 无标签 自动形成的分组 将位置相近的数据点分成若干组

回归和分类都需要已知答案来训练，因此属于监督学习；聚类没有预先提供类别，因此属于无监督学习。

最小二乘线性回归

线性回归希望用一条直线描述输入 $x$ 与目标值 $y$ 之间的关系：

$$ y=ax+b $$

其中，$a$ 是斜率，$b$ 是截距。最小二乘法会选择一组 $a$ 和 $b$，使所有样本的残差平方和尽可能小：

$$ \sum_{i=1}^{n}\left[y_i-(ax_i+b)\right]^2 $$

平方可以避免正误差和负误差相互抵消，同时会让较大的误差受到更明显的惩罚。

斜率和截距可以直接计算：

$$ a=\frac{n\sum x_i y_i-\sum x_i\sum y_i} {n\sum x_i^2-(\sum x_i)^2} $$

$$ b=\frac{\sum y_i-a\sum x_i}{n} $$

一个简单例子

假设有三个样本：

$x$ $y$
1 2
2 3
3 5

可以得到：

$$ \sum x_i=6,\quad \sum y_i=10,\quad \sum x_i y_i=23,\quad \sum x_i^2=14 $$

代入公式：

$$ a=\frac{3\times23-6\times10}{3\times14-6^2}=1.5 $$

$$ b=\frac{10-1.5\times6}{3}=\frac{1}{3} $$

最终拟合直线约为：

$$ y=1.5x+0.33 $$

当输入 $x=4$ 时，模型预测：

$$ y=1.5\times4+0.33=6.33 $$

C++ 实现思路

程序只需遍历一次样本，累计四个统计量，再代入公式即可：

void LeastSquares(const std::vector<DataPoint>& points,
                  double& a, double& b) {
    if (points.empty()) {
        a = b = 0.0;
        return;
    }

    double sumX = 0.0;
    double sumY = 0.0;
    double sumXY = 0.0;
    double sumX2 = 0.0;

    for (const auto& point : points) {
        sumX += point.x;
        sumY += point.y;
        sumXY += point.x * point.y;
        sumX2 += point.x * point.x;
    }

    const double n = static_cast<double>(points.size());
    const double denominator = n * sumX2 - sumX * sumX;
    if (std::abs(denominator) < 1e-12) {
        a = b = 0.0;
        return;
    }

    a = (n * sumXY - sumX * sumY) / denominator;
    b = (sumY - a * sumX) / n;
}

该算法的时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。如果所有样本的 $x$ 都相同，公式分母为零，此时无法求出唯一斜率，需要单独处理。

决策树回归

线性回归只能拟合一条直线。当数据关系不是线性的，可以使用决策树回归。

决策树回归会不断选择阈值，把数据分成左右两部分。例如：

x <= 3.5 进入左子树
x > 3.5 进入右子树

每个叶节点保存该区域内所有目标值的平均值。预测时，从根节点出发，根据输入与阈值的关系向左或向右移动，最后返回叶节点的均值。

如何选择划分位置

回归树通常用均方误差衡量一组数据是否集中：

$$ \operatorname{MSE}(D)=\frac{1}{|D|} \sum_{i=1}^{|D|}(y_i-\bar y)^2 $$

对一个候选阈值，需要计算左右子集的加权误差：

$$ L=\frac{|D_L|}{|D|}\operatorname{MSE}(D_L) +\frac{|D_R|}{|D|}\operatorname{MSE}(D_R) $$

算法选择 $L$ 最小的阈值。

一个简单例子

假设数据如下：

$x$ $y$
1 2
2 2
3 8
4 8

候选阈值可以取相邻 $x$ 的中点，即 $1.5$、$2.5$ 和 $3.5$。

如果按 $x=2.5$ 划分：

  • 左侧目标值为 $\lbrace 2,2\rbrace$，均值为 $2$，MSE 为 $0$；
  • 右侧目标值为 $\lbrace 8,8\rbrace$，均值为 $8$，MSE 为 $0$；
  • 加权误差为 $0$。

因此，$2.5$ 是一个非常合适的阈值。模型得到的规则是：

x <= 2.5 时预测 2
x > 2.5 时预测 8

这也解释了为什么回归树的预测图像通常是阶梯形：同一个叶节点对应的输入区间会得到相同预测值。

前缀和优化

如果每测试一个阈值都重新遍历左右数据，计算开销会比较大。项目在排序后建立 $y$ 和 $y^2$ 的前缀和。

对任意区间，可以快速得到：

$$ \operatorname{MSE}=E[y^2]-E[y]^2 $$

这样每个候选切分位置的误差可以在 $O(1)$ 时间内计算。单个节点中，排序复杂度为 $O(n\log n)$，扫描候选阈值为 $O(n)$。

树深对结果的影响

树的最大深度决定模型复杂度：

  • 深度较小，划分次数少，曲线简单，可能欠拟合；
  • 深度较大，模型可以描述更多局部变化，但可能过拟合；
  • 设置最小分裂样本数，可以避免节点在样本很少时继续划分。

项目同时绘制浅层树和较深的树，可以直观看到预测曲线从粗略到细致的变化。

决策树分类

决策树分类与决策树回归的整体结构相似，区别主要在于：

  • 回归树预测连续数值，叶节点保存平均值；
  • 分类树预测离散类别，叶节点保存多数类别；
  • 回归树可以用 MSE 选择阈值；
  • 分类树可以用信息增益选择阈值。

项目使用 Iris 鸢尾花数据集。每个样本包含四个特征：

  • 花萼长度
  • 花萼宽度
  • 花瓣长度
  • 花瓣宽度

目标类别包括山鸢尾、变色鸢尾和维吉尼亚鸢尾。

信息熵

信息熵用于描述类别的混乱程度：

$$ H(D)=-\sum_{k=1}^{K}p_k\log_2p_k $$

其中，$p_k$ 是第 $k$ 类样本所占比例。

如果节点中的样本全部属于同一类，熵为 $0$；如果各类别数量接近，数据更加混乱，熵会更大。

一个简单例子

假设某节点中有四个样本：

A, A, B, B

两类比例都为 $\frac{1}{2}$，因此：

$$ H(D)=-\frac{1}{2}\log_2\frac{1}{2} -\frac{1}{2}\log_2\frac{1}{2}=1 $$

现在用某个特征进行划分，得到：

左侧：A, A
右侧：B, B

左右子集的熵都是 $0$。信息增益为：

$$ Gain(D)=H(D)-\frac{|D_L|}{|D|}H(D_L) -\frac{|D_R|}{|D|}H(D_R)=1 $$

这次划分完全分开了两个类别，因此效果很好。

建树过程

分类树的训练过程可以概括为：

  • 遍历每个特征；
  • 对特征值排序并去重；
  • 将相邻特征值的中点作为候选阈值；
  • 计算每个候选划分的信息增益；
  • 选择信息增益最大的特征和阈值；
  • 对左右子集递归执行相同操作。

当样本已经属于同一类别、达到最大深度或找不到有效划分时停止递归，并将当前节点设置为叶节点。

如何评价分类结果

最常用的基础指标是准确率：

$$ Accuracy=\frac{\text{预测正确的样本数}} {\text{样本总数}}\times100% $$

项目先使用固定随机种子打乱 Iris 数据，再按照 $8:2$ 划分训练集和测试集。固定随机种子可以让每次运行得到相同的数据划分，方便比较和复现实验结果。

训练准确率很高并不一定代表模型效果好，还需要观察测试准确率。如果训练准确率明显高于测试准确率，模型可能出现了过拟合。

K-Means 聚类

K-Means 用于在没有标签的情况下，将数据自动分成 $K$ 个簇。它希望同一簇内的样本彼此接近，不同簇的中心尽量分开。

算法的基本过程是：

  • 选择 $K$ 个初始聚类中心；
  • 将每个样本分配给距离最近的中心；
  • 对每个簇中的样本求平均，得到新中心；
  • 重复分配和更新，直到中心几乎不再移动。

二维空间中常用欧几里得距离：

$$ d(\mathbf{x},\boldsymbol{\mu})= \sqrt{\sum_{j=1}^{m}(x_j-\mu_j)^2} $$

一个简单例子

假设有六个二维点：

(1, 1), (1, 2), (2, 1)
(8, 8), (8, 9), (9, 8)

设置 $K=2$，初始中心选择 $(1,1)$ 和 $(8,8)$。

第一次分配后，前三个点更接近 $(1,1)$，后三个点更接近 $(8,8)$。随后计算两个簇的新中心：

$$ \boldsymbol{\mu}_1= \left(\frac{1+1+2}{3},\frac{1+2+1}{3}\right) =(1.33,1.33) $$

$$ \boldsymbol{\mu}_2= \left(\frac{8+8+9}{3},\frac{8+9+8}{3}\right) =(8.33,8.33) $$

再次分配时，各点所属簇不会改变，中心也保持稳定，算法便可以停止。

为什么需要 K-Means++

普通 K-Means 如果随机选出的初始中心过于接近，可能需要更多次迭代，也可能得到较差结果。

K-Means++ 的初始化方式是：

  • 随机选择第一个中心；
  • 计算每个样本到最近已有中心的距离平方；
  • 按距离平方作为权重选择下一个中心；
  • 重复以上过程，直到得到 $K$ 个中心。

距离现有中心越远的点，被选为新中心的概率越大。因此，初始中心通常会分布得更分散。

需要注意，这里是“按概率选择”，而不是每次直接选择最远点。这样可以降低异常值被固定选中的风险。

收敛与空簇处理

项目计算新旧中心之间的位移。如果最大位移不超过容差，就认为算法已经收敛：

$$ \max_k\left\lVert\boldsymbol{\mu}_k^{new} -\boldsymbol{\mu}_k^{old}\right\rVert\leq\varepsilon $$

如果某个簇没有分配到任何样本，就无法计算平均值。一个简单的处理方式是暂时保留该簇原来的中心。也可以重新选择距离其他中心较远的样本作为中心。

K-Means 的局限也比较明显：需要提前指定 $K$，对初始中心敏感，更适合近似球状、大小接近的簇，而且容易受到异常值影响。

可视化如何帮助理解算法

图形界面不改变算法本身，但能把抽象结果转换为更直观的图像：

  • 在线性回归中，同时绘制原始散点和拟合直线；
  • 在决策树回归中，用阶梯线展示分段常数预测；
  • 在决策树分类中，用不同颜色表示不同类别；
  • 在 K-Means 中，用颜色表示聚类标签，用特殊标记显示中心。

从数据坐标转换到屏幕坐标时，横坐标可以按比例映射：

$$ x_s=x_{left}+\frac{x-x_{min}}{x_{max}-x_{min}} (x_{right}-x_{left}) $$

由于屏幕纵坐标通常向下增大，纵坐标映射需要反向：

$$ y_s=y_{bottom}-\frac{y-y_{min}}{y_{max}-y_{min}} (y_{bottom}-y_{top}) $$

项目使用 EasyX 完成这些基础绘制和交互。对于理解算法而言，重点仍然是数据如何训练、模型如何预测以及结果为什么呈现出当前形态。

几种算法的对比

算法 任务 主要依据 结果特点
最小二乘线性回归 回归 残差平方和最小 一条连续直线
决策树回归 回归 加权 MSE 最小 分段常数、阶梯形
决策树分类 分类 信息增益最大 一组可解释的判断规则
K-Means 聚类 样本到中心的距离 自动形成若干数据簇

线性回归结构简单、计算速度快，但只能描述近似线性关系。决策树能够表达非线性规则，解释也比较直观，但树过深时容易过拟合。K-Means 不需要标签，实现简单，不过需要提前指定簇数，并且会受到数据分布和初始中心影响。

总结

通过手动实现这些基础算法，可以更清楚地看到机器学习的核心过程：

  • 回归是在寻找输入到连续数值的映射；
  • 分类是在学习区分不同类别的规则；
  • 聚类是在没有标签时发现数据内部的分组；
  • 损失函数或评价指标决定了算法如何选择更好的参数；
  • 停止条件和边界处理决定了程序是否可靠。

相比只调用现成接口，小规模示例更适合观察每一步计算。把算法结果绘制出来后，拟合直线、树的阶梯预测和聚类中心都会变得容易理解，这也是该 C++ 可视化项目最主要的学习价值。