经典机器学习

经典机器学习

经典 ML 算法从数据中学习模式，而无需显式编程，它们使用解析解或启发式搜索，而非梯度下降。本文件涵盖朴素贝叶斯、k-NN、决策树、随机森林、SVM、k-means 聚类和 PCA。

• 机器学习研究的是这样一类算法：它们通过从数据中学习来提升自己在某项任务上的表现，而不是被人显式地写死规则。你不必写"如果收入 > 5 万且年龄 < 30 就批准贷款"，而是把成千上万条过往贷款决策交给算法，让它自己琢磨出其中的规律。

• 机器学习大致分三种范式。**监督学习（supervised learning）**使用带标签的数据，即每个输入都有一个已知的正确输出，算法学习的是从输入到输出的映射。**无监督学习（unsupervised learning）**面对的是无标签数据，目标是发现其中隐藏的结构，比如簇或压缩表示。**强化学习（reinforcement learning）**则通过试错学习，在环境中采取行动并据此获得奖励或惩罚（详见第 4 节）。

• 在监督学习内部，**分类（classification）预测离散类别（是不是垃圾邮件、猫还是狗），而回归（regression）**预测连续值（房价、明天气温）。两者的边界并不总是泾渭分明：逻辑回归（logistic regression）名字里带"回归"，做的却是分类。

• 概率模型中一个关键区分是生成式与判别式（generative vs discriminative）。生成式模型学习联合分布 P(x, y)，也就是说它理解数据本身是如何生成的，能够生成新样本。判别式模型则直接学习 P(y \mid x)，只关注类别之间的边界。朴素贝叶斯是生成式的；逻辑回归（第 2 节）是判别式的。生成式模型更灵活，但更难训练好；判别式模型在数据充足时往往分类精度更高。

• **朴素贝叶斯（Naive Bayes）**是最简单也最有效的分类器之一。它直接套用贝叶斯定理（来自第 5 章）：

• 所谓"朴素"，是一个很强的独立性假设：它把每个特征都看作在给定类别下相互独立。如果你在判断邮件是否为垃圾邮件，朴素贝叶斯会假设——一旦已知邮件是垃圾邮件——"free"这个词出现与否和"winner"这个词出现与否毫无关系。这在现实中几乎从不成立，但分类器依然出奇地好用。

• 由于 P(x) 对所有类别都相同，分类就简化为挑选使分子最大的那个类别：

• 先验 P(C_k) 就是训练集中每个类别所占的比例。似然 P(x_i \mid C_k) 取决于你有什么样的特征，由此衍生出三种常见变体。

• **多项式朴素贝叶斯（Multinomial Naive Bayes）**专为计数数据设计，比如文档中的词频。每个特征 x_i 表示词 i 出现的次数，似然服从多项式分布。它是文本分类、情感分析和垃圾邮件过滤的标准选择。

• **高斯朴素贝叶斯（Gaussian Naive Bayes）**假设每个特征在每个类别内服从正态分布。你从训练数据中估计出类别 k 下特征 i 的均值 \mu_{ik} 和方差 \sigma_{ik}^2，然后计算：

• 当你的特征是身高、体重或传感器读数这类连续量时，这是自然的选择。

• **伯努利朴素贝叶斯（Bernoulli Naive Bayes）**建模的是二值特征：每个特征要么出现（1）要么不出现（0）。它不数一个词出现了几次，只记录它出没出现。这种做法适合短文本或二值特征向量。

• 一个实际问题是：如果某个特征值在训练数据中从未与某个类别同时出现，似然就会变成零；而由于所有项都相乘，整个后验就会整个塌缩为零。**拉普拉斯平滑（Laplace smoothing）**通过给每个"特征-类别"组合加一个小计数（通常是 1）来修复这一点：

• 这里 \alpha 是平滑参数（通常取 1），V 是该特征可能取值的个数。这样就保证了没有任何概率恰好为零。

• **决策树（decision tree）**走的是完全不同的路子。它不算概率，而是通过一连串是非题把特征空间切分开。想象一下"二十个问题"这个游戏：每一步你都要问那个最能缩小可能范围的问题。

• 树从根节点出发，带着所有训练样本。在每个内部节点上，它选一个特征和一个阈值来做切分（比如"年龄是否 < 30？"）。样本根据答案流向左子树或右子树。如此递归下去，直到叶子节点——叶子保存着预测结果：分类时取多数类，回归时取均值。

