人工智能算法與實(shí)踐-第7章 決策樹

7.4算法總結(jié)7.1算法概述7.2算法原理7.3算法案例目錄第七章決策樹算法人工智能算法與實(shí)踐—1

—

01算法概述PartTHREE—2

—

決策樹（DecisionTree）是機(jī)器學(xué)習(xí)中常用的方法之一。決策樹模型分為分類決策樹和回歸決策樹。分類決策樹模型是一種樹形結(jié)構(gòu)模型，用于描述對樣本數(shù)據(jù)的分類。決策樹由節(jié)點(diǎn)（Node）和有向邊（DirectedEdge）組成。節(jié)點(diǎn)分為內(nèi)部節(jié)點(diǎn)和葉節(jié)點(diǎn)。內(nèi)部節(jié)點(diǎn)代表一個(gè)要素或?qū)傩?，葉節(jié)點(diǎn)代表一個(gè)類。7.1.1算法簡介—3

—

7.1.2如何生成一棵決策樹—4

—

（1）學(xué)習(xí)特征變量的分枝策略。（2）根據(jù)特征變量，將數(shù)據(jù)集分割為多個(gè)子集。按照分枝策略，對樣本數(shù)據(jù)進(jìn)行測試，并將樣本數(shù)據(jù)集分割成子集（子節(jié)點(diǎn)）。（3）構(gòu)建子樹。根據(jù)第（2）的每個(gè)數(shù)據(jù)子集，構(gòu)建多棵子樹。對于每個(gè)子樹，重復(fù)第（1）步和第（2）步的過程，直到達(dá)到停止生長的條件。（4）對樹進(jìn)行剪枝?？赡軙纬蛇^度擬合，需要對樹進(jìn)行剪枝以獲得最好的泛化效果。7.1.3決策過程—5

—

在經(jīng)過訓(xùn)練后的決策樹中，每個(gè)葉節(jié)點(diǎn)對應(yīng)一個(gè)分類器，通過對新樣本數(shù)據(jù)的葉節(jié)點(diǎn)歸屬進(jìn)行測試，就可以實(shí)現(xiàn)對新樣本數(shù)據(jù)的分類預(yù)測。那么如何利用決策樹進(jìn)行分類？1．葉節(jié)點(diǎn)中哪個(gè)類別的樣本多，就把葉節(jié)點(diǎn)歸為該類別一般而言，葉節(jié)點(diǎn)中會包含每個(gè)分類的樣本，統(tǒng)計(jì)葉節(jié)點(diǎn)中每個(gè)分類的樣本數(shù)目所占的比例，并將這個(gè)葉節(jié)點(diǎn)的類別歸入樣本數(shù)目所占的比例最高的類別。2．每個(gè)葉節(jié)點(diǎn)對應(yīng)一條規(guī)則從根節(jié)點(diǎn)到葉節(jié)點(diǎn)，形成了一條規(guī)則，且這個(gè)規(guī)則是完備的，即每個(gè)樣本數(shù)據(jù)必屬于其中某一條規(guī)則。規(guī)則：變量A>c1、變量B<c2且變量C>c3。3．每個(gè)葉子節(jié)點(diǎn)組成的規(guī)則形成一個(gè)決策樹分類器在預(yù)測時(shí)，只要測試樣本數(shù)據(jù)屬于哪一條規(guī)則，即可得到對應(yīng)的分類歸屬，如圖所示。02算法原理PartTHREE—6

—

7.2.1信息量—7

—

