董跃华　刘　力

1(江西理工大学信息工程学院　江西 赣州 341000)2(江西理工大学计算机科学与技术系　江西 赣州 341000)



基于均衡系数的决策树优化算法

董跃华1刘力2

1(江西理工大学信息工程学院江西 赣州 341000)2(江西理工大学计算机科学与技术系江西 赣州 341000)

摘要针对ID3算法多值偏向及误分类代价被忽视的问题，结合属性相似度和代价敏感学习，提出基于均衡系数的决策树优化算法。该算法既克服了多值偏向，又考虑了误分类代价问题。首先引进属性相似度和性价比值两者的均衡系数，对ID3算法进行改进；然后运用麦克劳林公式对ID3算法进行公式简化；最后将算法改进和公式简化相结合，得到基于均衡系数的决策树优化算法。实验结果表明，基于均衡系数的决策树优化算法，既能够提高分类精度，缩短决策树生成时间，又能考虑代价问题并降低误分类代价，还能克服多值偏向问题。

关键词ID3算法属性相似度代价敏感学习决策树均衡系数

0引言

数据分类是数据挖掘中重要的研究方法之一，其中有决策树分类器、贝叶斯分类器等基本技术。目前各类决策树算法中，ID3算法的影响最大，但ID3算法存在多值偏向等问题。针对ID3算法的多值偏向问题，自Quinlan提出C4.5算法[1]以来，许多学者进行相关的改进工作：文献[2]根据概率统计中条件概率的大小划分属性；文献[3,4]选取关联度值最大的属性作为分裂属性；文献[5-8]将粗糙集理论中的属性重要度或属性依赖度作为选择分裂属性的标准；文献[9,10]将属性相似度作为选择分裂属性的标准。在一定程度上，文献[2-10]引入新的属性分裂标准虽能克服多值偏向，但新的选择标准意味着会涉及统计学、粗糙集等其他领域知识，因为其不同于信息熵理论的计算方式，所以在分类准确率上会低于ID3算法。

针对ID3算法忽视因误分类而产生的代价问题，除了近来一些学者将误分类代价最小化作为分类效果新的衡量标准，并提出代价敏感学习CSL(Cost-Sensitive Learning)[11]之外，相关学者也进行了一些研究工作：文献[12]在CSL的基础上，提出基于误分类代价和测试代价的决策树算法，该算法虽考虑了代价问题，但却忽视属性自身的分类能力；文献[13,14]在文献[12]的基础上进行改进，提出了基于代价问题与信息熵公式相结合的决策树算法，该算法虽兼顾了代价问题和属性自身的分类能力，但仍存在多值偏向问题。

本文在文献[9]和文献[14]的基础上,结合属性相似度和代价敏感学习，提出了基于均衡系数的决策树优化算法，通过引入属性相似度和性价比值两者的均衡系数，对ID3算法改进。实验结果表明，基于均衡系数的决策树优化算法，能够克服多值偏向问题，提高分类精度，兼顾代价问题并降低误分类代价。

1ID3算法

1.1ID3算法的基本思想

设训练集S有s个样本，将训练集分成m个类，第i类的实例个数为si。选择属性Ai划分训练集S，设属性Ai有属性值{S1，S2，…，Sj，…，Sk}，Sj中属于第i类的训练实例个数为sij，则得到划分属性Ai的信息增益为[15]：

Gain(Ai,S)=Info(S)-InfoAi(S)

(1)

其中：

(2)

(3)

(4)

其中，pi为S中属于第i类的概率，pi=si/s；pij为sj中第i类样本的概率，pij=sij/sj。

1.2ID3算法的缺陷

ID3算法虽是常用的分类算法，但其仍存在一些缺陷：

(1) 信息熵的计算方式使ID3算法的属性选择容易偏向于取值较多的属性，但有较多属性值的属性不一定是当前最佳分裂属性；

(2) 分类过程中存在误分类情况，而ID3算法却忽视了因误分类而产生的代价问题[16]；

