机器学习决策树

决策树

决策树是一种监督学习分类算法

预测方式：

根据输入的样本X的特征属性和决策树的取值，将输入的X样本分配到某一个叶子节点中。
将叶子节点中出现最多的Y值，作为输入的X样本的预测类别。（分支）
目的：

最优的模型应该是：叶子节点中只包含一个类别的数据。用到了“贪心”

决策树构建步骤
例子

步骤一：将所有的特征看成一个一个的节点（分类标志）
eg（拥有房产、婚姻状态、年收入这些特征，我们可以看成一个一个的节点。）

步骤二：遍历当前特征的每一种分割方式，找到最好的分割点eg（婚姻状态这个特征，我们可以按照单身、已婚、离婚进行划分；也可以按照结过婚、没有结过婚进行划分，对于拥有房产，只能分成两种）；将数据划分为不同的子节点，eg： N1、 N2….Nm；计算划分之后所有子节点的“纯度”信息

步骤三：使用第二步遍历所有特征，选择出最优的特征，以及该特征的最优的划分方式，得出最终的子节点N1、 N2….Nm

步骤四：对子节点N1、N2….Nm分别继续执行2-3步，直到每个最终的子节点都足够“纯”。

例子

常见算法

常用的决策树算法有ID3，C4.5和CART。

ID3：以信息增益为准则来选择划分属性。
C4.5：使用信息增益率来进行属性的选择。
CART：使用基尼系数来选择划分属性。

1.ID3

Gain：决策树的信息增益
H（D）：分割前的纯度。
H（D｜A）：在给定条件A下的纯度，两者之差为信息增益度。如果信息增益度越大，则H（D｜A）越小，则代表结果集的数据越纯。
P（i）：每一个所对应的概率

信息熵”是度量样本集合不确定度（纯度）的最常用的指标。

在我们的ID3算法中，我们采取信息增益这个量来作为纯度的度量。我们选取使得信息增益最大的特征进行分裂

优点：决策树构建速度快；实现简单

缺点：

计算依赖于特征数目较多的特征，而属性值最多的属性并不一定最优 。
ID3算法不是递增算法，ID3算法是单变量决策树，对于特征属性之间的关系不会考虑。
抗噪性差。
只适合小规模数据集，需要将数据放到内存中。
C4.5是ID3的优化

2.C4.5：

在ID3算法的基础上，进行算法优化提出的一种算法(C4.5)，使用信息增益率来取代ID3中的信息增益。

Gain_ratio：信息增益率
IV（a）:属性a的固有值
Gain: 信息增益

不再使用ID3算法的信息增益，而是使用了信息增益率这个概念。
我们可以看出，信息增益率=信息增益/IV(a),说明信息增益率是信息增益除了一个属性a的固有值得来的。
由上面的计算例子，可以看出IV(a)其实能够反映出，当选取该属性，分成的V类别数越大，IV(a)就越大，如果仅仅只用信息增益来选择属性的话，那么我们偏向于选择分成子节点类别大的那个特征。

但是在前面分析了，并不是很好，所以我们需要除以一个属性的固定值，这个值要求随着分成的类别数越大而越小。于是让它做了分母。这样可以避免信息增益的缺点