决策树分类器,是一种基于实例的分类算法,广泛被应用于人工智能领域。ID3算法是最为经典的决策树建树算法,它通过递归和逐次挑选信息量最多的属性来构造决策树。决策树的结构有时非常庞大和复杂,而决策树分类图看起来非常直观,并且可以从建树的原始数据集中挖掘出一些关键的信息,因此决策树图的绘制是非常必要的。本研究从分子生物学领域中的基因分型决策树绘制为实例,浅谈如何使用MALAB语言编译生成AUTOLISP代码,从而实现可变ID3基因分型决策树分类图的绘制。
决策树分类器(decision tree classifier, DTC),简称决策树,是一种基于实例的归纳分类算法。它专注于从一些松散、零乱的事例中概括出树形式的分类规则。它选用从上到下的递归方法,在决策树的中间节点同其属性值进行比较, 并根据对应的属性值选择向下的分支, 最终在决策树的末端(叶节点)得到分类结论。由于每项决策都可能延伸出两个以上的选项,引出不同的推论,其外形类似树的枝干,故命名为决策树。决策树是使用最广泛的非参数分类方法,其基本思想是将一个复杂的决策分解成若干个简单的决策。相对其他人工智能算法,决策树有以下特点:决策树拥有最直观的知识表达,易于被人们理解和接受;决策树采用非参数方式,不需要使用者干预,非常适用于知识发现;决策树算法能够进行自我调整,当训练数据样本量突增后分类性能不会大幅度下降。目前,决策树分类器以其出色的分类性能,已广泛应用于人工智能领域,如数据挖掘、模式识别和图像分析等。
1.1. 决策树学习算法 决策树诞生于1966 年Hunt 等人提出的CLS 学习算法[1],它是早期的决策树学习算法。Quinlian 于1979 提出处理离散取值的ID3 算法,和于1993 提出离散和连续取值均可处理的C4.5 算法,以及上世纪八十年代初提出的基于二叉树的快速算法C5.0 算法标志着决策树走向成熟[2]-[6]。下面我们以算法明确和学习能力强的ID3 算法为例,看决策树是如何实现分类的。
ID3 算法: Procedure ID3 (Node n, Instances X, Feature f) 1) Best entropy = 1 2) for each feature f i in f 3) Calculation its conditional entropy H(X/f i) 4) if H(X/f i) < Best entropy 5) Best entropy= H(X/f i) 6) Best feature= f i