(3) 数据集中样本数增多时，算法对应计算量的增长幅度变大。

针对ID3算法的缺陷，可在多值偏向、误分类代价、信息熵公式简化方面对ID3算法进行改进。

2ID3算法相关的改进研究

针对多值偏向、误分类代价、信息熵公式简化这3个方面，相关专家学者对ID3算法进行改进并分别提出3种改进算法。本文的主要工作即为：通过研究3种改进算法的优缺点，寻找一种新的改进算法，使新的改进算法在继承3种改进算法优点的同时，也要克服其不足之处。

2.1针对多值偏向的ID3算法改进

文献[9]提出基于属性相似度的决策树改进算法，并表明将属性相似度作为属性选取标准可克服多值偏向问题。

2.1.1基于属性相似度的决策树改进算法的原理

文献[9]中参照知识粒度[17]的定义将条件属性Ai与决策属性D的属性相似度定义为：

(5)

其中Ai为条件属性集合C中的元素，C为：C={A1,A2,…,Ai,…,An}，D为决策属性集合：D={D1,D2,…,Dm}。元素fi，j表示属性Ai中属于Dj类样本个数，可用m+1行n+1列矩阵表示，矩阵中第j行第n+1列表示决策属性Dj的总样本个数，第m+1行第i列表示属性Ai的总样本个数。

式(5)中属性相似度值S(D,Ai)的大小表示条件属性Ai与决策属性D之间相似度程度的大小。

2.1.2基于属性相似度的决策树改进算法的不足

(1) 因属性相似度脱离信息熵理论而导致其在分类准确率上低于ID3算法。

(2) 未考虑因误分类而产生的代价问题。

2.2针对误分类代价的ID3算法改进

文献[14]提出一种基于代价敏感学习的决策树改进算法，该算法将信息熵理论与代价敏感学习相结合，在继承ID3算法较高分类准确率的同时，也考虑了误分类代价问题。

2.2.1基于代价敏感学习的决策树改进算法的原理

若选择Ai作为分裂属性且当前决策树结点Node为正例结点，裂后有n个子属性{S1,S2,…,Si,…,Sn}，对应n个子节点(Node1,Node2,…,Nodei,…,Noden,),子结点Nodei包含xi个正例和yi个反例，令前r个子结点为正例结点，后(n-r)个子结点为反例结点[18]。属性Ai的代价性能比值Cost_ratio(Ai)定义为[19]：

(6)

其中，Cost(Ai)为Ai未分裂时当前结点Node的误分类代价；FP为错误正例造成的误分类代价，FN为错误反例所造成的误分类代价，T_Cost(Ai)为获取属性Ai信息时所需付出的测试代价，分母加1是为防止某个属性测试代价为0时而导致计算错误出现。

2.2.2基于代价敏感学习的决策树改进算法的不足

该算法仍存在公式计算量较为庞大的问题以及多值偏向的问题。

2.3针对信息熵公式简化的ID3算法改进

文献[20,21]通过运用等价无穷小的方式，令ID3算法公式中的log对数运算转变为四则运算，以达到简化信息熵公式的目的。

2.3.1信息熵公式简化的原理

含拉格朗日型余项的麦克劳林公式定义为[22]：

(7)

由此得到近似公式：

(8)

由此可得：

(9)

当x趋向于0时，可得等价无穷小变换：

ln(1+x)～x

2.3.2等价无穷小简化信息熵公式的不足

当自变量必须趋向于0时，才可使用等价无穷小进行等价变换。当自变量不趋向于0时，使用等价无穷小变换会导致简化后的公式比原信息熵公式的精度低。

3基于均衡系数的决策树优化算法

3.1基于均衡系数的决策树优化算法的思路

3.1.1改进基于属性相似度和代价敏感学习决策树算法的不足

