机器学习

机器学习数学基础：概率统计与矩阵知识梳理

概率统计理论基础

概率统计是机器学习中不可或缺的基石，它为理解数据、构建模型和评估结果提供了理论支撑。

随机试验与随机事件

• 随机试验：指在一定条件下，结果不确定的观测或试验。
• 随机事件：随机试验可能发生的结果，分为必然事件、不可能事件和随机事件。
• 事件关系与运算：包括事件的包含 ()、相等 ()、积/交 ()、互不相容 ()、和/并 ()、对立 ()、差 ()。事件间的运算满足交换律、结合律、分配律和对偶原则。

概率基本概念与重要公式

• 概率 (Probability)：度量随机事件发生可能性大小的数值，满足非负性 ()、规范性 ()、有限可加性和互补性 ()等性质。
• 联合概率 (Joint Probability)：事件A和B共同发生的概率，记作 或 。
• 条件概率 (Conditional Probability)：事件B已发生的条件下，事件A发生的概率，记作 。
• 独立事件 (Independent Events)：事件A的发生不影响事件B发生的概率。
• 条件独立 (Conditional Independence)：在给定事件C的条件下，事件A和B相互独立。
• 乘法公式 (Multiplication Theorem/Formula)： 。可推广到多个事件。
• 全概率公式 (Law of Total Probability)：用于已知原因求结果的概率， 。
• 贝叶斯公式 (Bayes’ Theorem)：用于已知结果求原因的概率， 。它连接了先验概率、似然概率和后验概率。

随机变量及其数字特征

• 随机变量：将随机试验结果映射到实数上的函数。
• 概率分布函数 (CDF)：描述随机变量取值不超过某个实数的概率， 。具有单调不减、非负有界、右连续等性质。
• 离散型随机变量：取值是有限或可数无限个的随机变量，其概率分布可用概率分布律表示。
• 连续型随机变量：取值是不可数无限个的随机变量，其概率分布可用概率密度函数 (PDF) 描述。
• 期望 (Expectation)：随机变量的概率平均值。
• 方差 (Variance)：描述随机变量值偏离期望值的程度。
• 标准差 (Standard Deviation)：方差的平方根。
• 矩：包括原点矩和中心矩。
• 协方差 (Covariance)：衡量两个随机变量线性相关程度。
• 相关系数 (Correlation Coefficient)：标准化的协方差，。
• 高斯分布 (Gaussian Distribution)：机器学习中常见的概率分布，包括一维和多维形式。

概率密度函数估计

根据样本数据估计概率密度函数 。

• 参数化方法 (Parametric Methods)：假设概率密度函数形式已知，估计未知参数。
  • 最大似然估计 (Maximum Likelihood Estimation, MLE)：选择使似然函数（观测到样本集的概率密度）最大的参数值作为估计值。需要求解似然函数或对数似然函数的导数为零的方程。
  • 估计量的性质与评价标准：无偏性、渐近无偏性、有效性、一致性。
• 非参数化方法 (Nonparametric Methods)：概率密度函数形式未知，直接依据样本估计总体分布。
  • 直方图方法：将数据空间划分成小区域，统计落入各区域的样本数来估计概率密度。
  • Parzen窗法 (Parzen Window Method)：使用窗函数对样本进行加权，估计概率密度。
  • k近邻法 (k-nearest Neighbor Method)：固定落入区域内的样本数k，通过确定包含k个近邻的区域体积来估计概率密度。

矩阵基础概念 (课后拓展)

矩阵是处理多维数据和线性变换的重要工具。

矩阵的定义与特殊矩阵

• 矩阵：由m行n列数组成的数表。
• 特殊矩阵：方阵 (行数=列数)、行矩阵、列矩阵、零矩阵 (所有元素为零)、单位矩阵 (主对角线为1，其余为0)、对角矩阵 (非主对角线元素为0)、对称矩阵 ()。
• 行列式与矩阵的区别：行列式是一个数值，矩阵是一个数表。

矩阵的运算

• 加法：同型矩阵对应元素相加。
• 数乘：数与矩阵中每个元素相乘。
• 乘法：第一个矩阵的列数等于第二个矩阵的行数时才能相乘。矩阵乘法不满足交换律。
• 幂：方阵的多次相乘。
• 转置：矩阵的行换成同序数的列得到的新矩阵。
• 逆矩阵：对于方阵A，如果存在矩阵B使得 ，则B为A的逆矩阵，记作 。逆矩阵具有唯一性。
• 秩 (Rank)：矩阵中不等于零的最高阶子式的阶数。
• 迹 (Trace)：方阵主对角线元素之和。
• 求导：向量对向量的求导得到Jacobian矩阵。

机器学习模型评估与选择：核心概念与方法

机器学习基础回顾

首先，回顾机器学习的定义：一个计算机程序如果在任务T上，用性能指标P衡量，随经验E的增加，性能得到提高，则称该程序从经验E中学习到了任务T。根据输出变量的类型和学习方式，机器学习主要分为监督学习（分类、回归）、无监督学习（聚类、降维）以及半监督学习。

• 监督学习：数据拥有标签。
  • 分类：输出是离散值，如手写数字识别。
  • 回归：输出是连续值，如天气预测。
• 无监督学习：数据没有标签。
  • 聚类：将数据分组。
  • 降维：减少数据维度。

分类和回归任务有不同的训练和测试过程，核心在于从带有标签的训练数据中学习规律，并对新的测试数据进行预测。

模型评估与选择的核心问题

模型的误差是预测输出与真实输出之间的差异。

• 训练误差或经验误差：模型在训练集上的误差。
• 测试误差（Testing error）：模型在新样本上的误差，反映模型的泛化能力。

模型评估与选择的目标是选择在未知数据上表现最好的模型，即最小化测试误差。这通常包括以下步骤：

1. 将数据集划分为训练集和测试集。
2. 在训练集上训练模型。
3. 在测试集上评估模型的泛化性能。
4. 基于评估结果进行模型选择。

数据集划分方法

为了客观评估模型的泛化能力，需要将数据集进行划分。常用的方法包括：

