基于决策树的数据挖掘-汽车评价分类的算法设计与实现

1、基于决策树的数据挖掘汽车评价分类的算法设计与实现1 决策树技术面临的挑战及目前研究方向随着数据挖掘技术的兴起， 作为拟人决策主要方法之一， 近年来决策树又重新引起了人 们的兴趣，并得到更广泛的应用。目前决策树技术的主要研究方向有以下几点：1.1 决策树技术与其他技术的结合如何将决策树技术和其他新兴的技术相结合以便取长补短一直是决策树技术研究的热 点，近几年来国际上发表的有关决策树的文章也大多集中在这个方面的研究。 近年关于决策 树和其他技术的研究主要包括：1.1.1 决策树技术和神经网络技术相结合 12 。人工神经网络的多层结构使它具有对任意输入输出进行映射的功能。同样， 决策树也具有产生 维

2、空间下任意复杂的决策边界的功能。因此，可以将决策树重新构造成一个多层的 神经网络。 这种由决策树转化而成的神经网络具有加快神经网络训练速度等优点。 另外一类 方法正好相反， 它研究的是由神经网络中得到所需要的决策树。 这类方法解决了由神经网络 得到的知识难于被人们理解的缺点。1.1.2 决策树技术和模糊集合原理的结合决策树技术虽然有许多优点，但也存在着不稳定的缺点，即决策树带来了较大的变动。 模糊集合的融通性使人们利用模糊逻辑来解决决策树的这一缺点并取得了不错的效果。最 近，C.OIaru提出了一种新的模糊决策树方法-软决策树。软决策树综合决策树的生成和修剪来决定其本身的结构，并利用重修( R

3、efitting )和磨合( Backfitting )来提高树的归纳能 力。 软决策树比一般决策 树的正确率要高。 此外， M. Dong 等人 提出的 基于前瞻 (Look-Ahead )的模糊决策树也能够在得到较好的归纳特性的前提下产生较小体积的决策 树4。1.1.3 决策树技术和进化算法，遗传算法及遗传编程的结合 56789 。基于进化算法的决策树系统具有较好的抗噪声能力， 同时进化算法很容易在并行计算机 上运行， 因此可以期待基于进化算法的决策树的运算能力有较大的提高。此外， 由于进化算法为随机算法， 它可以在任何时候对同一数据集合产生不同的决策树，通过利用投票 (Vote)的方法可

4、以得到理想的分类器。 因为总体分类器比单个分类器的错误率低， 所以基于进化算 法的决策树在减小错误率方面也有优势。 同样，将决策树运用于进化计算也能够提高进化算 法的性能。 例如， 利用决策树为进化算法播种具有较好质量的初始种群能提高进化算法的搜 索能力并缩短运行时间。将遗传算法用于分类和概念学习任务比较常见， 但真正将它作为一种发展决策树的实用 工具的研究还比较少。 A. PapageIis 等将遗传算法直接用于产生决策树。与一般遗传算法 采用二进制串的形式不同， 他们采用了二进制树结构来进行问题表示。 当无关属性或比较强 的条件相关属性存在时，遗传算法比其他的贪婪启发方式( Greedy

5、Heuristics )具有优势。 D. R. CarvaIho 提出了一个混合决策树和遗传算法的算法， 一定程度地解决了低训练数据易 于产生错误的规则的缺点。 需要注意的是， 遗传算法和决策树结合的缺点是计算量较大。 将 遗传编程用于决策树可以改进标准贪婪决策树归纳算法的一些局限性。遗传编程种群中的每个个体都可以是一个决策树。 遗传编程中使用的函数是决策树的特性以及遗传编程中的终结 集(Terminal Set )。利用遗传编程构造决策树可以取得比较好的效果，特别是发现小数据 量下的最优决策树。1.1.4 决策树技术和多智能体的结合 将决策树用于多智能体控制并不多见。 但正由于多智能体系统的

