算法-基于ID3和C4.5的决策树算法

偏执的太偏执、 2022-05-14 01:55 154阅读 0赞

**目录**

摘要

构建过程

ID3算法

注意点：

C4.5

参考文献：

--------------------

# 摘要 #

决策树算法是相对比较清晰简单的有监督分类算法，所谓有监督就是需要给出标准的已知分类的样本数据集，根据数据集训练或者说构建出一个模型，然后根据模型对新的数据进行预测分类。**决策树是一种思想不是一种算法**，决策树最终生成的模型很好理解和想象，可以简单的理解成if..else即可。可以是二叉树，可以是不规则的二叉树或者多叉树。

根据样本构建决生成决策树的过程是重点，如何构建生成决策树呢？

# 构建过程 #

我们假设一个数据集D，如果通过一种方法，让这些样本生成一个自顶向下结构的树，树的每个非叶子节点对应一个属性，每个叶子节点对应一个类别，其实也是一个子集。可以想象理解为一个比较纯的分类子集。我们可以采用一定的标准和规则分割训练样本称为几个子集，然后再以相同的规则去分割每个子集，递归这个过程，直到每个子集只包含属于同一类样本时停止，即到叶子结点了停止。训练的过程中，每个分割结点需要保存好分类的属性。实现这个过程的算法有很多,参考[常见的决策树算法][Link 1]，包括有：CLS、ID3、C4.5、SLIQ、CART。我这里主要记录ID3算法和它的升级算法C4.5

# ID3算法 #

所有涉及ID3算法的博文都会提到一个概念“熵”，那么到底什么是熵？这是个啥玩意，我昨天看了一片阮大神写的一篇[《熵：宇宙的中级规则》][Link 2]，瞬间就理解的非常透彻。其实最简单的可以理解为**混乱无序的程度。**这也解释了前面说的叶子结点一般情况下最终是类型纯度最高的数据。我们在构建决策树的时候，首先要找的根节点，可以理解为第一个if的条件，数据集中每一个样本都有很多属性，那么我们选择哪一个属性作为第一个根节点呢？这就涉及到熵了，我们分类或者分割的原则肯定，被分到一类的元素相似度肯定是最高，或者说纯度最大，也就意味着熵最小。那么可以简单的理解为：通过求每一个属性的条件熵，看那个对应的熵最大，则以这个属性作为分割点开始。

设D为用类别对训练元祖进行划分的，划分为m个类，则D的熵表示为：

![gif.latex_info_28D_29_-_5Csum_20_5Em_7Bi_1_7Dp_ilog_2_28p_i_29][]

m：数据集D中总共有m类数据集

Pi：这一类数据数据集的概率，这一类数据的个数/总样本数

![70][]

infoA(D)表示为某一个属性的熵 。  
v:这个属性(取值)分支个数。

Dj:这个属性对应分支上样本的个数  
D:样本总个数

Info(Dj):这个分支的熵

![70 1][]

Gain(A):信息增益

即：针对一个一个特征而言，就看一个特征X,系统有它和没有它时候的信息量是多少，两者的差值就是这个特征给系统带来的信息增益。取信息增益最大的特征作为分裂点，后面递归这样操作。

# 注意点： #

(1).若所有特征属性已经用于分类后，仍然没有得到完全纯正的分类结果。可以使用多数表决，将叶节点中大部分数据所属类作为分类结果。

(2).为了防止过拟合，可以设定阈值。比如当某个节点的数据表中多数类的比例超过70%时停止分类。

# C4.5 #

ID3信息增益的计算依赖特征数目较多的特征，而属性值最多的属性并不一定最优，针对这种情况C4.5作为ID3算法的改进版，使用信息增益率来计算查找分割点。

![70 2][]

![70 3][]

# 参考文献： #

[https://blog.csdn.net/csdn595075652/article/details/48790903][https_blog.csdn.net_csdn595075652_article_details_48790903]

[https://blog.csdn.net/Gamer\_gyt/article/details/51242815][https_blog.csdn.net_Gamer_gyt_article_details_51242815]

[https://blog.csdn.net/gao1440156051/article/details/52373647][https_blog.csdn.net_gao1440156051_article_details_52373647]

[https://blog.csdn.net/jerry81333/article/details/53125197][https_blog.csdn.net_jerry81333_article_details_53125197]

[https://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html][https_www.cnblogs.com_leoo2sk_archive_2010_09_19_decision-tree.html]

[Link 1]: https://blog.csdn.net/fengbingchun/article/details/78880934
[Link 2]: http://www.ruanyifeng.com/blog/2017/04/entropy.html
[gif.latex_info_28D_29_-_5Csum_20_5Em_7Bi_1_7Dp_ilog_2_28p_i_29]: /images/20220514/d47215fffd9140f49a9fc1aad4d1da3c.png
[70]: /images/20220514/109acabb1d79420c8949192f8739d7e6.png
[70 1]: /images/20220514/d463f6ef68d445b0adad0f89ea266007.png
[70 2]: /images/20220514/b9f7a4de2db94074b46481d7feea692a.png
[70 3]: /images/20220514/269f9f0ad34d40c5b5e828c00a0a6229.png
[https_blog.csdn.net_csdn595075652_article_details_48790903]: https://blog.csdn.net/csdn595075652/article/details/48790903
[https_blog.csdn.net_Gamer_gyt_article_details_51242815]: https://blog.csdn.net/Gamer_gyt/article/details/51242815
[https_blog.csdn.net_gao1440156051_article_details_52373647]: https://blog.csdn.net/gao1440156051/article/details/52373647
[https_blog.csdn.net_jerry81333_article_details_53125197]: https://blog.csdn.net/jerry81333/article/details/53125197
[https_www.cnblogs.com_leoo2sk_archive_2010_09_19_decision-tree.html]: https://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html