• 留出法（Hold-out）：将数据集随机划分为训练集和测试集。通常采用2/3数据用于训练，1/3用于测试。优点是简单易行，缺点是受数据划分方式影响较大。
• 随机子抽样（Random Sub-sampling）：多次重复留出法，取平均结果。可以减少单次划分带来的偏差，但每个样本被用于训练的次数不同。
• k折交叉验证（k-fold Cross-validation）：将数据集划分为k个大小相似的互斥子集。每次用k-1个子集训练，1个子集测试，重复k次。每个样本都被用于测试一次，用于训练k-1次。相比留出法和随机子抽样，评估结果更稳定可靠。
• 留一法（Leave-one-out）：k折交叉验证的特殊情况，k等于样本总数。每次只留下一个样本做测试。评估结果比较准确，但计算量巨大，适用于数据集较小的情况。
• 自助法（Bootstrapping）：通过有放回地从数据集中抽样，生成多个与原数据集大小相同的训练集。未被抽到的样本组成测试集。约有36.8%的样本不会被抽到。适用于数据集较小的情况，能够产生多个不同的训练集，对集成学习有利，但改变了数据集的初始分布，可能引入估计偏差。

不同的划分方法有各自的适用场景以及对方差和偏差的影响。

模型的性能度量

根据任务类型，有不同的性能度量指标。

回归任务

主要使用误差来衡量预测值与真实值之间的差距：

• 平均绝对误差（Mean Absolute Error, MAE）：
• 均方误差（Mean Squared Error, MSE）：

分类任务

基本指标包括：

• 错误率：分类错误的样本数占总样本数的比例。
• 准确率：分类正确的样本数占总样本数的比例，1 - 错误率。
  错误率和准确率直观且计算简单，但在数据类别不均衡时可能无法全面反映模型性能。

为了更详细地评估分类器性能，特别是处理类别不平衡问题时，引入以下概念和指标，通常基于混淆矩阵（Confusion Matrix）：

对于二分类问题（正例P，负例N）：

真实类别 \ 预测结果	正例 P	负例 N
正例 P	真正例 TP	假负例 FN
负例 N	假正例 FP	真负例 TN

这里对表中的四个概念进行一些解释：真正例指被分类器正确分类的正元组，真负例指被分类器正确分类的负元组，假正例指被分类器错标称正的负元组，加负例指被分类器错标为负的正元组

• 准确率（Accuracy）：
• 错误率（ErrorRate）：
• 查准率（Precision）：预测为正例的样本中，真正例的比例。 。衡量模型预测正例的准确性。
• 查全率（Recall）或敏感性（Sensitivity）：所有真正例中，被模型正确识别为正例的比例 。衡量模型找出所有正例的能力。

查准率和查全率互相矛盾，查准率高则查全率低，反之亦然

• 真阳性率（True Positive Rate, TPR）：等同于查全率。
• 真阴性率（True Negative Rate, TNR）或特异性（Specificity）：所有真负例中，被模型正确识别为负例的比例 。衡量模型找出所有负例的能力。
• 假阳性率（False Positive Rate, FPR）：所有真负例中，被模型错误识别为正例的比例 。

查准率和查全率往往存在矛盾，可以通过 P-R曲线 Precision-Recall Curve来可视化模型在不同阈值下的查准率和查全率表现。

综合查准率和查全率的指标：

• F1度量：查准率和查全率的调和平均，。
• F度量：允许调整查全率对查准率的相对重要性，。时更侧重查全率，时更侧重查准率。

其他重要的分类评估工具包括：

• ROC曲线（Receiver Operating Characteristic Curve）：以TPR为纵坐标，FPR为横坐标，反映模型在不同阈值下识别正例和负例的能力。 [cite: 50]
• AUC（Area Under Curve）：ROC曲线下的面积，用于衡量模型的整体性能，AUC值越大，模型性能越好。 [cite: 51]

代价敏感性能度量

在某些应用中，不同类型的错误可能导致不同的损失。代价敏感性能度量考虑了这一点，通过代价矩阵（Cost Matrix）定义不同误分类的代价，并计算代价敏感错误率。

贝叶斯决策理论：让机器做出更明智的判断

在机器学习领域，我们经常面临如何让机器根据已有数据做出最优决策的问题。贝叶斯决策理论正是解决此类问题的一大利器，它为我们提供了一个在不确定性条件下进行最优决策的数学框架。本文将带您梳理贝叶斯决策理论的核心概念，助您理解机器如何“思考”并做出判断。

一、概率论基础回顾：决策的基石

在深入贝叶斯决策理论之前，我们首先需要回顾几个关键的概率论概念，它们是理解贝叶斯决策的基石。

• 乘法公式：用于计算多个事件同时发生的概率。简单来说，事件A和事件B同时发生的概率等于在事件B发生的条件下事件A发生的概率乘以事件B发生的概率，即 。这个公式可以推广到多个事件的情况。
• 全概率公式：当某个事件B的发生总是伴随着一系列互不相容的事件 之一发生时，事件B的概率可以通过对所有 求和得到。它描述了“知因求果”的过程，即在已知各种原因发生的概率及其导致结果发生的条件下，计算结果发生的总概率。
• 贝叶斯公式：这是贝叶斯决策理论的核心。它恰好与全概率公式相反，描述了“知果求因”的过程。即在结果事件B已经发生的条件下，推断某个原因事件 发生的条件概率。其基本形式为：
  

公式中的 被称为先验概率（在观测到结果B之前对原因 的判断），而 被称为后验概率（在观测到结果B之后对原因 的修正判断）。贝叶斯公式告诉我们，对结果的任何观测都将增加我们对原因事件真实分布的认识。

二、贝叶斯决策理论：核心思想与应用

贝叶斯决策理论的目标是在各种可能的决策中选择期望损失最小的决策。在分类问题中，这意味着将样本划分到后验概率最大的那个类别。

1. 基本概念

在讨论贝叶斯决策之前，我们先明确几个基本概念：

• 样本 (Sample)：通常表示为一个d维向量 ，代表我们观察到的一个具体实例。
• 类别/状态 (Class/State)：用 表示，代表样本可能属于的不同类别。
• 先验概率 (Prior Probability)：，表示在没有任何其他信息的情况下，某个类别 本身出现的概率，是由以往历史数据得到的概率
• 后验概率：，表示利用最新输入数据对先验概率加以修正后
  的概率