6、复杂性， 而机器学习有 潜力提供一个鲁棒性较强的机制来有效协调各智能体间的行为，因此对多智能体结合机器学习是一个很有前途的方向。近几年P. Stone 和 M. Veloso 发表了一些这方面的文章10 1112 。他们提出了基于决策树 C4.5 算法中置信度( Confidence Factor )下的多智能体 控制，并将此应用于机器人足球控制。1.2 寻找新的构造决策树的方法自从 Quinlan 提出 ID3 和 C4.5 方法后，有不少专家提出了其他构造决策树的方法， 如由 Brieman 等人提出的 CART 方法和由 Kass 提出的 CHAID 方法。最近， M. Ankerst

7、等提出了基于多维可视化下的交互式的决策树构造 13。此方法在决策树构造阶段加入了专 家知识， 这样便于用户更深地理解产生决策树的数据及最终产生的决策树。同时此方法也显著地减小了决策树的大小。在 M. Ankerst 等提出的方法中，他们主要用两类进化算法替代 了传统的贪婪搜索算法以实现数值属性的任意分割。1.3 寻找更好的简化决策树的方法简化决策树的研究工作主要有两个方面， 一是对比各种不同的简化决策树方法， 分析它 们各自的特性、 优点和缺点。 另外一个就是寻找更好的与传统方法不同的简化决策树的方法， 这一直是决策树技术研究的一个热点。 近年来， 针对不同的应用领域并且随着其他新技术的 加入

8、，陆续有这方面的文章发表。例如， D. Founrnier 等提出的一种新的修剪决策树的方法 -DI 修剪法 14。此方法针对数据不确定的情况，利用特性索引(Quality Index )来权衡处理决策树深度和节点杂质。 DI- 修剪法将保持那些虽不能减小错误率但能指出一些特殊性质的 群体的子树。 D. Founrnier 等认为这对于研究不确定数据是非常关键的。1.4 研究产生决策树的训练和检验数据的大小及特性与决策树特性之间的关系与上述简化决策树不同， 这类研究着眼于产生决策树的数据。 训练数据的增加经常造成 决策树大小的线性增加， 而这种增加并没有都带来决策树准确性的提高。一些专家认为，

9、 在产生决策树前尽量减少数据量比在决策树产生后再简化决策树更加有效。实际上， 这就是经常提起的数据预处理技术( Data Preprocessing )，与决策树修剪技术( Pruning )相对应， 也称它为数据减少技术 ( Data Reduction Techniques )。近几年，有关这方面的研究取得 了一些进展 151617 。1.5 不确定环境下决策树研究不确定环境下的决策研究一直是一个热点，决策树技术就是其中一个重要的方法之一。前面介绍的决策树技术与模糊集合原理的结合就是一个不错的选择。此外，Z. Eloudi 等人提出了一种基于置信度函数的决策树 18。此算法利用置信度函数原

10、理来代表分类问题中的 参数不确定性，在不确定环境下决策树构造和不确定环境下的分类均取得了比较好的效果。 目前正在进行决策树与专家系统相结合的研究，以便在不确定环境下更好地决策。1.6 决策树技术中时间复杂度与准确性之间的矛盾决策树技术与神经网络技术相比所具有的最大优点就是训练决策树的时间远远低于训 练神经网络的时间。 决策树技术中如何处理时间复杂度和分类准确性之间的矛盾是一个令人 感兴趣的问题。到底如何取舍需要具体问题具体分析。例如，0.Taner 等人提出的全变量决策树 ( 0mnivariate Decision Tree ) 19。在分类正确性方面超过了其他决策树方法，却付 出了需要更多

11、训练时间的代价。 随着微处理器速度越来越快、 价钱越来越便宜， 以及并行计 算的运用，使人们在做决定时拥有比以前更大的自由。1.7 决策树技术的软件实现将决策树技术软件化一直是决策树技术的方向之一。目前市场上的大多数据挖掘软件如SAS等都包含有决策树技术部分。如何开发出功能更加强大、使用更加方便、界面更加友 好的软件以实现决策树技术，一直是大家努力的方向。以上这些决策树的研究并不是孤立的，它们经常相互联系、相互结合。2决策树算法实例在汽车评价分类的数据库中给汽车定义了6个属性：（1）购买价格buying，该属性取值有 4种，分别为vhigh、high、med和low（2）保养维护费用 main

