决策树
1. 特征选择
1.1 熵和条件熵
设 是一个有限取值 (K种) 的随机变量，其概率分布为：
则随机变量的熵为：
熵用于衡量随机变量的不确定性，且只与随机变量的分布有关，与 的取值无关。因此可以记为：
此外，规定 .
条件熵：用于衡量已知某条件下，随机变量的不确定性，定义：
（有样本数据得出的熵称为经验熵）
1.2 信息增益（比）
信息增益：用于衡量某特征对得原随机变量的不确定性的减少程度。定义：
即为特征 带来的信息增益.
信息增益算法：
输入：训练数据 和特征
输出：特征 对训练数据 的信息增益
- 计算训练集 的经验熵
其中， 样本中，第 类的数量.
- 计算特征 对数据集 的经验条件熵
其中， 表示依据特征 划分 ( 为特征A取值的个数)，第 种类别的样本数量； .
- 计算信息增益：
信息增益比算法：
其中 ， 为 D 中特征A的种类数。
1.3 Gini指数
设随机变量 有 种取值，每种取值的概率为 , 则该概率分布的Gini指数为：
对于样本数据，给定训练集 ，设 表示样本中取值为 的集合，则样本的Gini指数为：
如果样本根据特征 取某一值 (称为切分点) 与否分为 和 两部分，则在特征 下，样本的Gini指数定义为：
Gini(D)表示集合 的不确定性，Gini(D|A=a) 则表示集合由特征 的切分点 划分后的不确定性。
2. 决策树的生成
2.1 ID3
基于信息增益递归地选择最优特征构造决策树
输入：训练集 D，特征集 A，阈值
输出：决策树 T
- 如果 D 中所有实例均属于同一类别 , 则所构建的决策树为 T 单节点树，且 即为该节点的类的标记。
- 如果 T 不是单节点树，则计算特征集合 A 中各特征对 D 的信息增益，选择信息增益最大的特征 .
- 如果 的信息增益小于阈值 , 则将 T 视为单节点树，并将 D 中所属数量最多的类 作为该节点的类的标记并返回 T。
- 否则，对于 的每一特征取值 , 按照 将 D 划分成若干非空子集 , 以 中所属数量最多的类作为标记并构建子节点，由节点和子节点构成树 T 并返回。
- 对于第 个子节点，以 为训练集，以 为特征集，递归地调用(1)~（4）步，即可得到决策子树 并返回。
2.2 C4.5
将ID3构建算法中的第二步更改为选取信息增益比最大的特征，其余步骤不变。
2.3 CART
CART 全称为分类与回归树 (classificiation and regression tree). 它既可以做分类，也可以做回归。
CART可以理解为在给定随机变量 X 的条件下输出随机变量 Y 的条件概率分布的学习算法。CART 生成的决策树都是二叉决策树，内部节点取值为“是”和“否”，这些节点划分方法等价于递归地二分每个特征，将特征空间划分成有限个单元，并在这些单元上确定预测的概率分布，即前述的预测条件概率分布。
输入：训练集 D，停止计算的条件
输出：CART 决策树
根据训练数据集，从根节点开始，递归地对每个节点进行以下操作，构建二叉决策树：
- 计算特征集中每个特征 a 及其所有取值 , 根据 将数据集划分为 和 两个部分，计算 利用 (*) 计算Gini指数。
- 取Gini指数最小的特征及其对应的划分点作为最优特征和最优划分点，据此将当前节点划分为两个子节点，将训练集根据特征分配到两个子节点中。
- 对两个子节点递归地调用 (1) 和 (2)，直至满足停止条件（如限制最大树深）。
- 生成CART决策树。
输入：训练集 D.
输出：回归树.
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。
- 选择最优切分变量 j 及其切分点 s，即求解：
遍历变量 j, 对固定的切分变量 j 扫描切分点 s, 选择使上式最小的.
- 用选定的划分区域并决定相应的输出值：
- 继续对两个子区域调用 (1), (2)，直至满足停止条件（如限制最大树深）。
- 将输入空间划分为 M 个区域：, 生成决策树：
由（**）可知，在进行区域划分时遵循平方误差最小准则。
3. 决策树的剪枝
决策树生成算法递归地产生决策树，生成的决策树大而全，很容易出现过拟合现象。剪枝通过简化决策树来降低过拟合。
一般分为预剪枝和后剪枝两种：
- 预剪枝：在决策树生成过程中提前停止树的增长。思路为在决策树节点分裂之前，计算当前节点划分能否提升模型泛化能力，如果不能，则决策树应该在改点停止生长。这种剪枝方法简单高效，但在一定程度上存在欠拟合的风险，导致决策树生长不够完全。
- 后剪枝：先完成决策树的生成，然后在通过极小化损失函数的方式进行剪枝。
- 设树 T 的叶节点数为 , t 是树 的叶节点，该节点有 个样本点，其中 类的样本点有 个 , 为叶节点 t 上的经验熵， 为参数。
- 损失函数为：
- 损失函数中 衡量了模型对训练数据的预测误差（越大则误差越大，拟合效果越不好）， 表示模型复杂度， 则是两者之间的 tradeoff。较大的 意味着倾向于选择较简单的模型，反之则倾向于选择较复杂的模型。
其中经验熵为：
剪枝算法：
输入：生成算法产生的整个树 T，参数
输出：修剪后的子树
- 计算每个节点的经验熵。
- 递归地从树的叶节点向上回缩。设一组叶节点回缩到其父节点之前与之后 T 分别为 , 对应的损失函数分别为 , 若：, 则进行剪枝，即父节点变为新的叶节点。
- 返回步骤2，直至不能继续位置，得到损失函数最小的子树
- (在得到的子树序列中，通过交叉验证选择最优的子树。)
后剪枝最好在验证集上进行，只有在数据量不够时选择在训练集上进行。
4. Sk-learn 接口
分类树
from sklearn.tree import DecisionTreeClassifier clf = DecisionTreeClassifier() clf.fit(X_train, y_train) y_pred = clf.predict(X_test) acc = accuracy_score(y_test, y_pred)
回归树
from sklearn.tree import DecisionTreeRegressor reg = DecisionTreeRegressor() reg.fit(X_train, y_train) y_pred = reg.predict(X_test) mse = mean_squard_error(y_test, y_pred)
随机森林
1. Boosting v.s. Bagging
- Boosting: 串行地训练一系列弱分类器，使得被先前弱分类器分类错误的样本在后续得到更多的关注(不断地迭代和残差拟合)，最后将这些分类器组合成最优强分类器。
- Bagging: 并行式集成学习框架，通过自助采样 (bootstrap sampling)，即：给定包含 m 个样本的数据集，有放回地随机抽取一个样本放入采样集中，经过 m 次采样，可得到一个和原始数据及一样大小的采样集。最终采样得到 T 个包含 m 个样本的采样集，然后基于每个采样集训练一个基分类器，最后将这些基分类器进行组合。
随机森林是 Bagging 学习框架的一个代表，通过样本和特征的两个随机性来构建基分类器，由多棵决策树形成随机森林。
输入：训练数据 D，特征集合 A
输出：随机森林
- 有放回地随机选择 个样本 。
- 在节点分裂时，随机从 A 中选取 n ( << |A|)个特征。
- 依据(1) (2)中产生的样本和特征集构建决策树。
- 重复(1)~(3)构建大量的决策树组成随机森林，然后将每棵树的结果进行综合（分类问题可用投票法，回归问题可用均值法。）
2. Sk-learn 接口
分类
from sklearn.ensemble import RandomForestClassifier clf = RandomForestClassifier(max_depth = 3, random_state = 0) clf.fit(X_train, y_train) y_pred = clf.predict(X_test) acc = accuracy_score(y_test, y_pred)
回归
from sklearn.tree import RandomForestRegressor reg = RandomForestRegressor() reg.fit(X_train, y_train) y_pred = reg.predict(X_test) mse = mean_squard_error(y_test, y_pred)
Loading Comments...