• 关键问题来了：该按哪个特征切分？我们希望切分出的子节点尽量"纯净"，即绝大多数样本都属于同一类。衡量不纯度有两个常用指标：基尼不纯度（Gini impurity）和熵（entropy）。

• 基尼不纯度衡量的是：如果按节点中的分布随机给一个样本打标签，它被错分的概率有多大：

• 如果一个节点完全纯净（全是同一类），基尼为 0。如果各类占比均衡（比如两类各占一半），基尼达到最大值 0.5。

• 熵（来自第 5 章的信息论部分）衡量的是平均"意外程度"：

• 纯净节点的熵为 0。完全均衡的二类节点熵为 1 比特。实际中，基尼和熵得到的树非常接近；基尼略快一点，因为它不用算对数。

• **信息增益（information gain）**是一次切分带来的不纯度下降。对于把集合 S 分成 S_L 和 S_R 的切分：

• 算法在每个节点贪心地选择信息增益最高的切分。这是一种局部最优而非全局最优的策略，但实际效果很好。

• 回归树的工作方式相同，只是叶子预测的是连续值（到达该叶子的样本的均值），切分准则用的是方差缩减，而非基尼或熵。

• 如果放任不管，决策树会一直切分下去，直到每个叶子都纯净——这几乎等同于把训练数据背下来，是严重的过拟合。**剪枝（pruning）**就是对付这个问题的。预剪枝在长树之前就设好限制：最大深度、每个叶子的最少样本数、或进行一次切分所需的最小信息增益。后剪枝则先把整棵树长完，再删掉那些在验证集上不能提升性能的分支。

• 单棵决策树容易解释，但往往不稳定：数据的小小变化就可能产生一棵截然不同的树。**集成方法（ensemble methods）**把许多模型组合起来，得到比任何单一模型都更好的预测。

• 核心思想是"群体的智慧"。如果你问 100 个平庸的分类器然后多数表决，只要这些分类器犯的错相对独立，集成结果就可以非常出色。

• Bagging（bootstrap aggregating，自助聚合）在数据的不同随机子集上训练多个模型，这些子集是有放回采样（bootstrap sample）得到的。每个模型大约能看到原始数据的 63%。预测时，回归取平均，分类取多数表决。由于每个模型看到的数据不同，它们犯的错也不同，求平均就能消掉大部分方差。

• **随机森林（Random Forest）**是把 bagging 用在决策树上，还多加了一招：每次切分时，树只考虑一个随机选出的特征子集（通常是从 d 个特征里选 \sqrt{d} 个）。这进一步降低了树之间的相关性，让集成更强大。随机森林是整个机器学习中最可靠的"开箱即用"分类器之一。

• Boosting 的哲学正好相反。它不是让模型彼此独立地训练，而是串行训练，每一个新模型都把注意力集中在前面模型搞错的样本上。

• AdaBoost（Adaptive Boosting，自适应提升）为每个训练样本维护一个权重。一开始所有权重相等。训练完一个弱学习器（通常是很浅的决策树，称为"树桩"）后，被错分的样本权重提高，这样下一个学习器就会更关注它们。最终预测是所有学习器的加权投票，表现更好的学习器话语权更大：

• 学习器 t 的权重 \alpha_t 取决于它的错误率 \epsilon_t：

• 错误率低的学习器获得很大的正权重；表现仅相当于随机猜测（\epsilon = 0.5）的则权重为零。

• **梯度提升（Gradient Boosting）**推广了这一思想。它不再给样本重新加权，而是训练每个新模型去预测当前集成所产生的残差误差（损失函数的负梯度）。对于平方误差损失，残差就是预测值与目标值之差。基于决策树的梯度提升（GBDT）是众多结构化数据竞赛获胜方案背后的核心（XGBoost、LightGBM、CatBoost 都是流行的实现）。

• 关键对比：bagging 降低的是方差（把噪声平均掉），而 boosting 降低的是偏差（纠正系统性错误）。bagging 在单模型过拟合时效果最好；boosting 在单模型欠拟合时效果最好。

• 转到无监督学习，k-means 聚类是最简单也最常用的聚类算法。给定 n 个数据点和目标簇数 K，它通过最小化每个点到其簇中心的距离总和，把每个点分到 K 个组之一。

• 算法交替执行两步。先是分配：把每个点分到最近的中心。再是更新：把每个中心更新为分配给它的所有点的均值。如此反复，直到分配不再变化。这保证会收敛，因为每一步簇内总距离都会下降（或保持不变）。

