Pattern recognition concepts

• Definition and description of basic terminology
• Recap of feature extraction and representation

Supervised learning for classification

• Nearest class mean classification
• K-nearest neighbours classification
• Bayesian decision theory and classification
• Decision trees for classification
• Ensemble learning and random forests

模式识别

模式识别简介 Introduction of Pattern Recognition

这是一个科学学科，目标是自动识别数据中的模式和规律。

例子

• 对象识别（例如：图像分类）
• 文本分类（例如：垃圾邮件/非垃圾邮件）
• 语音识别（例如：自动字幕）
• 事件检测（例如：在监控中）
• 推荐系统（例如：在网上商店中）

模式识别类别 Pattern Recognition Categories

基于不同的学习范式，可以分为：

• 监督学习（Supervised learning）： 学习一组具有可用标签（地面真相）的数据中的模式。

• 无监督学习（Unsupervised learning）： 在一组没有任何可用标签的数据中寻找模式。

• 半监督学习（Semi-supervised learning）： 使用带标签和不带标签数据的组合来学习模式。

• 弱监督学习（Weakly supervised learning）： 在模式学习中使用嘈杂的/有限的/不精确的监督信号。

模式识别基本概念 Pattern Recognition Concepts

• 对象（Objects）：是图像拍摄的（可识别的）物理实体
• 区域（Regions）：在图像分割后（理想情况下）对应于对象
• 类别（Classes）：是具有共同特征的对象的不相交子集
• 标签（Labels）：与对象相关联并指示其所属的类别
• 分类（Classification）：是基于特征将标签分配给对象的过程
• 分类器（Classifiers）：是执行分类任务的算法/方法
• 模式（Patterns）：是对象特征中的规律，并由分类器使用

• 预处理（Pre-processing）：旨在增强图像以便进一步处理。
• 特征提取（Feature extraction）：通过测量某些属性来减少数据。
• 特征描述符（Feature descriptors）：表示对象的标量属性。
• 特征向量（Feature vectors）：捕捉从数据中测量的所有属性。
• 特征选择（Feature selection）：旨在仅保留最具描述性的特征。
• 模型（Models）：是类别的（数学或统计）描述。
• 训练样本（Training samples）：是用于建立模型的带有已知标签的对象。
• 成本（Cost）：是做出错误决策/分配的后果。
• 决策边界（Decision boundary）：是特征空间中区域之间的分界线。

模式识别系统设计中的基本阶段

1. 图像采集（Image acquisition）：获取需要处理和分析的图像。
2. 预处理（Pre-processing）：对图像进行初步处理，例如噪声去除、图像增强等。
3. 特征提取（Feature extraction）：从预处理后的图像中提取有用的特征。
4. 特征选择（Feature selection）：选择最能代表图像特征的子集，减少数据维度。
5. 学习系统（Learning system）：使用选定的特征进行学习，建立分类模型。
6. 系统评估（System evaluation, test）：评估分类模型的性能和准确性。

模式识别模型 Pattern Recognition Models

生成模型（Generative models）

• 建模数据生成的“机制”
• 通过概率模型 $p(x|y)$ 和 $p(y)$ 来表示每个类别
• 获取数据的联合概率为 $p(x,y) = p(x|y)p(y)$
• 通过最大似然 $p(y|x)$ 隐式地找到决策边界
• 适用于无监督学习任务（未标记数据）

判别模型（Discriminative models）

• 关注决策边界的显式建模
• 适用于监督学习任务（有标记数据）

特征提取 Feature Extraction

通过以下特征对对象进行表征：

• 相同类别/类别中的对象具有相似的测量值
• 不同类别的对象具有不同的测量值

使用区分特征：

• 对象位置不变（平移）
• 对象方向不变（旋转）
• 对……不变（取决于应用）
• 好的例子有形状、颜色、纹理

特征的设计通常基于先前的经验或直觉

选择对以下方面具有鲁棒性的特征：

