第七章決策樹(shù)和科學(xué)決策與信息分析

第七章決策樹(shù)和決策規(guī)則本章目標(biāo)分析解決分類問(wèn)題的基于邏輯的方法的特性.描述決策樹(shù)和決策規(guī)則在最終分類模型中的表述之間的區(qū)別.介紹C4.5算法.了解采用修剪方法降低決策樹(shù)和決策規(guī)則的復(fù)雜度.決策樹(shù)和決策規(guī)則是解決實(shí)際應(yīng)用中分類問(wèn)題的數(shù)據(jù)挖掘方法。一般來(lái)說(shuō)，分類是把數(shù)據(jù)項(xiàng)映射到其中一個(gè)事先定義的類中的這樣一個(gè)學(xué)習(xí)函數(shù)的過(guò)程。由一組輸入的屬性值向量(也叫屬性向量)和相應(yīng)的類，用基于歸納學(xué)習(xí)算法得出分類。學(xué)習(xí)的目標(biāo)是構(gòu)建一個(gè)分類模型，通常也叫分類器。它可以根據(jù)有效的屬性輸入值預(yù)測(cè)一些實(shí)體(所給樣本)的類。是一個(gè)在樣本其他屬性已知的情況下預(yù)測(cè)另外一個(gè)屬性(樣本的類)的模型(分類的結(jié)果)。7.1決策樹(shù)從數(shù)據(jù)中生成分類器的一個(gè)特別有效的方法是生成一個(gè)決策樹(shù)。它是一種基于邏輯的方法，通過(guò)一組輸入-輸出樣本構(gòu)建決策樹(shù)的有指導(dǎo)學(xué)習(xí)方法。決策樹(shù)包含屬性已被檢驗(yàn)的節(jié)點(diǎn)，一個(gè)節(jié)點(diǎn)的輸出分枝和該節(jié)點(diǎn)的所有可能的檢驗(yàn)結(jié)果相對(duì)應(yīng)。圖7-2是一個(gè)簡(jiǎn)單的決策樹(shù)。該問(wèn)題有兩個(gè)屬性X,Y。所有屬性值X>1和Y>B的樣本屬于類2。不論屬性Y的值是多少，值X<1的樣本都屬于類1。對(duì)于樹(shù)中的非葉節(jié)點(diǎn)，可以沿著分枝繼續(xù)分區(qū)樣本，每一個(gè)節(jié)點(diǎn)得到它相應(yīng)的樣本子集。生成決策樹(shù)的一個(gè)著名的算法是Quinlan的ID3算法，C4.5是它改進(jìn)版。ID3算法的基本思路：從樹(shù)的根節(jié)點(diǎn)處的所有訓(xùn)練樣本開(kāi)始，選取一個(gè)屬性來(lái)劃分這些樣本。對(duì)屬性的每一個(gè)值產(chǎn)生一分枝。分枝屬性值的相應(yīng)樣本子集被移到新生成的子節(jié)點(diǎn)上。這個(gè)算法遞歸地應(yīng)用于每個(gè)子節(jié)點(diǎn)，直到一個(gè)節(jié)點(diǎn)上的所有樣本都分區(qū)到某個(gè)類中。到達(dá)決策樹(shù)的葉節(jié)點(diǎn)的每條路徑表示一個(gè)分類規(guī)則。該算法的關(guān)鍵性決策是對(duì)節(jié)點(diǎn)屬性值的選擇。ID3和C4.5算法的屬性選擇的基礎(chǔ)是基于使節(jié)點(diǎn)所含的信息熵最小化?；谛畔⒄摰姆椒▓?jiān)持對(duì)數(shù)據(jù)庫(kù)中一個(gè)樣本進(jìn)行分類時(shí)所做檢驗(yàn)的數(shù)量最小。ID3的屬性選擇是根據(jù)一個(gè)假設(shè)，即：決策樹(shù)的復(fù)雜度和所給屬性值表達(dá)的信息量是密切相關(guān)的?；谛畔⒌脑囂椒ㄟx擇的是可以給出最高信息的屬性，即這個(gè)屬性是使樣本分類的結(jié)果子樹(shù)所需的信息最小。7.2C4.5算法：生成一個(gè)決策樹(shù)C4.5算法最重要的部分是由一組訓(xùn)練樣本生成一個(gè)初始決策樹(shù)的過(guò)程。決策樹(shù)可以用來(lái)對(duì)一個(gè)新樣本進(jìn)行分類，這種分類從該樹(shù)的根節(jié)點(diǎn)開(kāi)始，然后移動(dòng)樣本直至達(dá)葉節(jié)點(diǎn)。在每個(gè)非葉決策點(diǎn)處，確定該節(jié)點(diǎn)的屬性檢驗(yàn)結(jié)果，把注意力轉(zhuǎn)移到所選擇子樹(shù)的根節(jié)點(diǎn)上。例如，如圖7-3a為決策樹(shù)分類模型，待分類有樣本如圖7-3b所示，由決策樹(shù)分類模型可得出待分類樣本為類2。(節(jié)點(diǎn)A,C,F(葉節(jié)點(diǎn)))C4.5算法的構(gòu)架是基于亨特的CLS方法，其通過(guò)一組訓(xùn)練樣本T構(gòu)造一個(gè)決策樹(shù)。用{C1,C2,…,CK}來(lái)表示這些類，集合T所含的內(nèi)容信息有3種可能性：T包含一個(gè)或更多的樣本，全部屬于單個(gè)的類Cj。那么T的決策樹(shù)是由類Cj標(biāo)識(shí)的一個(gè)葉節(jié)點(diǎn)。T不包含樣本。決策樹(shù)也是一個(gè)葉，但和該葉關(guān)聯(lián)的類由不同于T的信息決定，如T中的絕大多數(shù)類。3.T包含屬于不同類的樣本。這種情況下，是把T精化成朝向一個(gè)單類樣本集的樣本子集。根據(jù)某一屬性，選擇具有一個(gè)或更多互斥的輸出{O1,O2,…,On}的合適檢驗(yàn)。T被分區(qū)成子集T1,T2,…,Tn。T的決策樹(shù)包含標(biāo)識(shí)檢驗(yàn)的一個(gè)決策點(diǎn)和每個(gè)可能輸出的一個(gè)分枝(如圖7-3a中的A,B和C節(jié)點(diǎn))假設(shè)選擇有n個(gè)輸出(所給屬性的n個(gè)值)的檢驗(yàn)，把訓(xùn)練樣本集T分區(qū)成子集T1,T2,…,Tn。僅有的指導(dǎo)信息是在T和它的子集Ti中的類分布。如果S是任意樣本集，設(shè)freq(Ci,S)代表S中屬于Ci的樣本數(shù)量，|S|表示集合S中的樣本數(shù)量。ID3算法的屬性選擇的檢驗(yàn)方法采用增益標(biāo)準(zhǔn)，它基于信息論中熵的概念。集合S的期望信息(熵)如下：T被分區(qū)之后的一個(gè)相似度標(biāo)準(zhǔn)，T按照一個(gè)屬性檢驗(yàn)X的幾個(gè)輸出進(jìn)行分區(qū)。所需信息為子集的熵的加權(quán)和:分區(qū)所對(duì)應(yīng)的信息增益:上式度量了按照檢驗(yàn)X進(jìn)行分區(qū)的T所得到的信息。該增益標(biāo)準(zhǔn)選擇了使Gain(X)最大化的檢驗(yàn)X，即此標(biāo)準(zhǔn)選擇的具有最高增益的那個(gè)屬性。例如：給定訓(xùn)練樣本如表7-1，14個(gè)樣本，3個(gè)屬性，分為兩個(gè)類。9個(gè)樣本屬于類1，5個(gè)屬于類2，因此分區(qū)前的熵為（基于類的熵計(jì)算）