• 类条件概率密度 (Class-conditional Probability Density)：，表示在已知样本属于类别 的条件下，观察到样本的概率密度。
• 样本分布密度 (Sample Distribution Density)：，表示观察到样本x的概率密度，可以通过全概率公式计算得到：。

2. 最小错误率贝叶斯决策

这是贝叶斯决策中最常用的一种策略。其核心思想是：对于一个给定的样本x，我们计算它属于各个类别的后验概率 ，然后选择具有最大后验概率的那个类别作为决策结果。这样做可以使得总体分类错误率最小。

根据贝叶斯公式，。由于对于同一个样本x，其 是相同的，因此比较后验概率 的大小，等价于比较 的大小。

所以，最小错误率贝叶斯决策的规则可以表示为：若 对所有 成立，则判决 。

举个例子：假设我们将某工厂生成的零件分为A B两类，两类产品的先验概率为：

且已知类条件概率密度函数服从正态分布：

• 均值为5，标准差为1
• 均值为8，标准差为1.5

那么对于一个新的长度为的零件，我们只需要计算与哪个更大，即将新的零件归为哪类的后验概率更大，就将其归为哪类。

3. 最小风险贝叶斯决策

在某些场景下，不同的错分带来的损失是不同的。例如，在医疗诊断中，将病人误诊为健康（漏诊）和将健康人误诊为病人（误诊）所带来的风险可能不同。最小风险贝叶斯决策考虑了这种不同错分带来的损失。

它引入了一个损失函数 ，表示当真实类别是 时，我们采取决策 (即将样本判为类别) 所带来的损失。那么，对于一个样本，采取决策 的条件风险 (Conditional Risk) 可以表示为所有可能真实类别的期望损失：，其中c是类别总数。

最小风险贝叶斯决策的规则是：计算样本采取每个可能决策 时的条件风险 ，然后选择使得条件风险最小的那个决策。

可以证明，最小错误率贝叶斯决策是最小风险贝叶斯决策在损失函数取特定值（例如，正确分类损失为0，错误分类损失为1）时的一个特例。

4. 朴素贝叶斯决策

在实际应用中，直接估计类条件概率密度 往往非常困难，尤其是当样本x的维度很高时。朴素贝叶斯决策为了简化计算，做了一个很强的假设：给定类别时，样本的各个特征之间是条件独立的。

这意味着 ，其中 是样本x的第k个特征。

尽管这个独立性假设在现实中往往不成立，但朴素贝叶斯分类器在很多情况下仍然表现出惊人的良好性能，并且计算简单、易于实现。

5. 贝叶斯估计

在前面的讨论中，我们假设先验概率 和类条件概率密度 是已知的。但在实际问题中，它们往往是未知的，需要从训练数据中进行估计。贝叶斯估计提供了一种估计这些概率参数的方法。与最大似然估计等方法不同，贝叶斯估计将待估计的参数也看作是随机变量，并为其引入先验分布，然后根据观测数据计算其后验分布。

总结

贝叶斯决策理论为我们提供了一个强大而灵活的框架，用于在不确定性下做出最优决策。从基本的概率回顾到最小错误率、最小风险以及朴素贝叶斯决策，再到参数的贝叶斯估计，这一理论贯穿了机器学习的诸多方面。理解贝叶斯决策的原理，不仅能帮助我们更好地应用相关的机器学习算法，也能启发我们对智能决策过程的深入思考。

机器学习中的线性模型：回归与分类

在线性模型中，我们探索如何使用简单的线性关系来解决复杂的机器学习问题，主要分为回归和分类两大任务。

初识线性模型

机器学习算法大致可分为监督学习和无监督学习。监督学习进一步细分为处理离散输出的分类问题和处理连续输出的回归问题。无监督学习则包括聚类和降维等任务。以下将重点讨论监督学习中的线性模型，特别是回归和分类。

回归：预测连续值

回归的起源与概念

“回归”一词最早由英国生物学家弗朗西斯·高尔顿（Francis Galton）提出。他在研究父母身高与子女身高关系时发现，如果父母身高高于平均身高，其子女身高倾向于“回归”到大众平均身高；反之亦然。

在机器学习中，回归的目标是找到一个函数，将输入变量映射到一个或多个连续的输出变量，并使预测值与真实值之间的差距尽可能小。例如，根据房屋的面积、卧室数量、房龄等特征来预测房价。

线性回归模型

最简单的回归模型是线性回归，它假设输出是输入特征的线性组合。其数学表达式可以写成：

其中， 是模型参数（权重）， 是输入特征向量（为了包含截距项 ，通常会增加一个恒为1的特征 ）。

为了增强模型的表达能力，可以使用基函数（Basis Functions）对原始输入特征进行变换。常见的基函数包括多项式基函数、高斯基函数和Sigmoid基函数。变换后的模型仍然是关于参数 的线性模型：

求解回归问题

求解线性回归问题的核心是确定模型参数 。基本思想是最小化预测值与真实输出值之间的差异。这通常通过定义一个目标函数（代价函数）来实现，最常用的是均方误差：

目标是找到使 最小的 。

我们有两种主要方法来求解这个问题：

1. 标准方程组 (Normal Equations):
   通过直接对代价函数求导并令其等于0，可以得到参数 的解析解。将代价函数写成矩阵形式 ，求导后得到：
   

2. 梯度下降 (Gradient Descent):
   梯度下降是一种迭代优化算法。它首先随机初始化参数 ，然后沿着代价函数梯度的反方向逐步更新参数，直到收敛。

   更新规则为：
   ，其中 是学习率（步长）。

   • 批处理梯度下降 (Batch Gradient Descent)：每次更新参数时使用所有的训练样本。对于凸函数，它可以保证达到全局最优，但在大样本情况下迭代速度较慢。
   • 随机梯度下降 (Stochastic Gradient Descent)：每次更新参数时只使用一个训练样本。它的收敛速度较快，对大样本数据更有效，并且有可能跳出局部最优解。也可以采用小批量（Mini-Batch）的方式，即每次使用一小部分样本进行更新。

