决策树算法及其改进

蔡星

摘 要：该文对传统的C4.5决策树数据挖掘算法进行了改进，提出了一种双重熵平均决策树算法。传统的C4.5决策树算法易出现无意义分枝，过度拟合等问题，针对该类问题，基于双重熵平均决策树算法，通过两次对样本子集熵平均值的计算、排序、合并处理，得到修正后的属性信息增益，并以此作为属性选择的依据，从而解决了传统C4.5决策树算法可解释性差、易产生碎片等问题。

关键词：C4.5决策树 算法 熵 平衡因子

中图分类号：TP311.13 文献标识码：A 文章编号：1674-098X（2014）04（c）-0040-02

数据联机分析功能是通过对数据的处理发现已知要素与分析度量值之间的关系，而数据挖掘则是从大量的数据中发现隐藏的规律。数据挖掘包括多种挖掘算法，为了研究毕业生不同属性与其就业状况之间的潜在知识和规律，该文采用决策树方法对高校毕业生数据进行分析，主要选用的是C4.5决策树算法。

1 C4.5算法思想

决策树的优点在于原理简单，发现知识较快；计算较为简单，运算速度较快，对于训练数据的处理和待决策数据的处理效率相对较高；适用于大量数据的综合处理，有利于挖掘数据中的重要属性；最终得到的挖掘结果是有意见的规则，有利于用户的理解。决策树的主要缺点包括：对数据的时间属性较为敏感，需要大量的预处理工作；对于非离散的连续性数据值处理效率和准确率不佳；易出现过度拟合的情况，产生大量的决策分支，导致决策规则过于庞大。

C4.5决策树算法是决策树算法的主流，它继承于传统的ID3算法，继承了其优势，改进了其缺点。但C4.5决策树算法依然存在着较多的问题，其中最为突出的是过度拟合情况，以及决策准确性方面的问题。针对上述问题，本课题提出了一种改进的C4.5决策树算法，在算法构建过程中，以树分枝的信息熵为研究对象，将熵值较高的部分和熵值较低的部分进行合并和平衡处理，从而达到减少决策树分支数量的目的；与此同时，考虑到C4.5算法在决策分支的确定过程中采用的是局部最优的方法，在准确性方面从整体上看有所欠缺，所以引入了了平衡因子控制算法的整体最优化性。

C4.5决策树算法设研究对象数据集为，该数据集中包括个类别，每一个类别表示为，选取该数据集中的一个属性数据，则可以被划分为多个子集，设有个取值，则被划分的子集可表示为。设为的例子总数，而为的例子数，为的例子总数，是的所有例子中所包括的的例子数，基于上述的设定，则可以得到如下定义：

（1）类别在出现的概率如式（1）所示：

（1）endprint

摘 要：该文对传统的C4.5决策树数据挖掘算法进行了改进，提出了一种双重熵平均决策树算法。传统的C4.5决策树算法易出现无意义分枝，过度拟合等问题，针对该类问题，基于双重熵平均决策树算法，通过两次对样本子集熵平均值的计算、排序、合并处理，得到修正后的属性信息增益，并以此作为属性选择的依据，从而解决了传统C4.5决策树算法可解释性差、易产生碎片等问题。

关键词：C4.5决策树 算法 熵 平衡因子

中图分类号：TP311.13 文献标识码：A 文章编号：1674-098X（2014）04（c）-0040-02

数据联机分析功能是通过对数据的处理发现已知要素与分析度量值之间的关系，而数据挖掘则是从大量的数据中发现隐藏的规律。数据挖掘包括多种挖掘算法，为了研究毕业生不同属性与其就业状况之间的潜在知识和规律，该文采用决策树方法对高校毕业生数据进行分析，主要选用的是C4.5决策树算法。

1 C4.5算法思想

决策树的优点在于原理简单，发现知识较快；计算较为简单，运算速度较快，对于训练数据的处理和待决策数据的处理效率相对较高；适用于大量数据的综合处理，有利于挖掘数据中的重要属性；最终得到的挖掘结果是有意见的规则，有利于用户的理解。决策树的主要缺点包括：对数据的时间属性较为敏感，需要大量的预处理工作；对于非离散的连续性数据值处理效率和准确率不佳；易出现过度拟合的情况，产生大量的决策分支，导致决策规则过于庞大。

