论文总字数：18580字

目 录

1 绪论 1

1.1研究背景与意义 1

1.2 国外研究现状 2

1.3国内研究现状 2

1.4 论文主要研究内容 3

2 决策树基础 4

2.1信息熵的概念 4

2.2划分选择 4

2.2.1信息增益 4

2.2.2增益率 4

2.2.3基尼指数 5

2.3剪枝处理 5

2.4连续值与缺失值处理 6

2.5本章小结 7

3 基于主成分分析的决策树构建 7

3.1背景 7

3.2相关性度量 8

3.3主成分分析法 9

3.4简单的决策树剪枝方法 10

3.5实例 12

3.6本章小结 15

4 算法的MATLAB实现 15

4.1目的 15

4.2步骤 15

4.3结果 24

4.4小结 25

参考文献 26

致谢 28

基于主成分分析的决策树剪枝算法

曲建璋

，China

Abstract：In recent years, the rapid development of artificial intelligence has affected people's lives in many fields. As a basic algorithm in the field of artificial intelligence, the decision tree algorithm can analyze the instances from a given data set and understand the nature of unknown things. It is a very important algorithm.

This paper simply introduces the basic process of the decision tree algorithm and the importance of pruning, and a new pruning method is proposed, This method constructs a decision tree through correlation analysis and principal component analysis. By constructing a reasonable upper limit value and lower limit value, the tree is pruned. This method simplifies the traditional decision tree construction and pruning algorithm and ensures the accuracy. In the end, we used MATLAB to program this method and proved the reliability of this method.

Key words：machine learning；decision tree；pruning；MATLAB；Principal component analysis；Gain rate

1绪论

1.1研究背景与意义

随着当今社会人工智能领域的发展，作为人工智能领域基础的机器学习课程(Machine Learning, ML)也得到了较快的发展与较大的关注。机器学习是由多个学科相互结合而产生的，它涉及了概率论、数据分析、统计学等多门数学学科并可用计算机语言进行编程实现以解决实际的问题，它的目标是使计算机能够像人一样从“数据”中“学习”新的知识从而得出应有的结果。

决策树是机器学习这门学科中使用的一种十分基础而重要的算法，它可以从给定的已知的训练数据集用过“学习”得到一个树形结构，用这个结构（即决策树）来对未知的一些新实例进行分类^[1]。例如，我们要在没有足够经验的条件评价一个西瓜的好坏， 而影响西瓜好坏的因素有很多，包括：色泽、根蒂、敲声、纹理、脐部、触感、密度、含糖率等等^[1]，每一项属性都对一个瓜是好是坏产生的影响，这种情况下，我们要想能够较为准确的判断出所给出瓜的好坏问题，必须进行大量的采样，即使所列出的几种属性每种只有两个取值，为了能够包含所有的情况，我们至少需要进行次有效采样，采样次数极大，严重影响了效率并造成了极大的浪费；而决策树可以在所给定的训练数据集中数据较少的情况下，根据各属性的重要性得出一个树，决策树的最下层的叶节点对应于最终决策结果（即一个瓜为好瓜或坏瓜）^[1]，从所得的树中可以直观且较为准确的判定所给样本的好坏。

决策树算法主要分为三个主要部分。第一是划分，每个事物包含多个属性，每个属性都对事物的性质有一定的影响，但影响程度有大有小（如经验所知，我们平常判断一个瓜的好坏时通常靠敲声），我们希望能找出在特定情况下对事物性质影响最大的那个属性（即最优划分属性）构造出决策树，这样可以使决策树的尽可能最优，通常我们使用的是信息增益、增益率、基尼指数等方法来进行度量；第二是剪枝处理，是防止利用训练样本构造决策树时拟合的太过仔细，将训练集的一些特例当作了所有元素都具有的一般性质而导致最终决策树特别庞大且准确性欠佳，我们这时通过主动将一些节点作为叶节点从而去除一些分支的方法来解决这个问题，通常使用的方法有两种，一种是预剪枝，一种是较为复杂的后剪枝；第三是连续值处理与数据的一些异常情况的处理，用来处理包含连续属性（如上所说的含糖率，它是一个百分数）的问题与属性缺失时的决策树的构造问题。

