资源描述:
《基于主成分分析的id3改进算法》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、基于主成分分析的id3改进算法ID3ImprovedAlgorithmBasedonPrincipalComponentAnalysis摘要:决策树算法中的ID3算法作为最有影响的一种决策树生成算法得到广泛应用,但其缺点也是显而易见的,本文运用主成分分析算法和该算法结合,探索了一种新的基于主成分分析的ID3改进算法,作为一种有益的探索,该算法的准确性和效率有待进一步考证。关键字:ID3算法,主成分分析,决策树Abstract:ID3algorithmisoneofthemostefficiencydecisiontreealgorithms,anditappliedto
2、manyareas」D3algorithmhasdistinetadvantages,butitsdisadvantagesareprominentalso.ThearticleappliedthealgorithmofprincipalcomponentanalysistogetherwiththeID3algorithm,exploredanimprovedalgorithm.Asanewalgorithm,ifsveracityandefficiencyneedextendresearch.Keywords:ID3algorithm,principalcompor
3、ientanalysis,decisiontree0引言决策树分类方法是一种有效的数据挖掘方法,Quinlan提出的ID3算法是最有影响的一种决策树生成算法,它己经广泛的应用于各种领域。该算法将信息论引入到了决策树算法中,把信息爛作为选择测试属性的标准,对训练实例集进行分类并构造决策树,其关键是选择何种属性作为依据来对整个实例空间进行划分。该算法优点多,但是缺点也较为突出⑴。其中一个缺点就是多值偏向问题,所谓多值偏向,就是决策树算法在选择分裂属性时,倾向于优先选取取值较多的属性。在实际问题中属性取值多的属性不一定是最优的⑶。本文采用主成分分析方法,首先选出众多属性中主要
4、的屈性,然后运用ID3方法建立决策树。最后经过一组数据集进行实验,证明了该种改进算法是切实可行的。1主成分分析基本原理主成分分析就是对原来多个变量进行适当的组合,组合成一些综合指标,用较少的综合指标来近似代替原来的多个变量。这种由原来多个变量组合而成的综合指标,就称为主成分(PrincipalComponent)⑷。主成分选取的原则是:主成分是原变量的线性组合;各个主成分之间互不相关;如果原来有加个变量,最多可以取到加个主成分,这加个主成分的变化,可以完全反映原来全部加个变量的变化;如果选取的主成分少于加个,那么这些少的主成分的变化,应该尽可能多地反映原来全部加个变量的
5、变化⑷。2基于主成分分析的ID3改进算法以经典的气候训练集⑴为例,首先用主成分分析的方法选出天气、气温、湿度和风四个属性屮的主要属性,具体做法如下:将气候训练集的14个样本中的数据用矩阵形式表示出来,即天气属性下的晴值设为1,多云设为2,雨设为3;同样气温属性下的热值设为1,适中值设为2,冷值设为3;温度属性下的高值设为1,正常值设为2;风属性下的无风设为1,有(12风设为2。得到如下观测数据矩阵:3122323332312221222111221Y—YSj=是四个屈性变量设勺二丄一^(心1,2,…,14,)=1,2,…,4)是中心化标准化的观测数据,其中S;-114
6、Xj二占£勺是四个属性变量的样本均值,14,=1的样本标准差。变换后的观测数据组成的矩阵如下:'■1.183・1.1830.0001.1831」831.1830.000・1.183-1.1831.183・1.1830.0000.0001.183、-1.323-1.323-1.3230.0001.3231.3231.3230.0001.3230.0000.0000.0001.3230.000X严1-1.000-1.000-1.000-1.0001.0001.0001.000-1.0001.0001.0001.000-1.0001.000-1.000c0.8661.155-
7、0.866-0.866-0.8661.1551.155-0.866-0.866-0.8661.1551.155-0.8661.155丿按照公式/?=右求出的矩阵就是样木相关阵(SampleCorrelationMatrix)。<1-00000.33540.33541.0000R=0.16900.56690.16900、0.56690.19091.0000・0.00000.1909-0.00001.0000对样本相关阵作特征分解,得到r=uut,K中A是由/?的特征值组成的对角阵。是由/?的标准正交化的特征向量按列并排组成的正交阵。0.3