Eurekaimer

DMML_24Fall_Re¶

Lecture1 - 绪论 & 基础复习¶

1. 课程考核与大作业 (关键信息)¶

• 成绩构成: 闭卷考试 (60%) + 实验 (20%) + 大作业 (20%)
• 大作业 (四选一, 15-18周展示):
  1. 遥感图像飞机检测: 目标检测 (Object Detection).
  2. “福”字识别: 图像分类, 重点解决类别不平衡 (Class Imbalance).
  3. 台风预报: 序列预测/回归, 需处理时空数据.
  4. 图像区域分割提取: 语义分割, 核心难点是保持空间相关性.

2. 数据挖掘核心概念 (Data Mining Fundamentals)¶

2.1 新数据的挑战 (Technical Challenges)¶

传统的统计分析面临新数据的四大挑战，这也是引入机器学习算法的动机：

• 可伸缩性 (Scalability): 数据无法一次性放入内存，需要 Out-of-core 或分布式算法.
• 高维性 (High Dimensionality): 维度灾难 (Curse of Dimensionality), 数据稀疏.
• 异构性 (Heterogeneous): 混合属性 (非结构化文本, 图像, 时间序列).
• 分布性 (Distributed): 数据地理分布, 需解决隐私与通信代价.

2.2 任务分类 (Taxonomy)¶

根据目标变量的存在与否及类型划分：

A. 预测性任务 (Predictive) - Supervised¶

利用训练数据学习映射函数 \(y=f(x|\theta)\)

1. 分类 (Classification)
   • 输入: 样本 \(\mathbf{x} \in \mathbb{R}^n\), 标签 \(c\) (离散).
   • 目标: 学习判别界面或概率分布.
   • 常用算法: Decision Tree, KNN, SVM, ANN, Naive Bayes.
2. 回归 (Regression)
   • 输入: 样本 \(\mathbf{x}\), 标签 \(y\) (连续).
   • 目标: 最小化预测误差.
   • 公式: \((w^*, b^*) = \arg\min_{w,b} \sum_{i=1}^{m} (f(x_i) - y_i)^2\) (以线性回归MSE为例).
3. 异常检测 (Anomaly Detection)
   • 目标: 识别显著偏离分布的 \(x\). 应用于欺诈检测、网络入侵.

B. 描述性任务 (Descriptive) - Unsupervised¶

发现数据内在结构，无标签 \(y\).

1. 聚类 (Clustering)
   • 目标: 最大化类间距离 (Inter-cluster), 最小化类内距离 (Intra-cluster).
   • 度量: 常用欧氏距离 (Euclidean Distance).
2. 关联规则 (Association Rule)
   • 形式: \(A \rightarrow B\) (蕴含关系).
   • 应用: 购物篮分析 (Market Basket Analysis).
3. 序列模式 (Sequential Pattern)
   • 关联规则 + 时间维度 (Time attribute).

3. 机器学习系统构建流程 (Process)¶

3.1 问题抽象化 (Abstraction) - 以“鱼类分类”为例¶

• 输入: 物理对象 (鱼).
• 特征工程 (Feature Extraction):
  • 物理特征 \(\rightarrow\) 数值特征向量 \(\mathbf{x} = [x_1, x_2]^T\) (如 \(x_1\)=长度, \(x_2\)=亮度).
  • 特征优选: 权衡特征数量 (维度) 与 计算复杂度/过拟合风险.
• 类别抽象: \(\omega_1\) (鲑鱼), \(\omega_2\) (鲈鱼).
• 决策规则 (Decision Rule):
  • 设定阈值 \(x_0\) (Threshold).
  • Rule: If \(x < x_0\) then \(\omega_1\), else \(\omega_2\).
  • 高维情况表现为特征空间中的超平面划分.

3.2 数据集划分 (Dataset Splitting) [Exam Point]¶

严谨的ML流程必须包含三部分：

1. 训练集 (Training Set): 用于拟合模型参数 (Parameters, e.g., 权重 \(w\)).
2. 验证集 (Validation Set):
   • 用途: 调整超参数 (Hyper-parameters), 模型选择.
   • 注意: 在此阶段评估模型性能，决定是否停止训练.
3. 测试集 (Test Set):
   • 用途: 评估最终模型的泛化能力 (Generalization).
   • 铁律: 绝对不能在测试集上调参 (No Peeking)! 测试集仅用于最后一次的 "Unseen data" 模拟.

4. 监督 vs 无监督 (对比总结)¶

5. 复习Checklist¶

• 理解 4V 特点对算法设计的影响 (内存/计算效率).
• 能够用数学语言描述分类 (\(c=f(x)\)) 与 回归 (Loss Function) 的区别.
• 牢记 Train/Val/Test 的功能区别 (特别是验证集的作用).
• 熟悉大作业中提到的四类问题对应的 ML 任务类型 (检测/不平衡分类/时序/分割).

Lecture2 - 数据处理¶

1. 数据的基本概念与表示 (Data Representation)¶

数据定义与矩阵表示¶

数据挖掘是在大型数据存储库中自动发现有用信息的过程。从数学角度看，数据集通常表示为数据矩阵 (Data Matrix)。