• 刚性变换（平移和旋转）
• 遮挡和其他3D到2D的投影失真
• 非刚性/关节对象变形（例如：手指握住杯子）
• 光照和阴影的变化

特征选择是依赖于问题和领域的，需要领域知识。

分类技术可以帮助使特征值对噪声的敏感度降低，并从较大的特征集中选择有价值的特征。

监督学习 Supervised Learning

• 特征空间 $X$ 和 标签空间 $Y$
• 函数 $f \in F: X \rightarrow Y$
• 训练集 $\{(x_i, y_i) \in X, Y\}$

学习阶段

• 找到一个函数 $\hat{f}$ 使得 $y_i \approx \hat{f}(x_i)$
• 生成模型 $\hat{f}$

预测阶段

• 对测试样本 $x$ 进行预测
• 输出 $y = \hat{f}(x)$

分类（Classification）

• 分类器通过将类标签分配给对象来执行对象识别，使用对象描述的特征。
• 完美分类通常是不可能的，而是确定每个可能类别的概率。
• 困难由对象在同一类别内和不同类别之间的特征值的变异性引起：
  • 变异性可能由于复杂性但也可能由于噪声引起。
  • 噪声特征和缺失特征是主要问题。
  • 并非总是可能确定对象所有特征的值。

下图：

• 一个对象（鱼）的分类示例，其中 $x \rightarrow y = \text{salmon}$
• 确定每个类别的概率，例如 $p_{\text{salmon}} = 0.7$ 和 $p_{\text{bass}} = 0.3$
• 类别的可视化分布，显示了宽度和亮度的特征在分类中的应用。

二分类（Binary Classification）

• 给定一个包含 ( N ) 个观测值的训练集：

  $$\{(x_i, y_i)\}, \quad x_i \in \mathbb{R}^d, \quad y_i \in \{-1, 1\}$$

• 分类是估计 $y_i = f(x_i)$ 的问题。

图示展示了一个二分类问题的例子，蓝色圆点和红色三角形分别代表两个类别，通过一条分界线（黄色曲线）将它们分开。

最近类别均值分类器 Nearest Class Mean Classifier

• 基于最小距离原则，其中类别样本仅是类别的质心（或均值）。

训练：给定训练样本对 $\{(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)\}$，每个类别 $k$ 的质心通过以下公式获得：

测试：如果未知对象的特征向量 $x$ 更接近于类别 $k$ 的质心而不是任何其他类别的质心，则将其分类为类别 $k$。

图示说明：

1. 图中有三类数据：蓝色圆点、红色三角形和绿色星星。
2. 橙色的质心表示蓝色圆点的均值，红色三角形的质心是橙色三角形。
3. 绿色星星表示一个未知对象。图中展示了绿色星星到橙色圆点质心和橙色三角形质心的距离。
4. 绿色星星到橙色圆点质心的距离大于到红色三角形质心的距离，因此绿色星星被分类为红色三角形类别。

多模式问题解决

• 图中展示了三个类别：Class 1、Class 2 和 Class 3。
• Class 1 用 “X” 表示，Class 2 用 “O” 表示，Class 3 用 “+” 表示。
• 每个类别都有一个黑点表示其质心（均值）。

Class 2 的问题：

• Class 2 有两个模式，即有两个集中区域。
• 如果只使用一个质心，Class 2 的质心会位于这两个模式的中间位置，这可能不能准确代表任何一个模式。

解决方法：

• 如果检测到多个模式，可以使用两个子类质心（subclass centroids）来更准确地表示每个模式。

说明：

1. 单质心：

   • 对于 Class 2，如果只使用一个质心，则质心会位于两个模式的中间（两个模式的平均位置）。
   • 这种情况下，质心不能准确代表 Class 2 的任何一个模式，从而可能导致分类错误。

2. 多质心：

   • 如果检测到多个模式，可以为每个模式计算一个质心。
   • 这种方法可以更准确地表示 Class 2 的结构，提高分类器的性能。