info(T)=-9/14log2(9/14)-5/14log2(5/14)=0.940按屬性1分區(qū)可得子集的熵的加權(quán)和：

infox1(T)=5/14(-2/5log2(2/5)-3/5log2(3/5))+4/14(-4/4log2(4/4)-0/4log2(0/4))+5/14(-3/5log2(3/5)-2/5log2(2/5))=0.694相應(yīng)的增益:Gain(x1)=0.94-0.694=0.246按屬性3分區(qū)可得子集的熵的加權(quán)和：

infox2(T)=6/14(-3/6log2(3/6)-3/6log2(3/6))+8/14(-6/8log2(6/8)-2/8log2(2/8))=0.892相應(yīng)的增益:Gain(x2)=0.94-0.892=0.048由于屬性2是數(shù)值型的連續(xù)數(shù)據(jù)，不能簡(jiǎn)單按上面方式計(jì)算。下面先介紹一下C4.5算法中一般包含3種類型的檢驗(yàn)結(jié)構(gòu)：1.離散值的“標(biāo)準(zhǔn)”檢驗(yàn)，對(duì)屬性的每個(gè)可能值有一個(gè)分枝和輸出。2.如果屬性Y有連續(xù)的數(shù)值，通過(guò)將該值和閾值Z比較，用輸出Y≤Z和Y＞Z定義二元檢驗(yàn)。3.基于離散值的更復(fù)雜的檢驗(yàn)，該檢驗(yàn)中屬性的每個(gè)可能值被分配到許多易變的組中，每組都有一個(gè)輸出和分枝。數(shù)值型屬性檢驗(yàn)：對(duì)于屬性Y，按訓(xùn)練樣本進(jìn)行分類，分類順序用{v1,v2,…,vm}表示，因此對(duì)Y僅有m-1個(gè)分區(qū)，要系統(tǒng)在檢查所有分區(qū)以求得最優(yōu)分區(qū)。通常選擇區(qū)間的中點(diǎn)為閾值。而C4.5算法選擇{vi,vi+1}的最小值vi為閾值。這確保出現(xiàn)結(jié)果中閾值屬于數(shù)據(jù)庫(kù)的一個(gè)值。對(duì)于上例，屬性2的值的集合是:{65,70,75,78,80,85,90,95,96}可能的閾值Z的集合是:{65,70,75,78,80,85,90,95}。從這8個(gè)值里選擇最優(yōu)的閾值(最高信息增益)，最優(yōu)的Z=80。(如果計(jì)算?)對(duì)應(yīng)屬性2的檢驗(yàn)3(屬性2≤80和屬性2＞80)的信息增益計(jì)算：

