改进的决策树ID3算法及应用

葛璐瑶

摘要 本文利用数据挖掘决策树ID3算法，以校园一卡通数据库中数据挖掘在高校贫困认定领域的应用为实例，通过对简单高效的ID3算法的改进，先排除掉其他因素的影响，再构建最优决策树，从而加强数据结果的可靠性。

【关键词】ID3算法 构建决策树 数据挖掘恩格尔系数

数据挖掘即在海量数据中通过特殊算法，从而挖掘出有效的、先前未知的信息，利用数据库、人工智能和数理统计等多方面的技术，是一类深层次的数据分析方法。常用的数据挖掘算法有很多，譬如CART分类算法、NaIveBayes朴素贝叶斯算法、EM最大期望算法等，不同的算法在数据挖掘领域用处也不尽相同。针对高校管理过程中生成的海量数据，可以对其挖掘利用，典型的即提取利用学生校园一卡通中的交易数据，对比分类，应用于高校贫困评定中。众所周知，高校在校生绝大部分的消费均在校园内完成，而随着数字化校园的构建，校园一卡通己成为高校内部消费购物的唯一途径，因此校园一卡通的充值金额、刷卡次数等可以在很大程度上衡量一个学生的消费水准，从而判定其财富程度。本文提出用决策树ID3算法处理校园一卡通中数据，但ID3算法仍存在许多弊端，因此提出采用改进的决策树ID3算法。

1 决策树ID3算法的描述

决策树ID3算法，它是一種通过对一个训练样集Es递归构造决策树的算法，在这个训练样集里选择一个属性划分类别，Es属性的取值为Cl、C2、C3…Cn概率值值为Pl、P2、P3 …Pn，定义一个函数称作信息值或熵：

Info（[Cl、C2".Cn]）=Entropy （Pl、P2--Pn）= - Pllog2Pl- P21092P2-"'Pnlog2Pn，若使用另一个样集里的属性M对样集Es分组，那么新的信息值，定义为：

Entropy （Es， M）=∑，（IEsi/Esl）Entropy （Es），M相对于Es的信息增益Gam（Es，M）定义为：Gain （Es，M）= Entropy（Es） - Entropy （Es，M），且信息增益越大，训练样集越容易实现简单分类。虽然利用上述的ID3算法可以很简单方便生成一棵决策树，但是使用ID3算法仍然存在许多问题，最典型问题即ID3算法只针对于当前属性值取最优分类，忽略全局其他因素[4]，所以需要对ID3算法进行进一步的改进，既要利用ID3算法的简单方便与直接，又要从长远考虑，综合其他因素生成最优决策树。因此，在原ID3算法的基础上加以改进，即判断最优分类属性时不仅考虑各个属性的信息增益，同时考虑其他干扰影响因素。

2 特征提取实例

电子支付平台是面向在校师生提供的一系列电子支付服务的网络平台，在高校管理过程中，电子支付平台会生成海量数据，这些数据含有潜在的意义，需要我们挖掘发现其中的隐含信息，以学生校园一卡通数据库中的信息为例，我们可以选取其中学生校园卡充值交易额、校园卡使用次数最为数据源，经过多次实验测试得到划分标准，应用于高校贫困学生认定中。具体过程如下：

2.1 确定数据挖掘对象

为了更好的认定学生贫困程度，不仅调取学生的校园一卡通交易数据，同时走访调查各个学生的附加信息，如家庭收入水平、学生每月生活费用等，表1为部分学生的每个月的基本信息，包括学生的家庭收入水平、学生生活费用总额、校园卡充值金额、校园卡交易次数、贫困判定结果，这些基本信息是高校贫困认定中有着重要意义的数据信息，在此信息的基础上，利用数据挖掘中决策树ID3算法，生成一棵简易决策树。

2.2 生成决策树

通过学生基本信息表，选择“贫困判定结果”为划分属性，训练样本含有7个“贫困”和5个“非贫困”，对应于信息值Info（[7，5]）=- （7/12） log2 （7/12） - （5/12） log2（ 5/12） =0.98。

在评估“家庭收入水平”属性时，对应于“贫困”和“非贫困”类的个数分别为[4，1]、[2-2]、[2，1]，他们的信息值分别是：Info（[4，1]）=0.72， Info（[2，2]）=l，Info（[2，1]）=0 92，那么“家庭收入水平”相对于“贫困判定结果”的信息值为：

Info（[4，1]，[2，2]，[2，1]）=（5/12）Info（[4，1]）+（4/12）1nfo（[2，2]）+（3/12）Info（[2，1]）=0.86，那么“家庭收入水平”相对于“贫困判定结果”的信息增益为：

Gain（家庭收入水平）=Info（[7，5]）-Info（[4，1]，[2，2][2，1]）=O.l2，同理可以求出其他属性的信息增益：Gain（学生生活费用总额）=0.41，Gam（校园卡充值金额）=0.06，Gain（校园卡交易次数）=0.30

由上述计算得“学生生活费用总额”信息增益值最大，因此选择“学生生活费用总额”为决策树根节点的划分属性，创建如图l所示决策树。

2.3 改进ID3算法

2.3.1 恩格尔系数

恩格尔系数（Engel's Coefficient）指居民家庭中食物支出占消费总支出的比重，恩格尔系数是用来衡量家庭富足程度的重要指标。

恩格尔系数A=食物支出金额/总支出金额

本文利用恩格尔系数的作用，在判定贫困程度过程中可以把校园一卡通的充值金额认定为食物支出金额，把学生生活费用认定为总支出金额，利用下式：

改进的恩格尔系数五=校园卡充值金/学生生活费用总额

从公式不难看出，系数越小，说明学生越富裕，贫困程度当然越小。

2.3.2 添加判定系数的判定方案

因此在利用决策树ID3算法判定学生贫困程度时，可以加入恩格尔系数，给定一个贫困程度的标准值五，计算每个申请贫困的学生的改进恩格尔系数A_i.。

若A_i≤A，则非贫困，不予考虑

若A_i>A，则初步判定贫困，构建决策树，确认最终结果。

3 结束语

虽然本文利用改进的ID3算法对学生贫困程度认定过程增加了限制条件，使判定过程更可靠，但是贫困认定并非一成不变，在认定过程中，每个学生的实际情况可能有所不同，认定选项也不是绝对有效的，因此上述算法的提出只能起到辅助性作用，真正的判定还需要结合更多方面，因此，在判定过程中仍然需要添加更多因素及条件，从而使判定结果更加有效可靠。

参考文献

[1]严坤.数据挖掘技术研究[J].电脑迷，2017 （10）：185.

[2]光峰，姚程宽，卢灿举，曹立勇，詹喆.数据挖掘经典算法研究[J]，商丘师范学院学报，2016，32 （03）： 44-47.

[3]李会，胡笑梅，决策树中ID3算法与C4.5算法分析与比较[J].水电能源科学，2008 （02）：129-132+163.

[4]杨洋.决策树ID3算法及其改进[J].软件导刊，2016 （08）： 46-48.

[5]田丽，智慧校园环境下的校园一卡通建设[J].华东师范大学学报（自然科学版），2015 （Sl）：530-535.

[6]刘星，恩格尔系数、基尼系数与经济增长关系研究[J].统计与决策，2014 （02）： 87- 89.