2016.11機器學習(MachineLearning)機器學習報告建議內容基本概念以及數學定義基本性質及其物理意義具體算法應用（詳細舉例講解）該算法與其他類似算法的分析比較可能的發展方向附參考文獻2報告建議內容基本概念以及數學定義2《機器學習》，TomM.Mitchell（湯姆·米切爾）著，曾華軍，張銀華等譯，機械工業出版社，2003年。參考書《機器學習》，TomM.Mitchell（湯姆·米切爾）著，其它參考書《機器學習及其應用》，周志華，王鈺主編，清華大學出版社，2009。《神經網絡與機器學習》，SimonHaykin著，機械工業出版社，2010。《機器學習導論》，EthemAlpaydin著，機械工業出版社，2009。《MachineLearning——AProbabilisticPerspective》KevinP.Murphy,2012其它參考書《機器學習及其應用》，周志華，王鈺主編，清華大學出第1章引言什么是機器學習

【經典定義】：計算機程序如何隨著經驗積累自動提高性能，系統自我改進的過程。或：計算機利用經驗改善系統自身性能的行為。——米切爾隨著該領域的發展，主要做智能數據分析。第1章引言什么是機器學習學習與智能學習現象語言、文字的認知識別圖像、場景、自然物體的認知識別規則（eg下雨天要帶雨傘）復雜的推理、判斷能力（智能）好人與壞人？好貓與壞貓？數據知識認知推理決策識別學習學習與智能學習現象數據知識認知學習什么是機器學習？使得計算機具備和人類一樣的學習能力決策推理認知識別……等智能給定數據（樣本、實例）和一定的學習規則，從數據中獲取知識的能力什么是機器學習？使得計算機具備和人類一樣的學習能力機器學習與人工智能自然智慧的偉大與奧妙舉例：嬰兒的認知能力（聲音、人臉、汽車…）重要的二個特點：容錯性，推廣能力（舉一反三）機器智能：希望用機器實現部分智能基于數據的機器學習問題（引自清華張學工教授）根據已知樣本估計數據之間的依賴關系，從而對未知或無法測量的數據進行預測和判斷關鍵：推廣能力機器學習與人工智能自然智慧的偉大與奧妙什么是機器學習中科院王玨研究員給出的定義：令W是給定世界的有限或無限所有觀測對象的集合，由于我們的觀測能力有限，我們只能獲得這個世界的一個子集，稱為樣本集。機器學習就是根據這個樣本集，推算這個世界W的模型，使它對這個世界（盡可能地）為真。三個重要的理論問題：一致：W與Q有相同的性質。eg.i.i.d劃分：設樣本定義于d維空間，要尋找在這個空間上的決策分界面泛化（推廣能力）：對未知樣本的判斷能力什么是機器學習中科院王玨研究員給出的定義：What’sistheLearningProblem?Learning=ImprovingwithexperienceatsometaskImproveovertaskTWithrespecttoperformancemeasurementPBasedonexperienceEExample:中國象棋任務T：下中國象棋性能目標P：比賽中擊敗對手（的百分比）訓練經驗E：和自己進行對弈，或者看棋譜Ref：《機器學習》（曾華軍等譯）What’sistheLearningProblemPedro對學習理解Pedro對學習理解MachineLearning引用自CMUDr.EricXing的LectureNotesMachineLearning引用自CMUDr.Eri機器學習的研究意義機器學習的研究意義機器學習的重要性！《Science》2001年論文：…每個科學領域的科學過程都有它自己的特點，但是，觀察、創立假設、根據決定性實驗或觀察的檢驗、可理解檢驗的模型或理論，是各個學科所共有的。對這個抽象的科學過程的每一個環節，機器學習都有相應的發展，我們相信它將導致科學方法中從假設生成、模型構造到決定性實驗這些所有環節的合適的、部分的自動化。當前機器學習研究在一些基本論題上取得令人印象深刻的進展，我們預期機器學習研究在今后若干年中將有穩定的進展！”在稍早前，2000年《Science》還發表了另外3篇ML方面的論文“TheManifoldWayofPerceptron”,“Aglobalgeometricframeworkfornonlineardimensionalityreduction”,”Nonlineardimensionalityreductionbylocally…”Mjolsness,DDeCoste,MachineLearningforScience:StateoftheArtandFutureProspects-Science,2001:2051-2055.