梯度下降 vs. 标准方程组

特点	梯度下降法	标准方程组
学习率	需要选择	不需要选择
迭代次数	需要多次迭代	不需要迭代
数据归一化	通常需要	通常不需要
样本量	适用于非常大的样本量	样本量大时计算 成本高

分类：预测离散类别

分类是监督学习的另一个重要问题，其目标是将输入变量分配到预定义的离散类别中。

线性判别函数

当类条件概率密度难以直接估计时，我们可以直接设计分类器，即判别函数。线性判别函数是最简单的一种，其形式为：

其中 是权向量， 是阈值权。

决策规则通常是：如果 ，则样本属于类别 ；如果 ，则样本属于类别 。
定义了一个决策面，在线性情况下它是一个超平面。向量 是这个超平面的法向量。判别函数 的值可以看作是样本点 到决策超平面距离的一种代数度量，其符号表示样本点在超平面的哪一侧。

• 广义线性判别函数：通过对原始特征进行非线性变换（例如，增加平方项 ），可以将非线性可分问题转化为高维空间中的线性可分问题，此时的判别函数称为广义线性判别函数。但这也可能导致维度灾难。
• 线性判别函数的齐次化：通过引入增广样本向量 和增广权向量 ，线性判别函数可以写成齐次形式 。这使得决策超平面在增广空间中通过原点，简化了表达和计算。

线性分类器设计

设计线性分类器的目标是利用训练样本找到最优的参数 和 （或 。一般步骤如下：

1. 准备带有类别标签的训练样本集。
2. 确定一个准则函数 ，它能够反映分类器的性能，其极值对应“最好”的决策。
3. 通过优化算法求解准则函数的极值，得到最优参数。

常见的准则函数包括：

1. Fisher准则

旨在找到一个投影方向，使得投影后类间离散度尽可能大，同时类内离散度尽可能小。

以二分类为例，假设d维样本为属于第类的样本，我们记第类样本的均值向量为

第样本类内离散度矩阵为

总类内离散度矩阵为

将每个向量投影至一维Y空间后得到，相应的我们有样本均值

以及样本类内离散度和总离散度

我们希望投影后在一维空间中的样本尽量分开，即两类均值之差越大越好，同时样本离散度越小越好。综合来看，我们就能够得到Fisher准则函数：

化为矩阵形式后，准则函数为：

其中 是类间离散度矩阵， 是总类内离散度矩阵。最终由拉格朗日乘子法解得最优的投影方向为 。

2. 感知机准则 (Perceptron Criterion)：

感知机模型本身是一个二元线性分类器，旨在找到一个超平面，将输入空间中的数据点划分为两个类别。其核心思想是错误驱动学习，即关注那些被当前模型错误分类的样本，并根据这些错误来调整模型的权重和偏置项，以期在下一次迭代中能够正确分类这些样本，或者至少减少分类的错误程度。

• 增广

在原样本向量的头部加入类别标签，将维向量增广至维。举例来说，假设向量属于类别A，向量属于类别B，那么增广的形式可以是：

• 线性可分：

假设现在有一组增广后的样本向量分别来自两个类别，如果存在一个权重向量，对于任意使得，那么称这组样本是线性可分的。

现在我们希望寻找这样一个权重向量，那么我们可以构造一个准则函数，它的大小取决于被错分类的样本。

其中表示被错分类的样本集合。当被错分类时：

每轮迭代中，如果遇到了这样的错分类向量，便将其放入错分类集合。每轮迭代后，我们可以使用梯度下降法求解解向量。将对求偏导，得到

那么每轮迭代权重更新的表达式为

其中是一个超参数，称为学习率。我们根据准则函数不断更新权重向量，直到不再发生变化

• 感知机准则的结果不唯一，且在样本线性不可分的时候无法收敛

3. 最小二乘准则 (Least Squares Criterion)

基于均方误差最小化来求解模型参数的方法称为“最小二乘法”。均方误差具有很好的几何意义，它对应着欧式距离，在线性分类问题中，最小二乘法就是试图找到一条直线，使所有样本到该直线的距离最短。

因此，我们可以定义如下准则函数

目标是求解使该准则函数取得最小值

最小二乘法对异常值（Outlier）非常敏感。

解密决策树：从基本概念到高级技巧

决策树是一种广泛应用于机器学习领域的强大工具，它通过一系列简单直观的规则来辅助决策和分类。本文将带您深入了解决策树的核心概念、主要算法以及在实践中可能遇到的挑战与解决方案。

什么是决策树？

想象一下，您在决定是否要出门打网球。您可能会考虑天气（晴朗、阴天、下雨？）、湿度（高、正常？）、风力（强、弱？）等因素。决策树就像是把这个决策过程可视化，它是一个树状结构，其中：

• 内部节点：代表一个“问题”或“属性”（例如，“天气如何？”）。
• 分支：代表该问题的一个可能“答案”或“属性值”（例如，“晴朗”）。
• 叶节点：代表最终的“决策”或“分类结果”（例如，“适合打网球”或“不适合打网球”）。

通过从根节点开始，根据实际情况回答一系列问题，沿着相应的分支向下，最终就能到达一个叶节点，从而得到决策结果。这种方法不仅直观，还可以看作是一系列“如果…那么…”规则的集合。

构建决策树：核心算法

构建决策树的关键在于如何选择最优的属性来进行划分，目标是让每个分支下的数据尽可能属于同一类别，即节点的“纯度”越来越高。以下是几种主流的决策树生成算法：

ID3

ID3 (Iterative Dichotomiser 3) 算法的核心思想是采用自顶向下的递归方法，利用信息论中的熵和信息增益作为属性选择的度量标准，从而构建一棵能够对数据进行有效分类的决策树。

为了理解ID3算法，首先需要掌握两个关键的信息论概念：

1. 信息熵 (Information Entropy)

在信息论中，熵是衡量一个随机变量不确定性大小的度量。对于一个样本集合 ，假设其中包含 个不同的类别，第 类样本所占的比例为 ( )，则集合 的经验信息熵定义为：

