论文总字数：24868字

摘 要

随着大数据时代的到来，人工智能再次走入大众的视野，机器学习作为其主要分支也发挥着极大的作用。决策树算法作为一种典型的分类方法，是基于树结构来进行决策判断的，可以快速并准确地分析数据，并在海量的数据中探索规律，进而完成对未知数据的分类。

本文首先对决策树的基础知识进行介绍，主要包括：如何构建一棵决策树、并选择不同的划分准则进行构建、处理决策树过拟合的方法、如何处理连续数据、如何处理噪声数据等等。同时我们选取UCI机器学习数据库中的十个数据库进行十折交叉验证，分别采用信息增益及增益率划分准则，使用预剪枝及后剪枝处理决策树过拟合问题，利用连续属性离散化处理连续数据，最后利用卡方检验处理数据中可能存在的噪声。实验发现，信息增益与增益率两种划分准则不会对分类精度产生太大影响；预剪枝和后剪枝可以显著减少决策树的结点个数，一定程度上预防过拟合，而利用卡方检验处理噪声数据也主要是对决策树的结点个数产生影响。

关键词：机器学习，决策树，信息增益

Abstract

With the arrival of the era of big data, artificial intelligence has come into the public's view again, and machine learning, as its main branch, also plays a great role., the decision tree algorithm as a kind of typical classification method, is to make decisions based on the tree structure, can rapidly and accurately analyze data, and to explore the law in the vast amounts of data, and then complete the unknown data classification.

This paper first introduces the basic knowledge of decision tree, including: how to build a decision tree, how to choose different partition criteria, how to deal with overfitting of decision tree, how to deal with continuous data, how to deal with noise and so on. At the same time, we select ten databases in UCI database for 10-fold cross-validation, respectively adopt the information gain and gain rate partition criteria, use pre-pruning and post-pruning to process decision tree overfitting, use continuous attributes to discretize continuous data, and finally use chi-square test to process the possible noise in the data center. It is found that the two classification criteria of information gain and gain rate have little effect on the classification accuracy. Pre-pruning and post-pruning can significantly reduce the number of nodes in the decision tree and prevent over-fitting to a certain extent, while noise data processed by chi-square test mainly affects the number of nodes in the decision tree.

KEY WORDS：machine learning, decision tree, information gain

目录

摘 要 Ⅲ

Abstract Ⅳ

第一章 绪论 1

1.1 引言 1

1.2 主要工作 1

1.3 论文结构 2

第二章 决策树 3

2.1 分类任务 3

2.2 决策树 3

2.2.1 决策树的定义 3

2.2.2 决策树的归纳推理 4

2.3 划分准则 5

2.3.1 信息增益 5

2.3.2 增益率 6

2.4 连续属性 7

2.5 剪枝 7

2.6 噪声 8

第三章 实验分析 9

3.1 实验方案 9

3.1.1 实验任务 9

3.1.2 实验数据 9

3.1.3 实验实现 11

3.1.4 实验步骤 13

3.2 实验结果 14

3.2.1 ID3决策树的性能 14

3.2.2 划分准则对决策树的性能影响 15

3.2.3 剪枝对决策树的性能影响 16

3.2.4 噪声对决策树的性能影响 18

3.3 实验结论 18

第四章 结语 20

参考文献 21

致 谢 22

绪论

引言

随着互联网的高速发展，网络数据的规模呈指数状急剧增加，大数据时代到来，这些数据极其庞大，但同时蕴藏着某些具有价值的知识，值得进一步挖掘并探索。与此同时计算机硬件的升级也提高了计算机的性能，在相同时间内可以更快地处理大规模数据。在此环境下，如何方便且有效地进行数据的分析与挖掘成为了广为关注的问题之一，人工智能也逐渐走入了大众的视野。

机器学习属于人工智能的一个分支，主要是在海量数据中训练得出一个学习模型，进而更加有效地预测尚未发生的事件，传统的机器学习算法包括：决策树、聚类、朴素贝叶斯、支持向量机等等，针对不同的数据集类型选择不同的机器学习算法可以更加有效地处理数据并发掘其中的规律。

其中，决策树算法是一种典型的分类方法。针对数据集的不同属性，由决策树的根部开始逐层判断，直至叶子结点判断结束，进而完成分类任务，既可以完成二分类任务也可以完成多分类任务，可以同时处理连续数据和离散数据。其中，ID3决策树是最重要且最常用的决策树之一，也是当今许多决策树的主要原型之一。决策树算法计算量相对较小，且容易转化为分类规则，其主要优点是模型具有可读性，分类速度快。通过对ID3决策树算法的实现与其在实际数据上的应用，有助于我们理解机器学习的算法。

普遍认为，最初的决策树算法是心理学家兼计算机科学家E.B.Hunt在1962年研究人类的概念学习过程时提出的CLS(Concept Learning System)模型，这个算法确定了决策树“分而治之”的学习策略。决策树学习算法最著名的代表是ID3[Quinlan,1979]，其划分准则是信息增益，之后著名的C4.5决策树算法[Quinlan,1993]对ID3进行改进，引入增益率划分准则，并采用信息增益与增益率相结合的方法进行划分属性，之后的CART决策树[Breiman et al.,1984]使用“基尼指数”来选择划分属性，除此之外人们还设计了很多其他准则来进行属性划分。

主要工作

本文的主要工作包含了几个不同的部分。在理论知识方面，从分类任务讲起，介绍决策树的定义、分类以及如何构建一棵完整的ID3决策树；利用数学公式展示如何通过信息增益及信息增益率选择划分准则；如何将连续属性离散化处理；如何通过剪枝处理决策树的过拟合问题以及如何利用卡方检测处理数据中的噪声。

剩余内容已隐藏，请支付后下载全文，论文总字数：24868字