经典机器学习

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

• 机器学习研究的是通过学习数据来提升算法在特定任务上的表现，而非靠显式规则编程。与其写"若收入 > 50k 且年龄 < 30 则批准贷款"，你只需将成千上万的历史贷款决策交给算法，让它自行找出模式。

• 机器学习有三大范式。监督学习使用带标签的数据，即每个输入都配有已知的正确输出。算法学习从输入到输出的映射。无监督学习处理无标签数据，试图发现隐藏结构，如聚类或压缩表示。强化学习通过试错学习，根据在环境中采取的行动接收奖励或惩罚（在文件04中介绍）。

• 在监督学习中，分类预测离散类别（垃圾邮件或非垃圾邮件、猫或狗），而回归预测连续值（房价、明日温度）。两者的界限并非总是泾渭分明：逻辑回归虽名为"回归"，但执行的是分类任务。

• 概率模型中一个关键区分是生成式与判别式。生成式模型学习联合分布 \(P(x, y)\)，这意味着它理解数据本身的生成方式，可以产生新的样本。判别式模型直接学习 \(P(y \mid x)\)，仅关注类别之间的边界。朴素贝叶斯是生成式的；逻辑回归（文件02）是判别式的。生成式模型更灵活但更难训练好；判别式模型在数据充足时通常分类准确度更高。

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

\[P(C_k \mid x) = \frac{P(x \mid C_k) \, P(C_k)}{P(x)}\]

• "朴素"之处在于一个强独立性假设：它假定在给定类别的条件下，每个特征相互独立。如果你在分类垃圾邮件，朴素贝叶斯假定一旦你知道某封邮件是垃圾邮件，其中出现"free"这个词就与出现"winner"这个词毫无关系。这在现实中几乎总是不成立，但该分类器依然出奇地好用。

• 由于 \(P(x)\) 对所有类别都相同，分类可简化为选择使分子最大化的类别：

\[\hat{y} = \arg\max_{k} \; P(C_k) \prod_{i=1}^{n} P(x_i \mid C_k)\]

• 先验概率 \(P(C_k)\) 就是每个类别在训练样本中所占的比例。似然 \(P(x_i \mid C_k)\) 取决于你拥有的特征类型，由此产生了三种常见的变体。

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

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

\[P(x_i \mid C_k) = \frac{1}{\sqrt{2\pi\sigma_{ik}^2}} \exp\!\left(-\frac{(x_i - \mu_{ik})^2}{2\sigma_{ik}^2}\right)\]

• 当特征是连续测量值（如身高、体重或传感器读数）时，这是自然而然的选择。

• 伯努利朴素贝叶斯建模二值特征：每个特征要么存在（1）要么不存在（0）。它不关注一个词出现了多少次，只跟踪它是否出现过。这适用于短文本或二值特征向量。

• 一个实际问题是：当某个特征值在训练数据中从未与某类别同时出现时，似然变为零。由于所有项相乘，整个后验概率就会崩塌为零。拉普拉斯平滑通过为每个特征-类别组合添加一个小计数（通常为1）来解决此问题：

\[P(x_i \mid C_k) = \frac{\text{count}(x_i, C_k) + \alpha}{\text{count}(C_k) + \alpha \cdot V}\]

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

• 决策树采用截然不同的方式。它不计算概率，而是通过一系列是/否问题来划分特征空间。可以类比"二十问"游戏：每一步你都问那个能最大程度缩小可能性范围的问题。

• 树从根节点开始，包含所有训练样本。在每个内部节点，它选择一个特征和一个阈值进行分裂（例如，"年龄是否 < 30？"）。样本根据答案流向左边或右边。这个过程递归进行，直到叶子节点，叶子节点保存预测值：分类问题取多数类别，回归问题取均值。

• 关键问题是：应该按哪个特征分裂？你希望产生的子节点尽可能"纯净"，即大多数样本属于同一类别。衡量不纯度的两个常用指标是基尼不纯度和熵。

• 基尼不纯度衡量的是如果按照节点中的分布进行标签，一个随机选取的样本被错误分类的概率：

\[\text{Gini}(S) = 1 - \sum_{k=1}^{K} p_k^2\]

• 如果节点完全纯净（全部属于同一类），基尼值为0。如果类别完全平衡（例如两类各占50/50），基尼值达到最大值0.5。

• 熵（来自第05章的信息论部分）衡量平均惊讶程度：

\[H(S) = -\sum_{k=1}^{K} p_k \log_2 p_k\]

• 纯节点的熵为0。完全平衡的二分类节点熵为1比特。在实践中，基尼和熵给出的树非常相似；基尼计算稍快，因为它避免了对数运算。

• 信息增益是通过一次分裂实现的不纯度减少量。对于将集合 \(S\) 划分为子集 \(S_L\) 和 \(S_R\) 的分裂：

\[\text{IG}(S, \text{split}) = H(S) - \frac{|S_L|}{|S|} H(S_L) - \frac{|S_R|}{|S|} H(S_R)\]