infox3(T)=9/14(-7/9log2(7/9)-2/9log2(2/9))+5/14(-2/5log2(2/5)-3/5log2(3/5))=0.837相應(yīng)的增益:Gain(x3)=0.94-0.837=0.103屬性1的增益最高，選擇該屬性進(jìn)行首次分區(qū)。每個(gè)屬性值具有一個(gè)分枝，產(chǎn)生3個(gè)分枝，如圖7-4所示.對(duì)每個(gè)分枝重復(fù)上述步驟選擇檢驗(yàn)和最優(yōu)化過(guò)程。對(duì)于子節(jié)點(diǎn)T2子集，4個(gè)樣本都是類1，該節(jié)點(diǎn)是葉節(jié)點(diǎn)。對(duì)于余下的節(jié)點(diǎn)，在T1中有5個(gè)樣本，最優(yōu)檢驗(yàn)有兩個(gè)選擇：屬性2≤70和屬性2＞70的檢驗(yàn)x4。

info(T1)=-2/5log2(2/5)-3/5log2(3/5)=0.940infox4(T1)=2/5(-2/2log2(2/2)-0/2log2(0/2))+3/5(-0/3log2(0/3)-3/3log2(3/3))=0Gain(x3)=0.94-0=0.94產(chǎn)生兩個(gè)分枝為最終葉節(jié)點(diǎn)，分枝中的數(shù)據(jù)子集屬于同一類。對(duì)根節(jié)點(diǎn)下的T3子集進(jìn)行同樣的計(jì)算，按屬性3=真和屬性3=假檢驗(yàn)，產(chǎn)生兩個(gè)葉節(jié)點(diǎn)。圖7-5表示數(shù)據(jù)庫(kù)T的最終決策樹(shù)。另外，決策樹(shù)可以用可執(zhí)行代碼（或偽代碼）的形式表示。圖7-6用偽代碼給出了上面例子的決策樹(shù)。

增益標(biāo)準(zhǔn)對(duì)具有許多輸出的檢驗(yàn)有嚴(yán)重的偏差，根據(jù)info(S)的定義，指定一個(gè)附加的參數(shù)：這表示通過(guò)把集T分區(qū)成n個(gè)子集Ti而生成的潛在信息?，F(xiàn)在，定義一個(gè)新的增益標(biāo)準(zhǔn)：Gain-radio(X)=gain(X)/Split-info(X)

