决策树(Decision Tree)
决策树学习，建立一颗树结构的模型。此模型由一系列逻辑决策构成。在此结构中决策点代表某个属性上的决策，分支表示决策选择项，树的叶子节点是一系列联合决策的结论。
决策树通过分而治之（Divide and conquer）方式-递归划分（recurisive partitioning）来建立。在这个建立过程中，我们从代表所有数据的根节点出发，选择通向目标分类的特性把样本拆分成不同的组,如此直至触及停止标准。有几类停止标准, 节点上的所有或几乎所有的样本都是属于同一类;没有特征能对样本进行继续分类了;树已经触及预定义的大小限制.
建立决策树面对的第一个挑战就是从哪个特征着手进行切分。如果我们切分出来的分段数据仅包含一类数据，那我们说这个“一致”（Pure）的。
我们用熵来度量一个集合的无序程度。度量无序程度还可以用基尼不纯度（Gini impurity）。这里我先学习了熵。
c
Entropy(S) = Σ -Pi log2(Pi)
i=1
熵计算公式中各个部分的意义如下。在一个分段S上有c个类层次。Pi是第i个类层次的占比。
有了一致性衡量的熵，我们就可以来解决如何拆分样本。这里就得说到信息增益（Information Gain）
InfoGain(F) = Entropy(S1) - Entropy(S2)
信息增益就是样本拆分前后的熵的差值。拆分后的熵的计算公式如下：
n
Entropy(S) = Σ wi Entropy(Pi)
i=1
这个就是拆分后各部分的熵Entropy(Pi)如这一部分在总样本中所占比的乘积的总和。
信息增益越高表明分拆越有效。
决策树算法：
a. C5.0
| 优点 | 缺点 |
适用于大多数情况的多用途分类器
| 模型偏向于具有大量层级的特征 |
| 高自动化学习过程,可以处理数据跟名词性特征以及确实数据 | 容易过拟合（overfit）与欠拟合（underfit）
|
| 只需用到重要特征 | 由于基于axis-parallel建模一些关系时会比较棘手 |
| 适用于训练样本相不少或是很大的情况 | 训练数据小的改变会很大地改变决策逻辑 |
| 生成相对小的树，对树的解释不需要大量的数学背景。 | 大的树难于理解，达成不直觉的决策。 |
| 性比其它复杂的模型，这个更有效 |
|
在C5.0里我们用熵（entropy）来衡量一致性。熵为0则表示样本是完全同质的。熵值越高则表示越无序。
当树膨胀到一定大小后会导致决策过于特殊化, 得出的模型过拟合。克服此现象的做法有pre-pruning跟post-pruning。 pre-pruning就是当决策点达到某个量时或者决策节点中只包含少量样本是就停止树的构建。pre-pruning无法预知会不会遗漏掉某些细微的但是有相当重要的模式。
pre-pruning之外的另一个方法就是post-pruning。当树构建的相当大后，我们用某些基于误码率的修剪标准来修建树。这个方式通常比pre-pruning更有效。
在post-pruning的过程有连个可能的处理，一个是子树提升（subtree raising）,还有一个是子树置换（subtree replacement）
C5.0很容易通过调整训练选项来在过拟合跟欠拟合间达成平衡。
C5.0比C4.5增加了自适应增强（adaptive boosting）.前一个分类器分错的样本会被用来训练下一个分类器。AdaBoost方法对于噪声数据和异常数据很敏感。但在一些问题中，AdaBoost方法相对于大多数其它学习算法而言，不会很容易出现过拟合现象。AdaBoost方法中使用的分类器可能很弱（比如出现很大错误率），但只要它的分类效果比随机好一点（比如两类问题分类错误率略小于0.5），就能够改善最终得到的模型。而错误率高于随机分类器的弱分类器也是有用的，因为在最终得到的多个分类器的线性组合中，可以给它们赋予负系数，同样也能提升分类效果。
除了自适应增强，C5.0还可以提供一个成本矩阵（cost matrix）来修正模型。
http://sjchen.im.nuu.edu.tw/MachineLearning/final/CLS_DT.pdf
分类规则（classification rule）
分类规则表示的是if-else形式的知识,规则由先导（antecedent）跟后继（consequence）构成一个假设。
One rule算法
RIPPER算法（Repeated Incremental Pruning to Produce Error Reduction）
发展
修剪
优化
从决策树到规则