【正文】 必須記住它們所獲取的知識(shí)，以便將來(lái)使用。 (x1,x2,…,x n) (y1,y2,…,y n) [(x1,x2,…,x n),(y1,y2,…,y n)] f 存儲(chǔ) 輸入模式 執(zhí)行函數(shù) 輸出模式 輸入輸出模式對(duì) 機(jī)械式學(xué)習(xí)的學(xué)習(xí)模型 記憶學(xué)習(xí) 模 型 9 歸納學(xué)習(xí) 歸納學(xué)習(xí)是指以歸納推理為基礎(chǔ)的學(xué)習(xí)，其任務(wù)是要從關(guān)于某個(gè)概念的一系列已知的正例和反例中歸納出一個(gè)一般的概念描述。它給學(xué)習(xí)者提供某一概念的一組正例和反例，學(xué)習(xí)者歸納出一個(gè)總的概念描述，并使這個(gè)描述適合于所有的正例，排除所有的反例。在現(xiàn)有的各種決策樹學(xué)習(xí)算法中，影響較大的是 ID3算法。 10 按例子的來(lái)源分類 ① 例子來(lái)源于教師的示例學(xué)習(xí) ② 例子來(lái)源于學(xué)習(xí)者本身的示例學(xué)習(xí) 學(xué)習(xí)者明確知道自己的狀態(tài)，但完全不清楚所要獲取的概念。 按例子的類型分類 ① 僅利用正例的示例學(xué)習(xí) 這種學(xué)習(xí)方法會(huì)使推出的概念的外延擴(kuò)大化。 示例學(xué)習(xí) 1. 示例學(xué)習(xí)的類型 11 示例空間 規(guī)則空間 驗(yàn)證過(guò)程 解釋過(guò)程 示例空間 是我們向系統(tǒng)提供的示教例子的集合。 解釋過(guò)程 是從搜索到的示例中抽象出一般性的知識(shí)的歸納過(guò)程。 規(guī)則空間 是事務(wù)所具有的各種規(guī)律的集合。 示例學(xué)習(xí) 2. 示例學(xué)習(xí)的模型 12 是指解釋過(guò)程從具體示例形成一般性知識(shí)所采用的歸納推理方法。 (2) 去掉條件 把示例中的某些無(wú)關(guān)的子條件舍去。常用的增加析取項(xiàng)的方法有前件析取法和內(nèi)部析取法兩種 (4) 曲線擬合 對(duì)數(shù)值問(wèn)題的歸納可采用最小二乘法進(jìn)行曲線擬合 示例學(xué)習(xí) 3. 示例學(xué)習(xí)的解釋方法 (1/5) 13 例： 假設(shè)例子空間中有以下兩個(gè)關(guān)于撲克牌中“同花”概念的示例： 示例 1： 花色 (c1，梅花 ) ∧ 花色 (c2，梅花 ) ∧ 花色 (c3，梅花 ) ∧ 花色 (c4，梅花 )∧ 花色 (c5，梅花 ) → 同花 (c1, c2, c3, c4, c5) 示例 2： 花色 (c1，紅桃 ) ∧ 花色 (c2，紅桃 ) ∧ 花色 (c3，紅桃 ) ∧ 花色 (c4，紅桃 )∧ 花色 (c5，紅桃 ) → 同花 (c1, c2, c3, c4, c5) 其中，示例 1表示 5張梅花牌是同花，示例 2表示 5張紅桃牌是同花。例如，有如下示例： 示例 3： 花色 (c1, 紅桃 )∧ 點(diǎn)數(shù) (c1， 2) ∧ 花色 (c2, 紅桃 )∧ 點(diǎn)數(shù) (c2， 3) ∧ 花色 (c3, 紅桃 )∧ 點(diǎn)數(shù) (c3， 4) ∧ 花色 (c4, 紅桃 )∧ 點(diǎn)數(shù) (c4， 5) ∧ 花色 (c5, 紅桃 )∧ 點(diǎn)數(shù) (c5， 6) → 同花 (c1, c2, c3, c4, c5) 示例學(xué)習(xí) 3. 示例學(xué)習(xí)的解釋方法 (3/5) 為了學(xué)習(xí)同花的概念，除了需要把常量變?yōu)樽兞客?，還需要把與花色無(wú)關(guān)的“點(diǎn)數(shù)”子條件舍去。包括前件析取法和內(nèi)部析取法。例如： 示例 4： 點(diǎn)數(shù) (c1, J)→ 臉 (c1) 示例 5： 點(diǎn)數(shù) (c1, Q)→ 臉 (c1) 示例 6： 點(diǎn)數(shù) (c1, K)→ 臉 (c1) 將各示例的前件進(jìn)行析取，就可得到所要求的規(guī)則： 規(guī)則 2： 點(diǎn)數(shù) (c1, J)∨ 點(diǎn)數(shù) (c1, Q)∨ 點(diǎn)數(shù) (c1, K)→ 臉 (c1) 內(nèi)部析取法： 是在示例的表示中使用集合與集合的成員關(guān)系來(lái)形成知識(shí)的。假設(shè)示例空間中的每個(gè)示例 (x, y, z)都是輸入 x, y與輸出 z之間關(guān)系的三元組。它們都是要擴(kuò)大條件的適用范圍。因此，在使用方法 (1)時(shí)應(yīng)特別小心。 示例學(xué)習(xí) 3. 示例學(xué)習(xí)的解釋方法 (5/5) 17 是一種由節(jié)點(diǎn)和邊構(gòu)成的用來(lái)描述分類過(guò)程的層次數(shù)據(jù)結(jié)構(gòu)。 在決策樹中，從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑都代表一個(gè)具體的實(shí)例，并且同一路徑上的所有屬性之間為合取關(guān)系，不同路徑（即一個(gè)屬性的不同屬性值）之間為析取關(guān)系。 圖 。 決策樹學(xué)習(xí) 1. 決策樹的概念 (1/2) 18 鳥類 家養(yǎng) 可能是和平鴿 可能是 信天翁 游泳 可能是 企鵝 可能是 鴕鳥 圖 一個(gè)簡(jiǎn)單的鳥類識(shí)別決策樹 會(huì)飛 不會(huì)飛 是 不是 會(huì) 不會(huì) 決策樹還可以表示成規(guī)則的形式。當(dāng)學(xué)習(xí)完成后，就可以利用這棵決策樹對(duì)未知事物進(jìn)行分類。其輸入是一個(gè)用來(lái)描述各種已知類別的例子集，學(xué)習(xí)結(jié)果是一棵用于進(jìn)行分類的決策樹。假設(shè) X為信源， xi為 X所發(fā)出的單個(gè)信息， P(xi)為 X發(fā)出 xi的概率，則信息熵可定義為： 其中， k為信源 X發(fā)出的所有可能的信息類型，對(duì)數(shù)可以是以各種數(shù)為底的對(duì)數(shù)，在 ID3算法中，我們?nèi)∫?2為底的對(duì)數(shù)。 )(log)()(log)()(log)()(log)()(12211ikiirrxPxPxPxPxPxPxPxPXH????????? ?21 條件熵 條件熵是收信者在收到信息后對(duì)信息源不確定性的度量。 ( | ) ( | ) l og ( | )kki j i jijH X Y P x y P x y?? ?? 決策樹學(xué)習(xí) 2. ID3算法 (3/11) 22 決策樹學(xué)習(xí) 2. ID3算法 (4/11) (2) ID3算法及舉例 ID3算法的學(xué)習(xí)過(guò)程： 首先以整個(gè)例子集作為決策樹的根節(jié)點(diǎn) S，并計(jì)算 S關(guān)于每個(gè)屬性的期望熵（即條件熵）； 然后選擇能使 S的期望熵為最小的一個(gè)屬性對(duì)根節(jié)點(diǎn)進(jìn)行分裂，得到根節(jié)點(diǎn)的一層子節(jié)點(diǎn)； 接著再用同樣的方法對(duì)這些子節(jié)點(diǎn)進(jìn)行分裂，直至所有葉節(jié)點(diǎn)的熵值都下降為 0為止。該樹中每一條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑，都代表了一個(gè)分類過(guò)程，即決策過(guò)程。 決策樹學(xué)習(xí) 2. ID3算法 (5/11) 24 表 71 關(guān)于選課決策的訓(xùn)練例子集 在該表中，訓(xùn)練例子集 S的大小為８。 序號(hào) 屬性值 決策方案 yi x1 x2 x3 1 1 1 1 y3 2 1 1 2 y1 3 1 2 1 y3 4 1 2 2 y2 5 2 1 1 y3 6 2 1 2 y2 7 2 2 1 y3 8 2 2 2 y3 決策樹學(xué)習(xí) 2. ID3算法 (6/11) 25 解： 首先對(duì)根節(jié)點(diǎn)，其信息熵為： 其中，３為可選的決策方案數(shù)，且有 P(y1)=1/8， P(y2)=2/8， P(y3)=5/8 即有： H(S)= (1/8)log2(1/8) (2/8)log2(2/8) (5/8)log2(5/8) = 按照 ID3算法，需要選擇一個(gè)能使 S的期望熵為最小的一個(gè)屬性對(duì)根節(jié)點(diǎn)進(jìn)行擴(kuò)展，因此我們需要先計(jì)算 S關(guān)于每個(gè)屬性的條件熵： 其中， t為屬性 xi的屬性值， St為 xi=t時(shí)的例子集， |S|和 |Si|分別是例子集 S和Si的大小。當(dāng) x1=1時(shí)， t=1時(shí)，有： S1={1， 2， 3， 4} 當(dāng) x1=2時(shí)， t=2時(shí)，有： S2={5， 6， 7， 8} 其中， S1和 S2中的數(shù)字均為例子集 S中的各個(gè)例子的序號(hào)，且有 |S|=8，|S1|=|S2|=4。用 x3對(duì) S擴(kuò)展后所得到的得到部分決策樹如圖 。由于 y3已是具體的決策方案，故該節(jié)點(diǎn)的信息熵為 0，已經(jīng)為葉節(jié)點(diǎn)。 至于節(jié)點(diǎn)“ x3=2， x1,x2”，其擴(kuò)展方法與上面的過(guò)程類似。由于它對(duì)屬性 x1和 x2的條件熵相同，因此可以先選擇 x1，也可以先選擇 x2，本例是先選擇 x2。在該決策樹中，各節(jié)點(diǎn)的含義與圖 。它是在領(lǐng)域知識(shí)的指導(dǎo)下，通過(guò)對(duì)單個(gè)問(wèn)題求解例子的分析來(lái)進(jìn)行學(xué)習(xí)的。三個(gè)空間及它們之間的關(guān)系如圖 。所謂可操作是指一個(gè)概念描述能有效的用于識(shí)別相應(yīng)概念的例子。解釋學(xué)習(xí)的任務(wù)就是要把不可操作的概念描述轉(zhuǎn)化為可操作的概念描述。 執(zhí)行過(guò)程： 先由 EXL接受輸入的概念描述 D1，然后再根據(jù) KB中的知識(shí)對(duì)D1進(jìn)行不同描述的轉(zhuǎn)換，并由 PS對(duì)每個(gè)轉(zhuǎn)換結(jié)果進(jìn)行測(cè)試，直到被 PS所接受，即為可操作的概念描述 D2為止；最后輸出 D2。 其基本思想： 先對(duì)某一情況建立一個(gè)解釋結(jié)構(gòu)，然后在對(duì)此解釋結(jié)構(gòu)進(jìn)行概括，獲取一般性控制知識(shí)。 求出： 滿足 OC的關(guān)于 GC的充分概念描述。 解釋學(xué)習(xí)的基本原理 34 其任務(wù)是要證明提供給系統(tǒng)的訓(xùn)練實(shí)例為什么是目標(biāo)概念的一個(gè)實(shí)例。一旦得到解，便完成了該問(wèn)題的證明，同時(shí)也獲得了一個(gè)解釋結(jié)構(gòu)。即 目標(biāo)概念： SafetoStack (x, y) 訓(xùn)練實(shí)例 （是一些描述物體 obj1與 obj2的事實(shí)）： On(obj1 ,obj2) 物體 1在物體 2的上面 Isa(obj1 , book) 物體 1是書 Isa(obj2 , table) 物體 2是桌子 Volume(obj1 , 1) 物體 1的體積是 1 Density(