第六章 機(jī)器學(xué)習(xí)(1)-_決策樹學(xué)習(xí)

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

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

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

4、學(xué)科、多種方法的知識發(fā)現(xiàn)、數(shù)據(jù)挖掘與機(jī)器學(xué)習(xí)研究 6 知識發(fā)現(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í)研討會;1984年,機(jī)器學(xué)習(xí)雜志問世。我國于1987年召開了第一屆全國機(jī)器學(xué)習(xí)研討會;1989年成立了以中國科技大學(xué)蔡慶生教授為理事長的理事會。 KDD一詞是在1989年于美國底特律市召開的第一屆KDD國際學(xué)術(shù)會議上正式形成的。 1995年,在加拿大召開了第一屆知識發(fā)現(xiàn)和數(shù)據(jù)挖掘國際學(xué)術(shù)會議。由于數(shù)據(jù)庫中

5、的數(shù)據(jù)被形象地喻為礦床,因此數(shù)據(jù)挖掘一詞很快流傳開來。 7環(huán)境向系統(tǒng)的學(xué)習(xí)部分提供某些信息，學(xué)習(xí)部分利用這些信息修改知識庫，以增進(jìn)系統(tǒng)執(zhí)行部分完成任務(wù)的效能，執(zhí)行部分根據(jù)知識庫完成任務(wù)，同時把獲得的信息反饋給學(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é)

6、習(xí)、類比學(xué)習(xí)、解釋學(xué)習(xí)等。 綜合多因素的分類： 有人工神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)、進(jìn)化學(xué)習(xí)、概念學(xué)習(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ǔ)上求得一個函數(shù)L:SZ，實現(xiàn)從給定數(shù)據(jù)到目標(biāo)空間的映射。 不同特征的學(xué)習(xí)函數(shù)實際上表示了不同的基本問題。 11 目標(biāo)空間是已知有限離散值空間，即， Z=C=c1,c2,ci,cn待求函數(shù)就是分類函數(shù)（分類器/分類模型）。 分類問題所用的訓(xùn)練數(shù)據(jù)是， 。 由于學(xué)習(xí)時目標(biāo)類別已知，所以分類算法都是有監(jiān)督學(xué)習(xí)。 常用的方法： 決策樹方法、貝葉斯方法、

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

8、好，同一類別內(nèi)的數(shù)據(jù)差距越小越好。 聚類問題所用的訓(xùn)練數(shù)據(jù)是D（ ）。 聚類問題要用無監(jiān)督學(xué)習(xí) 常用的方法： 劃分聚類法、層次聚類法、基于密度的聚類、基于網(wǎng)格的聚類、自組織特征映射網(wǎng)絡(luò)等等。SD 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)化問題，就是在給定

9、數(shù)據(jù)范圍內(nèi)尋找使某值達(dá)到最大（最?。┑姆椒?。 優(yōu)化問題一般都有一些約束條件 例如時空資源的限制等等。 典型代表就是NP問題，這也是計算機(jī)科學(xué)中的一類經(jīng)典問題。 解決優(yōu)化問題對于提高系統(tǒng)效率，保證系統(tǒng)實用性有重要意義。 常用的方法有： 遺傳算法、Hopfield神經(jīng)網(wǎng)絡(luò)、線性規(guī)劃方法等等。 16 機(jī)器學(xué)習(xí)一般不要求結(jié)果100%正確。 評估原則 學(xué)習(xí)結(jié)果的合理性和有效性 模型的泛化能力（Generalization）越強(qiáng)越好。 算法復(fù)雜度（Complexity） 時間復(fù)雜度、空間復(fù)雜度等。 減小時間復(fù)雜度常用的思路： 簡化問題，降低要求； 用空間換時間； 用并行化算法，提高并行度 17 模型魯棒性

10、（Robustness） 就是系統(tǒng)的健壯性，就是系統(tǒng)處理各種非正常數(shù)據(jù)的能力。 包括 對數(shù)據(jù)噪聲的處理， 對缺失數(shù)據(jù)及其它包含不完整信息數(shù)據(jù)的處理， 對錯誤數(shù)據(jù)或者含有矛盾數(shù)據(jù)的處理等等。 18 模型適應(yīng)性 是指對于不同數(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ù)都遵從同樣的分