信息量是指信息多少的量度。1928年，科學(xué)家“哈特萊”提出了采用事件出現(xiàn)概率倒數(shù)的對數(shù)作為信息的度量單位，如下式所示。信息量的大小以及信息所代表的事件發(fā)生的概率在信息中存在關(guān)聯(lián)。若一信息所代表的事件是必然事件，即事件發(fā)生的概率為100%，則此信息包含的信息量為0。若一信息所代表的事件是小概率事件，即該事件發(fā)生的概率很低，則該信息包含的信息量將無限大。例1：一位同學(xué)跑過來告訴你說，明天的太陽會從東邊升起。這個(gè)信息所包含的信息量就是0，因?yàn)檫@是一個(gè)必然事件。即使同學(xué)不告訴你，你也知道這個(gè)信息，太陽依舊會從東邊升起。例2：這位同學(xué)又告訴你一個(gè)信息，他非常神秘地告訴你一串?dāng)?shù)字并且說快去買彩票，買這組數(shù)字的彩票，明天能中五百萬。你買彩票之后果然中了五百萬。這個(gè)信息所包含的信息量是無窮大的，因?yàn)檫@是一個(gè)小概率事件。7.2.2信息熵—8

—

信息熵是表示信息不確定性的一種度量。無論是熱熵還是信息熵，其本質(zhì)都是表明事物的混亂程度。熵越高，越混亂；熵越低，則越有序。信息量衡量由特定事件生成的信息，而熵是對結(jié)果出現(xiàn)之前可以生成的信息量的期望?？紤]隨機(jī)變量的所有可能值，即所有可能的事件帶來的信息量的期望。熵是表示隨機(jī)變量不確定性的度量。假設(shè)X是一個(gè)取有限個(gè)值的離散隨機(jī)變量，其概率分布為：

則隨機(jī)變量X的熵定義為：

其中P(Xi)代表隨機(jī)事件X為Xi的概率

從信息量角度，熵可以理解為某一個(gè)隨機(jī)變量的平均信息量（隨機(jī)變量信息量的期望）。隨機(jī)變量可能有多種取值（隨機(jī)事件），每種取值發(fā)生的概率不一樣，概率低的取值信息量大，概率高的取值信息量小。熵是從平均來看這個(gè)隨機(jī)變量可以帶來的信息量。7.2.3條件熵—9

—

當(dāng)兩個(gè)分類的概率值相等，即兩個(gè)概率都等于0.5時(shí)，熵達(dá)到最大值。熵隨概率P變化的曲線如圖所示。條件熵的定義為：在給定條件X下，Y的條件概率分布的熵對X的數(shù)學(xué)期望。條件熵表示在已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性。公式為：推導(dǎo)后得到：7.2.4信息增益—10

—

信息增益是特征選擇的重要指標(biāo)，表示為知道某個(gè)特征后使不確定性減少的程度。信息越多，功能的重要性就越高，對應(yīng)的信息增益就越大。上面所說的信息熵代表了隨機(jī)變量的復(fù)雜度，條件熵代表在某一個(gè)條件下，隨機(jī)變量的復(fù)雜度，而信息增益=信息熵-條件熵，換而言之就是知道某個(gè)特征后使得不確定性減少的程度，即知道某個(gè)特征之前的熵與知道某個(gè)特征之后的熵之差。在決策樹中，根據(jù)某個(gè)特征將數(shù)據(jù)分割為多個(gè)子集，分割前與分割后的樣本數(shù)據(jù)熵之差就代表信息增益，信息增益越高則該特征對數(shù)據(jù)分類效果越好。7.2.4信息增益如下左圖所示，每個(gè)點(diǎn)表示一個(gè)數(shù)據(jù)樣本，藍(lán)色的點(diǎn)表示屬于A類，綠色的點(diǎn)表示屬于B類。在整個(gè)數(shù)據(jù)集合中，由于A、B兩類的發(fā)生概率相同，則熵為1。如下右圖所示，根據(jù)x1變量的值，將樣本數(shù)據(jù)分為兩個(gè)子集；左側(cè)的子集中全為藍(lán)色的點(diǎn)(A類)，該子集的熵為0。同樣右側(cè)的熵也為0，分割后整體熵為0。7.2.4信息增益—12

—

