《人工智能課件 －07機(jī)器學(xué)習(xí)》由會(huì)員分享，可在線閱讀，更多相關(guān)《人工智能課件 －07機(jī)器學(xué)習(xí)（81頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第7章 機(jī)器學(xué)習(xí)第一節(jié) 基本概念一、什么是機(jī)器學(xué)習(xí)一、什么是機(jī)器學(xué)習(xí)一、什么是機(jī)器學(xué)習(xí)一、什么是機(jī)器學(xué)習(xí)1、學(xué)習(xí)對(duì)“學(xué)習(xí)”概念研究有較大影響的幾種觀點(diǎn)：(1)學(xué)習(xí)是系統(tǒng)改進(jìn)其性能的過(guò)程-西蒙的觀點(diǎn)(2)學(xué)習(xí)是獲取知識(shí)的過(guò)程-ES專家的觀點(diǎn)(3)學(xué)習(xí)是技能的獲取-心理學(xué)家的觀點(diǎn)(4)學(xué)習(xí)是事物規(guī)律的發(fā)現(xiàn)過(guò)程-AI專家的觀點(diǎn)綜合觀點(diǎn)：綜合觀點(diǎn)：綜合觀點(diǎn)：綜合觀點(diǎn)：學(xué)習(xí)是一個(gè)有特定目的的知識(shí)獲取過(guò)程，其內(nèi)在的行為是獲取知識(shí)、積累經(jīng)驗(yàn)、發(fā)現(xiàn)規(guī)律；外部表現(xiàn)為改進(jìn)性能、適應(yīng)環(huán)境、實(shí)現(xiàn)系統(tǒng)的自我完善。第一節(jié) 基本概念2、機(jī)器學(xué)習(xí) 所謂機(jī)器學(xué)習(xí)就是使計(jì)算機(jī)能模擬人的學(xué)習(xí)行為，自動(dòng)地通過(guò)學(xué)習(xí)獲取知識(shí)和技能，不斷

2、改善其性能，實(shí)現(xiàn)自我完善。q機(jī)器學(xué)習(xí)研究工作的主要方面機(jī)器學(xué)習(xí)研究工作的主要方面機(jī)器學(xué)習(xí)研究工作的主要方面機(jī)器學(xué)習(xí)研究工作的主要方面(1)學(xué)習(xí)機(jī)理的研究；(2)學(xué)習(xí)方法的研究；(3)面向任務(wù)的學(xué)習(xí)。第一節(jié) 基本概念二、機(jī)器學(xué)習(xí)的發(fā)展歷史二、機(jī)器學(xué)習(xí)的發(fā)展歷史二、機(jī)器學(xué)習(xí)的發(fā)展歷史二、機(jī)器學(xué)習(xí)的發(fā)展歷史大致分為四個(gè)階段。(1)第一階段，20世紀(jì)50年代中期到60年代中期，稱為熱烈時(shí)期。研究的內(nèi)容主要是“沒(méi)有知識(shí)”的學(xué)習(xí)，其對(duì)象是各類自組織系統(tǒng)和自適應(yīng)系統(tǒng)，主要方法是不斷修改系統(tǒng)的控制參數(shù)以改進(jìn)系統(tǒng)的性能，不涉及與具體任務(wù)有關(guān)的知識(shí)。(2)第二階段，20世紀(jì)60年代中期到70年代中期，稱為冷靜時(shí)期

3、。研究目標(biāo)是模擬人類的概念學(xué)習(xí)過(guò)程，并采用邏輯結(jié)構(gòu)和圖結(jié)構(gòu)作為機(jī)器內(nèi)部的描述。第一節(jié) 基本概念(3)第三階段，20世紀(jì)70年代中期到80年代中期，稱為復(fù)興時(shí)期。單概念學(xué)習(xí)擴(kuò)展到多概念學(xué)習(xí)，探索不同的學(xué)習(xí)策略和學(xué)習(xí)方法。機(jī)器的學(xué)習(xí)過(guò)程一般建立在大規(guī)模的知識(shí)庫(kù)上，實(shí)現(xiàn)知識(shí)強(qiáng)化學(xué)習(xí)。示例歸約學(xué)習(xí)成為研究的主流。(4)第四階段，20世紀(jì)80年代中期以后，符號(hào)學(xué)習(xí)由“無(wú)知”學(xué)習(xí)轉(zhuǎn)向到有專門(mén)領(lǐng)域知識(shí)的增長(zhǎng)型學(xué)習(xí)，因而出現(xiàn)了有一定知識(shí)背景的分析學(xué)習(xí)。第二節(jié) 主要策略與基本結(jié)構(gòu)一、主要策略一、主要策略一、主要策略一、主要策略 機(jī)械學(xué)習(xí)策略 指導(dǎo)式學(xué)習(xí)策略 類比學(xué)習(xí)策略 示例學(xué)習(xí)策略二、機(jī)器學(xué)習(xí)的分類二、機(jī)器學(xué)

4、習(xí)的分類二、機(jī)器學(xué)習(xí)的分類二、機(jī)器學(xué)習(xí)的分類q1、按系統(tǒng)的學(xué)習(xí)能力分 有監(jiān)督學(xué)習(xí) 無(wú)監(jiān)督學(xué)習(xí)q2、按學(xué)習(xí)方法分 機(jī)械式學(xué)習(xí) 指導(dǎo)式學(xué)習(xí) 類比學(xué)習(xí) 示例學(xué)習(xí) 解釋學(xué)習(xí)q3、按推理方式分 演繹學(xué)習(xí) 歸納學(xué)習(xí)q4、按綜合屬性分 歸納學(xué)習(xí) 分析學(xué)習(xí) 連接學(xué)習(xí) 遺傳算法 分類器系統(tǒng)第二節(jié) 主要策略與基本結(jié)構(gòu)第二節(jié) 主要策略與基本結(jié)構(gòu)三、機(jī)器學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)三、機(jī)器學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)三、機(jī)器學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)三、機(jī)器學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)環(huán)境學(xué)習(xí)知識(shí)庫(kù)執(zhí)行學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu) 一個(gè)學(xué)習(xí)系統(tǒng)應(yīng)具有環(huán)境、學(xué)習(xí)、知識(shí)庫(kù)、執(zhí)行四個(gè)要素。1973年莎利斯關(guān)于機(jī)器學(xué)習(xí)系統(tǒng)的定義：如果一個(gè)系統(tǒng)能夠從某個(gè)過(guò)