当类别内部有多个模式时，使用单一质心可能不够准确，建议使用多个子类质心来更好地表示数据结构。

优缺点

优点（Pros）：

• 简单（Simple）：算法简单易懂，计算量较小。
• 快速（Fast）：计算质心和分类速度较快。
• 效果良好（Works well）：当类别紧凑且彼此相距较远时，分类效果很好。

缺点（Cons）：

• 对复杂类别效果差（Poor results for complex classes）：对于具有多模态（multimodal）、非球形（non-spherical）的复杂类别，分类效果不好。
• 无法很好地处理异常值和噪声数据（Cannot handle outliers and noisy data well）：对异常值和噪声数据的处理能力较差，容易受到这些数据的影响。

K近邻分类器 K-Nearest Neighbours Classifier

定义：K-NN是一种分类器，它基于数据集中最接近的K个样本来决定一个样本的类别标签。通过计算测试样本与所有训练样本之间的距离，选择K个最近的训练样本来决定测试样本的类别。

1. 左图：最近类别均值分类器（Nearest Class Mean）

   • 图示展示了最近类别均值分类器的工作原理，绿色星星表示未知样本。
   • 通过计算到橙色圆点质心和红色三角形质心的距离，将样本分类为更接近的类别。在这个例子中，绿色星星被分类为红色三角形类别，因为它更接近红色三角形的质心。

2. 右图：K近邻分类器（K-NN）

   • 图示展示了K-NN分类器的工作原理，绿色星星表示未知样本。
   • 计算绿色星星到所有样本的距离，然后选择K个最近的样本（这里K可能是3或更多），根据这些最近邻的类别来决定绿色星星的类别。
   • 在这个例子中，K近邻中有两个红色三角形和一个蓝色圆点，所以绿色星星被分类为红色三角形类别。

计算过程

计算距离：

1. 对每个新的测试样本，计算该测试样本与所有训练样本之间的距离。
2. 选择距离最近的K个训练样本。

多数表决：

1. 测试样本将被分配到在K个最近邻中占多数的那个类别。
2. 从已知类别的训练样本集中选择最近邻。

计算距离方式：

• 欧几里得距离（Euclidean distance）：常用于连续变量的情况。图中左下角的散点图展示了一个例子，绿色星号表示未知类，红色方块和蓝色方块分别表示两种已知类。KNN分类器会根据距离最近的K个邻居来决定未知类的分类。

• 汉明距离（Hamming distance）：常用于离散变量的情况。表格展示了汉明距离的计算示例，两个二进制数之间的汉明距离是它们不同位置的数量。

优缺点

优点：

• 非常简单和直观：KNN算法非常容易理解和解释。
• 容易实现：算法的实现比较简单，不需要复杂的编程技巧。
• 没有先验假设：KNN算法不需要对数据进行假设，这使得它可以应用于各种类型的数据。
• 无需训练步骤：KNN是一种惰性学习方法，不需要模型训练阶段。
• 决策边界是非线性的：KNN的决策边界可以是非常复杂和非线性的，适用于多种模式识别任务。

缺点：

• 对大数据集来说算法比较慢：因为KNN需要计算每个测试点与所有训练数据点的距离，所以在数据量很大的情况下计算开销非常大。
• 需要同质的特征类型和尺度：KNN要求输入的特征具有相似的性质和尺度，否则需要进行标准化处理。
• 在变量数量增加时表现不好：当特征数量增加时（维度灾难），KNN的表现会显著下降。
• 找到最佳的K值具有挑战性：选择合适的K值（邻居的数量）对算法的表现有重要影响，但选择过程可能比较复杂。

贝叶斯决策理论 Bayesian Decision Theory

1. 分类器的决策可能是正确的，也可能是不正确的，因此它们应该是概率性的（软决策而不是硬决策）：贝叶斯决策理论认为，分类器的决策应当基于概率，这样可以反映决策的不确定性，而不是简单地做出二元的硬性决策。

