分類決策樹_ID3算法

決策樹,決策樹基本概念,決策樹算法,主要內(nèi)容,決策樹基本概念,決策樹算法,決策樹基本概念,關(guān)于分類問題,分類（Classification）任務(wù)就是通過學(xué)習(xí)獲得一個目標函數(shù)（TargetFunction）f,將每個屬性集x映射到一個預(yù)先定義好的類標號y。,分類任務(wù)的輸入數(shù)據(jù)是紀錄的集合，每條記錄也稱為實例或者樣例。用元組(X,y)表示，其中，X是屬性集合，y是一個特殊的屬性，指出樣例的類標號（也稱為分類屬性或者目標屬性）,決策樹基本概念,關(guān)于分類問題,X,y,分類與回歸,分類目標屬性y是離散的，回歸目標屬性y是連續(xù)的,決策樹基本概念,解決分類問題的一般方法,分類技術(shù)是一種根據(jù)輸入數(shù)據(jù)集建立分類模型的系統(tǒng)方法。分類技術(shù)一般是用一種學(xué)習(xí)算法確定分類模型，該模型可以很好地擬合輸入數(shù)據(jù)中類標號和屬性集之間的聯(lián)系。學(xué)習(xí)算法得到的模型不僅要很好擬合輸入數(shù)據(jù)，還要能夠正確地預(yù)測未知樣本的類標號。因此，訓(xùn)練算法的主要目標就是要建立具有很好的泛化能力模型，即建立能夠準確地預(yù)測未知樣本類標號的模型。分類方法的實例包括：決策樹分類法、基于規(guī)則的分類法、神經(jīng)網(wǎng)絡(luò)、支持向量級、樸素貝葉斯分類方法等。,決策樹基本概念,解決分類問題的一般方法,通過以上對分類問題一般方法的描述，可以看出分類問題一般包括兩個步驟：1、模型構(gòu)建（歸納）通過對訓(xùn)練集合的歸納，建立分類模型。2、預(yù)測應(yīng)用（推論）根據(jù)建立的分類模型，對測試集合進行測試。,決策樹基本概念,解決分類問題的一般方法,學(xué)習(xí)算法,學(xué)習(xí)模型,模型,應(yīng)用模型,訓(xùn)練集（類標號已知）,檢驗集（類標號未知）,歸納,推論,決策樹基本概念,決策樹,決策樹是一種典型的分類方法，首先對數(shù)據(jù)進行處理，利用歸納算法生成可讀的規(guī)則和決策樹，然后使用決策對新數(shù)據(jù)進行分析。本質(zhì)上決策樹是通過一系列規(guī)則對數(shù)據(jù)進行分類的過程。,決策樹基本概念,決策樹的優(yōu)點1、推理過程容易理解，決策推理過程可以表示成IfThen形式；2、推理過程完全依賴于屬性變量的取值特點；3、可自動忽略目標變量沒有貢獻的屬性變量，也為判斷屬性變量的重要性，減少變量的數(shù)目提供參考。,主要內(nèi)容,決策樹基本概念,決策樹算法,決策樹算法,與決策樹相關(guān)的重要算法,1、Hunt,Marin和Stone于1966年研制的CLS學(xué)習(xí)系統(tǒng)，用于學(xué)習(xí)單個概念。2、1979年,J.R.Quinlan給出ID3算法，并在1983年和1986年對ID3進行了總結(jié)和簡化，使其成為決策樹學(xué)習(xí)算法的典型。3、Schlimmer和Fisher于1986年對ID3進行改造，在每個可能的決策樹節(jié)點創(chuàng)建緩沖區(qū)，使決策樹可以遞增式生成，得到ID4算法。4、1988年，Utgoff在ID4基礎(chǔ)上提出了ID5學(xué)習(xí)算法，進一步提高了效率。1993年，Quinlan進一步發(fā)展了ID3算法，改進成C4.5算法。5、另一類決策樹算法為CART，與C4.5不同的是，CART的決策樹由二元邏輯問題生成，每個樹節(jié)點只有兩個分枝，分別包括學(xué)習(xí)實例的正例與反例。,CLS,ID3，C4.5，CART,決策樹算法,假定公司收集了左表數(shù)據(jù)，那么對于任意給定的客人（測試樣例），你能幫助公司將這位客人歸類嗎？即：你能預(yù)測這位客人是屬于“買”計算機的那一類，還是屬于“不買”計算機的那一類？又：你需要多少有關(guān)這位客人的信息才能回答這個問題？,決策樹的用途,誰在買計算機？,年齡？,學(xué)生？,信譽？,青,中,老,否,是,優(yōu),良,決策樹的用途,決策樹算法,誰在買計算機？,年齡？,學(xué)生？,信譽？,青,中,老,否,是,優(yōu),良,決策樹的用途,決策樹算法,決策樹算法,決策樹的表示,決策樹的基本組成部分：決策結(jié)點、分支和葉子。,年齡？,學(xué)生？,信譽？,青,中,老,否,是,優(yōu),良,決策樹中最上面的結(jié)點稱為根結(jié)點。是整個決策樹的開始。每個分支是一個新的決策結(jié)點，或者是樹的葉子。每個決策結(jié)點代表一個問題或者決策.通常對應(yīng)待分類對象的屬性。每個葉結(jié)點代表一種可能的分類結(jié)果,在沿著決策樹從上到下的遍歷過程中，在每個結(jié)點都有一個測試。對每個結(jié)點上問題的不同測試輸出導(dǎo)致不同的分枝，最后會達到一個葉子結(jié)點。這一過程就是利用決策樹進行分類的過程，利用若干個變量來判斷屬性的類別,ID3,決策樹算法,ID3算法主要針對屬性選擇問題。是決策樹學(xué)習(xí)方法中最具影響和最為典型的算法。該方法使用信息增益度選擇測試屬性。當獲取信息時，將不確定的內(nèi)容轉(zhuǎn)為確定的內(nèi)容，因此信息伴著不確定性。從直覺上講，小概率事件比大概率事件包含的信息量大。如果某件事情是“百年一見”則肯定比“習(xí)以為常”的事件包含的信息量大。如何度量信息量的大??？,ID3信息量大小的度量,決策樹算法,Shannon1948年提出的信息論理論。事件ai的信息量I（ai）可如下度量：,其中p(ai)表示事件ai發(fā)生的概率。假設(shè)有n個互不相容的事件a1,a2,a3,.,an,它們中有且僅有一個發(fā)生，則其平均的信息量可如下度量：,ID3信息量大小的度量,決策樹算法,上式，對數(shù)底數(shù)可以為任何數(shù)，不同的取值對應(yīng)了熵的不同單位。通常取2，并規(guī)定當p(ai)=0時=0,信息增益用來衡量給定的屬性區(qū)分訓(xùn)練樣例的能力，中間（間接）表示屬性ID3算法在生成樹的每一步使用信息增益從候選屬性中選擇屬性用熵度量樣例的均一性,決策樹算法,信息增益用熵度量樣例的均一性熵刻畫了任意樣例集合S的純度給定包含關(guān)于某個目標概念的正反樣例的樣例集S，那么S相對這個布爾型分類（函數(shù)）的熵為信息論中對熵的一種解釋：熵確定了要編碼集合S中任意成員的分類所需要的最少二進制位數(shù)；熵值越大，需要的位數(shù)越多。更一般地，如果目標屬性具有c個不同的值，那么S相對于c個狀態(tài)的分類的熵定義為,決策樹算法,用信息增益度量熵的降低程度屬性A的信息增益，使用屬性A分割樣例集合S而導(dǎo)致的熵的降低程度Gain(S,A)是在知道屬性A的值后可以節(jié)省的二進制位數(shù)例子，注意是對當前樣例集合計算上式,理解信息熵,1、信息熵是用來衡量一個隨機變量出現(xiàn)的期望值，一個變量的信息熵越大，那么它出現(xiàn)的各種情況也就越多，也就是包含的內(nèi)容多，我們要描述它就需要付出更多的表達才可以，也就是需要更多的信息才能確定這個變量。2、信息熵是隨機變量的期望。度量信息的不確定程度。信息的熵越大，信息就越不容易搞清楚（雜亂）。3、一個系統(tǒng)越是有序，信息熵就越低；反之，一個系統(tǒng)越是混亂，信息熵就越高。信息熵也可以說是系統(tǒng)有序化程度的一個度量。4、信息熵用以表示一個事物的非確定性，如果該事物的非確定性越高，你的好奇心越重，該事物的信息熵就越高。5、熵是整個系統(tǒng)的平均消息量。信息熵是信息論中用于度量信息量的一個概念。一個系統(tǒng)越是有序，信息熵就越低；反之，一個系統(tǒng)越是混亂，信息熵就越高。6、處理信息就是為了把信息搞清楚，實質(zhì)上就是要想辦法讓信息熵變小。,理解信息增益,熵：表示隨機變量的不確定性。條件熵：在一個條件下，隨機變量的不確定性。信息增益：熵-條件熵。表示在一個條件下，信息不確定性減少的程度。例如：假設(shè)X(明天下雨)的信息熵為2（不確定明天是否下雨），Y(如果是陰天則下雨）的條件熵為0.01（因為如果是陰天就下雨的概率很大，信息就少了）信息增益=2-0.01=1.99。信息增益很大。說明在獲得陰天這個信息后，明天是否下雨的信息不確定性減少了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-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9537,決策樹算法,第2步計算條件屬性的熵,條件屬性共有4個。分別是年齡、收入、學(xué)生、信譽。分別計算不同屬性的信息增益。,決策樹算法,第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步計算年齡的熵,年齡共分三個組：青年、中年、老年中年買與不買比例為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步計算年齡的熵,年齡共分三個組：青年、中年、老年所占比例青年組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步計算學(xué)生的熵,學(xué)生共分二個組：學(xué)生、非學(xué)生E（學(xué)生）=0.7811年齡信息增益=0.9537-0.7811=0.1726（3）,決策樹算法,第5步計算信譽的熵,信譽分二個組：良好，優(yōu)秀E（信譽）=0.9048信譽信息增益=0.9537-0.9048=0.0453（4）,決策樹算法,第6步計算選擇節(jié)點,年齡信息增益=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/384P2=256/384I(S1,S2)=I(128,256)=-P1Log2P1-P2Log2P2=-(P1Log2P1+P2Log2P2)=0.9183,決策樹算法,如果選擇收入作為節(jié)點分高、中、低,平均信息期望（加權(quán)總和）：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,注意,決策樹算法,年齡,青年,中年,老年,學(xué)生,買,信譽,葉子,否,是,優(yōu),良,買,不買,買/不買,買,葉子,葉子,葉子,決策樹算法,ID3決策樹建立算法1決定分類屬性；2對目前的數(shù)據(jù)表，建立一個節(jié)點N3如果數(shù)據(jù)庫中的數(shù)據(jù)都屬于同一個類，N就是樹葉，在樹葉上標出所屬的類4如果數(shù)據(jù)表中沒有其他屬性可以考慮，則N也是樹葉，按照少數(shù)服從多數(shù)的原則在樹葉上標出所屬類別5否則，根據(jù)平均信息期望值E或GAIN值選出一個最佳屬性作為節(jié)點N的測試屬性6節(jié)點屬性選定后，對于該屬性中的每個值：從N生成一個分支，并將數(shù)據(jù)表中與該分支有關(guān)的數(shù)據(jù)收集形成分支節(jié)點的數(shù)據(jù)表，在表中刪除節(jié)點屬性那一欄如果分支數(shù)據(jù)表非空，則運用以上算法從該節(jié)點建立子樹。,決策樹算法,決策樹的數(shù)據(jù)準備,原始表,決策樹算法,整理后的數(shù)據(jù)表,決策樹的數(shù)據(jù)準備,Datacleaning刪除/減少noise，補填missingvaluesDatatransformation數(shù)據(jù)標準化（datanormalization）數(shù)據(jù)歸納（generalizedatatohigher-levelconceptsusingconcepthierarchies）例如：年齡歸納為老、中、青三類控制每個屬性的可能值不超過七種（最好不超過五種）Relevanceanalysis對于與問題無關(guān)的屬性：刪對于屬性的可能值大于七種又不能歸納的屬性：刪,決策樹算法,決策樹的數(shù)據(jù)準備,決策樹算法,處理連續(xù)屬性值,決策樹算法比較適合處理離散數(shù)值的屬性。實際應(yīng)用中屬性是連續(xù)的或者離散的情況都比較常見。在應(yīng)用連續(xù)屬性值時，在一個樹結(jié)點可以將屬性Ai的值劃分為幾個區(qū)間。然后信息增益的計算就可以采用和離散值處理一樣的方法。原則上可以將Ai的屬性劃分為任意數(shù)目的空間。C4.5中采用的是二元分割（BinarySplit）。需要找出一個合適的分割閾值。參考C4.5算法Top10algorithmsindataminingKnowledgeInformationSystem200814:137,決策樹算法,ID3算法小結(jié),ID3算法是一種經(jīng)典的決策樹學(xué)習(xí)算法，由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵為度量，用于決策樹節(jié)點的屬性選擇，每次優(yōu)先選取信息量最多的屬性，亦即能使熵值變?yōu)樽钚〉膶傩?，以?gòu)造一顆熵值下降最快的決策樹，到葉子節(jié)點處的熵值為0。此時，每個葉子節(jié)點對應(yīng)的實例集中的實例屬于同一類。,決策樹算法,ID3算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（1）,通過ID3算法來實現(xiàn)客戶流失的預(yù)警分析，找出客戶流失的特征，以幫助電信公司有針對性地改善客戶關(guān)系，避免客戶流失利用決策樹方法進行數(shù)據(jù)挖掘，一般有如下步驟：數(shù)據(jù)預(yù)處理、決策樹挖掘操作，模式評估和應(yīng)用。電信運營商的客戶流失有三方面的含義：一是指客戶從一個電信運營商轉(zhuǎn)網(wǎng)到其他電信運營商，這是流失分析的重點。二是指客戶月平均消費量降低，從高價值客戶成為低價值客戶。三、指客戶自然流失和被動流失。在客戶流失分析中有兩個核心變量：財務(wù)原因非財務(wù)原因、主動流失被動流失?？蛻袅魇Э梢韵鄳?yīng)分為四種類型：其中非財務(wù)原因主動流失的客戶往往是高價值的客戶。他們會正常支付服務(wù)費用，并容易對市場活動有所響應(yīng)。這種客戶是電信企業(yè)真正需要保住的客戶。,決策樹算法,ID3算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（2）,數(shù)據(jù)預(yù)處理數(shù)據(jù)挖掘的處理對象是大量的數(shù)據(jù)，這些數(shù)據(jù)一般存儲在數(shù)據(jù)庫系統(tǒng)中（該用戶相關(guān)數(shù)據(jù)存儲在其CRM中），是長期積累的結(jié)果。但往往不適合直接挖掘，需要做數(shù)據(jù)的預(yù)處理工作，一般包括數(shù)據(jù)的選擇(選擇相關(guān)的數(shù)據(jù))、凈化(消除冗余數(shù)據(jù))、轉(zhuǎn)換、歸約等。數(shù)據(jù)預(yù)處理工作準備是否充分，對于挖掘算法的效率乃至正確性都有關(guān)鍵性的影響。該公司經(jīng)過多年的電腦化管理，已有大量的客戶個人基本信息(文中簡稱為客戶信息表)。在客戶信息表中，有很多屬性，如姓名用戶號碼、用戶標識、用戶身份證號碼(轉(zhuǎn)化為年齡)、在網(wǎng)時間（竣工時間）、地址、職業(yè)、用戶類別、客戶流失（用戶狀態(tài)）等等，數(shù)據(jù)準備時必須除掉表中一些不必要的屬性，一般可采用面向?qū)傩缘臍w納等方法去掉不相關(guān)或弱相關(guān)屬性。,決策樹算法,ID3算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（3）,屬性刪除：將有大量不同取值且無概化操作符的屬性或者可用其它屬性來代替它的較高層概念的那些屬性刪除。比如客戶信息表中的用戶標識、身份證號碼等，它們的取值太多且無法在該取值域內(nèi)找到概化操作符，應(yīng)將其刪除，得到表1。,決策樹算法,ID3算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（4）,屬性概化：用屬性概化閾值控制技術(shù)沿屬性概念分層上卷或下鉆進行概化。文化程度分為3類：W1初中以下(含初中)，W2高中(含中專)，W3大學(xué)(?？?、本科及以上)；職業(yè)類別：按工作性質(zhì)來分共分3類：Z1一Z3；繳費方式：托收：T1,營業(yè)廳繳費：T2,充值卡：T3。連續(xù)型屬性概化為區(qū)間值：表中年齡、費用變化率和在網(wǎng)時間為連續(xù)型數(shù)據(jù)，由于建立決策樹時，用離散型數(shù)據(jù)進行處理速度最快，因此對連續(xù)型數(shù)據(jù)進行離散化處理，根據(jù)專家經(jīng)驗和實際計算信息增益，在“在網(wǎng)時長”屬性中，通過檢測每個劃分，得到在閾值為5年時信息增益最大，從而確定最好的劃分是在5年處，則這個屬性的范圍就變?yōu)?：H1,H2。而在“年齡”屬性中，信息增益有兩個鋒值，分別在40和50處，因而該屬性的范圍變?yōu)?0-50即變?yōu)榍嗄?，中年，老年：N1,N2,N3；費用變化率：指（當月話費近3個月的平均話費）/近3個月的平均話費）0，F(xiàn)1:30%，F(xiàn)2：30%-99%,F3:100%變?yōu)镕1,F2,F3。,決策樹算法,ID3算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（5）,決策樹算法,ID3算法實際應(yīng)用-在電信行業(yè)應(yīng)用實例（6）,在圖中，NO表示客戶不流失，YES表示客戶流失。從圖可以看出，客戶費用變化率為100%的客戶肯定已經(jīng)流失；而費用變化率低于30%的客戶；即每月資費相對穩(wěn)定的客戶一般不會流失，費用變化率在30%99%的客戶有可能流失，其中年齡在4050歲之間的客戶流失的可能性非常大，而年齡低于40歲的客戶，用充值卡繳費的客戶和在網(wǎng)時間較短的客戶容易流失；年齡較大的客戶，則工人容易流失。,步驟1：生成訓(xùn)練集和測試集生成訓(xùn)練集iris.train=iris2*(1:75)-1,（意思是返回原數(shù)據(jù)集1、3、5、7、8。、149奇數(shù)行行所有列的數(shù)據(jù)）生成測試集iris.test=iris2*(1:75),（意思是返回原數(shù)據(jù)集2、4、6、8、10、。、150偶數(shù)行所有列的數(shù)據(jù)）步驟2：生成決策樹模型model-rpart(SpeciesSepal.Length+Sepal.Width+Petal.Length+Petal.Width,data=iris.train,method=class)繪制決策樹fancyRpartPlot(model)步驟3：對測試集進行預(yù)測iris.rp3=predict(model,iris.test,-5,type=class)注釋：iris.test,-5的意思是去掉原測試集第5列后的數(shù)據(jù)步驟4：查看預(yù)測結(jié)果并對結(jié)果進行分析，計算出該決策樹的accuracy（分類正確的樣本數(shù)除以總樣本數(shù)）table(iris.test,5,iris.rp3)注釋：iris.test,5的意思是取出測試集第5列的數(shù)據(jù)R語言中使用table(data)進行頻數(shù)統(tǒng)計iris.rp3setosaversicolorvirginicasetosa2500versicolor0241virginica0322accuracy=（25+24+22）/75=94.67%步驟5：生成規(guī)則asRules(model),步驟1：生成訓(xùn)練集和測試集生成訓(xùn)練集iris.train=iris2*(1:75)-1,（意思是返回原數(shù)據(jù)集1、3、5、7、8。、149奇數(shù)行行所有列的數(shù)據(jù)）生成測試集iris.test=iris2*(1:75),（意思是返回原數(shù)據(jù)集2、4、6、8、10、。、150偶數(shù)行所有列的數(shù)據(jù)）步驟2：生成決策樹模型model-rpart(SpeciesSepal.Length+Sepal.Width+Petal.Length+Petal.Width,data=iris.train,method=class)繪制決策樹fancyRpartPlot(model)步驟3：對測試集進行預(yù)測iris.rp3=predict(model,iris.test,-5,type=class)注釋：iris.test,-5的意思是去掉原測試集第5列后的數(shù)據(jù)步驟4：查看預(yù)測結(jié)果并對結(jié)果進行分析，計算出該決策樹的accuracy（分類正確的樣本數(shù)除以總樣本數(shù)）table(iris.test,5,iris.rp3)注釋：iris.test,5的意思是取出測試集第5列的數(shù)據(jù)R語言中使用table(data)進行頻數(shù)統(tǒng)計iris.rp3setosaversicolorvirginicasetosa2500versicolor0241virginica0322accuracy=（25+24+22）/75=94.67%步驟5：生成規(guī)則asRules(model),