5、程或環(huán)境的未知特征中學(xué)到有關(guān)信息，并且能把學(xué)到的信息用于未來(lái)的估計(jì)、分類、決策或控制，以便改進(jìn)系統(tǒng)的性能，那么它就是學(xué)習(xí)系統(tǒng)，因此，一個(gè)學(xué)習(xí)系統(tǒng)應(yīng)具有環(huán)境、具有一定的學(xué)習(xí)能力、能應(yīng)用知識(shí)求解問(wèn)題、能提高系統(tǒng)的性能。環(huán)境向系統(tǒng)的學(xué)習(xí)部分提供某些信息，學(xué)習(xí)部分利用這些信息修改知識(shí)庫(kù)，以增進(jìn)系統(tǒng)執(zhí)行部分完成任務(wù)的效能，執(zhí)行部分根據(jù)知識(shí)庫(kù)完成任務(wù)，同時(shí)把獲得的信息反饋給學(xué)習(xí)部分。第二節(jié) 主要策略與基本結(jié)構(gòu)q影響學(xué)習(xí)系統(tǒng)設(shè)計(jì)的重要因素影響學(xué)習(xí)系統(tǒng)設(shè)計(jì)的重要因素影響學(xué)習(xí)系統(tǒng)設(shè)計(jì)的重要因素影響學(xué)習(xí)系統(tǒng)設(shè)計(jì)的重要因素(1)環(huán)境向系統(tǒng)提供的信息質(zhì)量(2)知識(shí)的表示形式q選擇表示方式時(shí)，應(yīng)注意的問(wèn)題選擇表示方式時(shí)

6、，應(yīng)注意的問(wèn)題選擇表示方式時(shí)，應(yīng)注意的問(wèn)題選擇表示方式時(shí)，應(yīng)注意的問(wèn)題 表達(dá)能力 易于推理 容易修改知識(shí)庫(kù) 知識(shí)表示易于擴(kuò)展第三節(jié) 機(jī)械學(xué)習(xí) 機(jī)械學(xué)習(xí)又稱為死記硬背式學(xué)習(xí)，是一種最簡(jiǎn)單、最原始的學(xué)習(xí)方法。q基本思想：基本思想：基本思想：基本思想：把新的知識(shí)存儲(chǔ)起來(lái)，供需要時(shí)檢索調(diào)用，而無(wú)需推理和計(jì)算。在機(jī)械學(xué)習(xí)中只記憶計(jì)算的輸入輸出，忽略計(jì)算過(guò)程，因此就把計(jì)算問(wèn)題化簡(jiǎn)成存儲(chǔ)問(wèn)題。即：(X1,X2,Xn)(Y1,Y2,Ym)f(X1,X2,Xn)(Y1,Y2,Ym)第三節(jié) 機(jī)械學(xué)習(xí)q機(jī)械學(xué)習(xí)的主要問(wèn)題機(jī)械學(xué)習(xí)的主要問(wèn)題機(jī)械學(xué)習(xí)的主要問(wèn)題機(jī)械學(xué)習(xí)的主要問(wèn)題(1)存儲(chǔ)信息的組織；(2)環(huán)境的穩(wěn)定性與

7、存儲(chǔ)的信息的通用性；(3)存儲(chǔ)與計(jì)算之間的權(quán)衡。第四節(jié) 歸納學(xué)習(xí) 歸納學(xué)習(xí)是應(yīng)用歸納推理進(jìn)行學(xué)習(xí)的一類方法，分為示例學(xué)習(xí)(有教師)、觀察與發(fā)現(xiàn)學(xué)習(xí)(無(wú)教師)兩種。一、歸納推理一、歸納推理一、歸納推理一、歸納推理從具體到一般的推理方法。q歸納推理的重要特性歸納推理的重要特性歸納推理的重要特性歸納推理的重要特性(1).歸納出的結(jié)論只能以某種程度相信它為真；(2).歸納推理是非單調(diào)的。第四節(jié) 歸納學(xué)習(xí)q常用的歸納推理方法常用的歸納推理方法常用的歸納推理方法常用的歸納推理方法1、枚舉歸納2、聯(lián)想歸納3、類比歸納4、逆推理歸納5、消除歸納1、枚舉歸納 設(shè)a1,a2,an是某類事物A中的具體事物，若已知a

8、1,a2,an都有屬性P，并且沒(méi)有發(fā)現(xiàn)反例，當(dāng)n足夠大時(shí)，就可得出結(jié)論：“A中所有事物都具有屬性P”。例如、張三是足球運(yùn)動(dòng)員，他的體格健壯。李四是足球運(yùn)動(dòng)員，他的體格健壯。劉六是足球運(yùn)動(dòng)員，他的體格健壯。當(dāng)事實(shí)足夠多時(shí)，可歸納出：“凡是足球運(yùn)動(dòng)員，他的體格一定健壯”的一般性結(jié)論。第四節(jié) 歸納學(xué)習(xí)第四節(jié) 歸納學(xué)習(xí)如果，每個(gè)實(shí)例都帶有一定得可信度因子，例如、張三是足球運(yùn)動(dòng)員，他的體格健壯(0.95)。李四是足球運(yùn)動(dòng)員，他的體格健壯(0.90)。劉六是足球運(yùn)動(dòng)員，他的體格健壯(1.0)。則可用各個(gè)實(shí)例可信度的平均值作為一般知識(shí)的可信度。例如、得出的結(jié)論：“凡是足球運(yùn)動(dòng)員，他的體格一定健壯”(0.95

9、)第四節(jié) 歸納學(xué)習(xí)2、聯(lián)想歸納 若已知兩個(gè)事物a與b有n個(gè)屬性相似或相同，即 a具有屬性P1，b具有屬性P1 a具有屬性P2，b具有屬性P2 a具有屬性Pn，b具有屬性Pn發(fā)現(xiàn)a具有屬性Pn+1，則當(dāng)n足夠大時(shí)，可歸納出：b也具有屬性Pn+1 的結(jié)論。第四節(jié) 歸納學(xué)習(xí)3、類比歸納設(shè)A、B分別是兩類事物的集合：A=a1,a2,B=b1,b2,并ai和bi總是成對(duì)出現(xiàn)，且當(dāng)ai有屬性P時(shí)，bi就有屬性Q與之對(duì)應(yīng)，即 P(ai)Q(bi)則當(dāng)A與B有一對(duì)新元素出現(xiàn)時(shí)，設(shè)為a和b，若已知a有屬性P，就可得出b有屬性Q，即 P(a)Q(b)第四節(jié) 歸納學(xué)習(xí)4、逆推理歸納 是一種由結(jié)論成立而推出前提以某種

