基于信息增益和GEP的决策树属性约简算法  

Constructing Decision Tree Attribution Reduction Algorithms with Gene Expression Programming Based on Information Gain

作　　者：王艳[1] 元昌安[2] 刘富田 

机构地区：[1]广西师范学院师园学院,广西南宁530226 [2]广西师范学院计算机与信息工程学院,广西南宁530023 [3]南宁市城市应急联动中心,广西南宁530022

出　　处：《广西师范大学学报（自然科学版）》2010年第3期113-117,共5页Journal of Guangxi Normal University:Natural Science Edition

基　　金：国家自然科学基金资助项目(60763012);广西自然科学基金资助项目(桂科自0731028);广西高等学校优秀人才资助计划项目(RC2007022);广西研究生教育创新计划项目(2008106030774M04)

摘　　要：分类是数据挖掘的一个重要研究方向,使用决策树进行分类是一种常用而且高效的分类方法。目前传统的算法有ID 3、C 4.5、CART等,这些算法都有如下的局限性:必须人工输入归类集合,划分属性,确定最优的分类集合。为了解决这些问题,本文做了如下工作:①提出信息增益排列GEP染色体头部的思想;②给出基于信息增益的GEP构造决策树属性约简算法(IG-GEPDTAR)并用实验进行验证;③实验表明该算法构造的决策树在具有100%准确性的同时,比使用GEP算法构造的决策树减少了冗余分支,其节点数比传统的ID 3算法和P ID算法构造的决策树的节点数分别减少了82.9%和31.2%。Classification is an important sector of Data Mining,and decision tree is one of the efficient classification methods used constantly. Nowadays,there are several classification algorithms which use decision tree ,for instance ID3,C4.5 and CART. But there are some disadvantages to use them,for example ,class set must be input manually ,attribute must be separated and the best class set is needed. This paper makes the following contributions to avoid these disadvantages.on the one hand,proposing a new concept of using information gain to line GEP chromosome＇s head ;on the other hand,proposing the algorithms of IG-GEPDTAR （constructing decision tree attribution reduction algorithms with gene expression programming based on information gain） and validate it by using experiment data. The result shows that decision tree constructed by IG-GEPDTAR is absolutely correct and better,it has less redundancies than Candida Ferreira＇s,has 82. 9% less nodes than that of ID3 algorithms,and has 31.2% less nodes than that of Wang Chunnian＇s.

关 键 词：GEP 信息增益 决策树归纳 熵 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]