特征的分类能力评估
定义
给定数据集 $D=\{(x_i,y_i)\}_{i=1}^N$, 其中 $x_i=\left(x_i^{(1)},x_i^{(2)},\cdots,x_i^{(m)}\right) \in \mathcal{X}$ 是第 $i$ 个样本的特征向量, $y_i \in \mathcal{Y}=\{c_1,c_2,\cdots,c_K\}$ 是第 $i$ 个样本的标签. 假设数据集 $D$ 根据特征分成了 $K$ 个子集 $D_1,D_2,\cdots,D_K$, 定义 经验熵 为
$$ H(D) = -\sum_{k=1}^K \frac{|D_k|}{|D|} \log_2 \frac{|D_k|}{|D|} $$现在给定某维特征 $A$ 和其取值集合 $\{a_1,a_2,\cdots,a_m\}$, 根据 $A$ 的取值将数据集 $D$ 分成了 $m$ 个子集 $D_1^A,D_2^A,\cdots,D_m^A$, 并进一步考虑 $D_i^A$ 中的标签分布, 定义 条件经验熵 为
$$ H(D|A) = \sum_{i=1}^m \frac{|D_i^A|}{|D|} H(D_i^A) $$如果条件经验熵和经验熵之差越大, 则说明特征 $A$ 对数据集 $D$ 的分类能力越强.
定义
属性 $A$ 对数据集 $D$ 的 信息增益 $g(D,A)$ 定义为
$$ g(D,A) = H(D) - H(D|A) $$考虑到信息增益的计算会偏向于选择取值较多的特征, 为了避免这种情况, 引入信息增益率来评估特征的分类能力.
定义
特征 $A$ 的 分裂信息 $IV(A)$ 定义为
$$ IV(A) = -\sum_{i=1}^m \frac{|D_i^A|}{|D|} \log_2 \frac{|D_i^A|}{|D|} $$特征 $A$ 的 信息增益率 $g_R(D,A)$ 定义为
$$ g_R(D,A) = \frac{g(D,A)}{IV(A)} $$分裂信息其实就是按照 $A$ 取值作划分的经验熵.
除了信息增益和信息增益率, 还有 Gini 指数可以用来评估特征的分类能力.
定义
数据集 $D$ 的 Gini 指数 $\text{Gini}(D)$ 定义为
$$ \text{Gini}(D) = 1 - \sum_{k=1}^K \left(\frac{|D_k|}{|D|}\right)^2 $$特征 $A$ 的 Gini 指数 $\text{Gini}(D,A)$ 定义为
$$ \text{Gini}(D,A) = \sum_{i=1}^m \frac{|D_i^A|}{|D|} \text{Gini}(D_i^A) $$如果按照特征 $A$ 是否取值为 $a_i$ 对数据集 $D$ 进行划分 $D=D_i^A \cup (D-D_i^A)$, 则 $A=a_i$ 的 Gini 指数 $\text{Gini}_d(D,A=a_i)$ 定义为
$$ \text{Gini}_d(D,A=a_i) = \frac{|D_i^A|}{|D|} \text{Gini}(D_i^A) + \frac{|D-D_i^A|}{|D|} \text{Gini}(D-D_i^A) $$Gini 指数可以看作任取两个样本, 它们的标签不一致的概率. 如果 Gini 指数越小, 则说明特征 $A$ 对数据集 $D$ 的分类能力越强.
决策树模型
算法生成决策树
输入: 训练数据集 $D=\{(x_i,y_i)\}_{i=1}^N$, 特征集 $\mathcal{A}=\{A_1,A_2,\cdots,A_m\}$, 最优特征选择函数 $F$.
输出: 决策树 $T$.
- 若数据集 $D$ 中所有样本的标签都是 $c_k$, 则生成一个类标记为 $c_k$ 的叶结点, 返回 $T$;
- 若 $A=\emptyset$, 且 $D$ 非空, 则生成一个单节点树, 并以 $D$ 中样本数最多的类标记作为该节点的类标记, 返回 $T$;
- 计算 $A^\ast=F(D,\mathcal{A})$;
- 对 $A^\ast$ 的每一个取值 $a_i$, 构造一个对应于 $D_i$ 的子节点;
- 若 $D_i=\emptyset$, 则将子节点标记为叶结点, 类标记为 $D$ 中样本数最多的类标记;
- 否则, 将 $D_i$ 中样本数最多的类标记作为该节点的类标记
- 对每个 $D_i$ 对应的非叶子节点, 以 $D_i$ 为训练集, 以 $\mathcal{A}-\{A^\ast\}$ 为特征集, 递归调用 1-6 步, 构建决策树 $T$.
如果以信息增益为特征选择函数, 即 $A^\ast = \arg\max_{A \in \mathcal{A}} g(D,A)$, 则算法对应于 ID3 算法; 如果以信息增益率为特征选择函数, 即 $A^\ast = \arg\max_{A \in \mathcal{A}} g_R(D,A)$, 则算法对应于 C4.5 算法.
二路划分会采用以特征的可能取值为切分点的二分法划分当前数据集, 例如与选择 Gini 指数最小的特征和切分点对应的特征值, 即 $(A^\ast,a^\ast) = \arg\min_{A \in \mathcal{A},a \in V(A)} \text{Gini}_d(D,A=a)$, 则算法对应于 CART 算法.
为了降低过拟合风险, 可以对决策树进行剪枝. 常用的是后剪枝, 即先生成一棵完全生长的决策树, 然后根据泛化性能决定是否剪枝. 也可以采用正则化方法, 例如, 定义决策树 $T$ 的损失或代价函数:
$$ C_\alpha(T) = C(T) + \alpha |T| $$其中 $C(T)$ 用于衡量 $T$ 对 $D$ 的拟合程度, $|T|$ 表示 $T$ 的叶结点个数, $\alpha \geq 0$ 用于权衡拟合程度和模型复杂度.
CART 算法有特别的剪枝处理: 从 CART 算法生成得到完整决策树 $T_0$ 开始, 产生一个递增的权衡系数序列 $0=\alpha_0 < \alpha_1 < \cdots < \alpha_n < +\infty$ 和一个嵌套的子树序列 $\{T_0, T_1, \cdots, T_n\}$, $T_i$ 为 $\alpha \in [\alpha_i, \alpha_{i+1})$ 时的最优子树, $T_n$ 是根节点单独构成的树.
如果是连续特征, 则可以考虑将其离散化, 例如, 通过二分法将其划分为两个区间, 选择最优划分点.
现在继续从经验风险的角度来看决策树模型.采用 $0-1$ 损失函数, 设节点 $t$ 设置的标记是 $c_k$, 则在 $t$ 对应的数据集上的经验风险为
$$ \frac{1}{|D_t|} \sum_{i=1}^{|D_t|} I(y_i \neq c_k) $$显见, 等价于
$$ \max_{c_k \in \mathcal{Y}} \frac{1}{|D_t|} \sum_{i=1}^{|D_t|} I(y_i = c_k) $$从现在来看, 决策树构造过程中划分的单元都是矩形的, 即分类边界是若干与特征坐标轴平行的边界组成. 多变量决策树模型允许用若干特征的线性组合来划分数据集, 对每个非叶结点学习一个线性分类器.
最小二乘回归树模型
CART 算法用于回归问题时, 采用平方误差损失函数选择属性和切分点.
算法CART
输入: 训练数据集 $D=\{(x_i,y_i)\}_{i=1}^N$, 特征集 $\mathcal{A}=\{A_1,A_2,\cdots,A_m\}$.
输出: 回归树 $T$.
-
设回归树将输入空间划分为 $M$ 个单元 $R_1,R_2,\cdots,R_M$, 并在每个单元上有一个固定的输出值 $c_m$, 则回归树模型可以表示为
$$ f(x)=\sum_{m=1}^M c_m I(x \in R_m) $$ -
如果采用平方误差, 则 $R_m$ 的输出值 $c_m$ 应该是 $R_m$ 中所有样本输出值的均值, 即
$$ \hat{c}_m = \frac{1}{|R_m|} \sum_{x_i \in R_m} y_i $$ -
对于一个输入空间, 若选用第 $j$ 维特征变量作为切分变量, $s$ 作为切分点, 则可以将输入空间划分为两个区域
$$ R_1(j,s) = \{x|x^{(j)} \leq s\}, \quad R_2(j,s) = \{x|x^{(j)} > s\} $$则可以通过求解优化问题
$$ \min_{j,s} \left[\min_{c_1} \sum_{x_i \in R_1(j,s)} (y_i-c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j,s)} (y_i-c_2)^2\right] $$来确定最优切分变量 $j$ 和切分点 $s$. 实际上这里的 $c_i$ 就应该取 2 步中的 $\hat{c}_m$.
-
从初始输入空间开始, 按照误差最小原则递归划分, 重复如上过程, 直到满足停止条件.
对于剪枝, 和分类任务处理框架一致, 采用
$$ C_\alpha(T) = C(T) + \alpha |T| $$计算损失, 其中
$$C(T) = \sum_{t=1}^{|T|} N_tQ_t(T) = \sum_{t=1}^{|T|} \sum_{x_i \in R_t} (y_i-\hat{c}_t)^2$$$N_t$ 表示叶结点 $t$ 中的样本数, $Q_t(T)$ 表示叶结点 $t$ 的均方损失, $\hat{c}_t$ 表示叶结点 $t$ 的输出值均值.