用數(shù)學(xué)語言可將信息增益描述為：特征A對訓(xùn)練數(shù)據(jù)集D的信息增益為g(D,A)，定義為集合D經(jīng)驗(yàn)熵H(D)與特征A給定條件下D的經(jīng)驗(yàn)條件熵H(D|A)之差。（1）假設(shè)訓(xùn)練數(shù)據(jù)集為D，|D|則表示數(shù)據(jù)集中樣本的個(gè)數(shù)。（2）假設(shè)數(shù)據(jù)D中有B個(gè)分類記作，表示類Cb的樣本個(gè)數(shù)，那么。（3）假設(shè)A為數(shù)據(jù)集D中的某一個(gè)特征變量，該特征變量有n種取值。根據(jù)特征A的取值，將D劃分為n個(gè)子集D1,D2...Dn，|Di|表示子集Di中的樣本個(gè)數(shù)，則有。（4）子集|Di|中屬于類Cb的樣本集合為Dib，則|Dib|為Dib的樣本個(gè)數(shù)。信息增益為：7.2.5信息增益比—13

—

以信息增益作為劃分訓(xùn)練數(shù)據(jù)集的特征，存在偏向于選擇取值較多的特征問題，容易過度擬合，因此將引入信息增益比來解決該問題。信息增益比是特征A對數(shù)據(jù)集D的信息增益與特征A的不同取值的熵之比：反映的是特征變量A的各個(gè)可能取值的分布情況，如果不同取值的分布比較分散即不純度很高，則越大，信息增益除以表示對其懲罰度越高。7.2.6決策樹的生成—14

—

從根節(jié)點(diǎn)出發(fā)，根節(jié)點(diǎn)包括所有的訓(xùn)練樣本。如果一個(gè)節(jié)點(diǎn)（包括根節(jié)點(diǎn)）內(nèi)所有樣本均屬于同一類別，那么該節(jié)點(diǎn)就成為葉節(jié)點(diǎn)，并將該節(jié)點(diǎn)標(biāo)記為樣本個(gè)數(shù)最多的類別。否則采用信息增益法來選擇用于對樣本進(jìn)行劃分的特征，該特征即為測試特征，特征的每一個(gè)值都對應(yīng)著從該節(jié)點(diǎn)產(chǎn)生的一個(gè)分支及被劃分的一個(gè)子集。在決策樹中，所有的特征均為符號值，即離散值。如果某個(gè)特征的值為連續(xù)值，則需要先將其離散化。遞歸上述劃分子集及產(chǎn)生葉節(jié)點(diǎn)的過程，使每一個(gè)子集都會產(chǎn)生一個(gè)決策（子）樹，直到所有節(jié)點(diǎn)變成葉節(jié)點(diǎn)。遞歸操作的停止條件就是：（1）一個(gè)節(jié)點(diǎn)中所有的樣本均為同一類別，那么產(chǎn)生葉節(jié)點(diǎn)；（2）沒有特征可以用來對該節(jié)點(diǎn)樣本進(jìn)行劃分，這里用attribute_list=null來表示。此時(shí)也強(qiáng)制產(chǎn)生葉節(jié)點(diǎn)，該節(jié)點(diǎn)的類別為樣本個(gè)數(shù)最多的類別；（3）沒有樣本能滿足剩余特征的取值，即test_attribute=對應(yīng)的樣本為空。此時(shí)也強(qiáng)制產(chǎn)生葉節(jié)點(diǎn)，該節(jié)點(diǎn)的類別為樣本個(gè)數(shù)最多的類別。03算法案例PartTHREE—15

—

7.3.1借貸人狀態(tài)評估—16

—

隨著社會的發(fā)展，在許多金融活動中存在大量的個(gè)人信用評估。貸款是當(dāng)今社會一個(gè)普遍的行為，但銀行要對借貸人進(jìn)行評估。傳統(tǒng)處理的方法由各專家評估打分方式實(shí)現(xiàn)，由此將產(chǎn)生過多的人為干預(yù)的因素，并且大大增加了工作量，大數(shù)據(jù)技術(shù)的發(fā)展，可避免傳統(tǒng)方式的缺陷和弊端。申請人要滿足銀行的條件才可以貸款成功。下表是一個(gè)由15個(gè)樣本組成的貸款申請訓(xùn)練數(shù)據(jù)。數(shù)據(jù)包括貸款申請人的4個(gè)特征：第1個(gè)特征是年齡，有3個(gè)可能值：18-25歲，26-50歲，50歲以上；第2個(gè)特征是有工作，有2個(gè)可能值：是，否；第3個(gè)特征是有房產(chǎn)，有2個(gè)可能值：是，否；第4個(gè)特征是信貸情況，有3個(gè)可能值：非常好，好，一般。表的最后一列是類別，表示是否同意貸款，取2個(gè)值：是，否。7.3.1借貸人狀態(tài)評估—17