受到令人驚訝的重視！機器學習的重要性！《Science》2001年論文：Mjol機器學習的重要性摘自南京大學周志華教授生物信息學計算金融學分子生物學行星地質學……工業過程控制機器人……遙感信息處理信息安全機器學習機器學習的重要性摘自南京大學周志華教授生物計算分子行星……工多學科交叉機器學習也是一個多學科交叉的產物，它吸取了人工智能、概率統計、神經生物學、認知科學、信息論、控制論、計算復雜性理論、哲學等學科的成果。實踐證明，機器學習在很多應用領域發揮了重要的實用價值，特別是在數據挖掘、語音識別、圖像處理、機器人、車輛自動駕駛、生物信息學、信息安全、遙感信息處理、計算金融學、工業過程控制。多學科交叉機器學習也是一個多學科交叉的產物，它吸取了人工智能重要性：例子—網絡安全入侵檢測：是否是入侵？是何種入侵？如何檢測？歷史數據：以往的正常訪問模式及其表現、以往的入侵模式及其表現……對當前訪問模式分類這是一個典型的預測型機器學習問題常用技術：神經網絡決策樹支持向量機k近鄰序列分析聚類…………重要性：例子—網絡安全入侵檢測：如何檢測？這是一個典型的預測搜索引擎摘自南京大學周志華教授搜索引擎摘自南京大學周志華教授重要性：例子—生物信息學常用技術：神經網絡支持向量機隱馬爾可夫模型k近鄰決策樹序列分析聚類…………重要性：例子—生物信息學常用技術：重要性：例子—數據驅動控制重要性：例子—數據驅動控制相關學科對ML的影響人工智能：學習的概念符號表示Bayes方法統計學：統計學習理論(SLT)計算復雜性理論控制論信息論：最小描述長度哲學：“Occam’sRazor原則”，“沒有免費午餐”心理學和神經生物學：NeuralNetworks（神經網絡）相關學科對ML的影響人工智能：機器學習目前主要的一些研究領域符號機器學習Eg.決策樹，ID3，…計算學習理論（統計學習理論）PAC，SVM監督學習，非監督學習，半監督學習集群機器學習EnsembleLearning，Boosting流行（Manifold）學習強化學習Ranking學習聚類學習…機器學習目前主要的一些研究領域符號機器學習MachineLearningTopicsfromWiki/wiki/Machine_LearningMachineLearningTopicsfromW機器學習簡要發展歷史回顧機器學習簡要發展歷史回顧ML的發展歷史(1)1950s：神經科學的理論基礎James關于神經元是相互連接的發現McCullon&Pitts的神經元模型Hebb學習律（相互連接強弱度的變換規則）1960s：感知器（Perceptron）時代1957年Rosenblatt首次提出ML的發展歷史(1)1950s：神經科學的理論基礎ML的發展歷史(2)1969年：《Perceptron》出版，提出著名的XOR問題1970s：符號主義，邏輯推理1980s：MLP+BP算法成功解決XOR問題，從此進入神經網絡時代（連接主義）1960s-1970s:統計學習理論創立VC維的基本概念結構風險最小化原則概率空間的大數定律ML的發展歷史(2)1969年：《Perceptron》出版ML的發展歷史(3)1990s：統計學習理論的發展及完善典型代表：SVM（Vapnik，Bell實驗室）結構風險最小化最小描述長度原則小樣本問題核函數、核空間變化PAC理論下的弱可學習理論的建立支持向量機…ML的發展歷史(3)1990s：統計學習理論的發展及完善ML的發展歷史(4)2000s：各種機器學習理論及算法得以充分發展符號機器學習計算機器學習（統計學習理論，典型例子：SVM）集群機器學習（典型代表：Boosting）強化機器學習流行機器學習監督學習，非監督學習半監督學習、….ML的發展歷史(4)2000s：各種機器學習理論及算法得以充未來發展趨勢機器實際上是一個應用驅動的學科，其根本的驅動力是：“更多、更好地解決實際問題”由于近20年的飛速發展，機器學習已經具備了一定的解決實際問題的能力，似乎逐漸開始成為一種基礎性、透明化的“支持技術、服務技術”基礎性：在眾多的學科領域都得以應用（“無所不在”）透明化：用戶看不見機器學習，看見的是防火墻、生物信息、搜索引擎；（“無所不在”）“機器更好用了”(正如CALO的一些描述：“youwon’tleavehomewithoutit”；”embodiedasasoftwareenvironmentthattranscendsworkstations,PDA’s,cellphones,…”)未來發展趨勢機器實際上是一個應用驅動的學科，其根本的驅動力是討論議題機器學習的主要策略與基本結構機器學習的主要策略機器學習系統的基本結構討論議題機器學習的主要策略與基本結構機器學習系統的基本結構我們以西蒙的學習定義做為出發點，建立起下圖1.1所示的簡單的學習模型，然后通過對這個簡單模型的討論，總結出設計學習系統應當注意的某些總的原則。圖1.1學習系統的基本結構機器學習系統的基本結構我們以西蒙的學習定義做為出發點，建立學習問題的標準描述定義如果一個計算機針對某類任務T，用P來衡量性能，根據經驗E來自我完善，那么我們稱這個計算機程序在從經驗E中學習，針對某類任務T，它的性能用P來衡量。西洋跳棋學習問題的解釋E，和自己下棋T，參與比賽P，比賽成績（或贏棋能力，擊敗對手的百分比）手寫識別學習問題機器人駕駛學習問題學習問題的標準描述定義學習問題的標準描述（2）定義太寬泛甚至包括了以非常直接的方式通過經驗自我提高的計算機程序實際的機器學習問題往往比較復雜定義一類問題探索解決這類問題的方法理解學習問題的基本結構和過程學習問題的標準描述（2）定義太寬泛有監督學習有監督的學習方法在樣本標簽已知的情況下，可以統計出各類訓練樣本不同的描述量，如其概率分布，或在特征空間分布的區域等，利用這些參數進行分類器設計，稱為有監督的學習方法。有監督學習有監督的學習方法無監督學習無監督學習然而在實際應用中，不少情況下無法預先知道樣本的標簽，也就是說沒有訓練樣本因而只能從原先沒有樣本標簽的樣本集開始進行分類器設計，這就是通常說的無監督學習方法。對一個具體問題來說有監督與無監督的作法是不相同的無監督學習無監督學習有監督學習x1x2有監督學習x1x2無監督學習x1x2無監督學習x1x2機器學習的問題存在什么樣的算法能從特定的訓練數據學習一般的目標函數呢？如果提供了充足的訓練數據，什么樣的條件下，會使特定的算法收斂到期望的函數？哪個算法對哪些問題和表示的性能最好？多少訓練數據是充足的？怎樣找到學習到假設的置信度與訓練數據的數量及提供給學習器的假設空間特性之間的一般關系？學習器擁有的先驗知識是怎樣引導從樣例進行泛化的過程的？當先驗知識僅僅是近似正確時，它們會有幫助嗎？關于選擇有效的后驗訓練經驗，什么樣的策略最好？這個策略的選擇會如何影響學習問題的復雜性。怎樣把學習任務簡化為一個或多個函數逼近問題？換一種方式，系統該試圖學習哪些函數？這個過程本身能自動完成嗎？學習器怎樣自動地改變表示法來提高表示和學習目標函數的能力？機器學習的問題存在什么樣的算法能從特定的訓練數據學習一般的目課程內容簡介第2章，基于符號和邏輯表示的概念學習（簡介）第3章，決策樹第4章，回歸模型與神經網絡第5章，評估假設第6章，貝葉斯理論（混合模型與EM算法）第7章，基于實例的學習（核函數與徑向基函數網絡）第8章，馬爾科夫與隱馬爾可夫模型第9章，支持向量機（線性判別與SVM）第10章，增強學習課程內容簡介第2章，基于符號和邏輯表示的概念學習（簡介）參考期刊與會議相關雜志MachineLearningNeuralComputationJournaloftheAmericanStatisticalAssociationIEEEtransactionsonPatternAnalysis&MachineIntelligence國際會議國際機器學習會議ICML神經信息處理系統會議NIPS計算學習理論會議CCLT國際遺傳算法會議ICGA參考期刊與會議相關雜志參考學術期刊及國際會議參考學術期刊及國際會議一些網絡資源(1)

AAAIMachineLearningTopics：/AITopics/html/machine.html-SupportVectorMachines：/index.html

一些網絡資源(1)http://machine-learn一些網絡資源(2)/~tom/10701_sp11/lectures.shtmlMachineLearning(Spring2011)@CMUTomMitchellVideoLecture&SlidesMachineLearningResources:/~dwaha/research/machine-learning.html

一些網絡資源(2)一些網絡資源(3)Weka：DataMining(ML)softwareinJava:http://www.cs.waikato.ac.nz/ml/weka/

