決策平衡單法和決策樹算法研究

２０PAGEI決策平衡單法當(dāng)我們面臨多種選擇時(shí)，每種選擇對我們都會(huì)產(chǎn)生不同的影響，決策平衡單把這些選擇可能產(chǎn)生的影響放到統(tǒng)一的框架中進(jìn)行分析，引導(dǎo)個(gè)體認(rèn)真思考每種選擇對自身和他人造成的精神和物質(zhì)方面的得失，并按照重要性給每個(gè)因素賦予權(quán)重，之后對每個(gè)選項(xiàng)給出分?jǐn)?shù)。具體步驟為：（1）列出你潛在的3-5個(gè)職業(yè)選項(xiàng)，排列在決策平衡單的頂部。（2）判斷各個(gè)職業(yè)選項(xiàng)的利弊得失，集中于四個(gè)方面進(jìn)行評估，分別是：自我物質(zhì)方面的得失、他人物質(zhì)方面的得失、個(gè)人精神方面的得失，他人精神方面的得失。自我物質(zhì)方面的得失，包括收入、升遷機(jī)會(huì)、工作穩(wěn)定性、工作環(huán)境的安全、休閑時(shí)間、對健康的影響、就業(yè)機(jī)會(huì)、足夠的社會(huì)資源等。他人（父母、師長、配偶等）物質(zhì)方面的得失，包括家庭經(jīng)濟(jì)、家庭地位、與家人相處的時(shí)間等。個(gè)人精神方面的得失，包括興趣的滿足、能力的滿足、價(jià)值觀的滿足，生活方式的改變、成就感、自我實(shí)現(xiàn)的程度、挑戰(zhàn)性等。他人（父母、師長、配偶等）精神方面的得失，包括成就感、自豪感、依賴等。（3）為各考慮項(xiàng)目賦予權(quán)重：對個(gè)人而言，每個(gè)項(xiàng)目的價(jià)值是不同的，個(gè)體可以主觀地給每個(gè)項(xiàng)目賦予權(quán)重（如1-5），一個(gè)項(xiàng)目越重要，其權(quán)重越高，5為最高權(quán)重，表示“非常重要”，3代表“一般”，1代表“最不重要”。（4）給各考慮項(xiàng)目評分，決策者為每個(gè)項(xiàng)目賦予數(shù)值，代表得失程度，“＋”、“－”號代表得與失，分值在-5到5分之間，其中5代表“完全滿足”，0代表“不知道或無法確定”，-5代表“完全不滿足”。（5）逐一計(jì)算各個(gè)職業(yè)選項(xiàng)的得分，與權(quán)重相乘，計(jì)算各個(gè)選項(xiàng)的總分。（6）將每一項(xiàng)目所有正負(fù)積分相加，得出總分。排名各個(gè)職業(yè)選項(xiàng)的優(yōu)先順序，即可作為個(gè)體職業(yè)生涯決策的依據(jù)。生涯決策平衡單樣表選擇項(xiàng)目重要性權(quán)數(shù)（1－5）選擇一選擇二選擇三考慮因素＋－＋－＋－個(gè)人物質(zhì)方面的得失1.收入

2．工作的難易程度

3.升遷的機(jī)會(huì)

4.工作環(huán)境的安全

5.休閑時(shí)間

6.生活變化

7.對健康的影響

8.就業(yè)機(jī)會(huì)

其他……

他人物質(zhì)方面的得失1.家庭經(jīng)濟(jì)

2.家庭地位

3.與家人相處的時(shí)間

其他……

個(gè)人精神方面的得失1.生活方式的改變

2.成就感

3.自我實(shí)現(xiàn)的程度

4.興趣的滿足

5.挑戰(zhàn)性

6.社會(huì)聲望的提高

其他……

他人精神方面的得失1.父母

2.師長

3.配偶

其他……

加權(quán)后合計(jì)

加權(quán)后得失差數(shù)

