决策树python实现

2019-04-14 本文已影响0人 simple的课

参考书籍：机器学习--周志华 / 数据挖掘导论 / 统计学习方法

博主还非常nice地给我发了数据集，感谢！

1. 概念

决策树是基于树结构来进行决策的。根结点包含样本全集，叶结点对应于决策结果。其他的每个结点对应于一个属性测试，每个结点包含的样本集合根据属性测试的结果被划分到子节点中。

属性：{色泽，根蒂，敲声，纹理，脐部，触感}

属性值： eg：色泽={青绿，乌黑，浅白}

2. 最优划分属性选择算法

信息熵（information entropy）：D的信息熵： $Ent(D) = - \sum_{k=1}^n p_{k} \log_2 p_{k}$

$p_{k}$ 为当前样本集合D中第 $k$ 类样本所占的比例。

$Ent(D)$ 的值越小，则D的纯度越高。

ID3算法：以信息增益(information gain)为准则来选择划分属性。

属性a对样本集D进行划分所获得的信息增益： $Gain(D, a) = Ent(D) - \sum_{v=1}^V\frac{\vert D^v \vert }{D} Ent(D^v)$

$D^v$ 表示D中所有在属性a上取值为 $a^v$ 的样本。

信息增益越大，使用属性a来进行划分所获得的纯度提升越大。选取信息增益最大的属性作为划分属性。

C4.5算法：以增益率则来选择最优划分属性（先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的）

增益率： $Gainratio(D, a) = \frac{Gain(D, a)}{IV(a)}$

$IV(a) = -\sum_{v=1}^V\frac{\vert D^v \vert }{\vert D \vert }\log_2 \frac{|D^v| }{\vert D \vert }$

CART算法：以基尼指数(来选择划分属性。

基尼值： $Gain(D) = 1-\sum_{k=1}^np_{k}^2$

$Gini index =(D, a) = \sum_{v=1}^V\frac{|D^v| }{|D|} Gini(D^v)$

3. python实现

1. 需要用到的工具import

2. 主函数

3. 数据处理并导入

4. 建立决策树

5. 如果每条数据只包含分类结果，则选择分类结果count最大的输出，这是一种特殊情况

6. 利用信息增益最大的原则选择划分属性

7. step6中计算信息增益的时候需要用到的信息熵

8. 在step6中计算信息增益需要用到的函数。

完整代码：