12、t，该属性取值有 4种，分别为vhigh、high、med和low（3）车门数量doors，该属性取值有 4种，分别为2、3、4和5more（4）载人数量persons，该属性取值有 3种，分别为2、4和more（5）行李箱容量lug_boot，该属性取值有 3种，分别为small、med和big（6）安全性safety，该属性取值有 4种，分别为low、med和high本文采用了完整涵盖 6个属性所有1728（4*4*4*3*3*4 ）种取值组合的数据库，根据每 辆汽车各个属性的取值组合，消费者对汽车给出4种评价，分别为unacc、acc、good和vgood。数据库来源：http:/arc

13、/ml/datasets/Car+Evaluation2.1 CLS算法逻辑与实现用CLS算法生成决策树首先要确定6个属性的先后顺序，即决策树每层需要对哪种属性进行取值分类和判断。如下图所示，程序使用者在运行算法之前可以在下拉列表中选择决 策树前2层的属性，其余 4种属性将按照数据库中从左至右的默认顺序依次作为决策树之 后4层的属性。Ch 000 thv first attributm：| pmr.en寸”And th second attribute: safely下图即为选择persons和safety作为前2层属性时6个属性的排列顺序：Attribute/

14、Resutt NamepersonssafetybuyingmaintdoorsIug b0atColumn No.572346Count of Values334443Values2lowvhighvhigh2small4medhighhigh3medmorehighmedmed4biglowlow5more附录1的代码为生成决策树的主要过程，首先将所有汽车按照第1层属性的取值进行分类，例如按上图顺序按 persons分为3类（2、4和more ）。然后依次进行判断每类汽车 的消费者评价是否一致，若一致则在该类下生成叶子结点，例如persons取值为2的汽车均被评价为unacc，于是生成如下

15、图所示的叶子结点：若该类汽车的消费者评价不一致，则进入决策树第2层的生成过程，将该类汽车按照第2层属性的取值继续细分，例如 persons取值为4的汽车没有一致的消费者评价，于是 按safety继续细分为3类（low、med和high ）依次进行判断，如下图所示：persons4safetylowmedhigh根据这种方法层层推进，最终即可生成完整的决策树，而每层的生成方法和逻辑与附录 1的代码相似，因此不一一叙述。2.2 ID3算法逻辑与实现用ID3算法生成决策树不需要事先确定 6个属性的先后顺序，而是由附录 3的代码在 生成新结点是计算每种属性的信息熵并选择这个结点的属性，选择结点属性之后

16、和CLS算法一样进行该属性不同取值的分类和判断。附录2的代码为生成决策树的主要过程，首先计算各属性的信息熵并选择第1层的属性，例如在汽车评价案例中经过计算选择safety为第1层属性，如下图所示：然后按safety分为3类（low、med和high），依次进行判断每类汽车的消费者评价是否一致，若一致则在该类下生成叶子结点，例如safety取值为low的汽车均被评价为 unacc，于是生成如下图所示的叶子结点：若该类汽车的消费者评价不一致，则进入决策树第2层的生成过程，按该类汽车计算各属性的信息熵并选择结点属性，根据不同取值继续细分并判断，例如safety取值为med的汽车没有一致的消费者评价，

17、于是计算并选取persons作为结点属性，继续细分为3类（2、4和more ）依次进行判断，如下图所示：safelymedpersons24more根据这种方法层层推进，最终即可生成完整的决策树，而每层的生成方法和逻辑与附录 1的代码相似，因此不一一叙述。与CLS算法规定了每层的结点属性不同，在 ID3算法中对每个新的结点都需要计算各 属性的信息熵来选择属性，所以某个结点按属性的取值分类后， 下一层的几个结点未必采用 相同的属性，例如下图中第 4层的4个结点并没有选择同样的属性。safetymedpersons4buyingvhighmaimhigh lug bt>otmedmaintl