小案例張莎，巧用求職決策平衡單，成才與就業(yè)，張莎，巧用求職決策平衡單，成才與就業(yè)，2012年Z3期。畢業(yè)前夕，老師把小慧找來談心，希望她能夠繼續(xù)深造，說憑借她現(xiàn)在的基礎(chǔ)，獲得更高的學(xué)歷肯定沒有問題，現(xiàn)在的社會(huì)越來越重視文憑，有了高學(xué)歷何愁沒有好工作？小慧明白老師的意思，自己的?？莆膽{不夠硬，繼續(xù)深造是早晚的事情，憑借自己的努力，將來肯定能找到起點(diǎn)更高的工作，但是，繼續(xù)深造需要支付一筆不小的學(xué)費(fèi)，家里壓力比較大。正當(dāng)小慧難以抉擇的時(shí)候，另一家銷售公司向小慧拋出了橄欖枝，原來這家公司有個(gè)項(xiàng)目急缺一名文字功底扎實(shí)的策劃，公司經(jīng)理看到了小慧的作品非常欣賞，愿意出雙倍工資聘請她。小慧陷入深深迷茫中：一個(gè)是自己心儀的興趣所在，一個(gè)是有發(fā)展?jié)摿Φ纳龑W(xué)之道，一個(gè)是解決家庭燃眉之急的現(xiàn)實(shí)之需，自己該何去何從呢？下面是小輝利用生涯決策平衡單作出的職業(yè)決策的結(jié)果：選擇項(xiàng)目重要性權(quán)數(shù)（1－5）雜志社升學(xué)銷售公司考慮因素＋－＋－＋－個(gè)人物質(zhì)方面的得失1.個(gè)人收入42352.未來發(fā)展32513.休閑時(shí)間12534.對健康的影響2012他人物持方面的得失1.家庭收入52552.家庭地位3213個(gè)人精神方面的得失1.創(chuàng)造性33222.變化性和多樣性32523.影響和幫助他人22114.自由獨(dú)立23525.被認(rèn)可42526.挑戰(zhàn)性33437.應(yīng)用所長35528.興趣的滿足4541他人精神方面的得失1.父親42542.母親42543.弟弟43034.老師4252總分14164147小慧通過生涯決策平衡單的決策之后，她的決策方案的得分是：銷售公司＞雜志社＞升學(xué)深造，綜合平衡之后，銷售公司策劃崗位較為符合小敏的職業(yè)生涯目標(biāo)。通過案例分析，我們能發(fā)現(xiàn)，列舉考慮因素、給每項(xiàng)因素分配權(quán)重以及給各項(xiàng)因素打分的過程，就是決策者理清思路的過程，決策平衡單法提供了一個(gè)思考的框架和過程。

摘要隨著信息科技的高速發(fā)展，人們對于積累的海量數(shù)據(jù)量的處理工作也日益增重，需求是發(fā)明之母，數(shù)據(jù)挖掘技術(shù)就是為了順應(yīng)這種需求而發(fā)展起來的一種數(shù)據(jù)處理技術(shù)。數(shù)據(jù)挖掘技術(shù)又稱數(shù)據(jù)庫中的知識(shí)發(fā)現(xiàn)，是從一個(gè)大規(guī)模的數(shù)據(jù)庫的數(shù)據(jù)中有效地、隱含的、以前未知的、有潛在使用價(jià)值的信息的過程。決策樹算法是數(shù)據(jù)挖掘中重要的分類方法，基于決策樹的各種算法在執(zhí)行速度、可擴(kuò)展性、輸出結(jié)果的可理解性、分類預(yù)測的準(zhǔn)確性等方面各有千秋，在各個(gè)領(lǐng)域廣泛應(yīng)用且已經(jīng)有了許多成熟的系統(tǒng)，如語音識(shí)別、模式識(shí)別和專家系統(tǒng)等。本文著重研究和比較了幾種典型的決策樹算法，并對決策樹算法的應(yīng)用進(jìn)行舉例。關(guān)鍵詞：數(shù)據(jù)挖掘；決策樹；比較AbstractWith

the

rapid

development

of

Information

Technology,

people

are

facing

much

more

work

load

in

dealing

with

the

accumulated

mass

data.Data

mining

technology

is

also

called

the

knowledge

discovery

in

database,

data

from

a

large

database

of

effectively,

implicit,

previously

unknown

and

potentially

use

value

of

information