• 对象 (Objects/Samples): 行向量，表示实体（如记录、点、向量、模式）。
• 属性 (Attributes/Features): 列向量，表示对象的维度。

• 矩阵表示:
  设数据集 \(D\) 包含 \(m\) 个对象，每个对象有 \(n\) 个属性，则 \(D\) 可表示为 \(m \times n\) 矩阵：

  \[ D = \begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1n} \\ x_{21} & x_{22} & \cdots & x_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ x_{m1} & x_{m2} & \cdots & x_{mn} \end{pmatrix} \]

  其中第 \(i\) 行代表第 \(i\) 个对象，第 \(j\) 列代表第 \(j\) 个属性。

属性类型¶

• 离散 (Discrete): 具有有限或无限可数个值。
• 连续 (Continuous): 取实数值。
• 非对称属性 (Asymmetric Attributes): 只有非零值才是重要的（常见于稀疏数据）。

特殊数据类型的数学结构¶

1. 文档数据 (Document Data):
   • 表示为词 (Term) 向量。
   • 每个分量对应词在文档中出现的频率（TF）。
   • 通常导致高维稀疏矩阵。
2. 图数据 (Graph Data): 包含对象间的结构关系（邻接矩阵）。
3. 时序数据 (Temporal/Sequence Data): 数据间存在序关系 \(t_1, t_2, \dots, t_n\)。
4. 图像数据:
   • 数学表示: \(f(x, y, \lambda, t)\)
     • \((x, y)\): 2-D 空间坐标。
     • \(\lambda\): 波长（对应颜色/光谱）。
     • \(t\): 时间（对应视频帧）。
   • 离散化后为像素矩阵，像素值代表亮度（灰度值）。

2. 数据集的一般特性 (General Characteristics)¶

• 维度 (Dimensionality): 属性的数量。
  • 维数灾难 (Curse of Dimensionality): 随着维度增加，数据在空间中变得极其稀疏，距离度量（如欧氏距离）失效，模型泛化能力下降。
• 稀疏性 (Sparsity): 对象的大部分属性值为0。
• 分辨率 (Resolution): 数据的聚合程度，不同的分辨率可能表现出不同的统计模式。

3. 汇总统计 (Summary Statistics)¶

用于捕捉数据分布特征的度量。

频率与众数¶

• 频率: 给定属性值 \(v_i\)，其频率为具有该值的对象数除以总对象数 \(m\)。
• 众数 (Mode): 频率最高的值。
  • 注: 对连续属性，众数通常无意义（除非离散化），主要用于填充缺失值。

位置度量 (Location Measures)¶

• 均值 (Mean): \(\bar{x} = \frac{1}{m} \sum_{i=1}^{m} x_i\)
  • 缺点: 对离群点 (Outliers) 敏感。

• 中位数 (Median):

  \[ \text{median}(x) = \begin{cases} x_{(r+1)} & \text{若 } m \text{ 为奇数, } m=2r+1 \\ \frac{1}{2}(x_{(r)} + x_{(r+1)}) & \text{若 } m \text{ 为偶数, } m=2r \end{cases} \]
  • 特点: 鲁棒性强 (Robust)。
  • 截断均值 (Trimmed Mean): 去掉两端 \(p\%\) 的极端值后计算的均值。

散布度量 (Dispersion Measures)¶

• 极差 (Range): \(\text{range}(x) = \max(x) - \min(x)\)
• 方差 (Variance): \(s_x^2 = \frac{1}{m-1} \sum_{i=1}^{m} (x_i - \bar{x})^2\)
• 绝对平均偏差 (AAD): \(\text{AAD}(x) = \frac{1}{m} \sum_{i=1}^{m} |x_i - \bar{x}|\)
• 中位数绝对偏差 (MAD): \(\text{MAD}(x) = \text{median}(\{|x_1 - \bar{x}|, \dots, |x_m - \bar{x}|\})\)
  • 注: MAD 对离群点非常鲁棒。
• 四分位数极差 (IQR): \(IQR = x_{75\%} - x_{25\%}\)

4. 数据质量与噪声 (Data Quality)¶

• 噪声 (Noise): 测量误差的随机部分。
  • 数学模型: \(Observed = Signal + Noise\)。
  • 处理: 信号处理、鲁棒算法。
• 离群点 (Outlier): 特征显著不同于其他大部分数据的对象。
  • 可能是异常（Anomalous）对象，也可能是合法的高价值对象（如欺诈检测）。
• 缺失值处理策略:
  • 删除对象/属性。
  • 估计/插值（均值、众数、回归）。
  • 加权填补（用所有可能值代替，以可能性为权重）。

5. 数据预处理 (Data Preprocessing)¶

5.1 聚集与抽样¶

• 聚集 (Aggregation): 转换标度（如从天到月），减少数据变异性 (Variability)，提高稳定性。
• 抽样 (Sampling): 选择子集进行分析。
  • 动机: 克服计算资源限制（与统计学中“获取数据成本高”的动机不同，数据挖掘关注的是“处理全量数据成本高”）。

