【文章內(nèi)容簡(jiǎn)介】 ，首先使決策樹得到充分生長(zhǎng)，然后再通過修剪降低決策樹的復(fù)雜度，從而保證決策樹的泛化能力。具體方法如下： （ 1）決策樹的構(gòu)建：在決策樹的構(gòu)建過程中，對(duì)于每一個(gè)可以進(jìn)一步劃分的結(jié)點(diǎn)都進(jìn)行劃分，直到得到一個(gè)不可進(jìn)一步劃分的子結(jié)點(diǎn)，并將該子結(jié)點(diǎn)定為葉結(jié)點(diǎn)。這樣構(gòu)造的決策樹，其葉結(jié)點(diǎn)均為不可再進(jìn)一步劃分的結(jié)點(diǎn)。 2022/2/15 《人工智能》 41 決策樹修剪（ 2） （ 2）在上述決策樹構(gòu)建完畢后，從葉結(jié)點(diǎn)一層開始，考察兄弟葉結(jié)點(diǎn)是否可以合并。如果可以合并，則對(duì)這些兄弟結(jié)點(diǎn)進(jìn)行合并，并將其父結(jié)點(diǎn)設(shè)為葉結(jié)點(diǎn)。在對(duì)所有可以合并的兄弟葉結(jié)點(diǎn)進(jìn)行合并后，可以形成一棵新的決策樹。對(duì)于新形成的決策樹，可以重復(fù)上述兄弟結(jié)點(diǎn)的合并過程，直到最后得到一棵決策樹，其中任意兩個(gè)兄弟葉結(jié)點(diǎn)都不再滿足合并的條件。這棵決策樹，就是我們最終選擇的決策樹。 2022/2/15 《人工智能》 42 決策樹修剪（ 3） ( ) ( ) ( ) ( )ny nnynnnN Ni n i n i n i nNN??? ? ? ?????()i n A??（ 3）兄弟葉結(jié)點(diǎn)合并的條件為 其中， ny及 nn為兄弟葉結(jié)點(diǎn)， n為其父結(jié)點(diǎn)。 Nn 為父結(jié)點(diǎn)中樣本的數(shù)量， Nny及 Nnn 為兩個(gè)子結(jié)點(diǎn)中樣本的數(shù)量。 上述合并條件中，△ i(n)代表了由于合并所導(dǎo)致的不純凈度的損失。 A為閾值，在修剪過程開始前預(yù)先設(shè)定。 葉結(jié)點(diǎn)的類別 設(shè)分類問題為 C類的分類問題。對(duì)于葉結(jié)點(diǎn) n，如果在該結(jié)點(diǎn)對(duì)應(yīng)的樣本中，屬于第 i 類的樣本數(shù)量最多，則判該葉結(jié)點(diǎn)為第 i類。 2022/2/15 《人工智能》 43 討論 （ 1）根據(jù)決策樹可以得出若干條規(guī)則。一條從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路途對(duì)應(yīng)于一條 IFTHEN規(guī)則。其中，路徑的非葉結(jié)點(diǎn)部分構(gòu)成了規(guī)則的條件部分（ IF部分），葉結(jié)點(diǎn)給出了規(guī)則的結(jié)論（ THEN部分）。 例子： IF COLOR=RED AND SIZE=MEDIUM THEN IT IS AN APPLE 用途：知識(shí)的獲取。 （ 2）決策樹方法同樣可用于連續(xù)取值的特征量。當(dāng)特征向量空間為歐氏空間時(shí)，同樣可以采用決策樹方法來構(gòu)造分類器。當(dāng)然，一般情況下在歐氏空間中通常采用神經(jīng)網(wǎng)絡(luò)來構(gòu)造分類器。 2022/2/15 《人工智能》 44 類比學(xué)習(xí) 類比 (analogy)是一種很有用的和有效的推理方法，它能夠清晰簡(jiǎn)潔地描述對(duì)象間的相似性；也是人類認(rèn)識(shí)世界的一種重要方法。 類比學(xué)習(xí) (learning by analogy)就是通過類比，即通過相似事物加以比較所進(jìn)行的一種學(xué)習(xí)。 例如，當(dāng)人們遇到一個(gè)新問題需要進(jìn)行處理，但又不具備處理這個(gè)問題的知識(shí)時(shí)，通常采用的辦法就是回憶一下過去處理過的類似問題，找出一個(gè)與目前情況最接近的處理方法來處理當(dāng)前問題。 2022/2/15 《人工智能》 45 類比推理和類比學(xué)習(xí) 類比推理 類比推理是由新情況與已知情況在某些方面的相似來推出它們?cè)谄渌嚓P(guān)方面的相似。顯然，類比推理是在兩個(gè)相似域之間進(jìn)行的：類比推理的目的是從源域中選出與當(dāng)前問題最近似的問題及其求解方法以求解決當(dāng)前的問題，或者建立起目標(biāo)域中已有命題間的聯(lián)系，形成新知識(shí)。 類比推理過程如下： (1) 回憶與聯(lián)想 遇到新情況或新問題時(shí)，首先通過回憶與聯(lián)想在 S中找出與當(dāng)前情況相似的情況，這些情況是過去已經(jīng)處理過的，有現(xiàn)成的解決方法及相關(guān)的知識(shí)。 2022/2/15 《人工智能》 46 (2) 選擇 從找出的相似情況中選出與當(dāng)前情況最相似的情況及其有關(guān)知識(shí)。 (3) 建立對(duì)應(yīng)映射 在 S與 T的相似情況之間建立相似元素的對(duì)應(yīng)關(guān)系，并建立起相應(yīng)的映射。 (4) 轉(zhuǎn)換 在上一步建立的映射下，把 S中的有關(guān)知識(shí)引到 T中來，從而建立起求解當(dāng)前問題的方法或者學(xué)習(xí)到關(guān)于 T的新知識(shí)。 2022/2/15 《人工智能》 47 類比學(xué)習(xí) 類比學(xué)習(xí)是基于類比推理的。類比學(xué)習(xí)的過程主要分為兩步：首先歸納找出源問題和目標(biāo)問題的公共性質(zhì)，然后再演繹推出從源問題到目標(biāo)問題的映射，得出目標(biāo)問題的新的性質(zhì)。所以類比學(xué)習(xí)既有歸納過程，又有演繹過程。 類比學(xué)習(xí)的主要過程可描述如下： (1) 輸入一組已知條件（已解決問題）和一組未完全確定的條件（新問題）。 (2) 對(duì)輸入的兩組條件，根據(jù)其描述，按某種相似性的定義尋找兩者可類比的對(duì)應(yīng)關(guān)系。 (3) 按相似變換的方法，將已有問題的概念、特性、方法、關(guān)系等映射到新問題上，以獲得待求解新問題所需的新知識(shí)。 (4) 對(duì)類推得到的新問題的知識(shí)進(jìn)行校驗(yàn)。驗(yàn)證正確的知識(shí)存入知識(shí)庫中，而暫時(shí)還無法驗(yàn)證的知識(shí)只能作為參考性知識(shí)，置于數(shù)據(jù)庫中。 2022/2/15 《人工智能》 48 基于范例的學(xué)習(xí) 范例（ case）： “范例是一段帶有上下文信息的知識(shí)，該知識(shí)表達(dá)了推理機(jī)在達(dá)到其目標(biāo)的過程中能起關(guān)鍵作用的經(jīng)驗(yàn)”。具體來說，一個(gè)范例應(yīng)具有如下特性： ? 范例表示了與某個(gè)上下文有關(guān)的具體知識(shí)，這種知識(shí)具有可操作性。 ? 范例可以是各式各樣的，可有不同的形狀和粒度，可涵蓋或大或小的時(shí)間片，可帶有問題的解答或動(dòng)作執(zhí)行后的效應(yīng)。 ? 范例記錄了有用的經(jīng)驗(yàn)，這種經(jīng)驗(yàn)?zāi)軒椭评頇C(jī)在未來更容易地達(dá)到目標(biāo)，或提醒推理機(jī)失敗發(fā)生的可能性有多大等等。 2022/2/15 《人工智能》 49 基于范例的推理 人們?yōu)榱私鉀Q一個(gè)新問題，先是進(jìn)行回憶，從記憶中找到一個(gè)與新問題相似的范例，然后把該范例中的有關(guān)信息和知識(shí)復(fù)用到新問題的求解之中。這種推理就是 基于范例的推理 (CaseBased Reasoning, CBR)，也簡(jiǎn)稱為范例推理。 在基于范例推理中，把當(dāng)前所面臨的問題或情況稱為目標(biāo)范例 (target case)，而把記憶的問題或情況稱為源范例 (base case)。粗略地說，基于范例推理就是由目標(biāo)范例的提示而獲得記憶中的源范例，并由源范例來指導(dǎo)目標(biāo)范例求解的一種策略。 2022/2/15 《人工智能》 50 范例推理基本流程 提出解決方案 確認(rèn)解決方案 以前案例 新案例 學(xué)過的 案例 取回案例 新案例 解決的案例 修改 案例 一般知識(shí) 提取 使用 修改 保留 問題 2022/2/15 《人工智能》 51 ? 基于范例推理中知識(shí)表示是以范例為基礎(chǔ) ， 范例的獲取比規(guī)則獲取要容易 ， 大大簡(jiǎn)化知識(shí)獲取 。 ? 對(duì)過去的求解結(jié)果進(jìn)行復(fù)用 ， 而不是再次從頭推導(dǎo) ， 可以提高對(duì)新問題的求解效率 。 ? 過去求解成功或失敗的經(jīng)歷可以指導(dǎo)當(dāng)前求解時(shí)該怎樣走向成功或避開失敗 ， 這樣可以改善求解的質(zhì)量 。 ? 對(duì)于那些目前沒有或根本不存在的問題 ， 可以通過計(jì)算推導(dǎo)來解決的問題 。 如在法律中的判例 ，基于范例推理能很好發(fā)揮作用 。 范例推理的特點(diǎn) 2022/2/15 《人工智能》 52 基于范例的學(xué)習(xí) 基于范例的推理系統(tǒng)經(jīng)過不斷的積累經(jīng)驗(yàn)（案例），同時(shí)合適地對(duì)其進(jìn)行索引，系統(tǒng)的推理效率和問題求解能力會(huì)隨之增加。因此在 CBR中，學(xué)習(xí)的主要任務(wù)是對(duì)案例庫的豐富和優(yōu)化。 在 CBR中，大多數(shù)學(xué)習(xí)是通過如下兩種方式體現(xiàn)的：一個(gè)是新范例的積累，推理系統(tǒng)的范例對(duì)問題的覆蓋越多，其功能越強(qiáng)；另一個(gè)是設(shè)計(jì)覆蓋了成功事例也覆蓋了失敗事例的推理要比只設(shè)計(jì)成功情況的推理系統(tǒng)要好，索引的重新賦值，調(diào)節(jié)索引可使得范例能在更合適的時(shí)機(jī)被回憶。 2022/2/15 《人工智能》 53 基于范例學(xué)習(xí)的一般過程 新問題 新范例 檢索 歷史范例 范例庫 復(fù)用 保存 修正范例 修正 解答范例 確認(rèn)解 建議解 2022/2/15 《人工智能》 54 范例的內(nèi)容 (1) 問題或情景描述： 是對(duì)要求解的問題或要理解的情景的描述 ， 一般要包括這些內(nèi)容：當(dāng)范例發(fā)生時(shí)推理器的目標(biāo) ， 完成該目標(biāo)所要涉及的任務(wù) ， 周圍世界或環(huán)境與可能解決方案相關(guān)的所有特征 。 (2) 解決方案： 是問題如何在一特定情形下得到解決 。 它可能是對(duì)問題的簡(jiǎn)單解答 ， 也可能是得出解答的推導(dǎo)過程 。 (3) 結(jié)果： 記錄了實(shí)施解決方案后的結(jié)果情況 ， 是失敗還是成功 。 有了結(jié)果內(nèi)容 ， CBR在給出建議解時(shí)有能給出曾經(jīng)成功地工作的范例 ， 同時(shí)也能利用失敗的范例來避免可能會(huì)發(fā)生的問題 。 當(dāng)對(duì)問題還缺乏足夠的了解時(shí) ， 通過在范例的表示上加上結(jié)果部分能取得較好的效果 。 2022/2/15 《人工智能》 55 范例的索引 建立范例索引有三個(gè)原則： ① 索引與具體領(lǐng)域有關(guān) 。 數(shù)據(jù)庫中的索引是通用的 ， 目的僅僅是追求索引能對(duì)數(shù)據(jù)集合進(jìn)行平衡的劃分從而使得檢索速度最快；而范例索引則要考慮是否有利于將來的范例檢索 ， 它決定了針對(duì)某個(gè)具體的問題哪些范例被復(fù)用； ② 索引應(yīng)該有一定的抽象或泛化程度 ， 這樣才能靈活處理以后可能遇到的各種情景 ， 太具體則不能滿足更多的情況； ③ 索引應(yīng)該有一定的具體性 ， 這樣才能在以后被容易地識(shí)別出來 ， 太抽象則各個(gè)范例之間的差別將被消除 。 2022/2/15 《人工智能》 56 范例學(xué)習(xí)的主要問題（ 1） (1) 范例表示 ：基于范例推理方法的效率和范例表示緊密相關(guān)。范例表示涉及這樣幾個(gè)問題 : 選擇什么信息存放在一個(gè)范例中；如何選擇合適的范例內(nèi)容描述結(jié)構(gòu)；范例庫如何組織和索引。對(duì)于那些數(shù)量達(dá)到成千上萬、而且十分復(fù)雜的范例 , 組織和索引問題尤其重要。 (2) 分析模型 ：分析模型用于分析目標(biāo)范例，從中識(shí)別和抽取檢索源范例庫的信息。 (3) 范例檢索 ：利用檢索信息從源范例庫中檢索并選擇潛在可用的源范例。這步非常關(guān)鍵。一般講，范例匹配不是精確的，只能是部分匹配或近似匹配。因此，它要求有一個(gè)相似度的評(píng)價(jià)標(biāo)準(zhǔn)。該標(biāo)準(zhǔn)定義得好，會(huì)使得檢索出的范例十分有用，否則將會(huì)嚴(yán)重影響后面的過程。 2022/2/15 《人工智能》 57 范例學(xué)習(xí)的主要問題（ 2） (4) 類比映射 : 尋找目標(biāo)范例同源范例之間的對(duì)應(yīng)關(guān)系。 (5) 類比轉(zhuǎn)換 : 轉(zhuǎn)換源范例中同目標(biāo)范例相關(guān)的信息，以便應(yīng)用于目標(biāo)范例的求解過程中。把檢索到的源范例的解答復(fù)用于新問題或新范例之中需要解決的問題分別是：源范例與目標(biāo)范例間有何不同之處；源范例中的哪些部分可以用于目標(biāo)范例。需要根據(jù)它們之間的不同對(duì)復(fù)用的求解方案進(jìn)行調(diào)整。 (6) 解釋過程 : 對(duì)把轉(zhuǎn)換過的源范例的求解方案應(yīng)用到目標(biāo)范例時(shí)所出現(xiàn)的失敗做出解釋，給出失敗的因果分析報(bào)告。有時(shí)對(duì)成功也同樣做出解釋?；诮忉尩乃饕彩且环N重要的方法。 (7) 范例修補(bǔ) : 有些類似于類比轉(zhuǎn)換，區(qū)別在于修補(bǔ)過程的輸入是解方案和一個(gè)失敗報(bào)告，而且也許還包含一個(gè)解釋，然后修改這個(gè)解以排除失敗的因素。 2022/2/15 《人工智能》 58 范例學(xué)習(xí)的主要問題（ 3） (8) 類比驗(yàn)證 : 驗(yàn)證目標(biāo)范例和源范例進(jìn)行類比的有效性。 (9) 范例保存 : 新問題得到了解決，則形成了一個(gè)可能用于將來情形與之相似的問題。這時(shí)有必要把它加入到范例庫中。這是學(xué)習(xí)也是知識(shí)獲取。此過程涉及選取哪些信息保留，以及如何把新范例有機(jī)集成到范例庫中。修改和精化源范例庫 , 其中包括泛化和抽象等過程。 在決定選取范例的哪些信息進(jìn)行保留時(shí)，一般要考慮以下幾點(diǎn)：和問題有關(guān)的特征描述；問題的求解結(jié)果；以及解答為什么成功或失敗的原因及解釋。 把新范例加入到范例庫中， 需要對(duì)它建立有效的索引，這樣以后才能對(duì)之作出有效的回憶。為此，可能要對(duì)范例庫的索引內(nèi)容甚至結(jié)構(gòu)進(jìn)行調(diào)整，如改變索引的強(qiáng)度或特征權(quán)值。 2022/2/15 《人工智能》 59 解釋學(xué)習(xí) 基于解釋的學(xué)習(xí)： ? 一種從單個(gè)觀察中抽象出通用規(guī)則的方法 ? 目標(biāo)是下次可以快速地解決類似的問題 ? 通過保存結(jié)果和避免從零開始解決問題來提高速度 ? 更進(jìn)一步 EBL從觀察到規(guī)則 解釋學(xué)習(xí) (ExplanationBased Learning, 簡(jiǎn)稱 EBL)是一種分析學(xué)習(xí)方法，在領(lǐng)域知識(shí)指導(dǎo)下 , 通過對(duì)單個(gè)問題求解實(shí)例的分析 , 構(gòu)造出求解過程的因果解釋結(jié)構(gòu) , 并獲取控制知識(shí) ,以便用于指導(dǎo)以后求解類似問題。 2022/2/15 《人工智能》 60 解釋學(xué)習(xí)過程和算法 解釋學(xué)習(xí)一般包括下列 3個(gè)步驟： (1) 利用基于解釋的方法對(duì)訓(xùn)練例子進(jìn)行分析與解釋。 (2) 對(duì)例子的結(jié)構(gòu)進(jìn)行概括性解釋。 (3) 從解釋結(jié)構(gòu)中識(shí)別出訓(xùn)練例子的特性，獲取一般控制知識(shí)。