人工智能導(dǎo)論-第六章-機(jī)器學(xué)習(xí)

1、第六章 機(jī)器學(xué)習(xí)6.1 概述6.2 決策樹學(xué)習(xí)6.3 貝葉斯學(xué)習(xí)6.4 統(tǒng)計(jì)學(xué)習(xí)6.5 聚類26.1.1 什么是機(jī)器學(xué)習(xí)？學(xué)習(xí)是人類具有的一種重要智能行為，但究竟什么是學(xué)習(xí)，長期以來卻眾說紛紜。關(guān)于“學(xué)習(xí)”這一概念的主要觀點(diǎn)：學(xué)習(xí)是系統(tǒng)改進(jìn)其性能的過程。這是西蒙的觀點(diǎn)。西蒙的觀點(diǎn)：學(xué)習(xí)就是系統(tǒng)在不斷重復(fù)的工作中對本身能力的增強(qiáng)或者改進(jìn)，使得系統(tǒng)在下一次執(zhí)行同樣任務(wù)或類似任務(wù)時(shí)，會(huì)比現(xiàn)在做得更好或效率更高。學(xué)習(xí)是獲取知識的過程。這是從事專家系統(tǒng)研究的人們的觀點(diǎn)。學(xué)習(xí)是技能的獲取。這是心理學(xué)家的觀點(diǎn)。學(xué)習(xí)是事物規(guī)律的發(fā)現(xiàn)過程。 3基本的學(xué)習(xí)形式有2種：知識獲取和技能求精。例如，我們說某人學(xué)過物理。

2、我們的意思是，此人已經(jīng)掌握了有關(guān)物理學(xué)的基本概念，并且理解其含義，同時(shí)還懂得這些概念之間以及它們與物理世界之間的關(guān)系。一般地，知識獲取可看作學(xué)習(xí)新的符號信息，而這些符號信息是以有效方式與應(yīng)用這種信息的能力相適應(yīng)的。第二類學(xué)習(xí)形式是通過實(shí)踐逐步改進(jìn)機(jī)制和認(rèn)知技能。例如騎自行車或彈鋼琴等等。學(xué)習(xí)的很多過程都是由改進(jìn)所學(xué)的技能組成。這些技能包括意識的或者機(jī)制的協(xié)調(diào)，而這種改進(jìn)又是通過反復(fù)實(shí)踐和從失敗的行為中糾正偏差來進(jìn)行的。知識獲取的本質(zhì)可能是一個(gè)自覺的過程，其結(jié)果產(chǎn)生新的符號知識結(jié)構(gòu)和智力模型。而技能求精則是下意識地借助于反復(fù)實(shí)踐來實(shí)現(xiàn)的。人類的學(xué)習(xí)一般表現(xiàn)尾這兩種活動(dòng)的結(jié)合。 4至今，還沒有統(tǒng)一

3、的“機(jī)器學(xué)習(xí)”定義，而且也很難給出一個(gè)公認(rèn)的和準(zhǔn)確的定義。一般認(rèn)為機(jī)器學(xué)習(xí)是研究如何使用機(jī)器來模擬人類學(xué)習(xí)活動(dòng)的一門學(xué)科。 最早的具有學(xué)習(xí)能力的程序：1959年美國的塞繆爾(Samuel)設(shè)計(jì)了一個(gè)下棋程序，這個(gè)程序具有學(xué)習(xí)能力，它可以在不斷的對奕中改善自己的棋藝。4年后，這個(gè)程序戰(zhàn)勝了設(shè)計(jì)者本人。又過了3年，這個(gè)程序戰(zhàn)勝了美國一個(gè)保持8年之久的常勝不敗的冠軍。5第一階段在50年代中葉到60年代中葉，神經(jīng)元模型的研究。第二階段在60年代中葉至70年代，符號學(xué)習(xí)的研究。第三階段80年代，連接學(xué)習(xí)的研究與符號學(xué)習(xí)的進(jìn)展。90年代以后，綜合多學(xué)科、多種方法的知識發(fā)現(xiàn)、數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)研究 6知識發(fā)

4、現(xiàn)(Knowledge Discovering in Database)與數(shù)據(jù)挖掘(Data Mining)是人工智能、機(jī)器學(xué)習(xí)與(Machine Learning)數(shù)據(jù)庫技術(shù)相結(jié)合的產(chǎn)物。1980年,在美國召開了第一屆國際機(jī)器學(xué)習(xí)研討會(huì);1984年,機(jī)器學(xué)習(xí)雜志問世。我國于1987年召開了第一屆全國機(jī)器學(xué)習(xí)研討會(huì);1989年成立了以中國科技大學(xué)蔡慶生教授為理事長的理事會(huì)。KDD一詞是在1989年于美國底特律市召開的第一屆KDD國際學(xué)術(shù)會(huì)議上正式形成的。1995年,在加拿大召開了第一屆知識發(fā)現(xiàn)和數(shù)據(jù)挖掘國際學(xué)術(shù)會(huì)議。由于數(shù)據(jù)庫中的數(shù)據(jù)被形象地喻為礦床,因此數(shù)據(jù)挖掘一詞很快流傳開來。 7環(huán)境向系

