分類決策樹_ID3算法

《分類決策樹_ID3算法》由會員分享，可在線閱讀，更多相關《分類決策樹_ID3算法（51頁珍藏版）》請在裝配圖網上搜索。

1、決策樹,決策樹基本概念,決策樹算法,主要內容,決策樹基本概念,決策樹算法,決策樹基本概念,關于分類問題,分類（Classification）任務就是通過學習獲得一個目標函數（TargetFunction）f,將每個屬性集x映射到一個預先定義好的類標號y。,分類任務的輸入數據是紀錄的集合，每條記錄也稱為實例或者樣例。用元組(X,y)表示，其中，X是屬性集合，y是一個特殊的屬性，指出樣例的類標號（也稱為分類屬性或者目標屬性）,決策樹基本概念,關于分類問題,X,y,分類與回歸,分類目標屬性y是離散的，回歸目標屬性y是連續的,決策樹基本概念,解決分類問題的一般方法,分類技術是一種根據輸入數據集建立分類

2、模型的系統方法。分類技術一般是用一種學習算法確定分類模型，該模型可以很好地擬合輸入數據中類標號和屬性集之間的聯系。學習算法得到的模型不僅要很好擬合輸入數據，還要能夠正確地預測未知樣本的類標號。因此，訓練算法的主要目標就是要建立具有很好的泛化能力模型，即建立能夠準確地預測未知樣本類標號的模型。分類方法的實例包括：決策樹分類法、基于規則的分類法、神經網絡、支持向量級、樸素貝葉斯分類方法等。,決策樹基本概念,解決分類問題的一般方法,通過以上對分類問題一般方法的描述，可以看出分類問題一般包括兩個步驟：1、模型構建（歸納）通過對訓練集合的歸納，建立分類模型。2、預測應用（推論）根據建立的分類模型，對測試

3、集合進行測試。,決策樹基本概念,解決分類問題的一般方法,學習算法,學習模型,模型,應用模型,訓練集（類標號已知）,檢驗集（類標號未知）,歸納,推論,決策樹基本概念,決策樹,決策樹是一種典型的分類方法，首先對數據進行處理，利用歸納算法生成可讀的規則和決策樹，然后使用決策對新數據進行分析。本質上決策樹是通過一系列規則對數據進行分類的過程。,決策樹基本概念,決策樹的優點1、推理過程容易理解，決策推理過程可以表示成IfThen形式；2、推理過程完全依賴于屬性變量的取值特點；3、可自動忽略目標變量沒有貢獻的屬性變量，也為判斷屬性變量的重要性，減少變量的數目提供參考。,主要內容,決策樹基本概念,決策樹算法

4、,決策樹算法,與決策樹相關的重要算法,1、Hunt,Marin和Stone于1966年研制的CLS學習系統，用于學習單個概念。2、1979年,J.R.Quinlan給出ID3算法，并在1983年和1986年對ID3進行了總結和簡化，使其成為決策樹學習算法的典型。3、Schlimmer和Fisher于1986年對ID3進行改造，在每個可能的決策樹節點創建緩沖區，使決策樹可以遞增式生成，得到ID4算法。4、1988年，Utgoff在ID4基礎上提出了ID5學習算法，進一步提高了效率。1993年，Quinlan進一步發展了ID3算法，改進成C4.5算法。5、另一類決策樹算法為CART，與C4.5不同

5、的是，CART的決策樹由二元邏輯問題生成，每個樹節點只有兩個分枝，分別包括學習實例的正例與反例。,CLS,ID3，C4.5，CART,決策樹算法,假定公司收集了左表數據，那么對于任意給定的客人（測試樣例），你能幫助公司將這位客人歸類嗎？即：你能預測這位客人是屬于“買”計算機的那一類，還是屬于“不買”計算機的那一類？又：你需要多少有關這位客人的信息才能回答這個問題？,決策樹的用途,誰在買計算機？,年齡？,學生？,信譽？,青,中,老,否,是,優,良,決策樹的用途,決策樹算法,誰在買計算機？,年齡？,學生？,信譽？,青,中,老,否,是,優,良,決策樹的用途,決策樹算法,決策樹算法,決策樹的表示,決策