11、布規(guī)律。 保留法（Holdout） 取S的一部分（通常為2/3）作為訓(xùn)練數(shù)據(jù)，剩下的部分（通常為1/3）作為測試數(shù)據(jù)。 最后在測試數(shù)據(jù)集上驗證學(xué)習(xí)結(jié)果。 特點 僅僅使用了部分（2/3）數(shù)據(jù)訓(xùn)練學(xué)習(xí)模型，沒有充分利用所有的已知數(shù)據(jù)。 保留法一般用于已知數(shù)據(jù)量非常巨大的時候。 20交叉驗證法（Cross Validation） 也稱為交叉糾錯法 把S劃分為k個不相交的子集，即S=S1,S2,Sk，(SiSj=,1i,jk) 然后取其中一個子集作測試集，剩下數(shù)據(jù)作訓(xùn)練集。 取Si做測試集，則S-Si就做訓(xùn)練集。 重復(fù)k次，把每一個子集都做一次測試集。 于是會得到k個測試結(jié)果，最終的測試結(jié)果就是這k個

12、測試結(jié)果的平均值。特點 交叉驗證法還可以再重復(fù)多次，每次變換不同的k值或者不同的劃分。 交叉驗證法充分利用了所有已知數(shù)據(jù)，可以獲得較好的學(xué)習(xí)結(jié)果，但是顯然需要更長的訓(xùn)練時間。 交叉驗證法一般用于已知數(shù)據(jù)量不太大的時候。 21 隨機(jī)法 隨機(jī)抽取S中的一部分?jǐn)?shù)據(jù)作為測試數(shù)據(jù)，把剩下的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)。 重復(fù)這一過程足夠多次。 最終測試結(jié)果是所有測試結(jié)果的平均值。 特點 隨機(jī)法可以重復(fù)無數(shù)次，每個數(shù)據(jù)都可能被充分地用于訓(xùn)練和測試，可以把測試結(jié)果的置信區(qū)間減小到指定寬度。 隨機(jī)法中不同的測試集不能看作是對已知數(shù)據(jù)的獨立抽取。而交叉驗證法中不同的測試集是獨立的，因為一個數(shù)據(jù)只在測試集中出現(xiàn)一次。 22

13、誤差（Error） 測試數(shù)據(jù)集T上的誤差是其中，Ei表示某個數(shù)據(jù)的理想結(jié)果，Li表示該數(shù)據(jù)的機(jī)器學(xué)習(xí)結(jié)果。 常用的誤差實際上就是方差 |1)(TiiiiLEPTError |112)()(TidjijijiLEPTError23 正確率（Accuracy）或錯誤率（Error Rate） 正確率是被正確處理的數(shù)據(jù)個數(shù)與所有被處理數(shù)據(jù)個數(shù)的比值其中TError表示被正確處理的數(shù)據(jù)，也就是誤差足夠小的數(shù)據(jù) 錯誤率則是沒有被正確處理的數(shù)據(jù)個數(shù)與所有被處理數(shù)據(jù)個數(shù)的比值 |)(TTTAccuracyError)(1|1|)(TAccuracyTTTTTTErrorRateErrorError24 復(fù)合

14、指標(biāo) 精度（Precision，或稱為命中率，準(zhǔn)確率） 召回率（Recall，或稱為覆蓋率） a：判定屬于類且判定正確； b：判定屬于類且判定錯誤； c：判定不屬于類且判定正確； d：判定不屬于類且判定錯誤。T=a+b+c+d|)(baaTprecision|)(daaTrecall|)(dcbacaTAccuracy25 F度量（F-Measure） F度量是精度和召回率的調(diào)和平均數(shù)（Harmonic Mean） 其中是一個大于0的實數(shù)，表示精度相對于召回率的權(quán)重。 最常用=1，即F1度量 )()()()() 1()(22TrecallTprecisionTrecallTprecisionT

15、F)()()()(2)(1TrecallTprecisionTrecallTprecisionTF26 多分類問題學(xué)習(xí)結(jié)果的評判 對于測試集T，目標(biāo)類別共有k個 宏平均法（Macro Average） 思路 先計算各個類別自身的精度和召回率， 然后把各個類別的指標(biāo)加在一起求算術(shù)平均值。 宏平均精度 宏平均召回率 kiimacroTprecisionkTprecision1)(1)(kiimacroTrecallkTrecall1)(1)(27 微平均法（Micro Average） 把整個測試集看作單分類問題，一次性計算所有個體樣本指標(biāo)的平均值。 微平均精度 微平均召回率 kiikiikiim

16、icrobaaTprecision111|)(kiikiikiimicrodaaTrecall111|)(28決策樹學(xué)習(xí)是應(yīng)用最廣的歸納推理算法之一。它是一種逼近離散值函數(shù)的方法。 學(xué)習(xí)到的函數(shù)被表示為決策樹的形式表示。 主要用于分類決策樹學(xué)習(xí)方法對噪聲數(shù)據(jù)有很好的健壯性能夠?qū)W習(xí)析取表達(dá)式29決策樹生成方法：從一棵為空的決策樹開始，不斷地在決策樹中加入新的節(jié)點，直到生成的決策樹能夠?qū)λ杏?xùn)練樣本正確分類為止。通過把實例從根節(jié)點排列(sort)到某個葉子節(jié)點來分類實例，葉子節(jié)點即為實例所屬的分類。樹上的每一個節(jié)點說明了對實例的某個屬性(attribute)的測試，并且該節(jié)點的每一個后繼分枝對應(yīng)于