其中，， 是属于第 类的样本数量， 是样本总数。 的值越小，表示样本集合 的纯度越高，即不确定性越小。当集合中所有样本都属于同一类别时，熵为0；当样本均匀分布在各个类别时，熵达到最大值。ID3算法的目标就是通过选择合适的属性来不断降低子集的熵，从而使得划分后的数据更有序。

2. 条件熵 (Conditional Entropy)

条件熵 表示在已知随机变量 的条件下，随机变量 的不确定性。在决策树的上下文中，假设我们选择属性 来划分数据集 。属性 有 个可能的取值 ，根据属性 的不同取值，可以将数据集 划分为 个子集 。那么，在给定属性 的条件下，数据集 的经验条件熵 定义为：

这里， 是属性 取值为 的样本子集的大小， 是该子集的经验信息熵，其计算方式为：

3. 信息增益 (Information Gain)

信息增益是ID3算法进行属性选择的核心度量。它表示在得知某一属性 的信息后，使得数据集 的不确定性减少的程度（即熵的下降程度）。特征 对训练数据集 的信息增益 定义为集合 的经验熵 与特征 给定条件下的经验条件熵 之差：

ID3算法在每一步选择节点时，会计算所有候选属性的信息增益，并选择那个使得信息增益最大的属性作为当前节点的划分属性。其直观意义是，选择这个属性进行划分，能够最大程度地降低数据集的混乱程度，使得划分后的子集尽可能地“纯净”。

C4.5

ID3 算法使用信息增益作为属性选择标准时，存在一个显著的偏好，即倾向于选择那些具有较多取值的属性，即使这些属性的实际分类能力并不强。为了克服这一缺陷，C4.5 引入了信息增益率。

信息增益率的定义为信息增益 与属性 的“固有值”(Intrinsic Value) 或称“分裂信息”(Split Information) 的比率：

其中，属性 的固有值 定义为：

这里， 是属性 的不同取值的数量， 是数据集中属性 取第 个值的样本数量， 是数据集的总样本数量。属性的取值越多， 的值通常也越大。通过将信息增益除以这个固有值，C4.5 算法能够对取值数目较多的属性进行“惩罚”，从而缓解了 ID3 算法的偏好性，使得属性选择更为公平和合理。
值得注意的是，C4.5 并非直接选择信息增益率最大的属性，而是采用一种启发式策略：先从候选属性中找出信息增益高于平均水平的属性，然后再从这些属性中选择信息增益率最高的。这样做是为了避免分裂信息 过小（例如属性取值非常少时）导致信息增益率被不成比例地放大。

CART (Classification and Regression Trees)

CART (Classification and Regression Trees) 算法是一种广泛应用的决策树构建算法，由 Breiman 等人于1984年提出。与 ID3 和 C4.5 算法不同，CART 算法生成的决策树是严格的二叉树，即每个非叶节点只有两个分支。这一特性使得 CART 树的结构更为简洁。CART 算法既可以用于分类任务，也可以用于回归任务，其核心思想是通过递归地将当前样本集划分为两个子集，使得划分后的纯度（分类树）或均方误差（回归树）最优。

在构建分类树时，CART算法采用基尼指数 (Gini Index) 作为选择最优划分属性和最优划分点的标准。

数据集的基尼指数：基尼指数衡量的是从数据集中随机抽取两个样本，其类别标记不一致的概率。因此，基尼指数越小，数据集的纯度越高。对于一个给定的样本集 ，假设有 个类别，第 类样本所占的比例为 ，则数据集 的基尼指数定义为：

其中， 是属于第 类的样本数量， 是样本总数。

属性划分的基尼指数：当根据属性 的某个可能取值（或对于连续属性的某个划分点）将数据集 分为两个子集 和 时，划分后的基尼指数定义为这两个子集基尼指数的加权平均：

CART 算法的目标是选择一个属性 和该属性的一个划分方式（对于离散属性是值的二分组合，对于连续属性是一个阈值），使得划分后的 最小。即最优划分属性 和最优划分方式的选择标准为：

决策树的挑战与优化

在实际应用中，决策树可能会遇到一些问题，需要相应的策略进行优化：

1. 过拟合 (Overfitting)：决策树在训练数据上表现很好，但在新的、未见过的数据上表现较差的现象。这可能是因为决策树过于复杂，学习到了训练数据中的噪声或一些偶然的规律。

   • 剪枝 (Pruning)：是解决过拟合的主要手段。
     • 预剪枝 (Pre-pruning)：在决策树生成过程中，对每个节点在划分前进行评估，如果划分不能带来泛化性能的提升，则停止划分。这样做可以减少训练时间和过拟合风险，但可能导致欠拟合。
     • 后剪枝 (Post-pruning)：先生成一棵完整的决策树，然后自底向上对非叶节点进行考察，如果将其替换为叶节点能提升泛化性能，则进行替换。这种方法通常能带来更好的泛化性能，但训练开销更大。

2. 处理连续值属性：像ID3这样的早期算法无法直接处理连续值的属性。C4.5等算法采用二分法对连续属性进行离散化处理。具体做法是，将连续属性的取值排序，然后选择最佳的分割点将数据分为两部分，计算信息增益（或增益率、基尼指数），并选择最优的分割点。

3. 处理缺失值：实际数据中常常存在某些属性值缺失的情况。C4.5算法提供了一种处理缺失值的方法：

   • 属性选择时：仅使用在当前属性上没有缺失值的样本来计算信息增益。
   • 划分样本时：如果样本在某个属性上的值缺失，可以将该样本以一定的权重（基于已知值的样本分布）分配到所有子节点中。

4. 处理不同代价的属性：在某些应用场景（如医疗诊断）中，获取不同属性值的代价可能不同。此时，可以在属性选择标准中引入代价因素，例如将信息增益除以代价，或使用更复杂的代价敏感函数，优先选择低代价的属性。

支持向量机 (SVM)

SVM 概述：寻找最优的“分界线”

SVM 最早由 C. Cortes 和 V. Vapnik 于1995年提出，其理论基础是统计学习理论 (Statistical Learning Theory, SLT)。简单来说，SVM 的核心思想是在特征空间中找到一个能够将不同类别样本最好地分离开的超平面（在二维空间中可以理解为一条直线）。所谓“最好”，指的是这个超平面不仅能正确地将两类样本分开，而且使得离它最近的样本点（即支持向量）到该超平面的间隔最大化。这个间隔被称为“边距 (Margin)”。