6、樹的基本組成部分：決策結點、分支和葉子。,年齡？,學生？,信譽？,青,中,老,否,是,優,良,決策樹中最上面的結點稱為根結點。是整個決策樹的開始。每個分支是一個新的決策結點，或者是樹的葉子。每個決策結點代表一個問題或者決策.通常對應待分類對象的屬性。每個葉結點代表一種可能的分類結果,在沿著決策樹從上到下的遍歷過程中，在每個結點都有一個測試。對每個結點上問題的不同測試輸出導致不同的分枝，最后會達到一個葉子結點。這一過程就是利用決策樹進行分類的過程，利用若干個變量來判斷屬性的類別,ID3,決策樹算法,ID3算法主要針對屬性選擇問題。是決策樹學習方法中最具影響和最為典型的算法。該方法使用信息增益度選

7、擇測試屬性。當獲取信息時，將不確定的內容轉為確定的內容，因此信息伴著不確定性。從直覺上講，小概率事件比大概率事件包含的信息量大。如果某件事情是“百年一見”則肯定比“習以為?！钡氖录男畔⒘看?。如何度量信息量的大小？,ID3信息量大小的度量,決策樹算法,Shannon1948年提出的信息論理論。事件ai的信息量I（ai）可如下度量：,其中p(ai)表示事件ai發生的概率。假設有n個互不相容的事件a1,a2,a3,.,an,它們中有且僅有一個發生，則其平均的信息量可如下度量：,ID3信息量大小的度量,決策樹算法,上式，對數底數可以為任何數，不同的取值對應了熵的不同單位。通常取2，并規定當p(a

8、i)=0時=0,信息增益用來衡量給定的屬性區分訓練樣例的能力，中間（間接）表示屬性ID3算法在生成樹的每一步使用信息增益從候選屬性中選擇屬性用熵度量樣例的均一性,決策樹算法,信息增益用熵度量樣例的均一性熵刻畫了任意樣例集合S的純度給定包含關于某個目標概念的正反樣例的樣例集S，那么S相對這個布爾型分類（函數）的熵為信息論中對熵的一種解釋：熵確定了要編碼集合S中任意成員的分類所需要的最少二進制位數；熵值越大，需要的位數越多。更一般地，如果目標屬性具有c個不同的值，那么S相對于c個狀態的分類的熵定義為,決策樹算法,用信息增益度量熵的降低程度屬性A的信息增益，使用屬性A分割樣例集合S而導致的熵的降低程

9、度Gain(S,A)是在知道屬性A的值后可以節省的二進制位數例子，注意是對當前樣例集合計算上式,理解信息熵,1、信息熵是用來衡量一個隨機變量出現的期望值，一個變量的信息熵越大，那么它出現的各種情況也就越多，也就是包含的內容多，我們要描述它就需要付出更多的表達才可以，也就是需要更多的信息才能確定這個變量。2、信息熵是隨機變量的期望。度量信息的不確定程度。信息的熵越大，信息就越不容易搞清楚（雜亂）。3、一個系統越是有序，信息熵就越低；反之，一個系統越是混亂，信息熵就越高。信息熵也可以說是系統有序化程度的一個度量。4、信息熵用以表示一個事物的非確定性，如果該事物的非確定性越高，你的好奇心越重，該事物

