關(guān)于人工智能的課件

1、 決策樹學(xué)習(xí) 什么是決策樹 怎樣學(xué)習(xí)決策ID3算法1什么是決策樹 決策樹(decision tree)也稱判定樹，它是由對象的若干屬性、屬性值和有關(guān)決策組成的一棵樹。節(jié)點(diǎn):屬性（一般為語言變量）分枝:屬性值（一般為語言值）邏輯“或”關(guān)系:從同一節(jié)點(diǎn)出發(fā)的各個分枝；邏輯“與”關(guān)系:位于同一條分枝路徑上的各個“屬性-值”對；從根節(jié)點(diǎn)到每一個葉子節(jié)點(diǎn)的所有節(jié)點(diǎn)和邊，按順序串連成一條分枝路徑，葉子節(jié)點(diǎn)為這個與關(guān)系的對應(yīng)結(jié)果，即決策。二.決策樹學(xué)習(xí) 2、怎樣學(xué)習(xí)決策樹首先，選取一個屬性，按這個屬性的不同取值對實(shí)例集進(jìn)行分類；并以該屬性作為根節(jié)點(diǎn)，以這個屬性的諸取值作為根節(jié)點(diǎn)的分枝，進(jìn)行畫樹。Title

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

3、, (2,C), (3,C), (4,B), (5,A), (6,A), (7,C), (8,B), (9,A), (10,A), (11,B), (12,B) 其中每個元組表示一個實(shí)例，前面的數(shù)字為實(shí)例序號，后面的字母為實(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)

4、 于是，我們得到以性別作為根節(jié)點(diǎn)的部分決策樹（見下圖）。 決策樹生成過程 決策樹生成過程 最后生成的 決策樹 由決策樹所得的規(guī)則集 女性且年齡在25歲以上，則給予A類保險； 女性且年齡在21歲到25歲之間，則給予A類保險； 女性且年齡在21歲以下，則給予C類保險； 男性且年齡在25歲以上，則給予B類保險； 男性且年齡在21歲到25歲之間且未婚，則給予C類保險； 男性且年齡在21歲到25歲之間且已婚，則給予B類保險； 男性且年齡在21歲以下且未婚，則給予C類保險； 男性且年齡在21歲以下且已婚，則給予B類保險。 ID3算法ID3算法是一個經(jīng)典的決策樹學(xué)習(xí)算法，由Quinlan于1979年提出?；?/p>

5、本思想：以信息熵為度量，用于決策樹節(jié)點(diǎn)的屬性選擇，每次優(yōu)先選取信息量最多的屬性，亦即能使熵值變成最小的屬性，以構(gòu)造一棵熵值下降最快的決策樹，到葉子節(jié)點(diǎn)處的熵值為0。此時，每個葉子節(jié)點(diǎn)對應(yīng)的實(shí)例集中的實(shí)例屬于同一類。1）信息熵和條件熵將實(shí)例集視為一個離散的信息系統(tǒng)，用信息熵表示信息量，實(shí)例的結(jié)論為隨機(jī)事件，諸屬性視為信息源。H(S)和H(S|A)分別稱為實(shí)例集S的信息熵和條件熵, 其計算公式如下:其中,i(i=1, 2, , n)為S中各實(shí)例所有可能的結(jié)論；lb即log2。ak(k=1, 2, , m)為屬性A的取值, Sak為按屬性A對實(shí)例集S進(jìn)行分類時所得諸子類中與屬性值ak對應(yīng)的那個子類。 1）信息熵和條件熵 （2）基于條件熵的屬性選擇按性別劃分, 實(shí)例集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)有: 又 將以上3式代入公式(9-