process.Algorithmofdecisiontreeindataminingisanimportantmethodofclassificationbasedondecisiontreealgorithms,inexecutionspeed,scalability,outputresultcomprehensibility,classificationaccuracy,eachhasitsownmerits.,extensiveapplicationinvariousfieldsandhavemanymaturesystem,suchasspeechrecognition,patternrecognitionandexpertsystemandsoon.Thispaperstudiesandcomparesseveralkindsoftypicaldecisiontreealgorithm,andthealgorithmofdecisiontreeapplicationexamples.Keywords:Datamining;decisiontree；Compare目錄第一章緒論 ５第二章文獻(xiàn)綜述 ５2.1數(shù)據(jù)挖掘簡述 ５2.2決策樹算法背景知識(shí)及研究現(xiàn)狀 ６2.2.1決策樹算法描述 ６2.2.2關(guān)聯(lián)分析決策樹算法研究現(xiàn)狀 ７第三章決策樹算法 ７3.1CLS算法 ７3.2ID3算法 ９3.2.1信息量大小的度量 ９3.2.2ID3決策樹應(yīng)用舉例 １０3.3C4.5算法 １２3.3.1用信息增益率選擇屬性 １３3.3.2處理連續(xù)屬性值 １３3.3樹剪枝 １４3.4weka平臺(tái)的簡述 １４第四章決策樹在學(xué)生成績中的應(yīng)用 １４4.1數(shù)據(jù)的預(yù)處理 １４4.2數(shù)據(jù)的訓(xùn)練集處理 １６4.3數(shù)據(jù)的校驗(yàn)和成績分析 １７第五章結(jié)論 １８參考文獻(xiàn) I5第一章緒論無論在企業(yè)應(yīng)用領(lǐng)域，還是在科學(xué)領(lǐng)域，數(shù)據(jù)挖掘技術(shù)有著廣泛的應(yīng)用價(jià)值。

在企業(yè)應(yīng)用領(lǐng)域，用于制定好的市場策略以及企業(yè)的關(guān)鍵性決策。在商業(yè)面，

數(shù)據(jù)挖掘技術(shù)可以增強(qiáng)企業(yè)的競爭優(yōu)勢，縮短銷售周期，降低生產(chǎn)成本，有助制定市場計(jì)劃和銷售策略，并已經(jīng)成為電子商務(wù)中的關(guān)鍵技術(shù)。