18、owrnaint2.3 CLS算法与ID3算法效果比较CLS算法的效果根据属性顺序的不同会有很大的差异，下表即为根据不同属性顺序生 成决策树的叶子结点数：属性顺序叶子结点数safety Tpersons t buying t maintT doors t lug boot469persons t safety t buying t maintT doors t lug boot469buying t maint t doors t persons t lug boot t safety965lug boot t maintT buying t doorsT persons t safety10

19、75doors t lug boot t buying TmaintT persons t safety1102可以看到属性顺序对于效果的影响十分巨大，通过改变顺序叶子结点数的变化可能超过1倍。经过多次测试，用CLS算法生成汽车评价决策树的最少叶子结点数为469个，而ID3算法生成的决策树只有296个叶子结点。由于ID3算法选取结点属性的方法更加灵活、合理，从直观上判断会比 CLS算法效果更佳，所以这样的结果差异也在情理之中。3总结本文实例是用 VBA语言编程，界面为 Excel 2003 （具体见电子版），语言和界面不够 专业，所以实现速度也没有达到最理想，最快的42 ''最

20、慢的4 '以上。进一步工作会在编程语言上改进，以实现最佳效果。附录 附录 1 CLS 算法生成决策树的过程Private Function DECISIONTREE(LAYER_COUNT As Integer, ROW_COUNT As Integer)Dim LAYER_RANGE As Range, TREE_RANGE As Range, RANGE2 As Range, ROW2 As Integer, I As Integer, J As Integer, K As Integer, X As IntegerDim VALUE1 As String, COLUMN1 As