2. 可以使用概率分布来做出具有最小期望错误率的分类决策：通过利用概率分布，可以计算出在不同情况下的期望错误率，从而选择错误率最小的决策。

3. 引入先验知识：贝叶斯决策理论的重要特点之一是引入先验知识，即利用已有的知识或经验来调整决策过程。

图中右下角的直方图展示了两个类别（鲑鱼和海鲈）的亮度分布，通过概率分布可以确定分类的决策边界（$x*$）。

贝叶斯分类法 Bayesian Classification

贝叶斯分类：根据观察到的特征，将一个对象分配到它最有可能属于的类中。

假设以下信息是已知的：

• 每个类别 $c_i$ 的先验概率 $p(c_i)$
• 类条件分布 $p(x|c_i)$

计算后验概率 $p(c_i|x)$ 的方法：

根据贝叶斯定理，如果所有类别都是不相交的，后验概率由以下公式给出：

决策规则

1. 给定观察到的特征 $x$：

   • 如果 $p(c_1|x)$ 比 $p(c_2|x)$ 大，我们自然会倾向于认为它属于类别 $c_1$。

2. 决策规则：

   • 选择后验概率最大的类别：
     $$c = {\arg \max}_i (p(c_i|x))$$

3. 等价于：

   • 选择使得 $p(x|c_i)p(c_i)$ 最大的类别：
     $$c = {\arg \max}_i (p(x|c_i)p(c_i))$$

4. 公式：

   • 后验概率 $p(c_i|x)$ 可以表示为：
     $$p(c_i|x) = \frac{p(x|c_i)p(c_i)}{\sum_j p(x|c_j)p(c_j)} = \frac{p(x|c_i)p(c_i)}{p(x)} \propto p(x|c_i)p(c_i)$$

错误概率

1. 对于给定的观测 $x$，错误概率 $p(\text{error}|x)$ 计算如下：

   • 如果我们决定选择 $c_2$，错误概率是 $p(c_1|x)$
   • 如果我们决定选择 $c_1$，错误概率是 $p(c_2|x)$

   公式表示为：

   $$p(\text{error}|x) = \begin{cases} p(c_1|x) & \text{if we decide } c_2 \\ p(c_2|x) & \text{if we decide } c_1 \end{cases}$$

2. 通过以下决策可以最小化错误概率：

   • 如果 $p(c_1|x) > p(c_2|x)$，则选择 $c_1$
   • 如果 $p(c_2|x) > p(c_1|x)$，则选择 $c_2$

3. 这被称为贝叶斯决策规则（Bayes decision rule）：

   • 贝叶斯决策规则的核心思想是选择后验概率最大的类别，从而最小化决策错误的概率。

贝叶斯决策例子

例1

• 假设我们要分类鱼的种类：鲑鱼（salmon）、海鲈（sea bass）和其他（other）。
• 根据以往的经验，我们已经知道每个类别的概率：

• 如果我们仅根据先验概率进行决策，最好的选择是总是分类为海鲈（Sea bass），因为它的先验概率最高（0.6）。
• 这种方法称为基于先验的决策规则（decision rule based on prior）。
• 这种方法的问题在于它永远不会预测其他类别，导致分类效果很差。

例子仅仅依赖先验概率的局限性，强调结合观测数据和先验知识的重要性，以提高分类准确性。

例2

• 使用某个特征（例如长度）来增加更多的信息。
• 根据经验，我们知道不同长度下的类条件概率：

• 现在我们可以根据这些类条件概率和先验概率 $p(c_i)$ 来估计每个类别的后验概率 $p(c_i|x)$。

• 后验概率 $p(c_i|x)$ 由以下公式计算：

通过结合观测到的特征（例如长度）的类条件概率和先验概率，我们可以更准确地估计每个类别的后验概率，从而做出更好的分类决策。

例3