在划分部分中，除了所提到的三种，还有许多其它的决策树构造与剪枝方法，但现在已经证明，不同的决策树构造准则会在一定程度上影响决策树的复杂度，但对泛化性能只能产生较小的影响^[2]因此现在基本上使用其中较好的基尼指数。在处理连续值与缺失值时所采用的方法即为C4.5采用的方法，这种方法是现在公认的处理连续值与缺失值简单且有效的方法。在剪枝方面，传统的预剪枝使得很多分支都没有完全进行展开，而某分支虽然有可能暂时使泛化性能下降，但在此节点的叶节点上的后续展开可能在一定程度上提高泛化性能，预剪枝在解决“过拟合”问题的时候使决策树带来了“欠拟合”的风险；传统后剪枝它先生成完整的决策树，再逐个节点检验其对精度的影响，虽然有较好的泛化性能，但需要对已生成的决策树自底向下逐个节点进行测试，这需要花费大量额外的时间。

剪枝方法和程度对决策树泛化性能的影响相当显著，实验已表明，在数据带有一定的噪声时，通过剪枝甚至可以将决策树的泛化性能提高25%^[3]，而过度拟合在多数问题上会导致决策树的分类精度降低10%~25%^[4]，因此，设计一个能在一定程度上解决传统剪枝算法的缺点的可靠的剪枝算法对决策树的研究来说十分重要。

1.2 国外研究现状

决策树算法最初是由心理学家兼计算机科学家E.B.Hunt在1962年所提出的Concept Learning System（简称CLS），这个算法确立了一种 “分而治之”的原则和策略，对后来的决策树的产生起到了奠基的重要作用。澳大利亚计算机科学家罗斯.昆兰在1978年对此算法进行了较大的改进，引入了信息增益准则并在1979年提出了ID3算法，后来，昆兰又在ID3的基础上提出了重要的C4.5算法，这种算法解决了原先算法不能处理连续值和缺失值的问题^[5]，其中的很多方法一直使用至今，其中的连续值处理方法和缺失值处理方法是现在公认的较好的方法。

在1987年，昆兰提出了REP(Reduced Error Pruning)后剪枝方法，它将每一个节点都作为候选的剪枝对象，对于树的每一个子树，使它成为叶子节点，生成一颗新树，重复此过程，直到决策树中任意一个子树成为了叶节点而不降低准确性，这样则说明剪枝完成 ^[6]。后来，为了克服该方法需要独立剪枝数据集的问题，他又提出了一种叫做PEP的剪枝方法(Pessimistic Error Pruning)^[6],并对误差估计增加了连续性校正,对每个子树的错误率做出了比较合理的估计，被认为是后剪枝算法中较好的一种方法。

Niblett提出了MEP剪枝方法，利用误差的期望概率来进行剪枝，这种算法的优点是并不需要一个额外的数据集合来作为剪枝时的验证集。后来，人们提出了CART(Classification and Regression Trees)算法，这种算法是在MEP算法的基础上加以优化的一种后剪枝算法，通过对树的评价来选择一个最优秀的树作为最终的决策树。

Rostogi提出了一种PUBLIC算法^[7]，它可以将树的建立与剪枝结合在一起，在决策树的建立阶段估计一个节点在以后的过程中是否会被删除，对有可能被删除的节点不进行本应当进行的扩展，这种方法提高了效率，避免了计算机运行时的空间的浪费。

在2001年，Boonsren Kijsirikul将神经网络运用到决策树的剪枝过程中去，将传统的决策树转换为神经网络，使用反向传播算法进行训练^[5][8]，在某些领域起到了突出的作用。

剪枝算法是多种多样的，数学家和计算机科学家都在努力寻找一些更为简单准确的方法，Mingers通过大量的实验对几种较为常见的剪枝方法进行了比较^[3]，他认为随着规模和领域的变化，不同的剪枝算法所能提供的作用也各不相同，目前没有方法能够在不同的情况下表现都超越其他的方法，即目前还没有一种最优的方法。

1.3国内研究现状

刘小虎和李生在1998年提出了一种决策树优化算法^[9]，在选择一个当前最优属性作为当前的节点进行划分时，我们除了要考虑该节点所能引起的信息增益，还要考虑在选择这一属性作为节点后，对此节点的后续划分所带来的信息增益，若第一次划分无法提高泛化性能而第二次划分最终能提高泛化性能，我们依然对此节点进行划分；这种方法比较复杂，在构造决策树时会大大降低构造的速度，但所构造的决策树有较高的准确性，可以较好的解决“过拟合”和“欠拟合”问题，降低了决策树算法中剪枝所占的比重，因而具有较高的实用性。

洪家荣等人在选择最优属性来构建决策树时，充分考虑到了传统增益率的作用，因此他们除了采用了传统的增益率，还在增益率的基础上使用了属性聚类的方法来减少决策树的分支的数量^[10]，这一方法大大降低了决策树的复杂度，减少了剪枝的必要性与进行剪枝时所需的计算量与复杂度

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

相关图片展示：