5.2 离散化与二元化 (Discretization & Binarization)¶

将连续属性转换为分类属性，或将多分类转换为二元属性。

非监督离散化¶

• 等宽 (Equal Width)。
• 等频 (Equal Frequency)。
• K-means 聚类离散化。

监督离散化：基于熵 (Entropy-based)¶

利用类标号 (Class Labels) 信息，通过最小化熵来寻找最佳分割点。

• 区间熵的计算:
  设 \(k\) 为类标号数，\(m_i\) 是第 \(i\) 个区间中值的总数，\(m_{ij}\) 是第 \(i\) 个区间中属于类 \(j\) 的值的数量。
  第 \(i\) 个区间的熵 \(e_i\) 定义为：

  \[ e_i = - \sum_{j=1}^{k} p_{ij} \log_2 p_{ij} \]

  其中 \(p_{ij} = \frac{m_{ij}}{m_i}\) 是第 \(i\) 个区间中类 \(j\) 的概率。

• 总熵 (分割质量度量):
  该分割的总熵 \(e\) 是每个区间熵的加权平均：

  \[ e = \sum_{i=1}^{n} w_i e_i \]

  其中 \(w_i = \frac{m_i}{m}\) 是第 \(i\) 个区间样本占总样本的比例，\(n\) 是区间个数。
  算法逻辑: 寻找使总熵 \(e\) 最小的分割点，递归进行。

5.3 变量变换 (Variable Transformation)¶

