1. Classification Task

(1）模型训练过程可分为两阶段：

Induction（归纳）：通过训练集（Training Set）使用学习算法（Learning Algorithm）生成模型（Model）

Deduction（演绎）：将生成的模型应用到测试集（Test Set），预测未知样本的类别（Class）

 

 

2. 决策树的基本直觉（Intuition behind a Decision Tree）

 

（1）分类过程等价于逐步提问：

每个问题都针对一个属性（Attribute）

问题的回答决定下一个问题（或是否继续提问）

直到可明确归属类别为止

 

 

3. 决策树示例（Example of a Decision Tree）

 

（1）图中展示了通过属性 Refund、Marital Status（MarSt） 与 Taxable Income（TaxInc） 进行划分的树结构

（2）属性类型分类：

Refund / Marital Status：Categorical Attributes（类别属性）

Taxable Income：Continuous Attribute（连续属性）

 

4. 决策树结构（Structure of a Decision Tree）

 

（1）决策树为层级结构（Hierarchical Structure），包含以下节点：

Root Node（根节点）：无入边 (incoming edge)，0个或多个出边 (outgoing edges)

Internal Node（内部节点）：1个入边，2个或多个出边

Leaf/Terminal Node（叶节点/终端节点）：1个入边，无出边

 

（2）每个非叶节点包含一个属性判断条件（Test Condition）

（3）每个叶节点被赋予一个类标签（Class Label）

 

 

5. 相同数据集上的不同决策树（Another Decision Tree on Same Dataset）

 

（1）对同一组数据集可以构造出多个不同结构的决策树

（2）不同的划分顺序（例如先用 Marital Status 而非 Refund）会导致结构差异

（3）这说明：同一个数据可能存在多个符合的树结构（“There could be more than one tree that fits the same data”）

 

6. 决策树学习的挑战（Challenge in Learning Decision Tree）

 

（1）理论上可以从给定属性中构造出指数级多的不同决策树

（2）某些树在分类准确性方面更优，但找到最优树在计算上是不可行的 (computationally infeasible)

（3）解决策略：使用启发式算法（Efficient Algorithms）构造一个相对合理但非最优的树

（4）常用方法为贪婪策略（Greedy Strategy）：在每一步选择局部最优的属性进行划分

 

启发式算法（Heuristic Algorithm）是一种在复杂或计算量巨大的问题中，通过经验规则快速找到“够好”解的方法，而不是穷举所有可能去寻找“最优解”。

 

常见算法包括：

Hunt’s Algorithm（最早期）

CART

ID3, C4.5

SLIQ, SPRINT

 

 

7. Hunt算法的基本结构（General Structure of Hunt’s Algorithm）

 

（1）假设 Dt 是到达某个节点 t 的训练记录集合

（2）基本流程如下：

若 Dt 中所有记录属于同一类别 yₜ，则该节点为叶节点，类别为 yₜ

若 Dt 为空，则为默认类别 y_d

若 Dt 中有多个类别，则选择一个最优属性进行划分，递归对每个子集重复该过程

 

 

8. Hunt算法应用示例（Hunt’s Algorithm Example）

 

默认类别为 “Don’t Cheat”，因为它在数据中为多数类

 

 

 

二、输入向量与监督学习回顾（Revisit Supervised Learning & Input Vectors）

 

 

1. 监督学习复习（Revisit Supervised Learning）

 

（1）监督学习的输入为一组输入（Input）和对应标签（Label）的训练集

（2）例如：

图像识别（Image Recognition）任务的输入是图像，标签是类别

文本分类（Document Classification）的输入是文本，标签是文档类型

 

 

2. 输入向量（Input Vectors）

 

（1）机器学习系统通常将各种类型的数据（图像、文本、音频等）转化为向量（Vector）表示

（2）图像示例：

人眼看到的是完整图片，计算机看到的是像素矩阵，再展开成向量

 

 

 

3. 表示策略（Representation Strategy）

 

（1）向量化输入（Vector Representation）是数据预处理的核心

（2）通过映射（Mapping）输入至更适合处理的空间

（3）向量化具有线性代数友好特性，便于后续模型处理

 

表示（Representation）= 将数据映射到便于操作的空间，便于线性代数计算

vectoes are  a great representation since we can do linear algebra

 

4. 图像向量化示例（From Images to Vectors）

 

（1）图像可以用原始像素点（Raw Pixels）表示为二维灰度矩阵

（2）矩阵再展开为一维向量（如 [60, 60, 60, 255,…]），可作为模型输入

 

 

 

1. 训练数据的数学形式（Mathematical Form of Training Data）

 

（1）训练集由多个输入向量与对应标签组成：

{(x¹, t¹), (x², t²), …, (xⁿ, tⁿ)}

其中，x 属于 R^d，t 为标签（Label）

 

（2）t 的类型：

 

回归问题（Regression）：t 为连续值（如股价 stock price）

分类问题（Classification）：t 为离散值（如1,2,…,C）

现在，标签 t 在很多任务中往往是一个结构化对象（如图像）

 

 

 

 

三、K近邻算法（k-Nearest Neighbors，kNN）

 

 

1. 最近邻算法的数学表达（Nearest Neighbors）

（1）给定一个新的输入向量 x，寻找训练集中最接近的样本，将其标签作为预测输出

（2）相似性通过欧几里得距离（Euclidean Distance）度量

公式如下：

 

 

 

 

1. 决策边界（Decision Boundaries）

 

（1）kNN的分类结果形成了Voronoi图样式的决策区域

（2）边界将输入空间划分为不同的类别区间

（3）维度高时也能形成复杂的3D边界图（3D decision boundary）

 

 

 

3. 对噪声的敏感性（Sensitivity to Noise）

 

（1）当 k = 1 时，模型可能对错误数据（噪声）过于敏感，造成误分类（Overfitting）

（2）解决方法：增加 k 值，让更多邻居参与投票 (vote)，提升稳定性与鲁棒性

 

 

 

 

4. 选择 k 的权衡（Choosing k: Tradeoffs）

 

（1）小的 k 值

 

优点：能够捕捉细粒度模式（fine-grained patterns）

缺点：容易过拟合（Overfitting），对训练数据中的偶然噪声敏感

 

（2）大的 k 值

 

优点：通过“平均多数”方式进行平稳预测，鲁棒性更强

缺点：可能欠拟合（Underfitting），忽略局部细节模式

 

（3）经验法则：

 

k 的选取通常满足 k < sqrt{n}，n 为训练样本总数

 

 

 

 5. 泛化能力与误差（Generalization and Error）

 

（1）我们希望模型能泛化（Generalize）到从未见过的数据

（2）通过测试集（Test Set）可以测量泛化误差（Generalization Error）

 

• 训练误差低 ≠ 测试误差低
• 需平衡训练准确率与泛化能力

 

图中曲线说明：

 

k 较小时训练误差低但测试误差高（过拟合）

k 稍大时测试误差较低，达到泛化最优区间

k 过大则训练与测试误差都增大（欠拟合）

 

 

 

 

6. 验证集调参（Hyperparameter Tuning via Validation Set）

 

（1）k 是一个超参数（Hyperparameter），不可通过训练数据直接学习

（2）通过验证集（Validation Set）尝试不同的 k 值选择最佳组合

（3）测试集只用于最终评估，避免泄漏（Data Leakage）

 

 

 

 

四、应用（Examples）

 

 1. 手写数字识别（Digit Classification）

 

数据集：MNIST（Yann LeCun）

输入维度：28×28 灰度图像，共 d=784

训练样本数：60,000，测试样本数：10,000

kNN在该任务中表现优秀，使用合适的距离度量后准确率大幅提升：

• 欧几里得距离误差率约 5%
• 加入形状匹配策略后降至 0.63%

 

 

 

使用 Shape Contexts 描述图像形状

 

方法：将两幅图像变形对齐（warp）

衡量方式：对应点之间的平均距离

 

 

 

• 鱼图像做形变，尽可能对齐另一个鱼的对应位置

 

数据集：8000 万彩色图像，分辨率为 32×32

KNN可以在海量数据中进行语义匹配（Semantic Matching）

图像间的相似性度量非常关键，选对特征或距离函数至关重要

示例图展示了从低分辨灰度图到高质量配对图的逐步改进

 

 

 

当数据的维度（特征数量）越来越多时，很多机器学习方法（包括KNN）的性能会急剧变差，这种现象就叫“维度灾难”。

 

 

怎么解决维度灾难？

 

降维：如 PCA、t-SNE、autoencoder 等压缩特征

特征选择：只保留最重要的特征

使用对高维更稳健的模型：比如支持向量机（SVM）、神经网络等