基于ID3决策树的数据分析文献综述

一、选题背景和意义：

随着大数据时代的兴起，产生的数据越发庞大，但是大部分的数据其实是没有意义的，而将海量的数据通过人为的处理和整理，能够通过庞大的数据得到有效的数据和结论以及规律，而以往是使用统计学的手段对数据进行处理，但面对海量的数据，统计的手段展现了他的局限性，为了处理海量的数据，诞生了数据挖掘、机器学习等技术用于对数据进行处理和分析。而本设计在对数据集处理的选择上，选择了ID3决策树算法。

ID3决策树算法作为一种解决分类问题的分类算法已经相当成熟，决策树学习的本质是从训练数据中归纳出一组分类规则。他的设计原理是根据给定的训练集，对不同的属性分别计算相应的信息增益并且以此为依据构建形成一个决策树模型，来达到实现分类的目的。

但ID3决策树算法也存在其缺陷，比如他不能处理连续属性。本设计将在实现ID3决策树算法的基础之上，进行改进，使改进之后的基于ID3决策树算法的程序不但可以处理离散属性还能处理连续属性，并能处理二类及多类分类问题。本设计旨在在学习和了解机器学习和分类算法的基础上通过实现来加深对这类问题的一种解决方案的深刻认识，同时根据查阅的资料来优化算法以适应于更广阔的的分类问题。

二、课题关键问题及难点：

课题的关键问题和难点在于学习和了解ID3算法，并且使用高级语言实现ID3决策树，并且需要考虑如何使得所编写的程序能够处理离散属性和连续属性，还能处理二分类及多分类问题，同时需要生成适合的训练集用于训练模型，并对模型的结果的性能进行分析。

三、文献综述（或调研报告）：

本设计是基于ID3决策树进行数据分析，首先要了解什么是分类问题。对于一个对象集合，他拥有许多不同的属性，不同属性对于这一对象有着不同大小的影响，有的属性的变化会给对象带来巨大的变化，而有的属性的变化则相对而言变化更小，而分类问题则是使用给定的数据集开发一个分类规则，该规则可以根据其属性值确定对象的类别。如果属性足够，那么总是可以构造一个决策树来正确地对训练集中的每个对象进行分类，并且通常会有很多这样的正确决策树。归纳的实质是超越训练集的范围，以训练集构造一个决策树，该决策树不仅对训练集中的对象进行正确分类，而且需要对其他（看不见的）对象也进行正确分类。为了做到这一点，决策树必须捕获对象的类与其属性值之间的某种有意义的关系。如果在给定两个决策树之间的选择，且每个决策树在训练集上都是正确的，那么应当选择更简单的决策树，因为是它更可能捕获问题中固有的结构。

ID3决策树算法是基于信息增益作为分类依据，进行分类建模的算法。信息熵是指的对于一个集合他根据集合内部不同类所占的频率进行计算所得到的一个反应集合信息纯度的值，该值越小则该集合的纯度越高。而信息增益是指的使用信息熵减去集合内不同属性的划分的和，一般而言信息增益越大意味着使用该属性在这个取值所划分得到的纯度提升越大，以此为划分依据，不断递归生成决策树。

在决策树学习中剪枝是决策树学习算法对付“过拟合”的主要手段.为了尽可能正确分类训练样本,结点划分过程将不断重复,有时会造成决策树分支过多,这时就可能因训练样本学得“太好”了，以至于把训练集自身的一些特点当作所有数据都具有的一-般性质而导致过拟合.因此,可通过主动去掉一些分支来降低过拟合的风险.决策树剪枝的基本策略有“预剪枝”(prepruning)和“后剪枝”(post-pruning) [Quinlan, 1993]. 预剪枝是指在决策树生成过程中,对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点;后剪枝则是先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶节点。