基于属性相似度的决策树改进算法可克服多值偏向问题；基于代价敏感学习的决策树改进算法可克服因脱离信息熵理论而导致分类准确率低下的问题，也能克服误分类代价被忽略的问题，因而将两种决策树改进算法相结合可弥补两者自身的不足。本文通过运用等效电阻原理，将文献[9]的属性相似度和文献[14]的代价性能比值相结合得到新的指标系数——均衡系数，均衡系数能够同时继承两种决策树改进算法的优势，因而能够同时兼顾多值偏向和误分类代价被忽视问题。最后将均衡系数引入信息熵公式以完成对ID3算法的改进。

3.1.2改进等价无穷小简化信息熵公式的不足

当自变量不会趋向于0时，使用等价无穷小变换会导致简化后的公式精度降低。信息熵公式的值的大小在0和1之间，因而在式(9)的基础上可得：

当x∈(0,1)时：

(10)

通过运用公式(10)对信息熵公式中的对数运算进行近似转换，以完成信息熵公式的简化。

3.1.3DTEC算法

本文针对“多值偏向、误分类代价被忽视问题”和“信息熵计算公式”两个方面，将改进基于属性相似度和代价敏感学习决策树算法的不足、改进等价无穷小简化信息熵公式的不足两部分的工作相结合，分别对ID3算法进行算法改进和公式简化，提出了基于均衡系数的决策树优化算法，简称DTEC算法。

3.2ID3算法的改进

3.2.1均衡系数的引入1) 代价性能比值的改进

误分类代价为专家给的相对值，测试代价多以货币为单位，代价性能比值中分子与分母两者的值域显然不在同一范围，这会导致比值不准确并产生误差。为克服该问题，可采用规范化方法对性能比值进行改进，将测试代价规范化至误分类代价的取值区间，规范化后的测试代价为T_NewCost(Ai)：

(max[Cost(Ai)]-min[Cost(Ai)])+min[Cost(Ai)]

(11)

则改进后的代价性能比值New_Cost_ratio(Ai)为：

(12)

式(12)中的分子和分母已处于同一数量级，可避免出现比值结果偏向分子和分母中数量级较大者的数量级偏向问题。

2) 均衡系数的引入

电路中有等效电阻原理：电阻R1和R2并联，等价于串联入等效电阻R′。电阻R1、R2、R′两端电压均为U，通过电流分别为IR1、IR2、IR′。由此可推导出如下关系：

(13)

属性相似度和性价比值分别对应电阻R1和R2，均衡系数对应电阻R′，运用等效电阻原理可将本文提出的均衡系数R(Ai)可定义为：

(14)

均衡系数R(Ai)的作用效果，等效于属性相似度和性价比值两者指标尽可能取较优值，同时令两者共同作用的效果达到最优值。

3.2.2引入均衡系数对ID3算法的改进

均衡系数对ID3算法式(1)进行改进后，得到新的信息增益式(15)：

Gain(Ai,S)New=Gain(Ai,S)×R(Ai)

=[Info(S)-InfoAi(S)]×R(Ai)

(15)

令改进后的信息增益Gain(Ai,S)new，作为属性分裂的新标准。新的属性分裂标准Gain(Ai,S)new既能克服ID3算法的多值偏向问题，又能使选择的分裂属性具有较小的误分类代价。

3.2.3ID3算法改进后的多值偏向分析1) ID3算法多值偏向分析

(16)

由此可知式(18)的恒成立是造成多向偏值问题的本质，所以要解决多向偏值问题只要避免式(16)恒成立即可。

2) ID3算法被改进后的多值偏向分析

(17)

(18)

3.3信息熵公式的简化

将ID3算法的信息增益公式完全展开后，变形为式(19)：

(19)

式(19)中常数m为训练集类别数，Info(S)为一个定值，因此式(19)只保留后一项也不会影响最终比较结果，则取后一项可得式(20)：

(20)

从式(20)中可看出：对数运算是计算中主要的耗时部分，因而消去对数运算能够降低计算量并提高计算效率。

sj中属于第i类的训练实例个数为sij，pij是Sj中属于第i类的概率，pij=sij/sj，且s1j+...+smj=sj，因此式(20)可进行如下转化：

