《Python金融數(shù)據(jù)挖掘》高等教育出版第九章決策樹分類算法【知識(shí)框架圖】決策樹分類算法應(yīng)用場(chǎng)景與研究意義信息熵熵的概念、意義與計(jì)算熵增益與熵增益率ID3算法流程與實(shí)現(xiàn)C4.5算法流程與實(shí)現(xiàn)目錄Contents第一節(jié)決策樹算法原理第二節(jié)Python代碼實(shí)現(xiàn)第三節(jié)案例本章學(xué)習(xí)目標(biāo)了解決策樹分類算法研究的對(duì)象、意義和應(yīng)用場(chǎng)景。掌握信息熵的概念、意義和計(jì)算方法。掌握熵增益、熵增益率的概念、意義和計(jì)算方法。掌握ID3、C4.5決策樹算法的原理和實(shí)現(xiàn)方法。需求背景在日常生活中，我們所做出的決策往往要根據(jù)一系列現(xiàn)有條件和過去經(jīng)驗(yàn)。例如，當(dāng)某只股票的技術(shù)指標(biāo)呈現(xiàn)出某種狀態(tài)時(shí)，反映了基本面的某些信息，借助歷史經(jīng)驗(yàn)可以推斷該股票價(jià)格有較大的可能上行（或下行）。這種根據(jù)歷史數(shù)據(jù)提煉出規(guī)則，并以現(xiàn)有信息為基礎(chǔ)形成決策，在數(shù)據(jù)挖掘領(lǐng)域中，我們稱之為決策樹分類算法。決策樹（DecisionTree）是一種十分常用的分類方法，屬于監(jiān)督學(xué)習(xí)（SupervisedLearning）。監(jiān)督學(xué)習(xí)就是給出一批樣本，每個(gè)樣本都有一組屬性和一個(gè)分類結(jié)果（即類標(biāo)簽已知），算法通過學(xué)習(xí)這些樣本，得到一個(gè)決策樹，這個(gè)決策樹能夠?qū)π碌臄?shù)據(jù)給出合適的分類。01決策樹算法原理為便于理解決策樹的結(jié)構(gòu)，先給出一個(gè)成績(jī)等級(jí)評(píng)定決策樹的例子，如圖9-2所示。序號(hào)外型性格職業(yè)上進(jìn)心交往？1帥不好一般否否2不帥好一般上進(jìn)否3帥好一般上進(jìn)是4不帥爆好好上進(jìn)是5帥不好一般上進(jìn)否6帥不好一般上進(jìn)否7帥好好否是8不帥好較好上進(jìn)是9帥爆好較好上進(jìn)是10不帥不好好上進(jìn)是11帥好一般否否12帥好一般否否圖9?2成績(jī)判定決策樹表9?1女生交往判別具備編程知識(shí)的讀者很快發(fā)現(xiàn)，這是一個(gè)由分支/選擇判斷構(gòu)成的判定流程。在這個(gè)流程中，依次檢查是否滿足某個(gè)特定條件，得到一個(gè)最終結(jié)果或進(jìn)入下一步判斷。上述流程是已知輸入成績(jī)和判定規(guī)則，求判定結(jié)果。對(duì)于數(shù)據(jù)挖掘而言，這個(gè)過程是可逆轉(zhuǎn)的：已知輸入成績(jī)和最終的判定結(jié)果，要求決策樹算法能夠生成如圖9-2所示的判定樹/決策樹。例如，有統(tǒng)計(jì)女生根據(jù)男生條件決定是否交往的數(shù)據(jù)，如表9-1所示。男生們希望根據(jù)表9-1中的數(shù)據(jù)，生成決策樹，從而了解女生的決策過程。通過仔細(xì)觀察表9-1中的數(shù)據(jù)發(fā)現(xiàn)，“職業(yè)”是決定性的因素，“職業(yè)”是“好”或者“較好”的男生，“交往”結(jié)果都是“是”。因此，可以認(rèn)為選擇“職業(yè)”這個(gè)因素作為首次決策的依據(jù)時(shí)，區(qū)分效果會(huì)很好。那么，有什么量化的手段來幫助我們?cè)u(píng)估這些因素，進(jìn)而做出高效的選擇呢？信息熵信息熵（InformationEntropy）可以用來評(píng)估因素指標(biāo)的重要程度。假定有隨機(jī)變量X={x1，x2，…，xn}，X中第i類樣本xi所占的比例為p(x_i)，則X的信息熵定義為：簡(jiǎn)單地說，計(jì)算結(jié)果指出了需要多少個(gè)二進(jìn)制位，可以消除概率事件的不確定性。H(X)值越大，意味著需要越多的二進(jìn)制位來消除不確定性（也就是需要多少個(gè)二進(jìn)制位來傳遞信息）；H(X)值越小，則X的不確定性越小，用來描述區(qū)分信息的二進(jìn)制位就越少。例子：對(duì)一個(gè)只有on/off兩種等可能狀態(tài)的燈，D={on，off}。D信息熵為：結(jié)論：使用1個(gè)二進(jìn)制位，就可準(zhǔn)確地描述燈亮，或者不亮的狀態(tài)。如果是某種極端情況，這盞燈壞了，那么它只有一種可能狀態(tài)D={off}，那么D的信息熵為：結(jié)論：因?yàn)檫@盞燈是確定狀態(tài)，不用任何其他信息我們都可以知道它的on/off狀態(tài)。例子：具體到表9-1，如果用{職業(yè)}作為分類標(biāo)準(zhǔn)，該屬性的值為“好/較好”的男生在{交往？}中都取得了“是”的結(jié)果。也就意味著，按照該標(biāo)準(zhǔn)劃分，對(duì)于“好/較好”的樣本，不需要再有額外的信息，我們就能得到“交往”的分類結(jié)果。另一方面，如果使用{外型}作為分類標(biāo)準(zhǔn)，8個(gè)“帥”的樣本中，有5個(gè)結(jié)論是“否”，有3個(gè)是“是”；4個(gè)“不帥”的樣本中，有1個(gè)結(jié)論是“否”，有3個(gè)是“是”。顯然，使用{外型}作為分類標(biāo)準(zhǔn)，需要其他額外信息，才能確定某個(gè)樣本的分類結(jié)果。上面案例的樣本數(shù)量和屬性種類都有限，可以通過觀察得到結(jié)論。對(duì)于大樣本多屬性的數(shù)據(jù)，可以通過信息熵來進(jìn)行量化分析得到結(jié)論。首先考慮樣本總體情況：12個(gè)“交往”的樣本中，最終的分類結(jié)果有6個(gè)“是”，6個(gè)“否”。其信息熵為：接下來考慮條件熵H(Y|X)，它表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性，隨機(jī)變量X給定的條件下隨機(jī)變量Y的條件熵（ConditionalEntropy）。其數(shù)學(xué)定義公式為：表9-1的例子Y={是，否}，知道了男生的職業(yè)信息X，有3個(gè)可能取值X={一般，較好，好}。那么序號(hào){1，2，3，5，6，11，12}樣本的職業(yè)為“一般”，“交往”為“是”的個(gè)數(shù)為1個(gè)，“否”的個(gè)數(shù)為6個(gè)；序號(hào)為{8，9}樣本的職業(yè)為“較好”，“交往”為“是”的個(gè)數(shù)為2個(gè)，“否”的個(gè)數(shù)為0個(gè)；序號(hào)為{4，7，10}樣本的職業(yè)為“好”，“交往”為“是”的個(gè)數(shù)為3個(gè)，“否”的個(gè)數(shù)為0個(gè)。根據(jù)這些數(shù)據(jù)，三個(gè)屬性對(duì)應(yīng)的信息熵分別為：另外，三個(gè)屬性對(duì)應(yīng)發(fā)生的概率分別為：如何選擇屬性，需要看信息增益（InformationGain）。也就是說，信息增益是相對(duì)于屬性而言的，信息增益越大，屬性對(duì)最終的分類結(jié)果影響也就越大，應(yīng)該選擇對(duì)最終分類結(jié)果影響最大的那個(gè)屬性作為分類屬性。屬性A對(duì)訓(xùn)練數(shù)據(jù)集D的信息增益g(D,A)，定義為集合D的信息熵H(D)與屬性A給定條件下D的條件熵H(D|A)之差：可以理解為：引入某一個(gè)條件后，不確定性減小了，這個(gè)減小的量=信息增益=信息熵-條件熵。信息增益越大，則說明引入的條件能更好地消除不確定性。例子：具體到表9-1，如果選擇“職業(yè)”作為條件X，那么不用看其他因素，基本上可以直接確定女生的“交往”意圖。根據(jù)公式，對(duì)應(yīng)的信息增益為：g(Y,X)=H(Y)-H(Y|X)=1-0.2674=0.7326上述信息增益計(jì)算方法，并根據(jù)信息增益進(jìn)行決策的過程，稱為ID3決策樹學(xué)習(xí)算法。有些時(shí)候，使用信息增益會(huì)比較粗暴，效果也不一定好。因?yàn)樵鲆孢@個(gè)指標(biāo)天然地偏向于選擇那些分支比較多的屬性。這種偏向性是必須消除的，算法應(yīng)該公正地評(píng)價(jià)所有的屬性。因此，另外一個(gè)指標(biāo)被提出來：信息增益率（GainRatio）。某一屬性A的增益率計(jì)算公式定義為：表上述信息增益率計(jì)算方法，并根據(jù)信息增益率進(jìn)行決策的過程，稱為C4.5決策樹學(xué)習(xí)算法。決策樹分類算法的流程圖如右圖所示。02Python代碼實(shí)現(xiàn)【例9-1】某保險(xiǎn)公司APP對(duì)某保險(xiǎn)產(chǎn)品被加入購(gòu)物車后是否實(shí)際成交進(jìn)行了統(tǒng)計(jì)，結(jié)果如表9-2所示。ID年齡收入范圍工作性質(zhì)信用評(píng)分購(gòu)買決策01<30高不穩(wěn)定較差否02<30高不穩(wěn)定好否0330-40高不穩(wěn)定較差是04>40中等不穩(wěn)定較差是05>40低穩(wěn)定較差是06>40低穩(wěn)定好否0730-40低穩(wěn)定好是08<30中等不穩(wěn)定較差否09<30低穩(wěn)定較差是10>40中等穩(wěn)定較差是11<30中等穩(wěn)定好是1230-40中等不穩(wěn)定好是1330-40高穩(wěn)定較差是14>40中等不穩(wěn)定好否表9?2用戶屬性與購(gòu)買決策作為保險(xiǎn)公司的營(yíng)銷策略分析人員，希望找出影響用戶做出最終購(gòu)買決策的因素，以便根據(jù)這些因素做出針對(duì)性的促銷策略。從算法設(shè)計(jì)的角度來說，根據(jù)這些觀察結(jié)果，構(gòu)造出顧客的決策樹，然后來預(yù)測(cè)顧客的活動(dòng)。這就是設(shè)計(jì)和實(shí)現(xiàn)決策樹分類算法的目標(biāo)。圖9-4保險(xiǎn)產(chǎn)品購(gòu)買決策樹Python實(shí)現(xiàn)代碼：決策樹分類算法從In[2]:開始。為了便于處理，In[2]:對(duì)表92的數(shù)據(jù)按照以下規(guī)則轉(zhuǎn)換為數(shù)值型列表數(shù)據(jù)：年齡：標(biāo)記為Age，<30賦值為0；30-40賦值為1；>40賦值為2。收入：標(biāo)記為Income，低賦值為0；中等賦值為1；高賦值為2。工作性質(zhì)：標(biāo)記為Job，不穩(wěn)定賦值為0；穩(wěn)定賦值為1。信用評(píng)分：標(biāo)記為Credit，較差賦值為0；好賦值為1。Out: [[0,2,0,0,'N'],[0,2,0,1,'N'],[1,2,0,0,'Y'],[2,1,0,0,'Y'],[2,0,1,0,'Y'],[2,0,1,1,'N'],[1,0,1,1,'Y'],[0,1,0,0,'N'],[0,0,1,0,'Y'],[2,1,1,0,'Y'],[0,1,1,1,'Y'],[1,1,0,1,'Y'],[1,2,1,0,'Y'],[2,1,0,1,'N']]['Age','Income','Job','Credit']計(jì)算數(shù)據(jù)集的信息熵：決策樹ID3算法決策樹C45算法：輔助函數(shù)majorityCnt：最終生成決策樹：從右圖可以看到：首先選取Age屬性對(duì)樣本集進(jìn)行劃分。對(duì)于Age屬性值為0（即<30）的，進(jìn)一步根據(jù)Income屬性進(jìn)行劃分，該屬性取值為0的客戶，最終分類為N；為1的客戶，最終分類為Y。對(duì)于Age屬性值為1的（即30-40），不用再檢查其他屬性，分類結(jié)果均為Y。對(duì)于Age屬性值為2（即>40）的，進(jìn)一步根據(jù)Job屬性進(jìn)行劃分，該屬性取值為0的客戶，最終分類為Y；為1的客戶，最終分類為N。使用生成的決策樹模型，對(duì)測(cè)試樣本進(jìn)行分類：第18行構(gòu)造了一個(gè)測(cè)試樣本[0,2,0,1]，其對(duì)應(yīng)的客戶信息是[“年齡”：<30；“收入范圍”：高；“工作性質(zhì)”：不穩(wěn)定；“信用評(píng)分”：好]，最終分類結(jié)果是：N。意味著具備這個(gè)屬性組合的客戶將不會(huì)購(gòu)買產(chǎn)品。03案例【例9-2】某銀行打算對(duì)客戶進(jìn)行某項(xiàng)理財(cái)產(chǎn)品促銷。類似產(chǎn)品的促銷記錄表明：促銷成功與否和客戶的工齡、職位、教育程度和婚姻狀況有關(guān)。記錄如表9-3所示。ID工齡工作性質(zhì)教育程度婚姻狀況銷售結(jié)果100011211N100021231N100031341Y100044221Y100051132Y100061131N100071331N100084322Y100092211N……101321311N其中ID列為客戶識(shí)別號(hào)，其他列的取值規(guī)則如下：工齡：<3年：1；3-5年：1；5-10年：2；>10年：3。工作性質(zhì)：機(jī)關(guān)事業(yè)單位：1；國(guó)企：2；私營(yíng)企業(yè)：3。教育程度：高中及以下：1；大專：2；本科：3；研究生：4?；橐鰻顩r：未婚：1；已婚：2。銷售結(jié)果：該客戶未購(gòu)買產(chǎn)品：N；購(gòu)買產(chǎn)品：Y。要求通過以上數(shù)據(jù)構(gòu)造客戶購(gòu)買產(chǎn)品的決策樹，用于針對(duì)性地對(duì)其他屬性客戶進(jìn)行產(chǎn)品促銷。在上一節(jié)代碼的基礎(chǔ)上，本例需要對(duì)數(shù)據(jù)文件進(jìn)行預(yù)處理，使之能夠滿足createTree函數(shù)和classify函數(shù)的輸入?yún)?shù)要求。Python程序：輸出結(jié)果：產(chǎn)品促銷決策樹：接下來使用這個(gè)決策樹，對(duì)某一個(gè)特定屬性的用戶是否會(huì)購(gòu)買產(chǎn)品進(jìn)行預(yù)測(cè)。給定客戶的資料為：[工齡6年，國(guó)企，本科，已婚]，按照數(shù)值化規(guī)則，其對(duì)應(yīng)的屬性向量為[2,2,3,2]。本章小結(jié)本章介紹了決策樹的基本概念和原理，學(xué)習(xí)如何計(jì)算信息熵、信息增益、信息增益率以及對(duì)應(yīng)的決策樹分割準(zhǔn)則。ID3和C4.5是兩個(gè)有代表性的決策樹學(xué)習(xí)算法，大家可以通過本章案例、習(xí)題和實(shí)驗(yàn)報(bào)告進(jìn)一步熟悉這些算法。除信息增益、增益率外，人們還設(shè)計(jì)了許多其他的準(zhǔn)則用于決策樹劃分選擇。然而有實(shí)驗(yàn)研究表明，這些準(zhǔn)則雖然對(duì)決策樹的尺寸有較大影響，但對(duì)泛化性能的影響很有限。本章小結(jié)決策樹剪枝是決策樹學(xué)習(xí)算法對(duì)付“過擬合”的主要手段。在決策樹學(xué)習(xí)中，為了盡可能正確分類訓(xùn)練樣本，結(jié)點(diǎn)劃分過程將不斷重復(fù)，有時(shí)會(huì)造成決策樹分支過多，這時(shí)就可能因訓(xùn)練樣本學(xué)得"太好"了，以致于把訓(xùn)練集自身的一些特點(diǎn)當(dāng)作所有數(shù)據(jù)都具有的一般性質(zhì)而導(dǎo)致過擬合。因此，可通過主動(dòng)去掉一些分支來降低過擬合的風(fēng)險(xiǎn)。決策樹剪枝的基本策略有“預(yù)剪枝”和“后剪枝”。有關(guān)決策樹剪枝的基本策略，剪枝方法和程度對(duì)決策樹泛化性能的影響，讀者可以參考其他相關(guān)書籍。重要概念1.信息熵2.信息熵增益3.信息熵增益率4.決策樹ID3、C4.5算法復(fù)習(xí)思考題1.給出數(shù)據(jù)表9-4記錄已有的用戶是否可以償還債務(wù)。ID擁有房產(chǎn)婚姻情況年收入（千元）無法償還債務(wù)1是單身125否2否已婚100否3否單身70否4是已婚120否5否離婚95是6否已婚60否7是離婚220否8否單身85是9否已婚75否10否單身90是表9-4貸款申請(qǐng)樣本數(shù)據(jù)表復(fù)習(xí)思考題問題：如果新來一個(gè)用戶：無房產(chǎn)，單身，年收入55K。根據(jù)上表歷史數(shù)據(jù)，手工畫出一棵決策樹，預(yù)測(cè)該客戶是否有能力償還債務(wù)。2.給出表9-5的貸款申請(qǐng)樣本數(shù)據(jù)，希望通過所給的訓(xùn)練數(shù)據(jù)學(xué)習(xí)一個(gè)貸款申請(qǐng)的決策樹，用于對(duì)未來的貸款申請(qǐng)進(jìn)行分類，即當(dāng)新的客戶提出貸款申請(qǐng)時(shí)，根據(jù)申請(qǐng)人的特征利用決策樹決定是否批準(zhǔn)貸款申請(qǐng)。復(fù)習(xí)思考題表9-5貸款申請(qǐng)樣本數(shù)據(jù)表ID年齡工作自有住房信貸情況類別（是否同意貸款）1青年否否