• 假设我们有一条长70厘米的鱼，我们的预测是什么？

计算后验概率：

• 根据这些概率，我们预测这条鱼的种类为海鲈（Sea bass）。

如果类条件概率相同，那么先验概率将成为决策的关键因素。在这个例子中，尽管观察到的特征值相同，先验概率较高的类别仍然更可能被选择。

贝叶斯决策风险 Bayesian Decision Risk

如果鲑鱼的价格是海鲈的两倍，而海鲈的价格也高于其他类型的鱼，那么任何误分类的成本是否相同？

• 将高价鱼（鲑鱼或海鲈）误分类为低价鱼（其他类型的鱼）：这种误分类将导致较大的经济损失，因为高价鱼的价值没有得到体现。
• 将低价鱼误分类为高价鱼：这种误分类可能导致额外的成本，例如顾客付出了更多的金钱但得到的却是低价鱼，或者对商家的声誉造成负面影响。
• 将一种高价鱼误分类为另一种高价鱼：例如，将鲑鱼误分类为海鲈，或者将海鲈误分类为鲑鱼。尽管这两种鱼的价格不同，但误分类的成本将取决于两者价格差异的大小。

因此，误分类的成本是不同的，应当根据具体的价格和类别来评估误分类的经济影响。这也强调了在分类过程中考虑成本敏感的决策非常重要。在贝叶斯决策理论中，这可以通过引入损失函数来实现，以更好地反映实际应用中的经济损失。

简介

分类准确性： 如果我们只关心分类的准确性（所有鱼类的价格相同），那么我们可以通过最大化后验概率来做决策。

最小化损失： 如果价格不同，我们需要最小化损失：

• 损失是基于我们决策的行动 $\alpha_i$ 的成本： $\lambda(\alpha_i|c_i)$ （注意，这不是概率）。
• 与行动 $\alpha_i$ 相关的期望损失为：
  $$R(\alpha_i|x) = \sum_j \lambda(\alpha_i|c_j) p(c_j|x)$$
• $R(\alpha_i|x)$ 也称为条件风险（conditional risk）。
• 最优的贝叶斯决策策略是最小化条件风险。

总结：

• 当所有类别的价格相同时，最大化后验概率即可实现最佳分类。
• 当类别的价格不同，误分类的成本也不同，因此应根据具体的损失函数来最小化总体风险。

这种方法可以更准确地反映实际应用中的经济影响，通过考虑不同决策的成本，从而做出更合适的分类决策。

例1

假设我们有以下损失函数 $\lambda(\alpha_i|c_i)$：

计算条件风险：

我们要计算在鱼的长度为50到100厘米之间时，将其分类为鲑鱼的条件风险 $R(\text{sell as salmon} | 50 < x < 100)$：

具体计算：

根据这个示例，我们通过考虑不同类别的损失函数和条件概率，计算出分类错误的条件风险。最优的贝叶斯决策策略是最小化这个条件风险。

例2

在不同分类情况下的条件风险计算结果：

条件风险计算结果：

• 如果鱼的长度在50到100厘米之间，最小化损失的方法是将其预测为鲑鱼（salmon）。

问题：

• 这个示例中的损失函数是否合适？
• 如何定义损失函数？

损失函数的定义取决于实际应用中不同错误分类的成本。在这个例子中，损失函数是根据以下假设定义的：

• 将一种鱼误分类为另一种鱼会产生不同的经济损失。
• 例如，将鲑鱼误分类为海鲈的损失是2，将海鲈误分类为鲑鱼的损失是10。

定义损失函数时需要考虑以下因素：

1. 经济成本：不同错误分类的实际经济影响。
2. 机会成本：由于错误分类而失去的机会。
3. 客户满意度：错误分类对客户满意度的影响。
4. 其他因素：如法规和公司政策等。

一个合适的损失函数应该能够准确反映这些因素，帮助决策者在不同情况下做出最优决策。

概率估计 Estimating the probabilities