近似式(10)比等价无穷小公式ln(1+x)≈x的精度要高。使用近似简化式(10)可进一步化简为：

Gain(Ai)2

ln2和样本个数s均为常数项，去掉后不影响结果的比较，将其去掉后进一步简化得到式(21)：

(21)

式(21)中的较为耗时的log对数运算已消除，公式完全由加减乘除四种基本运算组成，计算量降低且计算效率得到提高。

3.4DTEC算法的提出

DTEC算法包括均衡系数的引入、ID3算法改进和ID3算法公式简化三个部分的工作，将均衡系数式(14)、ID3算法改进式(15)和ID3算法简化式(21)相结合得到DTEC算法式(22)：

(22)

DTEC算法采用式(22)作为新的属性选择标准。DTEC算法既能克服多值偏向，考虑代价问题并降低误分类代价，又能简化ID3算法公式，降低计算量并提高计算效率。

3.5DTEC算法描述

输入：训练样本集S(样本中的属性值均进行离散化操作),C为条件属性集合，属性Ai∈C；D为决策属性集合。

输出：DTEC决策树。

步骤1计算条件属性Ai与决策属性D的属性相似度值S(D,Ai)；

步骤2在属性集合C中，计算属性Ai对应的代价性能比值New_Cost_ratio(Ai)′；

步骤3计算属性Ai对应属性相似度和性价比值两者的均衡系数R(Ai)；

步骤4引入均衡系数R(Ai)对ID3算法进行改进，得到属性分裂标准Gain(Ai,S)New；

步骤5利用麦克劳林展开式对ID3算法公式进行简化，得到属性分裂标准Gain(Ai)3；

步骤7按照式(22)分别计算各个属性对应的熵值，选取熵值最大的属性作为决策树的根节点，对样本元组进行分类。对分类后形成的子集，用递归的方法，计算熵值并按照熵值的大小进行属性分裂，直到DTEC决策树构建完成。

4实验及结果分析

4.1实验环境

4.1.1实验采用工具

1) 实验采用的数据集

本实验在标准数据集UCI上进行，采用UCI提供的若干个标准数据集(如表1所示)进行数据分析。

表1　数据集

2) 实验采用的实例训练集

采用商务购车顾客数据库(如表2所示)作为训练集D，对数据进行选取、预处理和转换操作后得到样本集合，该集合包含4个条件属性：喜欢的季节(含4个属性值：春天、夏天、秋天、冬天)、是否商务人士(含2个属性值：是、否)、收入(含3 个属性值：高、中、低)、驾车水平(含2 个属性值：良好、一般)。样本集合根据类别属性“是否买车”(含有 2 个属性值：买、不买)进行划分。

表2　商务购车顾客数据库训练集D

3) 实验采用平台

本实验采用WEKA平台，WEKA是一款免费且基于JAVA环境下开源的机器学习以及数据挖掘软件。由于WEKA属于开源软件，WEKA中的ID3算法位于weka.classifiers.trees包中，因此改进后的ID3算法只要符合其接口规范，就可以将新算法嵌入到WEKA中并调试运行。

本实验将ID3的WEKA源代码导入NetBeans IDE 8.0 RC中并添加DTEC算法源代码，然后在NetBeans IDE 8.0 RC中分别编译ID3算法和DTEC算法程序。

4) 实验采用设备配置

实验所采用计算机配置为：CPU为酷睿i5 2300系列，主频为2.8GHz，内存为4G，操作系统为Win 7。

5) 实验采用仿真软件

本实验将Matlab 2012a作为绘图仿真软件。

4.1.2实验初始条件

(1) 将表1数据集中2/3的样本作为训练集，1/3的样本作为测试集，采用文献[24]中的方法对数据集中连续性属性进行离散化操作。

(2) 令各个数据集处在相同的软硬件环境下，并使各个数据集的测试代价都相同。

(3) 分类准确率实验评价标准

