资源描述：
《一种基于改进sliq决策树分类算法的应用研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、http://www.paper.edu.cn1一种基于改进SLIQ决策树分类算法的应用研究林和平，张雪峰东北师范大学计算机学院，长春(130117）E-mail：nenulhp@163.com摘要：在数据挖掘的分类问题中，决策树已经被认为是非常有效的一种方法，本文提出了一种改进的SLIQ(Mehtaet.al,1996)决策树分类算法，克服了原有SLIQ算法需要大量计算决策树每个节点的吉尼指数（giniindex）的缺点。为了获得决策树中每个节点的最佳分裂属性，原有SLIQ算法不得不计算所有属性的所有属性值的吉尼指数。改进的SLIQ算法能够有效地减少计算的复杂度，且算法不需要将所有属性的所
2、有属性值的吉尼指数全部计算，而是通过计算不同范围内的属性值就可以达到同样的效果。本文结合实际生活中的实例，将该算法与原有SLIQ算法和基于人工神经网络的分类算法应用结果比较，实验结果表明该算法的分类准确率远远高于SLIQ算法和基于人工神经网络的分类算法。关键词：数据挖掘；决策树；SLIQ算法中图分类号：TP301.6文献标识码：A0.引言[10]数据分类是数据挖掘的重要问题之一，在分类问题中有许多的解决方法，例如基于决策树的算法和基于人工神经网络的算法。分类与回归树（ClassificationAndRegression[2]Tree,CART）是一种产生二叉决策树的流行技术，分裂是围绕如何
3、确定最佳分裂点进行的，在每一步，通过穷尽搜索来确定最佳分裂。m公式：Φ(s/t)=2ΡLΡR∑
4、Ρ(Cj
5、tL)−Ρ(Cj
6、tR)
7、（1）j=1这个公式是用来评价当前接点t和每个可能分裂属性和标准s。其中L和R是指树中当前节点的左子树和右子树。Ρ和Ρ分别指在训练集中的一个元组在树的左边和右边的LR概率，Ρ(C
8、t)和Ρ(C
9、t)分别指在左子树和右子树中的一个元组属于类别C的概率。jLjRj即使对于训练数据得到的树是最好的，但对于将来所有可能加入的数据则未必是最好。基[4]于信息论构建决策树的ID3算法主要是选择具有最高信息增益的属性作为分裂属性，决[5]策树算法C4.5在几个方面上改进了ID
10、3算法。s熵公式：H{P1,P2Λ,Ps}=∑(Pilog(1/pi))（2）i=1s其中给定概率P1,P2Λ,Ps，且∑Pi=1；i=1s信息增益公式：Gain{D,S}=H(D)−∑P(Di)H(Di)（3）i=1其中给定一个数据库状态D，S个新状态S={D,DΛ,D}；12s[6]ID3算法的主要缺点之一就是偏袒具有较多值的属性，因而可能导致过拟和。在极端的情况下，如果某个属性对于训练集中的每个元组都有唯一的一个值，则认为该属性是1本课题得到国家自然科学基金（应对规划研究，项目编号：60473042）的资助。-1-http://www.paper.edu.cn最好的，这是因为对于每个划
11、分都只有一个元组。决策树算法C4.5通过利用增益比率来代替信息增益，可以弥补当一个子集的规模与初始集合的规模很相近时增益比率非常大这种[1]Gain(D,S)情况的。增益比率公式：GainRatio{D,S}==（4）
12、D
13、
14、D
15、
16、D
17、12SH(,,Λ,)DDD[8]在SLIQ（SupervisedLearningInQuest,SLIQ）算法中,使用Gini指数代替增益比率,选择具有最低Gini指数的值进行分裂，Gini指数比增益比率性能更好,且计算方便。对于数据2库D,gini{D}=1−∑Pj（5）,其中Pj是类别Cj在数据库D中出现的频率。Gini指数最大的特点是计算时只需考虑类值在
18、被划分时每一部分的分布情况。ID3算法不能够充分处[7]理缺失数据和噪音数据，SLIQ算法能够弥补ID3算法存在的这些不足。在SLIQ算法中，产生决策树中的每个节点时需要计算任一属性，本文旨在提出一种基于SLIQ算法的一种改进的决策数分类算法，改进的SLIQ算法能够有效地减少计算的复杂性，且算法不需要将所有属性的所有属性值的Gini指数全部计算出来，而是通过计算不同范围内的属性值就可以达到同样的效果，而且算法的分类准确率远远高于SLIQ算法和基于人工神经网络的分类算法。1.分析SLIQ决策树算法[3]SLIQ算法的最重要思想是在决策树的构造过程中采用了“预排序”和“广度优先”两[11]种技术
19、：1)预排序。对于连续属性来说,在每个内部结点寻找其最优分裂标准的时候,都需要对训练集按照该属性的取值进行排序,而排序是个很浪费时间的操作。为此SLIQ算法采用了预排序的技术,以便能够消除在决策树的每个结点对数据集进行排序的操作。所谓预排序,就是针对每个属性的取值,把所有的记录按照从小到大的顺序进行排序。具体实现时,需要为训练集数据的每个属性创建一个属性列表，为每个元组的类别创建一个类别列表。算法实现时需要有
