1、一.示例學(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，

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

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

4、，按這個(gè)屬性的不同取值對(duì)該子集進(jìn)行分類，并以該屬性作為節(jié)點(diǎn)，以這個(gè)屬性的諸取值作為節(jié)點(diǎn)的分枝，繼續(xù)進(jìn)行畫(huà)樹(shù)。 如此繼續(xù)，直到所分的子集全都滿足：實(shí)例結(jié)論完全相同，而得到所有的葉子節(jié)點(diǎn)為止。, 決策樹(shù)學(xué)習(xí)舉例 設(shè)表1 所示的是某保險(xiǎn)公司的汽車駕駛保險(xiǎn)類別劃分的部分事例。我們將這張表作為一個(gè)實(shí)例集，用決策樹(shù)學(xué)習(xí)來(lái)歸納該保險(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è)

5、實(shí)例，前面的數(shù)字為實(shí)例序號(hào)，后面的字母為實(shí)例的決策項(xiàng)保險(xiǎn)類別。 用 “小”、“中”、“大” 分別代表 “21”、“21且25”、“25” 這三個(gè)年齡段。,對(duì)于S，我們按屬性“性別”的不同取值將其分類。由表1 可見(jiàn)，這時(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)的部分決策樹(shù)（見(jiàn)下圖）。,決策樹(shù)生成過(guò)程,決策樹(shù)生成過(guò)程,決策樹(shù)生成過(guò)程,最后生成的 決策樹(shù),由決策樹(shù)所得的規(guī)則集： 女性且年齡在25歲以上，則

6、給予A類保險(xiǎn)； 女性且年齡在21歲到25歲之間，則給予A類保險(xiǎn)； 女性且年齡在21歲以下，則給予C類保險(xiǎn)； 男性且年齡在25歲以上，則給予B類保險(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)典的決策樹(shù)學(xué)習(xí)算法，由Quinlan于1979年提出。ID3算法的基本思想是，以信息熵為度量，用于決策樹(shù)節(jié)點(diǎn)的屬性選擇，每次優(yōu)先選取信息量最多的屬性，亦即能使熵值變成最小的屬性，以構(gòu)造一棵熵值下降最快的決策

7、樹(shù)，到葉子節(jié)點(diǎn)處的熵值為0。此時(shí)，每個(gè)葉子節(jié)點(diǎn)對(duì)應(yīng)的實(shí)例集中的實(shí)例屬于同一類。,（1）信息熵和條件熵 設(shè)S是一個(gè)實(shí)例集(S也可以是子實(shí)例集),A為S中實(shí)例的一個(gè)屬性。H(S)和H(S|A)分別稱為實(shí)例集S的信息熵和條件熵, 其計(jì)算公式如下: 其中,i(i=1, 2, , n)為S中各實(shí)例所有可能的結(jié)論；lb即log2。 其中,ak(k=1, 2, , m)為屬性A的取值, Sak為按屬性A對(duì)實(shí)例集S進(jìn)行分類時(shí)所得諸子類中與屬性值ak對(duì)應(yīng)的那個(gè)子類。,（2）基于條件熵的屬性選擇,按性別劃分, 實(shí)例集S被分為兩個(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ì)子集S男而