10、可信度成立的歸納方法。一般模式是：(1)若H為真時(shí)，則HE必為真或以可信度cf1成立；(2)觀察到E成立或以可信度cf2成立；(3)則H以某種可信度cf成立。表示為：H E cf1 E cf2 H cfcf的計(jì)算方法可根據(jù)問(wèn)題的實(shí)際情況而定。例如，可把P(E|H)當(dāng)成HE的可信度cf1，則EH的可信度cf1可按Bayes公式計(jì)算。由cf1和cf2就可計(jì)算出H的可信度 cf=cf1cf2第四節(jié) 歸納學(xué)習(xí)5、消除歸納 當(dāng)我們對(duì)某個(gè)事物發(fā)生的原因不清楚時(shí)，通常會(huì)作一些假設(shè)，這些假設(shè)之間是析取關(guān)系。以后，隨著對(duì)事物認(rèn)識(shí)的不斷深化，原先作出的某些假設(shè)有可能被否定，經(jīng)過(guò)若干次否定后，剩下的就可作為事物發(fā)生

11、的原因。這樣的思維過(guò)程稱為消除歸納。已知：A1 V A2 V V An A1 Ai 結(jié)論：Aj第四節(jié) 歸納學(xué)習(xí)二、示例學(xué)習(xí)二、示例學(xué)習(xí)二、示例學(xué)習(xí)二、示例學(xué)習(xí) 示例學(xué)習(xí)是通過(guò)從環(huán)境中獲得若干與某個(gè)概念相關(guān)的示例，經(jīng)歸納得出一般性概念的學(xué)習(xí)方法。1 1、示例學(xué)習(xí)的學(xué)習(xí)模型、示例學(xué)習(xí)的學(xué)習(xí)模型、示例學(xué)習(xí)的學(xué)習(xí)模型、示例學(xué)習(xí)的學(xué)習(xí)模型示例空間搜索解釋形成知識(shí)知識(shí)庫(kù)驗(yàn)證第四節(jié) 歸納學(xué)習(xí)示例學(xué)習(xí)的學(xué)習(xí)過(guò)程：示例學(xué)習(xí)的學(xué)習(xí)過(guò)程：示例學(xué)習(xí)的學(xué)習(xí)過(guò)程：示例學(xué)習(xí)的學(xué)習(xí)過(guò)程：首先從示例空間中選擇合適的訓(xùn)練示例，然后經(jīng)解釋歸納出一般性知識(shí)，最后再?gòu)氖纠臻g中選擇更多的示例對(duì)它進(jìn)行驗(yàn)證。與示例空間有關(guān)的主要問(wèn)題是示例

12、的質(zhì)量。與示例空間有關(guān)的主要問(wèn)題是示例的質(zhì)量。與示例空間有關(guān)的主要問(wèn)題是示例的質(zhì)量。與示例空間有關(guān)的主要問(wèn)題是示例的質(zhì)量。“搜索”作用是從示例空間中查找所需的示例；“解釋”是從搜索到的示例中抽象出所需的有關(guān)信息供形成知識(shí)使用?！靶纬芍R(shí)”通過(guò)綜合、歸納等形式形成一般的知識(shí)?！膀?yàn)證”檢驗(yàn)所形成的知識(shí)的正確性。第四節(jié) 歸納學(xué)習(xí)2、形成知識(shí)的方法(1)變量代換常量 是枚舉歸納的常用方法。例如，“同花”概念的形成示例1：花色(c1,C)花色(c2,C)花色(c3,C)花色(c4,C)同花(c1,c2,c3,c4)示例2：花色(c1,H)花色(c2,H)花色(c3,H)花色(c4,H)同花(c1,c2,

13、c3,c4)將這兩個(gè)示例中的常量C和H用變量x代換即可形成一般性知識(shí)：花色(c1,x)花色(c2,x)花色(c3,x)花色(c4,x)同花(c1,c2,c3,c4)第四節(jié) 歸納學(xué)習(xí)(2)舍棄條件 是把示例中的某些無(wú)關(guān)條件的子條件舍去。例如：花色(c1,C)點(diǎn)數(shù)(c1,2)花色(c2,C)點(diǎn)數(shù)(c2,4)花色(c3,C)點(diǎn)數(shù)(c3,6)花色(c4,C)點(diǎn)數(shù)(c4,2)同花(c1,c2,c3,c4)由于點(diǎn)數(shù)對(duì)形成“同花”概念無(wú)直接影響，則可把示例中的“點(diǎn)數(shù)”舍去。第四節(jié) 歸納學(xué)習(xí)(3)增加操作 有時(shí)需要通過(guò)增加操作來(lái)形成知識(shí)，常用的方法有前件析取法和內(nèi)部析取法。前件析取法：前件析取法：前件析取法：

14、前件析取法：通過(guò)對(duì)示例的前件進(jìn)行析取形成知識(shí)。例如，“臉牌”示例1:點(diǎn)數(shù)(c1,J)臉(c1)示例2:點(diǎn)數(shù)(c1,Q)臉(c1)示例3:點(diǎn)數(shù)(c1,K)臉(c1)若將各示例的前件進(jìn)行析取，則可得到一般知識(shí)：規(guī)則：點(diǎn)數(shù)(c1,J)V 點(diǎn)數(shù)(c1,Q)V 點(diǎn)數(shù)(c1,K)臉(c1)第四節(jié) 歸納學(xué)習(xí) 內(nèi)部析取法內(nèi)部析取法內(nèi)部析取法內(nèi)部析取法：在示例的表示中使用集合與集合間的成員關(guān)系來(lái)形成知識(shí)。例如，“臉牌”示例1:點(diǎn)數(shù)(c1)J臉(c1)示例2:點(diǎn)數(shù)(c1)Q臉(c1)示例3:點(diǎn)數(shù)(c1)K臉(c1)用內(nèi)部析取法可得到一般知識(shí)：規(guī)則：點(diǎn)數(shù)(c1)J,Q,K臉(c1)第四節(jié) 歸納學(xué)習(xí)(4)合取變析取

15、是通過(guò)把示例中條件的合取關(guān)系變?yōu)槲鋈￡P(guān)系來(lái)形成一般性知識(shí)的。例如，由“男同學(xué)和女同學(xué)可以組成一個(gè)班”，可以歸納出“男同學(xué)或女同學(xué)可以組成一個(gè)班”(5)歸結(jié)歸納 利用歸結(jié)原理，可得到如下形成知識(shí)的方法。PE1H PE2H可得到：E1E2H第四節(jié) 歸納學(xué)習(xí)三、觀察與發(fā)現(xiàn)學(xué)習(xí)三、觀察與發(fā)現(xiàn)學(xué)習(xí)三、觀察與發(fā)現(xiàn)學(xué)習(xí)三、觀察與發(fā)現(xiàn)學(xué)習(xí) 觀察學(xué)習(xí)(主要用于概念聚類)觀察與發(fā)現(xiàn)學(xué)習(xí) 機(jī)器發(fā)現(xiàn)(發(fā)現(xiàn)規(guī)律、或規(guī)則)1、概念聚類 基本思想：基本思想：基本思想：基本思想：把示例按一定的方式和準(zhǔn)則進(jìn)行分組，如劃分為不同的類、不同的層次等，使不同的組代表不同的概念，并且對(duì)每一組進(jìn)行特征概括，得到一個(gè)概念的語(yǔ)義描述。2、機(jī)