分类准确率是分类问题中常用的评价标准，能体现出分类器对数据集的分类性能。分类准确率指分类器中被正确分类的样本个数在总的检验集中所占比例[25]，定义为式(23)：

(23)

其中s为总的样本个数，m为分类类别个数，si为训练集中属于第i类的实例个数。

(4) 误分类代价实验评价标准

评定标准：使用误分类代价比值w进行评价。误分类代价比值w定义为：

(24)

其中，Cost表示误分类代价，T_Cost表示测试代价，误分类代价比值w越大，表明在一个基本单位内的测试代价，所均分到的误分类代价越大。同时表明当误分类代价作为分类效果的衡量标准时，分类效果较差；当误分类代价比值w较小时，则说明分类效果较好。

4.2DTEC算法的实例验证与分析

以训练集D为例，根据式(1)计算ID3算法信息增益，根据式(22)计算DTEC算法的信息增益，根据式(21)计算ID3算法公式简化后的信息增益，最后按照决策树建树规则，构建各自的决策树，分别如图1、图2、图3所示。

图1　原ID3算法生成的决策树

图2　DTEC算法生成的决策树

图3　在原ID3基础上公式简化后生成的决策树

图1、图2、图3综合分析发现：

(1) 比较图1和图2。属性“喜欢的季节”属性值个数最多，多值偏向使其成为决策树的根节点。“喜欢的季节”是一种主观想法，不是购车的决定性因素。现实生活中，“收入”在一定程度上更能决定是否购车。由图2可看出，DTEC算法令“喜欢的季节”属性离决策树根结点的距离变远，降低其重要性；令“收入”属性作为决策树根结点，提高其重要性，符合实际情况，因此DTEC算法在一定程度上克服了多值偏向问题。

(2) 比较图1和图3。由图3可看出，ID3算法公式简化后生成的决策树与原ID3算法生成的决策树完全一致。表明本文中对原ID3算法进行近似转化的简化公式精度较高，能够与原ID3算法生成的决策树基本保持一致。

4.3实验验证及分析

4.3.1分类准确率和叶子节点数的比较

在表2提供的数据集进行实验数据测试，每一个数据集上进行10次试验。在分类准确率的实验结果中，去掉最大数据和最小数据，再求出平均分类准确率作为最终实验数据，可使实验结果具有普遍性。

将每一个数据集分成10个数据组，每个数据组中分别用ID3算法、C4.5算法、文献[9]算法、文献[14]算法和DTEC算法构建决策树，每个数据组上均构建10次。在叶子节点数的实验结果中，去掉最大数据和最小数据，再求出平均叶子节点数作为该数据组的最终数据。每个数据集里以数据组为最小单位进行类似操作，求出其平均叶子节点数作为该数据集的最终实验数据。实验结果如表3、表4所示。

表3　实验结果一

表4　实验结果二

从表3、表4的实验结果中可看出:相比于ID3算法、文献[14]算法、C4.5算法、文献[9]算法，DTEC算法具有较高的分类准确率和较少的平均叶子节点数，并降低了构建决策树的复杂度。

4.3.2决策树生成时间的比较

采用实例表1中提供训练集D，分别对ID3算法、文献[14]算法、C4.5算法、文献[9]算法和DTEC算法进行10次计算时间的测试,在实验结果中去掉最大数据和最小数据，再求出平均时间作为构建决策树所花费的时间。实验结果如图4所示。

图4　五种算法生成决策树的时间对比

图4中横坐标表示训练集样本的取值个数，纵坐标表示构建决策树所花费的时间。

从图4中可看出:(1) 样本个数偏少时，五种算法花费时间相差不大。(2) 从整体上看文献[14]算法，所花费的时间与ID3算法的时间基本相同。(3) 当样本个数相同时，DTEC算法构建决策树所花费的时间最少。(4) 当样本个数达到一定数量时，DTEC算法所节省的时间随着样本个数递增而变多，这表明：在构建大规模数据集的决策树时，使用DTEC算法能够节约更多的时间。