这个方法展示了通过样本数据来估计概率分布参数，从而应用贝叶斯决策理论进行分类。

• 经验估计：可以通过样本经验估计 $p(x|c_i)$ 和 $p(c_i)$ 的值。
• 参数模型：如果我们知道分布遵循某种参数模型（定义模型），可以使用样本来估计模型参数（学习参数）。

示例：

• 假设类别 $i$ 可以用一个协方差矩阵 $\Sigma_i$ 已知但均值 $\mu_i$ 未知的正态分布来描述。
• 均值的估计可以是训练集中标记样本的平均值： $\hat{\mu}_i = \bar{x}$

优缺点

优点：

• 简单且直观：贝叶斯决策规则分类器易于理解和实现。
• 考虑不确定性：在做决策时考虑了概率和不确定性，使得决策更加可靠。
• 允许结合新信息与当前知识：可以将新的观测数据与现有的先验知识相结合，不断更新和改进模型。

缺点：

• 计算量大：计算后验概率和最小化条件风险可能需要大量计算资源，尤其是在高维数据集上。
• 先验选择具有主观性：先验概率的选择可能带有主观性，不同的先验选择可能导致不同的结果。

决策树 Decision Trees

• 大多数模式识别方法解决的问题是特征向量为实值的情况，并且存在某种度量标准。
• 有些分类问题涉及名义数据（nominal data），即具有离散描述符且没有自然的相似性或排序概念的数据。
  • 例如：{高，中，低}，{红，绿，蓝}
  • 名义数据也称为分类数据（categorical data）。

名义数据可以使用基于规则的方法进行分类。

连续值也可以使用基于规则的方法处理。

这种方法为处理各种类型的数据提供了灵活性，特别是在特征不易度量或排序时，基于规则的方法可以有效地进行分类。

决策树概要 Decision Trees Summary

方法：

• 通过一系列问题分类样本：决策树通过一系列的问题来逐步分类样本。
• 下一个问题取决于当前问题的答案：每个问题的答案决定了接下来要问的问题。
• 问题序列显示在有向决策树或简单的树中：决策树是一种直观的方式来表示分类过程。

结构：

• 树中的节点表示特征：每个节点表示一个特征。
• 叶节点包含类别标签：叶节点表示最终的分类结果。
• 一次一个或几个特征来分割搜索空间：每次使用一个或几个特征来划分数据。
• 每个分支节点有一个子节点表示父特征的每个可能值：每个分支节点代表一个特征的一个值，连接到相应的子节点。

分类：

• 从根节点开始：分类过程从根节点开始。
• 跟随适当的链接到达叶节点：根据特征的值选择路径，直到到达叶节点。
• 将叶节点的类别标签分配给测试样本：最终，测试样本被分配到叶节点的类别标签。

决策树构建 Desicion Trees Construction

• 二叉决策树：一种具有与每个节点相关的决策函数的二叉树结构。

• 数值特征值和决策函数选择左/右分支，如果特征值低于/高于某个阈值。

• 每个节点仅使用一个特征和一个阈值。

• 给定一组训练样本：可能存在多个决策树能够对它们进行分类，这取决于特征的顺序。

• 选择最佳树：我们必须根据某些标准选择能给出“最佳”树的特征。

• 计算方面最小的树优先：在计算上，最小的树通常是首选。

算法步骤 Algorithm

• 选择一个特征放置在节点上（第一个是根节点）：
  • 选择一个用于分割数据的特征。
• 为每个可能的值（名义）或范围（数值）创建一个分支：
  • 根据特征值的不同创建分支。
• 对于每个分支节点，使用实际到达该分支的样本重复步骤1和2：
  • 继续分割数据，直到达到某个终止条件。
• 当节点上的所有样本具有相同的分类（或标签）时，停止生长该部分树：
  • 如果节点上的所有样本都属于同一类，则该节点成为叶节点，不再分裂

如何确定要分裂的特征？