7.3未知屬性值C4.5算法的前一版本是基于所有屬性值都已確定這一假設(shè)。但是在一個(gè)數(shù)據(jù)庫(kù)，經(jīng)常會(huì)缺少某些樣本的一些屬性。由于該屬性值與某個(gè)樣本是不相關(guān)的，或搜集樣本時(shí)沒(méi)有對(duì)它進(jìn)行記錄，或在數(shù)據(jù)錄入時(shí)有人為的誤差，就可能出現(xiàn)屬性值丟失的情況。解決丟失值問(wèn)題的兩種方法：1.拋棄數(shù)據(jù)庫(kù)中有丟失數(shù)據(jù)的樣本。2.定義一個(gè)新的算法或改進(jìn)現(xiàn)有算法來(lái)處理丟失的數(shù)據(jù)。第一種解決方案很簡(jiǎn)單，但當(dāng)樣本集中存在大量丟失值時(shí)不能采用這種方法。在C4.5算法中,有未知值的樣本是按照已知值的相對(duì)頻率隨機(jī)分布的,這是普遍使用的法則。除了考慮到僅有的幾個(gè)有已知屬性值的樣本，Info(T)和Infox(T)的計(jì)算和前面機(jī)相同。然后可以用系數(shù)Ｆ合理地修正增益參數(shù)，該系數(shù)表示所給屬性已知的概率。Ｆ＝數(shù)據(jù)庫(kù)中一個(gè)給出的屬性值具有已知值的樣本的數(shù)量/數(shù)據(jù)集中樣本數(shù)量總和。新的增益標(biāo)準(zhǔn)有以下形式：Gain(x)=F·(Info(T)-Infox(T))同樣，通過(guò)把具有未知值的樣本看作分區(qū)的一個(gè)附加組可以修改Split-info(x)。如果檢驗(yàn)x有n個(gè)輸出，Split-info(x)按照檢驗(yàn)把數(shù)據(jù)集分區(qū)成n+1個(gè)子集計(jì)算。例如：一個(gè)改進(jìn)了的C4.5決策樹(shù)的方法。數(shù)據(jù)集見(jiàn)表7-2。該例有14個(gè)樣本，屬性1有一個(gè)丟失值，用“?”表示。只有13個(gè)樣本數(shù)據(jù)完整。分區(qū)前的熵是：Info(T)=-8/13log2(8/13)-5/13log2(5/13)=0.961屬性1檢驗(yàn)的信息：infox1(T)=5/13(-2/5log2(2/5)-3/5log2(3/5))+3/13(-3/3log2(3/3)-0/3log2(0/3)) +5/13(-3/5log2(3/5)-2/5log2(2/5))=0.747該檢驗(yàn)所獲得的信息系數(shù)F(F=13/14)修正：Gain(x1)=13/14(0.961-0.747)=0.199該值比上個(gè)例子的值0.216小。然后，該分區(qū)信息仍是根據(jù)整個(gè)訓(xùn)練集來(lái)確定的，而且更大，因?yàn)閷?duì)未知值有一個(gè)額外的類別。Split-info(xi)=-(5/14log(5/14)+3/14log(3/14)+5/14log(5/14)+1/14log(1/14))=1.876另外，每個(gè)樣本都有一個(gè)相關(guān)的新參數(shù),即概率。顯然，當(dāng)一個(gè)值已知的樣本從T分配給Ti時(shí)，它屬于Ti的概率是1，屬于其他所有子集的概率是0。當(dāng)一值是未知時(shí)，只能得出不穩(wěn)定的概率描述。因此C4.5和每個(gè)子集Ti中的每個(gè)樣本是用權(quán)重w聯(lián)系起來(lái)的，它表示屬于每個(gè)子集的樣本概率。為了使該解決方法更具一般性，必須認(rèn)為分區(qū)前樣本的概率并不總是等于1。因此，分區(qū)后丟失值的新參數(shù)wnew為：wnew=wold·P(Ti)對(duì)于屬性1的檢驗(yàn)x1分區(qū)結(jié)果，丟失值的記錄將被表示在3個(gè)子集中。如圖7-7所示。因?yàn)樽畛醯?舊的)w值等于1，新的權(quán)值wi等于概率5/13,3/13,和5/13。在C4.5中，Ti的算式如下：|T1|=5+5/13,|T2|=3+3/13,|T3|=5+5/13對(duì)屬性2和屬性3檢驗(yàn)分區(qū)，最終決策樹(shù)如圖7-8中所示的形式。上圖與圖7-6結(jié)構(gòu)相同，但是因?yàn)樽罱K分類的不明確性，每個(gè)決策都以形式(|Ti|/E)和兩個(gè)參數(shù)關(guān)聯(lián)。|Ti|是到葉節(jié)點(diǎn)的部分樣本和，E是屬于除了指定類以外的類的樣本的數(shù)量。2.4/0.4例如，(3.4/0.4)的意思是：3.4(3+5/13)個(gè)訓(xùn)練樣本到達(dá)葉節(jié)點(diǎn)，其中0.4(5/13)并不屬于分配給葉的類?？梢杂冒俜?jǐn)?shù)表示參數(shù)|Ti|和E：3/3.4·100%=所給葉的88%的樣本將被分給類20.4/3.4·100%=所給葉的12%的樣本將被分給類1第3章科學(xué)決策與信息分析主要內(nèi)容：信息分析在決策中的作用；各類型決策中的信息保障；信息分析的工作流程?；疽螅毫私飧黝悰Q策中信息利用的重要性；了解不同決策階段信息服務(wù)的特點(diǎn)；理解決策對(duì)信息的基本要求；掌握信息分析工作的基本流程。3.1信息分析在決策中的作用3.1.1決策活動(dòng)中的信息利用信息分析:是對(duì)情報(bào)進(jìn)行定向濃集和科學(xué)抽象的一種科學(xué)勞動(dòng).信息在軍事戰(zhàn)略制定中的作用；信息在制定地區(qū)經(jīng)濟(jì)發(fā)展規(guī)劃中的作用；信息在科學(xué)管理中的作用；信息在對(duì)外貿(mào)易中的作用；信息在制定生產(chǎn)計(jì)劃中的作用；信息在提高產(chǎn)品質(zhì)量、發(fā)展花色品種中的作用。3.1信息分析在決策中的作用決策階段信息服務(wù)的內(nèi)容與特點(diǎn)決策前（超前服務(wù)）促成決策及早完成（快）；有助于決策者掌握預(yù)測(cè)性信息（準(zhǔn)）；有助于決策者更新知識(shí)、增強(qiáng)判斷力（增）決策中（跟蹤服務(wù)）確立目標(biāo)階段；決策方案準(zhǔn)備階段；選定決策方案階段。決策后（反饋服務(wù)）跟蹤反饋；循環(huán)反饋；同步追蹤反饋。3.1.2不同決策階段的信息服務(wù)3.1信息分析在決策中的作用3.1.3決策對(duì)信息的基本要求可靠性（可信度）——信息的真實(shí)性和準(zhǔn)確性。信息源；信息獲取手段；信息獲取的條件。完整性（完全度）——包括決策對(duì)象全部的信息全面收集歷史的、現(xiàn)實(shí)的和未來(lái)的信息；兼顧反映正面的和反面問(wèn)題的信息。精確性（精確度）——反映事物特征的細(xì)微化程度。不同決策對(duì)信息的精確度要求不同；劃定范圍，確定上限和下限。3.2各類型決策中的信息保障3.2.1新產(chǎn)品研制的信息保障創(chuàng)意產(chǎn)生與篩選階段的信息保障創(chuàng)意產(chǎn)生于對(duì)信息的收集、吸收和理解；創(chuàng)意孕育著新產(chǎn)品，要盡可能多的收集；篩選是從多個(gè)創(chuàng)意中選擇出具有開(kāi)發(fā)價(jià)值項(xiàng)目的過(guò)程，其要求是：新意；可行；實(shí)用；有效。3.2各類型決策中的信息保障3.2.1新產(chǎn)品研制的信息保障開(kāi)發(fā)決策階段的信息保障主要任務(wù)是針對(duì)經(jīng)過(guò)初步篩選出的幾個(gè)創(chuàng)意中的每一個(gè)新產(chǎn)品開(kāi)發(fā)構(gòu)想收集信息；主要目的是從若干初步入選的新產(chǎn)品開(kāi)發(fā)設(shè)想中挑選一個(gè)，作為本企業(yè)的新產(chǎn)品研制項(xiàng)目。新產(chǎn)品設(shè)計(jì)階段的信息保障方案設(shè)計(jì)：正確選型，確定新產(chǎn)品的基本結(jié)構(gòu)和基本參數(shù)。技術(shù)設(shè)計(jì)：確定產(chǎn)品的具體結(jié)構(gòu)和形式，進(jìn)行各部分、各部件的設(shè)計(jì)和組裝設(shè)計(jì)。施工設(shè)計(jì)：繪制新產(chǎn)品試制所需的全套圖紙，編制有關(guān)制造工藝的全部文件。3.2各類型決策中的信息保障3.2.2對(duì)外經(jīng)濟(jì)貿(mào)易中的信息保障法律信息保障