16、器發(fā)現(xiàn) 困難的。第五節(jié) 類比學(xué)習(xí) 類比學(xué)習(xí)是通過(guò)對(duì)相似事物進(jìn)行比較所進(jìn)行的一種學(xué)習(xí)方法，基礎(chǔ)是類比推理。例如、盧瑟福將原子結(jié)構(gòu)和太陽(yáng)系進(jìn)行類比，發(fā)現(xiàn)了原子結(jié)構(gòu)；水管中的水壓計(jì)算公式與電路中的電壓計(jì)算公式相似。第五節(jié) 類比學(xué)習(xí)一、類比推理一、類比推理一、類比推理一、類比推理 類比推理是指，由新情況與記憶中的已知情況在某些方面相似，從而推出它們?cè)谄渌嚓P(guān)方面也相似。類比推理是在兩個(gè)相似域之間進(jìn)行的：一個(gè)是已認(rèn)識(shí)的域，稱為源域，記為 S；另一個(gè)是當(dāng)前尚未完全認(rèn)識(shí)的域，稱為目標(biāo)域，記為T(mén)。類比推理的目的就是從S中選出與當(dāng)前問(wèn)題最近似的問(wèn)題及其求解方法來(lái)求解當(dāng)前的問(wèn)題，或者建立起目標(biāo)域中已有命題間的聯(lián)系

17、，形成新知識(shí)。設(shè)S1、T1分別表示 S 與 T 中的某一情況，且S1與T1相似，再假設(shè)S2與S1相關(guān)，則由類比推理可推出T中的T2,且T2與S2相似。第五節(jié) 類比學(xué)習(xí)q推理過(guò)程推理過(guò)程推理過(guò)程推理過(guò)程(1)回憶與聯(lián)想 通過(guò)回憶與聯(lián)想在S中找出與當(dāng)前問(wèn)題相似的問(wèn)題。(2)選擇 從S的相似的問(wèn)題選出最相似的問(wèn)題。(3)建立對(duì)應(yīng)關(guān)系 在S與T相似的問(wèn)題之間建立相似元素的對(duì)應(yīng)關(guān)系，并建立相應(yīng)的映射。(4)轉(zhuǎn)換 把S中的有關(guān)知識(shí)引入到T中，從而建立起求解當(dāng)前問(wèn)題的方法或者學(xué)習(xí)到關(guān)于T的新知識(shí)。第五節(jié) 類比學(xué)習(xí)q類比推理形式的說(shuō)明類比推理形式的說(shuō)明類比推理形式的說(shuō)明類比推理形式的說(shuō)明 設(shè)有兩個(gè)具有相同或相

18、似的論域：源域S和目標(biāo)域T，且已知S中的元素a和T中的元素b具有相似的屬性P，即P(a)P(b)，a還具有屬性Q，即Q(a)。根據(jù)類比推理，b也具有屬性Q。即 P(a)Q(a),P(a)P(b)|-Q(b)Q(a)第五節(jié) 類比學(xué)習(xí)二、類比學(xué)習(xí)二、類比學(xué)習(xí)二、類比學(xué)習(xí)二、類比學(xué)習(xí)主要包括四個(gè)過(guò)程(1)輸入一組已知條件(已解決的問(wèn)題)和一組未完全確定的條件(新問(wèn)題)；(2)對(duì)輸入的兩組條件，根據(jù)其描述，按某種相似性的定義尋找兩者可類比的對(duì)應(yīng)關(guān)系；(3)根據(jù)相似變換的方法，將已解決的問(wèn)題的概念、特性、方法、關(guān)系等映射到新問(wèn)題上，以獲得待求解新問(wèn)題的新知識(shí)；(4)對(duì)類比推理中得到的新知識(shí)進(jìn)行驗(yàn)證。第五

19、節(jié) 類比學(xué)習(xí)q類比學(xué)習(xí)的研究分為兩類類比學(xué)習(xí)的研究分為兩類類比學(xué)習(xí)的研究分為兩類類比學(xué)習(xí)的研究分為兩類(1)問(wèn)題求解型的類比學(xué)習(xí) 基本思想：基本思想：基本思想：基本思想：是當(dāng)求解一個(gè)新問(wèn)題時(shí)，總是首先回憶以 前是否求解過(guò)類似的問(wèn)題，若是，則可以 此為根據(jù)，通過(guò)對(duì)先前的求解過(guò)程加以適 當(dāng)修改，使之滿足新問(wèn)題的解。(2)預(yù)測(cè)推定型的類比學(xué)習(xí) 又分為傳統(tǒng)的類比法和因果關(guān)系型的類比兩種類型。第五節(jié) 類比學(xué)習(xí) 傳統(tǒng)類比法 傳統(tǒng)類比法可用來(lái)推斷一個(gè)不完全確定的事物可能還具有的其他屬性。因果關(guān)系型類比 因果關(guān)系型類比的基本問(wèn)題是：已知因果關(guān)系S1:AB，給定事物 A與A相似，則可能有與B相似的事物B滿足因果

20、關(guān)系 S2:AB。進(jìn)行類比的關(guān)鍵是匹配，實(shí)現(xiàn)匹配的常用方法：進(jìn)行類比的關(guān)鍵是匹配，實(shí)現(xiàn)匹配的常用方法：進(jìn)行類比的關(guān)鍵是匹配，實(shí)現(xiàn)匹配的常用方法：進(jìn)行類比的關(guān)鍵是匹配，實(shí)現(xiàn)匹配的常用方法：等價(jià)匹配：兩個(gè)對(duì)象之間具有完全相同的特性數(shù)據(jù)。選擇匹配：選擇中特性進(jìn)行匹配。規(guī)則匹配：規(guī)則的前提和結(jié)論都匹配，則規(guī)則匹配。啟發(fā)式匹配：通過(guò)抽象，在更高層次上進(jìn)行匹配。第六節(jié) 解釋學(xué)習(xí) 一種分析學(xué)習(xí)方法?；舅枷耄夯舅枷耄夯舅枷耄夯舅枷耄和ㄟ^(guò)運(yùn)用相關(guān)的領(lǐng)域知識(shí)，對(duì)當(dāng)前提供的實(shí)例進(jìn)行分析，從而構(gòu)造解釋并產(chǎn)生相應(yīng)的知識(shí)。已建立的系統(tǒng)，米切爾的LEX、LEAP；明頓的PRODIGY等。第六節(jié) 解釋學(xué)習(xí)一、基于解釋