4.3.3 误分类代价的比较

以表3、表4中五种算法作为考察对象，让每种算法按其自身的分裂属性原则建立决策树，最后比较它们各自产生的误分类代价比值。实验结果如图5所示。

图5　各个数据集下误分类代价比值的对比

图5中横坐标表示各个数据集以及它们的名称，纵坐标表示各个算法在不同数据集上的误分类代价比值。

从图5中可看出:(1)文献[14]算法比ID3算法、C4.5算法、文献[9]算法的误分类代价比值都要小，当误分类代价作为分类效果的衡量标准时，文献[14]算法分类效果较好。(2)DTEC算法比ID3算法、C4.5算法、文献[9]算法的误分类代价比值都要小，但与文献[14]算法的误分类代价比值相差不大，当误分类代价作为分类效果的衡量标准时，DTEC算法与文献[14]算法分类效果近似。

4.4实验结论

结合图1、图2和图3可看出：(1) 本文提出的DETC算法能够克服多值偏向问题；(2) DETC算法中对ID3算法公式简化的部分，并未降低原ID3算法公式的精度，DETC算法生成的决策树与原ID3算法生成的决策树基本保持一致。

结合表3、表4、图4和图5中可看出：(1) 文献[9]算法和C4.5算法虽然分类精度较高，决策树建立时间较少，但未考虑误分类代价问题，当误分类代价作为分类效果的衡量标准时，分类效果较差；(2) 文献[14]算法误分类代价比值较小，虽当误分类代价作为分类效果的衡量标准时，分类效果较好，但分类精度低，决策树建立时间较长，此外文献[14]算法仍存在多值偏向问题；(3) 本文提出DTEC算法，继承了以上各个算法的长处，实验结果分析表明：本文的优化算法具有较高的分类精度，较少的平均叶子节点数；具有较少的决策树建立时间；考虑了代价问题并具有较低的误分类代价比值；此外还能克服ID3算法的多值偏向问题。

5结语

针对ID3算法不足之处，结合属性相似度和代价敏感学习提出了DTEC算法。首先，运用等效电阻原理得到属性相似度和性价比值两者的均衡系数，引入的均衡系数同时兼顾两者，使属性相似度和代价敏感学习的性价比值均较大；然后，通过引入均衡系数对原ID3算法进行改进，既克服了多值偏向问题，又兼顾了代价问题；再运用麦克劳林公式对ID3算法公式进行简化，降低计算量并提高计算效率；最后将ID3算法的改进工作和简化工作相结合，得到DTEC算法。实验结果表明，本文提出的DTEC算法较之其他改进算法，不仅克服了多值偏向问题，还能考虑代价问题并降低误分类代价，此外还具有较高的分类精度和较短的决策树建立时间。

参考文献

[1] 朱明.数据挖掘[M].中国科学技术大学出版社,2002:67-68.

[2] 李世娟,马骥,白鹭.基于改进ID3算法的决策树构建[J].沈阳大学学报:自然科学版,2009,21(6):23-25.

[3] 韩松来,张辉,周华平.基于关联度函数的决策树分类算法[J].计算机应用,2005,25(11):2655-2657.

[4] Jin C,Delin L,Fenxiang M.An improved ID3 decision tree algorithm[C]//Computer Science & Education,2009.ICCSE’09.4th International Conference on.IEEE,2009:127-130.

[5] 陶荣,张永胜,杜宏保.基于粗集论中属性依赖度的ID3改进算法[J].河南科技大学学报:自然科学版,2010,31(1):42-45.

[6] 朱颢东,钟勇.ID3算法的优化[J].华中科技大学学报:自然科学版,2010,38(5):9-12.

[7] 朱颢东.ID3算法的改进和简化[J].上海交通大学学报,2010,44(7):883-886.

[8] 黄宇达,范太华.决策树ID3算法的分析与优化[J].计算机工程与设计,2012,33(8):3089-3093.

[9] 陆秋,程小辉.基于属性相似度的决策树算法[J].计算机工程,2009,35(6):82-84.