LibSVM--ALibraryforSupportVectorMachines：.tw/~cjlin/libsvmMLC++:/tech/mlc/:AlibraryofC++classesforsupervisedmachinelearningUCI-MachineLearninginformation,softwareanddatabases:/ml/一些網絡資源(3)Weka：DataMining(ML)一些網絡資源(4)KernalMachines://software/:MachineLearningOpenSourceSoftware.sg/home/aswduch/ai-ml.html

數據挖掘研究院：/一些網絡資源(4)KernalMachines:htt概念學習給定某一類別的若干正例和反例，從中獲得該類別的一般定義。搜索的觀點在預定義的假設空間中搜索假設，使其與訓練樣例有最佳的擬合。利用假設空間的偏序結構算法收斂到正確假設的條件?歸納學習的本質，從訓練數據中泛化的理由?第2章概念學習和一般到特殊序概念學習第2章概念學習和一般到特殊序簡介許多機器學習涉及到從特殊訓練樣例中得到一般概念。概念，可被看作一個對象或事件集合，它是從更大的集合中選取的子集，或在這個較大集合中定義的布爾函數。概念學習問題的定義給定一個樣例集合以及每個樣例是否屬于某個概念的標注，怎樣推斷出該概念的一般定義。又稱從樣例中逼近布爾函數。概念學習是指從有關某個布爾函數的輸入輸出訓練樣例中推斷出該布爾函數。簡介許多機器學習涉及到從特殊訓練樣例中得到一般概念。概念學習任務一個例子目標概念Aldo進行水上運動的日子，表示為布爾函數EnjoySport任務目的基于某天的各屬性，預測EnjoySport的值給定一個樣例集D每個樣例表示為6個屬性的集合概念學習任務一個例子概念學習任務（2）YesChangeCoolStrongHighWarmSunny4NoChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample表2-1目標概念EnjoySport的訓練樣例概念學習任務（2）YesChangeCoolStrongHi概念學習任務（3）表示假設的形式（目標函數的表示）一個簡單的形式，實例的各屬性約束的合取式令每個假設為6個約束（或變量）的向量，每個約束對應一個屬性可取值范圍，為？任意本屬性可接受的值明確指定的屬性值不接受任何值假設的例子<?,Cold,High,?,?,?><?,?,?,?,?,?> //所有的樣例都是正例<,,,,,> //所有的樣例都是反例概念學習任務（3）表示假設的形式（目標函數的表示）概念學習任務（4）形式化描述：已知實例集X每個實例x由6個屬性描述，每個屬性的取值范圍已確定假設集H每個假設h描述為6個屬性的取值約束的合取目標概念c一個布爾函數，變量為實例訓練樣例集D目標函數（或目標概念）的正例和反例求解H中的一假設h，使對于X中任意x，h(x)=c(x)概念學習任務（4）形式化描述：術語定義實例x實例集X概念目標概念c訓練樣例x訓練樣例集D正例，目標概念成員反例，非目標概念成員假設h假設集H機器學習的目標就是尋找一個假設h，使得對所有的h，都有h(x)=c(x)術語定義實例x歸納學習假設什么是歸納學習？從特殊的樣例得到普遍的規律（從特殊到一般）歸納只能保證輸出的假設能與訓練樣例相擬合歸納假設的一個基本假定對于未見實例最好的假設就是與訓練數據最佳擬合的假設歸納學習假設任一假設如果在足夠大的訓練樣例集中很好地逼近目標函數，它也能在未見實例中很好地逼近目標函數。歸納學習假設什么是歸納學習？作為搜索的概念學習概念學習可以看作一個搜索的過程搜索范圍：假設的表示所隱含定義的整個空間搜索目標：能夠最好地擬合訓練樣例的假設當假設的表示形式選定后，那么就隱含地為學習算法確定了所有假設的空間例子EnjoySport的假設空間，如果屬性Sky有3種可能的值，而AirTemp、Humidity、Wind、Water和Forecast都只有兩種可能值。實例空間X：包含3×2×2×2×2×2=96種不同的實例假設空間H包含5×4×4×4×4×4=5120種語法不同的假設由于：包含有符號的假設將每個實例都分類為反例。因此，語義不同的假設只有1+4×3×3×3×3×3=973個。作為搜索的概念學習概念學習可以看作一個搜索的過程假設的一般到特殊序假設的一般到特殊序關系考慮下面兩個假設h1=<sunny,?,?,Strong,?,?>h2=<Sunny,?,?,?,?,?>任何被h1劃分為正例的實例都會被h2劃分為正例，因此h2比h1更一般。利用這個關系，無需列舉所有假設，就能在無限的假設空間中進行徹底的搜索假設的一般到特殊序假設的一般到特殊序關系假設的一般到特殊序（2）關系“更一般”的精確定義任給實例x和假設h，說x滿足h，當且僅當h(x)=1令hj和hk是在X上定義的布爾函數，稱hj比hk更一般，當且僅當(xX)[(hk(x)=1)(hj(x)=1)]記為hjmore_general_than_or_equal_tohk，或hj

ghk假設的一般到特殊序（2）關系“更一般”的精確定義假設的一般到特殊序（3）“更一般”的嚴格情形hj>ghk，當且僅當，(hj

ghk)(hk

ghj)“更特殊”關系的定義hj

ghk，當且僅當，hk