近年來，隨著我國高等教育的飛速發(fā)展，高校的教學(xué)管理信息不斷增多。教學(xué)工作信息化有了很大的進(jìn)步，好多高校在管理學(xué)生和教師信息方面有了很好的方式。比如我校的教務(wù)系統(tǒng)，這些系統(tǒng)為老師和學(xué)生提供了很好的幫助。這些系統(tǒng)中積累了大量的數(shù)據(jù)。目前的這些數(shù)據(jù)庫系統(tǒng)雖然基本上都可以實(shí)現(xiàn)數(shù)據(jù)的錄入、修改、統(tǒng)計(jì)、查詢等功能，但是這些數(shù)據(jù)所隱藏的價(jià)值并沒有被充分的挖掘和利用，信息資源的浪費(fèi)還是比較嚴(yán)重的。為了提高教學(xué)質(zhì)量，將數(shù)據(jù)挖掘技術(shù)引入到高校學(xué)生成績分析中，對這些數(shù)據(jù)進(jìn)行深入的挖掘和合理的分析，從而挖掘出傳統(tǒng)的分析方法所無法得出的結(jié)論。進(jìn)而利用分析結(jié)果引導(dǎo)教學(xué)的開展，從而有利于提高教學(xué)質(zhì)量。第二章文獻(xiàn)綜述數(shù)據(jù)挖掘作為一個(gè)新興的多學(xué)科交叉應(yīng)用領(lǐng)域，正在各行各業(yè)的決策支持活動(dòng)扮演著越來越重要的角色。2.1數(shù)據(jù)挖掘簡述數(shù)據(jù)挖掘（英語：Datamining），又譯為資料探勘、數(shù)據(jù)采礦。它是數(shù)據(jù)庫知識(shí)發(fā)現(xiàn)（英語：Knowledge-DiscoveryinDatabases，簡稱：KDD)中的一個(gè)步驟。數(shù)據(jù)挖掘一般是指從大量的數(shù)據(jù)中自動(dòng)搜索隱藏于其中的有著特殊關(guān)系性（屬于Associationrulelearning）的信息的過程。數(shù)據(jù)挖掘通常與計(jì)算機(jī)科學(xué)有關(guān)，并通過統(tǒng)計(jì)、在線分析處理、情報(bào)檢索、機(jī)器學(xué)習(xí)、專家系統(tǒng)（依靠過去的經(jīng)驗(yàn)法則）和模式識(shí)別等諸多方法來實(shí)現(xiàn)上述目標(biāo)。數(shù)據(jù)挖掘是通過分析每個(gè)數(shù)據(jù)，從大量數(shù)據(jù)中尋找其規(guī)律的技術(shù)，主要有數(shù)據(jù)準(zhǔn)備、規(guī)律尋找和規(guī)律表示3個(gè)步驟。數(shù)據(jù)準(zhǔn)備是從相關(guān)的數(shù)據(jù)源中選取所需的數(shù)據(jù)并整合成用于數(shù)據(jù)挖掘的數(shù)據(jù)集；規(guī)律尋找是用某種方法將數(shù)據(jù)集所含的規(guī)律找出來；規(guī)律表示是盡可能以用戶可理解的方式（如可視化）將找出的規(guī)律表示出來。決策樹是判定給定樣本與某種屬性相關(guān)聯(lián)的決策過程的一種表示方法，從數(shù)據(jù)中生成分類器的一個(gè)特別有效的方法是生成一棵決策樹，該方法廣泛應(yīng)用與數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)等領(lǐng)域，用來解釋用分類相關(guān)的問題，決策樹表示法是應(yīng)用最廣泛的邏輯方法之一。目前生成決策樹方法的算法主要有三種：CART算法、ID3算法和C4.5算法。其中C4.5算法具有分類速度快且精度高的特點(diǎn)，是發(fā)展比較完善的一種決策樹算法。2.2決策樹算法背景知識(shí)及研究現(xiàn)狀2.2.1決策樹算法描述決策樹，顧名思義就是一個(gè)類似于流程圖的樹型結(jié)構(gòu)?！獋€(gè)決策樹由根結(jié)點(diǎn)、分支和葉結(jié)點(diǎn)構(gòu)成。樹的最高層節(jié)點(diǎn)稱為根結(jié)點(diǎn)，是整個(gè)決策樹的開始。與根結(jié)點(diǎn)相連的不同分支，對應(yīng)這個(gè)屬性的不同取值，根據(jù)不同的回答轉(zhuǎn)向相應(yīng)的分支，在新到達(dá)的結(jié)點(diǎn)處做同樣的分支判斷，持續(xù)這一過程直到到達(dá)某個(gè)葉結(jié)點(diǎn)。在決策樹中，每個(gè)內(nèi)部結(jié)點(diǎn)表示一個(gè)測試，該結(jié)點(diǎn)的每個(gè)分支表示該測試的一個(gè)結(jié)果，每個(gè)葉結(jié)點(diǎn)表示一個(gè)類別。例如公司需要預(yù)測某位客人是否要買計(jì)算機(jī)，圖2.1就是為了解決這個(gè)問題而建立的一顆決策樹,從中可以看到?jīng)Q策樹的基本組成部分：根結(jié)點(diǎn)、分支和葉結(jié)點(diǎn)。年齡年齡學(xué)生信譽(yù)買買不買不買買中青老否是優(yōu)良圖2.1決策樹2.2.2關(guān)聯(lián)分析決策樹算法研究現(xiàn)狀決策樹算法廣泛應(yīng)用于各個(gè)領(lǐng)域，已經(jīng)有了廣泛的應(yīng)用并且有許多成熟的系統(tǒng)，如語音識(shí)別、醫(yī)療診斷、模式識(shí)別和專家系統(tǒng)等。目前，決策樹技術(shù)面臨的挑戰(zhàn)表現(xiàn)在以下幾個(gè)方面：(1)可擴(kuò)展性亟待提高。在大型數(shù)據(jù)集中，能從中快速而準(zhǔn)確地發(fā)現(xiàn)隱藏于其中的主要分類規(guī)則，即認(rèn)為算法具有良好的可擴(kuò)展性。數(shù)據(jù)挖掘面臨的數(shù)據(jù)往往是海量的，對實(shí)時(shí)性要求較高的決策場所，數(shù)據(jù)挖掘方法的主動(dòng)性和快速性顯得日益重要。(2)適應(yīng)多數(shù)據(jù)類型和容噪性。隨著計(jì)算機(jī)網(wǎng)絡(luò)和信息的社會(huì)化，數(shù)據(jù)挖掘的對象已不單是關(guān)系數(shù)據(jù)庫模型，而是分布、異構(gòu)的多類型數(shù)據(jù)庫，數(shù)據(jù)的非結(jié)構(gòu)化程度、噪聲等現(xiàn)象越來越突出，這也是決策樹技術(shù)面臨的困難問題。(3)決策樹方法的遞增性。數(shù)據(jù)挖掘出來的知識(shí)，只是相對于某一時(shí)間的某些數(shù)據(jù)，新的數(shù)據(jù)可能使發(fā)現(xiàn)的新知識(shí)與原來的知識(shí)沖突。因此，設(shè)計(jì)具有遞增性決策樹挖掘方法，也是實(shí)用化的基本要求之一。第三章決策樹算法3.1CLS算法CLS算法是早期的決策樹學(xué)習(xí)算法，是許多決策樹學(xué)習(xí)算法的基礎(chǔ)。CLS基本思想：從一棵空決策樹開始，選擇某一屬性作為測試屬性。該測試屬性對應(yīng)決策樹中的決策結(jié)點(diǎn)。根據(jù)該屬性的值的不同，可將訓(xùn)練樣本分成相應(yīng)的子集，如果該子集為空，或該子集中的樣本屬于同一個(gè)類，則該子集為葉結(jié)點(diǎn)，否則該子集對應(yīng)于決策樹的內(nèi)部結(jié)點(diǎn)，即測試結(jié)點(diǎn)，需要選擇一個(gè)新的分類屬性對該子集進(jìn)行劃分，直到所有的子集都為空或者屬于同一類。例1：如表3.1所示為人員眼睛、頭發(fā)顏色與所屬人種之間的關(guān)系：人員眼睛顏色頭發(fā)顏色所屬人種1黑色黑色黃種人2藍(lán)色金色白種人3灰色金色白種人4藍(lán)色紅色白種人5灰色紅色白種人6黑色金色混血7灰色黑色混血8藍(lán)色黑色混血根據(jù)表3.1所提供的信息，選擇“眼睛顏色”為測試屬性，可將該樣本劃分為相應(yīng)的子集如圖3.1所示。眼睛顏色眼睛顏色[1,6][2,4,8][3,5,7]黑色藍(lán)色灰色根據(jù)“眼睛顏色”所劃分的子集中的樣本不屬于同一類，所以選擇新的測試屬性“頭發(fā)顏色”對各個(gè)子集進(jìn)行劃分，如圖3.2所示，所得的樣本屬于同一類，決策樹構(gòu)建完成。眼睛顏色眼睛顏色頭發(fā)顏色頭發(fā)顏色頭發(fā)顏色黑色藍(lán)色灰色白種人[4]白種人[2]混血[7]白種人[6]黃種人[1]混血[8]白種人[5]白種人[3]黑色金色金色紅色黑色金色紅色黑色圖3.2決策樹3.2ID3算法ID3算法是決策樹學(xué)習(xí)算法中最具有影響和最為典型的算法，它的基本思想是，利用信息熵原理，選擇信息增益最大的屬性作為分類屬性。3.2.1信息量大小的度量Shannon1948年提出的信息論理論。事件ai的信息量I(ai)可如下度量：，其中p(ai)表示事件ai發(fā)生的概率。假設(shè)有n個(gè)互不相容的事件a1,a2,a3,……，an，它們中有且僅有一個(gè)發(fā)生，則其平均的信息量可如下度量：=，在決策樹分類中，假設(shè)S是訓(xùn)練樣本集合，|S|是訓(xùn)練樣本數(shù)，樣本劃分為n個(gè)不同的類C1，C2，……Cn，這些類的大小分別標(biāo)記為|C1|，|C2|，……，|Cn|。則任意樣本S屬于類Ci的概率為：。假設(shè)屬性A的所有不同值的集合為XA，Sv是S中屬性A的值為v的樣本子集，在選擇屬性A后的每一個(gè)分支節(jié)點(diǎn)上，對該節(jié)點(diǎn)的樣本集Sv分類的熵為E(Sv)。選擇A導(dǎo)致的期望熵定義為每個(gè)子集Sv的熵的加權(quán)和，權(quán)值為屬于Sv的樣本占原始樣本S的比例,即期望熵為：,屬性A相對樣本集合S的信息增益Gain(S，A)定義為：，其中Gain(S，A)是指因知道屬性A的值后導(dǎo)致的熵的期望壓縮。Gain(S，A)越大，說明選擇測試屬性A對分類提供的信息越多。ID3算法就是將每個(gè)節(jié)點(diǎn)選擇信息增益Gain(S，A)最大的屬性作為測試屬性。3.2.2ID3決策樹應(yīng)用舉例例2：公司收集了數(shù)據(jù)如下表3.2所示，對于任意給定的客人，能否幫助公司將這位客人歸類。表3.2誰在買計(jì)算機(jī)計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買(1)計(jì)算決策屬性的熵決策屬性“買計(jì)算機(jī)？”，該屬性分為兩類：買、不買。S1(買)=641S2(不買)=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1，S2)=I(641,383)=-P1log2P1-P2log2P2=0.9537(2)計(jì)算條件屬性的熵條件屬性共有4個(gè)，分別是年齡、收入、學(xué)生、信譽(yù)。分別計(jì)算不同屬性的信息增益。計(jì)算年齡的熵：年齡共分三個(gè)組：青年、中年、老年青年買與不買比例為128/256P1=128/384P2=256/384I(S1，S2)=I(128,256)=-P1log2P1-P2log2P2=0.9183中年買與不買的比例為256/0P1=256/256P2=0/256I(S1,S2)=I(256,0)=-P1log2P1-P2log2P2=0老年買與不買的比例為257/127P1=257/384P2=127/384I(S1，S2)=I(257,127)=-P1log2P1-P2log2P2=0.9157所占比例：青年組：384/1024=0.375；中年組：256/1024=0.25；老年組：384/1024=0.375計(jì)算年齡的平均信息期望：E(年齡)=0.375*0.9183+0.25*0+0.375*0.9157=0.6877G(年齡)=0.9537-0.6877=0.266計(jì)算收入的熵：收入共分三個(gè)組：高、中、低E(收入)=0.9361G(收入)=0.9537-0.9361=0.0176計(jì)算學(xué)生的熵：學(xué)生共分為兩個(gè)組：學(xué)生、非學(xué)生E(學(xué)生)=0.7811G(學(xué)生)=0.9537-0.7811=0.1726計(jì)算信譽(yù)的熵：信譽(yù)分兩個(gè)組：良好，優(yōu)秀E(信譽(yù))=0.9048G(信譽(yù))=0.9537-0.9048=0.0453(3)計(jì)算選擇結(jié)點(diǎn)：通過以上計(jì)算可知，年齡信息增益值最大，因此選擇年齡屬性進(jìn)行分支，觀察表3.2，當(dāng)年齡為“中”時(shí)，對應(yīng)的歸類都為買，因此該處形成葉結(jié)點(diǎn)；而年齡取“青”、“老”時(shí)，對應(yīng)的歸類不唯一，因此構(gòu)造樹結(jié)構(gòu)如圖3.3：年齡年齡買/不買買/不買買中青老在年齡屬性為青年時(shí)，分別計(jì)算收入信息增益、學(xué)生信息增益、信譽(yù)信息增益可知，在屬性學(xué)生處信息增益值最大，因此取學(xué)生為分支屬性；同理，當(dāng)年齡屬性為老年時(shí)，同樣的計(jì)算可得分支屬性為信譽(yù)。預(yù)測消費(fèi)者是否會(huì)購買電腦的決策樹分類構(gòu)建完成，如圖3.4所示：年齡年齡學(xué)生信譽(yù)買買不買不買買中青老否是優(yōu)良圖3.4誰在買計(jì)算機(jī)3.3C4.5算法C4.5算法是ID3算法的改進(jìn)，它繼承了ID3算法的優(yōu)點(diǎn)并對ID3算法進(jìn)行了改進(jìn)和補(bǔ)充。C4.5算法采用信息增益率作為選擇分支屬性的標(biāo)準(zhǔn)，克服了ID3算法中信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足，并能夠完成對連續(xù)屬性離散化的處理，還能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。3.3.1用信息增益率選擇屬性信息增益率等于信息增益與分裂信息的比值，定義如下：，上式中SplitInfo(A)表示屬性A的分裂信息，分裂信息用來衡量屬性分裂數(shù)據(jù)的廣度和均勻，其定義如下：。根據(jù)例2中提供的信息，可計(jì)算：SplitInfo([384,256,384])=-(0.375*log20.375+0.25*log20.25+0.375*log20.375)=2.999GainRatio(年齡)=gain(年齡)/split([384,256,384])=0.266/2.999=0.089其他的三個(gè)屬性可以類似地得出它們的信息增益率，如下表3.3所示：表3.3屬性對應(yīng)的信息增益率年齡收入Gain0.266Gain0.018SplitInfo2.999SplitInfo1.528GainRatio0.089GainRatio0.012學(xué)生信譽(yù)Gain0.173Gain0.045Splitinfo0.998SplitInfo0.929GainRatio0.173GainRatio0.048利用C4.5算法構(gòu)建決策樹中選取各屬性中信息增益率最大的屬性作為分裂點(diǎn)，以后的做法與ID3的相同，唯一的不同之處是判斷標(biāo)準(zhǔn)由信息增益變成了信息增益率。3.3.2處理連續(xù)屬性值C4.5既可以處理離散型描述屬性，也可以處理連續(xù)性描述屬性。在選擇某結(jié)點(diǎn)上的分枝屬性時(shí)，對于離散型描述屬性，C4.5的處理方法與ID3相同，按照該屬性本身的取值個(gè)數(shù)進(jìn)行計(jì)算；對于某個(gè)連續(xù)性描述屬性，C4.5將作以下處理：(1)對屬性的取值由小到大進(jìn)行排序。(2)兩個(gè)屬性取值之間的中點(diǎn)作為可能的分裂點(diǎn)，將該結(jié)點(diǎn)上的數(shù)據(jù)集分成兩部分，計(jì)算每個(gè)可能的分裂點(diǎn)的信息增益。(3)計(jì)算每一種分割所對應(yīng)的信息增益率，選擇最大的分割點(diǎn)來劃分?jǐn)?shù)據(jù)集。3.3樹剪枝剪枝方法的主要目的是去掉那些噪聲或異常數(shù)據(jù)，使決策樹具有更泛化能力。剪枝常采用統(tǒng)計(jì)度量，剪掉最不可靠的分枝，從而帶來較快的分類，提高樹獨(dú)立于測試數(shù)據(jù)進(jìn)行正確分類的能力。剪枝按其實(shí)施的時(shí)間分為兩種方法：事前修剪法和事后修剪法。C4.5算法采用一種后剪枝方法。事后剪枝是由完全生長的樹剪去分枝。通過刪除結(jié)點(diǎn)的分枝，剪掉樹結(jié)點(diǎn)。它在允許決策樹得到最充分生長的基礎(chǔ)上，再根據(jù)一定的規(guī)則，剪去決策樹中的那些不具有一般代表性的葉結(jié)點(diǎn)或分枝。修剪后，被修剪的分枝結(jié)點(diǎn)就成為一個(gè)葉結(jié)點(diǎn)，并將其標(biāo)記為它所包含樣本中類別個(gè)數(shù)最多的類別。3.4決策樹算法比較分析基于決策樹算法自提出至今種類不下幾十種。各種算法在執(zhí)行速度、可擴(kuò)展性、輸出結(jié)果的可理解性，分類預(yù)測的準(zhǔn)確性等方面各有千秋。最早提出的CLS算法只是給出了生成決策樹系統(tǒng)的框架，卻沒有具體說明算法的內(nèi)容；ID3算法采用信息熵的增益進(jìn)行屬性選擇，但只能處理具