10、的信息熵就越高。5、熵是整個系統的平均消息量。信息熵是信息論中用于度量信息量的一個概念。一個系統越是有序，信息熵就越低；反之，一個系統越是混亂，信息熵就越高。6、處理信息就是為了把信息搞清楚，實質上就是要想辦法讓信息熵變小。,理解信息增益,熵：表示隨機變量的不確定性。條件熵：在一個條件下，隨機變量的不確定性。信息增益：熵-條件熵。表示在一個條件下，信息不確定性減少的程度。例如：假設X(明天下雨)的信息熵為2（不確定明天是否下雨），Y(如果是陰天則下雨）的條件熵為0.01（因為如果是陰天就下雨的概率很大，信息就少了）信息增益=2-0.01=1.99。信息增益很大。說明在獲得陰天這個信息后，明天是

11、否下雨的信息不確定性減少了1.99，是很多的，所以信息增益大。也就是說陰天這個信息對下雨來說是很重要的。,ID3信息量大小的度量,決策樹算法,Gain（S，A）是屬性A在集合S上的信息增益Gain（S，A）=Entropy（S）-Entropy（S，A）Gain（S，A）越大，說明選擇測試屬性對分類提供的信息越多,決策樹算法,第1步計算決策屬性的熵,決策屬性“買計算機？”。該屬性分兩類：買/不買S1(買)=641S2（不買）=383S=S1+S2=1024P1=641/1024=0.6260P2=383/1024=0.3740I(S1,S2)=I(641,383)=-P1Log2P1-P2Lo

12、g2P2=-(P1Log2P1+P2Log2P2)=0.9537,決策樹算法,第2步計算條件屬性的熵,條件屬性共有4個。分別是年齡、收入、學生、信譽。分別計算不同屬性的信息增益。,決策樹算法,第2-1步計算年齡的熵,年齡共分三個組：青年、中年、老年青年買與不買比例為128/256S1(買)=128S2（不買）=256S=S1+S2=384P1=128/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183,決策樹算法,第2-2步計算年齡的熵,年齡共分三個組：青年、中年、老年中年買與不買比例為

13、256/0S1(買)=256S2（不買）=0S=S1+S2=256P1=256/256P2=0/256I(S1,S2)=I(256，0)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0,決策樹算法,第2-3步計算年齡的熵,年齡共分三個組：青年、中年、老年老年買與不買比例為257/127S1(買)=257S2（不買）=127S=S1+S2=384P1=257/384P2=127/384I(S1,S2)=I(257，127)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9157,決策樹算法,第2-4步計算年齡的熵,年齡共分

14、三個組：青年、中年、老年所占比例青年組384/1025=0.375中年組256/1024=0.25老年組384/1024=0.375計算年齡的平均信息期望E（年齡）=0.375*0.9183+0.25*0+0.375*0.9157=0.6877G（年齡信息增益）=0.9537-0.6877=0.2660（1）,決策樹算法,第3步計算收入的熵,收入共分三個組：高、中、低E（收入）=0.9361收入信息增益=0.9537-0.9361=0.0176(2),決策樹算法,第4步計算學生的熵,學生共分二個組：學生、非學生E（學生）=0.7811年齡信息增益=0.9537-0.7811=0.1726（3）

15、,決策樹算法,第5步計算信譽的熵,信譽分二個組：良好，優秀E（信譽）=0.9048信譽信息增益=0.9537-0.9048=0.0453（4）,決策樹算法,第6步計算選擇節點,年齡信息增益=0.9537-0.6877=0.2660（1）收入信息增益=0.9537-0.9361=0.0176（2）年齡信息增益=0.9537-0.7811=0.1726（3）信譽信息增益=0.9537-0.9048=0.0453（4）,決策樹算法,年齡,青年,中年,老年,買/不買,買,買/不買,葉子,決策樹算法,青年買與不買比例為128/256S1(買)=128S2（不買）=256S=S1+S2=384P1=128

16、/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183,決策樹算法,如果選擇收入作為節點分高、中、低,平均信息期望（加權總和）：E(收入）=0.3333*0+0.5*0.9183+0.1667*0=0.4592Gain(收入)=I(128,256)-E(收入)=0.91830.4592=0.4591,I(0,128)=0比例:128/384=0.3333I(64,128)=0.9183比例:192/384=0.5I(64,0)=0比例:64/384=0.1667,注意,決策樹算法,年齡,青

17、年,中年,老年,學生,買,信譽,葉子,否,是,優,良,買,不買,買/不買,買,葉子,葉子,葉子,決策樹算法,ID3決策樹建立算法1決定分類屬性；2對目前的數據表，建立一個節點N3如果數據庫中的數據都屬于同一個類，N就是樹葉，在樹葉上標出所屬的類4如果數據表中沒有其他屬性可以考慮，則N也是樹葉，按照少數服從多數的原則在樹葉上標出所屬類別5否則，根據平均信息期望值E或GAIN值選出一個最佳屬性作為節點N的測試屬性6節點屬性選定后，對于該屬性中的每個值：從N生成一個分支，并將數據表中與該分支有關的數據收集形成分支節點的數據表，在表中刪除節點屬性那一欄如果分支數據表非空，則運用以上算法從該節點建立子樹

18、。,決策樹算法,決策樹的數據準備,原始表,決策樹算法,整理后的數據表,決策樹的數據準備,Datacleaning刪除/減少noise，補填missingvaluesDatatransformation數據標準化（datanormalization）數據歸納（generalizedatatohigher-levelconceptsusingconcepthierarchies）例如：年齡歸納為老、中、青三類控制每個屬性的可能值不超過七種（最好不超過五種）Relevanceanalysis對于與問題無關的屬性：刪對于屬性的可能值大于七種又不能歸納的屬性：刪,決策樹算法,決策樹的數據準備,決策樹算法

19、,處理連續屬性值,決策樹算法比較適合處理離散數值的屬性。實際應用中屬性是連續的或者離散的情況都比較常見。在應用連續屬性值時，在一個樹結點可以將屬性Ai的值劃分為幾個區間。然后信息增益的計算就可以采用和離散值處理一樣的方法。原則上可以將Ai的屬性劃分為任意數目的空間。C4.5中采用的是二元分割（BinarySplit）。需要找出一個合適的分割閾值。參考C4.5算法Top10algorithmsindataminingKnowledgeInformationSystem200814:137,決策樹算法,ID3算法小結,ID3算法是一種經典的決策樹學習算法，由Quinlan于1979年提出。ID3算

20、法的基本思想是，以信息熵為度量，用于決策樹節點的屬性選擇，每次優先選取信息量最多的屬性，亦即能使熵值變為最小的屬性，以構造一顆熵值下降最快的決策樹，到葉子節點處的熵值為0。此時，每個葉子節點對應的實例集中的實例屬于同一類。,決策樹算法,ID3算法實際應用-在電信行業應用實例（1）,通過ID3算法來實現客戶流失的預警分析，找出客戶流失的特征，以幫助電信公司有針對性地改善客戶關系，避免客戶流失利用決策樹方法進行數據挖掘，一般有如下步驟：數據預處理、決策樹挖掘操作，模式評估和應用。電信運營商的客戶流失有三方面的含義：一是指客戶從一個電信運營商轉網到其他電信運營商，這是流失分析的重點。二是指客戶月平均

21、消費量降低，從高價值客戶成為低價值客戶。三、指客戶自然流失和被動流失。在客戶流失分析中有兩個核心變量：財務原因非財務原因、主動流失被動流失?？蛻袅魇Э梢韵鄳譃樗姆N類型：其中非財務原因主動流失的客戶往往是高價值的客戶。他們會正常支付服務費用，并容易對市場活動有所響應。這種客戶是電信企業真正需要保住的客戶。,決策樹算法,ID3算法實際應用-在電信行業應用實例（2）,數據預處理數據挖掘的處理對象是大量的數據，這些數據一般存儲在數據庫系統中（該用戶相關數據存儲在其CRM中），是長期積累的結果。但往往不適合直接挖掘，需要做數據的預處理工作，一般包括數據的選擇(選擇相關的數據)、凈化(消除冗余數據)、轉

22、換、歸約等。數據預處理工作準備是否充分，對于挖掘算法的效率乃至正確性都有關鍵性的影響。該公司經過多年的電腦化管理，已有大量的客戶個人基本信息(文中簡稱為客戶信息表)。在客戶信息表中，有很多屬性，如姓名用戶號碼、用戶標識、用戶身份證號碼(轉化為年齡)、在網時間（竣工時間）、地址、職業、用戶類別、客戶流失（用戶狀態）等等，數據準備時必須除掉表中一些不必要的屬性，一般可采用面向屬性的歸納等方法去掉不相關或弱相關屬性。,決策樹算法,ID3算法實際應用-在電信行業應用實例（3）,屬性刪除：將有大量不同取值且無概化操作符的屬性或者可用其它屬性來代替它的較高層概念的那些屬性刪除。比如客戶信息表中的用戶標識、

23、身份證號碼等，它們的取值太多且無法在該取值域內找到概化操作符，應將其刪除，得到表1。,決策樹算法,ID3算法實際應用-在電信行業應用實例（4）,屬性概化：用屬性概化閾值控制技術沿屬性概念分層上卷或下鉆進行概化。文化程度分為3類：W1初中以下(含初中)，W2高中(含中專)，W3大學(專科、本科及以上)；職業類別：按工作性質來分共分3類：Z1一Z3；繳費方式：托收：T1,營業廳繳費：T2,充值卡：T3。連續型屬性概化為區間值：表中年齡、費用變化率和在網時間為連續型數據，由于建立決策樹時，用離散型數據進行處理速度最快，因此對連續型數據進行離散化處理，根據專家經驗和實際計算信息增益，在“在網時長”屬性

24、中，通過檢測每個劃分，得到在閾值為5年時信息增益最大，從而確定最好的劃分是在5年處，則這個屬性的范圍就變為5：H1,H2。而在“年齡”屬性中，信息增益有兩個鋒值，分別在40和50處，因而該屬性的范圍變為40-50即變為青年，中年，老年：N1,N2,N3；費用變化率：指（當月話費近3個月的平均話費）/近3個月的平均話費）0，F1:30%，F2：30%-99%,F3:100%變為F1,F2,F3。,決策樹算法,ID3算法實際應用-在電信行業應用實例（5）,決策樹算法,ID3算法實際應用-在電信行業應用實例（6）,在圖中，NO表示客戶不流失，YES表示客戶流失。從圖可以看出，客戶費用變化率為100%

25、的客戶肯定已經流失；而費用變化率低于30%的客戶；即每月資費相對穩定的客戶一般不會流失，費用變化率在30%99%的客戶有可能流失，其中年齡在4050歲之間的客戶流失的可能性非常大，而年齡低于40歲的客戶，用充值卡繳費的客戶和在網時間較短的客戶容易流失；年齡較大的客戶，則工人容易流失。,步驟1：生成訓練集和測試集生成訓練集iris.train=iris2*(1:75)-1,（意思是返回原數據集1、3、5、7、8。、149奇數行行所有列的數據）生成測試集iris.test=iris2*(1:75),（意思是返回原數據集2、4、6、8、10、。、150偶數行所有列的數據）步驟2：生成決策樹模型mod

26、el-rpart(SpeciesSepal.Length+Sepal.Width+Petal.Length+Petal.Width,data=iris.train,method=class)繪制決策樹fancyRpartPlot(model)步驟3：對測試集進行預測iris.rp3=predict(model,iris.test,-5,type=class)注釋：iris.test,-5的意思是去掉原測試集第5列后的數據步驟4：查看預測結果并對結果進行分析，計算出該決策樹的accuracy（分類正確的樣本數除以總樣本數）table(iris.test,5,iris.rp3)注釋：iris.te

27、st,5的意思是取出測試集第5列的數據R語言中使用table(data)進行頻數統計iris.rp3setosaversicolorvirginicasetosa2500versicolor0241virginica0322accuracy=（25+24+22）/75=94.67%步驟5：生成規則asRules(model),步驟1：生成訓練集和測試集生成訓練集iris.train=iris2*(1:75)-1,（意思是返回原數據集1、3、5、7、8。、149奇數行行所有列的數據）生成測試集iris.test=iris2*(1:75),（意思是返回原數據集2、4、6、8、10、。、150偶數行

28、所有列的數據）步驟2：生成決策樹模型model-rpart(SpeciesSepal.Length+Sepal.Width+Petal.Length+Petal.Width,data=iris.train,method=class)繪制決策樹fancyRpartPlot(model)步驟3：對測試集進行預測iris.rp3=predict(model,iris.test,-5,type=class)注釋：iris.test,-5的意思是去掉原測試集第5列后的數據步驟4：查看預測結果并對結果進行分析，計算出該決策樹的accuracy（分類正確的樣本數除以總樣本數）table(iris.test,5,iris.rp3)注釋：iris.test,5的意思是取出測試集第5列的數據R語言中使用table(data)進行頻數統計iris.rp3setosaversicolorvirginicasetosa2500versicolor0241virginica0322accuracy=（25+24+22）/75=94.67%步驟5：生成規則asRules(model),