基于数据流的决策树的探讨

《基于数据流的决策树的探讨》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、中山大学硕士学位论文1．2本文选取决策树作为研究重点的意义本文选取决策树作为研究方向，并尝试对数据流分类进行探讨，基于以下原因：1．决策树的研究历史悠久，早于20世纪60年代，Hunt等人建立学习系统CLS(ConceptLearningSystem)，一直发展到现在，研究成果丰富，但是决策树算法具有很强的针对性，常常针对具体领域具体问题调整模型及其参数，使得决策树的准确分类率不断调高，不断涌现出新的决策树算法。所以本文结合数据流的具体数据类型，尝试提出较好的决策树算法来提高准确分类率，缩短构造树的时间，应用于概率分布变化的数据源中。2．决策树与其它算法相比有其优势。与神经网络相

2、比，神经网络，虽然反复调整每个神经元的权重值，提高准确率，而且能增量学习，但是训练时间较长，特别对于大量数据。决策树的准确率一般比神经网络差，但是它采用贪心算法，不回溯，构建时间远远低于神经网络。与最近邻算法相比，决策树类似于最近邻，它的叶子代表任何样本的K个最近邻，每个相邻点(从属性的角度来看)的类标个数来决定叶子的类别，也就是根据样本概率估计作出决策。与规则归纳相比，决策树能产生一个最有效的最小规则集，如果属性有重叠，则选择最好的那个，但是规则归纳只把它们都表示出来。3．数据流是当前研究热点，也是很大的需求，有着很高的价值意义。这种数据最早出现在银行和证券领域，如今也出现在地

3、质测量、气象、天文观测等方面。特别是互联网和无线通信网，产生了大量的数据流类型的数据。数据流不同与数据仓库，它是实时产生，一般不被存储，而且不一定服从同一分布，这样大量的数据蕴含着当前实际的信息，所以要求敏捷地处理，尽量短时间内挖掘出其中的有用信息。正好决策树的速度快，精度高，生成模式简单，能满足数据流的特点。2中山大学硕士学位论文1．3本文的工作本文介绍了决策树的经典算法，基于内存的ID3系列(ID3Ⅲ，ID4嘲，ID5R嘲，C4．5‘41)，基于磁盘(数据库)的SLIQ嘲，SPRINT嘲，CLOUDS忉算法，基于数据流的VFDT系列(VFDT‘引，CVFDT嘲，CFD％㈨，f

4、VFDT‘¨1)。在此基础上，本文形成了对决策树改进的研究角度：1．如何更好地计算对节点不纯度，来分裂节点生成子树；2．对节点如何进行操作(分裂和合并)，是增量学习还是非增量学习；3．对时间复杂度和空间复杂度的考虑，如何扫描数据，加快构造决策树的速度。现实生活上，企业对处理数据的量方面提出了更高的要求，要能高效地处理像流水一样的无穷无尽的数据。本文根据这些研究角度和需求，提出了从值域角度来离散化连续型属性的值域区间法，并在值域区间法的基础上，实现了对数据流模型进行分类的决策树算法一基于值域区间的增量学习决策树算法RangeIntervalDecisiontreE(RIDE)，主要

5、创新之处有：●提出的值域区间法，是从值域的角度抽取样本点，来对连续型属性进行离散化，计算样本点的gini值，来对不纯度进行估计。由于在海量数据中，不可能(时间和空间上不能实现)也不必要(统计学提供一定数量样本能代表整个样本空间的依据)对所有可能的分裂值计算gini值；值域区间采用计算极可能是最小gini值，或与最小gini值相差不大的个别分裂点，来替代对所有分裂点计算；◆能根据数据的变化而对个别节点进行修改，以提高分类准确率。虽然用生长节点的方法能暂时解决准确率问题，但是会令决策树不断庞大，所以RIDE算法对节点的修改，首先会尝试合并节点，再使用生长方式，努力控制决策树的规模；·

6、由于数据量是无穷的，所以尽可能采用一次扫描实例，提取实例中的类别信息，不对实例进行保存，包括硬盘上的存储。但是由于需要把历史数据的类别信息传递给子节点，RIDE采用最近样本集来代表整个空间的类别比例分布。3中山大学硕士学位论文1．4论文结构本文介绍了决策树的经典算法，并在此基础上改进VFDT算法，并用UCI数据集对值域区间法进行验证，和采用类似【9】的超平面法生成数据流来测试RIDE算法。文章余下部分是这样安排的：第二章：系统介绍基于内存的和基于磁盘的决策树经典算法。第三章，简介基于数据流的决策树VFDT系列算法。第四章，介绍本文提出的值域区间法，给出了实验结果。第五章，介绍RI

7、DE决策树算法，给出了实验结果。第六章，总结全文，并提出进一步工作的一些想法。4中山大学硕士学位论文第二章经典决策树算法简介2．1什么是决策树决策树(decisiontree)是一种树形结构的分类器。它是有向树，有且仅有一个根节点(树根)，从树根指向第一层树分支点(或树叶)，第一层树分支点指向第二层树分支点(或树叶)，直到最底层全部为树叶。这里的树叶代表一个分类的类别，树分支点代表一个实例的属性，树分支点与树分支点或树叶之间的连接代表一个判断条件。如图2-1是一棵根据天气情况决定