机器学习-决策树()

决策树原理

决策树特点

• 树形结构流程图（漏斗型），模型本身包含一些列逻辑决策。数据分类从根节点开始，根据特征值遍历树上的各个决策节点。
• 几乎可应用于任何类型的数据建模，且性能不错。但当数据有大量多层次的名义特征或者大量的数值特征时，可能会生成一个过于复杂的决策树。
• 递归划分/分而治之：利用特征值将数据分解成具有相似类的较小的子集。
• 过程：从代表整个数据集的根节点开始，选择最能预测目标类的特征，然后将案例划分到该特征不同值的组中（即第一组树枝），继续分而治之其他节点，每次选择最佳的候选特征，直到节点上所有案例都属于同一类，或者没有其他的特征来区分案例，或者决策树已经达到了预先定义的大小。
• 由于数据可一直划分（直到组内的特征没有区别），所以决策树容易过拟合，给出过于具体细节的决策。

决策树难点

1. 选择最佳分割

确定根据哪个特征来进行分割。

可以根据熵Entropy(S)，来度量纯度。熵的取值0-1。0表示样本完全同质，1表示样本凌乱最大。

$$H(X) = -\sum_{i=1}^{n}P(x_i)\log_2 P(x_i)$$

用熵值计算每一个可能特征的分割引起的同质性（均匀性）变化，即分割前与分割后的数据分区熵值之差。

$$InfoGain(F) = Entropy(S_{1}) - Entropy(S_{2})$$

信息增益越高，根据某一特征分割后创建的分组越均衡。

同样的除了熵之外也可以用基尼系数，卡方统计量，增益比等指标计算特征分割指标

2. 修剪决策树

• 修建决策树减少它的大小，避免过拟合。
• 提前终止法/预剪枝决策树法：决策节点达到一定数量的案例就停止。
• 后剪枝决策树法（更有效）：根据节点处的错误率使用修剪准则将树减少到更合适的大小。