决策树是一种基本的分类与回归方法。
优点:计算复杂度不高，输出结果易于理解，对中间值缺失不敏感，可以处理不相关特征数据。
缺点：肯能会产生过度匹配问题。
适用数据类型：数值型和标称型。
信息熵
问题：
每个节点在哪个维度做划分？
某个维度在哪个值上做划分？
熵在信息论中代表
随机变量不确定度的度量。
一组数据，越不确定，越随机，相应的，信息熵就越大。
熵越大，数据的不确定性越高。
熵越小，数据的不确定性越低。
香农提出的信息熵公式：
举例：
写成如下形式：
划分之后使信息熵降低。
ID3算法
ID3算法是决策树的一种，它是基于奥卡姆剃刀原理的，即用尽量用较少的东西做更多的事。
从信息论知识中我们直到，期望信息越小，信息增益越大，从而纯度越高。所以ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。下面先定义几个要用到的概念。
信息熵前面已经介绍。
现在我们假设将训练元组D按属性A进行划分，则A对D划分的期望信息为：
而信息增益即为两者的差值：
ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂。下面我们继续用SNS社区中不真实账号检测的例子说明如何使用ID3算法构造决策树。
介绍一下这里面的专有名词：
- 日至密度、好友密度、是否使用真实的头像——条件属性。
- 账号是否为真实——决策属性。
- 其中s、m和l分别表示小、中和大。
设L、F、H和R表示日志密度、好友密度、是否使用真实头像和账号是否真实，下面计算各属性的信息增益。
因此日志密度的信息增益是0.276。
用同样方法得到H和F的信息增益分别为0.033和0.553。
因为F具有最大的信息增益，所以第一次分裂选择F为分裂属性，分裂后的结果如下图表示：
在上图的基础上，再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。
上面为了简便，将特征属性离散化了，其实日志密度和好友密度都是连续的属性。对于特征属性为连续值，可以如此使用ID3算法：
先将D中元素按照特征属性排序，则每两个相邻元素的中间点可以看做潜在分裂点，从第一个潜在分裂点开始，分裂D并计算两个集合的期望信息，具有最小期望信息的点称为这个属性的最佳分裂点，其信息期望作为此属性的信息期望。
ID3算法存在一些问题：
(1)信息增益的计算依赖于特征数目较多的特征，而属性取值最多的属性并不一定最优。
(2)ID3是非递增算法。
(3)ID3是单变量决策树(在分枝节点上只考虑单个属性)，许多复杂概念的表达困难，属性相互关系强调不够，容易导致决策树中子树的重复或有些属性在决策树的某一路径上被检验多次。
(4)抗噪性差，训练例子中正例和反例的比例较难控制。
由于ID3算法在实际应用中存在一些问题，于是Quilan提出了C4.5算法，严格上说C4.5只能是ID3的一个改进算法。
C4.5算法
ID3算法存在一个问题，就是偏向于多值属性，例如，如果存在唯一标识属性ID，则ID3会选择它作为分裂属性，这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率（gain ratio）的信息增益扩充，试图克服这个偏倚。
C4.5算法首先定义了“分裂信息”，其定义可以表示成：
其中各符号意义与ID3算法相同，然后，增益率被定义为：
C4.5选择具有最大增益率的属性作为分裂属性，其具体应用与ID3类似，不再赘述。
- 优点：
（1）通过信息增益率选择分裂属性，克服了ID3算法中通过信息增益倾向于选择拥有多个属性值的属性作为分裂属性的不足；
（2）能够处理离散型和连续型的属性类型，即将连续型的属性进行离散化处理；
（3）构造决策树之后进行剪枝操作；
（4）能够处理具有缺失属性值的训练数据。 - 缺点：
（1）算法的计算效率较低，特别是针对含有连续属性值的训练样本时表现的尤为突出。
（2）算法在选择分裂属性时没有考虑到条件属性间的相关性。
CART算法
CART和C4.5的主要区别：
- CART决策树的生成就是递归地构建二叉决策树的过程。
- CART决策树既可以用于分类也可以用于回归。
- 当CART是分类树时，采用GINI值作为节点分裂的依据；当CART是回归树时，采用样本的最小方差作为节点分裂的依据
- C4.5采用信息增益率来作为分支特征的选择标准，而CART则采用基尼（Gini）系数；
- C4.5不一定是二叉树，但CART一定是二叉树。
基尼系数的公式为：
基尼系数越高，随机性越强。
基尼系数越低，数据确定性越强。