決策樹學(xué)習(xí)相關(guān)資料

一.示例學(xué)習(xí)示例學(xué)習(xí)也稱實例學(xué)習(xí),它是一種歸納學(xué)習(xí)。示例學(xué)習(xí)是從若干實例(包括正例和反例)中歸納出一般概念或規(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)→同花(c1，c2，c3，c4)對于這個問題可采用通常的曲線擬合技術(shù)，歸納出規(guī)則：(x，y，2x+3y+1)即 z＝2x＋3y＋1例2假設(shè)示例空間存放有如下的三個示例：示例1：(0，2，7)示例2：(6，-1，10)示例3：(-1，-5，-10)這是三個3維向量，表示空間中的三個點?，F(xiàn)要求求出過這三點的曲線。二.決策樹學(xué)習(xí)

1．什么是決策樹

決策樹(decisiontree)也稱判定樹，它是由對象的若干屬性、屬性值和有關(guān)決策組成的一棵樹。其中的節(jié)點為屬性（一般為語言變量），分枝為相應(yīng)的屬性值（一般為語言值）。從同一節(jié)點出發(fā)的各個分枝之間是邏輯“或”關(guān)系；根節(jié)點為對象的某一個屬性；從根節(jié)點到每一個葉子節(jié)點的所有節(jié)點和邊，按順序串連成一條分枝路徑，位于同一條分枝路徑上的各個“屬性-值”對之間是邏輯“與”關(guān)系，葉子節(jié)點為這個與關(guān)系的對應(yīng)結(jié)果，即決策。

決策樹示意圖

例3下圖所示是機場指揮臺關(guān)于飛機起飛的簡單決策樹。

例4下圖是一個描述“兔子”概念的決策樹。

2.怎樣學(xué)習(xí)決策樹

決策樹學(xué)習(xí)的基本方法和步驟：首先，選取一個屬性，按這個屬性的不同取值對實例集進行分類；并以該屬性作為根節(jié)點，以這個屬性的諸取值作為根節(jié)點的分枝，進行畫樹。然后，考察所得的每一個子類，看其中的實例的結(jié)論是否完全相同。如果完全相同，則以這個相同的結(jié)論作為相應(yīng)分枝路徑末端的葉子節(jié)點；否則，選取一個非父節(jié)點的屬性，按這個屬性的不同取值對該子集進行分類，并以該屬性作為節(jié)點，以這個屬性的諸取值作為節(jié)點的分枝，繼續(xù)進行畫樹。如此繼續(xù)，直到所分的子集全都滿足：實例結(jié)論完全相同，而得到所有的葉子節(jié)點為止?！駴Q策樹學(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)}其中每個元組組表示一個實實例，前面的的數(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ī)則集：①女性且年年齡在25歲歲以上，則給給予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í)習(xí)算法，，由Quinlan于于1979年提提出。ID3算算法的基基本思想想是，以以信息熵熵為度量量，用于于決策樹樹節(jié)點的的屬性選選擇，每每次優(yōu)先先選取信信息量最最多的屬屬性，亦亦即能使使熵值變變成最小小的屬性性，以構(gòu)構(gòu)造一棵棵熵值下下降最快快的決策策樹，到到葉子節(jié)節(jié)點處的的熵值為為0。此此時，每每個葉子子節(jié)點對對應(yīng)的實實例集中中的實例例屬于同同一類。。（1））信息熵熵和條條件熵熵設(shè)S是一個個實例例集(S也可以以是子子實例例集),A為S中實例例的一一個屬屬性。。H(S)和H(S|A)分別別稱為為實例例集S的信息息熵和和條件件熵,其其計算算公式式如下下:其中,μi(i=1,2,……,n)為S中各各實例例所有有可能能的結(jié)結(jié)論；；lb即log2。。其中,ak(k=1,2,……,m)為屬屬性A的取值值,Sak為按屬屬性A對實例例集S進行分分類時時所得得諸子子類中中與屬屬性值值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男而言,對子集集S女而言,于是,由公式式(9-1)