• 函数变换: \(\log(x), e^x, |x|\) 等，用于改变数据分布。
• 标准化/归一化 (Normalization):
  • Z-score: \(x' = \frac{x - \bar{x}}{s}\) (利用均值和标准差)。
  • 鲁棒标准化: 使用中位数代替均值，绝对标准差代替标准差。
  • 目的: 消除量纲影响，保持数值稳定性（对神经网络等基于梯度的算法至关重要）。

6. 特征工程 (Feature Engineering)¶

特征创建与提取¶

• 特征提取 (Feature Extraction): 针对具体领域（如图像、音频），由原始数据构建新特征。
• 特征映射: 将数据映射到新空间（如傅立叶变换检测周期性模式）。

维归约 (Dimensionality Reduction)¶

• 动机:
  • 避免维数灾难。
  • 降低噪声（删除不相关特征）。
  • 降低时间/空间复杂度。
  • 可视化需求。
• 常用方法:
  • PCA (主成分分析): 线性、非监督，寻找最大方差方向。
  • LDA (线性判别分析): 线性、监督，寻找最大类间距离方向。

原始特征的问题¶

• 相关性低: 特征与分类问题无关。
• 病态矩阵: 特征过多且样本有限时，计算逆矩阵或参数估计时容易出现数值不稳定（病态矩阵问题）。

Lecture3 - 降维与概念学习 (Dimensionality Reduction & Concept Learning)¶

1. 降维技术概述¶

数据预处理中的核心步骤，旨在解决维数灾难 (Curse of Dimensionality)。

• 目的:
  • 提高算法的时间和内存效率。
  • 去除不相关特征与噪声，提升模型泛化能力。
  • 数据可视化 (通常降至2维或3维)。
• 分类:
  1. 特征提取 (Feature Extraction): 通过数学变换将原始特征空间映射到新的低维空间 (如 PCA, LDA)。
  2. 特征选择 (Feature Selection): 从原始特征集中选出一个最佳子集 (如 Filter, Wrapper, Embedded)。

2. 特征提取 (Feature Extraction)¶

将 \(M\) 个原始特征通过线性或非线性组合，转换为 \(m\) 个新特征 (\(m < M\))。

2.1 主成分分析 (PCA) - 无监督¶

• 核心思想: 将数据投影到方差最大的方向上。
  • 方差 (Variance) 被视为信息的度量，方差越大，包含的信息（区分度）越大。
• 数学原理:
  • 寻找正交变换矩阵 \(A\)，使得新特征 \(y = A^T x\) 的协方差矩阵对角化。
  • 选取协方差矩阵的前 \(m\) 个最大特征值对应的特征向量作为主成分。
• 优缺点:
  • 优点: 无参数限制，计算快，正交去相关。
  • 缺点: 无监督（不利用类别标签），方差大的方向未必是分类效果最好的方向。

2.2 线性判别分析 (LDA) - 有监督¶

• 核心思想 (Fisher 投影准则): 寻找最佳投影方向，使得投影后满足：
  • 类内散度 (Intra-class scatter) 最小: 同类样本尽可能聚集。
  • 类间散度 (Inter-class scatter) 最大: 不同类样本尽可能分开。

• 优化目标:
  最大化广义瑞利商:

  \[ J(w) = \frac{w^T S_B w}{w^T S_W w} \]

  其中 \(S_B\) 为类间散度矩阵，\(S_W\) 为类内散度矩阵。

3. 特征选择 (Feature Selection)¶

直接筛选特征子集，保留特征的原始物理含义。

3.1 特征类型¶

• 冗余特征 (Redundant): 信息被其他特征包含（如“购买价格”与“含税价格”）。
• 不相关特征 (Irrelevant): 对任务完全无用（如“学生ID”预测“成绩”）。

3.2 选择策略 (三大类)¶

1. 过滤法 (Filter)
   • 机制: 在学习算法运行前进行，独立于具体模型。
   • Relief 算法: 设计“相关统计量”。
     • 计算样本与同类近邻 (Near-hit) 和异类近邻 (Near-miss) 的距离差。
     • 如果特征能让同类更近、异类更远，则权重增加。
2. 包装法 (Wrapper)
   • 机制: 将学习算法作为“黑盒”，直接用模型的性能（如准确率）来评价特征子集。
   • LVW (Las Vegas Wrapper): 随机采样特征子集 \(\rightarrow\) 交叉验证评估 \(\rightarrow\) 寻找最优。
   • 特点: 效果通常比过滤法好，但计算开销极大。
3. 嵌入法 (Embedded)
   • 机制: 特征选择过程与学习器训练过程融为一体。
   • L1 正则化 (LASSO):
     • 优化目标: \(\min \sum (y_i - w^T x_i)^2 + \lambda \|w\|_1\)
     • 几何解释: L1范数 (\(|w_1| + |w_2| \le C\)) 的等值线是方形，与损失函数的切点容易落在坐标轴上，导致部分系数 \(w_i\) 变为 0，从而实现稀疏化（特征选择）。
     • 对比: L2范数（圆形）通常只让权重变小，不易减为0。

4. 概念学习 (Concept Learning)¶

4.1 基础定义¶

• 定义: 从训练样例中逼近一个布尔函数（目标概念）的过程。
• 术语:
  • 实例集合 (X): 总体。
  • 目标概念 (c): \(c: X \rightarrow \{0, 1\}\) (待学习的真理)。
  • 训练样例 (D): 样本对 \(\langle x, c(x) \rangle\)。
  • 假设 (h): 学习器给出的估计函数，\(h \in H\) (假设空间)。

4.2 偏序关系 (Partial Ordering)¶

假设空间存在“一般”与“特殊”的层级结构：
* More General (\(\ge_g\)): 如果假设 \(h_j\) 覆盖的实例集合包含 \(h_k\) 覆盖的集合，则称 \(h_j\) 比 \(h_k\) 更一般。
* 作用: 使得我们可以通过搜索（而非枚举）来寻找目标假设。

4.3 经典算法¶

1. Find-S 算法

   • 策略: 寻找与正例一致的极大特殊 (Maximally Specific) 假设。
   • 流程: 初始化 \(h\) 为全 \(\emptyset\) (最特殊)。每遇到一个正例，将 \(h\) 中不匹配的属性约束放宽（泛化）以覆盖该正例。
   • 缺点: 忽略反例，无法判断是否存在多个一致假设，对噪声敏感。

2. 候选消除算法 (Candidate-Elimination)

   • 变型空间 (Version Space): 假设空间 \(H\) 中所有与训练集 \(D\) 一致的假设集合。
   • 边界表示:
     • S集: 极大特殊边界 (Specific Boundary)。
     • G集: 极大一般边界 (General Boundary)。
     • 变型空间即为 \(S\) 与 \(G\) 之间的所有假设。
   • 流程:
     • 正例 \(\rightarrow\) 泛化 \(S\) (使其更一般)，移除 \(G\) 中不一致的。
     • 反例 \(\rightarrow\) 特殊化 \(G\) (使其更特殊)，移除 \(S\) 中不一致的。
   • 收敛: 当 \(S\) 和 \(G\) 收敛到同一个假设时，找到目标概念。

5. 归纳偏置与理论 (Inductive Bias & NFL)¶

5.1 归纳偏置 (Inductive Bias)¶

• 定义: 学习算法在学习过程中对某种类型假设的偏好或预先假定。
• 重要性: 如果没有归纳偏置，算法无法对未见样本 (Unseen Instances) 进行分类（即无法进行归纳推理）。
• 类型:
  • 奥卡姆剃刀 (Occam's Razor): 偏好简单的假设（若多个假设与观察一致，选最简单的）。
  • 限制偏置: 限制假设空间的形式（如只允许合取式）。

5.2 没有免费的午餐定理 (NFL)¶

• 内容: 如果对所有可能的问题（所有可能的分布）求平均，所有学习算法（包括随机猜测）的期望性能是相同的。
• \[ \sum_f E_{ote}(\mathcal{L}_a | X, f) = \sum_f E_{ote}(\mathcal{L}_b | X, f) \]
• 启示:
  • 不存在“万能”的最佳算法。
  • 算法的优劣取决于其归纳偏置是否与具体问题的特征相匹配。
  • 研究机器学习必须关注具体的问题背景。

Lecture4 - 机器学习基础与图像特征 (Machine Learning Basics & Image Features)¶

1. 机器学习的基本过程¶

机器学习的本质是寻找一个函数 (Looking for a Function)，通过数据拟合输入与输出之间的映射关系。

1.1 一般流程¶

1. 特征提取 (Feature Extraction): 将原始数据（如图像像素、音频波形）转化为计算机可理解的特征向量。
2. 定义模型集合 (Define a Set of Functions): 选定一个假设空间（如线性模型、神经网络）。
3. 确定最优准则 (Goodness of Function): 定义损失函数（Loss Function）来评估模型的好坏。
4. 选择最优映射 (Pick the Best Function): 利用学习算法（如梯度下降）在假设空间中搜索最优解。

1.2 举例¶

• 图像识别: \(f(\text{Image}) = \text{"Cat"}\)
• 语音识别: \(f(\text{Audio}) = \text{"How are you"}\)
• 围棋: \(f(\text{Board State}) = \text{Next Move}\)

2. 图像特征基础 (Image Features)¶

特征是连接原始数据与机器学习算法的桥梁。根据人类视觉系统的感知，图像特征分为三个层次：

1. 低层特征 (Low-level Features): 描述图像的视觉属性（外观、边缘、纹理、形状）。
2. 中层语义 (Mid-level Representations): 连接低层与高层的纽带，如视觉词袋 (BoW)。
3. 高层语义特征 (High-level Semantic Features): 场景、行为、情感等抽象概念。

3. 常见的图像特征描述子¶

3.1 颜色特征 (Color Features)¶

• 颜色矩 (Color Moments):
  • 利用一阶矩（均值 \(\mu\)）、二阶矩（标准差 \(\sigma\)）、三阶矩（偏度 \(s\)）来描述颜色分布。
  • 通常在 RGB 空间计算，共 9 个分量（3个通道 \(\times\) 3个矩）。
• 颜色直方图 (Color Histogram):
  • 统计图像中不同颜色出现的频率。
  • 特点: 对图像旋转、平移、缩放具有不变性，但丢失了空间信息。

3.2 形状特征 (Shape Features)¶

• Hu 不变矩 (Hu Moments):
  • 利用二阶和三阶中心矩构造出的 7 个不变矩（\(\phi_1 \sim \phi_7\)）。
  • 特点: 对平移、旋转、尺度缩放具有不变性 (Translation, Rotation, Scale Invariant)。
  • 常用于简单的物体识别（如商标、二值图像）。
• 傅里叶描述子 (Fourier Descriptors):
  • 将物体边界视为封闭曲线，通过傅里叶变换将边界坐标转换为频域系数。
  • 低频系数描述整体形状，高频系数描述细节。
• Hough 变换 (Hough Transform):
  • 用于检测直线、圆等参数化形状。
  • 核心思想: 将图像空间的点映射到参数空间（投票机制）。
  • 直线检测: 利用极坐标方程 \(\rho = x \cos\theta + y \sin\theta\)。

3.3 纹理特征 (Texture Features)¶

• 灰度共生矩阵 (GLCM):
  • 统计像素对 \((i, j)\) 在特定方向 \(\theta\) 和距离 \(d\) 下同时出现的概率。
  • 基于 GLCM 可计算能量、熵、对比度、相关性等统计量。
• 局部二值模式 (LBP):
  • 比较中心像素与 \(3 \times 3\) 邻域像素的大小，生成二进制编码。
  • 特点: 计算简单，对光照变化具有较强的鲁棒性，常用于人脸识别和纹理分类。

3.4 中层语义特征：视觉词袋模型 (Bag-of-Words, BoW)¶

• 灵感: 源于文本处理（统计文档中关键词的频率）。
• 流程:
  1. 特征提取: 提取图像局部特征（如 SIFT）。
  2. 生成码书 (Codebook Generation): 利用 K-means 聚类将特征量化为“视觉单词 (Visual Words)”。
  3. 特征编码: 统计图像中每个视觉单词出现的频率，生成直方图向量。
• 应用: 图像检索、场景分类。

Lecture5 - 模型评估与选择 (Model Assessment and Selection)¶

1. 损失函数与风险 (Loss & Risk)¶

1.1 损失函数 (Loss Function)¶

损失函数 \(L(y, f(x))\) 用于度量模型预测值 \(f(x)\) 与真实值 \(y\) 之间的差异。常见的损失函数包括：
* 0-1 损失 (0-1 loss): 用于分类问题，预测错误为1，正确为0。
* 平方损失 (Quadratic loss): \(L(y, f(x)) = (y - f(x))^2\)，常用于回归。
* 绝对损失 (Absolute loss): \(L(y, f(x)) = |y - f(x)|\)。
* 对数损失 (Logarithmic loss): \(L(y, P(y|x)) = -\log P(y|x)\)，常用于概率预测。

1.2 风险函数 (Risk Function)¶

• 期望风险 (Expected Risk / Risk Function): \(R_{exp}(f)\) 是模型在联合分布 \(P(X,Y)\) 下的平均损失，代表模型在总体样本上的表现（理论值，通常未知）。

• 经验风险 (Empirical Risk): \(R_{emp}(f)\) 是模型在训练数据集上的平均损失。

  \[ R_{emp}(f) = \frac{1}{N} \sum_{i=1}^{N} L(y_i, f(x_i)) \]

1.3 模型选择策略¶

• 经验风险最小化 (ERM): 直接最小化训练误差。当样本量较小时，易导致过拟合 (Overfitting)。
• 结构风险最小化 (SRM): 在经验风险的基础上加入正则化项 \(\lambda J(f)\)，平衡模型的拟合能力与复杂度，防止过拟合。

2. 性能度量 (Performance Measures)¶

2.1 分类任务的基础指标¶

• 错误率 (Error Rate): 误分类样本占比。
• 准确率 (Accuracy): 正确分类样本占比。
  • 局限性: 在样本不平衡（如正样本极少）的情况下，准确率会失效（例如全部预测为负类也能得到极高准确率）。

2.2 混淆矩阵与衍生指标¶

混淆矩阵 (Confusion Matrix) 将预测结果分为四类：TP (真反), FN (假负), FP (假正), TN (真负)。

• 查准率/精度 (Precision): \(P = \frac{TP}{TP + FP}\)。预测为正的样本中有多少是真的正样本。
• 查全率/召回率 (Recall/Sensitivity): \(R = \frac{TP}{TP + FN}\)。所有正样本中有多少被预测出来了。

• F1 度量: Precision 和 Recall 的调和平均数，用于综合评估。

  \[ F_1 = \frac{2 \times P \times R}{P + R} \]

2.3 P-R 曲线与 ROC 曲线¶

• P-R 曲线: 以查准率 P 为纵轴，查全率 R 为横轴。
• ROC 曲线 (Receiver Operating Characteristic):
  • 纵轴: 真正率 (TPR) = Recall = \(\frac{TP}{TP + FN}\)
  • 横轴: 假正率 (FPR) = \(\frac{FP}{TN + FP}\) (负样本中被误判为正的比例)
  • 优势: 相比 P-R 曲线，ROC 曲线对样本类别比例不敏感。
• AUC (Area Under ROC Curve): ROC 曲线下的面积。AUC 越大，模型性能越好（理想值为1，随机猜测为0.5）。

3. 模型检验与比较方法¶

3.1 评估方法 (Evaluation Methods)¶

• 留出法 (Hold-out): 将数据集划分为互斥的训练集和验证集（如 2/3 训练，1/3 验证）。需保持数据分布一致性，通常采用多次随机划分取平均。
• 交叉验证法 (Cross Validation):
  • K折交叉验证: 将数据分 K 份，轮流用 K-1 份训练，1 份测试。
  • 留一法 (LOO): K 等于样本数，每次只留一个样本做测试。准确但计算量大。
• 自助法 (Bootstrapping): 有放回采样，适合小数据集。

3.2 统计假设检验 (Hypothesis Testing)¶

用于判断两个模型性能的差异是否具有统计学意义，而非仅仅是随机波动。
* 二项检验 / t 检验: 比较单个或两个模型在特定数据集上的表现。
* McNemar 检验: 比较两个分类器在同一测试集上的分类结果差异。
* Friedman 检验 & Nemenyi 检验: 用于多个算法在多个数据集上的性能比较与排序。

4. 偏差-方差分解 (Bias-Variance Decomposition)¶

泛化误差可以分解为三部分：
$$ E(f; D) = \text{Bias}^2 + \text{Variance} + \text{Noise} $$

• 偏差 (Bias): 学习算法的期望预测与真实结果的偏离程度。度量了算法的拟合能力。
  • 欠拟合 (Underfitting): 偏差主导，模型太简单，连训练集都学不好。
• 方差 (Variance): 同样大小的训练集的变动所导致的学习性能的变化。度量了算法的稳定性。
  • 过拟合 (Overfitting): 方差主导，模型太复杂，对训练数据的微小扰动极其敏感。
• 噪声 (Noise): 数据本身的固有误差，是学习性能的上限（无法克服）。

权衡 (Trade-off):
* 增加模型复杂度（如增加多项式阶数）：偏差减小，方差增大（易过拟合）。
* 降低模型复杂度（如正则化）：偏差增大，方差减小（易欠拟合）。

Lecture6 - 线性分类器与优化准则 (Linear Classifiers and Optimization Criteria)¶

1. 线性分类器基础 (Linear Classifier Basics)¶

1.1 基本概念¶

• 定义: 通过一个线性判别函数（直线、平面或超平面）将特征空间一分为二的分类器。
• 判别函数:
  $$ g(x) = w^T x + w_0 $$
  其中 \(w\) 为权向量，\(w_0\) 为阈值（或偏置）。
• 决策规则:
  • 若 \(g(x) > 0\)，判为正类 (\(\omega_1\))。
  • 若 \(g(x) < 0\)，判为负类 (\(\omega_2\))。
  • 若 \(g(x) = 0\)，位于决策面上（边界）。

1.2 增广变换 (Augmented Transformation)¶

为了简化数学处理，将权向量 \(w\) 和偏置 \(w_0\) 合并：
* 增广样本向量: \(y = [1, x_1, x_2, \dots, x_d]^T\) (维数 \(D+1\))。
* 增广权向量: \(a = [w_0, w_1, w_2, \dots, w_d]^T\)。
* 新判别函数: \(g(x) = a^T y\)。决策面变为过原点的超平面 \(a^T y = 0\)。

2. 垂直平分分类器 (Perpendicular Bisector Classifier)¶

又称最小距离分类器 (Minimum Distance Classifier)。

2.1 设计思路¶

• 基于两类样本的均值向量 (\(m_1, m_2\))。
• 决策面是连接两类均值点线段的垂直平分面。

2.2 数学形式¶

• 判别函数:

  \[ g(x) = (m_1 - m_2)^T x - \frac{1}{2}(m_1 - m_2)^T (m_1 + m_2) \]

• 等价形式:

  \[ d(x, m_1) < d(x, m_2) \Rightarrow x \in \omega_1 \]

  即样本距离哪个类的均值更近，就判为哪一类。

2.3 特点¶

• 计算简单，无须复杂的优化过程。
• 非最佳决策: 仅考虑均值，未考虑样本的分布方差（离散度）。

3. Fisher 线性判别分析 (Fisher Linear Discriminant)¶

3.1 核心思想¶

将高维样本投影到一维直线上，使得投影后的样本：
* 类内距离最小 (Within-class scatter minimized): 同类样本尽可能聚集。
* 类间距离最大 (Between-class scatter maximized): 不同类样本尽可能分开。

3.2 Fisher 准则函数¶

其中 \(\tilde{m}\) 为投影后的均值，\(\tilde{S}^2\) 为投影后的类内离散度。

3.3 最佳投影方向¶

通过对 \(J_F(w)\) 求导并令其为 0 (使用 Lagrange 乘子法)，得到最佳投影方向 \(w^*\)：

其中 \(S_W\) 为总类内离散度矩阵。

4. 感知器准则 (Perceptron Criterion)¶

4.1 适用前提¶

样本集必须是线性可分 (Linearly Separable) 的，即存在一个超平面能将两类完全分开。

4.2 规范化¶

为了统一处理，将所有负类 (\(\omega_2\)) 样本的增广向量乘以 -1。
* 规范化后目标: 寻找权向量 \(a\)，使得对所有样本 \(y_i\)，都有 \(a^T y_i > 0\)。

4.3 准则函数¶

感知器准则函数只关注被错误分类的样本集合 \(Y_{error}\)：

• 若所有样本正确分类，\(Y_{error}\) 为空，\(J_p(a) = 0\) (极小值)。
• 若有错分，错分样本的 \(a^T y < 0\)，则 \(-a^T y > 0\)，导致 \(J_p(a) > 0\)。

4.4 优化算法 (梯度下降)¶

使用梯度下降法迭代求解 \(a\)：

• 物理意义: 当出现错分样本时，用该样本向量去“修正”权向量，直到所有样本都被正确分类。
• 收敛性: 若样本线性可分，感知器算法保证收敛。

Lecture7 - 贝叶斯分类器 (Bayesian Classifiers)¶

1. 贝叶斯理论基础¶

1.1 核心公式¶

• 贝叶斯公式 (Bayes' Theorem):

  \[ P(\omega_i | x) = \frac{P(x | \omega_i) P(\omega_i)}{P(x)} \]
  • \(P(\omega_i)\): 先验概率 (Prior)，类别 \(\omega_i\) 在观察到数据前发生的概率。
  • \(P(x | \omega_i)\): 类条件概率 (Class-Conditional Probability) / 似然 (Likelihood)，在类别 \(\omega_i\) 下观察到特征 \(x\) 的概率。
  • \(P(\omega_i | x)\): 后验概率 (Posterior)，在观察到特征 \(x\) 后，样本属于类别 \(\omega_i\) 的概率。
  • \(P(x)\): 证据因子 (Evidence)，归一化常数，\(P(x) = \sum_j P(x | \omega_j) P(\omega_j)\)。

1.2 频率派 vs 贝叶斯派¶

• 频率派 (Frequentist): 认为参数 \(\theta\) 是固定但未知的常数，通过最大化似然函数 \(P(X; \theta)\) 来估计参数 (MLE)。
• 贝叶斯派 (Bayesian): 认为参数 \(\theta\) 是随机变量，服从某个先验分布，通过最大化后验概率 \(P(\theta | X)\) 来估计参数 (MAP)。

2. 最小错误率 Bayes 决策 (Minimum Error Rate)¶

2.1 决策规则¶

目标是使分类错误的概率最小化。
* 规则: 将样本 \(x\) 分配给后验概率最大的类别。

1

$$ \text{Decide } \omega_i \text{ if } P(\omega_i | x) > P(\omega_j | x), \forall j \neq i $$

• 等价规则:
  • 比较分子 (忽略 \(P(x)\)): \(p(x | \omega_i) P(\omega_i) > p(x | \omega_j) P(\omega_j)\)
  • 似然比检验: \(\frac{p(x | \omega_i)}{p(x | \omega_j)} > \frac{P(\omega_j)}{P(\omega_i)}\)
  • 对数似然比: \(\ln p(x | \omega_i) + \ln P(\omega_i) > \ln p(x | \omega_j) + \ln P(\omega_j)\)

2.2 特点¶

• 在概率意义上是最优的。
• 需要知道先验概率和类条件概率密度（通常难以准确获得）。

3. 最小风险 Bayes 决策 (Minimum Risk)¶

3.1 问题的提出¶

最小错误率假设所有错误的代价是一样的。但在实际应用中（如癌症诊断），漏报 (False Negative) 的代价通常远高于 误报 (False Positive)。

3.2 风险函数¶

• 损失函数 \(\lambda(\alpha_i, \omega_j)\): 真实类别为 \(\omega_j\) 但决策为 \(\alpha_i\) 时的代价。
• 条件风险 \(R(\alpha_i | x)\): 对于特定样本 \(x\)，采取决策 \(\alpha_i\) 的期望损失。
  $$ R(\alpha_i | x) = \sum_{j=1}^C \lambda(\alpha_i, \omega_j) P(\omega_j | x) $$

3.3 决策规则¶

• 规则: 选择使条件风险最小的决策。

  \[ \alpha^* = \arg \min_{\alpha_i} R(\alpha_i | x) \]

• 与最小错误率的关系: 当采用 0-1 损失函数 (对错分惩罚为1，正确为0) 时，最小风险决策等价于最小错误率决策。

4. 最小最大决策 (Minimax Decision)¶

4.1 适用场景¶

当先验概率 \(P(\omega_i)\) 未知或不确定时，传统的贝叶斯决策无法直接使用。

4.2 核心思想¶

• 设计一个分类器，使得在最坏的先验概率分布下，风险也是最小的。
• 博弈论视角：假设“大自然”会选择一个让分类器风险最大的先验分布，而分类器的目标是最小化这个最大风险。
• 这是一种保守的策略，保证了性能的下限。

5. 正态分布下的 Bayes 分类器¶

当类条件概率密度 \(p(x | \omega_i)\) 服从多维正态分布 \(N(\mu_i, \Sigma_i)\) 时，判别函数可以写成二次型形式：

特殊情况下的决策面¶

1. \(\Sigma_i = \sigma^2 I\) (各维度独立等方差): 决策面是线性的，退化为最小欧氏距离分类器（考虑先验修正）。
2. \(\Sigma_i = \Sigma\) (各类协方差矩阵相同): 决策面是线性的 (Linear Discriminant Analysis, LDA)。
3. \(\Sigma_i\) 任意: 决策面是二次曲面 (Quadratic Discriminant Analysis, QDA)，如双曲线、椭圆、抛物线等。

Lecture8 - 线性分类器进阶 (Advanced Linear Classifiers)¶

1. 最小错分样本数准则 (Minimum Squared Error Criterion)¶

1.1 问题的提出¶

• 感知器准则要求样本集必须是线性可分的，否则无法收敛。
• 在实际应用中，完全线性可分的情况很少见。
• 目标: 寻找一个权向量，使得被错误分类的样本数量最少。

1.2 准则函数¶

• 准则一: 直接最小化错分样本的模长。

  \[ J(a) = || Ya - b ||^2 \]
  • \(Y\): 样本矩阵。
  • \(b\): 正常数向量（如全1向量）。
  • 准则二: 利用不等式约束。
  \[ \max J(a) = \sum_{i=1}^N \frac{1 + \text{sgn}(a^T y_i)}{2} \]
  • \(\text{sgn}(u) = 1\) 若 \(u \ge 0\)，否则为 -1。
  • 该函数直接统计正确分类的样本数，但难以优化（非连续、不可导）。

1.3 求解方法¶

• 通常采用启发式搜索或近似算法。
• 特点: 设计过程复杂，计算量大。

2. 最小平方误差准则 (Minimum Squared Error, MSE)¶

2.1 核心思想¶

将分类问题转化为回归问题。

• 将不等式约束 \(a^T y_i > 0\) 转化为等式约束 \(a^T y_i = b_i\) (\(b_i > 0\))。
• 目标是使实际输出 \(a^T y_i\) 与期望输出 \(b_i\) 之间的均方误差最小。

2.2 准则函数¶

其中 \(Y\) 是样本矩阵（每一行为一个样本），\(b\) 是目标向量（通常设为全1）。

2.3 极值解¶

通过对 \(J(a)\) 求导并令其为 0，可得解析解：

• \(Y^\dagger = (Y^T Y)^{-1} Y^T\) 被称为 \(Y\) 的伪逆矩阵 (Pseudo-Inverse)。
• 特点:
  • 解析解存在且唯一（若 \(Y^T Y\) 可逆）。
  • 计算简单，无需迭代。
  • 即使样本线性不可分，也能得到一个解（MSE 意义下的最优解）。

3. 总结与回顾¶

3.1 线性分类器对比¶

3.2 实验与应用¶

• 实验1: 手写LBP特征提取。LBP (Local Binary Pattern) 是一种纹理特征，对光照变化鲁棒。
• 实验2: 垂直平分分类器编程实现。

Final Note: 线性分类器是机器学习的基石。虽然现代深度学习模型（如 CNN, Transformer）在复杂任务上表现更好，但线性模型因其可解释性强、计算效率高，在很多场景下仍然是首选基准模型。

评论