21、學(xué)習(xí)的概念一、基于解釋學(xué)習(xí)的概念一、基于解釋學(xué)習(xí)的概念一、基于解釋學(xué)習(xí)的概念 通過(guò)運(yùn)用相關(guān)的領(lǐng)域知識(shí)及一個(gè)訓(xùn)練實(shí)例來(lái)對(duì)某個(gè)目標(biāo)概念進(jìn)行學(xué)習(xí)，并最終形成對(duì)這個(gè)概念的一般性描述。q米切爾關(guān)于解釋學(xué)習(xí)的一般框架米切爾關(guān)于解釋學(xué)習(xí)的一般框架米切爾關(guān)于解釋學(xué)習(xí)的一般框架米切爾關(guān)于解釋學(xué)習(xí)的一般框架給定：領(lǐng)域知識(shí)DT,目標(biāo)概念TC,訓(xùn)練實(shí)例TE,操作性準(zhǔn)則OC。找出：滿足OC的關(guān)于TC的充分條件。第六節(jié) 解釋學(xué)習(xí)二、基于解釋學(xué)習(xí)的學(xué)習(xí)過(guò)程二、基于解釋學(xué)習(xí)的學(xué)習(xí)過(guò)程二、基于解釋學(xué)習(xí)的學(xué)習(xí)過(guò)程二、基于解釋學(xué)習(xí)的學(xué)習(xí)過(guò)程 1、構(gòu)造解釋 學(xué)習(xí)過(guò)程 2、獲取一般性知識(shí)1、構(gòu)造解釋 任務(wù)：任務(wù)：任務(wù)：任務(wù)：證明提供給

22、系統(tǒng)的訓(xùn)練實(shí)例為什么是滿足目標(biāo)概念的一個(gè)實(shí)例。證明過(guò)程通過(guò)運(yùn)用領(lǐng)域知識(shí)進(jìn)行演繹實(shí)現(xiàn)，證明的結(jié)果是得到一個(gè)解釋結(jié)構(gòu)。例如、設(shè)要學(xué)習(xí)的目標(biāo)概念是“一個(gè)物體(Obj1)可以安全地放置在另一個(gè)物體(Obj2)上”，即 Safe-To-Stack(Obj1,Obj2)第六節(jié) 解釋學(xué)習(xí)第六節(jié) 解釋學(xué)習(xí)訓(xùn)練實(shí)例為描述物體訓(xùn)練實(shí)例為描述物體Obj1Obj1與與Obj2Obj2的事實(shí)的事實(shí)：On(Obj1,Obj2)Isa(Obj1,book-AI)Isa(Obj2,table-book)Volume(Obj1,1)Density(Obj1,0.1)第六節(jié) 解釋學(xué)習(xí) 領(lǐng)域知識(shí)是把一個(gè)物體放置在另一個(gè)物體上面的安

23、全領(lǐng)域知識(shí)是把一個(gè)物體放置在另一個(gè)物體上面的安全性準(zhǔn)則：性準(zhǔn)則：Fragile(y)Safe-To-Stack(x,y)Lighter(x,y)Safe-To-Stack(x,y)Volume(p,v)Density(p,d)*(v,d,w)Weight(p,w)Isa(p,table-book)Weight(p,15)Weight(p1,w1)Weight(p2,w2)smaller(w1,w2)Lighter(p1,p2)第六節(jié) 解釋學(xué)習(xí)證明過(guò)程：證明過(guò)程：Safe-To-Stack(Obj1,Obj2)Lighter(Obj1,Obj2)Weight(Obj1,0.1)Weight(Ob

24、j2,15)Smaller(0.1,15)Isa(Obj2,table-book)Volume(Obj1,1)Density(Obj1,0.1)*(1,0.1,0.1)第六節(jié) 解釋學(xué)習(xí)2 2、獲取一般性知識(shí)、獲取一般性知識(shí)、獲取一般性知識(shí)、獲取一般性知識(shí) 任務(wù)：任務(wù)：任務(wù)：任務(wù)：對(duì)解釋結(jié)構(gòu)進(jìn)行一般化處理，從而得到關(guān)于目標(biāo)概念的一般性知識(shí)。處理的方法處理的方法處理的方法處理的方法：通常是把常量代換為變量，并把某些不重要的信息去掉，只保留對(duì)以后求解問(wèn)題所必須的關(guān)鍵信息。對(duì)上面的解釋結(jié)構(gòu)進(jìn)行一般化處理可以得到一般的解釋結(jié)構(gòu)。第六節(jié) 解釋學(xué)習(xí)Safe-To-Stack(O1,O2)Lighter(O1

25、,O2)Weight(O1,w1)Weight(O2,15)Smaller(w1,15)Isa(O2,table-book)Volume(O1,v1)Density(O1,d1)*(v1,d1,w1)第六節(jié) 解釋學(xué)習(xí)得到的一般知識(shí)：Volume(O1,v1)Density(O1,d1)*(v1,d1,w1)Isa(O2,table-book)Smaller(w1,15)Safe-To-Stack(O1,O2)第六節(jié) 解釋學(xué)習(xí)三、領(lǐng)域知識(shí)的完善性三、領(lǐng)域知識(shí)的完善性三、領(lǐng)域知識(shí)的完善性三、領(lǐng)域知識(shí)的完善性 由于領(lǐng)域知識(shí)可能不完善，因此會(huì)出現(xiàn)兩種極端情況：1、構(gòu)造不出解釋 2、構(gòu)造出多種解釋 解決

26、的根本方法：解決的根本方法：解決的根本方法：解決的根本方法：提供完善的領(lǐng)域知識(shí)。同時(shí)具有測(cè)試和修正不完善知識(shí)的能力。第七節(jié) 概念學(xué)習(xí)和一般到特殊序一、簡(jiǎn)介一、簡(jiǎn)介一、簡(jiǎn)介一、簡(jiǎn)介 問(wèn)題：?jiǎn)栴}：?jiǎn)栴}：?jiǎn)栴}：給定一樣例集合以及每個(gè)樣例是否屬于某一概念的標(biāo)注，怎樣自動(dòng)推斷出該概念的一般定義。該問(wèn)題被稱為概念學(xué)習(xí)，或稱為從樣例中逼近布爾函數(shù)。有怎樣的函數(shù)形式？輸入xi輸出yi=f(xi)概念學(xué)習(xí)：概念學(xué)習(xí)：概念學(xué)習(xí)：概念學(xué)習(xí)：概念學(xué)習(xí)是指從有關(guān)某個(gè)布爾函數(shù)的輸入輸出訓(xùn)練樣例中推斷出該布爾函數(shù)。第七節(jié) 概念學(xué)習(xí)和一般到特殊序例子、例子、例子、例子、ExampleSkyAirTempHumidityWin