• 使用信息论中的度量标准：

  • 熵（Entropy）：熵衡量了系统的混乱程度或不确定性。
  • 信息增益（Information Gain）：信息增益衡量了某个特征在分裂数据集时减少的不确定性。

• 决策树例子展示了根据长度 $x_1$ 和宽度 $x_2$ 的分裂决策。

  • 首先根据长度 $x_1 > 80$ 分裂。
  • 然后根据宽度 $x_2 > 10$ 或 $x_2 > 30$ 进一步分裂。
  • 最后根据长度 $x_1 > 110$ 进行最终分裂。

通过使用熵和信息增益，可以选择最优的特征进行分裂，从而构建出有效的决策树。这种方法确保每一步分裂都能最大程度地减少系统的不确定性，从而提高分类的准确性。

这个图片介绍了如何使用熵来构建最优决策树：

构建最优决策树 Constructing Optimal Desicion Tree

熵 Entropy

要从训练数据中构建最优决策树，我们必须定义“最优”。基于信息论的一个简单标准是熵。

• 一组事件 $y = \{y_1, y_2, ..., y_n\}$ 的熵 $H(y)$ 定义为：

  $$H(y) = \sum_{i=1}^{n} -p(y_i) \log_2 p(y_i)$$

  其中 $p(y_i)$ 是事件 $y_i$ 的概率。

• 熵可以视为信息源的不确定性的平均值。

  • 如果信息源没有不确定性：$H = 0$
  • 如果信息源不确定：$H > 0$

图展示了不同随机性和熵的情况：

• 高随机性，高熵，高混乱。
• 低随机性，低熵，低混乱。

通过最小化熵，可以选择最优的特征进行分裂，从而减少分类的不确定性和提高分类准确性。

信息增益 Information Gain

信息增益是基于熵的度量，用于指导在构建最优决策树时选择哪个特征。

如果 $S$ 是一组训练样本，$f$ 是样本的一个特征，则相对于特征 $f$ 的信息增益定义为：

其中：

• 这表示总体熵减去特征 $f$ 的值分裂后的加权熵。

选择具有最高信息增益的特征进行分裂：使用信息增益最大的特征来分裂数据，从而减少不确定性并提高分类效果。

这个方法通过最大化信息增益来选择分裂特征，使得每次分裂后数据的混乱程度（熵）都能最大程度地降低，从而构建出高效的决策树。

示例

例1：熵

考虑鱼类分类的例子，我们有三个类别：鲑鱼（Salmon）、海鲈（Sea bass）和其他（Other）。每个类别的先验概率分别为：

• 鲑鱼：0.3
• 海鲈：0.6
• 其他：0.1

熵的计算：

• 将这些概率代入公式，熵的计算如下：
  $$H = -[0.3 \log_2(0.3) + 0.6 \log_2(0.6) + 0.1 \log_2(0.1)] = 1.29$$

例2：信息增益

有两个特征：长度$x_1$和宽度$x_2$，为了示例假设每个特征有三个类别：

• $x_1 \in \{\text{Small}, \text{Medium}, \text{Large}\}$

• $x_2 \in \{\text{Small}, \text{Medium}, \text{Large}\}$

• 表格列出了两个类别（鲑鱼和海鲈）的15个观测值/样本：

熵的计算：

对于特征 $x_1$：

信息增益 $IG(S, x_1)$：

对于特征 $x_2$：

信息增益 $IG(S, x_2)$：

由于 $IG(S, x_2) > IG(S, x_1)$，决策树首先选择特征 $x_2$ 进行分裂。

• 根据其分支划分数据集，并在每个分支上重复相同的过程。
• 熵大于0的分支需要进一步分裂。

优缺点

优点：

• 易于解释：决策树的结构类似于人类的决策过程，直观易懂。
• 可以处理数值和分类数据：决策树能够处理各种类型的数据，包括连续的数值数据和离散的分类数据。
• 对离群值和缺失值具有鲁棒性：决策树不容易受到异常数据点和缺失值的影响。
• 提供特征重要性的信息：通过决策树，可以得出每个特征在分类任务中的重要性，有助于进行特征选择。

