基于信息增益法的决策树构造方法

基于信息增益法的决策树构造方法 基于信息增益法的决策树构造方法 新疆农业大学2008,31(2):91,94 JournalofXinjiangAgriculturalUniversity 文章编号:1007—8614(2008)02—0091-04 基于信息增益法的决策树构造方法 朱平,张太红,张晓明 (新疆农业大学计算机与信息工程学院,乌鲁木齐830052) 摘要:决策树数据挖掘技术是目前最有影响和使用最多的一种数据挖掘技术.决策树构造的方法很多,本研 究提出一种基于信息增益的决策树构造方法,给出了相应的决策树构造算法,并通过一个实例对其进行了说明. 关键词:数据挖掘;决策树;信息增益 中图分类号:TP274.2文献标识码:A ADecision—MakingTreeConstruction MethodBasedonInformationGain ZHUPing,ZHANGTai—hong,ZHANGXiao—ming (CollegeofComputerandInformationEngineering,XinjiangAgriculturalUniversity,Uru mqi, 830052) Abstract:Decision—Makingtreemethodisoneofthemostimportantandusefulwaysofdataminingtech— nology.Thispaperfirstproposesadecision—makingtreeconstructionmethodbaseoninformationgain, thengivesthecorrespondingalgorithmthroughoneexample. Keywords:data—mining;decision—makingtree;informationgain 近几年来,各类院校的办学规模逐渐扩大,而院 校录取考生报到率也在下降.报到率低一方面会浪 费该地区招生 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 名额;另一方面不利于院校自身 的发展.报到率低成为招生主管部门和院校面临的 一 个新课 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 . 为了科学客观地 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 影响院校报到率因素和预 测来年的报到人数,更好的做好招生工作.本研究 采用分类分析中的决策树方法,对新疆警官高等专 科学校招生数据库中的数据进行数据挖掘,为管理 者决策提供理论依据. 1基于ID3的决策树生成 ID3决策树算法是1986年由Quinlan提出的. ID3l_】算法运用信息熵理论,选择当前样本集中具 有最大信息增益值的属性作为测试属性,样本集的 划分则依据测试属性的取值进行,测试属性有多少 不同取值就将样本集划分为多少子样本集,用迭代 的方法在相应的样本子集的节点上生长出新的叶子 收稿日期:2007—11—17 通讯作者:张太红,E—mail:zth@xjau.edu.cn 节点,直到无可分样本,无剩余属性或样本同属于一 个类别时结束.信息论知识表明系统的不确定性越 小,信息的传递就越充分.ID3算法根据信息论理 论,采用信息增益作为划分后样本集的不确定性的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 ,即算法在每个非叶节点选择信息增益最大 的属性作为测试属性. 1.1ID3算法原理 设S是S个数据样本的集合.假定类标号属性 具有个不同的值,定义个不同类C(i一1,…, ).设S是类C中的样本数.对一个给定的样本 分类所需的期望信息由式(2.1)给出: lH j(ss2一,S,)一>Plog2(P)(1) i=1 式中:P是任意样本属于C的概率,并用s/s 估计. 设属性A具有个不同值{A,A,…,A).可 以用属性A将S划分为个子集{S,S,…,S};其 中S,包含S中这样一些样本,它们在A上具有值 92新疆农业大学 .如果A选作测试属性(即最好的分裂属性),则这 些子集对应于包含集合S的节点生长出来的分枝. 设S是子集S中类C,的样本数.根据由A划分 成子集的熵(entropy)或期望信息由式(2)给出: E(A)=妻I(S…,)(2) 式中:I(SS巧,…,S):P—S/J5JJ是中的 样本属于类C的概率. 最后用属性A划分样本集S后所得的信息增 益是: Gain(A)一(S1,S2,…,S),E(A)(3) 算法计算每个属性的信息增益,具有最高信息 增益的属性选作给定集合S的测试属性.创建一 个节点,并以该属性标记,对属性的每个值创建分 枝,并据此划分样本. 1.2ID3算法描述 假设用T代表当前训练样本集,当前的候选属 性集用T_attributelist表示,候选属性集中的所有 属性皆为离散型,连续值属性必须事先经过预处理 转化为离散型.ID3算法的描述为: 算法:Generate—decision—tree由给定的训练集 产生一棵决策树 输入:训练集T,属性集合T—attributelist 输出:一棵决策树 [1-]~lJ建根节点N; E2]IFT都属于同一类c,则返回N为叶节点, 标记为类C; E3]IFT—attributelist为空,则返回N为叶节 点,标记N为T中出现最多的类; [4]ForeachT—attributelist中的属性计算信息 增益Gain; [5]N的测试属性Test—attribute为T—at— tributelist中具有最高Gain值的属性; [6]ForeachTest—attribute的不同取值 { 由节点N长出一个新叶子节点 IF新叶节点对应的样本子集T为空 不再分裂此子节点,将其标记为T中 出现最多的类; ELSE在该叶节点上执行 Generate— decision— tree(T,T一 at- tributelist),继续对它分裂 ) 此算法是一个贪心算法,采用自上而下,分而治 之的递归方式来构造一个决策树. 2报到率问题实现过程 2.1确定业务对象 采用决策树__3方法,针对院校学生的报到情况 (已报到或不报到)进行分类分析,建立基于报到率 的决策树分类模型,根据决策树模型生成规则集,并 使用决策树模型预测新生报到率,从而预测来年的 报到人数. 2.2数据预处理 表1为院校录取考生表. 以2006年新疆警官高等专科学校录取数据和 未报到考生为例,利用决策树技术研究考生报到与 否可以由哪些属性决定(表2). 表1院校录取考生表 Table1Tableofnewstudentsenrolledbycollegesanduniversities 第2期朱平,等:基于信息增益法的决策树构造方法93 决策属性是否报到共有1016考生记录,其中 884考生是报到,132考生是未报到,那么使用(1), (2),(3)公式分别计算以下属性的熵: 表2属性的决策矩阵 Table2Decision.makingmatrixofattributes 录取志愿序号的熵: I(S)一一(884/1016)log2(884/1016)一(132/ 1016)log2(132/1016)一0.557 Entropy(S,投档成绩低于本三)一一(37/598) log2(37/598)一(561/598)log2(561/598)一0.335 Entropy(S,投档成绩高于本三)一一(95/418) log2(95/418)一(323/418)log2(323/418)一0.773 Entropy(S,投档成绩)一(598/1016)*Entro— PY(S,投档成绩低于本三)+(418/1016)*Entro— PY(S,投档成绩高于本三)一0.511 Gain(投档成绩)一I(S)一Entropy(S,投档成 绩)一0.046 同理 Gain(科类)一0.008 Gain(录取志愿序号)一0.004 Gain(计划性质)一0.001 根据以上数据得出Gain(投档成绩)>Gain(科 类)~Gain(录取志愿序号)~Gain(计划性质),为了 清楚的挖掘出有价值的信息,选择信息增量最大属 性:投档成绩和科类创建分枝,并据此划分样本 (图1). sfbd(是否报到) Node0 Category%月 -0l3.0l32 _l87.0884 Tota1lo0.01016 sfsx(投档成绩) 1(高于本三分数线) Nodel Category%月 -022.795 0l77.3323 T0tal41.1418 0(低于本三分数线) Node2 Category%月 -06237 lUl93.856l T0ta158.9598 kldm(科类) 1(文科)5(理科)1(文科)5(理科) NoI1e3 Category%月 -0l9.440 掰l80.6l66 Tota120.3206 N13(Ie4 Category%月 -025.955 l74.1l57 Tota120.9212 Node5 Category%月 -05.422 _l94.6382 Total39.7404 Node6 Category%月 -07.7l5 -l92.3179 Total19.1194 图1院校报到率分析与预测模型 Fig.1Analysisonregistrationrateofstudentsandforecastingscale 3预测模型解释 节点Node0为该院校总体样本. 节点Node1和节点Node2是在总体样本 Node0上按信息增量最大的属性:投档成绩,分别 94新疆农业大学2008年 化分出高于本三分数线样本集和低于三本分数 线样. 节点Node3和节点Node4是在样本Node1, 节点Node5和节点Node6是在样本Node2上按 信息增量第二的属性:科类,分别划分文科,理科. 对院校报到率分析与预测使用的分类模型,结 果被解释为分类模式,该模式可用以下规则描述: 报考该学院的考生总体报到率为87.0. 如果投档成绩低于本科三批次录取分数线的考 生报考该院校,那么报到率93.8. 如果投档成绩高于本科三批次录取分数线的考 生报考该院校,那么报到率77.3. 如果投档成绩低于本科三批次录取分数线的文 科考生报考该院校,那么报到率94.6. 如果投档成绩低于本科三批次录取分数线的理 科考生报考该院校,那么报到率92.3. 如果投档成绩高于本科三批次录取分数线的文 科考生报考该院校,那么报到率80.6. 如果投档成绩高于本科三批次录取分数线的理 科考生报考该院校,那么报到率74.1. 4结果分析 投档成绩高于本三录取分数线的考生报到率 低,只有占该样本的77.3.其中该样本集中理科 考生占投档成绩高于本科三批次录取分数线的理科 考生录取样本的80.6,样本集中文科考生占投档 成绩高于本科三批次录取分数线的文科考生录取样 本的74.1. 对于这些报到率低的样本集,在录取前有必要 采取一定的措施来遏止浪费招生计划的现象.比 如:院校采取签定 协议 离婚协议模板下载合伙人协议 下载渠道分销协议免费下载敬业协议下载授课协议下载 ,交纳一定的保证金,超计划 录取该样本集的考生来弥补未报到考生留下的空缺 计划或者省级招办将这些未报到考生记录到诚信档 案里面,来年录取来对这些考生采取一定程度上 限制. 由实验证明:ID3算法的优点是算法的理论清 晰,方法简单,学习能力较强.其缺点是只对比较小 的数据集有效,且对噪声比较敏感,当训练数据集加 大时,决策树可能会随之改变. 参考文献:' [1]王霓虹.基于数据挖掘的决策树算法研究及应用探讨[D3.哈尔滨;东北林业大学,2006. [23王睿.基于兴趣度的判定树算法快速分类的优化[D].成都;电子科技大学,2006. [33倪春鹏.决策树在数据挖掘中若干问题的研究[D3.天津:天津大学,2004. [43IanHWritten,EibeFrank.数据挖掘:实用机器学习技术.2版.董琳,译.北京:机械工业出版社,2006.