—

ID年齡有工作有房產(chǎn)信貸情況類別118-25歲否否一般否218-25歲否否好否318-25歲是否好是418-25歲是是一般是518-25歲否否一般否626-50歲否否一般否726-50歲否否好否826-50歲是是好是926-50歲否是非常好是1026-50歲否是非常好是1150歲以上否是非常好是1250歲以上否是好是1350歲以上是否好是1450歲以上是否非常好是1550歲以上否否一般否根據(jù)表中的信息可知，可以由年齡、工作、房產(chǎn)以及信貸情況等條件來唯一地確定是否放貸。但總結(jié)表中信息，得知有房產(chǎn)的申請者一般都會通過貸款，而沒有房產(chǎn)的申請者是否通過貸款要看其他幾種條件。7.3.2利用信息增益選擇最優(yōu)劃分屬性—18

—

（1）計(jì)算整個(gè)樣本數(shù)據(jù)集的熵其中，為拒絕貸款的用戶概率，為同意貸款的用戶概率（2）計(jì)算根據(jù)為“有工作”這一特征變量對數(shù)據(jù)集分割后的熵條件有工作（總量=5）無工作（總量=10）是否同意貸款是，是，是，是，是否，否，否，否，否，否是，是，是，是(3)工作特征變量的信息增益同理也可以計(jì)算出其他幾個(gè)屬性的信息增益，在決策樹的每一個(gè)非葉子結(jié)點(diǎn)劃分之前，先計(jì)算每一個(gè)屬性所帶來的信息增益，選擇最大信息增益的屬性來劃分。因?yàn)樾畔⒃鲆嬖酱?，區(qū)分樣本的能力就越強(qiáng)，越具有代表性。7.3.2利用信息增益選擇最優(yōu)劃分屬性—19

—

利用信息增益選擇最優(yōu)劃分屬性的代碼如下7.3.2利用信息增益選擇最優(yōu)劃分屬性—20

—

7.3.3遞歸構(gòu)建決策樹—21

—

通常一棵決策樹包含一個(gè)根節(jié)點(diǎn)、若干個(gè)內(nèi)部節(jié)點(diǎn)和若干個(gè)葉節(jié)點(diǎn)，葉節(jié)點(diǎn)對應(yīng)決策結(jié)果，根節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)對應(yīng)一個(gè)屬性測試，每個(gè)節(jié)點(diǎn)包含的樣本集合根據(jù)屬性測試的結(jié)果劃分到子節(jié)點(diǎn)中。對整個(gè)訓(xùn)練集選擇的最優(yōu)劃分屬性就是根節(jié)點(diǎn)。第一次劃分后，數(shù)據(jù)被向下傳遞到樹分支的下一個(gè)節(jié)點(diǎn)，并再次劃分?jǐn)?shù)據(jù)。構(gòu)建決策樹是一個(gè)遞歸的過程，而遞歸結(jié)束的條件是，所有屬性都被遍歷完，或者每個(gè)分支下的所有樣本都屬于同一類。7.3.3遞歸構(gòu)建決策樹—22

—

遞歸構(gòu)建決策樹的代碼如下：7.3.4決策結(jié)果—23

—

最終決策結(jié)果如下圖所示：04算法總結(jié)PartTHREE—24

—

7.4算法總結(jié)—25

—

優(yōu)點(diǎn)1）簡單直觀，生成的決策樹很直觀。2）基本不需要預(yù)處理，不需要提前歸一化，處理缺失值。3）既可以