文档介绍：数据分类是数据挖掘中的一种分析方法,通过学****训练集构造一个分类函数或分类模型,该函数或模型能够把数据记录映射到给定类别中的某一个,从而可以应用于数据预测。训练集由一组数据库记录构成,记录形式可以表示为(V 1,V 2,?,V n ),其中, CV i表示样本的属性值,表示类 C 别。分类模型的构造方法包括统计方法(如贝叶斯方法)、机器学****方法(如决策树方法)、神经网络方法、粗集方法和遗传算法等。本文阐述了各种决策树分类算法的基本思想包括、,ID3 、、、和,通过分析比较, 总结了各种算法的主要特性,为国内研究者提供借鉴。决策树分类算法 1 算法 ID3 早期决策树算法是年由提出的算法 1986QuilanID3 [1],它是一个从上到下、分而治之的归纳过程。算法选择具有 ID3 最高信息增益的属性作为测试属性。定义1 :设样本集按离散属性的个不同的取值,划 TAs 分为T 1,?,T S共个子集,则用进行划分的信息增益为: sTA ) inf( | | | | ) inf( ) , ( 1 i s i i T T T T T A gain × ?= ∑= ) inf(T ,其中表示的信息 T ∑= × ?= m j j j p p T 1 2 ) ( log ) inf( p 熵。设中有个类,则,其中, Tm 表示中包含类的概率。 Tj 算法思想描述如下: ID3初始化决策树为只含一个树根,其中是全体样本 (1) T(X,Q)X 集,为全体属性集。 Q 中所有叶节点’’都满足属于同一类或’为空(2) if(T(X,Q)XQ) 算法停止; then (3) else 任取一个不具有中所述状态的叶节点’’; { (2)(X,Q) ’中的属性计算信息增益’; (4) for each QA do gain(A, X) 选择具有最高信息增益的属性作为节点’’的测试(5) B(X, Q) 属性; 的取值(6) for each Bb do 从该节点’’伸出分支,代表测试输出{(X, Q)B=b ; 求得中值等于 X B b 的子集 X 并生成相应的叶节点, (X ’’, Q- ; {B})} 转; (7) (2)} 算法 ID3, [1] 数据。对此,算法 [2]作了两点改进。算法挑选具有 最高信息增益率的属性作为测试属性。定义2 :设样本集按离散属性的个不同的取值,划 TAs 分为T 1,?,T S共个子集,则用对进行划分的信息增益率 sAT ) , ( ) , ( ) , ( T A split T A gain T A ratio = 为,其中∑= × ?= s i i i T T T T T A split 1 2 )| | | |( log | | | | ) , ( 。算法不仅可以处理离散属性方法与中相同, (ID3) 还可以处理连续属性。它规定在连续属性上的测试导致两 A 个分支分别对应于条件≤和>,其中称作局部阈,AVAVV 值。若是测试属性,则称作阈值。要确定的局部阈 AVA 值,首先对中属性值已知的样本进行快速排序,依次考 TA 察排序后的每对相邻值的中间值,以及对应的划分条件