• 算法在每个节点贪婪地选择信息增益最高的分裂方式。这是局部最优策略，而非全局最优，但在实践中效果很好。

• 回归树的工作方式相同，但叶子节点预测连续值（到达该叶子的样本均值），分裂标准使用方差减小而非基尼或熵。

• 不加约束的话，决策树会不断分裂直到每个叶子都是纯净的，这本质上就是记忆训练数据。这是严重的过拟合。剪枝可以应对这个问题。预剪枝在生长之前设定限制：最大深度、每个叶子的最少样本数、或分裂所需的最小信息增益。后剪枝先生成完整的树，然后移除那些在验证集上不提升表现的分支。

• 单棵决策树易于解释，但往往不稳定：数据的微小变化可能产生完全不同的树。集成方法组合多个模型，获得比任何单模型都更好的预测。

• 核心思想是"群体智慧"。如果你让100个平庸的分类器投票，取多数票，集成结果可以非常出色，只要各个分类器犯的错误在一定程度上相互独立。

• Bagging（Bootstrap aggregating，自助聚合）在不同的随机数据子集上训练多个模型，子集通过有放回抽样（Bootstrap采样）得到。每个模型大约看到63%的原始数据。预测时，取输出的均值（回归）或多数投票（分类）。因为每个模型看到的数据不同，它们犯的错误也不同，通过平均可以抵消大部分方差。

• 随机森林是将Bagging应用于决策树，但多了一个技巧：每次分裂时，树只考虑一个随机的特征子集（通常是从 \(d\) 个特征中选 \(\sqrt{d}\) 个）。这进一步降低树之间的相关性，使集成更加强大。随机森林是整个机器学习中最可靠的现成分类器之一。

• Boosting采用相反的哲学。它不是独立训练模型，而是顺序训练，每个新模型专注于之前模型做错的那些样本。

• AdaBoost（自适应Boosting）为每个训练样本维护一个权重。初始时所有权重相等。在训练一个弱学习器（通常是一棵非常浅的决策树，称为"stump"）之后，被错误分类的样本获得更高的权重，让下一个学习器对它们给予更多关注。最终预测是所有学习器的加权投票，表现更好的学习器拥有更大的发言权：

\[H(x) = \text{sign}\!\left(\sum_{t=1}^{T} \alpha_t \, h_t(x)\right)\]

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

\[\alpha_t = \frac{1}{2} \ln\!\left(\frac{1 - \epsilon_t}{\epsilon_t}\right)\]

• 错误率低的学习器获得较大的正权重；表现与随机无异（\(\epsilon = 0.5\)）的学习器权重为零。

• 梯度提升推广了这一思想。不是重新加权样本，而是每个新模型被训练来预测当前集成模型的残差（损失函数的负梯度）。对于平方误差损失，残差就是预测值与目标值之间的差。带决策树的梯度提升（GBDT）是结构化数据竞赛中许多优胜方案背后的核心技术（XGBoost、LightGBM、CatBoost是流行实现）。

• 核心对比：Bagging降低方差（通过平均消除噪声），而Boosting降低偏差（修正系统性错误）。Bagging在单模型过拟合时效果最好；Boosting在单模型欠拟合时效果最好。

• 转向无监督学习，K-均值聚类是最简单也最广泛使用的聚类算法。给定 \(n\) 个数据点和目标簇数 \(K\)，它通过最小化每个点与其簇中心的距离之和，将每个点分配到 \(K\) 个组中的一个。

• 算法交替执行两个步骤。首先，分配每个点到最近的质心。其次，更新每个质心为其分配点的均值。重复进行，直到分配不再变化。这保证会收敛，因为总簇内距离在每一步都减少（或保持不变）。

• 形式化地，K-均值最小化簇内平方和，称为惯性：

\[J = \sum_{k=1}^{K} \sum_{x \in C_k} \|x - \mu_k\|^2\]

• 其中 \(\mu_k\) 是簇 \(C_k\) 的质心。

• K-均值对初始化敏感。糟糕的起始质心可能导致较差的局部最小值。K-Means++ 初始化策略先随机选择第一个质心，然后以与到最近已有质心的平方距离成正比的概率选择后续每个质心。这使初始中心分散开来，几乎总能给出更好的结果。

• 如何选择 \(K\)？有两个常用工具。肘部法绘制惯性 vs \(K\) 的曲线，寻找添加更多簇不再明显改善效果的"肘部"点。轮廓系数衡量一个点与自己所在簇的相似度与最近其他簇的相似度之比，范围从-1（分错簇）到+1（很好地聚类）。所有点的平均轮廓系数给出整体聚类质量的度量。

• K-均值的局限：它假设簇是球形的且大小大致相等，而且做"硬"分配（每个点恰好属于一个簇）。高斯混合模型（GMM）放宽了这两个限制。

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

\[P(x) = \sum_{k=1}^{K} \pi_k \, \mathcal{N}(x \mid \mu_k, \Sigma_k)\]

