人工智能與專家系統(tǒng)第七章

第七章機(jī)器學(xué)習(xí)7.1概述7.2歸納學(xué)習(xí)7.3決策樹(shù)學(xué)習(xí)7.4基于實(shí)例的學(xué)習(xí)本章小結(jié)課后練習(xí)題普通高等院?！笆濞曇?guī)劃教材第七章機(jī)器學(xué)習(xí)機(jī)器能否像人類一樣具有學(xué)習(xí)才干呢？1959年美國(guó)的塞繆爾設(shè)計(jì)了一個(gè)下棋程序，這個(gè)程序具有學(xué)習(xí)才干，它可以在不斷的對(duì)弈中改善本人的棋藝。4年后，這個(gè)程序戰(zhàn)勝了設(shè)計(jì)者本人。又過(guò)了3年，這個(gè)程序戰(zhàn)勝了美國(guó)一個(gè)堅(jiān)持8年之久的常勝不敗的冠軍。它向人們展現(xiàn)了機(jī)器學(xué)習(xí)的才干。本章主要引見(jiàn)機(jī)器學(xué)習(xí)的根本概念和歸納學(xué)習(xí)、決策樹(shù)學(xué)習(xí)、基于實(shí)例的學(xué)習(xí)等詳細(xì)的機(jī)器學(xué)習(xí)方法，希望讀者能對(duì)這一領(lǐng)域有一個(gè)初步的了解和認(rèn)識(shí)。普通高等院?！笆濞曇?guī)劃教材7.1概述機(jī)器學(xué)習(xí)的研討是根據(jù)生理學(xué)、認(rèn)知科學(xué)等對(duì)人類學(xué)習(xí)機(jī)理的了解，建立人類學(xué)習(xí)過(guò)程的計(jì)算模型或認(rèn)識(shí)模型，開(kāi)展各種學(xué)習(xí)實(shí)際和學(xué)習(xí)方法，研討通用的學(xué)習(xí)算法并進(jìn)展實(shí)際上的分析，建立面向義務(wù)的具有特定運(yùn)用的學(xué)習(xí)系統(tǒng)。這些研討目的相互影響相互促進(jìn)。自從1980年在卡內(nèi)基-梅隆大學(xué)召開(kāi)第一屆機(jī)器學(xué)術(shù)研討會(huì)以來(lái)，機(jī)器學(xué)習(xí)的研討任務(wù)開(kāi)展很快，已成為中心課題之一。普通高等院校“十二五〞規(guī)劃教材7.1.1什么是機(jī)器學(xué)習(xí)1．關(guān)于機(jī)器學(xué)習(xí)的定義Langley(1996)定義的“機(jī)器學(xué)習(xí)是一門(mén)人工智能的科學(xué)，該領(lǐng)域的主要研討對(duì)象是人工智能，特別是如何在閱歷學(xué)習(xí)中改善詳細(xì)算法的性能。〞TomMitchell的機(jī)器學(xué)習(xí)(1997)對(duì)信息論中的一些概念有詳細(xì)的解釋,其中定義機(jī)器學(xué)習(xí)時(shí)提到，“機(jī)器學(xué)習(xí)是對(duì)能經(jīng)過(guò)閱歷自動(dòng)改良的計(jì)算機(jī)算法的研討〞Alpaydin(2004)也提出本人對(duì)機(jī)器學(xué)習(xí)的定義，“機(jī)器學(xué)習(xí)是用數(shù)據(jù)或以往的閱歷，以此優(yōu)化計(jì)算機(jī)程序的性能規(guī)范。〞顧名思義，機(jī)器學(xué)習(xí)是研討如何運(yùn)用機(jī)器來(lái)模擬人類學(xué)習(xí)活動(dòng)的一門(mén)學(xué)科。普通高等院校“十二五〞規(guī)劃教材7.1.1什么是機(jī)器學(xué)習(xí)稍為嚴(yán)厲的提法是：機(jī)器學(xué)習(xí)是一門(mén)研討機(jī)器獲取新知識(shí)和新技藝，并識(shí)別現(xiàn)有知識(shí)的學(xué)問(wèn)。這里所說(shuō)的“機(jī)器〞，指的就是計(jì)算機(jī)，如今是電子計(jì)算機(jī)，以后還能夠是中子計(jì)算機(jī)、光子計(jì)算機(jī)或神經(jīng)計(jì)算機(jī)等等。普通高等院校“十二五〞規(guī)劃教材7.1.1什么是機(jī)器學(xué)習(xí)2．機(jī)器學(xué)習(xí)的開(kāi)展簡(jiǎn)史最早的具有學(xué)習(xí)才干的程序是年美國(guó)的設(shè)計(jì)的跳棋程序。第一階段是20世紀(jì)50到60年代的探求階段。主要成果有：感知機(jī)(Perceptron)；Friedberg等模擬隨機(jī)突變和自然選擇過(guò)程的程序；Hunt等的決策樹(shù)歸納程序CLS。第二階段是20世紀(jì)70年代的開(kāi)展階段。主要系統(tǒng)和算法包括：Winston的積木世界學(xué)習(xí)系統(tǒng)；Michalski基于邏輯的歸納學(xué)習(xí)系統(tǒng)AQVAL；Michalski和Chilausky的AQII；Quinlan的ID3程序；Mitchell的版本空間方法。普通高等院校“十二五〞規(guī)劃教材7.1.1什么是機(jī)器學(xué)習(xí)第三階段是20世紀(jì)80年代至今的鼎盛階段。主要成果有：一方面?zhèn)鹘y(tǒng)的符號(hào)學(xué)習(xí)的各種方法已日臻完善。另一方面，機(jī)器學(xué)習(xí)的根底實(shí)際的研討越來(lái)越引起人們的注重。3．機(jī)器學(xué)習(xí)的普通步驟圖7.1.1機(jī)器學(xué)習(xí)的根本系統(tǒng)構(gòu)造模型普通高等院?！笆濞曇?guī)劃教材7.1.1什么是機(jī)器學(xué)習(xí)“環(huán)境〞是指外部信息的來(lái)源，它為系統(tǒng)的學(xué)習(xí)提供有關(guān)信息；“學(xué)習(xí)〞是系統(tǒng)的學(xué)習(xí)構(gòu)造，從環(huán)境中獲得外部信息，然后經(jīng)分析、綜合、類比和歸納等思想過(guò)程獲得知識(shí)，并存入知識(shí)庫(kù)中更新知識(shí)庫(kù)；“知識(shí)庫(kù)〞用于存放由學(xué)習(xí)得到的知識(shí)，在存儲(chǔ)時(shí)要適當(dāng)?shù)慕M織，便于運(yùn)用和維護(hù)；“執(zhí)行〞環(huán)節(jié)是基于學(xué)習(xí)得到的新的知識(shí)庫(kù)，它執(zhí)行一系列的義務(wù)。此外還需將執(zhí)行結(jié)果信息反響給學(xué)習(xí)環(huán)節(jié)，以完成對(duì)新“知識(shí)庫(kù)〞的評(píng)價(jià)，指點(diǎn)進(jìn)一步的學(xué)習(xí)任務(wù)。普通高等院校“十二五〞規(guī)劃教材7.1.1什么是機(jī)器學(xué)習(xí)圖7.1.2機(jī)器系統(tǒng)學(xué)習(xí)環(huán)節(jié)的普經(jīng)過(guò)程普通高等院?！笆濞曇?guī)劃教材7.1.2機(jī)器學(xué)習(xí)方法的分類1．按學(xué)習(xí)時(shí)所用的分類方法進(jìn)展分類：〔1〕機(jī)械式學(xué)習(xí)〔2〕示教學(xué)習(xí)〔3〕類比學(xué)習(xí)〔4〕解釋學(xué)習(xí)2．按推理的戰(zhàn)略分類〔1〕演繹學(xué)習(xí)〔2〕歸納學(xué)習(xí)3．按綜合要素分類〔1〕銜接學(xué)習(xí)〔2〕分析學(xué)習(xí)〔3〕分類器系統(tǒng)普通高等院?！笆濞曇?guī)劃教材7.1.3機(jī)器學(xué)習(xí)中的推理方法〔1〕演繹推理演繹推理是結(jié)論可從叫做前提的知現(xiàn)實(shí)必然的得出的推理。假設(shè)前提為真，那么結(jié)論必然為真?！?〕歸納推理所謂歸納推理，就是從個(gè)別性知識(shí)推出普通性結(jié)論的推理。歸納推理的前提是其結(jié)論的必要條件?！?〕類比推理類比推理是根據(jù)兩個(gè)或兩類對(duì)象有部分屬性一樣，從而推出它們的其他屬性也一樣的推理。簡(jiǎn)稱類推、類比。它是以關(guān)于兩個(gè)事物某些屬性一樣的判別為前提，推出兩個(gè)事物的其他屬性一樣的結(jié)論的推理。普通高等院?！笆濞曇?guī)劃教材7.2歸納學(xué)習(xí)歸納學(xué)習(xí)是人工智能中開(kāi)展較為成熟，并得到廣泛的研討和運(yùn)用的學(xué)習(xí)方法。它是是由一些實(shí)例或反例，經(jīng)過(guò)歸納推理得出該概念的普通描畫(huà)。實(shí)現(xiàn)實(shí)例到規(guī)那么的歸納推理過(guò)程就是歸納學(xué)習(xí)過(guò)程。它的普通操作是泛化和特化，泛化用來(lái)擴(kuò)展假設(shè)的語(yǔ)義信息，以使其可以包含更多的正例，運(yùn)用于更多的情況。特化是泛化的相反的操作，用于限制概念描畫(huà)的運(yùn)用范圍。普通高等院?！笆濞曇?guī)劃教材7.2.1歸納學(xué)習(xí)的根本概念歸納是指從個(gè)別到普通，從部分到整體的推論行為。歸納推理是運(yùn)用歸納方法所進(jìn)展的推理，即從足夠多的實(shí)例中歸納出普通性的知識(shí)，它是一種從個(gè)別到普通的推理。歸納學(xué)習(xí)是運(yùn)用歸納推理進(jìn)展學(xué)習(xí)的一種學(xué)習(xí)方法。歸納學(xué)習(xí)旨在從大量的閱歷數(shù)據(jù)中歸納抽取出普通的斷定規(guī)那么和方式，是從特殊情況推導(dǎo)出普通規(guī)那么的學(xué)習(xí)方法。它的目的是構(gòu)成合理的能解釋知現(xiàn)實(shí)和預(yù)見(jiàn)新現(xiàn)實(shí)的普通性結(jié)論。歸納學(xué)習(xí)由于依賴于閱歷數(shù)據(jù)，因此又被稱為閱歷學(xué)習(xí)；由于依賴于數(shù)據(jù)間的類似性，因此也被稱為基于類似性的學(xué)習(xí)。普通高等院校“十二五〞規(guī)劃教材7.2.1歸納學(xué)習(xí)的根本概念1．歸納學(xué)習(xí)的雙空間模型圖7.2.1雙空間模型普通高等院?！笆濞曇?guī)劃教材7.2.1歸納學(xué)習(xí)的根本概念2．歸納學(xué)習(xí)的分類歸納學(xué)習(xí)按其有無(wú)教師指點(diǎn)可分為例如學(xué)習(xí)和察看與發(fā)現(xiàn)學(xué)習(xí)。例如學(xué)習(xí)，又叫做概念獲取——它的義務(wù)是確定概念的普通描畫(huà)，這個(gè)描畫(huà)應(yīng)能解釋一切給定的正例，并排除一切給定的反例，由于學(xué)習(xí)是根據(jù)教師分好類的正反例進(jìn)展學(xué)習(xí)，因此是有教師學(xué)習(xí)。察看與發(fā)現(xiàn)學(xué)習(xí)又稱為描畫(huà)的泛化——這類學(xué)習(xí)沒(méi)有教師的協(xié)助，它要產(chǎn)生解釋一切或大多數(shù)察看的規(guī)律和規(guī)那么，這些都是未經(jīng)分類的察看學(xué)習(xí)或是由系統(tǒng)本身的功能去發(fā)現(xiàn)。普通高等院?！笆濞曇?guī)劃教材7.2.1歸納學(xué)習(xí)的根本概念歸納學(xué)習(xí)還可以劃分為單概念學(xué)習(xí)和多概念學(xué)習(xí)兩類。典型的單概念學(xué)習(xí)系統(tǒng)包括米切爾的基于數(shù)據(jù)驅(qū)動(dòng)的變型空間法，昆蘭的ID3方法，狄特利希和米哈爾斯基提出的基于模型驅(qū)動(dòng)的Induce算法。典型的多概念學(xué)習(xí)方法和系統(tǒng)有米哈爾斯基的、元和程序等。多概念學(xué)習(xí)義務(wù)可以劃分成多個(gè)單概念學(xué)習(xí)的義務(wù)來(lái)完成。多概念學(xué)習(xí)與單概念學(xué)習(xí)的差別在于多概念學(xué)習(xí)必需處置概念之間的沖突問(wèn)題。普通高等院?！笆濞曇?guī)劃教材7.2.2變型空間學(xué)習(xí)1．變型空間的構(gòu)造7.2.2變型空間排序的關(guān)系普通高等院?！笆濞曇?guī)劃教材7.2.2變型空間學(xué)習(xí)2.候選項(xiàng)刪除算法算法過(guò)程：〔1〕初始化H為整個(gè)概念空間〔規(guī)那么空間〕。〔2〕接受一個(gè)新的示教例子?！?〕反復(fù)步驟〔2〕，直到G=S，且使這兩個(gè)集合都只含有一個(gè)元素為止?！?〕輸出H中的概念，即輸出G或S。普通高等院?！笆濞曇?guī)劃教材7.3決策樹(shù)學(xué)習(xí)決策樹(shù)學(xué)習(xí)是運(yùn)用最廣泛的歸納學(xué)習(xí)，特別是在專家系統(tǒng)、工業(yè)控制過(guò)程、金融保險(xiǎn)預(yù)測(cè)以及醫(yī)療診斷等領(lǐng)域。假設(shè)學(xué)習(xí)的義務(wù)是對(duì)一個(gè)大的實(shí)例集合做概念分類的歸納定義，而這些例子都是用一些無(wú)構(gòu)造的屬性值對(duì)來(lái)表示，那么可以采用決策樹(shù)學(xué)習(xí)算法。亨特(Hunt)的概念學(xué)習(xí)系統(tǒng)CLS是一種早期的基于決策樹(shù)的歸納學(xué)習(xí)系統(tǒng)。1979年，昆蘭對(duì)此進(jìn)展了開(kāi)展，提出了ID3算法，該算法不僅能方便地表示概念屬性值信息的構(gòu)造，而且能從大量實(shí)例數(shù)據(jù)中有效地生成相應(yīng)的決策樹(shù)模型。普通高等院?！笆濞曇?guī)劃教材7.3.1決策樹(shù)及構(gòu)造算法所謂決策樹(shù)是一個(gè)類似流程圖的樹(shù)構(gòu)造，其中樹(shù)的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)特征〔屬性〕變量值的檢驗(yàn)，每個(gè)分枝表示檢驗(yàn)結(jié)果，樹(shù)枝上的葉結(jié)點(diǎn)代表所關(guān)懷的因變量的取值，最頂端的結(jié)點(diǎn)稱為根結(jié)點(diǎn)，內(nèi)結(jié)點(diǎn)用矩形框表示，葉結(jié)點(diǎn)用橢圓框表示。從根結(jié)點(diǎn)到每個(gè)葉結(jié)點(diǎn)都有獨(dú)一的一條途徑，這條途徑就是一條決策“規(guī)那么〞。假設(shè)每個(gè)內(nèi)結(jié)點(diǎn)都恰好有兩個(gè)分枝，那么稱為二叉樹(shù)，類似可定義多叉樹(shù)，在一切的決策樹(shù)中，二叉樹(shù)最為常用。普通高等院?！笆濞曇?guī)劃教材7.3.1決策樹(shù)及構(gòu)造算法