• 形式上，k-means 最小化的是簇内平方和，称为惯性（inertia）：

• 其中 \mu_k 是簇 C_k 的中心。

• k-means 对初始化很敏感。糟糕的初始中心可能导致很差的局部极小。k-means++ 初始化策略随机选第一个中心，然后按与最近已有中心的平方距离成比例的概率挑选后续每个中心。这样能把初始中心摊开，几乎总能得到更好的结果。

• 怎么选 K？有两个常用工具。**肘部法则（elbow method）**画出惯性随 K 变化的曲线，寻找那个"拐点"——再加簇也没多大帮助的地方。**轮廓系数（silhouette score）**衡量一个点与自己所在簇的相似程度相对于最近的其他簇有多高，取值从 -1（分错簇）到 +1（分得很好）。所有点的平均轮廓系数给出了簇质量的总体度量。

• k-means 有局限：它假设簇是大小相近的球形，并且做"硬"分配（每个点恰好属于一个簇）。**高斯混合模型（Gaussian Mixture Models, GMM）**放开了这两个限制。

• GMM 把数据建模为 K 个高斯分布的混合，每个都有自己的均值 \mu_k、协方差 \Sigma_k 和混合权重 \pi_k（权重之和为 1）：

• 取代硬分配的是，每个点得到一个软分配：它属于每个簇的概率（称为"责任"）。一个落在两个高斯边界附近的点，可能是 60% 属于簇 A、40% 属于簇 B。

• GMM 用**期望最大化算法（Expectation-Maximisation, EM）**来拟合，它也像 k-means 一样交替执行两步。E 步计算责任度：对每个点，它来自各个高斯的概率是多少？M 步更新参数：给定责任度，最优的均值、协方差和混合权重是什么？EM 保证每次迭代都让数据似然增加，并收敛到一个局部极大。

• k-means 其实是带 GMM 的 EM 的一个特例：它对应于协方差相等且为球形、责任度为硬（0/1）的高斯。

• **支持向量机（Support Vector Machines, SVM）从几何视角来做分类。给定两个线性可分的类别，有无数个超平面能把它们分开。SVM 找的是那个最大间隔（maximum margin）**的，也就是超平面到每类最近数据点之间间隙最大的那个。

• 那些正好踩在间隔边缘上的最近点，称为支持向量（support vectors）。它们是定义边界唯一重要的点；你可以删掉所有其他训练点，得到的还是同一个超平面。

• 对于线性分类器 f(x) = w \cdot x + b，找最大间隔等价于求解：

• 这是一个凸二次规划问题，所以有唯一的全局解（不用担心局部极小）。

• 真实数据很少能完美分开。**软间隔 SVM（soft-margin SVM）**通过引入松弛变量 \xi_i \geq 0，允许一些点违反间隔：

• 超参数 C 控制权衡：C 大会重罚错分（拟合更紧，有过拟合风险），C 小则允许更多违反（间隔更宽，正则化更强）。

• SVM 最强大的特性是核技巧（kernel trick）。许多在原始特征空间中线性不可分的数据，映射到更高维空间后就变得可分了。核技巧让你能在那个高维空间里计算内积，却不必显式地计算这个变换。

• 核函数 K(x_i, x_j) = \phi(x_i) \cdot \phi(x_j) 替换掉 SVM 优化中的每一个内积。最流行的核是径向基函数（Radial Basis Function, RBF）核：

• RBF 核隐式地把数据映射到一个无穷维空间。参数 \gamma 控制单个训练点的影响能延伸多远：\gamma 大意味着每个点只影响它的近邻（有过拟合风险），\gamma 小则给出更平滑的边界。

• 其他常见核包括多项式核 K(x_i, x_j) = (x_i \cdot x_j + c)^d 和线性核 K(x_i, x_j) = x_i \cdot x_j（后者就是不做任何变换的标准 SVM）。

• 实践中，在深度学习接管一切之前，带 RBF 核的 SVM 是占统治地位的分类器。它在中小规模数据集上依然好用，尤其是当特征数相对于样本数很大时。

• SVM 与第 2 章（矩阵）的联系很深。这个优化通常在它的对偶形式下求解，此时解只依赖于训练样本之间的内积——这正是核技巧得以成立的原因。整个算法都运行在内积和线性代数的语言里。

• 总结一下经典 ML 工具箱：