5、統(tǒng)的學(xué)習(xí)部分提供某些信息，學(xué)習(xí)部分利用這些信息修改知識庫，以增進(jìn)系統(tǒng)執(zhí)行部分完成任務(wù)的效能，執(zhí)行部分根據(jù)知識庫完成任務(wù)，同時(shí)把獲得的信息反饋給學(xué)習(xí)部分。在具體的應(yīng)用中，環(huán)境，知識庫和執(zhí)行部分決定了具體的工作內(nèi)容，學(xué)習(xí)部分所需要解決的問題完全由上述3部分確定。 學(xué)習(xí)系統(tǒng)的基本結(jié)構(gòu)8機(jī)器學(xué)習(xí)系統(tǒng)中學(xué)習(xí)環(huán)節(jié)的一般過程 9按照有無指導(dǎo)來分：有監(jiān)督學(xué)習(xí)（或有導(dǎo)師學(xué)習(xí)）、無監(jiān)督學(xué)習(xí)（或無導(dǎo)師學(xué)習(xí)）和強(qiáng)化學(xué)習(xí)（或增強(qiáng)學(xué)習(xí)）。按學(xué)習(xí)方法來分：有機(jī)械式學(xué)習(xí)、指導(dǎo)式學(xué)習(xí)、范例學(xué)習(xí)、類比學(xué)習(xí)、解釋學(xué)習(xí)。按推理策略來分：有演繹學(xué)習(xí)、歸納學(xué)習(xí)、類比學(xué)習(xí)、解釋學(xué)習(xí)等。綜合多因素的分類：有人工神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)、進(jìn)化學(xué)習(xí)、概念學(xué)

6、習(xí)、分析學(xué)習(xí)、基于范例的學(xué)習(xí)等等。10機(jī)器學(xué)習(xí)中解決的基本問題主要有：分類、聚類、預(yù)測、聯(lián)想、優(yōu)化。令S表示數(shù)據(jù)空間，Z表示目標(biāo)空間。機(jī)器學(xué)習(xí)就是在現(xiàn)有觀察的基礎(chǔ)上求得一個(gè)函數(shù)L:SZ，實(shí)現(xiàn)從給定數(shù)據(jù)到目標(biāo)空間的映射。不同特征的學(xué)習(xí)函數(shù)實(shí)際上表示了不同的基本問題。 11目標(biāo)空間是已知有限離散值空間，即， Z=C=c1,c2,ci,cn待求函數(shù)就是分類函數(shù)（分類器/分類模型）。分類問題所用的訓(xùn)練數(shù)據(jù)是， 。由于學(xué)習(xí)時(shí)目標(biāo)類別已知，所以分類算法都是有監(jiān)督學(xué)習(xí)。常用的方法：決策樹方法、貝葉斯方法、前饋神經(jīng)網(wǎng)絡(luò)BP算法、支持向量機(jī)方法等 12目標(biāo)空間是連續(xù)值空間，待求函數(shù)就是回歸（擬合）曲線（面）。此

7、時(shí)機(jī)器學(xué)習(xí)解決預(yù)測問題，也就是求一個(gè)數(shù)據(jù)在目標(biāo)空間中符合某觀測規(guī)律的象。預(yù)測問題所用的訓(xùn)練數(shù)據(jù)是， 。 一般情況下我們事先已知（或者選擇了）曲線（面）模型，需要學(xué)習(xí)的是模型中的參數(shù)。例如已知多項(xiàng)式模型，但是要學(xué)習(xí)各項(xiàng)的系數(shù)。常用的方法：人工神經(jīng)網(wǎng)絡(luò)方法、線性回歸、非線性回歸、灰色預(yù)測模型等。 13目標(biāo)空間是未知有限離散值空間，即，Z=X=x1,x2,xk待求函數(shù)就是聚類函數(shù)，也稱為聚類模型。聚類問題就是把已知數(shù)據(jù)集劃分為不同子集（類別），并且不同類別之間的差距越大越好，同一類別內(nèi)的數(shù)據(jù)差距越小越好。聚類問題所用的訓(xùn)練數(shù)據(jù)是D（ ）。聚類問題要用無監(jiān)督學(xué)習(xí) 常用的方法：劃分聚類法、層次聚類法、基

