第 5 周：决策树与随机森林

6.2.2 决策树与集成方法

**决策树（Decision Tree）**通过递归划分特征空间进行预测。主要算法包括ID3、C4.5和CART：

ID3：使用信息增益选择划分特征，仅处理离散特征
C4.5：ID3的改进版，处理连续特征，使用信息增益率
CART：既可分类也可回归，使用基尼指数或均方误差

信息熵衡量数据集的不确定性： $H(D) = -\sum_{k=1}^{K}p_k \log_2 p_k$

信息增益表示特征对降低不确定性的贡献： $Gain(D, A) = H(D) - \sum_{v \in Values(A)}\frac{|D^v|}{|D|}H(D^v)$

基尼指数衡量从数据集中随机抽取两个样本类别不一致的概率： $Gini(D) = 1 - \sum_{k=1}^{K}p_k^2$

**集成学习（Ensemble Learning）**通过组合多个基学习器提升性能：

**随机森林（Random Forest）**由Leo Breiman于2001年提出，是Bagging算法的扩展。它通过以下方式构建多样化的决策树集合：

Bootstrap采样：从原始数据中有放回地随机抽取样本构建训练集
随机特征选择：在每个节点分裂时，随机选择mtry个特征进行最优分裂点搜索

随机森林的最终预测通过投票（分类）或平均（回归）实现。其优势包括：降低过拟合风险、提供特征重要性评估、并行训练效率高。

**梯度提升树（Gradient Boosting）**通过串行训练弱学习器，每个新学习器拟合前面所有学习器的残差。XGBoost和LightGBM是该算法的优化实现，在数据竞赛中表现优异。

from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.ensemble import RandomForestClassifier, GradientBoostingClassifier

# 决策树
dt = DecisionTreeClassifier(max_depth=5, min_samples_split=10, random_state=42)
dt.fit(X_train, y_train)
print(f"Decision Tree Accuracy: {dt.score(X_test, y_test):.4f}")

# 随机森林
rf = RandomForestClassifier(n_estimators=100, max_depth=10, random_state=42)
rf.fit(X_train, y_train)
print(f"Random Forest Accuracy: {rf.score(X_test, y_test):.4f}")

# 特征重要性
importances = pd.DataFrame({
    'feature': range(X_train.shape[1]),
    'importance': rf.feature_importances_
}).sort_values('importance', ascending=False)

6.2.3 支持向量机

**支持向量机（Support Vector Machine, SVM）**由Vapnik于1995年提出，是强大的分类和回归算法。其核心思想是寻找最优超平面，使得两类样本之间的间隔最大化。

硬间隔SVM假设数据线性可分，优化问题为：

$\min_{w,b} \frac{1}{2}\|w\|^2$ $s.t. \quad y_i(w^T x_i + b) \geq 1, \quad i=1,...,m$

软间隔SVM通过引入松弛变量处理噪声和近似线性可分情况：