27、dWaterForestEnjoySport1234sunnysunnyRainysunnyWarmWarmColdWarmNormalHighHighHighStrongStrongStrongStrongWarmWarmWarmCoolSameSameSameChangeYesYesNoYes目標(biāo)概念目標(biāo)概念EnjoySport的正例和反例的正例和反例 學(xué)習(xí)的任務(wù)：學(xué)習(xí)的任務(wù)：學(xué)習(xí)的任務(wù)：學(xué)習(xí)的任務(wù)：基于某天的各屬性，以預(yù)測(cè)出該天EnjoySport的值。第七節(jié) 概念學(xué)習(xí)和一般到特殊序 設(shè)，實(shí)例各屬性的約束關(guān)系是合取關(guān)系，因此，希望歸納出形如 Sky=?Wind=?EnjoySport=Y

28、es的知識(shí)。如何歸納？如何歸納？如何歸納？如何歸納？屬性空間的描述(假設(shè)空間 H,用向量形式描述)一些約定的符號(hào)：由“?”表示本屬性可取任意值；由“”表示本屬性不接受任何值；由“c”表示待學(xué)習(xí)的目標(biāo)概念。第七節(jié) 概念學(xué)習(xí)和一般到特殊序 如果某些示例x滿足假設(shè)h的所有約束，那么h將x分為類為正例(h(x)=1)，或反例(h(x)=0)。因此，假設(shè)可為下面形式的表達(dá)式 最一般的假設(shè)是G=，將所有的示例分類為正例。最特殊的假設(shè)是S=，將所有的示例分類為反例。因此，歸納的任務(wù)轉(zhuǎn)換為對(duì)假設(shè)空間的搜索問(wèn)題，即，因此，歸納的任務(wù)轉(zhuǎn)換為對(duì)假設(shè)空間的搜索問(wèn)題，即，因此，歸納的任務(wù)轉(zhuǎn)換為對(duì)假設(shè)空間的搜索問(wèn)題，即，

29、因此，歸納的任務(wù)轉(zhuǎn)換為對(duì)假設(shè)空間的搜索問(wèn)題，即，搜索能正確分類示例的一個(gè)假設(shè)或假設(shè)的集合搜索能正確分類示例的一個(gè)假設(shè)或假設(shè)的集合搜索能正確分類示例的一個(gè)假設(shè)或假設(shè)的集合搜索能正確分類示例的一個(gè)假設(shè)或假設(shè)的集合。第七節(jié) 概念學(xué)習(xí)和一般到特殊序q歸納學(xué)習(xí)的假設(shè)條件歸納學(xué)習(xí)的假設(shè)條件歸納學(xué)習(xí)的假設(shè)條件歸納學(xué)習(xí)的假設(shè)條件 任一假設(shè)如果能夠在足夠大的訓(xùn)練樣例集合中很好地逼近目標(biāo)函數(shù)，那么，它也能在未見(jiàn)的實(shí)例中很好地逼近目標(biāo)函數(shù)。第七節(jié) 概念學(xué)習(xí)和一般到特殊序二、作為搜索的概念學(xué)習(xí)二、作為搜索的概念學(xué)習(xí)二、作為搜索的概念學(xué)習(xí)二、作為搜索的概念學(xué)習(xí) 概念學(xué)習(xí)可以看成是一個(gè)搜索過(guò)程，范圍是假設(shè)的表示所隱含定義

30、的整個(gè)空間。搜索的目標(biāo)是尋找能很好地?cái)M合訓(xùn)練樣例的假設(shè)。1 1、假設(shè)的一般到特殊序、假設(shè)的一般到特殊序、假設(shè)的一般到特殊序、假設(shè)的一般到特殊序 例子，兩個(gè)假設(shè) h1=h2=h2比h1的約束要少，因此，任何被h1劃分為正例的樣例，也將被h2劃分為正例。即h2比h1更一般。第七節(jié) 概念學(xué)習(xí)和一般到特殊序 定義：設(shè)hj和hk是兩個(gè)布爾函數(shù)，如果 (xX)hk(x)=1)(hj(x)=1)則稱hj比hk更一般(記為 hjghk)。這種序稱為偏序。第七節(jié) 概念學(xué)習(xí)和一般到特殊序2 2、Find-S:Find-S:搜索極大特殊假設(shè)搜索極大特殊假設(shè)搜索極大特殊假設(shè)搜索極大特殊假設(shè) 使用偏序關(guān)系搜索與訓(xùn)練樣例

31、相一致的假設(shè)的一種方法是從假設(shè)空間H中最特殊的假設(shè)開(kāi)始，然后在該假設(shè)覆蓋正例失敗時(shí)將其一般化。Find-SFind-S算法算法算法算法(1)將h初始化為H中最特殊的假設(shè)(2)對(duì)每個(gè)正例x 對(duì)h的每個(gè)屬性約束ai 如果x滿足ai，那么不做任何事 否則,將h中ai替換為x滿足的另一個(gè)更一般約束(3)輸出假設(shè)h第七節(jié) 概念學(xué)習(xí)和一般到特殊序例，用Find-S，學(xué)習(xí)EnjoySport。設(shè)(最特殊的假設(shè))，h=由示例1(正例)，修改h為：h=由示例2(正例)，修改h為：h=示例3(反例)，不修改h由示例4(正例)，修改h為：h=最后的輸出是：第七節(jié) 概念學(xué)習(xí)和一般到特殊序三、變型空間和侯選消除算法三、

32、變型空間和侯選消除算法三、變型空間和侯選消除算法三、變型空間和侯選消除算法 在Find-S算法中，找到的只是H中能夠滿足訓(xùn)練樣例集合的多個(gè)假設(shè)中的一個(gè)。而在侯選消除算法中，輸出的是與訓(xùn)練樣例一致的所有假設(shè)的集合。定義：一個(gè)假設(shè)h與訓(xùn)練樣例集合D一致,當(dāng)且僅當(dāng)對(duì)D中的每一個(gè)樣例都有h(x)=c(x)。Consistent(h,D)=(D)h(x)=c(x)即，當(dāng)一個(gè)假設(shè)能正確分類一組樣例時(shí)，稱為這個(gè)假設(shè)與這些樣例是一致的。第七節(jié) 概念學(xué)習(xí)和一般到特殊序 侯選消除算法能夠表示與訓(xùn)練樣例一致的所有假設(shè)。在假設(shè)空間中的這一子集稱為關(guān)于假設(shè)空間H和訓(xùn)練樣例D的變型空間。定義：關(guān)于假設(shè)空間H和訓(xùn)練樣例D的

