基于决策树的数据挖掘汽车评价分类的算法设计与实现.docx
《基于决策树的数据挖掘汽车评价分类的算法设计与实现.docx》由会员分享，可在线阅读，更多相关《基于决策树的数据挖掘汽车评价分类的算法设计与实现.docx（14页珍藏版）》请在冰点文库上搜索。
基于决策树的数据挖掘汽车评价分类的算法设计与实现
基于决策树的数据挖掘
汽车评价分类的算法设计与实现
1决策树技术面临的挑战及目前研究方向
随着数据挖掘技术的兴起，作为拟人决策主要方法之一，近年来决策树又重新引起了人们的兴趣，并得到更广泛的应用。
目前决策树技术的主要研究方向有以下几点：
1.1决策树技术与其他技术的结合
如何将决策树技术和其他新兴的技术相结合以便取长补短一直是决策树技术研究的热点，近几年来国际上发表的有关决策树的文章也大多集中在这个方面的研究。
近年关于决策树和其他技术的研究主要包括：
1.1.1决策树技术和神经网络技术相结合[1][2]。
人工神经网络的多层结构使它具有对任意输入输出进行映射的功能。
同样，决策树也具
有产生维空间下任意复杂的决策边界的功能。
因此，可以将决策树重新构造成一个多层的神经网络。
这种由决策树转化而成的神经网络具有加快神经网络训练速度等优点。
另外一类方法正好相反，它研究的是由神经网络中得到所需要的决策树。
这类方法解决了由神经网络得到的知识难于被人们理解的缺点。
1.1.2决策树技术和模糊集合原理的结合
决策树技术虽然有许多优点，但也存在着不稳定的缺点，即决策树带来了较大的变动。
模糊集合的融通性使人们利用模糊逻辑来解决决策树的这一缺点并取得了不错的效果。
最近，C.OIaru提出了一种新的模糊决策树方法-软决策树⑶。
软决策树综合决策树的生成和修
剪来决定其本身的结构，并利用重修（Refitting）和磨合（Backfitting）来提高树的归纳能力。
软决策树比一般决策树的正确率要高。
此外，M.Dong等人提出的基于前瞻（Look-Ahead）的模糊决策树也能够在得到较好的归纳特性的前提下产生较小体积的决策树[4]。
1.1.3决策树技术和进化算法，遗传算法及遗传编程的结合[5][6][7][8][9]。
基于进化算法的决策树系统具有较好的抗噪声能力，同时进化算法很容易在并行计算机上运行，因此可以期待基于进化算法的决策树的运算能力有较大的提高。
此外，由于进化算
法为随机算法，它可以在任何时候对同一数据集合产生不同的决策树，通过利用投票（Vote）
的方法可以得到理想的分类器。
因为总体分类器比单个分类器的错误率低，所以基于进化算法的决策树在减小错误率方面也有优势。
同样，将决策树运用于进化计算也能够提高进化算法的性能。
例如，利用决策树为进化算法播种具有较好质量的初始种群能提高进化算法的搜索能力并缩短运行时间。
将遗传算法用于分类和概念学习任务比较常见，但真正将它作为一种发展决策树的实用工具的研究还比较少。
A.PapageIis等将遗传算法直接用于产生决策树。
与一般遗传算法采用二进制串的形式不同，他们采用了二进制树结构来进行问题表示。
当无关属性或比较强的条件相关属性存在时，遗传算法比其他的贪婪启发方式（GreedyHeuristics）具有优势。
D.R.CarvaIho提出了一个混合决策树和遗传算法的算法，一定程度地解决了低训练数据易于产生错误的规则的缺点。
需要注意的是，遗传算法和决策树结合的缺点是计算量较大。
将遗传编程用于决策树可以改进标准贪婪决策树归纳算法的一些局限性。
遗传编程种群中的每
个个体都可以是一个决策树。
遗传编程中使用的函数是决策树的特性以及遗传编程中的终结集（TerminalSet）。
利用遗传编程构造决策树可以取得比较好的效果，特别是发现小数据量下的最优决策树。
1.1.4决策树技术和多智能体的结合将决策树用于多智能体控制并不多见。
但正由于多智能体系统的复杂性，而机器学习有潜力提供一个鲁棒性较强的机制来有效协调各智能体间的行为，因此对多智能体结合机器学
习是一个很有前途的方向。
近几年P.Stone和M.Veloso发表了一些这方面的文章
[10][11][12]。
他们提出了基于决策树C4.5算法中置信度（ConfidenceFactor）下的多智能体控制，并将此应用于机器人足球控制。
1.2寻找新的构造决策树的方法
自从Quinlan提出ID3和C4.5方法后，有不少专家提出了其他构造决策树的方法，如由Brieman等人提出的CART方法和由Kass提出的CHAID方法。
最近，M.Ankerst等提出了基于多维可视化下的交互式的决策树构造[13]。
此方法在决策树构造阶段加入了专家知识，这样便于用户更深地理解产生决策树的数据及最终产生的决策树。
同时此方法也显
著地减小了决策树的大小。
在M.Ankerst等提出的方法中，他们主要用两类进化算法替代了传统的贪婪搜索算法以实现数值属性的任意分割。
1.3寻找更好的简化决策树的方法
简化决策树的研究工作主要有两个方面，一是对比各种不同的简化决策树方法，分析它们各自的特性、优点和缺点。
另外一个就是寻找更好的与传统方法不同的简化决策树的方法，这一直是决策树技术研究的一个热点。
近年来，针对不同的应用领域并且随着其他新技术的加入，陆续有这方面的文章发表。
例如，D.Founrnier等提出的一种新的修剪决策树的方法-DI修剪法[14]。
此方法针对数据不确定的情况，利用特性索引（QualityIndex）来权衡处理
决策树深度和节点杂质。
DI-修剪法将保持那些虽不能减小错误率但能指出一些特殊性质的群体的子树。
D.Founrnier等认为这对于研究不确定数据是非常关键的。
1.4研究产生决策树的训练和检验数据的大小及特性与决策树特性之间的关系
与上述简化决策树不同，这类研究着眼于产生决策树的数据。
训练数据的增加经常造成决策树大小的线性增加，而这种增加并没有都带来决策树准确性的提高。
一些专家认为，在
产生决策树前尽量减少数据量比在决策树产生后再简化决策树更加有效。
实际上，这就是经
常提起的数据预处理技术（DataPreprocessing），与决策树修剪技术（Pruning）相对应，也称它为数据减少技术（DataReductionTechniques）。
近几年，有关这方面的研究取得了一些进展[15][16][17]。
1.5不确定环境下决策树研究
不确定环境下的决策研究一直是一个热点，决策树技术就是其中一个重要的方法之一。
前面介绍的决策树技术与模糊集合原理的结合就是一个不错的选择。
此外，Z.Eloudi等人
提出了一种基于置信度函数的决策树[18]。
此算法利用置信度函数原理来代表分类问题中的参数不确定性，在不确定环境下决策树构造和不确定环境下的分类均取得了比较好的效果。
目前正在进行决策树与专家系统相结合的研究，以便在不确定环境下更好地决策。
1.6决策树技术中时间复杂度与准确性之间的矛盾
决策树技术与神经网络技术相比所具有的最大优点就是训练决策树的时间远远低于训练神经网络的时间。
决策树技术中如何处理时间复杂度和分类准确性之间的矛盾是一个令人感兴趣的问题。
到底如何取舍需要具体问题具体分析。
例如，0.Taner等人提出的全变量决
策树（0mnivariateDecisionTree）[19]。
在分类正确性方面超过了其他决策树方法，却付出了需要更多训练时间的代价。
随着微处理器速度越来越快、价钱越来越便宜，以及并行计算的运用，使人们在做决定时拥有比以前更大的自由。
1.7决策树技术的软件实现
将决策树技术软件化一直是决策树技术的方向之一。
目前市场上的大多数据挖掘软件如
SAS等都包含有决策树技术部分。
如何开发出功能更加强大、使用更加方便、界面更加友好的软件以实现决策树技术，一直是大家努力的方向。
以上这些决策树的研究并不是孤立的，
它们经常相互联系、相互结合。
2决策树算法实例
在汽车评价分类的数据库中给汽车定义了6个属性：
（1）购买价格buying，该属性取值有4种，分别为vhigh、high、med和low
（2）保养维护费用maint，该属性取值有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:
//archive.ics.uci.edu/ml/datasets/Car+Evaluation
2.1CLS算法逻辑与实现
用CLS算法生成决策树首先要确定6个属性的先后顺序，即决策树每层需要对哪种属
性进行取值分类和判断。
如下图所示，程序使用者在运行算法之前可以在下拉列表中选择决策树前2层的属性，其余4种属性将按照数据库中从左至右的默认顺序依次作为决策树之后4层的属性。
Ch00^0thvfirstattributm：
|pmr.en寸”
Andth@secondattribute:
safely
下图即为选择persons和safety作为前2层属性时6个属性的排列顺序：
Attribute/ResuttName
persons
safety
buying
maint
doors
Iugb0at
ColumnNo.
5
7
2
3
4
6
CountofValues
3
3
4
4
4
3
Values
2
low
vhigh
vhigh
2
small
4
med
high
high
3
med
more
high
med
med
4
big
low
low
5more
附录1的代码为生成决策树的主要过程，首先将所有汽车按照第1层属性的取值进行
分类，例如按上图顺序按persons分为3类（2、4和more）。
然后依次进行判断每类汽车的消费者评价是否一致，若一致则在该类下生成叶子结点，例如persons取值为2的汽车
均被评价为unacc，于是生成如下图所示的叶子结点：
若该类汽车的消费者评价不一致，则进入决策树第2层的生成过程，将该类汽车按照
第2层属性的取值继续细分，例如persons取值为4的汽车没有一致的消费者评价，于是按safety继续细分为3类（low、med和high）依次进行判断，如下图所示：
persons
4
safety
low
med
high
根据这种方法层层推进，最终即可生成完整的决策树，而每层的生成方法和逻辑与附录1的代码相似，因此不一一叙述。
2.2ID3算法逻辑与实现
用ID3算法生成决策树不需要事先确定6个属性的先后顺序，而是由附录3的代码在生成新结点是计算每种属性的信息熵并选择这个结点的属性，选择结点属性之后和CLS算
法一样进行该属性不同取值的分类和判断。
附录2的代码为生成决策树的主要过程，首先计算各属性的信息熵并选择第1层的属
性，例如在汽车评价案例中经过计算选择safety为第1层属性，如下图所示：
然后按safety分为3类（low、med和high），依次进行判断每类汽车的消费者评价是
否一致，若一致则在该类下生成叶子结点，例如safety取值为low的汽车均被评价为unacc，
于是生成如下图所示的叶子结点：
若该类汽车的消费者评价不一致，则进入决策树第2层的生成过程，按该类汽车计算
各属性的信息熵并选择结点属性，根据不同取值继续细分并判断，例如safety取值为med
的汽车没有一致的消费者评价，于是计算并选取persons作为结点属性，继续细分为3类
（2、4和more）依次进行判断，如下图所示：
safely
med
persons
2
4
more
根据这种方法层层推进，最终即可生成完整的决策树，而每层的生成方法和逻辑与附录1的代码相似，因此不一一叙述。
与CLS算法规定了每层的结点属性不同，在ID3算法中对每个新的结点都需要计算各属性的信息熵来选择属性，所以某个结点按属性的取值分类后，下一层的几个结点未必采用相同的属性，例如下图中第4层的4个结点并没有选择同样的属性。
safety
med
persons
4
buying
vhigh
maim
highlugbt>ot
med
maint
low
rnaint
2.3CLS算法与ID3算法效果比较
CLS算法的效果根据属性顺序的不同会有很大的差异，下表即为根据不同属性顺序生成决策树的叶子结点数：
属性顺序
叶子结点数
safetyTpersonstbuyingtmaintTdoorstlugboot
469
personstsafetytbuyingtmaintTdoorstlugboot
469
buyingtmainttdoorstpersonstlugboottsafety
965
lugboottmaintTbuyingtdoorsTpersonstsafety
1075
doorstlugboottbuyingTmaintTpersonstsafety
1102
可以看到属性顺序对于效果的影响十分巨大，通过改变顺序叶子结点数的变化可能超过
1倍。
经过多次测试，用CLS算法生成汽车评价决策树的最少叶子结点数为469个，而ID3
算法生成的决策树只有296个叶子结点。
由于ID3算法选取结点属性的方法更加灵活、合
理，从直观上判断会比CLS算法效果更佳，所以这样的结果差异也在情理之中。
3总结
本文实例是用VBA语言编程，界面为Excel2003（具体见电子版），语言和界面不够专业，所以实现速度也没有达到最理想，最快的42''最慢的4'以上。
进一步工作会在编程
语言上改进，以实现最佳效果。
附录附录1CLS算法生成决策树的过程
PrivateFunctionDECISIONTREE（LAYER_COUNTAsInteger,ROW_COUNTAsInteger）
DimLAYER_RANGEAsRange,TREE_RANGEAsRange,RANGE2AsRange,ROW2AsInteger,IAsInteger,JAsInteger,KAsInteger,XAsInteger
DimVALUE1AsString,COLUMN1AsInteger,CLASSAsString,CLASS_COLUMNAsInteger,DECISIONAsStringSetLAYER_RANGE=Range（"K5"）
CLASS_COLUMN=LAYER_COUNT+2
SetTREE_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=-1
ForI=1ToLAYER_RANGE.Cells（3,1）
VALUE1=LAYER_RANGE.Cells（3+I,1）
K=0
ForJ=2ToROW_COUNT
IfCells（J,COLUMN1）=VALUE1Then
CLASS=Cells（J,CLASS_COLUMN）
K=JExitFor
EndIf
Next
X=1
ForJ=KToROW_COUNT
IfCells（J,COLUMN1）=VALUE1AndNotCells（J,CLASS_COLUMN）=CLASSThen
X=0ExitFor
EndIf
Next
IfX=1Then
ROW2=ROW2+2
TREE_RANGE.Cells（ROW2,2）=VALUE1TREE_RANGE.Cells（ROW2,3）=CLASS
CallBORDER_MEDIUM（TREE_RANGE.Cells（ROW2,3））
CallCONECTION（TREE_RANGE.Cells（1,1）,TREE_RANGE.Cells（ROW2,3））
ElseIfX=0Then
ROW2=ROW2+2
TREE_RANGE.Cells（ROW2,2）=VALUE1
TREE_RANGE.Cells（ROW2,3）=LAYER_RANGE.Cells（1,2）
CallBORDER_THIN（TREE_RANGE.Cells（ROW2,3））
CallCONECTION（TREE_RANGE.Cells（1,1）,TREE_RANGE.Cells（ROW2,3））
SetRANGE2=TREE_RANGE.Cells（ROW2,3）
ROW2=ROW2-1+LAYER2（RANGE2,VALUE1,LAYER_RANGE,CLASS_COLUMN,ROW_COUNT）EndIf
Next
Range（"K13"）=（ROW2+1）/2
EndFunction
附录2ID3算法生成决策树的过程
PrivateFunctionDECISIONTREE（ROW_COUNTAsInteger）
As
As
DimLAYER_RANGEAsRange,TREE_RANGEAsRange,RANGE2AsRange,ROW2AsInteger,COLUMN1Integer,ATTRIBUTE1AsInteger,ATTRIBUTE2AsInteger,VALUE1AsString,CLASSAsString,CLASS_COLUMNInteger
DimIAsInteger,JAsInteger,KAsInteger,LAsInteger,NAsInteger,MAsInteger
SetLAYER_RANGE=Range（"K5"）
SetTREE_RANGE=Range（"K16"）
CLASS_COLUMN=8
M=LAYER_RANGE.Cells（3,7）
ATTRIBUTE1=CHOOSE_ATTRIBUTE（7,CLASS_COLUMN,ROW_COUNT,M,LAYER_RANGE）
LAYER_RANGE.Cells（8,ATTRIBUTE1）=1
TREE_RANGE.Cells（1,1）=LAYER_RANGE.Cells（1,ATTRIBUTE1）
BORDER_THIN（TREE_RANGE.Cells（1,1））
COLUMN1=LAYER_RANGE.Cells（2,ATTRIBUTE1）
ROW2=-1
ForI=1ToLAYER_RANGE.Cells（3,ATTRIBUTE1）
VALUE1=LAYER_RANGE.Cells（3+I,ATTRIBUTE1）
K=0
ForJ=2ToROW_COUNT
IfCells（J,COLUMN1）=VALUE1Then
CLASS=Cells（J,CLASS_COLUMN）
K=J
[REF].Cells（J,ATTRIBUTE1）=1
Else
[REF].Cells（J,ATTRIBUTE1）=0
EndIf
Next
X=1
ForJ=2ToROW_COUNT
IfCells（J,COLUMN1）=VALUE1AndNotCells（J,CLASS_COLUMN）=CLASSThen
X=0ExitFor
EndIf
Next
IfX=1Then
ROW2=ROW2+2
TREE_RANGE.Cells（ROW2,2）=VALUE1
TREE_RANGE.Cells（ROW2,3）=CLASS
CallBORDER_MEDIUM（TREE_RANGE.Cells（ROW2,3））
CallCONECTION（TREE_RANGE.Cells（1,1）,TREE_RANGE.Cells（ROW2,3））
ElseIfX=0Then
ROW2=ROW2+2
TREE_RANGE.Cells（ROW2,2）=VALUE1
M,
ATTRIBUTE2=CHOOSE_ATTRIBUTE（ATTRIBUTE1,CLASS_COLUMN,ROW_COUNT,LAYER_RANGE）
TREE_RANGE.Cells（ROW2,3）=LAYER_RANGE.Cells（1,ATTRIBUTE2）
CallBORDER_THIN（TREE_RANGE.Cells（ROW2,3））
CallCONECTION（TREE_RANGE.Cells（1,1）,TREE_RANGE.Cells（ROW2,3））
SetRANGE2=TREE_RANGE.Cells（ROW2,3）
ROW2=ROW2-1+LAYER2（RANGE2,ATTRIBUTE1,ATTRIBUTE2,LAYER_RANGE,CLASS_COLUMN,ROW_COUNT,M）
EndIf
Next
LAYER_RANGE.Cells（8,ATTRIBUTE1）=Empty
Range（"K13"）=（ROW2+1）/2
EndFunction
附录3ID3算法计算信息熵和选择结点属性的过程
PrivateFunctionENTROPY_CALCULATION（ATT_NOAsInteger,PREAT
升级会员 