缺点：

• 容易过拟合：决策树模型如果没有适当的剪枝，容易对训练数据过拟合，影响在测试数据上的泛化能力。
• 仅进行轴对齐的分裂：决策树的分裂仅沿着特征轴进行，无法处理一些复杂的分类边界。
• 贪婪算法：决策树的构建使用贪婪算法，每次选择最优的分裂，但未必能找到全局最优的决策树结构。

集成学习 Ensemble Learning

集成学习结合多个模型以提高预测性能，相较于单一模型可以获得更好的效果。

构建多个模型的方法：

• 使用不同的分类器或学习算法。
• 对同一算法使用不同的参数。
• 使用不同的训练样本。
• 使用不同的特征集。

集成学习的核心思想是通过结合多个模型的预测结果，来减少单一模型可能带来的偏差和方差，从而提高整体的预测准确性。常见的集成学习方法包括随机森林（Random Forest）、梯度提升树（Gradient Boosting Trees）和集成投票法（Voting Classifier）等。

随机森林 Random Forests

• 定义：随机森林是一种集成学习方法。
• 构建方法：通过训练构建多个决策树的集成。
• 输出：通过个别树的多数投票结果来确定最终分类。
• 优点：克服了单个决策树过拟合的问题。

随机森林通过构建多个决策树，并让这些树独立地对样本进行分类，最后通过多数投票来决定最终的分类结果，从而提高了模型的准确性和稳定性。这种方法能够有效地减小过拟合的风险，并且在处理高维数据和缺失数据时表现良好。

布莱曼算法 Breiman's Algorithm

1. 设定训练实例的数量为 $N$ 和特征的数量为 $M$（采用袋装法）。
2. 从原始数据中随机抽取 $N$ 个实例，并允许重复抽样。
3. 在每个节点上，从 $M$ 个特征中随机选择 $m$ 个特征($m \ll M$），并在最优特征上进行分裂（称为“特征袋装”）。
4. 将每棵树生长到最大的程度（不进行修剪）。
5. 重复 $B$ 次。保持 $m$ 的值在森林生长过程中不变。

测试过程：

1. 将新样本输入树中，分配到终端节点，并赋予终端节点的标签。
2. 遍历所有树，得到 $B$ 个预测结果。
3. 根据所有树的多数投票结果，得到最终的随机森林预测结果。

错误率相关

随机森林的错误率依赖于两个因素：

1. 森林中任何两棵树之间的相关性

   相关性增加会增加森林的错误率；无相关的树更能带来更好的泛化能力。

2. 森林中每棵树的强度

   强树具有较低的错误率。

   增强个别树的强度可以降低森林的错误率。

3. 选择参数 $m$

   减少 $m$ 可以降低相关性和强度。

   增加 $m$ 会增加相关性和强度。

   在某个中间值存在一个“最佳”的 $m$ 范围。

优缺点

优点：

• 高准确度：在许多问题上，随机森林在传统分类算法中具有很高的准确性。
• 有效处理大数据集：在大数据集上高效运作。
• 处理大量特征：可以在不进行特征选择的情况下处理成千上万个输入特征。
• 有效处理缺失值：能够有效处理数据中的缺失值。

缺点：

• 可解释性较差：相比单一决策树，随机森林的可解释性较差。
• 复杂度高：构建随机森林比构建单一决策树更加复杂和耗时。

考试例题

Which one of the following statements is correct for random forest classifiers?

A. Increasing the correlation between the individual trees decreases the random forest classification error rate.

B. Reducing the number of selected features at each node increases the correlation between the individual trees.

C. Reducing the number of selected features at each node increases the strength of the individual trees.

D. Increasing the strength of the individual trees decreases the random forest classification error rate.