33、變型空間，標(biāo)記為VSH,D，是H中與訓(xùn)練樣例D一致的所有假設(shè)構(gòu)成的子集。VSH,D=hH|Consistent(h,D)第七節(jié) 概念學(xué)習(xí)和一般到特殊序1 1、列表后消除算法、列表后消除算法、列表后消除算法、列表后消除算法 表示變型空間的一種直觀方法是列出其所有的成員，通過(guò)檢測(cè)所有成員就可得到H和D的變型空間。列表后消除算法列表后消除算法列表后消除算法列表后消除算法(1)VersionSpace 包含H中所有假設(shè)的列表(2)對(duì)每個(gè)訓(xùn)練樣例 從變型空間中移去所有h(x)c(x)的假設(shè)(3)輸出VersionSpace中的假設(shè)列表 原則上，只要假設(shè)空間是有限的，都可以使用該算法。原則上，只要假設(shè)空間

34、是有限的，都可以使用該算法。原則上，只要假設(shè)空間是有限的，都可以使用該算法。原則上，只要假設(shè)空間是有限的，都可以使用該算法。第七節(jié) 概念學(xué)習(xí)和一般到特殊序2 2、侯選消除算法、侯選消除算法、侯選消除算法、侯選消除算法變型空間的偏序表示：變型空間的偏序表示：變型空間的偏序表示：變型空間的偏序表示：只要能給出假設(shè)空間的極大一般成員G和極大特殊成員S，就可列出變型空間中的所有成員，其方法是使用偏序結(jié)構(gòu)來(lái)生成S和G集合之間的所有假設(shè)。第七節(jié) 概念學(xué)習(xí)和一般到特殊序侯選消除算法侯選消除算法侯選消除算法侯選消除算法 基本思想：基本思想：基本思想：基本思想：首先將G邊界集合初始化為H中的最一般假設(shè)：G0=，

35、將S邊界集合初始化為H中的最特殊假設(shè)：S0=；對(duì)每個(gè)訓(xùn)練樣例進(jìn)行處理時(shí)，S和G邊界被分別泛化和特殊化，從變型空間中逐步消除與樣例不一致的假設(shè)。在所有的樣例被處理完后，得到的變型空間就包含了所有與樣例一致的假設(shè)。第七節(jié) 概念學(xué)習(xí)和一般到特殊序侯選消除算法：侯選消除算法：侯選消除算法：侯選消除算法：將G集合初始化為H中極大一般假設(shè)將S集合初始化為H中極大特殊假設(shè)對(duì)每個(gè)訓(xùn)練樣例d,進(jìn)行下列操作：如果d是一個(gè)正例 從G中移去所有與d不一致的假設(shè) 對(duì)S中每個(gè)與d不一致的假設(shè)s 從S中移去s 把s的所有極小泛化式h加入到S中，其中h滿足 h與d一致，而且G的某個(gè)成員比h更一般 從S中移去這樣的假設(shè)：它比S

36、中另一假設(shè)更一般第七節(jié) 概念學(xué)習(xí)和一般到特殊序 如果d是一個(gè)反例 從S中移去所有與d不一致的假設(shè) 對(duì)G中每個(gè)與d不一致的假設(shè)g 從G中移去g 把g的所有極小特殊化式h加入到G中,其中h滿足 h與d一致，而且S的某個(gè)成員比h更特殊 從G中移去這樣的假設(shè)：它比G中另一假設(shè)更特殊第七節(jié) 概念學(xué)習(xí)和一般到特殊序例、學(xué)習(xí)“EnjoySport”S0:S1:S2:訓(xùn)練樣例：1.,EnjoySport=Yes2.,EnjoySport=YesG0,G1,G2:第七節(jié) 概念學(xué)習(xí)和一般到特殊序S2,S3G2:,G3:訓(xùn)練樣例：3.,EnjoySport=No 反例使G的邊界特殊化。在示例3中，由6個(gè)屬性可以使G

37、2特殊化，在此只有3個(gè)，因?yàn)槠渌?個(gè)不滿足示例1和示例2。第七節(jié) 概念學(xué)習(xí)和一般到特殊序S3S4,G3:,G4:訓(xùn)練樣例：4.,EnjoySport=Yes第七節(jié) 概念學(xué)習(xí)和一般到特殊序最終的變型空間最終的變型空間最終的變型空間最終的變型空間S4,G4:,第七節(jié) 概念學(xué)習(xí)和一般到特殊序關(guān)于變型空間和侯選消除算法的說(shuō)明：關(guān)于變型空間和侯選消除算法的說(shuō)明：關(guān)于變型空間和侯選消除算法的說(shuō)明：關(guān)于變型空間和侯選消除算法的說(shuō)明：(1)由侯選消除算法得到變型空間能夠收斂到目標(biāo)概念的假設(shè)條件是在訓(xùn)練樣例中沒(méi)有錯(cuò)誤；H中確實(shí)包含描述目標(biāo)概念的正確假設(shè)。(2)侯選消除算法提取的是合取關(guān)系，如果是析取關(guān)系，則前面

38、的假設(shè)空間無(wú)法包含，因此，必須擴(kuò)大假設(shè)空間，使每個(gè)可能的假設(shè)都包含在內(nèi)。(3)為了使侯選消除算法可以處理更大的假設(shè)空間，應(yīng)使用歸納偏置。歸納偏置就是在歸納時(shí)預(yù)先進(jìn)行的某種假設(shè)。例如，侯選消除的歸納偏置是“目標(biāo)概念包含在給定的H種”。第八節(jié) 決策樹(shù)學(xué)習(xí) 決策樹(shù)是一種逼近離散值函數(shù)的方法，對(duì)噪聲數(shù)據(jù)有很好的健壯性且能夠?qū)W習(xí)析取表達(dá)式。決策樹(shù)的歸納偏置是優(yōu)先選擇較小的樹(shù)。第八節(jié) 決策樹(shù)學(xué)習(xí)一、決策樹(shù)表示法一、決策樹(shù)表示法一、決策樹(shù)表示法一、決策樹(shù)表示法OutlookSunnyOvercastRainHumidityHighNormalNoYesYesWindStrongWeakNoYes概念 Pla

