決策樹學(xué)習(xí)ppt課件

1、一.例如學(xué)習(xí) 例如學(xué)習(xí)也稱實例學(xué)習(xí), 它是一種歸納學(xué)習(xí)。例如學(xué)習(xí)是從假設(shè)干實例(包括正例和反例)中歸納出普通概念或規(guī)那么的學(xué)習(xí)方法。 第一個拱橋的語義網(wǎng)絡(luò) 第二個拱橋的語義網(wǎng)絡(luò). 學(xué)習(xí)程序歸納出的語義網(wǎng)絡(luò) 拱橋概念的語義網(wǎng)絡(luò) .例 1 假設(shè)例如空間中有橋牌中同花概念的兩個例如: 例如1： 花樣(c1，梅花)花樣(c2，梅花)花樣(c3，梅花)花樣(c4，梅花)同花(c1，c2，c3，c4) 例如2： 花樣(c1，紅桃)花樣(c2，紅桃)花樣(c3，紅桃)花樣(c4，紅桃)同花(c1，c2，c3，c4) 關(guān)于同花的普通性規(guī)那么: 花樣(c1，x)花樣(c2，x)花樣(c3，x)花樣(c4，x)同

2、花(c1，c2，c3，c4).對于這個問題可采用通常的曲線擬合技術(shù)，歸納出規(guī)那么： (x，y，2x+3y+1)即 z2x3y1例2 假設(shè)例如空間存放有如下的三個例如： 例如1：(0，2，7) 例如2：(6，-1，10) 例如3：(-1，-5，-10) 這是三個3維向量，表示空間中的三個點?，F(xiàn)要求求出過這三點的曲線。.二.決策樹學(xué)習(xí) 1什么是決策樹 決策樹(decision tree)也稱斷定樹，它是由對象的假設(shè)干屬性、屬性值和有關(guān)決策組成的一棵樹。其中的節(jié)點為屬性普通為言語變量，分枝為相應(yīng)的屬性值普通為言語值。從同一節(jié)點出發(fā)的各個分枝之間是邏輯“或關(guān)系；根節(jié)點為對象的某一個屬性；從根節(jié)點到每一

3、個葉子節(jié)點的一切節(jié)點和邊，按順序串連成一條分枝途徑，位于同一條分枝途徑上的各個“屬性-值對之間是邏輯“與關(guān)系，葉子節(jié)點為這個與關(guān)系的對應(yīng)結(jié)果，即決策。. 決策樹表示圖 .例3 以下圖所示是機場指揮臺關(guān)于飛機起飛的簡單決策樹。 .例4 以下圖是一個描畫“兔子概念的決策樹。 .2. 怎樣學(xué)習(xí)決策樹 決策樹學(xué)習(xí)的根本方法和步驟：首先，選取一個屬性，按這個屬性的不同取值對實例集進(jìn)展分類；并以該屬性作為根節(jié)點，以這個屬性的諸取值作為根節(jié)點的分枝，進(jìn)展畫樹。然后，調(diào)查所得的每一個子類，看其中的實例的結(jié)論能否完全一樣。假設(shè)完全一樣，那么以這個一樣的結(jié)論作為相應(yīng)分枝途徑末端的葉子節(jié)點；否那么，選取一個非父節(jié)點

4、的屬性，按這個屬性的不同取值對該子集進(jìn)展分類，并以該屬性作為節(jié)點，以這個屬性的諸取值作為節(jié)點的分枝，繼續(xù)進(jìn)展畫樹。如此繼續(xù)，直到所分的子集全都滿足：實例結(jié)論完全一樣，而得到一切的葉子節(jié)點為止。 . 決策樹學(xué)習(xí)舉例 設(shè)表1 所示的是某保險公司的汽車駕駛保險類別劃分的部分事例。我們將這張表作為一個實例集，用決策樹學(xué)習(xí)來歸納該保險公司的汽車駕駛保險類別劃分規(guī)那么。 .表1 汽車駕駛保險類別劃分實例集 . 將實例集簡記為S=(1,C), (2,C), (3,C), (4,B), (5,A), (6,A), (7,C), (8,B), (9,A), (10,A), (11,B), (12,B) 其中每個

5、元組表示一個實例，前面的數(shù)字為實例序號，后面的字母為實例的決策項保險類別。 用 “小、“中、“大 分別代表 “21、“21且25、“25 這三個年齡段。. 對于S，我們按屬性“性別的不同取值將其分類。由表1 可見，這時S應(yīng)被分類為兩個子集：S1= (3,C), (4,B), (7,C), (8,B), (11,B), (12,B)S2=(1,C), (2,C), (5,A), (6,A), (9,A), (10,A) 于是，我們得到以性別作為根節(jié)點的部分決策樹見以下圖。. 決策樹生成過程 . 決策樹生成過程 . 決策樹生成過程 .最后生成的 決策樹 . 由決策樹所得的規(guī)那么集： 女性且年齡在2

6、5歲以上，那么給予A類保險； 女性且年齡在21歲到25歲之間，那么給予A類保險； 女性且年齡在21歲以下，那么給予C類保險； 男性且年齡在25歲以上，那么給予B類保險； 男性且年齡在21歲到25歲之間且未婚，那么給予C類保險； 男性且年齡在21歲到25歲之間且已婚，那么給予B類保險； 男性且年齡在21歲以下且未婚，那么給予C類保險； 男性且年齡在21歲以下且已婚，那么給予B類保險。. 3. ID3算法 ID3算法是一個經(jīng)典的決策樹學(xué)習(xí)算法，由Quinlan于1979年提出。ID3算法的根本思想是，以信息熵為度量，用于決策樹節(jié)點的屬性選擇，每次優(yōu)先選取信息量最多的屬性，亦即能使熵值變成最小的屬性

7、，以構(gòu)造一棵熵值下降最快的決策樹，到葉子節(jié)點處的熵值為0。此時，每個葉子節(jié)點對應(yīng)的實例集中的實例屬于同一類。.1信息熵和條件熵 設(shè)S是一個實例集(S也可以是子實例集),A為S中實例的一個屬性。H(S)和H(S|A)分別稱為實例集S的信息熵和條件熵, 其計算公式如下: 其中,i(i=1, 2, , n)為S中各實例一切能夠的結(jié)論；lb即log2。 其中,ak(k=1, 2, , m)為屬性A的取值, Sak為按屬性A對實例集S進(jìn)展分類時所得諸子類中與屬性值ak對應(yīng)的那個子類。. 2基于條件熵的屬性選擇.按性別劃分, 實例集S被分為兩個子類: S男 =(3,C), (4,B), (7,C), (8,B), (11,B), (12,B)S女 =(1,C), (2,C), (5,A), (6,A), (9,A), (10,A) 從而, 對子集S男而言,