8、于密度的聚類、基于網(wǎng)格的聚類、自組織特征映射網(wǎng)絡(luò)等等。14目標(biāo)空間就是數(shù)據(jù)空間本身，即，Z=S待求函數(shù)就是求自身內(nèi)部的一種映射。聯(lián)想問題，也稱為相關(guān)性分析或者關(guān)聯(lián)問題就是發(fā)現(xiàn)不同數(shù)據(jù)（屬性）之間的相互依賴關(guān)系。簡單地說，就是可以從事物A推出事物B，即AB常用的方法：反饋神經(jīng)網(wǎng)絡(luò)、關(guān)聯(lián)規(guī)則、回歸分析等等。 15目標(biāo)空間是數(shù)據(jù)空間上的某種函數(shù)（用F(S)表示），且學(xué)習(xí)目標(biāo)為使對函數(shù)F(S)的某種度量dF(S)達(dá)到極值。解決優(yōu)化問題，就是在給定數(shù)據(jù)范圍內(nèi)尋找使某值達(dá)到最大（最小）的方法。優(yōu)化問題一般都有一些約束條件例如時(shí)空資源的限制等等。典型代表就是NP問題，這也是計(jì)算機(jī)科學(xué)中的一類經(jīng)典問題。解決優(yōu)

9、化問題對于提高系統(tǒng)效率，保證系統(tǒng)實(shí)用性有重要意義。常用的方法有：遺傳算法、Hopfield神經(jīng)網(wǎng)絡(luò)、線性規(guī)劃方法等等。 16機(jī)器學(xué)習(xí)一般不要求結(jié)果100%正確。評估原則學(xué)習(xí)結(jié)果的合理性和有效性模型的泛化能力（Generalization）越強(qiáng)越好。算法復(fù)雜度（Complexity）時(shí)間復(fù)雜度、空間復(fù)雜度等。減小時(shí)間復(fù)雜度常用的思路：簡化問題，降低要求；用空間換時(shí)間；用并行化算法，提高并行度 17模型魯棒性（Robustness）就是系統(tǒng)的健壯性，就是系統(tǒng)處理各種非正常數(shù)據(jù)的能力。包括對數(shù)據(jù)噪聲的處理，對缺失數(shù)據(jù)及其它包含不完整信息數(shù)據(jù)的處理，對錯(cuò)誤數(shù)據(jù)或者含有矛盾數(shù)據(jù)的處理等等。 18模型適應(yīng)

10、性是指對于不同數(shù)據(jù)，學(xué)習(xí)模型本身需要做多少人工調(diào)整。我們一般都希望模型本身需要人工指定參數(shù)越少越好。自適應(yīng)模型并不意味著徹底不需要人工指定的參數(shù)。模型描述的簡潔性和可解釋性。根據(jù)奧坎姆剃刀（Occams Razor）原則，應(yīng)該優(yōu)先選擇更簡單的假設(shè)。模型描述愈簡潔、愈容易理解，則愈受歡迎。 19從S中分割出訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)假設(shè)S是已有數(shù)據(jù)集，并且訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)都遵從同樣的分布規(guī)律。 保留法（Holdout）取S的一部分（通常為2/3）作為訓(xùn)練數(shù)據(jù)，剩下的部分（通常為1/3）作為測試數(shù)據(jù)。最后在測試數(shù)據(jù)集上驗(yàn)證學(xué)習(xí)結(jié)果。特點(diǎn)僅僅使用了部分（2/3）數(shù)據(jù)訓(xùn)練學(xué)習(xí)模型，沒有充分利用所有的已知數(shù)據(jù)

11、。保留法一般用于已知數(shù)據(jù)量非常巨大的時(shí)候。 20交叉驗(yàn)證法（Cross Validation）也稱為交叉糾錯(cuò)法把S劃分為k個(gè)不相交的子集，即S=S1,S2,Sk，(SiSj=,1i,jk)然后取其中一個(gè)子集作測試集，剩下數(shù)據(jù)作訓(xùn)練集。取Si做測試集，則S-Si就做訓(xùn)練集。重復(fù)k次，把每一個(gè)子集都做一次測試集。于是會(huì)得到k個(gè)測試結(jié)果，最終的測試結(jié)果就是這k個(gè)測試結(jié)果的平均值。特點(diǎn)交叉驗(yàn)證法還可以再重復(fù)多次，每次變換不同的k值或者不同的劃分。交叉驗(yàn)證法充分利用了所有已知數(shù)據(jù)，可以獲得較好的學(xué)習(xí)結(jié)果，但是顯然需要更長的訓(xùn)練時(shí)間。交叉驗(yàn)證法一般用于已知數(shù)據(jù)量不太大的時(shí)候。 21隨機(jī)法隨機(jī)抽取S中的一部

