【正文】 ) ∧ 花色 (c2， x) ∧ 花色 (c3， x) ∧ 花色 (c4， x)∧ 花色 (c5，x)→ 同花 (c1, c2, c3, c4, c5) 15 示例學(xué)習(xí) 3. 示例學(xué)習(xí)的解釋方法 (4/5) (3)增加選擇 在析取條件中增加一個(gè)新的析取項(xiàng)。包括前件析取法和內(nèi)部析取法。 前件析取法： 是通過對(duì)示例的前件的析取來形成知識(shí)的。例如： 示例 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)系來形成知識(shí)的。例如，有如下關(guān)于“臉牌”的示例： 示例 7： 點(diǎn)數(shù) c1∈ {J}→ 臉 (c1) 示例 8： 點(diǎn)數(shù) c1∈ {Q}→ 臉 (c1) 示例 9： 點(diǎn)數(shù) c1∈ {K}→ 臉 (c1) 用內(nèi)部析取法，可得到如下規(guī)則： 規(guī)則 3： 點(diǎn)數(shù) (c1)∈ {J, Q, K}→ 臉 (c1) 16 (4)曲線擬合 對(duì)數(shù)值問題的歸納可采用曲線擬合法。假設(shè)示例空間中的每個(gè)示例 (x, y, z)都是輸入 x, y與輸出 z之間關(guān)系的三元組。例如，有下 3個(gè)示例： 示例 10： (0, 2, 7) 示例 11： (6, 1, 10) 示例 12： (1, 5, 16) 用最小二乘法進(jìn)行曲線擬合，可得 x, y, z之間關(guān)系的規(guī)則如下： 規(guī)則 4： z=2x+3y+1 說明： 在上述前三種方法中，方法 (1)是把常量轉(zhuǎn)換為變量；方法 (2)是去掉合取項(xiàng)（約束條件）；方法 (3)是增加析取項(xiàng)。它們都是要擴(kuò)大條件的適用范圍。從歸納速度上看，方法 (1)的歸納速度快，但容易出錯(cuò)；方法 (2)歸納速度慢，但不容易出錯(cuò)。因此，在使用方法 (1)時(shí)應(yīng)特別小心。例如： 對(duì)示例 示例 5及示例 6，若使用方法 (1) ,則會(huì)歸納出如下的錯(cuò)誤規(guī)則： 規(guī)則 5： （錯(cuò)誤）點(diǎn)數(shù) (c1, x)→ 臉 (c1) 它說明，歸納過程是很容易出錯(cuò)的。 示例學(xué)習(xí) 3. 示例學(xué)習(xí)的解釋方法 (5/5) 17 是一種由節(jié)點(diǎn)和邊構(gòu)成的用來描述分類過程的層次數(shù)據(jù)結(jié)構(gòu)。該樹的根接點(diǎn)表示分類的開始，葉節(jié)點(diǎn)表示一個(gè)實(shí)例的結(jié)束，中間節(jié)點(diǎn)表示相應(yīng)實(shí)例中的某一屬性，而邊則代表某一屬性可能的屬性值。 在決策樹中，從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑都代表一個(gè)具體的實(shí)例，并且同一路徑上的所有屬性之間為合取關(guān)系，不同路徑（即一個(gè)屬性的不同屬性值）之間為析取關(guān)系。 決策樹的分類過程就是從這棵樹的根接點(diǎn)開始，按照給定的事例的屬性值去測(cè)試對(duì)應(yīng)的樹枝，并依次下移，直至到達(dá)某個(gè)葉節(jié)點(diǎn)為止。 圖 。在該圖中： 根節(jié)點(diǎn)包含各種鳥類，葉節(jié)點(diǎn)是所能識(shí)別的各種鳥的名稱； 中間節(jié)點(diǎn)是鳥的一些屬性，邊是鳥的某一屬性的屬性值； 從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路徑都描述了一種鳥，它包括該種鳥的一些屬性及相應(yīng)的屬性值。 決策樹學(xué)習(xí) 1. 決策樹的概念 (1/2) 18 鳥類 家養(yǎng) 可能是和平鴿 可能是 信天翁 游泳 可能是 企鵝 可能是 鴕鳥 圖 一個(gè)簡單的鳥類識(shí)別決策樹 會(huì)飛 不會(huì)飛 是 不是 會(huì) 不會(huì) 決策樹還可以表示成規(guī)則的形式。上圖的決策樹可表示為如下規(guī)則集： IF 鳥類會(huì)飛 AND 是家養(yǎng)的 THEN 該鳥類是和平鴿 IF 鳥類會(huì)飛 AND 不是家養(yǎng)的 THEN 該鳥類是信天翁 IF 鳥類不會(huì)飛 AND 會(huì)游泳 THEN 該鳥類是企鵝 IF 鳥類不會(huì)飛 AND 不會(huì)游泳 THEN 該鳥類是鴕鳥 決策樹學(xué)習(xí)過程實(shí)際上是一個(gè)構(gòu)造決策樹的過程。當(dāng)學(xué)習(xí)完成后，就可以利用這棵決策樹對(duì)未知事物進(jìn)行分類。 決策樹學(xué)習(xí) 1. 決策樹的概念 (2/2) 19 決策樹學(xué)習(xí) 2. ID3算法 (1/11) D3算法是昆蘭（ ）于 1979年提出的一種以信息熵（ entropy）的下降速度作為屬性選擇標(biāo)準(zhǔn)的一種學(xué)習(xí)算法。其輸入是一個(gè)用來描述各種已知類別的例子集，學(xué)習(xí)結(jié)果是一棵用于進(jìn)行分類的決策樹。 主要討論： ID3算法的數(shù)學(xué)基礎(chǔ) ID3算法機(jī)器舉例 20 決策樹學(xué)習(xí) 2. ID3算法 (2/11) (1) ID3算法的數(shù)學(xué)基礎(chǔ) 下面討論信息熵和條件熵的數(shù)學(xué)概念 信息熵 信息熵是對(duì)信息源整體不確定性的度量。假設(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ù)。 信息熵反應(yīng)的是信源每發(fā)出一個(gè)信息所提供的平均信息量。 )(log)()(log)()(log)()(log)()(12211ikiirrxPxPxPxPxPxPxPxPXH????????? ?21 條件熵 條件熵是收信者在收到信息后對(duì)信息源不確定性的度量。若假設(shè)信源為 X，收信者收到的信息為 Y， P(xi/yj)為當(dāng) Y為 yj時(shí) X為 xi的條件概率，則條件熵可定義為： 它表示收信者收到 Y后對(duì) X不確定性的估計(jì)。 ( | ) ( | ) 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í)過程： 首先以整個(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為止。 這時(shí)，就可得到一棵與訓(xùn)練例子集對(duì)應(yīng)的熵為 0的決策樹，即 ID3算法學(xué)習(xí)過程所得到的最終決策樹。該樹中每一條從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的路徑，都代表了一個(gè)分類過程，即決策過程。 23 例 用 ID3算法完成下述學(xué)生選課的例子 假設(shè)將決策 y分為以下３類： y1：必修 AI y2：選修 AI y3：不修 AI 做出這些決策的依據(jù)有以下 3個(gè)屬性： x1：學(xué)歷層次 x1=1 研究生， x1=2 本科 x2：專業(yè)類別 x2=1 電信類， x2=2 機(jī)電類 x3：學(xué)習(xí)基礎(chǔ) x3=1 修過 AI， x3=2 未修 AI 表 S。 決策樹學(xué)習(xí) 2. ID3算法 (5/11) 24 表 71 關(guān)于選課決策的訓(xùn)練例子集 在該表中，訓(xùn)練例子集 S的大小為８。 ID3算法是依據(jù)這些訓(xùn)練例子，以S為根節(jié)點(diǎn)，按照信息熵下降最大的原則來構(gòu)造決策樹的。 序號(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的大小。 )(log)()( 231iii yPyPSH ???? )(||||)/(itti SHSSxSH ?? 決策樹學(xué)習(xí) 2. ID3算法 (7/11) 26 下面先計(jì)算 S關(guān)于屬性 x1的條件熵： 在表 71中， x1的屬性值可以為 1或 2。當(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。 由 S1可知 ： Ps1(y1)=1/4, Ps1(y2)=1/4, Ps1(y3)=2/4 則有 ： H(S1)= Ps1(y1)log2 Ps1(y1) Ps1(y2)log2 Ps1(y2 ) Ps1(y3)log2 Ps1(y3 ) = (1/4