决策树属性选取标准研究

决策树属性选取标准研究

总结决策树是机械学习中使用数据分类和预测的重要方法。生成决策树的基本方法是,对于一个含有若干普通属性和一个类别属性的数据集,决策树归纳算法按照一定的标准依次选择普通属性作为决策树的节点,在节点处按照属性的不同取值对数据集进行拆分,直到每一个数据子集都唯一地对应一个类别。其中属性选取标准在决策树算法中处于核心的地位。1986年,J.R.Quinlan提出了信息增益标准;1984年,L.Breiman等在CART系统中使用了Gini-Index标准;1986年,J.Mingers提出了χ2统计标准;1992年,K.Kira等提出了Relidf标准;1997年,S.J.Hong等提出了CM标准。根据属性间的相互依赖关系,这些属性选取标准可以分为两类:属性间相互独立的策略和属性间相互关联的策略。前者在进行属性选取时,认为各个属性间是相互独立的,每一个属性独立地影响分类属性的取值,如信息增益、Gini-Index和χ2统计就属于这一类。后者在进行属性选取时,认为各个属性对数据类别的影响不是独立的,每一个属性都在其它属性的背景下对数据类别发生影响,如RELIEF和CM就属于这一类。1属性之间的独立关系这种策略在评估每个属性时忽略其他属性的影响,认为属性之间是相互独立的。它的优点是运算效率比较高,而且能满足很多问题的实际需求。以下将分别介绍信息增益标准、Gini-Index标准和χ2统计标准。1.1radition和分类属性为了检验各个属性选取标准,本文用到了一个医学领域的数据集——乳腺癌的复发统计。数据集包括两个普通属性和一个类别属性。属性RADIATION表示患者是否接受过放射治疗,取值为(YES,NO)。属性MENOPAUSE表示患者的绝经时间,取值为(<60,≥60,NOT)。分类属性CLASS的取值为(RECUR,NOTRECUR)。如表1所示。1.2根据信息增益标准选择适用的属性符号定义:n表示数据集D中的样本总数,v表示D的类别属性的取值个数,p(cj),j=1,2,…,v表示D中第j类样本出现的概率,k表示属性的取值个数,ni,i=1,2,…,k表示属性的第i个取值所对应的数据子集中的样本总数,pi(cj)j=1,2,…,v表示属性的第i个取值所对应的数据子集中第j类样本出现的概率。对某一样本进行分类所带来的平均信息量I可表示为:Ι=v∑j=1[-p(cj)log2p(cj)]假定属性A有k个取值{A1,A2,⋯,Ak},这k个取值把数据集D划分为k个数据子集{D1,D2,⋯,DΚ},在数据子集Di中对某一样本进行分类所带来的平均信息量用I(Ai)表示,则某一样本首先经过属性A划分到不同的数据子集,然后再在数据子集中分类所带来的平均信息量E(A)为:E(A)=k∑i=1ninΙ(Ai)Ι(Ai)=v∑j=1[-pi(cj)log2pi(cj)]则按照属性A拆分数据集所带来的信息增益为:gain(A)=I-E(A)下面是此属性选择标准在乳腺癌复发统计数据集中的应用:对于RADIATION属性:Ι=-510log2510-510log2510=1Ι(A1)=-0-33log233=0Ι(A2)=-57log257-27log227=0.8631E(A)=310×0+710×0.8631=0.6042gain(REDΙAΤΙΟΝ)=1-0.6042=0.3958对于MENOPAUSE属性:I=1Ι(A1)=-35log235-25log225=0.9710Ι(A2)=-13log213-23log223=0.9183cΙ(A3)=-12log212-12log212=1E(A)=510×0.971+310×0.9183+210×1=0.9610gain(ΜEΝΟΡAUSE)=1-0.9610=0.0390所以,根据信息增益标准,优先选择属性RADIATION作为节点生成决策树。1.3集中数据的纯度Gini-Index是不纯度函数(impurityfunction)的一种。不纯度函数是用来度量数据集中的数据关于类的“纯度”的,如果数据均匀地分散于各个类中,则数据集的不纯度就大,反之,数据集的不纯度就小。根据属性的不同取值拆分数据集时,会导致数据集不纯度的减小,即纯度的增加。Gini-Index标准首先计算各个属性的纯度增量,然后选取纯度增量最大的属性来拆分数据集。1.3.1节点t的不纯度度量不纯度函数Φ定义在一个k元组(p(c1),p(c2),…,p(ck))上,此k元组具有下列性质:①p(ci)≥0∀i∈{1,2,⋯,k}②k∑i=1p(ci)=1不纯度函数Φ满足下列条件:①Φ在点(1k,1k,⋯,1k)处取得最大值②Φ在点(1,0,…,0),…,(0,0,…,1)处取得最小值③Φ是p(c1),p(c2),…,P(ck)的对称函数把不纯度函数应用在决策树中,节点t的不纯度度量可表示为为:其中p(cit),i=1,2,⋯,k表示节点t所对应的数据集中第i类数据所占的比例。假定节点t所对应的属性有n个取值,分别对应着n个数据子集t1,t2,…,tn,每个数据子集所占的比例分别为p(t1),p(t2),…,p(tn),则在节点t的拆分所引起的纯度增益为:Δi(t)=i(t)-n∑i=1p(ti)i(ti)1.3.2基于dini-目标的乳腺癌复苏统计数据集成Gini-Index作为不纯度函数的一种,其形式如下:Φ(p(c1),p(c2),⋯,p(ck))=k∑i=1k∑j=1,j≠ip(ci)p(cj)=1-k∑i=1(p(ci))2把Gini-Index应用在决策树中,则节点t的不纯度函数为:i(t)=k∑i=1k∑j=1,j≠ip(cit)p(cjt)=1-k∑j=1(p(cjt))2节点t处的拆分所引起的纯度增益为:Δi(t)=i(t)-n∑i=1p(ti)i(ti)假定节点t所对应的属性为A,则属性A的拆分度量为:gini(A)=Δi(t)下面是此属性选择标准在乳腺癌复发统计数据集中的应用:对于属性RADIATION:i(t)=1-(510)2-(510)2=0.5i(t1)=1-(57)2-(27)2=0.4082i(t2)=1-(0)2-(33)2=0gini(RADΙAΤΙΟΝ)=0.5-710×0.4082-310×0=0.2143对于属性MENOPAUSE:i(t)=0.5i(t1)=1-(35)2-(25)2=0.48i(t2)=1-(13)2-(23)2=0.4444gini(ΜEΝΟΡAUSE)=0.5-510×0.48-310×0.4444-210×0.5=0.02668所以,根据Gini-Index标准,优先选择属性RADIATION作为节点生成决策树。1.4列联表中频率的实验与统计x2统计是度量两个变量关联程度的一种方法。首先把两变量的取值频率表示在列联表中,然后比较实际观察到的频率(即列联表中的频率)与假定在没有关联的情况下期望的频率(通过列联表计算得到),所得到的统计量的分布近似于x2统计。此统计量的结果越大表示两变量的关联程度越大。1.4.1属性集中属性xj时的样本个数假定一个数据集含有属性A和分类属性C,则它们所形成的列联表如表2所示。xij表示数据集中属性A取值Ai,类C取值Cj的样本的个数;xi。表示属性A取值Ai时的样本总数;x。j表示类C取值Cj时的样本总数;N表示数据集中的样本总数。1.4.2类型和属性的相关此标准的基本方程为:x2=∑i=1r∑j=1c(xij-Eij)2Eijxij表示属性取第i个值,类取第j个值时样本的个数,Eij=xi。x。jΝ表示在假定属性和类没有关联时xij的期望值。此属性选择标准在乳腺癌复发统计数据集中的应用:对于属性RADIATION:x2=(0-1.5)21.5+(3-1.5)21.5+(5-3.5)23.5+(2-3.5)23.5=4.29对于属性MENOPAUSE:x2=(3-2.5)22.5+(2-2.5)22.5+(1-1.5)21.5+(2-1.5)21.5+(1-1)21+(1-1)21=0.533所以,根据x2统计标准,优先选择属性RADIATION作为节点生成决策树。2两个属性间的依赖关系有许多问题,单一属性不能传递类的信息,需要把几个属性结合起来才能传递类的信息。比如“异或运算”,当两个属性取值相同时,类的取值为1,当两个属性的取值不同时,类的取值为0。此时,两个属性相互依赖共同决定类的状况。对于此类问题,就必须在其他属性的背景下评估每个属性。与属性间相互独立的选择策略相比,这种方法的运算效率比较低,但往往能够发现属性间潜在的依赖关系。RELIEF算法和CM算法都采用了这种策略,它们都是以基于局部环境的距离为基础的。2.1局部属性的选取一个数据集有n个属性,则这n个属性就形成了一个n维空间,称为实例空间,数据集中的每一个样本称为实例空间中的一个实例。在实例空间中,一个实例和它临近的实例共同组成了一个局部环境。在局部环境中可能观察到一些属性间的潜在的依赖关系,而在全局环境中这些依赖关系可能会由于大量实例的平均作用而被抵消。所以,利用处于局部环境中的实例之间的距离作为属性选取的标准,就潜在地考虑了其它属性对当前属性的影响。对于属性Xi,两个实例r、s在该属性上的取值分别为和,则两实例在此属性上的分量距离为:如果Xi是分类属性(categoricalattribute):dirs={0ifxir=x(i)s1ifx(i)r≠x(i)s如果Xi是数值属性(numericalattribute):dirs=min((|x(i)r-x(i)s|/ti),1)ti是一个阈值,通常设定为属性取值范围的一半。实例空间中两实例之间的距离Drs可以定义为欧拉距离,也可定义为如下的Manhatan距离:2.2基于reliff算法的算法RELIEF标准的基本观念是:一个理想的属性,对于在实例空间中邻近的实例而言,如果它们是同一类的则应该有相同的取值,如果它们不是同一类的则应该有不同的取值。给定一个实例r,RELIEF搜索它的两个最近邻s、t,且s与r不同类,t与r同类,则对于属性Xi,RELIEF采用的度量标准为:q(Xi)=∑r(drs,i-drt,i)r∈Τ′⊂Τ其中集合T′是训练集T的一个随机子集。为了减少数据集中的噪声对算法的影响,文献把RELIEF扩展为ReliefF算法。在ReliefF算法中,采取的是k最近邻(k-nearest)策略:给定一个实例r,ReliefF搜索实例r的k个同类最近邻,k×(c-1)个不同类的最近邻,其中c为数据集中数据的类数。对于属性Xi,ReliefF采用的度量标准为:q(Xi)=∑r∑C(s)≠C(r)(p(C(s))1-p(C(r))drs,ik)-∑r∑C(s)=C(r)drs,ikC(s)表示实例s所属的类,C(r)表示实例r所属的类,p(C(s))表示在数据集T中与实例s同类的实例所占的百分比,p(C(r))表示在数据集T中与实例r同类的实例所占的百分比。2.3同类的实例r、s间距离drs的减函数CM标准的基本观念:①对于两个不同类的实例r、s,只有那些取值不同的属性对它们具有区分作用;②对于某个属性,它对不同类的实例r、s的区分作用是r、s间距离Drs的减函数。对于②的解释是,Drs越大则实例r、s中取值不同的属性越多,则所有取值不同的属性共同“分享”这种区分能力。Drs被称为实例r、s的环境强度。对于属性Xi,它的CM标准被定义为:CΜ(Xi)=∑r∑C(s)≠C(r)drs,iDrs2r∈Τ′⊆Τ其中r是T′中的一个实例,s是T′中r的不同类的一个k近邻。3属性选择标准的多值偏多所谓多值偏向是指属性选取标准在评估属性时,有优先选取取值较多的属性的倾向。多值偏向所带来的问题是,把属性在分类中的重要性与属性取值数多少关联起来,认为取值较多的属性在分类中具有更重要的作用。例如,假定一个数据集有一个属性“年龄”,对应于每一年有一个取值,而如果数据集中每一个人的年龄都不同,则根据“年龄”可以对数据集中的数据进行精确的分类,但这种分类对其它数据集的预测或者分类没有任何价值。如果属性A具有取值A1,A2,…,An,可以把其中的某个值拆分为两个值,把这组新的取值A′1,A′2,…,A′n,A′n+1赋予属性A′,然后把属性选择标准分别作用在A和A′上,然后通过比较两者的取值来评估属性选取标准的多值偏向,如果后者的取值大于前者,则认为此属性选取标准存在多值偏向问题。应用这种方法很容易证明信息增益、Gini-Index、和χ2统计都具有多值偏向的特征,而RELEF和CM则避免了多值偏向。人