ghj以EnjoySport為例說明上面的定義偏序的特點（區別于全序），全序上的搜索可以是二分法，偏序的搜索比無序簡單，比全序復雜。這個偏序關系的定義與目標概念無關假設的一般到特殊序（3）“更一般”的嚴格情形h1=<Sunny??Strong??>h2=<Sunny?????>h3=<Sunny????Cool?>x1=<SunnyWarmHighStrongCoolSame>x2=<SunnyWarmHighLightWarmSame>h1=<Sunny??Strong??>x1=<Find-S：尋找極大特殊假設使用more_general_than偏序的搜索算法從H中最特殊假設開始，然后在假設覆蓋正例失敗時將其一般化Find-S算法將h初始化為H中最特殊假設對每個正例x對h的每個屬性約束ai如果x滿足ai那么不做任何處理否則將h中ai替換為x滿足的另一個更一般約束輸出假設hFind-S：尋找極大特殊假設使用more_general_Find-S：尋找極大特殊假設（2）Find-S算法在例子EnjoySport上的應用h<,,,,,>h<Sunny,Warm,Normal,Strong,Warm,Same>h<Sunny,Warm,?,Strong,Warm,Same>遇到反例，h不變（因為h已經能夠正確地識別反例）h<Sunny,Warm,?,Strong,?,?>Find-S：尋找極大特殊假設（2）Find-S算法在例子E機器學習算法匯總匯總課件Find-S：尋找極大特殊假設（3）Find-S算法演示了一種利用more_general_than偏序來搜索假設空間的方法，沿著偏序鏈，從較特殊的假設逐漸轉移到較一般的假設。因此，每一步得到的假設都是在那一點上與訓練樣例一致的最特殊的假設。Find-S的重要特點：對以屬性約束的合取式描述的假設空間H，保證輸出為H中與正例一致的最特殊的假設。存在的問題是否收斂到了正確的目標概念？為什么要用最特殊的假設？訓練樣例是否相互一致？如果有多個極大特殊假設怎么辦？Find-S：尋找極大特殊假設（3）Find-S算法演示了一變型空間和候選消除算法候選消除算法概說概念學習的另一種方法，候選消除算法（candidate-elimination）Find-S算法的不足，輸出的假設只是H中能夠擬合訓練樣例的多個假設中的一個候選消除算法輸出與訓練樣例一致的所有假設的集合候選消除算法在描述這一集合時不需要明確列舉所有成員利用more_general_than偏序結構，可以維護一個一致假設集合的簡潔表示候選消除算法的應用：化學質譜分析、啟發式搜索的控制規則候選消除算法的缺點：容錯性能差變型空間和候選消除算法候選消除算法概說變型空間和候選消除算法（2）“一致”的定義一個假設h與訓練樣例集合D一致，當且僅當對D中每一個樣例<x,c(x)>都有h(x)=c(x)，即Consistent(h,D)(<x,c(x)>D)h(x)=c(x)“一致”與“滿足”的關系變型空間（VersionSpace）與訓練樣例一致的所有假設組成的集合表示了目標概念的所有合理的變型關于H和D的變型空間，記為VSH,D，是H中與訓練樣例D一致的所有假設構成的子集VSH,D={hH|Consistent(h,D)}變型空間和候選消除算法（2）“一致”的定義變型空間和候選消除算法（3）列表后消除算法表示變型空間的一種方法是列出其所有成員變型空間包含H中所有假設的列表對每個訓練樣例<x,c(x)>，從變型空間中移除所有h(x)c(x)的假設輸出VersionSpace中的假設列表優點保證得到所有與訓練數據一致的假設缺點非常繁瑣地列出H中的所有假設，大多數實際的假設空間無法做到變型空間和候選消除算法（3）列表后消除算法變型空間和候選消除算法（4）變型空間的更簡潔表示變型空間被表示為它的極大一般和極大特殊的成員這些成員形成了一般和特殊邊界的集合，這些邊界在整個偏序結構中劃分出變型空間以EnjoySport為例變型空間和候選消除算法（4）變型空間的更簡潔表示機器學習算法匯總匯總課件變型空間和候選消除算法（5）形式化定義極大一般極大特殊關于假設空間H和訓練數據D的一般邊界G，是在H中與D相一致的極大一般成員的集合關于假設空間H和訓練數據D的特殊邊界S，是在H中與D相一致的極大特殊成員的集合變型空間和候選消除算法（5）形式化定義變型空間和候選消除算法（6）變型空間表示定理:令X為一任意的實例集合，H為X上定義的布爾假設的集合。令c:X{0,1}為X上定義的任一目標概念，并令D為任一訓練樣例集合{<x,c(x)>}。對所有的X,H,c,D以及良好定義的S和G：

VSH,D={hH|(sS)(gG)(gghgs)}證明：只需證明：1）每一個滿足上式右邊的h都在VSH,D中，2）VSH,D的每個成員都滿足都滿足等式右邊。…變型空間和候選消除算法（6）變型空間表示定理:令X為一任意變型空間和候選消除算法（7）候選消除算法初始化G和S如果d是一個正例從G中移去所有與d不一致的假設對S中每個與d不一致的假設s從S中移去s把s的所有的極小泛化式h加入到S中，其中h滿足h與d一致，而且G的某個成員比h更一般從S中移去所有這樣的假設：它比S中另一個假設更一般如果d是一個反例從S中移去所有與d不一致的假設對G中每個與d不一致的假設g從G中移去g把g的所有的極小特殊化式h加入到G中，其中h滿足h與d一致，而且S的某個成員比h更特殊從G中移去所有這樣的假設：它比G中另一個假設更特殊變型空間和候選消除算法（7）候選消除算法變型空間和候選消除算法（8）算法舉例{<SunnyWarmNormalStrongWarmSame>}{<SunnyWarm?StrongWarmSame>}S1:S2:{<Sunny?????><?Warm????>

<?????Same>}G3:S2S3

