决策树技术分类

《决策树技术分类》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、决策树分类技术研究[摘要】决策树分类是一种重要的数据分类技术。该文通过对决策树分类方法的研究，进一步讨论了实际使用过程中决策树学习出现的常见问题的解决方法。为实际应用提供了依据。【关健词】决策树;分类1引言数据分类是数据挖掘中的一个重要问题，是一种有效的KDD分析方法。数据分类通过分析训练集中的数据，对类建立分类模型，然后利用这个分类模型，把数据库中的数据项映射到给定类别中。近年来，数据分类技术已被广泛、有效地应用于科学实验、医疗诊断、气象预报、信贷审核、商业预测等领域，引起了工业界和学术界的关注。依据其采用的分类模型，数据分类技术主要可分为:机器学习方法(如

2、决策树归纳)、统计方法(如贝叶斯分类和贝叶斯网络)、神经网络方法、遗传算法、粗糙集和模糊逻辑技术等。上述技术中，决策树技术是利用最广泛的分类技术。它有以下优点:首先，决策树方法结构简单，便于人们理解;其次，决策树模型效率高，对训练集数据量较大的情况较为适合;第三，决策树方法通常不需要受训数据外的知识;第四，决策树方法具有较高的分类精确度。同时决策树技术也有一些不足，如对于大型数据库的可伸缩性问题、对于非平衡数据进行分类时，剪枝会造成精确率的降低等。本文主要阐述了决策树分类的基本概念、算法以及实际使用中如何解决某些常见的问题，如:测试属性选择的度量标准、连续属性

3、的离散化处理、处理缺少属性值、树剪枝与避免过度拟合、分类法的准确率评估及提高和决策树的可伸缩性等。2决策树算法2.，决策树的构造方法决策树是一个类似于流程图的树结构，决策树通过把实例从根节点排列到某个叶子节点来分类实例，叶子节点即为实例所属的分类。树上的每一个节点说明了对实例的某个属性的测试，并且该节点的每一个后继分支对应于该属性的一个可能值。决策树构造的基本算法是贪心算法，它以自顶向下递规的方式构造判定树。算法的基本策略如下:1)树以代表训练样本的单个节点开始。2)如果样本都在同一个类，则该节点成为树叶，并用该类标记。3)否则，算法使用一种度量标准作为启发信

4、息，选择能够最好的将样本分类的属性，成为该节点的测试属性。4)对测试属性的每一个已知的值，创建一个分枝，并据此划分样本。5)算法使用同样的过程，递归的形成每个划分上的样本子决策树。当出现如下情况之一时，递归停止:(a)给定节点的所有样本属于同一类。(b)没有剩余的属性来进一步划分样本或者分枝中没有样本，这时使用多数表决，将给定的节点转换为树叶，并用父节点中多数类来标记它。2.2测试属性选择的度量标准J.RossQuinlan提出了ID31'%法。在此算法中采用信息论中的信息增益(informationgain)来衡量给定的属性区分训练样例的能力。其计算方法如下

5、:如果目标属性具有。个不同的值，那么数据样例集S相对于c个状态的分类的嫡定义为Entorpy⑤二艺Paog=pi;若A是S中的一个属性，Values(A)表示属性A所有可能的集合，S.是S中属性A的值为v的子集，即S,=IseSIA(s)=v)，则属性A相对于样例集合S的信息增益Gain(S,A)被定义为:Gain(S,A)=Entropy(S)一艺怜v.YY州人】iIsSddEntropy(S.)·这种方法使生成的树平均深度较小，从而有较快的分类速度。但是，信息增益度量存在一个内在偏置，它偏祖具有较多值的属性。在此基础上，Quinlan又于1993年对ID3

6、算法进行了补充和改进，提出了更先进的C4.5[2】算法，提出了信息增益率的属性度量方法。其定义如下:GainRatio(S,A卜Splulnformation(S,A)其中，Spiltlnformation(S,A)--i各骨log'A分裂信息(SplitWonnation)用来衡量属性分裂数据的广度和均匀性，避免了ID3算法所采用的信息增益倾向于选择取值较多的属性。Quinlan通过试验，对若干属性测试标准做了比较，发现信息增益率能得到更好的决策树，而且不易产生不平衡的划分。除了以上两种方法外，LopezdeMantaras在1991年提出了基于距离(dis

7、tance-based)的度量。这个度量标准定义了数据划分间的一种距离尺度。其效果接近信息增益率的度量效果，且避免了偏向有大量值的属性。此外，学者们还提出了Relief度量、J一度量,G统计、X2统计以及最小描述长度(MDL)等多种属性度量方法。对这些度量方法的研究和比较发现，没有一种度量方法在属性选择和处理噪声等问题中占有绝对的优势。因此，在实际构造决策树的过程中，要综合权衡效率和准确率等多种因素选择恰当的度量方法。2.3连续属性的离散化处理ID3算法被限制为只能取离散值的属性。为了消除这个限制，对于连续属性的离散化，我们可以采用信息增益率判别方法。具体的处

8、理分三步操作:1)实例排序首先，将该判