[10] Luo H,Chen Y,Zhang W.An Improved ID3 Algorithm Based on Attribute Importance-Weighted[C]//Database Technology and Applications (DBTA),2010 2nd International Workshop on.IEEE,2010:1-4.

[11] 黄小猛.异构代价敏感决策树与随机森林核心技术[D].广西师范大学,2013.

[12] Qin Z,Zhang S,Zhang C.Cost-sensitive decision trees with multiple cost scales[M]//AI 2004:Advances in Artificial Intelligence.Springer Berlin Heidelberg,2005:380-390.

[13] 覃泽,韦建忠.CSL中测试属性选择方法[J].微计算机信息,2008,24(6):288-289.

[14] 刘星毅.基于性价比的分裂属性选择方法[J].计算机应用,2009,29(3):839-842.

[15] 陈英,马仲兵,黄敏.优化的C4.5决策树算法[J].软件,2013,34(2):61-64.

[16] 刘春英.基于关联度的代价敏感决策树生成方法[J].长春工业大学学报:自然科学版,2013,34(2):218-222.

[17] 马福民,张腾飞.一种基于知识粒度的启发式属性约简算法[J].计算机工程与应用,2012,48(36):31-33.

[18] 孟光胜.基于关联度和代价敏感学习的决策树生成法[J].科学技术与工程,2013,13(5):1196-1199.

[19] 阮晓宏,黄小猛,袁鼎荣,等.基于异构代价敏感决策树的分类器算法[J].计算机科学,2013,40(11A):140-142.

[20] 喻金平,黄细妹,李康顺.基于一种新的属性选择标准的ID3改进算法[J].计算机应用研究,2012,29(8):2895-2898.

[21] 谢妞妞,刘於勋.决策树属性选择标准的改进[J].计算机工程与应用,2010,46(34):115-118.

[22] 同济大学数学系.高等数学:上册[M].6版.北京:高等教育出版社,2007.

[23] 张春丽,张磊.一种基于修正信息增益的ID3算法[J].计算机工程与科学,2008,30(11):46-47,94.

[24] Hu X,Cercone N.Data mining via discretization,generalization and rough set feature selection[J].Knowledge and Information Systems,1999,1(1):33-60.

[25] 武丽芬.改进的决策树算法在文理分科中的应用研究[J].微计算机应用,2011,32(8):7-12.

收稿日期：2014-12-07。董跃华，副教授，主研领域：数据挖掘，软件工程，软件测试。刘力，硕士生。

中图分类号TP301.6

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.07.061

DECISION TREE OPTIMISATION ALGORITHM BASED ON EQUILIBRIUM COEFFICIENT

Dong Yuehua1Liu Li2

1(SchoolofInformationEngineering,JiangxiUniversityofScienceandTechnology,Ganzhou341000,Jiangxi,China)2(DepartmentofComputerScienceandTechnology,JiangxiUniversityofScienceandTechnology,Ganzhou341000,Jiangxi,China)

AbstractFor the problems of ID3 algorithm in neglecting multi-value bias and misclassification cost, by combining the attribute similarity and cost sensitive learning we proposed an equilibrium coefficient-based decision tree optimisation algorithm. The algorithm solves the problem of multi-value bias and takes in to account the misclassification cost simultaneously. First, we introduced the equilibrium coefficient between attribute similarity and the value of performance to price ratio to improve ID3 algorithm. Then we used McLaughlin formula to carry out formula simplification on ID3 algorithm. Finally, we got the equilibrium coefficient-based decision tree optimisation algorithm by combining the algorithm improvement and formula simplification. Experimental results showed that the decision tree optimisation algorithm based on equilibrium coefficient can improve the classification accuracy, shorten the time of decision tree generation, and consider the cost problem as well as reduce misclassification cost. Moreover, it can also overcome the problem of multi-value bias.

KeywordsID3 algorithmAttribute similarityCost sensitive learningDecision treeEquilibrium coefficient