决策树模型

特征选择
约定记号:训练集\(D=\{(x_i,y_i)\}_{i=1}^N\), 样本 \(x_i\in\mathbb R^n\), 标签 \(y\in Y=\{c_1,c_2,\cdots,c_K\}\)。

经验熵:将D划分成\(D_1,\cdots, D_K\), 每一子集对应一类标签。设子集\(D_i\)在D中占比为\(p_i=\frac{|D_i|}{|D|}\), 定义经验熵\(H(D)\)为\[H(D)=-\sum\limits_{i=1}^K p_i\log_2 p_i.\] 经验熵刻画了数据集D的纯度。

条件经验熵:给定某维特征A及其取值范围\(\{a_1,\cdots,a_m\}\), 按照特征A也可将D划分为m个子集\(D_1^A,\cdots, D_m^A\).
进一步考察\(D_i^A\)中的分类情况,用\(D_{ik}^A\)表示其中标签为k的子集,则\(D_i^A\)的经验熵为\[H(D_i^A)=-\sum_{k=1}^K \frac{|D_{ik}^A|}{|D_i^A|} \log_2 \frac{|D_{ik}^A|}{|D_i^A|}. \]
用基于特征A划分的子集的平均经验熵,即给定条件A下,D的条件经验熵为\[H(D|A)=\sum_{i=1}^m \frac{|D_i^A|}{|D|}H(D_i^A).\]可以视为给定特征A的条件下,数据集D的纯度度量。

信息增益:定义\[G(D,A)=H(D) - H(D|A).\]刻画使用特征A来划分使得数据集D在纯度上的提升。信息增益越高,说明特征A为分类提供了更多的有效信息,刻画了特征A的分类能力。

使用信息增益准则对训练集中数量较多的属性有所偏好,可以用信息增益率进行修正。
信息增益率:特征A的分裂信息(又称固有值)\(IV(D,A)\)定义为\[IV(D,A)=-\sum_{i=1}^m \frac{|D_i^A|}{|D|}\log_2\frac{|D_i^A|}{|D|},\]并定义信息增益率\(G_R(D,A)\)为\[G_R(D,A)=\frac{G(D,A)}{IV(D,A)}.\]
基尼指数:数据集的基尼指数Gini(D)定义为\[Gini(D) = 1-\sum_{k=1}^K(\frac{|D_k|}{|D|})^2.\]其中平方项反映了从D中随机抽取两个样本,都属于\(c_k\)的概率。基尼指数可以看作从数据集中随机抽取两个样本,其标签不一致的概率。

根据基尼指数划分:特征A的基尼指数定义为\[Gini(D,A)=\sum_{i=1}^m \frac{|D_i^A|}{|D|} Gini(D_i^A).\]Gini(D, A)越小,说明同一\(D_i^A\)内的标签一致性更高,A的分类能力更强。

决策树学习算法
输入训练集D,特征集合\(\mathbb A\)和特征选择函数\(F(\cdot,\cdot)\),输出决策树T。
1. 首先解决平凡情况:(1)D中样本属于同一类别;(2)\(\mathbb A=\emptyset\)。 返回单结点树,并以D中样本最多的类别作为标记。
2. 计算\(A^*=F(D,\mathbb A)\)得到选择的特征, 对于\(A^*\)的每个可能取值\(a_i\),构造一个对应于\(D_i\)的子结点。
3. 若\(D_i=\emptyset\), 以D中最多的类别作为标记,并标记为叶子结点。
4. 对每个\(D_i\)对应的非叶结点,以\(D_i\)为训练集,\(\mathbb A -\{A^*\}\)为特征集,递归调用决策树算法,得到子树\(T_i\)。

决策树剪枝
剪枝能够降低决策树模型的过拟合风险,分为预剪枝和后剪枝。
预剪枝是在生成决策树过程中,如果新展开的结点在验证机上不能带来性能提升,则放弃展开此结点。后剪枝也类似,在构造好的决策树上由下至上分析每个结点。

后剪枝也可采用正则化方法。
定义决策树T的损失函数:\[C_\alpha(T)=C(T)+\alpha|T|.\]其中\(C(T)\)是评估T对D的拟合程度的函数,\(|T|\)是T的叶结点个数作为T的模型复杂度。\(C(T)\)可以定义为:\[C(T) = \sum_{t=1}^{|T|} N_tH_T(T),\]\(N_t, H_t(T)\)分别表示叶结点t对应的数据集大小和经验熵。

最小二乘回归树
使用平方误差最小准则来选择属性和最优切分点。
给定数据集\(D=\{(x_i,y_i)\}\),其中\(y_i\in\mathbb R\).
设回归树模型将输入空间划分成M个单元\(R_1,\cdots,R_M\),使得单元\(R_m\)上的输出值为\(c_m\)。则回归树模型的输出可以表示成\[f(x) =\sum_{m=1}^M c_m\cdot\mathbb I(x\in R_m)\]使用均方误差可得\[\hat c_m = \text{ave} \{y_i|x_i\in R_m\}.\]对于选择切分的维度j和切分点s,定义\(R_1(j,s)=\{x|x^j\le s\}, R_2= (j,s)=\{x|x^j > s\}\). 则通过求解\[\min\limits_{j,s}[\min_{c_1}\sum_{x\in R_1} (y_i-c_i)^2 + \min_{c_2}\sum_{x\in R_2} (y_i-c_i)^2]\]即得最优切分维度和切分点\((j,s)\).

    所属分类:机器学习     发表于2022-05-19