线性支持向量机：从硬间隔到软间隔

1. 线性可分与最大间隔（硬间隔SVM）

在理想情况下，数据集是线性可分的，即存在一个超平面能完美地将两类样本分开。线性SVM的目标就是找到这个具有最大间隔的超平面。这个超平面可以表示为 。

对于每一个样本点，其到超平面的距离可写为

如果超平面能够正确分类所有样本，那么对于任意样本都应该符合下式

若某样本点恰好使得上式取得等号，那么称其为“支持向量”

支持向量机希望在该式的约束下，找到具有最大“间隔”的划分超平面。我们“间隔”为两个异类支持向量到超平面的距离

而最大化间隔等价于最小化 ，或者更方便的，最小化

2. 处理噪声与离群点：软间隔SVM的引入

在现实世界的数据中，样本往往不是完全线性可分的，或者存在一些噪声和离群点。硬间隔SVM在这种情况下可能会表现不佳，甚至找不到合适的分类面。为了解决这个问题，软间隔SVM被提了出来。

软间隔SVM允许一些样本点被错误分类或者进入间隔区域，即允许某些样本不满足约束：

但在最大化间隔时，我们又希望不符合约束的样本尽量的少，因此可将优化目标改写为

由于我们只希望将“不符合约束”的情况加入到目标表达式中，因此需要一个损失函数来进行一个filter操作，过滤掉符合约束的情况，而将不符合约束的情况进行计数。通过观察这个表达式，显然当C为无穷大时，该表达式不允许任何的错分类情况出现，当C为有限值时，表达式允许一些错分类情况

我们引入松弛变量 来表示某个样本被错分类的程度，其计算方式为

相应的，我们可以将目标表达式改写为以下形式：

软间隔SVM的求解过程与硬间隔类似，同样利用拉格朗日乘子法和KKT条件。其最终的决策边界也主要由支持向量决定。软间隔SVM通过在准确性和泛化性之间进行权衡，使其在处理复杂数据集时更具鲁棒性。

相较于硬间隔，软间隔的泛化性更好一些，但由于求解时有超参数惩罚系数，其求解过程更复杂。

非线性支持向量机：核技巧

当数据呈现非线性分布时，线性SVM就无能为力了。这时，非线性SVM通过引入“核技巧 (Kernel Trick)”来解决问题。

核技巧的核心思想是将原始输入空间的样本通过一个非线性映射函数 映射到一个更高维的特征空间，使得原本在低维空间中线性不可分的样本在高维空间中变得线性可分。然后，就可以在高维特征空间中使用线性SVM进行分类。

然而，直接进行高维映射和计算会带来巨大的计算量（维度灾难）。但我们可以设想一个函数，使得与在高维特征空间中的内积结果等于在原始样本空间中利用该函数进行计算的结果，即

关键在于，我们无需关心 函数具体的形式，只需要知道一定存在这样一种低维向高维的映射，使得映射后的点积结果等于该核函数的结果。

常用的核函数包括：

• 线性核 (Linear Kernel):
• 多项式核 (Polynomial Kernel):
• 高斯核 (Gaussian Kernel / RBF Kernel):
• Sigmoid 核 (Sigmoid Kernel):

选择合适的核函数对于非线性SVM的性能至关重要，若核函数不合适，则意味着将样本映射到了一个不合适的特征空间，因此通常需要根据具体问题和数据特性进行选择。

SVM 的求解：序列最小优化算法 (SMO)

SVM的学习问题最终可以归结为一个凸二次规划问题。对于小规模数据集，可以使用通用的二次规划求解器。但当训练样本数量很大时，这些算法的效率会变得很低。

序列最小优化算法 (Sequential Minimal Optimization, SMO) 是一种高效的启发式算法，专门用于解决SVM的对偶问题。SMO的基本思想是：如果所有变量都满足KKT条件，则优化问题的解就找到了。SMO算法不断地将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量都满足KKT条件为止。由于子问题存在解析解，每次计算都非常快，因此即使子问题数量很多，总体上仍然高效。

感知器

一个简单的感知器是一种双层神经网络模型，包含一层输入神经元 和一层输出神经元 。每个输入神经元与输出神经元之间都有一定的连接权值 。输出神经元的活跃值由所有输入神经元的加权和以及激活函数共同得到：

我们可以通过监督学习和无监督学习两种方式对权重参数不断更新、调整不同神经元之间的连接强度

• 监督学习

每次获得某输出神经元的结果 后，计算其与目标值的误差并对权重进行更新：

• 无监督学习

它不依赖于外部提供的目标输出或误差信号，学习的依据是神经元之间的活动相关性：只有当两个相连的神经元同时被激活，即输出神经元的值大于0，它们之间的连接权重才会显著增强。

反向传播

对于上面的单层神经网络，我们可以使用梯度下降的方法对权值向量进行更新，然而多层感知器只能计算出输出层的误差，中间隐层由于不直接与外界连接，其误差无法估计。因此我们引入反向传播算法来解决这个问题。

假设现在有三个相邻层。节点接收的节点的输出为，节点的输出为，其他节点的输入输出计算方法同理。现在要计算误差相对于连接神经元 和 的权重 的梯度：

其中是可以直接计算的，结果为，将剩余部分记为。而又可以通过链式法则进行进一步拆解：

那么现在我们就可以根据的值计算的值了，然后再像上面的感知器一样更新第层的权值，就达到了更新隐藏层权值的目的

输出层作为最后一层，是比较特殊的。假设层为输出层，由于直接与，即输出层输出的信息相关，因此我们可以直接计算出：

• 局限性

反向传播作为一种改进型的梯度下降法，它也同样有着“可能陷入局部最优解”的缺点。

深度学习

CNN

CNN有一些特点，不过与其说特点不如说计算步骤：

