数据挖掘实训 Week 6

理论学习

1. 决策树

1.1 概念

• 每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。
• 优点：决策过程直观，易理解，可解释性强。

1.2 构造

• 属性是离散值且不要求生成二叉决策树，此时用属性的每一个划分作为一个分支。
• 属性是离散值且要求生成二叉决策树，此时使用属性划分的一个子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支。
• 属性是连续值，此时确定一个值作为分裂点split_point，按照>split_point和<=split_point生成两个分支。

1.3 不纯度衡量

• 信息熵用来描述信源的不确定度。H=-\sum^{n}_{i=1}p_i\log{p_i}
• 基尼系数：I_G(f)=\sum^m_{i=1}f_i(1-f_i)=\sum^m_{i=1}(f_i-f_i^2)=\sum^m_{i=1}f_i-\sum^m_{i=1}f_i^2=1-\sum^m_{i=1}f_i^2

1.4 决策树参数

• criterion：选用基尼不纯度或是交叉熵作为信息增益
• splitter：选取最佳划分或最佳的随机划分
• max_depth：决策树的最大深度
• min_samples_split：划分一个节点的最少样本数
• min_samples_leaf：生成一个叶子节点的最少样本数
• max_features：从最多多少个特征中来进行划分
• max_leaf_nodes：生成最多多少个叶子节点
• min_impurity_decrease：减少最小的不纯度才能进行分裂

2. 随机森林

• 用随机的方式建立一个森林（多棵决策树）
• 每一颗决策树之间没有关联的
• 有一个样本输入时，让每一棵决策树分别进行判断，看看这个样本应该属于哪一类，再进行voting（众数）
• 行采样：有放回采用；输入样本为N个，采样样本也为N个
• 列采样：M个feature中，选择m个（m<<M）
• 独立生成决策树：不剪枝；之前的两个随机采样的过程保证了随机性，使得不会出现over-fitting
• 可以产生高准确度的分类器；鲁棒性高、避免过拟合；能够处理很高维度的数据，并且不用做特征选择；实现简单、训练速度快；容易并行

3. GBDT

• GBDT（Gradient Boosting Decision Tree）：是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的结论累加起来做最终结果。
• DT（Regression Decision Tree）：回归树总体流程类似于分类树，区别在于回归树的每一个节点都会得一个预测值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化平方误差。
• 提升树（Boosting Decision Tree）：迭代多棵回归树来共同决策。当采用平方误差损失函数时，每一棵回归树学习的是之前所有树的结论和残差，拟合得到一个当前的残差回归树。提升树即是整个迭代过程生成的回归树的累加。
• GB（Gradient Boosting）：梯度迭代。每一个建立模型是在之前建立的模型损失函数的梯度下降方向。
• GB中每个新的模型的建立是为了使得之前模型的残差往梯度方向减少；传统Boost中对正确、错误的样本进行加权。
• GBDT几乎可用于所有回归问题，亦可用于二分类问题，不适合做多分类问题；可用于排序问题；常用于数据挖掘竞赛（模型融合）；用于广告推荐。

4. XGBoost

• xgboost是GB算法的高效实现，xgboost中的基学习器除了可以是CART（gbtree）也可以是线性分类器（gblinear）
• 优化了寻找最佳分割点的方式，不再是穷举寻找
• 考虑了训练数据为稀疏时的情况
• 并行化，在寻找最佳分割点的时候实现
• xgboost在目标函数中显式的加上了正则化项，基学习器为CART时，正则化项与树的叶子节点的数量T和叶子节点的值有关。
• GB中使用Loss Function对f(x)的一阶导数计算出伪残差用于学习生成fm(x)，xgboost不仅使用到了一阶导数，还使用二阶导数。
• CART回归树中寻找最佳分割点的衡量标准是最小化均方差，xgboost寻找分割点的标准是最大化，lamda，gamma与正则化项相关。

实践

运行XGBoost

提交成绩为0.7339。