普通高等院?！笆濞曇?guī)劃教材7.3.2根本的決策樹(shù)學(xué)習(xí)算法

普通高等院校“十二五〞規(guī)劃教材7.3.2根本的決策樹(shù)學(xué)習(xí)算法

普通高等院?！笆濞曇?guī)劃教材7.4基于實(shí)例的學(xué)習(xí)基于實(shí)例的學(xué)習(xí)采用保管實(shí)例本身的方法來(lái)表達(dá)從實(shí)例集提取出的知識(shí)，并將未知的新實(shí)例與現(xiàn)有的類知的實(shí)例聯(lián)絡(luò)起來(lái)進(jìn)展操作。這種方法直接在樣本上任務(wù)，不需求建立規(guī)那么。基于實(shí)例的學(xué)習(xí)方法包括最近鄰法、部分加權(quán)回歸法、基于范例的推理法等等?；趯?shí)例的學(xué)習(xí)只是簡(jiǎn)單地把訓(xùn)練樣例存儲(chǔ)起來(lái)，對(duì)這些實(shí)例進(jìn)展泛化的任務(wù)被推遲到必需分類新的實(shí)例時(shí)，所以也被稱為消極學(xué)習(xí)法。普通高等院?！笆濞曇?guī)劃教材7.4.1k-近鄰算法最近鄰法經(jīng)過(guò)間隔函數(shù)來(lái)判別訓(xùn)練集中的某個(gè)實(shí)例與哪個(gè)位置的測(cè)試實(shí)例最接近，一旦找到最接近的訓(xùn)練實(shí)例，那么最接近實(shí)例所屬的類就被預(yù)測(cè)為測(cè)試實(shí)例的類。本質(zhì)性的任務(wù)在對(duì)新的實(shí)例進(jìn)展分類時(shí)進(jìn)展，經(jīng)過(guò)間隔函數(shù)將每個(gè)新實(shí)例與現(xiàn)有的實(shí)例進(jìn)展比較，利用最接近的現(xiàn)有實(shí)例賦予新實(shí)例類別，這就是最近鄰分類方法。有時(shí)運(yùn)用多個(gè)最近鄰實(shí)例，并且用最近的K個(gè)鄰居所屬的多數(shù)類〔假設(shè)類是數(shù)值型，就是經(jīng)間隔加權(quán)的平均值〕賦予新的實(shí)例類別值，這就是K-近鄰法。普通高等院校“十二五〞規(guī)劃教材7.4.2間隔加權(quán)最近鄰法對(duì)K-近鄰算法的一個(gè)改良是對(duì)K個(gè)近鄰的奉獻(xiàn)進(jìn)展加權(quán)，越近的間隔賦予越大的權(quán)值，這就是所謂的間隔加權(quán)最近鄰法。K-近鄰算法的一切變體都只思索K個(gè)近鄰用以分類查詢點(diǎn)，假設(shè)按間隔加權(quán)，那么可以允許一切的訓(xùn)練樣例都影響實(shí)例Xq的分類，由于間隔非常遠(yuǎn)的實(shí)例影響很小。思索一切樣例的獨(dú)一缺乏是會(huì)使分類進(jìn)展得更慢。假設(shè)分類一個(gè)新實(shí)例時(shí)，思索一切的訓(xùn)練樣例，可以稱其為全局法；假設(shè)僅思索接近的訓(xùn)練樣例，那么稱為部分法。普通高等院?！笆濞曇?guī)劃教材7.4.3基于范例的學(xué)習(xí)1．基于范例推理的普經(jīng)過(guò)程〔1〕聯(lián)想記憶〔2〕類比映射〔3〕獲得求解方案〔4〕評(píng)價(jià)2．范例的表示(1)SUM_NAMEslots：簡(jiǎn)記為SMU槽。(2)Constraintslots：簡(jiǎn)記為CON槽。(3)Taxonomyslots：簡(jiǎn)記為T(mén)AX槽。(4)Causalityslots：簡(jiǎn)記為CAU槽。(5)Similarityslots：簡(jiǎn)記為SIM槽。普通高等院校“十二五〞規(guī)劃教材7.4.3基于范例的學(xué)習(xí)(6)Partonomyslots：簡(jiǎn)記為PAR槽。(7)Csaeslots：簡(jiǎn)記為CAS槽。(8)Theoryslots：簡(jiǎn)記為T(mén)HY槽。3．范例組織〔1〕范例內(nèi)容〔2〕范例索引4．范例的檢