1. 局部卷积操作：仅将局部窗口中的内容通过卷积核映射至特征图中的相应位置
2. 共享权重参数：卷积层在所有空间位置上共享权重。这减少了参数的数量，并实现了有效的计算。例如，如果将3×3滤波器应用于5×5输入，则在整个输入中重复使用相同的滤波器权重。
3. 多卷积核运算：每个卷积层可以有多个过滤器，每个过滤器检测不同的特征。
4. 池化(Pooling)处理：池层在减少特征映射的空间维度方面发挥着至关重要的作用，使模型的计算效率更高，更不容易过拟合。通过总结特征图的局部区域中的信息，池化有助于保留最重要的特征，同时丢弃不太相关的细节。这种降维也减少了后续层中的参数数量，加快了训练和推理。
5. 多层处理：单层卷积及池化仅学到局部特征。层数越多，所学特征越全局。层与层之间常使用激活函数以避免了梯度爆炸和梯度消失问题

优化

关于梯度下降

• 梯度下降的变体：
  • 随机梯度下降（SGD）：每次使用单个训练样本更新参数。速度快，但可能产生噪声。
  • 批量梯度下降（BGD）：每次更新使用整个训练集。收敛稳定，但计算成本高且可能陷入局部极小值。
  • 小批量梯度下降（MBGD）：目前标准的做法，使用一小批样本来更新参数。它平衡了BGD的稳定性和SGD的效率。
• 自适应优化器：为了克服选择合适学习率和应对困难拓扑结构的挑战，一系列自适应优化算法被开发出来。
  • 动量（Momentum）：该方法通过将先前更新向量的一部分添加到当前更新中，引入”惯性”，有助于在相关方向上加速SGD并抑制振荡。
  • Adagrad：为每个参数调整学习率，对频繁更新的参数使用较小的更新，对不频繁的参数使用较大的更新。它非常适合处理稀疏数据。
  • RMSprop：改进Adagrad，以解决其学习率急剧下降的问题。
  • Adam（自适应矩估计）：这是当今最常用的优化器。它结合了动量和自适应学习率（如RMSprop）的思想，在各种问题上通常都很有效。

关于梯度消失

随着网络越来越深，训练也变得越来越困难，例如会出现梯度消失问题，即网络浅层的梯度变得无限小，导致学习停滞。一些关键技术被开发出来以有效训练非常深的网络：

• ReLU（修正线性单元）：定义为 f(x)=max(0,x) 的激活函数。 它的非饱和特性和简单的梯度有助于缓解梯度消失问题，并显著加快训练速度。
• Dropout：一种强大的正则化技术，在训练期间随机将一部分神经元的激活设置为零。 这可以防止复杂的协同适应，迫使网络学习更鲁棒、更冗余的特征，从而减少过拟合。
• 批量归一化（Batch Normalization）：该技术对每一小批数据的层输出进行归一化。 它能稳定并加速训练过程，允许使用更高的学习率，减少对初始化的依赖，并起到正则化的作用。
• 残差连接（ResNets）：如前所述，这些”捷径”连接让梯度可以直接流过网络，通过确保增加层数不会降低性能，从而实现了极深架构的训练。

聚类计算

K-Means

K-Means算法是一种无监督的聚类算法，其核心思想是：对于给定的样本集，按照样本点之间的距离大小，将样本集划分为K个簇，并让簇内的点尽量紧凑，簇间的点尽量分开

给定待聚类的样本数据集，并设定超参数：聚类簇数量

1. 从中随机选择个样本作为聚类中心，设对应向量分别为
2. 计算各个样本到所有聚类中心的距离，并将其加入距离最近的簇中
3. 计算新的簇中心向量：
4. 重复第二步和第三步，直到簇中心向量不再发生变化

K-Means++

K-Means++的改进点在于初始的K个聚类中心的选取方法上。它不再通过随机选取，而是通过一下方式获得初始聚类中心：

1. 随机选取一个点作为聚类中心，之后选取一个距离该中心最远的点作为第二个聚类中心
2. 假设已经选择了个聚类中心，计算每一个数据点距离当前已有聚类中心的最短距离，每一个数据点被选为聚类中心的概率为：
3. 重复步骤2，直到选出K个聚类中心，就得到了初始聚类中心

ISODATA

在K-Means基础上增加对聚类结果的合并和分裂操作。具体来说，当两个聚类的中心距离小于某一阈值，则将他们合并为一个簇，当某类标准差大于一个阈值或其样本数多于某一阈值，则将其分裂为两个簇。

但这一方法导致超参数又变多了，这是我们不喜欢的

数据降维

为什么要降维

在原始的高维空间中，包含冗余信息和噪声信息，会在实际应用中引入误差，影响准确率；而降维可以提取数据内部的本质结构，减少冗余信息和噪声信息造成的误差，提高应用中的精度。

降维

本质上是利用某种映射将原高维度空间的数据点投影到低维度的空间

降维方法

需要注意的是，降维是一种无监督的学习方法，用于无监督的连续型数据学习

主成成分分析法 PCA

目的：将原有众多具有一定相关性的指标重新组合成一组少量互相无关的综合指标。

可能的实现路径：

• 使降维后样本的方差尽可能大，方差大了相关性一定就小了
• 从误差的角度看，希望尽可能少的去除有效信息，即使得降维后数据的均方误差尽可能小

1. 最大方差思想

假设我们现在有一个维数据集，现在需要将其降为维，。首先考虑，定义这个空间的投影方向为维向量，并令，那么每个数据点在新的一维空间中的表示为。

那么样本均值在新的一维空间中的表示为，其中，代表D维空间中的平均向量；

投影后的样本方差表示为

其中代表原样本的协方差矩阵

因此我们的目标就是最大化，同时有等式约束。利用拉格朗日乘子法并对求导置0，得到，进一步得到，其中是矩阵的特征值。根据要求，是所有特征值中最大的那个，那么就是矩阵最大特征值对应的特征向量，称为第一主成分，它指出了包含信息最多的一个方向

考虑更一般的维的情况。在获得第一主成分后，我们需要寻找第二个主成分，它使最大化，且满足单位向量约束，且满足与第一个主成分正交。经过推导，是协方差矩阵的第二大特征值对应的特征向量。以此类推，我们能够找到前大的特征值对应的特征向量。

2. 最小均方误差思想

