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

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

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

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

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

一些網(wǎng)絡(luò)資源(2)一些網(wǎng)絡(luò)資源(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/一些網(wǎng)絡(luò)資源(3)Weka：DataMining(ML)一些網(wǎng)絡(luò)資源(4)KernalMachines://software/:MachineLearningOpenSourceSoftware.sg/home/aswduch/ai-ml.html

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

ghk假設(shè)的一般到特殊序（2）關(guān)系“更一般”的精確定義假設(shè)的一般到特殊序（3）“更一般”的嚴(yán)格情形hj>ghk，當(dāng)且僅當(dāng)，(hj

ghk)(hk

ghj)“更特殊”關(guān)系的定義hj

ghk，當(dāng)且僅當(dāng)，hk

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

VSH,D={hH|(sS)(gG)(gghgs)}證明：只需證明：1）每一個(gè)滿足上式右邊的h都在VSH,D中，2）VSH,D的每個(gè)成員都滿足都滿足等式右邊。…變型空間和候選消除算法（6）變型空間表示定理:令X為一任意變型空間和候選消除算法（7）候選消除算法初始化G和S如果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中另一個(gè)假設(shè)更一般如果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中另一個(gè)假設(shè)更特殊變型空間和候選消除算法（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最終變型空間變型空間和候選消除的說(shuō)明候選消除算法收斂到正確的假設(shè)訓(xùn)練樣例中沒(méi)有錯(cuò)誤H中確實(shí)包含描述目標(biāo)概念的正確假設(shè)如果樣例中存在錯(cuò)誤如果給定足夠的訓(xùn)練數(shù)據(jù)，我們會(huì)發(fā)現(xiàn)S和G邊界收斂得到一個(gè)空的變型空間如果目標(biāo)概念不能由假設(shè)表示方式所描述比如是約束的析取<Sunny,?,?,?,?,?>∨<Cloudy,?,?,?,?,?>變型空間和候選消除的說(shuō)明候選消除算法收斂到正確的假設(shè)變型空間和候選消除（2）下一步需要什么樣的訓(xùn)練樣例一般來(lái)說(shuō)，概念學(xué)習(xí)的最優(yōu)查詢策略，是產(chǎn)生實(shí)例以滿足當(dāng)前變型空間中大約半數(shù)的假設(shè)。這樣，變型空間的大小可以在遇到每個(gè)新樣例時(shí)減半，正確的目標(biāo)概念就可在只用log2|VS|次實(shí)驗(yàn)后得到。變型空間和候選消除（2）下一步需要什么樣的訓(xùn)練樣例變型空間和候選消除（3）怎樣使用不完全學(xué)習(xí)概念雖然圖2-7的變型空間中仍包含多個(gè)假設(shè)，即目標(biāo)概念還未學(xué)習(xí)到，但是仍然有可能對(duì)新樣例進(jìn)行一定可信度的分類。待分類的新實(shí)例變型空間和候選消除（3）怎樣使用不完全學(xué)習(xí)概念概念的應(yīng)用概念的應(yīng)用概念的應(yīng)用判斷是否是正例判斷是否滿足S中的每個(gè)假設(shè)判斷是否是反例判斷是否不滿足G中的每個(gè)假設(shè)概念的應(yīng)用判斷是否是正例歸納偏置有關(guān)候選消除算法的幾個(gè)問(wèn)題如果目標(biāo)概念不在假設(shè)空間中怎么辦？是否可設(shè)計(jì)一個(gè)包含所有假設(shè)的空間來(lái)解決這一困難？假設(shè)空間的大小對(duì)于算法推廣到未見(jiàn)實(shí)例的能力有什么影響？假設(shè)空間的大小對(duì)所需訓(xùn)練樣例的數(shù)量有什么影響？歸納偏置有關(guān)候選消除算法的幾個(gè)問(wèn)題歸納偏置（2）一個(gè)有偏的假設(shè)空間在EnjoySport這個(gè)例子中，假設(shè)空間限制為只包含屬性值的合取。（有偏）這一限制，導(dǎo)致假設(shè)空間不能夠表示最簡(jiǎn)單的析取形式的目標(biāo)概念。歸納偏置（2）一個(gè)有偏的假設(shè)空間歸納偏置（3）無(wú)偏的學(xué)習(xí)器為了保證目標(biāo)概念在假設(shè)空間中，需要提供一個(gè)假設(shè)空間，它能表達(dá)所有的可教授概念。換言之，它能表達(dá)實(shí)例集X的所有子集。問(wèn)題：為什么2.3節(jié)中合取假設(shè)空間只能表示973個(gè)假設(shè)？歸納偏置（3）無(wú)偏的學(xué)習(xí)器歸納偏置（4）EnjoySport的無(wú)偏形式帶來(lái)的問(wèn)題：概念學(xué)習(xí)算法無(wú)法從訓(xùn)練樣例中泛化。要想獲得單個(gè)目標(biāo)概念，就必須提供X中所有實(shí)例作為訓(xùn)練樣例使用2.6.3節(jié)討論的部分學(xué)習(xí)的無(wú)效歸納偏置（4）EnjoySport的無(wú)偏形式歸納偏置（5）無(wú)偏學(xué)習(xí)的無(wú)用性歸納學(xué)習(xí)的一個(gè)基本屬性：學(xué)習(xí)器如果不對(duì)目標(biāo)概念的形式做預(yù)先的假定，它從根本上無(wú)法對(duì)未見(jiàn)實(shí)例進(jìn)行分類歸納學(xué)習(xí)需要的預(yù)先假定，稱為歸納偏置歸納偏置（5）無(wú)偏學(xué)習(xí)的無(wú)用性歸納偏置（6）歸納偏置的精確定義(Dcxi)L(xi,Dc)需要在Dcxi上附加怎樣的前提，以使L(xi,Dc)能夠演繹派生。L的歸納偏置定義為前提集合B，使所有的新實(shí)例滿足：

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

通過(guò)以上對(duì)分類問(wèn)題一般方法的描述，可以看出分類問(wèn)題一般包括兩個(gè)步驟：

1、模型構(gòu)建（歸納）通過(guò)對(duì)訓(xùn)練集合的歸納，建立分類模型。

2、預(yù)測(cè)應(yīng)用（推論）根據(jù)建立的分類模型，對(duì)測(cè)試集合進(jìn)行測(cè)試。決策樹(shù)基本概念解決分類問(wèn)題的一般方法通過(guò)以上決策樹(shù)基本概念解決分類問(wèn)題的一般方法TIDA1A2A3類1Y100LN2N125SN3Y400LY4N415MN學(xué)習(xí)算法學(xué)習(xí)模型模型應(yīng)用模型TIDA1A2A3類1Y100L？2N125S？3Y400L？4N415M？訓(xùn)練集（類標(biāo)號(hào)已知）檢驗(yàn)集（類標(biāo)號(hào)未知）歸納推論決策樹(shù)基本概念解決分類問(wèn)題的一般方法TIDA1A2A3類1Y決策樹(shù)表示法內(nèi)部節(jié)點(diǎn)(包括根節(jié)點(diǎn))指定了對(duì)實(shí)例的某個(gè)屬性的測(cè)試節(jié)點(diǎn)的每個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值葉子節(jié)點(diǎn)即為實(shí)例所屬的分類

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

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

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

信息論中對(duì)熵的一種解釋，熵確定了要編碼集合S中任意成員的分類所需要的最少二進(jìn)制位數(shù)更一般地，如果目標(biāo)屬性具有c個(gè)不同的值，那么S相對(duì)于c個(gè)狀態(tài)的分類的熵定義為

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

Values(A)是屬性A所有可能值的集合，Sv是S中屬性A的值為v的子集Gain(S,A)是在知道屬性A的值后可以節(jié)省的二進(jìn)制位數(shù)；用信息增益度量期望的熵降低<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計(jì)算屬性的信息增益<big,red,circle>:+DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainyMildHighWeakYesD5RainyCoolNormalWeakYesD6RainyCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainyMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainyMildHighStrongNo表3-2目標(biāo)概念PlayTennis的訓(xùn)練樣例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計(jì)算屬性的信息增益HumidityS：[9+,5-]HighNormal[3+110考慮表3-2的訓(xùn)練數(shù)據(jù)所代表的學(xué)習(xí)任務(wù)。創(chuàng)建決策樹(shù)的根節(jié)點(diǎn)。計(jì)算每一個(gè)候選屬性的信息增益，然后選擇信息增益最高的一個(gè)。

Gain（S，Outlook）＝0.246

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

根據(jù)信息增益標(biāo)準(zhǔn)，屬性O(shè)utlook被選作根節(jié)點(diǎn)的決策屬性，并為它的每一個(gè)可能值（Sunny、Overcast和Rainy）在根節(jié)點(diǎn)下創(chuàng)建分支，得到部分決策樹(shù)顯示在圖3-4中。對(duì)非終端的后繼節(jié)點(diǎn)再重復(fù)前面的過(guò)程以選擇一個(gè)新的屬性來(lái)分割訓(xùn)練樣例，這一次僅使用與這個(gè)節(jié)點(diǎn)關(guān)聯(lián)的訓(xùn)練樣例，直到滿足結(jié)束條件。ID3算法示例110考慮表3-2的訓(xùn)練數(shù)據(jù)所代表的學(xué)習(xí)任務(wù)。創(chuàng)建決策樹(shù)的根DayOutlookTemperatureHumidityWindPlayTennisD1SunnyHotHighWeakNoD2SunnyHotHighStrongNoD3OvercastHotHighWeakYesD4RainyMildHighWeakYesD5RainyCoolNormalWeakYesD6RainyCoolNormalStrongNoD7OvercastCoolNormalStrongYesD8SunnyMildHighWeakNoD9SunnyCoolNormalWeakYesD10RainyMildNormalWeakYesD11SunnyMildNormalStrongYesD12OvercastMildHighStrongYesD13OvercastHotNormalWeakYesD14RainyMildHighStrongNo表3-2目標(biāo)概念PlayTennis的訓(xùn)練樣例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算法第一步后形成的部分決策樹(shù)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決策樹(shù)學(xué)習(xí)中的假設(shè)空間搜索ID3算法搜索的假設(shè)空間就是可能的決策樹(shù)的集合。ID3以爬山算法遍歷這個(gè)假設(shè)空間，引導(dǎo)這種爬山搜索的評(píng)估函數(shù)是信息增益度量。觀察ID3的搜索空間和搜索策略，認(rèn)識(shí)到這個(gè)算法的優(yōu)勢(shì)和不足：假設(shè)空間包含所有的決策樹(shù)，它是關(guān)于現(xiàn)有屬性的有限離散值函數(shù)的一個(gè)完整空間維護(hù)單一的當(dāng)前假設(shè)（不同于上章變型空間候選消除算法），不能判斷有多少個(gè)其他的決策樹(shù)也與現(xiàn)有的訓(xùn)練數(shù)據(jù)一致不進(jìn)行回溯，可能收斂到局部最優(yōu)每一步都使用當(dāng)前所有的訓(xùn)練樣例，不同于基于單獨(dú)的訓(xùn)練樣例遞增作出決定，容錯(cuò)性增強(qiáng)115決策樹(shù)學(xué)習(xí)中的假設(shè)空間搜索ID3算法搜索的假設(shè)空間就是決策樹(shù)學(xué)習(xí)的歸納偏置ID3的搜索策略優(yōu)先選擇較短的樹(shù)選擇那些信息增益高的屬性離根節(jié)點(diǎn)較近的樹(shù)很難準(zhǔn)確刻畫(huà)ID3的歸納偏置近似的ID3的歸納偏置較短的樹(shù)比較長(zhǎng)的樹(shù)優(yōu)先近似在于ID3得到局部最優(yōu)，而不一定是全局最優(yōu)一個(gè)精確具有這個(gè)歸納偏置的算法，BFS-ID3更貼切近似的歸納偏置較短的樹(shù)比較長(zhǎng)的樹(shù)優(yōu)先，信息增益高的屬性更靠近根節(jié)點(diǎn)的樹(shù)優(yōu)先決策樹(shù)學(xué)習(xí)的歸納偏置ID3的搜索策略限定偏置和優(yōu)選偏置ID3和候選消除算法的比較ID3的搜索范圍是一個(gè)完整的假設(shè)空間，但不徹底地搜索這個(gè)空間候選消除算法的搜索范圍是不完整的假設(shè)空間，但徹底地搜索這個(gè)空間ID3的歸納偏置完全是搜索策略排序假設(shè)的結(jié)果，來(lái)自搜索策略候選消除算法完全是假設(shè)表示的表達(dá)能力的結(jié)果，來(lái)自對(duì)搜索空間的定義限定偏置和優(yōu)選偏置ID3和候選消除算法的比較限定偏置和優(yōu)選偏置優(yōu)選偏置（搜索偏置）ID3的歸納偏置是對(duì)某種假設(shè)勝過(guò)其他假設(shè)的一種優(yōu)選，對(duì)最終可列舉的假設(shè)沒(méi)有硬性限制限定偏置（語(yǔ)言偏置）候選消除算法的偏置是對(duì)待考慮假設(shè)的一種限定通常優(yōu)選偏置比限定偏置更符合歸納學(xué)習(xí)的需要優(yōu)選偏置和限定偏置的結(jié)合考慮第1章下棋的例子（優(yōu)選偏置和限定偏置）限定偏置和優(yōu)選偏置優(yōu)選偏置（搜索偏置）為什么短的假設(shè)優(yōu)先?ID3的歸納偏置的哲學(xué)基礎(chǔ)奧坎姆剃刀優(yōu)先選擇擬合數(shù)據(jù)的最簡(jiǎn)單的假設(shè)科學(xué)上的例子物理學(xué)家優(yōu)先選擇行星運(yùn)動(dòng)的簡(jiǎn)單假設(shè)；簡(jiǎn)單假設(shè)的數(shù)量遠(yuǎn)比復(fù)雜假設(shè)的數(shù)量少；簡(jiǎn)單假設(shè)對(duì)訓(xùn)練樣例的針對(duì)性更小，更像是泛化的規(guī)律，而不是訓(xùn)練樣例的另一種描述。為什么短的假設(shè)優(yōu)先?ID3的歸納偏置的哲學(xué)基礎(chǔ)奧坎姆剃刀設(shè)想你是在一條積雪的街上行走。在你前面有一個(gè)人帶著一頂黑色的高筒禮帽。街對(duì)面站著一群男孩，覺(jué)得這頂禮帽是個(gè)很好的目標(biāo)，其中一個(gè)扔雪球一下?lián)糁辛嗣弊印Ｗ屛覀兣e出兩種解釋來(lái)說(shuō)明這頂帽子的隨后遭遇。第一，在帽子受擊的一剎那，一隊(duì)天使疾飛而下，出其不意地把帽子從那人頭上揭走了。第二，雪球把帽子擊落了。我們將選擇？？種解釋。這就是科學(xué)上普遍適用的所謂“節(jié)儉律”的簡(jiǎn)單說(shuō)明。這條定律的意義，就在于說(shuō)明，最可能的解釋就是最好的解釋，有時(shí)這條定律又被稱為奧坎姆剃刀

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

SplitInformation(S,A)=

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