Supercised Learning & Reinforesment Learning
决策树分类
前提
- 假设我们有一个包含 $N$ 个样本的训练集,每个样本包含 $M$ 个特征,用 $X_{i,j}$ 表示第 $i$ 个样本的第 $j$ 个特征的取值,用 $y_i$ 表示第 $i$ 个样本的目标值(或标签)。决策树模型的目标是学习从特征到目标值的映射关系,并用学习到的模型对新的样本进行预测。
流程
- 计算特征阈值和判断最优特征
- 通过基尼指数判断最优特征
基尼指数越小表示数据集越纯。
对于一个特征 $A$ 和其取值 $a_i$,假设 $D$ 表示当前节点的数据集,$D_i$ 表示特征 $A$ 取值为 $a_i$ 时的子数据集,则基尼指数计算公式为:
$$Gini(D,A)=\sum_{i=1}^{k}\frac{|D_i|}{|D|}Gini(D_i)$$
其中,$k$ 表示特征 $A$ 的取值数目,$|D_i|$ 表示子数据集 $D_i$ 中样本的数目,$|D|$ 表示当前节点的样本数目,$Gini(D_i)$ 表示子数据集 $D_i$ 的基尼指数,计算公式为:
$$Gini(D_i)=1-\sum_{j=1}^{c}p_{ij}^2$$
其中,$c$ 表示类别数目,$p_{ij}$ 表示子数据集 $D_i$ 中属于第 $j$ 类的样本占比。
基尼指数越小表示使用特征 $A$ 进行划分后,得到的子数据集的纯度越高。因此,决策树算法选择基尼指数最小的特征作为最优特征进行划分。
- 计算特征阈值(用信息增益表示特征阈值)
信息增益是评价特征重要性的一种指标,它表示特征 $x_j$ 对分类的贡献程度。信息增益越大,说明特征的重要性越高。可以通过以下公式计算信息增益:
$$ \begin{aligned} Gain(D,x_j) &= H(D) - \sum_{i=1}^m \frac{|D_i|}{|D|} H(D_i) \\ H &= -\sum p(x) \times log_2[p(x)] \end{aligned} $$
- 其中 $H(D)$ 表示数据集 $D$ 的熵,$m$ 表示特征 $x_j$的可能取值个数,$D_i$ 表示数据集 $D$ 在特征 $x_j$ 取值为 $i$ 时对应的子集,$|D_i|$ 表示子集 $D_i$ 的大小,$|D|$ 表示数据集 $D$ 的大小。
-
对特征 $x_j$ 的取值进行排序,得到一个有序的列表 $[x_1,x_2,\cdots,x_m]$
-
对于相邻的取值 $x_i$ 和 $x_{i+1}$,将它们作为特征阈值 $s$,将数据集划分为两个子集 $D_1={x\in D|x_j\leq s}$ 和 $D_2={x\in D|x_j>s}$
-
计算使用特征阈值 $s$ 进行划分的信息增益 $Gain(D,x_j,s)$
- 根据 $x_j \leq s$ 和 $x_j > s$ 将数据集 $D$ 划分为两个子集 $D_1$ 和 $D_2$ ,然后计算信息增益
$$Gain(D,x_j,s) = H(D) - \frac{|D_1|}{|D|} H(D_1) - \frac{|D_2|}{|D|} H(D_2)$$
-
重复步骤2和3,直到计算完所有相邻取值的信息增益为止。
-
选择信息增益最大的特征阈值作为最终的特征阈值。
-
筛选最优特征
计算训练集的经验熵(entropy)$H(D)$,表示训练集中样本的不确定性
对于每个特征$A$,计算其对训练集的条件熵(conditional entropy)$H(D|A)$,表示在特征$A$已知的条件下,训练集中样本的不确定性,公式为: $$H(D|A)=\sum_{i=1}^{|A|} \frac{|D_i|}{|D|} H(D_i)$$ 其中,$|A|$表示特征$A$可能的取值个数,$|D_i|$表示在特征$A$取值为第$i$个值时,训练集中样本的个数,$H(D_i)$表示在特征$A$取值为第$i$个值时,训练集中样本的经验熵。
计算信息增益(information gain)$g(D,A)$,表示特征$A$对训练集划分的贡献程度,公式为: $$g(D,A)=H(D)-H(D|A)$$
选择信息增益最大的特征作为当前节点的划分特征,将训练集划分成更加纯净的子集,并递归地重复上述步骤,直到所有子集都变得足够纯或达到预定的停止条件为止,生成一棵完整的决策树。
- 需要注意的是,信息增益存在一个缺陷,即它倾向于选择可能取值较多的特征,因为这些特征往往可以划分出更多的子集。为了克服这个缺陷,可以使用其他的划分指标,例如基尼不纯度(Gini impurity)或者增益率(gain ratio),来选择最优的特征。
信息增益比(Information gain ratio)
- 信息增益比是信息增益的一种改进,它考虑了特征取值数目对信息增益的影响。可以通过以下公式计算信息增益比:
$$Gain \ ratio \ (D,x_j) = \frac{Gain(D,x_j)}{IV(x_j)}$$
- 其中 $IV(x_j)$ 表示特征 $x_j$ 的固有值,表示特征 $x_j$ 取值的多样性,可以通过以下公式计算:
$$IV(x_j) = - \sum_{i=1}^m \frac{|D_i|}{|D|} \log_2 \frac{|D_i|}{|D|}$$
- 在特征 $x_j$ 的阈值为 $s$ 时,可以根据 $x_j \leq s$ 和 $x_j > s$ 将数据集 $D$ 划分为两个子集 $D_1$ 和 $D_2$,然后计算信息增益比。
总结
- 以上三种方法都可以用于计算特征阈值,其中基尼指数适用于连续和离散特征,而信息增益和信息增益比适用于离散特征。在实际应用中,我们可以根据具体问题选择不同的评价指标来计算特征阈值,并选择最优的阈值来进行样本划分。
结点判定规则
假设第 $t$ 个节点的判定规则为 $f_t(x)$,其中 $x$ 表示一个样本的特征向量,$f_t(x)$ 返回一个取值为 $0$ 或 $1$ 的标记,表示该样本应该进入该节点的左子树($f_t(x)=0$)还是右子树($f_t(x)=1$)。可以将判定规则表示为:
$$f_t(x) = \begin{cases} 0, & \text{if}\ x \in R_{t,\text{left}} \ 1, & \text{otherwise} \end{cases}$$
其中 $R_{t,\text{left}}$ 是第 $t$ 个节点左子树的样本所在区域,可以用一个特征阈值组合来表示:
$$R_{t,\text{left}} = {x | x_j \leq s_t}$$
其中 $x_j$ 表示样本 $x$ 的第 $j$ 个特征的取值,$s_t$ 是第 $t$ 个节点的特征阈值。右子树的样本所在区域可以表示为 $R_{t,\text{right}} = { x | x_j > s_t }$。
树的结构
决策树模型的树的结构可以用一个树形图或者一组规则来表示。假设决策树模型的根节点为 $t=1$,可以用以下的数学公式来表示该模型:
$$\hat{y}i = \sum{t=1}^T c_t \cdot I(x_i \in R_{t})$$
其中 $\hat{y}_i$ 表示用决策树模型预测样本 $i$ 的目标值,$T$ 表示树的深度或节点个数,$c_t$ 表示第 $t$ 个节点的预测值,可以是该节点所属的样本的平均值或者分类问题中该节点所属的样本中出现最多的类别值, $I(x_i \in R_t)$ 是一个指示函数,如果样本 $i$ 属于第 $t$ 个节点的子树,取值为 $1$,否则取值为 $0$
代码
|
|
随机森林分类
|
|
XGBoost(eXtreme Gradient Boosting) + 网格搜索 + 交叉验证
原理
网格搜索
-
穷举所有给出的参数取值的组合
-
根据交叉验证计算模型质量
-
给出质量最高的模型
交叉验证
-
将数据集分成k个相等大小的子集(折)。
-
对于每个折,将其作为验证集,剩余的k-1个折作为训练集。
-
使用训练集进行模型的训练,并在验证集上进行性能评估。
-
计算模型在当前折上的评估指标(如准确率、F1 分数、均方误差等)。
-
重复步骤2-4,直到每个折都作为验证集并得到了一个评估指标。
-
统计k次评估指标的平均值作为模型的最终评估结果。
XGBoost
-
梯度提升树原理:XGBoost是基于梯度提升树(Gradient Boosting Tree)的算法。梯度提升树是一种迭代的集成学习算法,通过迭代地训练一系列决策树来逐步改进模型的预测能力。每个新的决策树都会尝试纠正前一棵树的预测误差,从而逐步减小模型的残差。
-
XGBoost的目标函数:XGBoost的目标函数由两部分组成:损失函数(Loss Function)和正则化项(Regularization Term)。损失函数衡量模型的预测误差,正则化项控制模型的复杂性。目标函数的目标是最小化损失函数和正则化项的和。
-
模型训练步骤:XGBoost的模型训练步骤如下:
-
初始化模型:将初始预测值设为全局平均值(或使用先验概率)。
-
迭代训练:对于每一轮迭代:
-
计算残差:计算当前模型的预测值与实际值之间的残差。
-
训练一个决策树:使用残差作为目标值,训练一个决策树模型。决策树的构建过程采用贪婪算法,通过优化目标函数来确定最佳的分裂点。
-
更新模型:根据学习率(步长)和决策树的输出,更新模型的预测值。
-
正则化:根据正则化项对树的结构进行修剪,以控制模型的复杂性。
-
-
重复步骤b,直到达到预先设定的迭代次数(即树的数量)或达到停止条件。
- 预测步骤:使用训练好的模型进行预测时,将待预测样本输入到每棵树中,根据树的结构和叶子节点的预测值得到最终的预测结果。最终的预测结果由所有树的预测值加权求和得到。
代码
|
|
Adaboost (Adaptive Boosting)
原理
AdaBoost是一种集成学习算法,用于提高分类器的准确性。它通过迭代地训练一系列弱分类器(即在某个特定任务上表现略好于随机猜测的分类器),并将它们组合成一个强分类器。
下面是AdaBoost算法的基本原理:
-
初始化样本权重:对于包含N个样本的训练集,初始时每个样本的权重相等,即1/N。
-
迭代训练弱分类器:对于每个迭代轮次t(从1到T),进行以下步骤:
-
使用当前样本权重训练一个弱分类器(例如决策树桩),得到分类器ht。
-
计算分类器ht在训练集上的误差率εt,即被错误分类的样本的权重之和。
-
计算分类器ht的权重系数αt,αt = 0.5 * ln((1-εt)/εt)。这个权重系数表示分类器ht在最终的强分类器中的重要程度,当分类器的误差率较低时,其权重系数会更大。
-
更新样本权重:根据样本是否被分类器ht正确分类来更新样本的权重,被错误分类的样本的权重会增加,而被正确分类的样本的权重会减少。
-
构建强分类器:将每个弱分类器的预测结果乘以其权重系数αt,并将它们线性组合得到最终的强分类器。
-
预测:使用强分类器对新样本进行预测。对于二分类问题,预测结果是通过对弱分类器的预测结果进行加权投票得到的。
代码
|
|
模拟退火 (Simulated Annealing, SA)
数学原理和过程 (默认求最小值)
-
令$T = T_0$ 表示开始退火的初始温度,随机产生一个初始解$x_t$,并计算对应的目标函数值
-
令$T= kT, k \in (0,1)$, 为温度下降速率
-
对当前解施加随机扰动,在其邻域内产生一个新解$x_{t+1}$,通过以下公式(MetroPolis 准则)判断是否接受这个解的概率
$$ \begin{aligned} P &= \begin{cases} 1 & E_{t+1} \le E_t \\ e^{\dfrac{-(E_{t+1} - E_t)}{kT}} & E_{t+1} \gt E_t \end{cases} \end{aligned} $$
流程图
应用
- 用于VLSI(超大集成电路设计)
双退火代码
|
|
Regression
多元逻辑回归(Multinomial Logistic Regression)
原理
-
在多元逻辑回归中,我们有一个因变量(多类别)和多个自变量。假设有 k 个类别,我们需要建立 k-1 个二元逻辑回归模型来预测每个类别相对于某个基准类别的概率。
-
数学上,多元逻辑回归使用 softmax 函数将线性组合的结果转化为概率分布。对于第 i 个类别(其中 i = 1, 2, …, k-1),我们定义一个线性组合:
$$ z_i = b_{i0} + b_{i1}x_1 + b_{i2}x_2 + … + b_{ip}x_p $$
- 通过应用 softmax 函数,我们可以计算每个类别的概率。对于第$i$个类别,其概率为:
$$ P(Y=i|X) = exp(z_i) / (exp(z_1) + exp(z_2) + … + exp(z_{k-1})) $$
意义
- 训练多元逻辑回归模型的目标是最大化似然函数或最小化交叉熵损失函数。通常使用梯度下降等优化算法来寻找最优的系数。
代码
|
|
Ridge Regression
原理
- 减小Overfitting
LASSO Regression
Classification
Bayes Algorithms
$$ \begin{gather} \begin{aligned} P(c|X) &= \frac{ P(x|c) P(c)}{ P(X) } \\
\end{aligned} \end{gather} $$
Other Algorithms
贪心算法
一种可能的贪心算法
|
|
动态规划算法
0-1背包问题
|
|
调度
时间片(轮转)
- 需要的已知数据
-
time_slice
: 时间片的长度 -
time_remaining
: 该任务还需要多长时间完成 -
time_available
: 当前时间片内的剩余时间
- 代码
|
|
EDF + Dynamic Programming + Linear Programming
|
|
SRIMAX(滑动平均的改良版)
|
|