$\min_{w,b,\xi} \frac{1}{2}\|w\|^2 + C\sum_{i=1}^{m}\xi_i$ $s.t. \quad y_i(w^T x_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0$

其中 $C$ 为惩罚参数，控制对误分类的容忍度。

**核技巧（Kernel Trick）**将数据映射到高维特征空间，使非线性可分问题转化为线性可分。常用核函数包括：

线性核： $K(x_i, x_j) = x_i^T x_j$
多项式核： $K(x_i, x_j) = (\gamma x_i^T x_j + r)^d$
RBF核（高斯核）： $K(x_i, x_j) = \exp(-\gamma\|x_i - x_j\|^2)$
Sigmoid核： $K(x_i, x_j) = \tanh(\gamma x_i^T x_j + r)$

核技巧的关键在于：无需显式计算高维映射 $\phi(x)$ ，直接通过核函数计算内积 $K(x_i, x_j) = \phi(x_i)^T \phi(x_j)$ 。

from sklearn.svm import SVC

# 线性SVM
svm_linear = SVC(kernel='linear', C=1.0)
svm_linear.fit(X_train, y_train)

# RBF核SVM
svm_rbf = SVC(kernel='rbf', C=1.0, gamma='scale')
svm_rbf.fit(X_train, y_train)

print(f"Linear SVM Accuracy: {svm_linear.score(X_test, y_test):.4f}")
print(f"RBF SVM Accuracy: {svm_rbf.score(X_test, y_test):.4f}")

6.2.4 K近邻与朴素贝叶斯

**K近邻算法（K-Nearest Neighbors, KNN）**是一种惰性学习算法，无需显式训练过程。预测时，找到测试样本在特征空间中的K个最近邻居，通过投票（分类）或平均（回归）确定预测结果。

距离度量是关键设计选择：

欧氏距离： $d(x, y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2}$
曼哈顿距离： $d(x, y) = \sum_{i=1}^{n}|x_i - y_i|$
闵可夫斯基距离： $d(x, y) = (\sum_{i=1}^{n}|x_i - y_i|^p)^{1/p}$

K值的选择需要权衡：较小的K值对噪声敏感，模型复杂度高；较大的K值决策边界平滑，但可能欠拟合。通常通过交叉验证选择最优K值。

**朴素贝叶斯（Naive Bayes）**基于贝叶斯定理和特征条件独立性假设：

$P(y_k|x) = \frac{P(x|y_k)P(y_k)}{P(x)}$

由于分母对所有类别相同，只需比较分子：

$\hat{y} = \arg\max_{y_k} P(y_k)\prod_{i=1}^{n}P(x_i|y_k)$

条件概率 $P(x_i|y_k)$ 的估计方法决定了朴素贝叶斯的变体：

高斯朴素贝叶斯：假设连续特征服从高斯分布
多项式朴素贝叶斯：适用于离散计数特征（如文本词频）
伯努利朴素贝叶斯：适用于二元特征

朴素贝叶斯的优势在于训练速度快、对缺失数据不敏感、适合高维数据；缺点在于特征独立性假设在实际中很少成立。

from sklearn.neighbors import KNeighborsClassifier
from sklearn.naive_bayes import GaussianNB

# KNN
knn = KNeighborsClassifier(n_neighbors=5, metric='euclidean')
knn.fit(X_train, y_train)
print(f"KNN Accuracy: {knn.score(X_test, y_test):.4f}")

# 朴素贝叶斯
nb = GaussianNB()
nb.fit(X_train, y_train)
print(f"Naive Bayes Accuracy: {nb.score(X_test, y_test):.4f}")

决策边界对比

图6-3：六种经典分类算法在不同数据集上的决策边界对比。从左到右分别为线性可分数据、月亮形数据（非线性）和环形数据（非线性）。可以观察到：逻辑回归产生线性边界；SVM(RBF)能够适应复杂非线性模式；决策树产生轴对齐的矩形边界；随机森林边界更平滑；KNN边界不规则；朴素贝叶斯产生平滑的二次决策边界。

表6-1：监督学习算法特性对比

算法	训练速度	预测速度	可解释性	处理非线性	对异常值敏感	适用数据规模
线性回归	快	极快	高	否	中	大规模
逻辑回归	快	极快	高	否	中	大规模
决策树	快	快	高	是	高	中小规模
随机森林	中	快	中	是	低	大规模
SVM	慢	快	低	是	中	中小规模
KNN	极快	慢	中	是	中	小规模
朴素贝叶斯	极快	极快	高	否	低	大规模

上表总结了各算法的核心特性，可作为算法选择的参考依据。实际应用中，建议从简单模型开始，逐步尝试更复杂的算法，通过交叉验证选择最优方案。

6.3 无监督学习算法

无监督学习处理没有标签的数据，目标是发现数据中隐藏的结构和模式。与监督学习相比，无监督学习更具挑战性，因为缺乏明确的评估标准，但也更贴近人类的学习方式。

6.3.1 聚类算法

K-Means算法是最广泛使用的聚类算法，通过迭代优化将数据划分为K个簇。算法步骤如下：

随机选择K个样本作为初始簇中心
将每个样本分配到距离最近的簇中心
重新计算每个簇的中心（所有样本的均值）
重复步骤2-3直到收敛

目标函数（惯性）为所有样本到其所属簇中心的距离平方和：

$J = \sum_{i=1}^{m}\sum_{k=1}^{K}r_{ik}\|x_i - \mu_k\|^2$

其中 $r_{ik}$ 为指示变量，当样本 $i$ 属于簇 $k$ 时为1，否则为0。

K-Means的优势在于算法简单、计算效率高；缺点是需要预先指定K值、对初始中心敏感、假设簇为球形分布。

**层次聚类（Hierarchical Clustering）**构建树状的簇结构，分为凝聚式（自底向上）和分裂式（自顶向下）两种策略。凝聚式从每个样本作为独立簇开始，逐步合并最相似的簇，直到所有样本归于一个簇。

簇间距离的计算方法：

单链接（Single Linkage）：两簇最近样本的距离
全链接（Complete Linkage）：两簇最远样本的距离
平均链接（Average Linkage）：两簇所有样本对距离的平均
Ward法：合并后簇内方差增量最小

**DBSCAN（Density-Based Spatial Clustering of Applications with Noise）**是基于密度的聚类算法，能够发现任意形状的簇并识别噪声点。核心概念包括：

核心点：在半径 $\epsilon$ 内包含至少MinPts个邻居的点
边界点：在核心点的 $\epsilon$ 邻域内但自身不是核心点
噪声点：既不是核心点也不是边界点

DBSCAN的优势在于：无需预设簇数量、能发现任意形状簇、自动识别噪声；缺点是对参数 $\epsilon$ 和MinPts敏感、在密度差异大的数据集上表现不佳。

聚类算法对比

图6-4：K-Means与DBSCAN在不同数据集上的聚类效果对比。第一行为原始数据，第二行为K-Means结果（红色X标记簇中心），第三行为DBSCAN结果（黑色点为噪声）。可以观察到：K-Means假设簇为球形，在月亮形和环形数据上表现不佳；DBSCAN能够发现任意形状簇，但在密度差异大的数据上可能将不同密度区域划分为多个簇。

from sklearn.cluster import KMeans, DBSCAN, AgglomerativeClustering
from sklearn.metrics import silhouette_score

# K-Means聚类
kmeans = KMeans(n_clusters=3, random_state=42, n_init=10)
labels_kmeans = kmeans.fit_predict(X)
print(f"K-Means Silhouette Score: {silhouette_score(X, labels_kmeans):.4f}")

# DBSCAN聚类
dbscan = DBSCAN(eps=0.5, min_samples=5)
labels_dbscan = dbscan.fit_predict(X)
n_clusters = len(set(labels_dbscan)) - (1 if -1 in labels_dbscan else 0)
print(f"DBSCAN found {n_clusters} clusters")

# 层次聚类
agg = AgglomerativeClustering(n_clusters=3, linkage='ward')
labels_agg = agg.fit_predict(X)

6.3.2 降维方法

高维数据面临"维度灾难"问题：数据稀疏性增加、计算复杂度上升、可视化困难。降维技术将数据映射到低维空间，同时尽可能保留重要信息。

**主成分分析（Principal Component Analysis, PCA）**是最常用的线性降维方法。其核心思想是找到数据方差最大的投影方向（主成分），将数据投影到这些方向上实现降维。

PCA的计算步骤：

数据中心化：减去各特征的均值
计算协方差矩阵： $C = \frac{1}{n-1}X^T X$
特征值分解： $Cv = \lambda v$
选择主成分：按特征值大小排序，选择前k个特征向量
数据投影： $X_{new} = X \cdot V_k$

第 $i$ 个主成分解释的方差比例为： $\frac{\lambda_i}{\sum_{j=1}^{d}\lambda_j}$

PCA可视化

图6-5：PCA降维分析。左上为各主成分的方差解释比例，中上为二维投影结果，右上为特征载荷（各特征对主成分的贡献）。可以观察到：第一主成分解释了超过90%的方差，花瓣长度和花瓣宽度对主成分的贡献最大。

**t-SNE（t-Distributed Stochastic Neighbor Embedding）**是强大的非线性降维技术，特别适用于高维数据的可视化。它通过保持高维空间中样本间的局部相似性来实现降维。

t-SNE的核心步骤：

在高维空间中计算样本对的条件概率（相似度）
在低维空间中初始化样本位置
通过梯度下降最小化高维和低维分布之间的KL散度
迭代优化直到收敛

t-SNE的优势在于能够揭示数据的局部结构，适合可视化；缺点包括计算成本高、结果具有随机性、全局结构可能失真。

**UMAP（Uniform Manifold Approximation and Projection）**是t-SNE的现代替代方案，在保持局部结构的同时更好地保留全局结构，且计算效率更高。

from sklearn.decomposition import PCA
from sklearn.manifold import TSNE
import umap

# PCA降维
pca = PCA(n_components=2)
X_pca = pca.fit_transform(X)
print(f"Explained variance ratio: {pca.explained_variance_ratio_}")

# t-SNE降维
tsne = TSNE(n_components=2, random_state=42, perplexity=30)
X_tsne = tsne.fit_transform(X)

# UMAP降维
reducer = umap.UMAP(n_components=2, random_state=42)
X_umap = reducer.fit_transform(X)

表6-2：降维方法对比

方法	类型	计算复杂度	保留全局结构	保留局部结构	主要用途
PCA	线性	O(nd²+d³)	是	否	预处理、去噪
Kernel PCA	非线性	O(n²d+n³)	是	部分	非线性降维
t-SNE	非线性	O(n²)	否	强	可视化
UMAP	非线性	O(n^1.14)	是	强	可视化、预处理

6.3.3 关联规则挖掘

关联规则挖掘发现数据集中项之间的有趣关系，典型应用是购物篮分析，发现"如果购买A，则很可能购买B"这样的规则。

Apriori算法基于"频繁项集的所有子集也必须是频繁的"这一先验性质，通过迭代生成候选集并剪枝来高效发现频繁项集。

关键度量指标：

支持度（Support）： $supp(X) = \frac{|\{t \in T : X \subseteq t\}|}{|T|}$
置信度（Confidence）： $conf(X \Rightarrow Y) = \frac{supp(X \cup Y)}{supp(X)}$
提升度（Lift）： $lift(X \Rightarrow Y) = \frac{conf(X \Rightarrow Y)}{supp(Y)}$

FP-Growth算法通过构建频繁模式树（FP-Tree）压缩数据库，避免生成大量候选集，效率显著优于Apriori。

from mlxtend.frequent_patterns import apriori, association_rules
from mlxtend.preprocessing import TransactionEncoder

# 示例购物篮数据
dataset = [['牛奶', '面包', '尿布'],
           ['可乐', '面包', '尿布', '啤酒'],
           ['牛奶', '尿布', '啤酒', '鸡蛋'],
           ['面包', '牛奶', '尿布', '啤酒'],
           ['面包', '牛奶', '尿布', '可乐']]

# 编码
te = TransactionEncoder()
te_ary = te.fit(dataset).transform(dataset)
df = pd.DataFrame(te_ary, columns=te.columns_)

# 发现频繁项集
frequent_itemsets = apriori(df, min_support=0.6, use_colnames=True)
print(frequent_itemsets)

# 生成关联规则
rules = association_rules(frequent_itemsets, metric="confidence", min_threshold=0.7)
print(rules[['antecedents', 'consequents', 'support', 'confidence', 'lift']])