编程练习（使用 CoLab 或 notebook）

1. 从零实现高斯朴素贝叶斯。在合成的两类二维数据上训练，并可视化决策边界。与 scikit-learn 的实现做对比。

import jax.numpy as jnp
import matplotlib.pyplot as plt
from sklearn.datasets import make_classification

# 生成合成数据
X, y = make_classification(n_samples=300, n_features=2, n_redundant=0,
                           n_informative=2, n_clusters_per_class=1, random_state=42)
X, y = jnp.array(X), jnp.array(y)

# 从零拟合高斯朴素贝叶斯
classes = jnp.unique(y)
params = {}
for c in classes:
    c = int(c)
    mask = y == c
    X_c = X[mask]
    params[c] = {
        'mean': jnp.mean(X_c, axis=0),
        'var': jnp.var(X_c, axis=0),
        'prior': jnp.sum(mask) / len(y)
    }

def gaussian_log_likelihood(x, mean, var):
    return -0.5 * jnp.sum(jnp.log(2 * jnp.pi * var) + (x - mean)**2 / var)

def predict(X):
    preds = []
    for x in X:
        log_posts = []
        for c in [0, 1]:
            log_post = jnp.log(params[c]['prior']) + gaussian_log_likelihood(
                x, params[c]['mean'], params[c]['var'])
            log_posts.append(log_post)
        preds.append(jnp.argmax(jnp.array(log_posts)))
    return jnp.array(preds)

# 决策边界可视化
xx, yy = jnp.meshgrid(jnp.linspace(X[:,0].min()-1, X[:,0].max()+1, 200),
                       jnp.linspace(X[:,1].min()-1, X[:,1].max()+1, 200))
grid = jnp.column_stack([xx.ravel(), yy.ravel()])
zz = predict(grid).reshape(xx.shape)

plt.figure(figsize=(8, 6))
plt.contourf(xx, yy, zz, alpha=0.3, cmap='coolwarm')
plt.scatter(X[y==0, 0], X[y==0, 1], c='#3498db', label='Class 0', edgecolors='k', s=20)
plt.scatter(X[y==1, 0], X[y==1, 1], c='#e74c3c', label='Class 1', edgecolors='k', s=20)
plt.title("Gaussian Naive Bayes Decision Boundary")
plt.legend()
plt.grid(alpha=0.3)
plt.show()

accuracy = jnp.mean(predict(X) == y)
print(f"Training accuracy: {accuracy:.2%}")
​

2. 构建一棵用基尼不纯度切分的决策树。实现单个节点的切分逻辑，展示信息增益如何选出最佳的特征和阈值。

import jax.numpy as jnp

def gini_impurity(y):
    """标签数组的基尼不纯度。"""
    classes, counts = jnp.unique(y, return_counts=True)
    probs = counts / len(y)
    return 1.0 - jnp.sum(probs ** 2)

def information_gain(y, left_mask):
    """按布尔掩码把 y 切成左/右两部分所带来的信息增益。"""
    parent_gini = gini_impurity(y)
    left_y, right_y = y[left_mask], y[~left_mask]
    n = len(y)
    if len(left_y) == 0 or len(right_y) == 0:
        return 0.0
    child_gini = (len(left_y)/n) * gini_impurity(left_y) + \
                 (len(right_y)/n) * gini_impurity(right_y)
    return float(parent_gini - child_gini)

def best_split(X, y):
    """寻找使信息增益最大的特征和阈值。"""
    best_ig, best_feat, best_thresh = -1, None, None
    for feat in range(X.shape[1]):
        thresholds = jnp.unique(X[:, feat])
        for thresh in thresholds:
            mask = X[:, feat] <= float(thresh)
            ig = information_gain(y, mask)
            if ig > best_ig:
                best_ig, best_feat, best_thresh = ig, feat, float(thresh)
    return best_feat, best_thresh, best_ig

# 示例：合成数据
from sklearn.datasets import make_classification
X, y = make_classification(n_samples=100, n_features=4, n_redundant=0, random_state=0)
X, y = jnp.array(X), jnp.array(y)

feat, thresh, ig = best_split(X, y)
print(f"Best split: feature {feat}, threshold {thresh:.3f}, info gain {ig:.4f}")
print(f"Parent Gini: {gini_impurity(y):.4f}")
mask = X[:, feat] <= thresh
print(f"Left Gini:   {gini_impurity(y[mask]):.4f} ({int(jnp.sum(mask))} samples)")
print(f"Right Gini:  {gini_impurity(y[~mask]):.4f} ({int(jnp.sum(~mask))} samples)")
​

