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

一.示例學(xué)習(xí)示例學(xué)習(xí)也稱實(shí)例學(xué)習(xí),它是一種歸納學(xué)習(xí)。示例學(xué)習(xí)是從若干實(shí)例(包括正例和反例)中歸納出一般概念或規(guī)則的學(xué)習(xí)方法。第一個(gè)拱橋的語(yǔ)義網(wǎng)絡(luò)第二個(gè)拱橋的語(yǔ)義網(wǎng)絡(luò)學(xué)習(xí)程序歸納出的語(yǔ)義網(wǎng)絡(luò)拱橋概念的語(yǔ)義網(wǎng)絡(luò)例1

假設(shè)示例空間中有橋牌中"同花"概念的兩個(gè)示例:

示例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)對(duì)于這個(gè)問題可采用通常的曲線擬合技術(shù)，歸納出規(guī)則：(x，y，2x+3y+1)即 z＝2x＋3y＋1例2假設(shè)示例空間存放有如下的三個(gè)示例：示例1：(0，2，7)示例2：(6，-1，10)示例3：(-1，-5，-10)這是三個(gè)3維向量，表示空間中的三個(gè)點(diǎn)。現(xiàn)要求求出過這三點(diǎn)的曲線。二.決策樹學(xué)習(xí)

1．什么是決策樹

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

決策樹示意圖

例3下圖所示是機(jī)場(chǎng)指揮臺(tái)關(guān)于飛機(jī)起飛的簡(jiǎn)單決策樹。

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

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

決策樹學(xué)習(xí)的基本方法和步驟：首先，選取一個(gè)屬性，按這個(gè)屬性的不同取值對(duì)實(shí)例集進(jìn)行分類；并以該屬性作為根節(jié)點(diǎn)，以這個(gè)屬性的諸取值作為根節(jié)點(diǎn)的分枝，進(jìn)行畫樹。然后，考察所得的每一個(gè)子類，看其中的實(shí)例的結(jié)論是否完全相同。如果完全相同，則以這個(gè)相同的結(jié)論作為相應(yīng)分枝路徑末端的葉子節(jié)點(diǎn)；否則，選取一個(gè)非父節(jié)點(diǎn)的屬性，按這個(gè)屬性的不同取值對(duì)該子集進(jìn)行分類，并以該屬性作為節(jié)點(diǎn)，以這個(gè)屬性的諸取值作為節(jié)點(diǎn)的分枝，繼續(xù)進(jìn)行畫樹。如此繼續(xù)，直到所分的子集全都滿足：實(shí)例結(jié)論完全相同，而得到所有的葉子節(jié)點(diǎn)為止。●決策樹學(xué)習(xí)舉舉例設(shè)表1所示示的是某保險(xiǎn)險(xiǎn)公司的汽車車駕駛保險(xiǎn)類類別劃分的部部分事例。我我們將這張表表作為一個(gè)實(shí)實(shí)例集，用決決策樹學(xué)習(xí)來來歸納該保險(xiǎn)險(xiǎn)公司的汽車車駕駛保險(xiǎn)類類別劃分規(guī)則則。表1汽車駕駛保險(xiǎn)類別劃分實(shí)例集

將實(shí)例集簡(jiǎn)記記為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)}其中每個(gè)元組組表示一個(gè)實(shí)實(shí)例，前面的的數(shù)字為實(shí)例例序號(hào)，后面面的字母為實(shí)實(shí)例的決策項(xiàng)項(xiàng)保險(xiǎn)類別。。用““小”、““中”、“大大”分別代表“＜21”、、“≥21且且≤25”、、“＞25””這三個(gè)年齡段段。對(duì)于S，我們們按屬性“性性別”的不同同取值將其分分類。由表1可見，這這時(shí)S應(yīng)被分分類為兩個(gè)子子集：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é)點(diǎn)的的部分決策樹樹（見下圖））。決策樹生成過過程決策樹生成過過程決策樹生成過過程最后生成的決策樹由決策樹所得得的規(guī)則集：①女性且年年齡在25歲歲以上，則給給予A類保險(xiǎn)險(xiǎn)；②女性且年年齡在21歲歲到25歲之之間，則給予予A類保險(xiǎn)；；③女性且年年齡在21歲歲以下，則給給予C類保險(xiǎn)險(xiǎn)；④男性且年年齡在25歲歲以上，則給給予B類保險(xiǎn)險(xiǎn)；⑤男性且年年齡在21歲歲到25歲之之間且未婚，，則給予C類類保險(xiǎn)；⑥男性且年年齡在21歲歲到25歲之之間且已婚，，則給予B類類保險(xiǎn)；⑦男性且年年齡在21歲歲以下且未婚婚，則給予C類保險(xiǎn)；⑧男性且年年齡在21歲歲以下且已婚婚，則給予B類保險(xiǎn)。3.ID3算算法ID3算算法是一一個(gè)經(jīng)典典的決策策樹學(xué)習(xí)習(xí)算法，，由Quinlan于于1979年提提出。ID3算算法的基基本思想想是，以以信息熵熵為度量量，用于于決策樹樹節(jié)點(diǎn)的的屬性選選擇，每每次優(yōu)先先選取信信息量最最多的屬屬性，亦亦即能使使熵值變變成最小小的屬性性，以構(gòu)構(gòu)造一棵棵熵值下下降最快快的決策策樹，到到葉子節(jié)節(jié)點(diǎn)處的的熵值為為0。此此時(shí)，每每個(gè)葉子子節(jié)點(diǎn)對(duì)對(duì)應(yīng)的實(shí)實(shí)例集中中的實(shí)例例屬于同同一類。。（1））信息熵熵和條條件熵熵設(shè)S是一個(gè)個(gè)實(shí)例例集(S也可以以是子子實(shí)例例集),A為S中實(shí)例例的一一個(gè)屬屬性。。H(S)和H(S|A)分別別稱為為實(shí)例例集S的信息息熵和和條件件熵,其其計(jì)算算公式式如下下:其中,μi(i=1,2,……,n)為S中各各實(shí)例例所有有可能能的結(jié)結(jié)論；；lb即log2。。其中,ak(k=1,2,……,m)為屬屬性A的取值值,Sak為按屬屬性A對(duì)實(shí)例例集S進(jìn)行分分類時(shí)時(shí)所得得諸子子類中中與屬屬性值值ak對(duì)應(yīng)的的那個(gè)個(gè)子類類。（2））基于條條件熵熵的屬屬性選選擇按性別別劃分分,實(shí)例集集S被分為為兩個(gè)個(gè)子類類: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)}從而,對(duì)對(duì)子集集S男而言,對(duì)子集集S女而言,于是,由公式式(9-1)