C4.5决策树算法是决策树算法的主流，它继承于传统的ID3算法，继承了其优势，改进了其缺点。但C4.5决策树算法依然存在着较多的问题，其中最为突出的是过度拟合情况，以及决策准确性方面的问题。针对上述问题，本课题提出了一种改进的C4.5决策树算法，在算法构建过程中，以树分枝的信息熵为研究对象，将熵值较高的部分和熵值较低的部分进行合并和平衡处理，从而达到减少决策树分支数量的目的；与此同时，考虑到C4.5算法在决策分支的确定过程中采用的是局部最优的方法，在准确性方面从整体上看有所欠缺，所以引入了了平衡因子控制算法的整体最优化性。

C4.5决策树算法设研究对象数据集为，该数据集中包括个类别，每一个类别表示为，选取该数据集中的一个属性数据，则可以被划分为多个子集，设有个取值，则被划分的子集可表示为。设为的例子总数，而为的例子数，为的例子总数，是的所有例子中所包括的的例子数，基于上述的设定，则可以得到如下定义：

（1）类别在出现的概率如式（1）所示：

（1）endprint

摘 要：该文对传统的C4.5决策树数据挖掘算法进行了改进，提出了一种双重熵平均决策树算法。传统的C4.5决策树算法易出现无意义分枝，过度拟合等问题，针对该类问题，基于双重熵平均决策树算法，通过两次对样本子集熵平均值的计算、排序、合并处理，得到修正后的属性信息增益，并以此作为属性选择的依据，从而解决了传统C4.5决策树算法可解释性差、易产生碎片等问题。

关键词：C4.5决策树 算法 熵 平衡因子

中图分类号：TP311.13 文献标识码：A 文章编号：1674-098X（2014）04（c）-0040-02

数据联机分析功能是通过对数据的处理发现已知要素与分析度量值之间的关系，而数据挖掘则是从大量的数据中发现隐藏的规律。数据挖掘包括多种挖掘算法，为了研究毕业生不同属性与其就业状况之间的潜在知识和规律，该文采用决策树方法对高校毕业生数据进行分析，主要选用的是C4.5决策树算法。

1 C4.5算法思想

决策树的优点在于原理简单，发现知识较快；计算较为简单，运算速度较快，对于训练数据的处理和待决策数据的处理效率相对较高；适用于大量数据的综合处理，有利于挖掘数据中的重要属性；最终得到的挖掘结果是有意见的规则，有利于用户的理解。决策树的主要缺点包括：对数据的时间属性较为敏感，需要大量的预处理工作；对于非离散的连续性数据值处理效率和准确率不佳；易出现过度拟合的情况，产生大量的决策分支，导致决策规则过于庞大。

C4.5决策树算法是决策树算法的主流，它继承于传统的ID3算法，继承了其优势，改进了其缺点。但C4.5决策树算法依然存在着较多的问题，其中最为突出的是过度拟合情况，以及决策准确性方面的问题。针对上述问题，本课题提出了一种改进的C4.5决策树算法，在算法构建过程中，以树分枝的信息熵为研究对象，将熵值较高的部分和熵值较低的部分进行合并和平衡处理，从而达到减少决策树分支数量的目的；与此同时，考虑到C4.5算法在决策分支的确定过程中采用的是局部最优的方法，在准确性方面从整体上看有所欠缺，所以引入了了平衡因子控制算法的整体最优化性。

C4.5决策树算法设研究对象数据集为，该数据集中包括个类别，每一个类别表示为，选取该数据集中的一个属性数据，则可以被划分为多个子集，设有个取值，则被划分的子集可表示为。设为的例子总数，而为的例子数，为的例子总数，是的所有例子中所包括的的例子数，基于上述的设定，则可以得到如下定义：

（1）类别在出现的概率如式（1）所示：

（1）endprint