21、Integer, CLASS As String, CLASS_COLUMN As Integer, DECISION As String Set LAYER_RANGE = Range("K5")CLASS_COLUMN = LAYER_COUNT + 2Set TREE_RANGE = Range("K16")TREE_RANGE.Cells(1, 1) = LAYER_RANGE.Cells(1, 1)BORDER_THIN (TREE_RANGE.Cells(1, 1)COLUMN1 = LAYER_RANGE.Cells(2, 1)ROW2 =

22、 -1For I = 1 To LAYER_RANGE.Cells(3, 1)VALUE1 = LAYER_RANGE.Cells(3 + I, 1)K = 0For J = 2 To ROW_COUNTIf Cells(J, COLUMN1) = VALUE1 ThenCLASS = Cells(J, CLASS_COLUMN)K = J Exit ForEnd IfNextX = 1For J = K To ROW_COUNTIf Cells(J, COLUMN1) = VALUE1 And Not Cells(J, CLASS_COLUMN) = CLASS ThenX = 0 Exit

23、 ForEnd IfNextIf X = 1 ThenROW2 = ROW2 + 2TREE_RANGE.Cells(ROW2, 2) = VALUE1 TREE_RANGE.Cells(ROW2, 3) = CLASSCall BORDER_MEDIUM(TREE_RANGE.Cells(ROW2, 3)Call CONECTION(TREE_RANGE.Cells(1, 1), TREE_RANGE.Cells(ROW2, 3)ElseIf X = 0 ThenROW2 = ROW2 + 2TREE_RANGE.Cells(ROW2, 2) = VALUE1TREE_RANGE.Cells

24、(ROW2, 3) = LAYER_RANGE.Cells(1, 2)Call BORDER_THIN(TREE_RANGE.Cells(ROW2, 3)Call CONECTION(TREE_RANGE.Cells(1, 1), TREE_RANGE.Cells(ROW2, 3)Set RANGE2 = TREE_RANGE.Cells(ROW2, 3)ROW2 = ROW2 - 1 + LAYER2(RANGE2, VALUE1, LAYER_RANGE, CLASS_COLUMN, ROW_COUNT) End IfNextRange("K13") = (ROW2 +

25、 1) / 2End Function附录 2 ID3 算法生成决策树的过程Private Function DECISIONTREE(ROW_COUNT As Integer)AsAsDim LAYER_RANGE As Range, TREE_RANGE As Range, RANGE2 As Range, ROW2 As Integer, COLUMN1 Integer, ATTRIBUTE1 As Integer, ATTRIBUTE2 As Integer, VALUE1 As String, CLASS As String, CLASS_COLUMN IntegerDim I As

26、 Integer, J As Integer, K As Integer, L As Integer, N As Integer, M As IntegerSet LAYER_RANGE = Range("K5")Set TREE_RANGE = Range("K16")CLASS_COLUMN = 8M = LAYER_RANGE.Cells(3, 7)ATTRIBUTE1 = CHOOSE_ATTRIBUTE(7, CLASS_COLUMN, ROW_COUNT, M, LAYER_RANGE)LAYER_RANGE.Cells(8, ATTRIBU

27、TE1) = 1TREE_RANGE.Cells(1, 1) = LAYER_RANGE.Cells(1, ATTRIBUTE1)BORDER_THIN (TREE_RANGE.Cells(1, 1)COLUMN1 = LAYER_RANGE.Cells(2, ATTRIBUTE1)ROW2 = -1For I = 1 To LAYER_RANGE.Cells(3, ATTRIBUTE1)VALUE1 = LAYER_RANGE.Cells(3 + I, ATTRIBUTE1)K = 0For J = 2 To ROW_COUNTIf Cells(J, COLUMN1) = VALUE1 Th

28、enCLASS = Cells(J, CLASS_COLUMN)K = JREF.Cells(J, ATTRIBUTE1) = 1ElseREF.Cells(J, ATTRIBUTE1) = 0End IfNextX = 1For J = 2 To ROW_COUNTIf Cells(J, COLUMN1) = VALUE1 And Not Cells(J, CLASS_COLUMN) = CLASS ThenX = 0 Exit ForEnd IfNextIf X = 1 ThenROW2 = ROW2 + 2TREE_RANGE.Cells(ROW2, 2) = VALUE1TREE_RA

29、NGE.Cells(ROW2, 3) = CLASSCall BORDER_MEDIUM(TREE_RANGE.Cells(ROW2, 3)Call CONECTION(TREE_RANGE.Cells(1, 1), TREE_RANGE.Cells(ROW2, 3)ElseIf X = 0 ThenROW2 = ROW2 + 2TREE_RANGE.Cells(ROW2, 2) = VALUE1M,ATTRIBUTE2 = CHOOSE_ATTRIBUTE(ATTRIBUTE1, CLASS_COLUMN, ROW_COUNT, LAYER_RANGE)TREE_RANGE.Cells(RO

30、W2, 3) = LAYER_RANGE.Cells(1, ATTRIBUTE2)Call BORDER_THIN(TREE_RANGE.Cells(ROW2, 3)Call CONECTION(TREE_RANGE.Cells(1, 1), TREE_RANGE.Cells(ROW2, 3)Set RANGE2 = TREE_RANGE.Cells(ROW2, 3)ROW2 = ROW2 - 1 + LAYER2(RANGE2, ATTRIBUTE1, ATTRIBUTE2, LAYER_RANGE, CLASS_COLUMN, ROW_COUNT, M)End IfNextLAYER_RA

31、NGE.Cells(8, ATTRIBUTE1) = EmptyRange("K13") = (ROW2 + 1) / 2End Function附录 3 ID3 算法计算信息熵和选择结点属性的过程Private Function ENTROPY_CALCULATION(ATT_NO As Integer, PREATT As Integer, CLASS_COLUMN As Integer, ROW_COUNT As Integer, M As Integer, LAYER_RANGE As Range) As DoubleDim ATT_C As Integer, PR

32、_ATT() As Double, COUNT_ATT As Integer, PR_CLA() As Double, COUNT_CLA As Integer, ENTROPY_CLA() As Double, TOTAL As Integer, RN As Integer, AN As Integer, CN As IntegerATT_C = LAYER_RANGE.Cells(3, ATT_NO)ENTROPY_CALCULATION = 0TOTAL = 0For RN = 2 To ROW_COUNTIf REF.Cells(RN, PREATT) = 1 ThenTOTAL =

33、TOTAL + 1End IfNextReDim PR_ATT(ATT_C) As DoubleFor AN = 1 To ATT_CCOUNT_ATT = 0ReDim Preserve ENTROPY_CLA(AN) As DoubleReDim PR_CLA(M) As DoubleENTROPY_CLA(AN) = 0For RN = 2 To ROW_COUNTIf REF.Cells(RN, PREATT) = 1 And Cells(RN, ATT_NO + 1) = LAYER_RANGE.Cells(3 + AN, ATT_NO) ThenCOUNT_ATT = COUNT_

34、ATT + 1 REF.Cells(RN, ATT_NO) = 1ElseREF.Cells(RN, ATT_NO) = 0End IfNextPR_ATT(AN) = COUNT_ATT / TOTALFor CN = 1 To MCOUNT_CLA = 0For RN = 2 To ROW_COUNTIf REF.Cells(RN, ATT_NO) = 1 And Cells(RN, CLASS_COLUMN) = LAYER_RANGE.Cells(3 + CN, 7)ThenCOUNT_CLA = COUNT_CLA + 1End IfNextPR_CLA(CN) = COUNT_CL

35、A / COUNT_ATTIf PR_CLA(CN) > 0 ThenENTROPY_CLA(AN) = ENTROPY_CLA(AN) - PR_CLA(CN) * Log(PR_CLA(CN) / Log(2)End IfNextENTROPY_CALCULATION = ENTROPY_CALCULATION + PR_ATT(AN) * ENTROPY_CLA(AN)NextEnd FunctionPrivate Function CHOOSE_ATTRIBUTE(PREATT As Integer, CLASS_COLUMN As Integer, ROW_COUNT As I

36、nteger,M As Integer, LAYER_RANGE As Range) As IntegerDim ENTROPY_ACC As Double, ENTROPY_TEMP As Double, ATT_NO As IntegerENTROPY_ACC = 2CHOOSE_ATTRIBUTE = 0For ATT_NO = 1 To 6If Not LAYER_RANGE(8, ATT_NO) = 1 ThenM,ENTROPY_TEMP = ENTROPY_CALCULATION(ATT_NO, PREATT, CLASS_COLUMN, ROW_COUNT, LAYER_RAN

37、GE)If ENTROPY_TEMP < ENTROPY_ACC ThenENTROPY_ACC = ENTROPY_TEMPCHOOSE_ATTRIBUTE = ATT_NOEnd IfEnd IfNextEnd Function参考文献：1 Boz O. Extracting decision trees from trained neural net-worksC. Edmonton, Alberta, Canada: Proc of the English ACM SIGKDD International Conference on Knowledge Discovery and

38、 Data Mining, 2002.2 Sethi L. Entropy nets: from decision trees to neural net-worksJ. Proc of IEEE,1990,78 (10) :1605-1613.3 Olaru C, Wehenkel L. A complete fuzzy decision tree techniqueJ. Fuzzy Sets and Systems,2003,138(2) :221-254.4 Dong M, Kothari R. Look-ahead based fuzzy decision tree induction

39、 J. IEEE Transactions on Fuzzy Systems, 2002, 9 (3) :461-468.5 Cantu -Paz E, Kamath C. Inducing oblique decision trees with evolutionary AlgorithmsJ . IEEE Transactions on Evolutionary Computation, 2003, 7 (1) : 54-68.6 Papagelis A, Kalles D. Breeding decision trees using evolutionary techniquesC. U

40、SA: Proceedings of ICML ' 01U,SA, 2001.7 Papagelis A, Kalles D. GA tree: genetically evolved decision treesC . USA: Proceedings of ICTAIP00,2000.8 Tur G, Guvenir H A. Decision tree induction using genetic programming C. Ankara, Turkish: Proceedings of the Fifth Turkish Symposium on Artificial In

41、telligence and Neural Networks,1996.9 Eggermont J. Evolving fuzzy decision trees with genetic programming and clusteringC. Milan, Italy: Proceedings of the 4th European Conference on Genetic Programming,2001.10 Stone P, VeIoso M. Using decision tree confidence factors for muItiagent control C . Minnesota, USA: Proceedings of the 2nd International Conference on Autonomous Agents, 1998.11 Stone P, VeIoso M. M