12、分?jǐn)?shù)據(jù)作為測試數(shù)據(jù)，把剩下的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)。重復(fù)這一過程足夠多次。最終測試結(jié)果是所有測試結(jié)果的平均值。特點(diǎn)隨機(jī)法可以重復(fù)無數(shù)次，每個(gè)數(shù)據(jù)都可能被充分地用于訓(xùn)練和測試，可以把測試結(jié)果的置信區(qū)間減小到指定寬度。隨機(jī)法中不同的測試集不能看作是對已知數(shù)據(jù)的獨(dú)立抽取。而交叉驗(yàn)證法中不同的測試集是獨(dú)立的，因?yàn)橐粋€(gè)數(shù)據(jù)只在測試集中出現(xiàn)一次。 22誤差（Error）測試數(shù)據(jù)集T上的誤差是其中，Ei表示某個(gè)數(shù)據(jù)的理想結(jié)果，Li表示該數(shù)據(jù)的機(jī)器學(xué)習(xí)結(jié)果。常用的誤差實(shí)際上就是方差 23正確率（Accuracy）或錯(cuò)誤率（Error Rate） 正確率是被正確處理的數(shù)據(jù)個(gè)數(shù)與所有被處理數(shù)據(jù)個(gè)數(shù)的比值其中TError

13、 0.4765MAP假設(shè)貝葉斯最優(yōu)分類器數(shù)據(jù)h數(shù)據(jù)為正數(shù)據(jù)為負(fù)不同的方法結(jié)果不同!h66貝葉斯學(xué)習(xí)為衡量多個(gè)假設(shè)的置信度提供了定量的方法，可以計(jì)算每個(gè)假設(shè)的顯式概率，提供了一個(gè)客觀的選擇標(biāo)準(zhǔn)。 特性 觀察到的每個(gè)訓(xùn)練樣例可以增量地降低或升高某假設(shè)的估計(jì)概率。先驗(yàn)知識可以與觀察數(shù)據(jù)一起決定假設(shè)的最終概率。允許假設(shè)做出不確定性的預(yù)測。例如前方目標(biāo)是駱駝的可能性是90%，是馬的可能性是5%。新的實(shí)例分類可由多個(gè)假設(shè)一起做出預(yù)測，用它們的概率來加權(quán)。即使在貝葉斯方法計(jì)算復(fù)雜度較高時(shí)，它仍可作為一個(gè)最優(yōu)決策標(biāo)準(zhǔn)去衡量其它方法。 67在機(jī)器學(xué)習(xí)中一個(gè)實(shí)例x往往有很多屬性其中每一維代表一個(gè)屬性，該分量的數(shù)值

14、就是所對應(yīng)屬性的值。68此時(shí)依據(jù)MAP假設(shè)的貝葉斯學(xué)習(xí)就是對一個(gè)數(shù)據(jù)，求使其滿足下式的目標(biāo)值。其中H是目標(biāo)值集合。 69估計(jì)每個(gè)P(hi)很容易，只要計(jì)算每個(gè)目標(biāo)值hi出現(xiàn)在訓(xùn)練數(shù)據(jù)中的頻率就可以。如果要如此估計(jì)所有的P(a1,a2,an|hi)項(xiàng)，則必須計(jì)算a1,a2,an的所有可能取值組合，再乘以可能的目標(biāo)值數(shù)量。假設(shè)一個(gè)實(shí)例有10個(gè)屬性，每個(gè)屬性有3個(gè)可能取值，而目標(biāo)集合中有5個(gè)候選目標(biāo)。那么P(a1,a2,an|hi)項(xiàng)就有 個(gè)。不適合于高維數(shù)據(jù)！70對于貝葉斯學(xué)習(xí),樸素貝葉斯（Nave Bayes）方法，也稱為簡單貝葉斯（Simple Bayes）方法,可以解決高維數(shù)據(jù)問題。樸素貝葉斯分類器采用最簡單的假設(shè)：對于目標(biāo)值，數(shù)據(jù)各屬性之間相互條件獨(dú)立。即，a1,a2,an的聯(lián)合概率等于每個(gè)單獨(dú)屬性的概率乘積：71將上頁的式子帶入上面求 的公式中，就得到樸素貝葉斯分類器所用的方法：其中 表示樸素貝葉斯分類器輸出的目標(biāo)值。72假設(shè)一個(gè)實(shí)例有10個(gè)屬性，每個(gè)屬性有3個(gè)可能取值，而目標(biāo)集合中有5個(gè)候選目標(biāo)。樸