首页理论教育C4.5分类算法在医药领域的应用

C4.5分类算法在医药领域的应用

2023-11-08 理论教育版权反馈

【摘要】：在C4.5算法中采用概率的方法，为缺失值的每个可能值赋予一个概率，而不是简单地用最常见的值替代该缺失值。C4.5决策树的生长阶段算法伪代码：C4.5决策树的剪枝处理阶段算法伪代码：5.C4.5算法的优缺点与其他分类算法相比，C4.5分类算法具有如下优点：产生的分类规则易于理解，准确率较高。为适应大规模数据集，在C4.5后出现有SLIQ和SPRINT等算法。

1.C4.5算法概念描述

基于ID3算法中存在的不足，Quinlan于1993年对其做出改进，提出了改进的决策树分类算法C4.5，该算法继承了ID3算法的优点，并在以下几个方面对ID3算法进行了改进：（1）能够处理连续型属性数据和离散型属性数据；（2）能够处理具有缺失值的数据；（3）使用信息增益率作为决策树的属性选择标准；（4）对生成的树进行剪枝处理，以获取简略的决策树；（5）从决策树到规则的自动产生。

C4.5算法概念描述：假定S为训练集，目标属性C具有m个可能的取值，C=｛C1，C2，…，Cm｝，即训练集S的目标属性具有m个类标号值C1，C2，…，Cm，C4.5算法所涉及的概念描述如下：

（1）假定训练集S中，Ci在所有样本中出现的频率为pi（i=1，2，3，…，m），则该集合S所包含的信息熵为：

pagenumber_ebook=106,pagenumber_book=95

（2）设用属性A来划分S中的样本，计算属性A对集合S的划分熵值EntropyA（S）定义如下：

若属性A为离散型数据，并具有k个不同的取值，则属性A依据这k个不同取值将S划分为k个子集｛S1，S2，…，Sk｝，属性A划分S的信息熵为：

pagenumber_ebook=106,pagenumber_book=95

其中|Si|和|S|分别是Si和S中包含的样本个数。

如果属性A为连续型数据，则按属性A的取值递增排序，将每对相邻值的中点看作可能的分裂点，对每个可能的分裂点，计算：

pagenumber_ebook=106,pagenumber_book=95

其中SL和SR分别对应于该分裂点划分的左右两部分子集，选择EntropyA（S）值最小的分裂点作为属性A的最佳分裂点，并以该最佳分裂点按属性A对集合S的划分熵值作为属性A划分S的熵值。

（3）C4.5以信息增益率作为选择标准，不仅考虑信息增益的大小程度，还兼顾为获得信息增益所付出的“代价”：

C4.5通过引入属性的分裂信息来调节信息增益，分裂信息定义：

pagenumber_ebook=106,pagenumber_book=95

信息增益率定义：

pagenumber_ebook=106,pagenumber_book=95

这样如果某个属性有较多的分类取值，则它的信息熵会偏大，但信息增益率由于考虑了分裂信息而降低，进而消除了属性取值数目所带来的影响。

2.C4.5算法演示

以Weather数据集为例，演示C4.5算法对该数据集进行训练，建立一棵决策树的过程，对未知样本进行预测。

（1）数据集的构成

Step1：计算所有属性划分数据集S所得的信息增益分别为（参考ID3例题演示）

Gain（S，outlook）=0.246；

Gain（S，temperature）=0.029；

Gain（S，humidity）=0.152；

Gain（S，wind）=0.049。(www.chuimin.cn)

Step2：计算各个属性的分裂信息和信息增益率。

以outlook属性为例，取值为overcast的样本有4条，取值为rain的样本有5条，取值为sunny的样本有5条：

pagenumber_ebook=107,pagenumber_book=96

同理，依次计算其他属性的信息增益率分别如下：

pagenumber_ebook=107,pagenumber_book=96

Step3：取值信息增益率最大的那个属性作为分裂结点，因此最初选择outlook属性作为决策树的根结点，产生3个分支，如图3-4所示。

Step4：对根结点的不同取值的分支，递归调用以上方法，求子树，最后通过C4.5获得的决策树如图2-5所示

pagenumber_ebook=108,pagenumber_book=97

图3-4　C4.5算法的决策树示例A

pagenumber_ebook=108,pagenumber_book=97

图3-5　C4.5算法的决策树示例B

3.C4.5对缺失数据的处理

由于决策树中节点的测试输出取决于单个属性的不同取值，当训练集或测试集中的某个样本数据的测试属性值未知，就无法得到当前节点的测试输出，因此ID3算法不允许训练集和测试集中存在缺失数据。对数据缺失值的处理，通常有两种方法：

方法一：抛弃数据集中具有缺失值的数据。在数据集中只有少量缺失值数据的情况下，可以抛弃具有缺失值的数据，但是当数据集中存在大量缺失值时不能采用这种方法。

方法二：以某种方式填充缺失的数据。如以该属性中最常见值或平均值替代该缺失值，或者以与缺失值样本所对应的类标号属性值相同的样本中该缺失值属性的最常见值或平均值来代替。

在C4.5算法中采用概率的方法，为缺失值的每个可能值赋予一个概率，而不是简单地用最常见的值替代该缺失值。

4.C4.5算法伪代码

C4.5决策树的建立可以分为两个过程：首先使用训练集数据，依据C4.5树生长算法构建一棵完全生长的决策树；然后对树进行剪枝，最后得到一棵最优决策树。

C4.5决策树的生长阶段算法伪代码：

pagenumber_ebook=109,pagenumber_book=98

C4.5决策树的剪枝处理阶段算法伪代码：

pagenumber_ebook=109,pagenumber_book=98

pagenumber_ebook=110,pagenumber_book=99

5.C4.5算法的优缺点

与其他分类算法相比，C4.5分类算法具有如下优点：产生的分类规则易于理解，准确率较高。其缺点：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。为适应大规模数据集，在C4.5后出现有SLIQ和SPRINT等算法。