熵表示随机变量不确定性的度量。
设$X$是一个取有限个值的离散随机变量,其概率分布为
\begin{align*} P \left( X = x_{i} \right) = p_{i}, \quad i =1, 2, \cdots, n \end{align*}
则随机变量$X$的熵
\begin{align*} H \left( X \right) = H \left( p \right) = - \sum_{i=1}^{n} p_{i} \log p_{i} \end{align*}
其中,若$p_{i}=0$,则定义$0 \log 0 = 0$
若
\begin{align*} p_{i} = \dfrac{1}{n} \end{align*}
则
\begin{align*} \\ & H \left( p \right) = - \sum_{i=1}^{n} p_{i} \log p_{i}
\\ & = - \sum_{i=1}^{n} \dfrac{1}{n} \log \dfrac{1}{n}
\\ & = \log n\end{align*}
由定义,得
\begin{align*} \\ & 0 \leq H \left( p \right) \leq \log n\end{align*}
设有随机变量$\left( X , Y \right)$,其联合分布 \begin{align*} \\ & P \left( X = x_{i}, Y = y_{j} \right) = p_{ij}, \quad i=1,2, \cdots, n; \quad j=1,2, \cdots, m\end{align*}
随机变量$X$给定的条件下随机变量$Y$的条件熵
\begin{align*} \\ & H \left( Y | X \right) = \sum_{i=1}^{n} p_{i} H \left( Y | X = x_{i} \right) \end{align*}
即,$X$给定条件下$Y$的条件概率分布的熵对$X$的数学期望。其中,$p_{i}=P \left( X = x_{i} \right), i= 1,2,\cdots,n$。
条件熵$H \left( Y | X \right)$表示在已知随机变量$X$的条件下随机变量$Y$的不确定性。
特征$A$对训练集$D$的信息增益
\begin{align*} \\ & g \left( D, A \right) = H \left( D \right) - H \left( D | A \right) \end{align*}
即,集合$D$的经验熵$H \left( D \right)$与特征$A$给定条件下$D$的经验条件熵$H \left( D | A \right)$之差。
其中,当熵和条件熵由数据估计(极大似然估计)得到时,对应的熵和条件熵分别称为经验熵和经验条件熵。
信息增益$g \left( X , Y \right)$表示已知特征$X$的信息而使得类$Y$的信息的不确定性减少的程度。
设训练数据集为$D$,$\left| D \right|$表示其样本容量,即样本个数。
设有$K$个类$C_{k}, k=1,2,\cdots,K$,$\left| C_{k} \right|$为属于类$C_{k}$的样本的个数,$\sum_{k=1}^{K} \left| C_{k} \right| = \left| D \right|$。
设特征$A$有$n$个不同的特征取值$\left\{ a_{1},a_{2},\cdots,a_{n}\right\}$,根据特征$A$的取值将$D$划分为$n$个子集$D_{1},D_{2},\cdots,D_{n}$,$\left| D_{i} \right|$为$D_{i}$的样本数,$\sum_{i=1}^{n}\left| D_{i} \right| = \left| D \right|$。
记子集$D_{i}$中属于类$C_{k}$的样本的集合为$D_{ik}$,即$D_{ik} = D_{i} \cap C_{k}$,$\left| D_{ik} \right|$为$D_{ik}$的样本个数。
信息增益算法:
输入:训练数据集$D$和特征$A$
输出:特征$A$对训练数据集$D$的信息增益$g \left( D, A \right) $
特征$A$对训练集$D$的信息增益比
\begin{align*} \\ & g_{R} \left( D, A \right) = \dfrac{g \left( D, A \right)}{H_{A} \left(D\right)}\end{align*}
即,信息增益$g\left( D, A \right)$与训练数据集$D$关于特征$A$的经验熵$H_{A}\left(D\right)$之比。
其中,
\begin{align*} \\ & H_{A} \left( D \right) = -\sum_{i=1}^{n} \dfrac{\left|D_{i}\right|}{\left|D\right|}\log_{2}\dfrac{\left|D_{i}\right|}{\left|D\right|}\end{align*}
ID3算法:
输入:训练数据集$D$,特征$A$,阈值$\varepsilon$
输出:决策树$T$
4. 如果$A_{g}$的信息增益小于阈值$\varepsilon$,则置$T$为单结点树,并将$D$中实例数量最大的类$C_{k}$作为该结点的类标记,返回$T$; 5. 否则,对$A_{g}$的每一个可能值$a_{i}$,依$A_{g}=a_{i}$将$D$分割为若干非空子集$D_{i}$,将$D_{i}$中实例数对大的类作为标记,构建子结点,由结点及其子结点构成树$T$,返回$T$; 6. 对第$i$个子结点,以$D_{i}$为训练集,以$A-\left\{A_{g}\right\}$为特征集,递归地调用步1.~步5.,得到子树$T_{i}$,返回$T_{i}$。
C4.5算法:
输入:训练数据集$D$,特征$A$,阈值$\varepsilon$
输出:决策树$T$
4. 如果$A_{g}$的信息增益小于阈值$\varepsilon$,则置$T$为单结点树,并将$D$中实例数量最大的类$C_{k}$作为该结点的类标记,返回$T$; 5. 否则,对$A_{g}$的每一个可能值$a_{i}$,依$A_{g}=a_{i}$将$D$分割为若干非空子集$D_{i}$,将$D_{i}$中实例数对大的类作为标记,构建子结点,由结点及其子结点构成树$T$,返回$T$; 6. 对第$i$个子结点,以$D_{i}$为训练集,以$A-\left\{A_{g}\right\}$为特征集,递归地调用步1.~步5.,得到子树$T_{i}$,返回$T_{i}$。
决策树的剪枝通过极小化决策树整体的损失函数或代价函数来实现。
设树$T$的叶结点个数为$\left| T \right|$,$t$是树$T$的叶结点,该叶结点有$N_{t}$个样本点,其中$k$类的样本点有$N_{tk}$个,$k=1,2,\cdots,K$,$H_{t}\left(T\right)$为叶结点$t$上的经验熵,
则决策树的损失函数
\begin{align*} \\ & C_{\alpha} \left( T \right) = \sum_{t=1}^{\left| T \right|} N_{t} H_{t} \left( T \right) + \alpha \left| T \right| \end{align*}
其中,$\alpha \geq 0$为参数,经验熵
\begin{align*} \\ & H_{t} \left( T \right) = - \sum_{k} \dfrac{N_{tk}}{N_{t}} \log \dfrac{N_{tk}}{N_{t}} \end{align*}
损失函数中,记
\begin{align*} \\ & C \left( T \right) = \sum_{t=1}^{\left| T \right|} N_{t} H_{t} \left( T \right) = - \sum_{t=1}^{\left| T \right|} \sum_{k=1}^{K} N_{tk} \log \dfrac{N_{tk}}{N_{t}} \end{align*}
则
\begin{align*} \\ & C_{\alpha} \left( T \right) = C \left( T \right) + \alpha \left| T \right| \end{align*}
其中,$C \left( T \right)$表示模型对训练数据的预测误差,即模型与训练数据的拟合程度,$\left| T \right|$表示模型复杂度,参数$\alpha \geq 0$控制两者之间的影响。
树的剪枝算法:
输入:决策树$T$,参数$\alpha$
输出:修剪后的子树$T_{\alpha}$
设一组叶结点回缩到其父结点之前与之后的整体树分别为$T_{B}$与$T_{A}$,其对应的损失函数值分别是$C_{\alpha} \left( T_{B} \right)$与$C_{\alpha} \left( T_{A} \right)$,如果 \begin{align*} \\ & C_{\alpha} \left( T_{A} \right) \leq C_{\alpha} \left( T_{B} \right) \end{align*} 则进行剪枝,即将父结点变为新的叶结点。 3. 返回2.,直到不能继续为止,得到损失函数最小的子树$T_{\alpha}$
假设$X$与$Y$分别为输入和输出变量,并且$Y$是连续变量,给定训练数据集
\begin{align*} \\ & D = \left\{ \left(x_{1},y_{1}\right), \left(x_{2},y_{2}\right),\cdots,\left(x_{N},y_{N}\right) \right\} \end{align*}
可选择第$j$个变量$x_{j}$及其取值$s$作为切分变量和切分点,并定义两个区域
\begin{align*} \\ & R_{1} \left( j,s \right) = \left\{ x | x_{j} \leq s \right\}, \quad R_{2} \left( j,s \right) = \left\{ x | x_{j} > s \right\} \end{align*}
最优切分变量$x_{j}$及最优切分点$s$
\begin{align*} \\ & j,s = \arg \min_{j,s} \left[ \min_{c_{1}} \sum_{x_{i} \in R_{1} \left(j,s\right)} \left( y_{i} - c_{1} \right)^{2} + \min_{c_{2}} \sum_{x_{i} \in R_{2} \left(j,s\right)} \left( y_{i} - c_{2} \right)^{2}\right] \end{align*}
其中,$c_{m}$是区域$R_{m}$上的回归决策树输出,是区域$R_{m}$上所有输入实例$x_{i}$对应的输出$y_{i}$的均值
\begin{align*} \\ & c_{m} = ave \left( y_{i} | x_{i} \in R_{m} \right), \quad m=1,2 \end{align*}
对每个区域$R_{1}$和$R_{2}$重复上述过程,将输入空间划分为$M$个区域$R_{1},R_{2},\cdots,R_{M}$,在每个区域上的输出为$c_{m},m=1,2,\cdots,M$,最小二乘回归树
\begin{align*} \\ & f \left( x \right) = \sum_{m=1}^{M} c_{m} I \left( x \in R_{m} \right) \end{align*}
最小二乘回归树生成算法:
输入:训练数据集$D$
输出:回归树$f \left( x \right)$
2. 用最优切分变量$x_{j}$与切分点$s$划分区域并决定相应的输出值 \begin{align*} \\ & R_{1} \left( j,s \right) = \left\{ x | x_{j} \leq s \right\}, \quad R_{2} \left( j,s \right) = \left\{ x | x_{j} > s \right\} \\ & c_{m} = \dfrac{1}{N} \sum_{x_{i} \in R_{m} \left( j,s \right)} y_{i}, \quad m=1,2\end{align*} 3. 继续对两个子区域调用步骤1.和2.,直到满足停止条件 4. 将输入空间划分为$M$个区域$R_{1},R_{2},\cdots,R_{M}$,生成决策树 \begin{align*} \\ & f \left( x \right) = \sum_{m=1}^{M} c_{m} I \left( x \in R_{m} \right) \end{align*}
分类问题中,假设有$K$个类,样本点属于第$k$类的概率为$p_{k}$,则概率分布的基尼指数 \begin{align*} \\ & Gini \left( p \right) = \sum_{k=1}^{K} p_{k} \left( 1 - p_{k} \right) = 1 - \sum_{k=1}^{K} \end{align*}
对于二分类问题,若样本点属于第1类的概率为$p$,则概率分布的基尼指数 \begin{align*} \\ & Gini \left( p \right) = \sum_{k=1}^{2} p_{k} \left( 1 - p_{k} \right) = 2p\left(1-p\right) \end{align*}
对于给定样本集和$D$,其基尼指数
\begin{align*} \\ & Gini \left( D \right) = 1 - \sum_{k=1}^{K} \left( \dfrac{\left| C_{k} \right|}{\left| D \right|} \right)^{2}\end{align*}
其中,$C_{k}$是$D$中属于第$k$类的样本自己,$K$是类别个数。
如果样本集合$D$根据特征$A$是否取某一可能值$a$被分割成$D_{1}$和$D_{2}$两个部分,即 \begin{align*} \\ & D_{1} = \left\{ \left(x,y\right) | A\left(x\right)=a \right\}, \quad D_{2} = D - D_{1} \end{align*} 则在特征$A$的条件下,集合$D$的基尼指数 \begin{align*} \\ & Gini \left( D, A \right) = \dfrac{\left| D_{1} \right|}{\left| D \right|} Gini \left( D_{1} \right) + \dfrac{\left| D_{2} \right|}{\left| D \right|} Gini \left( D_{2} \right)\end{align*}
基尼指数$Gini \left( D \right)$表示集合$D$的不确定性,基尼指数$Gini \left( D,A \right)$表示经$A=a$分割后集合$D$的不确定性。基尼指数值越大,样本集合的不确定性也越大。
CART生成算法:
输入:训练数据集$D$,特征$A$,阈值$\varepsilon$
输出:CART决策树$T$
对整体树$T_{0}$任意内部结点$t$,以$t$为单结点树的损失函数 \begin{align*} \\ & C_{\alpha} \left( t \right) = C \left( t \right) + \alpha \end{align*} 以$t$为根结点的子树$T_{t}$的损失函数 \begin{align*} \\ & C_{\alpha} \left( T_{t} \right) = C \left( T_{t} \right) + \alpha \left| T_{t} \right| \end{align*} 当$\alpha = 0$及$\alpha$充分小时,有不等式 \begin{align*} \\ & C_{\alpha} \left( T_{t} \right) < C_{\alpha} \left( t \right) \end{align*} 当$\alpha$增大时,在某一$\alpha$有 \begin{align*} \\ & \quad\quad C_{\alpha} \left( T_{t} \right) = C_{\alpha} \left( t \right) \\ & C \left( T_{t} \right) + \alpha \left| T_{t} \right| = C \left( t \right) + \alpha \\ & \quad\quad \alpha = \dfrac{C\left( t \right) - C \left(T_{t}\right)} { \left| T_{t} \right| -1 }\end{align*} 即$T_{t}$与$t$有相同的损失函数值,而$t$的结点少,因此对$T_{t}$进行剪枝。
CART剪枝算法:
输入:CART决策树$T_{0}$
输出:最优决策树$T_{\alpha}$
其中,$T_{t}$表示以$t$为根结点的子树,$ C\left(T_{t}\right)$是对训练数据的预测误差,$\left| T_{t} \right|$是$T_{t}$的叶结点个数。 4. 自下而上地访问内部结点$t$,如果有$g\left(t\right)=\alpha$,则进行剪枝,并对叶结点$t$以多数表决法决定其类别,得到树$T$ 5. 设$k=k+1, \alpha_{k}=\alpha, T_{k}=T$ 6. 如果$T$不是由根结点单独构成的树,则回到步骤4. 7. 采用交叉验证法在子树序列$T_{0},T_{1},\cdots,T_{n}$中选取最优子树$T_{\alpha}$