決策樹屬性選取標(biāo)準(zhǔn)研究

決策樹屬性選取標(biāo)準(zhǔn)研究

總結(jié)決策樹是機(jī)械學(xué)習(xí)中使用數(shù)據(jù)分類和預(yù)測的重要方法。生成決策樹的基本方法是,對(duì)于一個(gè)含有若干普通屬性和一個(gè)類別屬性的數(shù)據(jù)集,決策樹歸納算法按照一定的標(biāo)準(zhǔn)依次選擇普通屬性作為決策樹的節(jié)點(diǎn),在節(jié)點(diǎn)處按照屬性的不同取值對(duì)數(shù)據(jù)集進(jìn)行拆分,直到每一個(gè)數(shù)據(jù)子集都唯一地對(duì)應(yīng)一個(gè)類別。其中屬性選取標(biāo)準(zhǔn)在決策樹算法中處于核心的地位。1986年,J.R.Quinlan提出了信息增益標(biāo)準(zhǔn);1984年,L.Breiman等在CART系統(tǒng)中使用了Gini-Index標(biāo)準(zhǔn);1986年,J.Mingers提出了χ2統(tǒng)計(jì)標(biāo)準(zhǔn);1992年,K.Kira等提出了Relidf標(biāo)準(zhǔn);1997年,S.J.Hong等提出了CM標(biāo)準(zhǔn)。根據(jù)屬性間的相互依賴關(guān)系,這些屬性選取標(biāo)準(zhǔn)可以分為兩類:屬性間相互獨(dú)立的策略和屬性間相互關(guān)聯(lián)的策略。前者在進(jìn)行屬性選取時(shí),認(rèn)為各個(gè)屬性間是相互獨(dú)立的,每一個(gè)屬性獨(dú)立地影響分類屬性的取值,如信息增益、Gini-Index和χ2統(tǒng)計(jì)就屬于這一類。后者在進(jìn)行屬性選取時(shí),認(rèn)為各個(gè)屬性對(duì)數(shù)據(jù)類別的影響不是獨(dú)立的,每一個(gè)屬性都在其它屬性的背景下對(duì)數(shù)據(jù)類別發(fā)生影響,如RELIEF和CM就屬于這一類。1屬性之間的獨(dú)立關(guān)系這種策略在評(píng)估每個(gè)屬性時(shí)忽略其他屬性的影響,認(rèn)為屬性之間是相互獨(dú)立的。它的優(yōu)點(diǎn)是運(yùn)算效率比較高,而且能滿足很多問題的實(shí)際需求。以下將分別介紹信息增益標(biāo)準(zhǔn)、Gini-Index標(biāo)準(zhǔn)和χ2統(tǒng)計(jì)標(biāo)準(zhǔn)。1.1radition和分類屬性為了檢驗(yàn)各個(gè)屬性選取標(biāo)準(zhǔn),本文用到了一個(gè)醫(yī)學(xué)領(lǐng)域的數(shù)據(jù)集——乳腺癌的復(fù)發(fā)統(tǒng)計(jì)。數(shù)據(jù)集包括兩個(gè)普通屬性和一個(gè)類別屬性。屬性RADIATION表示患者是否接受過放射治療,取值為(YES,NO)。屬性MENOPAUSE表示患者的絕經(jīng)時(shí)間,取值為(<60,≥60,NOT)。分類屬性CLASS的取值為(RECUR,NOTRECUR)。如表1所示。1.2根據(jù)信息增益標(biāo)準(zhǔn)選擇適用的屬性符號(hào)定義:n表示數(shù)據(jù)集D中的樣本總數(shù),v表示D的類別屬性的取值個(gè)數(shù),p(cj),j=1,2,…,v表示D中第j類樣本出現(xiàn)的概率,k表示屬性的取值個(gè)數(shù),ni,i=1,2,…,k表示屬性的第i個(gè)取值所對(duì)應(yīng)的數(shù)據(jù)子集中的樣本總數(shù),pi(cj)j=1,2,…,v表示屬性的第i個(gè)取值所對(duì)應(yīng)的數(shù)據(jù)子集中第j類樣本出現(xiàn)的概率。對(duì)某一樣本進(jìn)行分類所帶來的平均信息量I可表示為:Ι=v∑j=1[-p(cj)log2p(cj)]假定屬性A有k個(gè)取值{A1,A2,?,Ak},這k個(gè)取值把數(shù)據(jù)集D劃分為k個(gè)數(shù)據(jù)子集{D1,D2,?,DΚ},在數(shù)據(jù)子集Di中對(duì)某一樣本進(jìn)行分類所帶來的平均信息量用I(Ai)表示,則某一樣本首先經(jīng)過屬性A劃分到不同的數(shù)據(jù)子集,然后再在數(shù)據(jù)子集中分類所帶來的平均信息量E(A)為:E(A)=k∑i=1ninΙ(Ai)Ι(Ai)=v∑j=1[-pi(cj)log2pi(cj)]則按照屬性A拆分?jǐn)?shù)據(jù)集所帶來的信息增益為:gain(A)=I-E(A)下面是此屬性選擇標(biāo)準(zhǔn)在乳腺癌復(fù)發(fā)統(tǒng)計(jì)數(shù)據(jù)集中的應(yīng)用:對(duì)于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對(duì)于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所以,根據(jù)信息增益標(biāo)準(zhǔn),優(yōu)先選擇屬性RADIATION作為節(jié)點(diǎn)生成決策樹。1.3集中數(shù)據(jù)的純度Gini-Index是不純度函數(shù)(impurityfunction)的一種。不純度函數(shù)是用來度量數(shù)據(jù)集中的數(shù)據(jù)關(guān)于類的“純度”的,如果數(shù)據(jù)均勻地分散于各個(gè)類中,則數(shù)據(jù)集的不純度就大,反之,數(shù)據(jù)集的不純度就小。根據(jù)屬性的不同取值拆分?jǐn)?shù)據(jù)集時(shí),會(huì)導(dǎo)致數(shù)據(jù)集不純度的減小,即純度的增加。Gini-Index標(biāo)準(zhǔn)首先計(jì)算各個(gè)屬性的純度增量,然后選取純度增量最大的屬性來拆分?jǐn)?shù)據(jù)集。1.3.1節(jié)點(diǎn)t的不純度度量不純度函數(shù)Φ定義在一個(gè)k元組(p(c1),p(c2),…,p(ck))上,此k元組具有下列性質(zhì):①p(ci)≥0?i∈{1,2,?,k}②k∑i=1p(ci)=1不純度函數(shù)Φ滿足下列條件:①Φ在點(diǎn)(1k,1k,?,1k)處取得最大值②Φ在點(diǎn)(1,0,…,0),…,(0,0,…,1)處取得最小值③Φ是p(c1),p(c2),…,P(ck)的對(duì)稱函數(shù)把不純度函數(shù)應(yīng)用在決策樹中,節(jié)點(diǎn)t的不純度度量可表示為為:其中p(cit),i=1,2,?,k表示節(jié)點(diǎn)t所對(duì)應(yīng)的數(shù)據(jù)集中第i類數(shù)據(jù)所占的比例。假定節(jié)點(diǎn)t所對(duì)應(yīng)的屬性有n個(gè)取值,分別對(duì)應(yīng)著n個(gè)數(shù)據(jù)子集t1,t2,…,tn,每個(gè)數(shù)據(jù)子集所占的比例分別為p(t1),p(t2),…,p(tn),則在節(jié)點(diǎn)t的拆分所引起的純度增益為:Δi(t)=i(t)-n∑i=1p(ti)i(ti)1.3.2基于dini-目標(biāo)的乳腺癌復(fù)蘇統(tǒng)計(jì)數(shù)據(jù)集成Gini-Index作為不純度函數(shù)的一種,其形式如下:Φ(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應(yīng)用在決策樹中,則節(jié)點(diǎn)t的不純度函數(shù)為:i(t)=k∑i=1k∑j=1,j≠ip(cit)p(cjt)=1-k∑j=1(p(cjt))2節(jié)點(diǎn)t處的拆分所引起的純度增益為:Δi(t)=i(t)-n∑i=1p(ti)i(ti)假定節(jié)點(diǎn)t所對(duì)應(yīng)的屬性為A,則屬性A的拆分度量為:gini(A)=Δi(t)下面是此屬性選擇標(biāo)準(zhǔn)在乳腺癌復(fù)發(fā)統(tǒng)計(jì)數(shù)據(jù)集中的應(yīng)用:對(duì)于屬性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對(duì)于屬性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所以,根據(jù)Gini-Index標(biāo)準(zhǔn),優(yōu)先選擇屬性RADIATION作為節(jié)點(diǎn)生成決策樹。1.4列聯(lián)表中頻率的實(shí)驗(yàn)與統(tǒng)計(jì)x2統(tǒng)計(jì)是度量兩個(gè)變量關(guān)聯(lián)程度的一種方法。首先把兩變量的取值頻率表示在列聯(lián)表中,然后比較實(shí)際觀察到的頻率(即列聯(lián)表中的頻率)與假定在沒有關(guān)聯(lián)的情況下期望的頻率(通過列聯(lián)表計(jì)算得到),所得到的統(tǒng)計(jì)量的分布近似于x2統(tǒng)計(jì)。此統(tǒng)計(jì)量的結(jié)果越大表示兩變量的關(guān)聯(lián)程度越大。1.4.1屬性集中屬性xj時(shí)的樣本個(gè)數(shù)假定一個(gè)數(shù)據(jù)集含有屬性A和分類屬性C,則它們所形成的列聯(lián)表如表2所示。xij表示數(shù)據(jù)集中屬性A取值A(chǔ)i,類C取值Cj的樣本的個(gè)數(shù);xi。表示屬性A取值A(chǔ)i時(shí)的樣本總數(shù);x。j表示類C取值Cj時(shí)的樣本總數(shù);N表示數(shù)據(jù)集中的樣本總數(shù)。1.4.2類型和屬性的相關(guān)此標(biāo)準(zhǔn)的基本方程為:x2=∑i=1r∑j=1c(xij-Eij)2Eijxij表示屬性取第i個(gè)值,類取第j個(gè)值時(shí)樣本的個(gè)數(shù),Eij=xi。x。jΝ表示在假定屬性和類沒有關(guān)聯(lián)時(shí)xij的期望值。此屬性選擇標(biāo)準(zhǔn)在乳腺癌復(fù)發(fā)統(tǒng)計(jì)數(shù)據(jù)集中的應(yīng)用:對(duì)于屬性RADIATION:x2=(0-1.5)21.5+(3-1.5)21.5+(5-3.5)23.5+(2-3.5)23.5=4.29對(duì)于屬性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所以,根據(jù)x2統(tǒng)計(jì)標(biāo)準(zhǔn),優(yōu)先選擇屬性RADIATION作為節(jié)點(diǎn)生成決策樹。2兩個(gè)屬性間的依賴關(guān)系有許多問題,單一屬性不能傳遞類的信息,需要把幾個(gè)屬性結(jié)合起來才能傳遞類的信息。比如“異或運(yùn)算”,當(dāng)兩個(gè)屬性取值相同時(shí),類的取值為1,當(dāng)兩個(gè)屬性的取值不同時(shí),類的取值為0。此時(shí),兩個(gè)屬性相互依賴共同決定類的狀況。對(duì)于此類問題,就必須在其他屬性的背景下評(píng)估每個(gè)屬性。與屬性間相互獨(dú)立的選擇策略相比,這種方法的運(yùn)算效率比較低,但往往能夠發(fā)現(xiàn)屬性間潛在的依賴關(guān)系。RELIEF算法和CM算法都采用了這種策略,它們都是以基于局部環(huán)境的距離為基礎(chǔ)的。2.1局部屬性的選取一個(gè)數(shù)據(jù)集有n個(gè)屬性,則這n個(gè)屬性就形成了一個(gè)n維空間,稱為實(shí)例空間,數(shù)據(jù)集中的每一個(gè)樣本稱為實(shí)例空間中的一個(gè)實(shí)例。在實(shí)例空間中,一個(gè)實(shí)例和它臨近的實(shí)例共同組成了一個(gè)局部環(huán)境。在局部環(huán)境中可能觀察到一些屬性間的潛在的依賴關(guān)系,而在全局環(huán)境中這些依賴關(guān)系可能會(huì)由于大量實(shí)例的平均作用而被抵消。所以,利用處于局部環(huán)境中的實(shí)例之間的距離作為屬性選取的標(biāo)準(zhǔn),就潛在地考慮了其它屬性對(duì)當(dāng)前屬性的影響。對(duì)于屬性Xi,兩個(gè)實(shí)例r、s在該屬性上的取值分別為和,則兩實(shí)例在此屬性上的分量距離為:如果Xi是分類屬性(categoricalattribute):dirs={0ifxir=x(i)s1ifx(i)r≠x(i)s如果Xi是數(shù)值屬性(numericalattribute):dirs=min((|x(i)r-x(i)s|/ti),1)ti是一個(gè)閾值,通常設(shè)定為屬性取值范圍的一半。實(shí)例空間中兩實(shí)例之間的距離Drs可以定義為歐拉距離,也可定義為如下的Manhatan距離:2.2基于reliff算法的算法RELIEF標(biāo)準(zhǔn)的基本觀念是:一個(gè)理想的屬性,對(duì)于在實(shí)例空間中鄰近的實(shí)例而言,如果它們是同一類的則應(yīng)該有相同的取值,如果它們不是同一類的則應(yīng)該有不同的取值。給定一個(gè)實(shí)例r,RELIEF搜索它的兩個(gè)最近鄰s、t,且s與r不同類,t與r同類,則對(duì)于屬性Xi,RELIEF采用的度量標(biāo)準(zhǔn)為:q(Xi)=∑r(drs,i-drt,i)r∈Τ′?Τ其中集合T′是訓(xùn)練集T的一個(gè)隨機(jī)子集。為了減少數(shù)據(jù)集中的噪聲對(duì)算法的影響,文獻(xiàn)把RELIEF擴(kuò)展為ReliefF算法。在ReliefF算法中,采取的是k最近鄰(k-nearest)策略:給定一個(gè)實(shí)例r,ReliefF搜索實(shí)例r的k個(gè)同類最近鄰,k×(c-1)個(gè)不同類的最近鄰,其中c為數(shù)據(jù)集中數(shù)據(jù)的類數(shù)。對(duì)于屬性Xi,ReliefF采用的度量標(biāo)準(zhǔn)為:q(Xi)=∑r∑C(s)≠C(r)(p(C(s))1-p(C(r))drs,ik)-∑r∑C(s)=C(r)drs,ikC(s)表示實(shí)例s所屬的類,C(r)表示實(shí)例r所屬的類,p(C(s))表示在數(shù)據(jù)集T中與實(shí)例s同類的實(shí)例所占的百分比,p(C(r))表示在數(shù)據(jù)集T中與實(shí)例r同類的實(shí)例所占的百分比。2.3同類的實(shí)例r、s間距離drs的減函數(shù)CM標(biāo)準(zhǔn)的基本觀念:①對(duì)于兩個(gè)不同類的實(shí)例r、s,只有那些取值不同的屬性對(duì)它們具有區(qū)分作用;②對(duì)于某個(gè)屬性,它對(duì)不同類的實(shí)例r、s的區(qū)分作用是r、s間距離Drs的減函數(shù)。對(duì)于②的解釋是,Drs越大則實(shí)例r、s中取值不同的屬性越多,則所有取值不同的屬性共同“分享”這種區(qū)分能力。Drs被稱為實(shí)例r、s的環(huán)境強(qiáng)度。對(duì)于屬性Xi,它的CM標(biāo)準(zhǔn)被定義為:CΜ(Xi)=∑r∑C(s)≠C(r)drs,iDrs2r∈Τ′?Τ其中r是T′中的一個(gè)實(shí)例,s是T′中r的不同類的一個(gè)k近鄰。3屬性選擇標(biāo)準(zhǔn)的多值偏多所謂多值偏向是指屬性選取標(biāo)準(zhǔn)在評(píng)估屬性時(shí),有優(yōu)先選取取值較多的屬性的傾向。多值偏向所帶來的問題是,把屬性在分類中的重要性與屬性取值數(shù)多少關(guān)聯(lián)起來,認(rèn)為取值較多的屬性在分類中具有更重要的作用。例如,假定一個(gè)數(shù)據(jù)集有一個(gè)屬性“年齡”,對(duì)應(yīng)于每一年有一個(gè)取值,而如果數(shù)據(jù)集中每一個(gè)人的年齡都不同,則根據(jù)“年齡”可以對(duì)數(shù)據(jù)集中的數(shù)據(jù)進(jìn)行精確的分類,但這種分類對(duì)其它數(shù)據(jù)集的預(yù)測或者分類沒有任何價(jià)值。如果屬性A具有取值A(chǔ)1,A2,…,An,可以把其中的某個(gè)值拆分為兩個(gè)值,把這組新的取值A(chǔ)′1,A′2,…,A′n,A′n+1賦予屬性A′,然后把屬性選擇標(biāo)準(zhǔn)分別作用在A和A′上,然后通過比較兩者的取值來評(píng)估屬性選取標(biāo)準(zhǔn)的多值偏向,如果后者的取值大于前者,則認(rèn)為此屬性選取標(biāo)準(zhǔn)存在多值偏向問題。應(yīng)用這種方法很容易證明信息增益、Gini-Index、和χ2統(tǒng)計(jì)都具有多值偏向的特征,而RELEF和CM則避免了多值偏向。人