17、該屬性的一個可能值。分類實例的方法：從這棵樹的根節(jié)點開始，測試這個節(jié)點指定的屬性；然后按照給定實例的該屬性值對應(yīng)的樹枝向下移動；然后這個過程再以新節(jié)點為根的子樹上重復(fù)。決策樹結(jié)構(gòu)決策樹結(jié)構(gòu) 圖結(jié)構(gòu)圖結(jié)構(gòu) 內(nèi)部節(jié)點（非樹葉節(jié)點，包括根節(jié)點）在一個屬性下的測試 分枝一個測試輸出 樹葉節(jié)點類標(biāo)識31決策樹結(jié)構(gòu)決策樹結(jié)構(gòu)（代表分類后所獲得的分類標(biāo)記）32：什么因素影響打網(wǎng)球？：什么因素影響打網(wǎng)球？33例子： 在一個水果的分類問題中，采用的特征向量為：顏色，尺寸，形狀，味道，其中： 顏色屬性的取值范圍：紅，綠，黃 尺寸屬性的取值范圍：大，中，小 味道屬性的取值范圍：甜，酸 形狀屬性的取值范圍：圓，細(xì)樣本

18、集樣本集：一批水果，知道其特征向量及類別問問 題題：一個新的水果，觀測到了其特征向量， 應(yīng)該將其分類哪一類？：水果的類別：水果的類別3435 通常決策樹代表實例屬性值約束的合取(conjunction)的析取式(disjunction)。從樹根到樹葉的每一條路徑對應(yīng)一組屬性測試的合取，樹本身對應(yīng)這些合取的析取。 上述例子可對應(yīng)如下析取式：(顏色=綠尺寸=大)(顏色=綠尺寸=中)(顏色=綠尺寸=小)(顏色=黃形狀=圓尺寸=大)(顏色=黃形狀=圓尺寸=小)(顏色=黃形狀=細(xì))(顏色=紅尺寸=中)(顏色=紅尺寸=小味道=甜)(顏色=紅尺寸=小味道=酸) 36：鳥是否會飛翔：鳥是否會飛翔3738構(gòu)建決策樹構(gòu)建決策樹40構(gòu)建決策樹過程構(gòu)建決策樹過程4142434445構(gòu)建決策樹46決策樹學(xué)習(xí)的適用問題 實例由“屬性-值”對表示 目標(biāo)函數(shù)具有離散的輸出值（1or 0） 可能需要析取的描述 訓(xùn)練數(shù)據(jù)可以包含錯誤 訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實例-賦給最常見的值或賦予每個可能值一個概率48 確定決策樹增長的深度，避免過度擬合； 處理連續(xù)值的屬性； 選擇一個適當(dāng)?shù)膶傩院Y選度量標(biāo)準(zhǔn)； 處理屬性值不完整的訓(xùn)練數(shù)據(jù)； 處理不同代價的屬性； 提高計算效率。 49 定義6.3 給定一個假設(shè)空間H和一個訓(xùn)練數(shù)據(jù)集D。對于一個假設(shè)h（hH），如果存在其它的假設(shè)h（hH），使得在訓(xùn)練數(shù)