3. 从零实现带 k-means++ 初始化的 k-means。对一个合成数据集聚类，并可视化每次迭代后的簇。

import jax
import jax.numpy as jnp
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

# 生成合成簇
X, y_true = make_blobs(n_samples=300, centers=4, cluster_std=0.8, random_state=42)
X = jnp.array(X)

def kmeans_plus_plus_init(X, K, key):
    """k-means++ 初始化。"""
    n = X.shape[0]
    idx = jax.random.randint(key, (), 0, n)
    centroids = [X[idx]]
    for _ in range(1, K):
        dists = jnp.min(jnp.stack([jnp.sum((X - c)**2, axis=1) for c in centroids]), axis=0)
        probs = dists / jnp.sum(dists)
        key, subkey = jax.random.split(key)
        idx = jax.random.choice(subkey, n, p=probs)
        centroids.append(X[idx])
    return jnp.stack(centroids)

def kmeans(X, K, max_iters=20, key=jax.random.PRNGKey(0)):
    centroids = kmeans_plus_plus_init(X, K, key)
    history = [centroids]
    for _ in range(max_iters):
        # 分配步
        dists = jnp.stack([jnp.sum((X - c)**2, axis=1) for c in centroids])
        labels = jnp.argmin(dists, axis=0)
        # 更新步
        new_centroids = jnp.stack([
            jnp.mean(X[labels == k], axis=0) for k in range(K)
        ])
        history.append(new_centroids)
        if jnp.allclose(centroids, new_centroids):
            break
        centroids = new_centroids
    return labels, centroids, history

K = 4
labels, centroids, history = kmeans(X, K)

# 绘制最终结果
colors = ['#3498db', '#e74c3c', '#27ae60', '#9b59b6']
plt.figure(figsize=(8, 6))
for k in range(K):
    mask = labels == k
    plt.scatter(X[mask, 0], X[mask, 1], c=colors[k], s=20, alpha=0.6)
    plt.scatter(centroids[k, 0], centroids[k, 1], c=colors[k], marker='X',
                s=200, edgecolors='k', linewidths=1.5)
plt.title(f"K-Means Clustering (K={K}, {len(history)-1} iterations)")
plt.grid(alpha=0.3)
plt.show()

# 计算惯性
inertia = sum(jnp.sum((X[labels == k] - centroids[k])**2) for k in range(K))
print(f"Final inertia: {inertia:.2f}")
​

4. 演示核技巧。通过把核矩阵与多项式核的显式特征映射做对比，说明 RBF 核确实在高维空间里计算内积。

import jax.numpy as jnp

# 简单的二维数据
X = jnp.array([[1.0, 2.0], [3.0, 4.0], [5.0, 6.0]])

# 多项式核：K(x,y) = (x·y + 1)^2
def poly_kernel(X, degree=2, c=1.0):
    return (X @ X.T + c) ** degree

# 二维输入的 2 次显式特征映射：(1, sqrt(2)*x1, sqrt(2)*x2, x1^2, x2^2, sqrt(2)*x1*x2)
def poly_features(X):
    x1, x2 = X[:, 0], X[:, 1]
    return jnp.column_stack([
        jnp.ones(len(X)),
        jnp.sqrt(2) * x1,
        jnp.sqrt(2) * x2,
        x1 ** 2,
        x2 ** 2,
        jnp.sqrt(2) * x1 * x2
    ])

K_trick = poly_kernel(X)
phi = poly_features(X)
K_explicit = phi @ phi.T

print("Kernel trick (polynomial degree 2):")
print(K_trick)
print("\nExplicit feature map dot products:")
print(K_explicit)
print(f"\nMatrices match: {jnp.allclose(K_trick, K_explicit)}")

# RBF 核：不存在有限的显式映射
def rbf_kernel(X, gamma=0.5):
    sq_dists = jnp.sum(X**2, axis=1, keepdims=True) + \
               jnp.sum(X**2, axis=1) - 2 * X @ X.T
    return jnp.exp(-gamma * sq_dists)

K_rbf = rbf_kernel(X)
print("\nRBF kernel matrix:")
print(K_rbf)
print("Diagonal is always 1 (a point is identical to itself)")
print("Off-diagonal entries decay with distance")
​