39、y Tennis 的決策樹(shù)第八節(jié) 決策樹(shù)學(xué)習(xí) 通常決策樹(shù)代表實(shí)例屬性值約束的合取。從樹(shù)根到葉節(jié)點(diǎn)的每一條路徑對(duì)應(yīng)一組屬性測(cè)試的合取，樹(shù)本身代表這些合取的析取。例如，前面的決策樹(shù)代表 (Outlook=Sunny Humidity=Normal)(Outlook=overcast)(Outlook=RainWind=Weak)第八節(jié) 決策樹(shù)學(xué)習(xí)q決策樹(shù)學(xué)習(xí)的使用范圍決策樹(shù)學(xué)習(xí)的使用范圍決策樹(shù)學(xué)習(xí)的使用范圍決策樹(shù)學(xué)習(xí)的使用范圍(1)實(shí)例是由“屬性-值”對(duì)表示的(2)目標(biāo)函數(shù)具有離散的輸出值(3)可能需要析取的描述(4)訓(xùn)練數(shù)據(jù)中可能包含錯(cuò)誤(5)訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例第八節(jié) 決策樹(shù)學(xué)習(xí)二

40、、基本的決策樹(shù)學(xué)習(xí)算法二、基本的決策樹(shù)學(xué)習(xí)算法二、基本的決策樹(shù)學(xué)習(xí)算法二、基本的決策樹(shù)學(xué)習(xí)算法 大多數(shù)決策樹(shù)學(xué)習(xí)算法是一種核心算法(ID3)的變形，該算法采用自頂向下的貪婪搜索遍歷可能的決策樹(shù)空間。1、節(jié)點(diǎn)的選擇依據(jù) ID3算法的核心問(wèn)題是選取在樹(shù)的每個(gè)節(jié)點(diǎn)要測(cè)試的屬性。ID3是選擇最有助于分類實(shí)例的屬性。定義定義定義定義(熵熵熵熵)：設(shè)S是包含某個(gè)目標(biāo)概念的樣例集合，如果目標(biāo)概念具有c個(gè)不同的屬性，那么S相對(duì)于c個(gè)狀態(tài)的分類的熵定義為：Entropy(S)=-pilog2pii=1c第八節(jié) 決策樹(shù)學(xué)習(xí) 定義定義定義定義(信息增益信息增益信息增益信息增益)：一個(gè)屬性A相對(duì)樣例集合S的信息增益定

41、義為：Gain(S,A)=Entropy(S)-Entropy(Sv)|Sv|S|vValue(A)其中，Value(A)是屬性A所有可能值的集合，Sv是S種屬性A為v的子集。第八節(jié) 決策樹(shù)學(xué)習(xí)例如、設(shè)S是一組有關(guān)天氣的訓(xùn)練樣例，它的Wind屬性具有Weak和Strong兩個(gè)值。S包含14個(gè)樣例9+,5-。在正例中的6個(gè)和反例中的2個(gè)有 Wind=Weak，其他的是Wind=Stron。則 Values(Wind)=Weak,Strong S=9+,5-Sweak6+,2-Sstrong 3+,3-Gain(S,Wind)=E(S)-(8/14)E(Sweak)-(6/14)E(Sstrong

42、)=0.94 (8/14)0.811-(6/14)1.0 =0.048第八節(jié) 決策樹(shù)學(xué)習(xí)2、ID3算法 設(shè)，T_Attrs是該樹(shù)要測(cè)試的目標(biāo)屬性，Attrs是除目標(biāo)屬性外供學(xué)習(xí)到的決策樹(shù)測(cè)試的屬性列表。創(chuàng)建樹(shù)的Root節(jié)點(diǎn) 如果樣例都為正，則返回label=+的單節(jié)點(diǎn)樹(shù)Root 如果樣例都為反，則返回label=-的單節(jié)點(diǎn)樹(shù)Root 如果Attrs為空，則返回單節(jié)點(diǎn)樹(shù)，label=樣例中最普通的T_Attrs值 否則開(kāi)始 AAttrs中分類樣例能力最好的屬性 Root的決策屬性A第八節(jié) 決策樹(shù)學(xué)習(xí) 對(duì)A的每個(gè)可能值vi 在Root下加一個(gè)新的分支對(duì)應(yīng)測(cè)試A=vi 令Examsvi為樣例中滿足屬

43、性A的值為vi的子集 如果為Examsvi空 在這個(gè)新分支下加一個(gè)葉節(jié)點(diǎn),節(jié)點(diǎn)label=樣例 中最普遍的T_Attrs值 否則在這個(gè)新分支下加一個(gè)子樹(shù)ID3 (Examsvi，T_Attrs，Attrs A)結(jié)束 返回Root第八節(jié) 決策樹(shù)學(xué)習(xí)例子、PlayTennis訓(xùn)練數(shù)據(jù)的ID3算法Day Outlook Temperature Humidity Wind PlayTennisD1D2D3D4D5D6D7D8D9D10D11D12D13D14SunnySunnyOvercastRainRainRainOvercastSunnySunnyRainSunnyOvercastOvercast

44、RainHotHotHotMildCoolCoolCoolMildCoolMildMildMildHotMildWeakStrongWeakWeakWeakStrongStrongWeakWeakWeakStrongStrongWeakStrongHighHighHighHighNormalNormalNormalHighNormalNormalNormalHighNormalHighNoNoYesYesYesNoYesNoYesYesYesYesYesNo第八節(jié) 決策樹(shù)學(xué)習(xí)確定根節(jié)點(diǎn)：確定根節(jié)點(diǎn)：確定根節(jié)點(diǎn)：確定根節(jié)點(diǎn)：有四個(gè)侯選屬性(Outlook,Temperature,Humidity

45、,Wind),計(jì)算每個(gè)侯選屬性信息增益：Gain(S,Outlook)=0.246 Gain(S,Terminature)=0.029 Gain(S,Humidity)=0.151 Gain(S,Wind)=0.048因此，選擇OutLook為根節(jié)點(diǎn)。第八節(jié) 決策樹(shù)學(xué)習(xí)OutlookD1,D2,D149+,5-?SunnyD1,D2,D8,D9,D112+,3-OvercastD3,D7,D12,D134+,0-YesRainD4,D5,D6,D10,D143+,2-第八節(jié) 決策樹(shù)學(xué)習(xí)對(duì)“Sunny”分支：Ssunny=D1,D2,D8,D9,D11 Gain(Ssunny,Humidity)=0.97 Gain(Ssunny,Temperature)=0.57 Gain(Ssunny,Wind)=0.19所以，節(jié)點(diǎn)測(cè)試屬性為“Humidity”第八節(jié) 決策樹(shù)學(xué)習(xí)SunnyHumidityD1,D2,D8,D9,D11HighWeakStrongD1,D20+,2-NoD8,D91+,1-?D111+,0-Yes第八節(jié) 決策樹(shù)學(xué)習(xí)對(duì)“Weak”分支繼續(xù)D8,D91+,1-TemperatureMildCoolD80+,1-NoD91+,0-Yes