决策树DecisionTree
决策树是基于树结构来进行决策的,以二分类任务为例,我们希望从给定训练数据集学得一个模型用以对新示例进行分类,这个把样本分类的任务,可看作对“当前样本属于正类吗?”这个问题的“决策”或“判定”过程.
这恰是人类在面临决策问题时一种很自然的处理机制，著名的例子如下：
学习决策过程中提出的每个判定问题都是对某个属性的“测试”决策过程的最终结论对应了我们所希望的判定结果
每个测试的结果或是导出最终结论，或者导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围之内
从根结点到每个叶结点的路径对应了一个判定测试序列
决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。
决策树是从有类标号的训练元组中学习决策树,适合探测式的知识发现，高维数据;
-
自上而下地分治构造，直到构造到叶子结点，叶子结点的测试条件如下：
-
当前结点包含的样本全部属于同一类别；
-
当前属性集为空，或所有样本在所有属性上取值相同；
-
当前结点包含的样本集合为空
-
-
分类的启发式方法
- 度量：信息增益/Gini系数/信息增益率
- ID3算法
- 选择最高信息增益的属性作为最具分类能力的属性
- 当前样本所需信息熵为
- 利用属性A来将D分为v个部分
- 使用A分支的信息增益
- C4.5算法
- 克服划分子集自由一个类的问题，使用规范化信息增益
- 划分带来的信息（固有值）
- 规范化信息增益率
- Cart算法
-
Gini指数反映数据量数据分区或训练元组D的不纯度
-
代表元组属于类的概率
-
对于D的基于指标A的二元分裂，
-
选择使得不纯度降低的最大化的二元划分
-
-
算法：
-
如何解决Overfit过拟合？
训练样本只是真实模型下的一个抽样集，导致模型泛化能力不强；
- 增加样本集
- 降低模型复杂度
- Train-Validation—Test
- 模型选择：正则项等
- 设定决策树的最大高度来限制树的生长
- 先剪枝：提前终止树的构造
- 节点分裂的度量低于阈值，划分停止
- 后剪枝：从完全生长的树剪去树枝
- 代价比较大
- 增加样本集
-
决策树归纳：提取分类规则
- 可以提取决策树表示的知识，并以IF-THEN形式的分类规则表示
- 对从根到树叶的每条路径创建一个规则
- 沿着给定路径上的每个属性-值对形成规则前件（"IF"部分）的一个合取项
- 叶节点包含类预测，形成规则后件（"THEN"部分）
- IF-THEN规则易于理解，尤其树很大时
- 评估：
- 覆盖率：
- 准确率：
- 解决多个规则触发的冲突：
- 规模序：按照苛刻性度量
- 规则序：根据类的重要性度量
在sklrean中默认的划分方式就是gini指数，默认的决策树是CART树；但是gini指数的划分趋向于孤立数据集中数量多的类，将它们分到一个树叶中，而熵偏向于构建一颗平衡的树，也就是数量多的类可能分散到不同的叶子中去了。