• 不再是硬分配，每个点得到软分配：它属于每个簇的概率（称为"责任度"）。一个靠近两个高斯分布边界的点可能是60%属于簇A，40%属于簇B。

• GMM使用期望最大化（EM）算法拟合，该算法交替执行两个步骤，与K-均值非常相似。E步计算责任度：对于每个点，它来自每个高斯分布的概率是多少？M步更新参数：给定责任度，最佳的均值、协方差和混合权重是什么？EM保证每次迭代都会增加数据似然，并收敛到局部最大值。

• K-均值实际上是带GMM的EM的一个特例：它对应的是协方差相等的球形高斯分布和硬（0/1）责任度。

• 支持向量机（SVM）从几何角度处理分类。给定两个线性可分的类别，存在无穷多个超平面可以将它们分开。SVM找出具有最大间隔的那个——即超平面到每类最近数据点之间的空隙尽可能大。

• 那些最近的点，即恰好位于间隔边缘上的点，称为支持向量。它们是唯一影响边界定义的点；你可以移除所有其他训练点，得到的仍然是同一个超平面。

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

\[\min_{w, b} \; \frac{1}{2}\|w\|^2 \quad \text{subject to} \quad y_i(w \cdot x_i + b) \geq 1 \; \text{for all } i\]

• 这是一个凸二次规划问题，因此有唯一全局解（无需担心局部最小值）。

• 实际数据很少完全可分离。软间隔SVM通过引入松弛变量 \(\xi_i \geq 0\) 允许一些点违反间隔约束：

\[\min_{w, b, \xi} \; \frac{1}{2}\|w\|^2 + C \sum_{i=1}^{n} \xi_i \quad \text{subject to} \quad y_i(w \cdot x_i + b) \geq 1 - \xi_i\]

• 超参数 \(C\) 控制权衡：大的 \(C\) 对错分类施加严厉惩罚（更紧地拟合，有过拟合风险），小的 \(C\) 允许更多违反（更宽的间隔，更强的正则化）。

• SVM最强大的特性是核技巧。许多在原始特征空间中不可线性分离的数据集，当映射到更高维空间后就变得可分离了。核技巧让你可以在高维空间中计算点积，而无需显式地进行变换。

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

\[K(x_i, x_j) = \exp\!\left(-\gamma \|x_i - x_j\|^2\right)\]

• 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与第02章（矩阵）有着深厚的联系。优化通常在其对偶形式中求解，其中解只依赖于训练样本之间的点积，这正是核技巧可行的原因。整个算法都在内积和线性代数的语言中运作。

• 经典机器学习工具包总结：

算法	类型	核心优势	核心弱点
朴素贝叶斯	监督学习（生成式）	快速，只需少量数据	独立性假设
决策树	监督学习	可解释	容易过拟合
随机森林	监督学习（集成）	稳健，超参数少	可解释性较差
梯度提升	监督学习（集成）	表格数据上最先进	较慢，需更多调参
K-均值	无监督学习（聚类）	简单，可扩展	假设球形簇
GMM	无监督学习（聚类）	软分配，形状灵活	对初始化敏感
SVM	监督学习	高维空间有效	大数据集上慢

编程任务（使用CoLab或notebook）

1. 从零实现高斯朴素贝叶斯。在合成2D数据上训练两个类别，可视化决策边界。与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='类别0', edgecolors='k', s=20)
   plt.scatter(X[y==1, 0], X[y==1, 1], c='#e74c3c', label='类别1', edgecolors='k', s=20)
   plt.title("高斯朴素贝叶斯决策边界")
   plt.legend()
   plt.grid(alpha=0.3)
   plt.show()
   
   accuracy = jnp.mean(predict(X) == y)
   print(f"训练准确率: {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"最佳分裂: 特征 {feat}, 阈值 {thresh:.3f}, 信息增益 {ig:.4f}")
   print(f"父节点基尼: {gini_impurity(y):.4f}")
   mask = X[:, feat] <= thresh
   print(f"左子基尼:   {gini_impurity(y[mask]):.4f} ({int(jnp.sum(mask))} 个样本)")
   print(f"右子基尼:  {gini_impurity(y[~mask]):.4f} ({int(jnp.sum(~mask))} 个样本)")
   

3. 使用K-Means++初始化从零实现K-均值。聚类合成数据集，可视化每次迭代的簇。

   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-均值聚类 (K={K}, {len(history)-1} 次迭代)")
   plt.grid(alpha=0.3)
   plt.show()
   
   # 计算惯性
   inertia = sum(jnp.sum((X[labels == k] - centroids[k])**2) for k in range(K))
   print(f"最终惯性: {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
   
   # 二维二次显式特征映射: (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("核技巧（二次多项式）:")
   print(K_trick)
   print("\n显式特征映射点积:")
   print(K_explicit)
   print(f"\n矩阵是否匹配: {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核矩阵:")
   print(K_rbf)
   print("对角线始终为1（一个点与自身完全相同）")
   print("非对角线元素随距离增加而衰减")