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

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

—

01算法概述PartTHREE—2

—

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

—

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

—

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

—

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

—

7.2.1信息量—7

—

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

—

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

則隨機變量X的熵定義為：

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

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

—

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

—

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

—

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

—

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

—

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

—

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

—

隨著社會的發(fā)展，在許多金融活動中存在大量的個人信用評估。貸款是當今社會一個普遍的行為，但銀行要對借貸人進行評估。傳統(tǒng)處理的方法由各專家評估打分方式實現(xiàn)，由此將產(chǎn)生過多的人為干預的因素，并且大大增加了工作量，大數(shù)據(jù)技術的發(fā)展，可避免傳統(tǒng)方式的缺陷和弊端。申請人要滿足銀行的條件才可以貸款成功。下表是一個由15個樣本組成的貸款申請訓練數(shù)據(jù)。數(shù)據(jù)包括貸款申請人的4個特征：第1個特征是年齡，有3個可能值：18-25歲，26-50歲，50歲以上；第2個特征是有工作，有2個可能值：是，否；第3個特征是有房產(chǎn)，有2個可能值：是，否；第4個特征是信貸情況，有3個可能值：非常好，好，一般。表的最后一列是類別，表示是否同意貸款，取2個值：是，否。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)以及信貸情況等條件來唯一地確定是否放貸。但總結表中信息，得知有房產(chǎn)的申請者一般都會通過貸款，而沒有房產(chǎn)的申請者是否通過貸款要看其他幾種條件。7.3.2利用信息增益選擇最優(yōu)劃分屬性—18

—

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

—

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

—

7.3.3遞歸構建決策樹—21

—

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

—

遞歸構建決策樹的代碼如下：7.3.4決策結果—23

—

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

—

7.4算法總結—25

—

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