决策树分类优化算法的研究

《决策树分类优化算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、‘国内图书分类号：TP301．6。国际图书分类号：004西南交通大学√～，，．．：_．．．研究生学位论文决策树分类优化算法的研究年级．．三雯雯主级一姓名昱绪玲申请学位级别亟±专业过篡扭廑旦垫苤指导教师邳垩塾握二零一零年十月十五日密级：公开ClassifiedIndex：TP301．6U．D．C：004SouthwestJiaotongUniversityMasterDegreeThesisTheResearchontheAlgorithmsofOptimizingDecisionTreeClassificationGrade：2007Candi

2、date·WuXulingAcademicDegreeAppliedfor：MasterSpeciality：ComputerApplicationTechnologySupervisor：ProfessorDengPingOct15，2010西南交通大学曲南父通大罕学位论文版权使用授权书一本学位论文作者完全了解学校有关保留、使用学位论文的规定，向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅权西南交通大学可以将本论文的全部或部分内容编入有关数据库进行影印、缩印或扫描等复印手段保存和汇编本学位论文。本学位论文属于1．保密口，在年解密

3、后适用本授权书；2．不保密d使用本授权书。(请在以上方框内打“4")学位论文作者签名：苏姥如指导老师签名：日期：≯口扣·II·I了日期：西南交通大学硕士学位论文主要工作(贡献)声明本人在学位论文中所做的主要工作或贡献如下：本文对决策树的集中分类算法进行了研究分析，并重点研究了其经典的ID3算法，在深入分析了ID3算法之后，对本算法存在的主要问题做了如下的改进工作。主要包括：1．针对1D3算法中的对数log计算以及属性信息增益的计算过程复杂这一问题，本文在ID3算法的基础上，提出了一种简化算法。运用了高等数学中的泰勒公式和麦克劳林公式的近似公式，

4、对属性信息增益的计算式进行化简，使得对属性信息增益的非常简洁。简化后的ID3算法与原ID3算法生成的决策树结构相似，但技术复杂性要小；随着数据集规模的变大，其效果更明显。2．ID3算法存在的另一个不足就是在利用信息增益选择测试属性时，往往偏向于选取有较多取值的属性。针对这一问题，本文对简化后的ID3算法引入了一个与属性取值个数相关的函数。这样，ID3的多值偏向问题得到了解决。3．用面向对象的JAVA高级语言实现了改进前后的1D3算法，并且在不同规模的数据集上进行仿真实验，把改进后算法分别与ID3算法、C4．5算法进行比较分析，验证了改进后算法在

5、构建决策树时所需的时间及分类准确率两个方面都优于其他两个算法。本人郑重声明：所呈交的学位论文，是在导师指导下独立进行研究工作所得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中作了明确说明。本人完全了解违反上述声明所引起的一切法律责任将由本人承担。学位论文作者签名：关纬谚日期：OsIo·17．I尸～一—————————————————————————————————————————————————一一西南交通大学硕士研究生学位论文第l页摘要4数据挖掘就是从

6、大量的、不完全的、有噪声的数据中，提取出有效的和潜在规律性信息的过程。数据挖掘的任务就是从数据集中发现模式，它融合了数据库、人工智能，、机器学习、统计学等多个领域的理论和知识。在数据挖掘中，分类和预测是被广泛研究的技术，并且己经广泛地应用于许多领域，对未来商业和人们的生活也将产生深远的影响。决策树方法自20世纪60年代以来，在分类、预测、规则提取等领域有着广泛的应用，其中以Quilan于1986年提出的ID3算法最为著名。本文主要研究决策树D3算法及其改进。本文深入研究了ID3算法的理论基础及构建决策树的过程等知识。Quirdan提出的ID3算

7、法虽然很经典，但也有美中不足之处。第一，算法中使用了对数计算，而且计算过程复杂；第二，取值较多的属性被选择的机率比较大，即多值偏向问题。为了解决ID3的这些问题，本文引入了泰勒公式和麦克劳林公式，对原ID3算法进行化简，不仅属性信息增益的计算步骤减少，而且使信息熵的计算公式本身变得十分简洁；对于ID3算法偏向于选取有较多取值的属性的缺点，用一个与属性取值个数相关的函数对简化后的属性信息增益进行修正。通过以上两个方面的优化，新算法在构建决策树的速度上得到提高，同时也解决了ID3算法多值偏向的不足。然后，使用同一个小数据集对改进前后的算法进行实例分

8、析，分别得到其对应的决策树。最后，用面向对象的JAVA高级语言实现了改进前后的ID3算法，并且在不同规模的数据集上进行仿真实验，把改进后算法分别与ID