目标：使原数据与降维后的数据（在原空间中重建后）的误差最小

首先在维空间中定义一组正交的维基向量，满足。由于基是完全的，那么每个数据点都可以表示为基向量的线性组合：

以上的过程相当于进行了一个的坐标变换。事实上，这一变换过程也可以用公式来表示。

将该式代入会上面的式子，得到

在D维空间中对M维空间中的向量进行近似表示的方式为：

其中是独特的，是共享的。

现在我们可以定义一个目标最小化失真度：

我们的目标就是最小化这个，对求导置0，分别得到，。将他们到中，得到：

依然采用拉格朗日乘子法，求导得到，将该等式再带入的表达式得到：

因此，要使最小，需要取个最小的特征值，即去掉这些最小特征值，保留个最大特征值，这与最大方差思想最终得到的结果是一致的

• 计算步骤

  • 计算给定样本的均值向量和协方差矩阵
  • 计算的特征向量与特征值
  • 将前M大的特征值对应的特征向量构成投影矩阵

• 优点

  • 具有很高普适性，最大程度地保持了原有数据的信息；
  • 可对主元的重要性进行排序，并根据需要略去部分维数，达到降维从而简化模型或对数据进行压缩的效果
  • 完全无参数限制，最终结果仅与数据有关

• 局限性

  • PCA假定数据的底层结构是线性的，因此它能进行的主元分析之间的关系也是线性的
  • 如果数据有较高信噪比，那么具有最高方差的一维向量可能是噪声

PCA vs LDA

PCA是无监督的，它的目标是希望投影后数据点尽可能分散、方差尽可能大；LDA是有监督，它的目标是希望投影后不同类别的点尽可能分散，而同一类别的点尽可能集中

Kernal PCA

将主成分分析的线性假设一般化使之适应非线性数据

等距映射

目标：保持数据点内在的几何性质（测地距离）

• 优点
  • 非线性
  • 非迭代
  • 全局最优
  • 参数可调
• 缺点
  • 容易受噪声干扰
  • 在大曲率区域存在短路现象
  • 不适用于非凸参数空间
  • 大样本训练速度慢

局部线性嵌入

前提假设：假设流形是 “局部线性的”

集成学习

集成学习算法分为两大类：串行化方法和并行化方法

串行化方法

串行化方法的典型算法为Boosting算法

核心思想：先训练一个基础学习器，根据该学习器的分类结果，提升错分类样本的权重，使错分类的样本在之后收到更多关注，然后基于调整后的数据集训练出下一个基学习器，直到基学习器的数量达到指定值。最终将这些基学习器加权结合。

Boosting族算法的著名代表为AdaBoost算法。该算法在每个基学习器训练完成后对其分类误差进行评估，根据误差大小设置该学习器的权重，误差越小权重越大。最终根据这些权重将基学习器进行组合。

特点：串行化方法使得不同学习器之间的相关性很强，导致方差不能显著降低，但串行训练能够逐步最小化损失函数，导致偏差降低。

并行化算法

• Bagging

核心思想：采用自助采样法构造T个包含m个训练样本的采样集，基于每个采样集训练一个基学习器，之后将他们结合：分类任务通常使用简单投票法，回归任务使用简单平均法。

特点：并行方法主要关注降低方差，在易受样本扰动的学习器上效果明显。一般不能显著降低偏差

• 随机森林

核心思想：使用自主采样法构造多个采样集，每个采样集选择一定数量的最优特征作为决策树的输入特征，根据每个采样集分别获得决策树，最后采用投票法或平均法得到结果

基学习器的多样性通过样本扰动和属性扰动实现，算法简单、容易实现。

半监督学习

半监督

所谓半监督学习，是指数据集中只有少量有标记的样本，其余样本均无标记，利用这样的数据集进行训练被称为半监督学习

基本假设

要利用未标记样本，就需要做一些将未标记样本所揭示的数据分布信息与类别标记相联系的假设

• 聚类假设

从全局角度看，假设数据结构存在簇结构，同一簇中的样本属于同一类。

• 流形假设

从局部来看，数据分布在一个流形结构，临近的样本具有相似的输出值。该假设认为处于很小局部区域内的样本应该具有相似性质，因此样本的标记也应该相似

半监督学习算法

半监督学习算法可分为“半监督分类算法”与“半监督聚类算法”：

• 半监督分类
  • 自学习方法
  • 直推式向量机
• 半监督聚类
  • 约束K均值算法
  • 约束种子K均值算法

半监督分类

• 自学习方法

核心思想：分类器递归拟合，每次递归时将满足指定置信度的样本放入已标记样本集，然后用新的样本集重新训练，直至未标记样本集为空

典型代表：最近邻自学习算法。使用已标记样本集合训练出一个分类器，然后选择距离已标记样本最近的未标记样本，使用当前分类器为该样本确定类别，然后将其加入已标记样本集合。重复以上过程直到没有未分类样本

• 半监督SVM

又称S3VM，其中直推式支持向量机T-SVM是最典型的算法

核心思想：遍历所有样本，通过尝试将每个样本分别作为正例和反例来寻找最优分类边界，以得到原始分类间隔中两类样本的最大分类间隔

它对传统SVM的约束表达式进行了修改：

其中分别代表已标记样本和未标记样本的惩罚因子，在初始化时需要设置，因为为标记样本的伪标记不准确，对应系数要小，在迭代过程中逐步提高的数值来增加未标记样本的贡献

由于遍历非常耗时，可以采用局部搜索迭代求近似解

半监督聚类

半监督聚类任务通常有两种数据集：

• 具有“必连与勿连”约束的数据集，必连指示某两个样本必须属于同一类，勿连指示某两个样本一定不是同一类
• 有少量标记的数据集

利用第一类数据集的典型算法有**约束K均值（Constrained K-means）**算法。相较于普通K-means算法，它在将某一样本归入距离其最近的类时，需要判断是否与“必连勿连”条件冲突，如果冲突则尝试次近的类

利用第二类数据集的典型算法有**约束种子K均值（Constrained Seed K-means）**算法。它直接使用有标记的样本初始化K个聚类中心，并且在聚类簇迭代过程中不改变这些样本所属的类