:{<SunnyWarm?Strong??>}S4:{<Sunny?????><?Warm????>}G4:G0G1:G0G1G2:變型空間和候選消除算法（8）算法舉例{<SunnyWarm圖2-7最終變型空間圖2-7最終變型空間變型空間和候選消除的說明候選消除算法收斂到正確的假設訓練樣例中沒有錯誤H中確實包含描述目標概念的正確假設如果樣例中存在錯誤如果給定足夠的訓練數據，我們會發現S和G邊界收斂得到一個空的變型空間如果目標概念不能由假設表示方式所描述比如是約束的析取<Sunny,?,?,?,?,?>∨<Cloudy,?,?,?,?,?>變型空間和候選消除的說明候選消除算法收斂到正確的假設變型空間和候選消除（2）下一步需要什么樣的訓練樣例一般來說，概念學習的最優查詢策略，是產生實例以滿足當前變型空間中大約半數的假設。這樣，變型空間的大小可以在遇到每個新樣例時減半，正確的目標概念就可在只用log2|VS|次實驗后得到。變型空間和候選消除（2）下一步需要什么樣的訓練樣例變型空間和候選消除（3）怎樣使用不完全學習概念雖然圖2-7的變型空間中仍包含多個假設，即目標概念還未學習到，但是仍然有可能對新樣例進行一定可信度的分類。待分類的新實例變型空間和候選消除（3）怎樣使用不完全學習概念概念的應用概念的應用概念的應用判斷是否是正例判斷是否滿足S中的每個假設判斷是否是反例判斷是否不滿足G中的每個假設概念的應用判斷是否是正例歸納偏置有關候選消除算法的幾個問題如果目標概念不在假設空間中怎么辦？是否可設計一個包含所有假設的空間來解決這一困難？假設空間的大小對于算法推廣到未見實例的能力有什么影響？假設空間的大小對所需訓練樣例的數量有什么影響？歸納偏置有關候選消除算法的幾個問題歸納偏置（2）一個有偏的假設空間在EnjoySport這個例子中，假設空間限制為只包含屬性值的合取。（有偏）這一限制，導致假設空間不能夠表示最簡單的析取形式的目標概念。歸納偏置（2）一個有偏的假設空間歸納偏置（3）無偏的學習器為了保證目標概念在假設空間中，需要提供一個假設空間，它能表達所有的可教授概念。換言之，它能表達實例集X的所有子集。問題：為什么2.3節中合取假設空間只能表示973個假設？歸納偏置（3）無偏的學習器歸納偏置（4）EnjoySport的無偏形式帶來的問題：概念學習算法無法從訓練樣例中泛化。要想獲得單個目標概念，就必須提供X中所有實例作為訓練樣例使用2.6.3節討論的部分學習的無效歸納偏置（4）EnjoySport的無偏形式歸納偏置（5）無偏學習的無用性歸納學習的一個基本屬性：學習器如果不對目標概念的形式做預先的假定，它從根本上無法對未見實例進行分類歸納學習需要的預先假定，稱為歸納偏置歸納偏置（5）無偏學習的無用性歸納偏置（6）歸納偏置的精確定義(Dcxi)L(xi,Dc)需要在Dcxi上附加怎樣的前提，以使L(xi,Dc)能夠演繹派生。L的歸納偏置定義為前提集合B，使所有的新實例滿足：

(BDcxi)├L(xi,Dc)考慮對于實例集合X的概念學習算法L。令c為X上定義的任一概念，并令Dc為c的任意訓練樣例集合，L(xi,Dc)表示經過Dc訓練后L賦予實例xi的分類。L的歸納偏置是最小斷言集合B，它使任意目標概念c和相應的訓練樣例Dc滿足： xiX[(BDcxi)├L(xi,Dc)]歸納偏置（6）歸納偏置的精確定義歸納偏置（6）候選消除算法的歸納偏置{cH}InductiveSystemsandEquivalentDeductiveSystems(歸納與演繹)歸納偏置（6）候選消除算法的歸納偏置歸納偏置（7）3個有偏程度不同的歸納學習算法機械式候選消除算法Find-S一種算法的有偏性越強，它的歸納能力越強，可以分類更多的未見實例。某些歸納偏置隱含在學習器中，有些表示為斷言集合，可由學習器操作。歸納偏置（7）3個有偏程度不同的歸納學習算法小結主要內容概念學習可看作搜索預定義潛在假設空間的過程;假設的一般到特殊偏序結構可以定義在任何概念學習問題中，這種結構便于假設空間的搜索;Find-S算法使用一般到特殊序，在偏序結構的一個分支上執行一般到特殊搜索，尋找一個與樣例一致的最特殊假設;候選消除算法利用一般到特殊序，通過漸近地計算極大特殊假設集合和極大一般假設集合發現變型空間；候選消除算法缺少健壯性，后面會描述一些學習算法，它們能夠處理有噪聲的數據和目標概念無法在假設空間中表示的情況歸納學習算法隱含了歸納偏置，候選消除算法的偏置是：目標概念可以在假設空間中找到。輸出的假設和對新實例的分類可由歸納偏置和訓練樣例演繹推出小結主要內容思考題2-1.解釋為什么EnjoySport學習任務的假設空間的大小為973。如果增加一屬性WaterCurrent，可取值Light、Moderate和Strong，那么可能的實例數和可能的假設數將會增加多少？推廣到一般，增加一新屬性A，有k種取值，實例數和假設數將會增加多少？思考題2-1.解釋為什么EnjoySport學習任務的假設空思考題2-2在候選消除算法中，如果訓練樣例按EnjoySport例子中的逆序出現，請分步給出S和G邊界集合。嘗試對訓練樣例排序，以使EnjoySport例子中的所有S和G集合的中間結果的大小之和為最小？YesChangeCoolStrongHighWarmSunny4NoChangeWarmStrongHighColdRainy3YesSameWarmStrongHighWarmSunny2YesSameWarmStrongNormalWarmSunny1EnjoySportForecastWaterWindHumidityAirTempSkyExample思考題2-2在候選消除算法中，如果訓練樣例按EnjoySp思考題2-3實現Find-S算法和候選消除算法。驗證它是否可成功地產生EnjoySport例子中各步驟結果。思考題2-3實現Find-S算法和候選消除算法。驗證它是第3章決策樹學習(Decision-TreeAlgorithm)第3章決策樹學習排名主題算法得票數發表時間作者陳述人1分類C4.5611993Quinlan,J.RHiroshiMotoda2聚類k-Means601967MacQueen,J.BJoydeepGhosh3統計學習SVM581995Vapnik,V.NQiangYang4關聯分析Apriori521994RakeshAgrawalChristosFaloutsos5統計學習EM482000McLachlan,GJoydeepGhosh6鏈接挖掘PageRank461998Brin,S.ChristosFaloutsos7集裝與推進AdaBoost451997Freund,Y.Zhi-HuaZhou8分類kNN451996Hastie,TVipinKumar9分類Na?veBayes452001Hand,D.JQiangYang10分類CART341984L.BreimanDanSteinberg共有145人參加了ICDM2006Panel(會議的專題討論),并對18種候選算法進行投票，選出了機器學習10大算法ICDM2006會議的算法投票結果排名主題算法得票數發表時間作者陳述人1分類C4.561199概論決策樹學習是應用最廣的歸納推理算法之一是一種逼近離散值函數的方法很好的健壯性能夠學習析取表達式ID3,Assistant,C4.5搜索一個完整表示的假設空間歸納偏置是優先選擇較小的樹決策樹表示了多個if-then規則概論決策樹學習是應用最廣的歸納推理算法之一提綱決策樹定義適用問題特征基本ID3算法決策樹學習的歸納偏置訓練數據的過度擬合…提綱決策樹定義決策樹基本概念關于分類問題分類（Classification）任務就是通過學習獲得一個目標函數（TargetFunction）f,將每個屬性集x映射到一個預先定義好的類標號y。分類任務的輸入數據是記錄的集合，每條記錄也稱為實例或者樣例。用元組(X,y)表示，其中，X是屬性集合，y是一個特殊的屬性，指出樣例的類標號（也稱為分類屬性或者目標屬性）決策樹基本概念關于分類問題分類（Classifica決策樹基本概念關于分類問題名稱體溫表皮覆蓋胎生水生動物飛行動物有腿冬眠類標號人類恒溫毛發是否否是否哺乳動物海龜冷血鱗片否半否是否爬行類鴿子恒溫羽毛否否是是否鳥類鯨恒溫毛發是是否否否哺乳類Xy分類與回歸分類目標屬性y是離散的，回歸目標屬性y是連續的決策樹基本概念關于分類問題名稱體溫表皮覆蓋胎生水生動物飛行動決策樹基本概念解決分類問題的一般方法

通過以上對分類問題一般方法的描述，可以看出分類問題一般包括兩個步驟：

1、模型構建（歸納）通過對訓練集合的歸納，建立分類模型。

2、預測應用（推論）根據建立的分類模型，對測試集合進行測試。決策樹基本概念解決分類問題的一般方法通過以上決策樹基本概念解決分類問題的一般方法TIDA1A2A3類1Y100LN2N125SN3Y400LY4N415MN學習算法學習模型模型應用模型TIDA1A2A3類1Y100L？2N125S？3Y400L？4N415M？訓練集（類標號已知）檢驗集（類標號未知）歸納推論決策樹基本概念解決分類問題的一般方法TIDA1A2A3類1Y決策樹表示法內部節點(包括根節點)指定了對實例的某個屬性的測試節點的每個后繼分支對應于該屬性的一個可能值葉子節點即為實例所屬的分類

決策樹代表實例屬性值約束的合取的析取式圖3-1

概念PlayTennis的決策樹OutlookHumidityWindNoYesNoYesYesSunnyRainyOvercastHighNormalStrongWeak決策樹表示法內部節點(包括根節點)指定了對實例的某個屬性的測決策樹學習的適用問題適用問題的特征實例由“屬性-值”對表示目標函數具有離散的輸出值可能需要析取的描述訓練數據可以包含錯誤訓練數據可以包含缺少屬性值的實例問題舉例醫學中的應用（如根據疾病分類患者、疾病分析與預測）根據起因分類設備故障（故障診斷）根據拖欠支付的可能性分類貸款申請分類問題核心任務是把樣例分類到各可能的離散值對應的類別決策樹學習的適用問題適用問題的特征基本的決策樹學習算法ID3大多數決策樹學習算法是一種核心算法的變體采用自頂向下的貪婪搜索遍歷可能的決策樹空間ID3是這種算法的代表該方法使用信息增益度選擇測試屬性。基本的決策樹學習算法ID3大多數決策樹學習算法是一種核心算法ID3算法通過自頂向下構造決策樹來進行學習。構造過程：ID3算法的核心問題是選取在樹的每個節點要測試的屬性。選擇根節點－使用統計測試確定每一個實例屬性單獨分類訓練樣例的能力，分類能力最好的屬性被選作樹的根節點為根節點屬性的每個可能值產生一個分支，并把訓練樣例排列到適當的分支重復上面的過程，用每個分支節點關聯的訓練樣例來選取在該點被測試的最佳屬性，直到滿足以下兩個條件中的任一個:1）所有的屬性已經被這條路徑包括；

2）與這個節點關聯的所有訓練樣例具有相同的目標屬性值ID3算法通過自頂向下構造決策樹來進行學習。構造過程：表3-1用于學習布爾函數的ID3算法ID3(Examples,Target_attribute,Attributes)創建樹的root節點如果Examples都為正,返回label=+的單節點樹root如果Examples都為反,返回label=-的單節點樹root如果Attributes為空，那么返回單節點root，label=Examples中最普遍的Target_attribute值否則開始AAttributes中分類examples能力最好的屬性root的決策屬性A對于A的每個可能值vi在root下加一個新的分支對應測試A=vi令Examplesvi為Examples中滿足A屬性值為vi的子集如果Examplesvi為空在這個新分支下加一個葉子節點，節點的label=Examples中最普遍的Target_attribute值否則在新分支下加一個子樹ID3（Examplesvi,Target_attribute,Attributes-{A}）結束返回root表3-1用于學習布爾函數的ID3算法ID3(Exampl最佳分類屬性信息增益(InformationGain)用來衡量給定的屬性區分訓練樣例的能力ID3算法在增長樹的每一步使用信息增益從候選屬性中選擇屬性用熵度量樣例的均一性給定包含關于某個目標概念的正反樣例的樣例集S，那么S相對這個布爾型分類的熵為

信息論中對熵的一種解釋，熵確定了要編碼集合S中任意成員的分類所需要的最少二進制位數更一般地，如果目標屬性具有c個不同的值，那么S相對于c個狀態的分類的熵定義為

Entropy(S)=最佳分類屬性信息增益(InformationGain)S的所有成員屬于同一類，Entropy(S)=0；S的正反樣例數量相等，Entropy(S)=1；S的正反樣例數量不等，熵介于0，1之間S的所有成員屬于同一類，Entropy(S)=0；拋一枚均勻硬幣的信息熵是多少？解：出現正面與反面的概率均為0.5，信息熵是拋一枚均勻硬幣的信息熵是多少？用信息增益度量期望的熵降低屬性的信息增益，由于使用這個屬性分割樣例而導致的期望熵降低一個屬性A相對樣例集合S的信息增益Gain(S,A)被定義為：

Values(A)是屬性A所有可能值的集合，Sv是S中屬性A的值為v的子集Gain(S,A)是在知道屬性A的值后可以節省的二進制位數；用信息增益度量期望的熵降低<big,red,circle>:+<small,red,circle>:+<small,red,square>:<big,blue,circle>:2+,2:E=1sizebigsmall1+,11+,1E=1E=1Gain=1(0.51+0.51)=02+,2:E=1colorredblue2+,10+,1E=0.918E=0Gain=1(0.750.918+0.250)=0.3112+,2

:E=1shapecirclesquare2+,10+,1E=0.918E=0Gain=1(0.750.918+0.250)=0.311計算屬性的信息增益<big,red,circle>:+DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainyMildHighWeakYesD5RainyCoolNormalWeakYesD6RainyCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainyMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainyMildHighStrongNo表3-2目標概念PlayTennis的訓練樣例DayOutlookTemperatureHumidityWHumidityS：[9+,5-]E(S)=0.940HighNormal[3+,4-]E=0.985[6+,1-]E=0.592Gain(S,Humidity)=0.940-(7/14)*0.985-(7/14)*0.592=0.151WindS：[9+,5-]E(S)=0.940WeakStrong[6+,2-]E=0.811[3+,3-]E=1Gain(S,Wind)=0.940-(8/14)*0.811-(6/14)*1=0.048計算屬性的信息增益HumidityS：[9+,5-]HighNormal[3+110考慮表3-2的訓練數據所代表的學習任務。創建決策樹的根節點。計算每一個候選屬性的信息增益，然后選擇信息增益最高的一個。

Gain（S，Outlook）＝0.246

Gain（S，Humidity）＝0.151Gain（S，Wind）＝0.048Gain（S，Temperature）＝0.029

根據信息增益標準，屬性Outlook被選作根節點的決策屬性，并為它的每一個可能值（Sunny、Overcast和Rainy）在根節點下創建分支，得到部分決策樹顯示在圖3-4中。對非終端的后繼節點再重復前面的過程以選擇一個新的屬性來分割訓練樣例，這一次僅使用與這個節點關聯的訓練樣例，直到滿足結束條件。ID3算法示例110考慮表3-2的訓練數據所代表的學習任務。創建決策樹的根DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainyMildHighWeakYesD5RainyCoolNormalWeakYesD6RainyCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainyMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainyMildHighStrongNo表3-2目標概念PlayTennis的訓練樣例DayOutlookTemperatureHumidityW112ID3算法步驟1OutlookSunnyRainyOvercast[D1,D2,…,D14][9+,5-][D1,D2,D8,D9,D11][2+,3-][D3,D7,D12,D13][4+,0-][D4,D5,D6,D10,D14][3+,2-]Gain(S,Outlook)=0.246Gain(S,Humidity)=0.151Gain(S,Wind)=0.048Gain(S,Temperature)=0.029112ID3算法步驟1OutlookSunnyRainyOvOutlook??YesSunnyOvercastRainD1,2,8,9,11D3,7,12,13D4,5,6,11,14D1~14[9+,5-][2+,3-][4+,0-][3+,2-]什么屬性？ID3算法第一步后形成的部分決策樹Outlook??YesSunnyOvercastRainD114ID3算法步驟2HumidityWindHighNormal[D1,D2,D8][0+,3-][D9,D11][2+,0-]StrongWeak[D6,D14][0+,2-][D4,D4,D10][3+,0-]NoYesNoYesYesOutlookSunnyRainyOvercast[D1,D2,…,D14][9+,5-][D1,D2,D8,D9,D11][2+,3-][D3,D7,D12,D13][4+,0-][D4,D5,D6,D10,D14][3+,2-]Gain(SSunny,Humidity)=0.970Gain(SSunny,Temperature)=0.570Gain(SSunny,Wind)=0.019Gain(SRain,Humidity)=0.019Gain(SRain,Temperature)=0.019Gain(SRain,Wind)=0.970114ID3算法步驟2HumidityWindHighNor115決策樹學習中的假設空間搜索ID3算法搜索的假設空間就是可能的決策樹的集合。ID3以爬山算法遍歷這個假設空間，引導這種爬山搜索的評估函數是信息增益度量。觀察ID3的搜索空間和搜索策略，認識到這個算法的優勢和不足：假設空間包含所有的決策樹，它是關于現有屬性的有限離散值函數的一個完整空間維護單一的當前假設（不同于上章變型空間候選消除算法），不能判斷有多少個其他的決策樹也與現有的訓練數據一致不進行回溯，可能收斂到局部最優每一步都使用當前所有的訓練樣例，不同于基于單獨的訓練樣例遞增作出決定，容錯性增強115決策樹學習中的假設空間搜索ID3算法搜索的假設空間就是決策樹學習的歸納偏置ID3的搜索策略優先選擇較短的樹選擇那些信息增益高的屬性離根節點較近的樹很難準確刻畫ID3的歸納偏置近似的ID3的歸納偏置較短的樹比較長的樹優先近似在于ID3得到局部最優，而不一定是全局最優一個精確具有這個歸納偏置的算法，BFS-ID3更貼切近似的歸納偏置較短的樹比較長的樹優先，信息增益高的屬性更靠近根節點的樹優先決策樹學習的歸納偏置ID3的搜索策略限定偏置和優選偏置ID3和候選消除算法的比較ID3的搜索范圍是一個完整的假設空間，但不徹底地搜索這個空間候選消除算法的搜索范圍是不完整的假設空間，但徹底地搜索這個空間ID3的歸納偏置完全是搜索策略排序假設的結果，來自搜索策略候選消除算法完全是假設表示的表達能力的結果，來自對搜索空間的定義限定偏置和優選偏置ID3和候選消除算法的比較限定偏置和優選偏置優選偏置（搜索偏置）ID3的歸納偏置是對某種假設勝過其他假設的一種優選，對最終可列舉的假設沒有硬性限制限定偏置（語言偏置）候選消除算法的偏置是對待考慮假設的一種限定通常優選偏置比限定偏置更符合歸納學習的需要優選偏置和限定偏置的結合考慮第1章下棋的例子（優選偏置和限定偏置）限定偏置和優選偏置優選偏置（搜索偏置）為什么短的假設優先?ID3的歸納偏置的哲學基礎奧坎姆剃刀優先選擇擬合數據的最簡單的假設科學上的例子物理學家優先選擇行星運動的簡單假設；簡單假設的數量遠比復雜假設的數量少；簡單假設對訓練樣例的針對性更小，更像是泛化的規律，而不是訓練樣例的另一種描述。為什么短的假設優先?ID3的歸納偏置的哲學基礎奧坎姆剃刀設想你是在一條積雪的街上行走。在你前面有一個人帶著一頂黑色的高筒禮帽。街對面站著一群男孩，覺得這頂禮帽是個很好的目標，其中一個扔雪球一下擊中了帽子。讓我們舉出兩種解釋來說明這頂帽子的隨后遭遇。第一，在帽子受擊的一剎那，一隊天使疾飛而下，出其不意地把帽子從那人頭上揭走了。第二，雪球把帽子擊落了。我們將選擇？？種解釋。這就是科學上普遍適用的所謂“節儉律”的簡單說明。這條定律的意義，就在于說明，最可能的解釋就是最好的解釋，有時這條定律又被稱為奧坎姆剃刀

奧坎姆剃刀設想你是在一條積雪的街上行走。在你前面有一個人帶著為什么短的假設優先奧坎姆剃刀的困難可以定義很多小的假設集合，根據什么相信有短描述的決策樹組成的小假設集合比其他可定義的小假設集合更適當？假設的規模由學習器內部使用的特定表示決定從生物進化的觀點看內部表示和奧坎姆剃刀原則為什么短的假設優先奧坎姆剃刀的困難決策樹學習的常見問題決策樹學習的實際問題確定決策樹增長的深度處理連續值的屬性選擇一個適當的屬性篩選度量標準處理屬性值不完整的訓練數據處理不同代價的屬性提高計算效率針對這些問題，ID3被擴展成C4.5決策樹學習的常見問題決策樹學習的實際問題避免過度擬合數據過度擬合對于一個假設，當存在其它的假設對訓練樣例的擬合比它差，但事實上在實例的整個分布上表現得卻更好時，我們說這個假設過度擬合訓練樣例。定義：給定一個假設空間H，一個假設hH，如果存在其它的假設h’H，使得在訓練樣例上h的錯誤率比h’小，但在整個實例分布上h’的錯誤率比h小，那么就說假設h過度擬合訓練數據。樹的規模accuracyontrainingdataontestdata避免過度擬合數據過度擬合樹的規模accuracyontra避免過度擬合數據（2）導致過度擬合的原因（1）一種可能原因是訓練樣例含有隨機錯誤或噪聲SunnyHotNormalStrongPlayTennis＝No避免過度擬合數據（2）導致過度擬合的原因（1）SunnyH避免過度擬合數據（3）導致過度擬合的原因（2）當訓練數據沒有噪聲時，過度擬合也有可能發生，特別是當少量的樣例被關聯到葉子節點時，很可能出現巧合的規律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實際的目標函數并無關系。過度擬合使決策樹的精度降低（10～25）％避免過度擬合數據（3）導致過度擬合的原因（2）避免過度擬合數據（4）避免過度擬合的方法及早停止樹增長后修剪法兩種方法的特點第一種方法更直觀第一種方法中，精確地估計何時停止樹增長很困難第二種方法被證明在實踐中更成功避免過度擬合數據（4）避免過度擬合的方法避免過度擬合數據（5）避免過度擬合的關鍵使用什么樣的準則來確定最終正確樹的規模解決方法使用與訓練樣例截然不同的一套分離的樣例，來評估通過后修剪方法從樹上修剪節點的效用。使用所有可用數據進行訓練，但進行統計測試來估計擴展（或修剪）一個特定的節點是否有可能改善在訓練集合外的實例上的性能。使用一個明確的標準來衡量訓練樣例和決策樹的復雜度，當這個編碼的長度最小時停止樹增長。避免過度擬合數據（5）避免過度擬合的關鍵避免過度擬合數據（6）方法評述第一種方法是最普通的，常被稱為訓練和驗證集法。可用數據分成兩個樣例集合：訓練集合，形成學習到的假設驗證集合，評估這個假設在后續數據上的精度方法的動機：即使學習器可能會被訓練集合誤導，但驗證集合不大可能表現出同樣的隨機波動驗證集合應該足夠大，以便它本身可提供具有統計意義的實例樣本。常見的做法是，樣例的三分之二作訓練集合，三分之一作驗證集合。避免過度擬合數據（6）方法評述錯誤率降低修剪將樹上的每一個節點作為修剪的候選對象修剪步驟刪除以此節點為根的子樹，使它成為葉結點把和該節點關聯的訓練樣例的最常見分類賦給它反復修剪節點，每次總是選取那些刪除后可以最大提高決策樹在驗證集合上的精度的節點繼續修剪，直到進一步的修剪是有害的為止數據分成3個子集訓練樣例，形成決策樹驗證樣例，修剪決策樹測試樣例，精度的無偏估計如果有大量的數據可供使用，那么使用分離的數據集合來引導修剪錯誤率降低修剪將樹上的每一個節點作為修剪的候選對象決策樹學習中錯誤率降低的修剪效果決策樹學習中錯誤率降低的修剪效果規則后修剪從訓練集合推導出決策樹，增長決策樹直到盡可能好地擬合訓練數據，允許過度擬合發生將決策樹轉化為等價的規則集合，方法是為從根節點到葉節點的每一條路徑創建一條規則通過刪除不會導致估計精度降低的前件來修剪每一條規則按照修剪過的規則的估計精度對它們進行排序，并按這樣的順序應用這些規則來分類后來的實例規則后修剪從訓練集合推導出決策樹，增長決策樹直到盡可能好地擬規則后修剪（2）例子if(outlook=sunny)(Humidity=High)thenPlayTennis=Noif(outlook=sunny)(Humidity=Normal)thenPlayTennis=Yes…考慮刪除先行詞(outlook=sunny)或(Humidity=High)選擇使估計精度有最大提升的步驟考慮修剪第二個前件作為進一步的修剪步驟規則后修剪（2）例子規則后修剪（3）規則精度估計方法使用與訓練集不相交的驗證集基于訓練集合本身被C4.5使用，使用一種保守估計來彌補訓練數據有利于當前規則的估計偏置過程先計算規則在它應用的訓練樣例上的精度然后假定此估計精度為二項式分布，并計算它的標準差對于一個給定的置信區間，采用下界估計作為規則性能的度量評論對于大的數據集，保守預測非常接近觀察精度，隨著數據集合的減小，離觀察精度越來越遠不是統計有效（此概念第5章介紹），但是實踐中發現有效規則后修剪（3）規則精度估計方法規則后修剪（4）把決策樹轉化成規則集的好處可以區分決策節點使用的不同上下文消除了根節點附近的屬性測試和葉節點附近的屬性測試的區別提高了可讀性規則后修剪（4）把決策樹轉化成規則集的好處合并連續值屬性ID3被限制為取離散值的屬性學習到的決策樹要預測的目標屬性必須是離散的樹的決策節點的屬性也必須是離散的簡單刪除上面第2個限制的方法通過動態地定義新的離散值屬性來實現，即先把連續值屬性的值域分割為離散的區間集合合并連續值屬性ID3被限制為取離散值的屬性合并連續值屬性（2）例子，Temperature應該定義什么樣的基于閾值的布爾屬性選擇產生最大信息增益的閾值按照連續屬性排列樣例，確定目標分類不同的相鄰實例產生一組候選閾值，它們的值是相應的A值之間的中間值可以證明產生最大信息增益的c值位于這樣的邊界中（Fayyad1991）通過計算與每個候選閾值關聯的信息增益評估這些候選值方法的擴展連續的屬性分割成多個區間，而不是單一閾值的兩個空間合并連續值屬性（2）例子，屬性選擇的其它度量標準信息增益度量存在一個內在偏置，偏向具有較多值的屬性避免方法，其它度量，比如增益比率增益比率通過加入一個被稱作分裂信息的項來懲罰多值屬性，分裂信息用來衡量屬性分裂數據的廣度和均勻性

SplitInformation(S,A)=

GainRatio(S,A)=分裂信息項阻礙選擇值為均勻分布的屬性問題，當某個SiS。解決方法：采用一些啟發式規則，比如僅對增益高過平均值的屬性應用增益比率測試屬性選擇的其它度量標準信息增益度量存在一個內在偏置，偏向具有屬性選擇的其它度量標準（2）基于距離的度量定義了數據劃分間的一種距離尺度計算每個屬性產生的劃分與理想劃分間的距離選擇最接近完美劃分的屬性LopezdeMantaras定義了這個距離度量，證明了它不偏向有大量值的屬性此外Mingers實驗，不同的屬性選擇度量對最終精度的影響小于后修剪的程度和方法的影響屬性選擇的其它度量標準（2）基于距離的度量缺少屬性值的訓練樣例例子，醫學領域經常需要根據此屬性值已知的實例來估計這個缺少的屬性值為了評估屬性A是否是決策節點n的最佳測試屬性，要計算決策樹在該節點的信息增益Gain(S,A)。假定<x,c(x)>是S中的一個訓練樣例，并且其