機器學習算法與實踐 課件全套 郭羽含 第1-12章 機器學習概述-神經(jīng)網(wǎng)絡

第一章機器學習概述機器學習（MachineLearning，ML）是一門多領域交叉學科，涉及概率論、統(tǒng)計學、逼近論、凸分析、算法復雜度理論等多門學科，專門研究計算機怎樣模擬或實現(xiàn)人類的學習行為，以獲取新的知識或技能，使之不斷改善自身的性能。機器學習發(fā)展極迅速，目前已經(jīng)成為一個廣袤的學科。1.1人工智能與機器學習

人工智能（artificialintelligence，AI）泛指讓機器具有人的智力的技術。人工智能是一個寬泛的技術領域，包括自然語言理解、計算機視覺、機器人、邏輯和規(guī)劃等，它可以被看作計算機專業(yè)的子領域。1.2機器學習的概念

機器學習的一個主要目的就是把人類思考和歸納經(jīng)驗的過程轉化為計算機對數(shù)據(jù)的處理，計算得出模型的過程。經(jīng)過計算得出的模型能夠以近似于人的方式解決更為復雜的問題。簡單地理解，機器學習就是指計算機通過觀察環(huán)境，與環(huán)境交互，在吸取信息中學習、自我更新和進步。機器學習算法是一種能夠從數(shù)據(jù)中學習的算法。關于其中“學習”的定義，參照TomMitchell在1997年出版的MachineLearning一書中提供的定義：“對于某類任務T和性能度量P，一個計算機程序被認為可以從經(jīng)驗E中學習是指，通過經(jīng)驗E改進后，它在任務T上由性能度量P衡量的性能有所提升?！?.2.1機器學習的定義

20世紀初至60年代初期的萌芽期20世紀60年代至80年代的摸索期20世紀90年代到目前的崛起期1.2.2機器學習的發(fā)展從學習方式上（1）監(jiān)督學習（SupervisedLearning）（2）無監(jiān)督學習（UnsuperisedLearning）（3）半監(jiān)督學習（Semi-supervisedLearning）（4）強化學習（ReinforcementLearning）1.2.3機器學習的分類從算法功能上（1）分類（Classification）（2）回歸（Regression）（3）聚類（Cluster）（4）降維（Dimensionalityreduction）1.2.3機器學習的分類1.3機器學習工具Python語言第三方工具庫編譯環(huán)境庫的下載與安裝1.3.1Python語言Python是一種開源的、解釋型、面向對象的編程語言。Python的特點如下：簡單易學解釋型語言面向對象免費和開源跨平臺和可移植性豐富的標準庫可擴展性和可嵌入性1.3.2第三方工具庫Python語言除了自身具備的優(yōu)點外，還具有大量優(yōu)秀的第三方函數(shù)模塊，對學科交叉應用非常有幫助。（1）操作系統(tǒng)管理與維護（2）科學計算與數(shù)據(jù)可視化（3）圖形用戶界面（GUI）開發(fā)（4）文本處理（5）網(wǎng)絡編程及Web開發(fā)（6）數(shù)據(jù)庫編程（7）游戲開發(fā)1.3.3編譯環(huán)境Python是跨平臺的，可以運行在Windows、Mac和Linux/Unix等操作系統(tǒng)上Python的下載與安裝（/downloads/windows/）1.3.3編譯環(huán)境（1）定制安裝Python（2）Python選定特性設置1.3.3編譯環(huán)境（3）Python高級選項設置（4）Python安裝進行中1.3.3編譯環(huán)境（5）Python成功安裝（6）Python3.11程序組1.3.3編譯環(huán)境系統(tǒng)環(huán)境變量的設置（1）安裝時直接添加安裝Python系統(tǒng)時選中“AddPython.exetoPATH”復選框，則系統(tǒng)自動將安裝路徑添加到環(huán)境變量Path中。（2）安裝后手動添加如果安裝時未選中“AddPython.exetoPATH”復選框，則可在安裝完成后手動添加。（操作過程如圖1-10所示）。1.3.3編譯環(huán)境Python運行（1）選擇“Python3.11（64-bit）”啟動Python解釋器1.3.3編譯環(huán)境Python運行（2）選擇“IDLE（Python3.1164-bit）”啟動Python集成開發(fā)環(huán)境IDLE1.3.4庫的下載與安裝1.

NumPyNumPy（NumerialPython的簡稱）是Python科學計算的基礎包。它提供了以下功能（不限于此）：快速高效的多維數(shù)組對象ndarray。用于對數(shù)組執(zhí)行元素級計算以及直接對數(shù)組執(zhí)行數(shù)學運算的函數(shù)。?于讀寫硬盤上基于數(shù)組的數(shù)據(jù)集的工具。線性代數(shù)運算、傅里葉變換，以及隨機數(shù)生成。1.3.4庫的下載與安裝2.PandasPandas提供了快速便捷處理結構化數(shù)據(jù)的大量數(shù)據(jù)結構和函數(shù)。Pandas兼具NumPy高性能的數(shù)組計算功能以及電子表格和關系型數(shù)據(jù)庫（如SQL）靈活的數(shù)據(jù)處理功能。它提供了復雜精細的索引功能，以便更為便捷地完成重塑、切片和切塊、聚合以及選取數(shù)據(jù)子集等操作。1.3.4庫的下載與安裝3.MatplotlibMatplotlib是最流行的用于繪制圖表和其它二維數(shù)據(jù)可視化的Python庫。它非常適合創(chuàng)建出版物上用的圖表。雖然還有其它的Python可視化庫，Matplotlib卻是使用最廣泛的，并且它和其它生態(tài)工具配合也非常完美。Matplotlib的安裝并沒有什么特別之處，可以通過“pipinstallmatplotlib”命令安裝或者自行下載源代碼安裝。1.3.4庫的下載與安裝4.SciPySciPy是一組專?解決科學計算中各種標準問題域的包的集合，主要包括下面這些包：egrate：數(shù)值積分例程和微分方程求解器。scipy.linalg：擴展了由numpy.linalg提供的線性代數(shù)例程和矩陣分解功能。scipy.optimize：函數(shù)優(yōu)化器（最小化器）以及根查找算法。scipy.signal：信號處理工具。scipy.sparse：稀疏矩陣和稀疏線性系統(tǒng)求解器。scipy.special：SPECFUN（這是一個實現(xiàn)了許多常用數(shù)學函數(shù)（如伽瑪函數(shù)）的Fortran庫）的包裝器。scipy.stats：標準連續(xù)和離散概率分布（如密度函數(shù)、采樣器、連續(xù)分布函數(shù)等）、各種統(tǒng)計檢驗方法，以及更好的描述統(tǒng)計法。1.3.4庫的下載與安裝5.Scikit-learn它的子模塊包括:分類：SVM、近鄰、隨機森林、邏輯回歸等等?；貧w：Lasso、嶺回歸等等。聚類：k-均值、譜聚類等等。降維：PCA、特征選擇、矩陣分解等等。選型：網(wǎng)格搜索、交叉驗證、度量。預處理：特征提取、標準化。1.4機器學習示例自動駕駛機器翻譯游戲中的人工智能1.4.1自動駕駛“自動駕駛”這個詞最早來自于飛機、列車、航運領域的輔助駕駛系統(tǒng)。它的廣義定義為：自動駕駛是無須人工的持續(xù)干預下，用于自動控制交通工具行駛軌跡的系統(tǒng)。上層控制：路線規(guī)劃，交通分析，交通安排。中層控制：無提示表，路障監(jiān)測，遵守交規(guī)。底層控制：巡航控制，防抱死，電子系統(tǒng)控制牽引力，燃油噴射系統(tǒng)，引擎調諧。1.4.2機器翻譯機器翻譯，即通過計算機將一種語言的文本翻譯成另一種語言，已成為目前解決語言屏障的重要方法之一。神經(jīng)網(wǎng)絡模型首先需要將源語言和目標語言的詞語轉化為向量表達，隨后用循環(huán)神經(jīng)網(wǎng)絡對翻譯過程進行建模，如圖所示。通常會先使用一個循環(huán)神經(jīng)網(wǎng)絡作為編碼器，將輸入序列（源語言句子的詞序列）編碼成為一個向量表示，然后再使用一個循環(huán)神經(jīng)網(wǎng)絡作為解碼器，從編碼器得到的向量表示里解碼得到輸出序列。1.4.3游戲中的人工智能AlphaGo的成功之處在于完美集成了深度神經(jīng)網(wǎng)絡、有監(jiān)督學習技術、強化學習技術和蒙特卡洛樹搜索算法。

1.5本章小結本章首先闡述了人工智能與機器學習之間的聯(lián)系；介紹了機器學習的定義、發(fā)展歷史、分類等相關基礎知識，學習了Python語言、第三方工具庫以及編譯環(huán)境等機器學習工具；最后，列舉了幾個當前比較熱門的機器學習應用實例。第二章機器學習基本理論機器學習方法離不開數(shù)據(jù)和模型，俗話說，“巧婦難為無米之炊”，數(shù)據(jù)便是“米”，模型則是“巧婦”。沒有充足的數(shù)據(jù)、合適的特征，再強大的模型結構也無法得到滿意的輸出。機器學習業(yè)界有一句經(jīng)典“Garbagein，garbageout”。對于一個機器學習問題，數(shù)據(jù)和特征往往決定了結果的上限，而模型和算法的選擇及優(yōu)化則逐步接近這個上限。282.1機器學習術語基本概念過擬合和欠擬合模型評估292.1.1基本概念數(shù)據(jù)集（dataset）是一種由數(shù)據(jù)所組成的集合，通常以表格的形式出現(xiàn)，其中每一行是一個數(shù)據(jù)，表示對一個事件或對象的描述，又稱為樣本（sample）或實例（instance）。每一列反映事件或對象在某方面的表現(xiàn)或性質，稱為特征（feature）或屬性（attribute）。屬性上的取值稱為屬性值（attributevalue）或特征值。所有屬性構成的空間稱為屬性空間（attributespace）、樣本空間（samplespace）或輸入空間（inputspace）。

屬性空間中的每一個點通常用一個向量來表示，稱為特征向量（featurevector），即每個特征向量附屬于一個實例。302.1.1基本概念模型（model）指描述特征和問題之間關系的數(shù)學對象。從數(shù)據(jù)中使用算法得到模型的過程稱為學習（learning）或訓練（training）。訓練過程中使用的數(shù)據(jù)集又被分為以下3種：訓練集（trainningset）：通常取數(shù)據(jù)集中一部分數(shù)據(jù)作為訓練集來訓練模型。測試集（testingset）：用來對已經(jīng)學習好的模型或者算法進行測試和評估的數(shù)據(jù)集。驗證集（validationset）：有時需要把訓練集進一步拆分成訓練集和驗證集，驗證集用于在學習過程中對模型進行調整和選擇。312.1.1基本概念每個實例中描述模型輸出的可能值稱為標簽（label）或標記。特征是事物固有屬性，標簽是根據(jù)固有屬性產(chǎn)生的認知。在經(jīng)過一定次數(shù)的訓練迭代后，模型損失不再發(fā)生變化或變化很小，說明當前訓練樣本已經(jīng)無法改進模型，稱為模型達到收斂（convergence）狀態(tài)。新的數(shù)據(jù)輸入到訓練好的模型中，以對其進行判斷稱為預測（prediction）。通過學習得到的模型適用于新樣本的能力，稱為泛化（generalization）能力。檢驗模型效果的方法稱為模型評估（evaluation）。322.1.2過擬合和欠擬合

當學習器把訓練樣本學得“太好”的時候，很可能將訓練樣本自身的一些特點當作所有潛在樣本的共有特性，這樣會導致泛化性能下降，這在機器學習中稱為“過擬合”。與之相反地，“欠擬合”是指對訓練樣本的一般性質尚未學習好。332.1.2過擬合和欠擬合處理過擬合的方法大致分為以下幾種：從數(shù)據(jù)入手，獲得更多的訓練數(shù)據(jù)。降低模型復雜度。正則化方法。集成學習方法。處理欠擬合的方法大致分為以下幾種：添加新特征。增加模型復雜度。減小正則化系數(shù)。342.1.3模型評估現(xiàn)實中如何進行模型的評估與選擇呢？通過實驗測試來對學習器的泛化誤差進行評估并進而做出選擇。具體地講，先使用某種實驗評估方法測得學習器的某個性能度量結果，然后對這些結果進行比較。這個評估的過程涉及到實驗評估方法的選擇、性能度量指標以及比較檢驗等幾個步驟。352.2實驗估計方法

362.2.1留出法

“留出法”是最簡單也是最直接的驗證方法，它將原始的樣本集合隨機劃分成訓練集和驗證集兩部分。比方說，對于一個點擊率預測模型，我們把樣本按照70%~30%的比例分成兩部分，70%的樣本用于模型訓練；30%的樣本用于模型驗證Scikit-learn提供的train_test_split函數(shù)能夠將數(shù)據(jù)集切分成訓練集和測試集兩類，其函數(shù)原型如下：sklearn.model_selection.train_test_split(X,y,**options)372.2.2交叉驗證法

“交叉驗證法”首先將全部樣本劃分成k個大小相等的樣本子集；依次遍歷這k個子集，每次把當前子集作為驗證集，其余所有子集作為訓練集，進行模型的訓練和評估；最后把k次評估指標的平均值作為最終的評估指標。

382.2.3自助法

自助法是基于自助采樣法的檢驗方法。對于總數(shù)為n的樣本集合，進行n次有放回的隨機抽樣，得到大小為n的訓練集。n次采樣過程中，有的樣本會被重復采樣，有的樣本沒有被抽出過，將這些沒有被抽出的樣本作為驗證集，進行模型驗證，這就是自助法的驗證過程。

392.3性能度量性能度量（performancemeasure）是指衡量模型泛化能力的評價標準，同時反映了任務需求。在對比不同模型能力時，使用不同的性能度量往往會導致不同的評判結果；這意味著模型的“優(yōu)劣”是相對的，對模型評價的標準不僅取決于算法和數(shù)據(jù)，還決定于任務需求。402.3.1錯誤率與精度

精度則定義為

412.3.2查準率、查全率與F1真實情況預測結果正例反例正例TP（真正例）FN（假反例）反例FP（假正例）TN（真反例）

422.3.3查準率、查全率與F1“平衡點”（Break-EventPoint，簡稱BEP）是“查準率＝查全率”時的取值

432.3.4ROC與AUCROC全稱是“受試者工作特征”（ReceiverOperatingCharacteristic）曲線AUC(AreaUnderROCCurve)

442.4比較檢驗統(tǒng)計假設檢驗（hypothesistest）為我們進行學習器性能比較提供了重要依據(jù)?；诩僭O檢驗結果可以推斷出，若在測試集上觀察到學習器A比B好，則A的泛化性能是否在統(tǒng)計意義上由于B，以及這個推斷結論的準確性有多大。452.4.1假設檢驗

462.4.1假設檢驗

472.4.1假設檢驗

αk251020300.0512.7062.7762.2622.0932.0450.106.3142.1321.8331.7291.699雙邊t檢驗的常用臨界值482.4.2交叉驗證t檢驗

492.4.2交叉驗證t檢驗

502.4.2交叉驗證t檢驗

512.5參數(shù)調優(yōu)機器學習常涉及兩類參數(shù)：一類是算法的參數(shù)亦稱“超參數(shù)”，數(shù)目常在10以內(nèi)；另一類是模型的參數(shù)，數(shù)目可能很多，例如大型“深度學習”模型甚至有上百億個參數(shù)。參數(shù)搜索算法一般包括三個要素：目標函數(shù)，即算法需要最大化/最小化的目標；搜索范圍，一般通過上限和下限來確定；算法的其他參數(shù)，如搜索步長。522.5.1網(wǎng)格搜索網(wǎng)格搜索是最簡單、應用最廣泛的超參數(shù)搜索算法，它通過查找搜索范圍內(nèi)的所有點來確定最優(yōu)值。如果采用較大的搜索范圍以及較小的步長，網(wǎng)格搜索有很大概率找到全局最優(yōu)值。

在實際應用中，網(wǎng)格搜索法一般會先使用較廣的搜索范圍和較大的步長，來尋找全局最優(yōu)值可能的位置；然后會逐漸縮小搜索范圍和步長，來尋找更精確的最優(yōu)值。這種操作方案可以降低所需的時間和計算量，但由于目標函數(shù)一般是非凸的，所以很可能會錯過全局最優(yōu)值。532.5.2隨機搜索隨機搜索（GridSearchCV）的思想與網(wǎng)格搜索比較相似，只是不再測試上界和下界之間的所有值，而是在搜索范圍中隨機選取樣本點。它的理論依據(jù)是，如果樣本點集足夠大，那么通過隨機采樣也能大概率地找到全局最優(yōu)值，或其近似值。GridSearchCV采用的是暴力尋找的方法來尋找最優(yōu)參數(shù)。當待優(yōu)化的參數(shù)是離散的取值的時候,GridSearchCV能夠順利地找出最優(yōu)的參數(shù)。但是當待優(yōu)化的參數(shù)是連續(xù)取值的時候暴力尋找就有心無力了。542.5.3貝葉斯優(yōu)化算法貝葉斯優(yōu)化算法通過對目標函數(shù)形狀進行學習，找到使目標函數(shù)向全局最優(yōu)值提升的參數(shù)。它學習目標函數(shù)形狀的方法是：首先根據(jù)先驗分布，假設一個搜集函數(shù)；然后，每一次使用新的采樣點來測試目標函數(shù)時，利用這個信息來更新目標函數(shù)的先驗分布；最后，算法測試由后驗分布給出的全局最值最可能出現(xiàn)的位置的點。55

2.6本章小結本章首先介紹了包含數(shù)據(jù)集、模型、泛化等常見的機器學習基礎概念，以及過擬合和欠擬合、模型評估等相關機器學習術語。接下來，介紹了留出法、交叉驗證法及自主法三種常見的模型評估方法，并分析對比了幾種方法的區(qū)別。介紹了用于衡量模型泛化能力的性能指標，錯誤率和精度，查準率、查全率和F1，以及ROC和AUC等。在此基礎上，介紹了用于評估的假設檢驗和交叉驗證等兩種比較檢驗方法。最后介紹了包括網(wǎng)格搜索、隨機搜索和貝葉斯優(yōu)化算法等三種常見的參數(shù)調優(yōu)方法。56第三章K近鄰K-近鄰算法（K-NearestNeighbor，KNN）是一種基于一定距離測度的抽樣檢驗方法，屬于監(jiān)督學習，所以使用算法時必須有已知標記的訓練集。K-近鄰算法既可用于分類也可用于回歸。在處理分類問題時，該方法只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分類樣本所屬的類別。處理回歸問題的流程與分類問題相似，區(qū)別在于樣本的輸出標記為距離其最近的一個或者幾個樣本的標記的加權平均值。573.1算法原理在分類問題中，給定一個訓練數(shù)據(jù)集，對于任何一個待分類樣本，在訓練數(shù)據(jù)集中找到與該樣本最鄰近的K個樣本（也就是最近的K個鄰居），那么即可以使用這K個樣本中的多數(shù)類別標記作為待分類樣本的類別標記。特別的，必須保證訓練數(shù)據(jù)集中的每個樣本都有類別標記。在回歸問題中，樣本的標記為連續(xù)變量，因此一般將待處理樣本的K個最近鄰的標記的加權平均值作為輸出（以距離的倒數(shù)為權重）。除此之外，還可以指定一個半徑，將半徑范圍內(nèi)的全部鄰居的標記的加權平均值作為輸出。583.1算法原理圖中的樣本有兩個類別，分別以正方形和三角形表示，而圖正中間的圓形代表待分類樣本。

首先假設我們選擇K的值為3，圓形樣本最近的3個鄰居是2個三角形和1個正方形，少數(shù)從屬于多數(shù)，基于統(tǒng)計的方法，判定這個待分類樣本屬于三角形一類。

如果我們選擇K的值為5，那么圓形樣本最近的5個鄰居是2個三角形和3個正方形，還是少數(shù)從屬于多數(shù)，可以判定這個待分類點屬于正方形一類。593.1算法原理K-近鄰算法的基本流程為：1）計算已經(jīng)正確分類的數(shù)據(jù)集中每個樣本與待分

類樣本之間的距離；2）按照距離遞增次序對數(shù)據(jù)集中的樣本排序；3）選取與待分類樣本距離最小的K個樣本；4）確定該K個樣本所在類別的出現(xiàn)頻率；5）返回該K個樣本出現(xiàn)頻率最高的類別作為待分

類樣本的預測類別。603.1算法原理K值的選擇會對算法的結果產(chǎn)生重大影響：K值較小意味著只有與待分類樣本較近的已知樣本才會對預測結果起作用，但容易發(fā)生過擬合K值較大可以減少學習的估計誤差，但是學習的近似誤差增大，因為這時與待分類樣本較遠的已知樣本也會對預測起作用，容易使預測發(fā)生錯誤。K值一般選擇一個奇數(shù)值，因為算法中的分類決策規(guī)則往往是多數(shù)表決，奇數(shù)取值可防止出現(xiàn)鄰居中不同類別樣本數(shù)量相等的情況。613.2距離度量方法

在K-近鄰算法以及其他很多機器學習算法中都會涉及到距離的計算，距離度量方式對算法的性能有很大的影響。

常用的距離計算方式如下： 1.閔科夫斯基距離（Minkowskidistance） 2.歐幾里德距離（Euclideandistance） 3.曼哈頓距離（Manhattandistance） 4.切比雪夫距離（Chebyshevdistance） 5.余弦相似度（Cosinesimilarity） 6.皮爾遜相關系數(shù)（Pearsoncorrelationcoefficient） 7.杰卡德相似系數(shù)（Jaccardsimilaritycoefficient） 8.馬氏距離（Mahalanobisdistance）62

3.2距離度量方法

63

3.2距離度量方法

64

3.2距離度量方法

65

3.2距離度量方法

66

3.3搜索優(yōu)化方法

當數(shù)據(jù)集和特征數(shù)量較大時，K-近鄰算法的距離計算成本可能會較高。在近鄰搜索的過程中，算法會有較高的計算成本。因此，為了提高K-近鄰算法的搜索效率，可以考慮使用特殊的結構來存儲已知樣本，以減少距離計算的次數(shù)。67

3.3.1

k-d樹 k-d樹（k-dimensionalTree）是針對暴力搜索效率低下而提出的基于樹的數(shù)據(jù)結構。

基本思想：若A點距離B點非常遠，B點距離C點非常近，可知A點與C點很遠，因此不需要準確計算它們之間的距離。通過這種方式，對于具有k個特征的n個樣本來說，近鄰搜索的計算成本可以降低至O[knlog(??)]以下，可以顯著改善暴力搜索在大樣本容量數(shù)據(jù)集中的表現(xiàn)。68

3.3.1

k-d樹例1：假設數(shù)據(jù)集有2個特征、6個樣本，如T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}。使用k-d樹算法確定樣本點的劃分空間分割線。

69

3.3.1

k-d樹首先，選擇劃分特征，即確定分割線是垂直于X軸還是Y軸。分別計算X軸和Y軸方向樣本的方差，得知X軸方向的方差最大，所以首先對X軸進行劃分，確定分割線的X軸坐標。然后基于上述步驟，對Y軸進行同樣劃分操作。70

3.3.1

k-d樹最后，對依然有樣本存在的子空間再按X軸進行劃分，直至子空間不再有樣本為止。由于此時的每個子空間僅包含一個樣本，因此可直接按剩余樣本劃分空間區(qū)域。71

3.3.1

k-d樹k-d樹的構建過程可以總結為：1）構造根結點，使根結點對應于k維空間中包含所有樣本點的超矩形區(qū)域；2）通過遞歸的方法，不斷地對k維空間進行切分，生成子結點。3）重復上述過程直到子區(qū)域內(nèi)沒有樣本時終止。在此過程中，將樣本保存在相應的結點上。4）通常，循環(huán)的依次選擇坐標軸對空間切分。72

3.3.1

k-d樹構建k-d樹時，關鍵需要解決2個問題：1）選擇向量的哪一維進行劃分？2）如何劃分數(shù)據(jù)？對于第一個問題，簡單的解決方法可以是隨機選擇某一維或按順序選擇，但是更好的方法應該是在數(shù)據(jù)比較分散的那一維進行劃分。好的劃分方法可以使構建的樹比較平衡，可以每次選擇中位數(shù)來進行劃分，這樣第二個問題也得到了解決。73

3.3.1

k-d樹如何利用k-d樹進行最近鄰搜索？

74

3.3.1

k-d樹如何利用k-d樹進行最近鄰搜索？

接著，由于被搜索點的劃分維度值3小于當前節(jié)點的劃分維度的值7，因此將當前節(jié)點的左子節(jié)點(5,4)作為新的當前節(jié)點。由于此時當前節(jié)點到被搜索點的距離為2.83，小于全局最短距離，所以更新當前最佳點為(5,4)。75

3.3.1

k-d樹如何利用k-d樹進行最近鄰搜索？

繼續(xù)下去，由于被搜索點的劃分維度值2小于當前節(jié)點的劃分維度值4，因此設當前節(jié)點的左子節(jié)點(2,3)為新的當前節(jié)點。由于此時當前節(jié)點到被搜索點的距離為1.41，小于全局最短距離，所以更新當前最佳點為(2,3)，全局最短距離為1.4176

3.3.1

k-d樹如何利用k-d樹進行最近鄰搜索？

77

3.3.1

k-d樹如何利用k-d樹進行最近鄰搜索？

78

3.3.2球樹 k-d樹算法雖然提高了K-近鄰算法的搜索效率，但在處理非均勻數(shù)據(jù)集和高維數(shù)據(jù)時也會出現(xiàn)效率不高的情況。為了優(yōu)化k-d樹的算法策略，提出了球樹模型。

球樹將數(shù)據(jù)遞歸地劃分為由質心c和半徑r定義的節(jié)點，每個結點本質上是一個空間，包含了若干個樣本點，每個空間內(nèi)有一個獨一無二的中心點79

3.3.2球樹

80

3.3.2球樹

首先建立根節(jié)點，找到包含所有樣本點的超球體，記錄球心位置，作為根節(jié)點。然后，找到所有點中距離最遠的兩個點，并判斷其他樣本點與這兩個點的距離，距離哪個點最近，則將該樣本點劃分到該點的類內(nèi)，這兩個類即是根節(jié)點的左子節(jié)點和右子節(jié)點。分別對兩個子節(jié)點構建超球體，記錄球心坐標和半徑。81

3.3.2球樹重復上述過程直至樣本全部劃分完畢82

3.4本章小結本章主要介紹了K-近鄰算法，給出了其在處理分類和回歸問題時的原理和流程，并介紹了k-d樹和球樹兩種提升K-近鄰搜索效率的方法。K-近鄰算法簡單易懂且實用，但是因為每一次分類或者回歸，都要把已知數(shù)據(jù)樣本和測試樣本的距離全部計算一遍并搜索其中最近的K個鄰居，在數(shù)據(jù)量和數(shù)據(jù)維度很大的情況下，需要的計算資源會十分巨大，因此會出現(xiàn)效率不高的現(xiàn)象。使用k-d樹和球樹兩種方式可以提升K-近鄰算法的搜索效率。k-d樹是每個節(jié)點都為k維點的二叉樹，所有非葉節(jié)點可以視作用一個超平面把空間分割成兩個半空間，其在數(shù)據(jù)維度較高而樣本數(shù)量又相對較少的情況下表現(xiàn)不佳。而球樹則沿著一系列球體來分割數(shù)據(jù)，雖然球樹構建數(shù)據(jù)結構的時間花費大于k-d樹，但在高維數(shù)據(jù)上表現(xiàn)得很高效。83第四章貝葉斯貝葉斯系列算法是基于貝葉斯定理和概率統(tǒng)計原理的一類算法。它們通過對特征之間的條件概率進行建模，從而進行分類、回歸、聚類等任務。貝葉斯模型作為一種重要的機器學習模型已在數(shù)據(jù)挖掘、計算機視覺、自然語言理解、經(jīng)濟統(tǒng)計與預測等領域得到廣泛應用。貝葉斯系列算法在處理小樣本問題、噪聲數(shù)據(jù)以及不確定性建模方面具有優(yōu)勢，并且能夠有效利用先驗知識進行模型推理與預測。844.1貝葉斯方法概述貝葉斯方法提供了一種基于主觀概率的數(shù)理統(tǒng)計分析方法，使用概率分布表示和理解樣本數(shù)據(jù)，根據(jù)樣本的先驗概率分布和訓練樣本的標記數(shù)據(jù)計算出相應的后驗概率分布，以貝葉斯風險為優(yōu)化目標實現(xiàn)對樣本數(shù)據(jù)的分類或回歸。854.1.1貝葉斯公式

864.1.1貝葉斯公式假設模型參數(shù)的各取值狀態(tài)互不相容，則可根據(jù)全概率公式得到概率P(X)。

因此可求得874.1.1貝葉斯公式

即后驗概率=先驗概率×樣本信息。884.1.2貝葉斯決策理論貝葉斯決策具體步驟：1）定義決策空間：確定可供選擇的決策及其可能的結果。2）確定先驗概率：對每個可能的結果（即條件）估計先驗概率。先驗概率可以基于經(jīng)驗或專家知識進行估計。3）觀測到證據(jù)：收集到與決策相關的證據(jù)或觀測數(shù)據(jù)。4）計算后驗概率：根據(jù)貝葉斯定理，將先驗概率和觀測到的證據(jù)相結合，計算各個條件下的后驗概率。5）選擇最優(yōu)決策：根據(jù)后驗概率，選擇具有最大后驗概率的決策，作為最優(yōu)的決策。894.1.3極大似然估計極大似然估計具體步驟：1）確定概率分布模型：假設觀測數(shù)據(jù)符合某個特定的概率分布模型，如正態(tài)分布、伯努利分布等。2）建立似然函數(shù)：將觀測數(shù)據(jù)看作是參數(shù)的函數(shù)，構建似然函數(shù)。似然函數(shù)表示給定參數(shù)值下觀測數(shù)據(jù)出現(xiàn)的概率。3）最大化似然函數(shù)：找到使似然函數(shù)取得最大值的參數(shù)值，即尋找最大似然估計。通常使用優(yōu)化算法，如梯度下降法或牛頓法，求解似然函數(shù)的最大值點。4）得出估計值：最大似然估計得到的參數(shù)值即為所要求的估計值。904.1.3極大似然估計

914.2樸素貝葉斯算法

樸素貝葉斯算法的核心思想是根據(jù)給定的特征向量，通過計算后驗概率來確定該樣本屬于不同類別的概率，然后選擇具有最大后驗概率的類別作為分類結果。924.2樸素貝葉斯算法

條件概率分布為

934.2樸素貝葉斯算法

樸素貝葉斯法對條件概率分布作了條件獨立性的假設

944.2樸素貝葉斯算法后驗概率計算根據(jù)貝葉斯定理可表示為

954.2.1高斯樸素貝葉斯

高斯樸素貝葉斯算法是一種基于貝葉斯定理和特征獨立性假設的分類算法，適用于處理連續(xù)特征的分類問題。

964.2.1高斯樸素貝葉斯

對于一個新的測試樣本，算法先計算該樣本在每個類別下的后驗概率。使用高斯分布的概率密度函數(shù)，算法計算每個特征值在給定類別下的對數(shù)似然。然后，將先驗概率和對數(shù)似然相加得到后驗概率。最后，選擇具有最大后驗概率的類別作為預測結果。97

高斯樸素貝葉斯算法的優(yōu)勢在于它對于大規(guī)模數(shù)據(jù)集具有較高的訓練和預測效率，并且對于缺失數(shù)據(jù)的處理比較魯棒。然而，它的一個主要限制是它假設特征之間是獨立的，這在某些實際問題中可能不符合實際情況，因此其結果可能受到特征相關性的影響。4.2.2多項式樸素貝葉斯

多項式樸素貝葉斯假設每個特征的出現(xiàn)次數(shù)是由多項分布生成的，即特征的計數(shù)符合多項分布。根據(jù)先驗概率和條件概率計算每個類別的后驗概率，并選擇具有最大后驗概率的類別作為預測結果。

對于每個測試樣本，算法會計算特征的計數(shù)，并使用條件概率計算后驗概率。984.2.3伯努利樸素貝葉斯

伯努利樸素貝葉斯算法的主要思想是將文檔表示為二進制特征向量，其中每個特征表示單詞或特定的文本屬性是否出現(xiàn)。因此每個特征的取值是布爾型的，即true和false，或者1和0。它基于一個關鍵假設，即每個特征在給定類別下是條件獨立的。

在訓練過程中，遍歷類別和特征，并根據(jù)特征是否存在來根據(jù)貝葉斯公式計算后驗概率。最后選擇具有最大后驗概率的類別作為預測結果。994.3半樸素貝葉斯算法

半樸素貝葉斯算法的核心思想是，適當考慮一部分屬性間的相互依賴信息。假設給定某個類別的條件下，特征之間的相關性可被一些選定的特征表示。

相比于傳統(tǒng)的樸素貝葉斯算法，半樸素貝葉斯算法考慮了特征之間的相關性，可以更準確地捕捉數(shù)據(jù)中的復雜關系。并且該算法允許根據(jù)具體問題選擇不同的核心特征和配對特征組合，可以適應不同類型的數(shù)據(jù)集和任務需求1004.3半樸素貝葉斯算法獨依賴估計（One-DependentEstimator，ODE）是半樸素貝葉斯分類器最常用的一種策略。獨依賴是假設每個屬性在類別之外最多依賴一個其他屬性，即：

1014.3半樸素貝葉斯算法

相比于傳統(tǒng)的樸素貝葉斯算法，半樸素貝葉斯算法考慮了特征之間的相關性。這使得模型可以更準確地捕捉數(shù)據(jù)中的復雜關系。半樸素貝葉斯算法允許根據(jù)具體問題選擇不同的核心特征和配對特征組合。這種靈活性使得算法可以適應不同類型的數(shù)據(jù)集和任務需求。此外，半樸素貝葉斯算法在處理高維數(shù)據(jù)時表現(xiàn)出較好的性能，因為它可以通過選擇核心特征和相關特征來減少特征空間的維度。

但是，在半樸素貝葉斯算法中，仍然假設給定類別下的特征是相互獨立的。然而，在實際問題中，特征之間通常存在一定的依賴關系。為了解決這個問題，可以引入更復雜的模型，如貝葉斯網(wǎng)絡、樹模型等，以捕捉特征之間的依賴性。1024.4貝葉斯網(wǎng)絡算法貝葉斯網(wǎng)絡（BayesianNetworks）也被稱為信念網(wǎng)絡（BelifNetworks）或者因果網(wǎng)絡（CausalNetworks），是描述數(shù)據(jù)變量之間依賴關系的一種圖形模式，是一種用來進行推理的模型。貝葉斯網(wǎng)絡為人們提供了一種方便的框架結構來表示因果關系。1034.4.1貝葉斯網(wǎng)結構

在貝葉斯網(wǎng)結構中，一條弧由一個屬性A指向另外一個屬性B說明屬性A的取值可以對屬性B的取值產(chǎn)生影響，由于是有向無環(huán)圖，A、B間不會出現(xiàn)有向回路。在貝葉斯網(wǎng)當中，直接的原因結點（弧尾）A叫做其結果結點（弧頭）B的雙親結點（parents），B叫做A的孩子結點（children）。如果從一個結點X有一條有向通路指向Y，則稱結點X為結點Y的祖先（ancestor），同時稱結點Y為結點X的后代（descendent）。1044.4.1貝葉斯網(wǎng)結構高油高糖飲食（X1）糖尿病（X2）高血脂（X3）心臟?。╔4）

左圖中共有四個結點和四條弧。高油高糖飲食X1是一個原因結點，它會導致糖尿病X2和高血脂X3。而我們知道糖尿病X2和高血脂X3都可能最終導致心臟病X4。1054.4.1貝葉斯網(wǎng)結構

1064.4.2貝葉斯網(wǎng)學習算法

貝葉斯網(wǎng)學習的首要任務就是根據(jù)訓練數(shù)據(jù)集來找出結構最“恰當”的貝葉斯網(wǎng)?！霸u分搜索”是求解這一問題的常用辦法。具體來說，我們先定義一個評分函數(shù)，以此來評估貝葉斯網(wǎng)與訓練數(shù)據(jù)的契合程度，然后基于這個評分函數(shù)來尋找結構最優(yōu)的貝葉斯網(wǎng)。1074.4.2貝葉斯網(wǎng)學習算法

1084.4.2貝葉斯網(wǎng)學習算法

1094.4.3貝葉斯網(wǎng)推斷

在現(xiàn)實應用中，貝葉斯網(wǎng)的近似推斷常使用吉布斯采樣來完成，這是一種隨機采樣方法。

1104.4.3貝葉斯網(wǎng)推斷

由于馬爾可夫鏈通常需很長時間才能趨于平穩(wěn)分布，因此吉布斯采樣算法的收斂速度較慢。此外，若貝葉斯網(wǎng)中存在極端概率“0”或“1”，則不能保證馬爾可夫鏈存在平穩(wěn)分布，此時吉布斯采樣會給出錯誤的估計結果。1114.5EM算法

1124.5EM算法 EM算法的每次迭代由兩步組成：E步，求期望（expectation）；M步，求極大（maximization），所以這一算法稱為期望極大算法（expectationmaximizationalgorithm），簡稱EM算法。 EM算法使用兩個步驟交替計算：第一步是期望(E)步，利用當前估計的參數(shù)值來計算對數(shù)似然的期望值；第二步是最大化(M)步，尋找能使E步產(chǎn)生的似然期望最大化的參數(shù)值。然后，新得到的參數(shù)值重新被用于E步，直到收斂到局部最優(yōu)解。1134.5EM算法例

三硬幣模型

1144.5EM算法

計算出每次試驗選擇B和C的概率，然后根據(jù)試驗數(shù)據(jù)進行加權求和。M步：更新模型參數(shù)的新估計值。根據(jù)函數(shù)求導來確定參數(shù)值：

對上式求導并令其值為0可得第一次迭代后的參數(shù)值，然后重復進行第二輪、第三輪，直至模型收斂。1154.6本章小結本章主要介紹了貝葉斯，講解了其理論、樸素貝葉斯算法、半樸素貝葉斯算法、貝葉斯算法、EM算法。樸素貝葉斯法是基于貝葉斯定理與特征條件獨立假設的分類方法。樸素貝葉斯的“樸素”體現(xiàn)在，假設各屬性之間沒有相互依賴。貝葉斯網(wǎng)絡也被稱為信念網(wǎng)絡或者因果網(wǎng)絡，是描述數(shù)據(jù)變量之間依賴關系的一種圖形模式，是一種用來進行推理的模型。EM算法是一種迭代算法，用于含有隱變量的概率模型參數(shù)的極大似然估計，或極大后驗概率估計。116第五章線性模型線性模型是機器學習中常用的一種建模方法，它基于線性關系對輸入特征與輸出目標之間的關系進行建模和預測。線性模型具有簡單且易于解釋的特征權重，使得我們可以理解每個特征對輸出的貢獻。而且，線性模型具有良好的可解釋性，可以用于推斷變量之間的關系和影響程度。1175.1線性回歸一元線性回歸假設因變量和自變量之間存在線性關系，這個線性模型所構成的空間是一個超平面（hyperplane）。超平面是n維歐氏空間中余維度等于一的線性子空間，如平面中的直線、空間中的平面等，總比包含它的空間少一維。在一元線性回歸中，一個維度是因變量，另一個維度是自變量，總共兩維。因此，其超平面只有一維，就是一條線。1185.1.1簡單線性回歸

簡單線性回歸是利用稱為線性回歸方程的最小二乘函數(shù)對一個或多個自變量和因變量之間關系進行建模的一種回歸分析。

1195.1.1簡單線性回歸

1205.1.2多變量線性回歸

直線回歸研究的是一個因變量與一個自變量之間的回歸問題。但是，在許多實際問題中，影響因變量的自變量往往不止一個，而是多個。

1215.1.2多變量線性回歸

1225.1.2多變量線性回歸

因此，線性回歸模型為

1235.1.3梯度下降法

梯度下降法(gradientdecent)是一個最優(yōu)化算法，通常也稱為最速下降法。常用于機器學習和人工智能當中用來遞歸性地逼近最小偏差模型。

當函數(shù)定義域和取值都在實數(shù)域中的時候，導數(shù)可以表示函數(shù)曲線上的切線斜率。除了切線的斜率，導數(shù)還表示函數(shù)在該點的變化率。在一元函數(shù)中，只有一個自變量變動，不存在偏導數(shù)。偏導數(shù)至少涉及到兩個自變量，是多元函數(shù)沿不同坐標軸的變化率1245.1.3梯度下降法

1255.1.3梯度下降法

1265.1.3梯度下降法

在具體使用梯度下降法的過程中，主要有以下三種：（1）批量梯度下降法

批量梯度下降法針對的是整個數(shù)據(jù)集，通過對所有的樣本的計算來求解梯度的方向。（2）小批量梯度下降法

在批量梯度下降法的方式中每次迭代都要使用到所有的樣本，對于數(shù)據(jù)量特別大的情況，如大規(guī)模的機器學習應用，每次迭代求解所有樣本需要花費大量的計算成本。（3）隨機梯度下降法

隨機梯度下降法可以看成是小批量梯度下降法的一個特殊的情形，即在隨機梯度下降法中每次僅根據(jù)一個樣本對模型中的參數(shù)進行調整，即每個小批量梯度下降法中只有一個訓練樣本1275.1.4多項式回歸

多項式回歸是研究一個因變量與一個或多個自變量間多項式關系的回歸分析方法。當自變量只有一個時，稱為一元多項式回歸。

同理當自變量有多個時，則稱為多元多項式回歸

1285.2邏輯回歸

1295.2邏輯回歸Sigmoid函數(shù)有一個非常實用的性質。其導數(shù)式為：

Sigmoid函數(shù)在實數(shù)范圍內(nèi)連續(xù)可導，優(yōu)化穩(wěn)定。任意自變量經(jīng)過Sigmoid函數(shù)映射后得到的結果可以看成是一個概率。Sigmoid函數(shù)值以0.5為中心，可以將大于0.5的數(shù)據(jù)映射為1類，小于0.5的數(shù)據(jù)映射為0類。1305.2.1二分類邏輯回歸邏輯回歸的表達式

1315.2.1二分類邏輯回歸繼上頁，則有

寫成對數(shù)形式就是交叉熵損失函數(shù)

1325.2.2多分類邏輯回歸

普通的邏輯回歸只能針對二分類(BinaryClassification)問題，要想實現(xiàn)多個類別的分類，我們必須要改進邏輯回歸，讓其適應多分類問題。

第一種方式是直接根據(jù)每個類別，都建立一個二分類器，帶有這個類別的樣本標記為1，帶有其他類別的樣本標記為0。針對每一個測試樣本，我們需要找到這k個分類函數(shù)輸出值最大的那一個，即為測試樣本的標記。

1335.2.2多分類邏輯回歸

第二種方式是修改邏輯回歸的損失函數(shù)，讓其適應多分類問題。這時損失函數(shù)不再籠統(tǒng)地只考慮二分類非1就0的損失，而是具體考慮每種樣本標記的損失。這種方法被稱為Softmax回歸。

1345.2.2多分類邏輯回歸損失函數(shù)可以表示為

對其求導，可得

其更新參數(shù)為

1355.3模型正則化

在訓練數(shù)據(jù)不夠多或者過度訓練時，常常會導致過擬合（Overfitting）。正則化（Regularization）方法即是在此時向原始模型引入額外信息，以防止過擬合并提高模型泛化性能。

正則化一般具有以下形式1365.3模型正則化

第1項的損失函數(shù)值較小的模型可能較復雜（有多個非零參數(shù)），這時第2項的模型復雜度會較大，正則化的作用是選擇損失函數(shù)值與模型復雜度同時較小的模型。1375.4本章小結

線性回歸是一種用于建模和預測連續(xù)數(shù)值輸出的線性模型，它假設輸入特征與輸出之間存在線性關系。多項式回歸是線性回歸的擴展，通過引入高階項，能夠擬合非線性關系的數(shù)據(jù)。邏輯回歸則是一種應用于分類問題的線性模型，在二分類情況下，它利用logistic函數(shù)將線性預測轉化為概率，常用于預測樣本的類別。而softmax回歸則是邏輯回歸在多分類問題上的推廣，通過對每個類別分別建立二分類邏輯回歸模型，并使用softmax函數(shù)計算每個類別的概率，從而進行多分類預測。138第六章支持向量機支持向量機（SupportVectorMachine，SVM）是一種常用的監(jiān)督學習算法，主要用于分類和回歸任務。其基本思想是在特征空間中找到一個最優(yōu)超平面，能夠將不同類別的樣本點盡可能地分開，并且使支持向量到超平面的距離最大化。在支持向量機（SVM）中，有幾種常用的方法和變體，如：線性支持向量機（LinearSVM）、非線性支持向量機（NonlinearSVM）、多類別支持向量機（Multi-classSVM）及支持向量回歸（SupportVectorRegression，SVR），用于解決不同類型的分類和回歸問題。1396.1算法概述線性支持向量機（LinearSVM）：基于線性可分的假設，在特征空間中尋找一個最優(yōu)超平面，能夠最大化不同類別的樣本點之間的間隔。非線性支持向量機（NonlinearSVM）：適用于數(shù)據(jù)集在原始特征空間中無法線性分割的情況。它使用核函數(shù)（如多項式核、高斯核）將樣本映射到高維特征空間，從而找到一個非線性的最優(yōu)超平面。1406.1算法概述多類別支持向量機（Multi-classSVM）：常見的方法是使用“一對一”（One-vs-One）策略，將每個類別與其他類別進行兩兩比較，構建多個二分類器。另一種方法是使用“一對其余”（One-vs-Rest）策略，將每個類別與其他所有類別組合成一個二分類器。支持向量回歸（SupportVectorRegression，SVR）：其目標是找到一個最優(yōu)超平面，使得樣本點盡可能地落在超平面的附近區(qū)域內(nèi)，并且最小化間隔內(nèi)的誤差。支持向量回歸能夠處理非線性回歸問題，并具有一定的抗噪能力。1416.2線性可分支持向量機及其對偶算法右圖假設訓練數(shù)據(jù)集是線性可分的，能將訓練樣本分開的劃分超平面可能有很多，應該選取哪一個呢？

0圖6-1

存在多個劃分超平面

142

6.2線性可分支持向量機及其對偶算法

0

圖6-2

支持向量與間隔143

6.2線性可分支持向量機及其對偶算法144

6.2線性可分支持向量機及其對偶算法145

6.2線性可分支持向量機及其對偶算法146

6.2線性可分支持向量機及其對偶算法147

6.2線性可分支持向量機及其對偶算法148

6.2線性可分支持向量機及其對偶算法

149

6.3線性支持向量機0圖6-3樣本近似線性可分

圖6-4支持向量與間隔

150

6.3線性支持向量機

圖6-4支持向量與間隔151

6.3線性支持向量機

152

6.3線性支持向量機

153

6.3線性支持向量機

1546.3線性支持向量機

1556.3線性支持向量機

1566.4非線性支持向量機

101110

1

圖6-5異或問題圖6-6異或問題映射到三維空間

157

6.4非線性支持向量機

1586.4非線性支持向量機

1596.4非線性支持向量機

160

6.4非線性支持向量機

161

6.4非線性支持向量機

162

6.4非線性支持向量機

1636.5.1線性支持向量機回歸

0圖6-7線性回歸1646.5.1線性支持向量機回歸

圖6-8支持向量機回歸

01656.5.1線性支持向量機回歸

圖6-8支持向量機回歸

01666.5.1線性支持向量機回歸

圖6-8支持向量機回歸

01676.5.1線性支持向量機回歸

1686.5.1線性支持向量機回歸

1696.5.1線性支持向量機回歸

1706.5.1線性支持向量機回歸

1716.5.2非線性支持向量機回歸

1726.5.2非線性支持向量機回歸

1736.5.2非線性支持向量機回歸

1746.6SMO算法

1756.6SMO算法

1766.6SMO算法

177

6.7

本章小結本章主要介紹了支持向量機的基本原理。首先，介紹支持向量機的基本分類模型及其對偶算法，從線性到非線性，分別介紹其原理及應用范圍。然后，從線性回歸到支持向量機回歸，對別介紹兩者的原理和區(qū)別。最后，基于Python編程，通過不同數(shù)據(jù)集展示不同模型的實現(xiàn)方法。178第七章決策樹決策樹（DecisionTree）是一種基本的分類與回歸方法，是最早的機器學習算法之一。1979年，J.RossQuinlan提出了ID3算法原型，并于1983年和1986年對ID3算法進行了總結和簡化，正式確立了決策樹理論。此間的1984年，LeoBreiman,JeromeFriedman,RichardOlshen與CharlesStone共同提出了分類與回歸樹（ClassificationandRegressionTrees），即CART算法。1993年，Quinlan在ID3算法的基礎上又提出了著名的C4.5算法。相對于其他算法，決策樹算法的基本原理更加符合人的思維方式，可以產(chǎn)生可視化的分類或回歸規(guī)則，生成的模型也具有可解釋性，因此其應用十分廣泛。本章主要介紹上述3種決策樹算法的原理、流程及實現(xiàn)。1797.1決策樹概述決策樹是一種呈樹形結構的層次模型，可以是二又樹也可以是多叉樹。在分類問題中，樹的每個非葉節(jié)點表示對一個特征的判斷，每個分支代表該特征在某個值域上的輸出，而每個葉節(jié)點存放一個類別。使用決策樹進行決策的過程就是從根節(jié)點開始，逐個判斷待分類項中相應的特征，并按照其值選擇輸出分支，直到到達葉節(jié)點，將葉節(jié)點存放的類別作為決策的結果。每一個樣本只會被一條路徑覆蓋（樣本的特征與路徑上的特征一致或樣本滿足規(guī)則的條件）。1807.1決策樹概述如果想知道在不同天氣情況下人們是否會去室外打球，就可以建立圖7-1中的決策樹。圖中的菱形框表示對一個特征的判斷，菱形框下方線段上的文字表示每個判斷的所有可能的取值。圖中最上方的矩形框為“根節(jié)點”，中間矩形框為“中間節(jié)點”，最下方矩形框為“葉節(jié)點”。圖7-1決策樹算法原理舉例181稱箭頭的起點是終點的“父節(jié)點”，終點是起點的“子節(jié)點”。當子節(jié)點只有兩個時，通常把他們稱為“左子節(jié)點”和“右子節(jié)點”。7.1決策樹概述決策樹構造過程：1）從根節(jié)點開始，將數(shù)據(jù)集依照某個特征的取值劃分為互不相交的幾個子集；2）如果某個子集中的樣本都屬于同一個類別或某一個類別所占的百分比大于設定的閾值，則將其設置為葉節(jié)點，并將多數(shù)樣本的類別作為該葉節(jié)點的類別。否則將該子集設置為中間節(jié)點，并依照某個特征的取值繼續(xù)劃分；3）重復步驟2）直至所有分支的末尾一行均為葉節(jié)點。

1827.1決策樹概述構造決策樹的關鍵是如何進行最優(yōu)特征劃分，即確定非葉節(jié)點對應的特征及其判斷閾值。最優(yōu)特征劃分的方法有很多，每種決策樹之所以不同，一般都是因為最優(yōu)特征選擇的標準上有所差異，不同的標準導致生成不同類型的決策樹。本章介紹其中三個相對而言比較基本且使用廣泛的算法：ID3、C4.5和CART。三種算法是以遞進的關系產(chǎn)生的。1）ID3算法是最基礎的決策樹算法，可以解決離散型數(shù)據(jù)的分類問題。2）C4.5算法在ID3算法的基礎上進一步發(fā)展，可以解決混合型數(shù)據(jù)的分類問題。3）CART算法則更進一步，在分類問題的基礎上，還可以解決回歸問題。雖說上述算法的功能越來越強大，但其核心思想都是一致的，即算法通過不斷劃分數(shù)據(jù)集來生成決策樹，其中每一步都選擇最優(yōu)的劃分特征。183一般而言，隨著劃分過程不斷進行，希望決策樹的每個分枝中所包含的樣本盡可能屬于同一類別，即節(jié)點的“純度”越來越高。因此，對于一個包含多個特征的數(shù)據(jù)集，應盡量選擇對劃分后子集的純度提升最多的特征。信息熵可以用來度量一個系統(tǒng)的有（無）序程度。如果將其應用在數(shù)據(jù)集上，那么一個集合中包含樣本的類別越多，則說明數(shù)據(jù)越“混亂”，信息墑越大；否則說明數(shù)據(jù)越“純凈”，信息墑越小。而我們要做的就是保證每一次劃分都讓劃分后的信息墑降低的最多，也就是信息墑的增益最大。ID3決策樹算法就是以信息增益作為決策樹分支的劃分依據(jù)，每次選擇信息增益最大的特征進行劃分。ID3算法只能處理離散數(shù)據(jù)，即可以處理像性別特征、布爾值特征等離散型特征，但沒法處理特征值在某個區(qū)間內(nèi)可以任意取值的特征，如身高特征、年齡特征等。7.2

ID3算法184

7.2.1信息熵和信息增益185

7.2.1信息熵和信息增益186

7.2.1信息熵和信息增益187

7.2.2

ID3算法流程188（8）對每個子集從步驟（1）開始繼續(xù)執(zhí)行。其中步驟（6）的“停止條件”（也可稱為“預剪枝”）有多種定義方法，較為常用的是如下兩種：1）若選擇作為劃分特征時的信息增益小于某個閾值，則停止；2）事先把數(shù)據(jù)集分為訓練集與測試集，若由訓練集得到的節(jié)點并不能降低測試集上的錯誤率，則停止。這兩種停止條件通用于C4.5算法和CART算法。同時，決策樹會在許多地方應用到遞歸的思想，上述算法中的步驟（7）正是經(jīng)典的遞歸。7.2.2

ID3算法流程189例7-1：表7-1給出了一個哺乳動物數(shù)據(jù)集包含14個樣本，樣本有“飲食習性”、“胎生動物”、“水生動物”、“會飛”四個特征，“哺乳動物”為樣本的類別標記，有“是”與“否”兩種取值。

7.2

ID3算法表7-1

哺乳動物分類數(shù)據(jù)集190

7.2

ID3算法191

7.2

ID3算法192

7.3

C4.5算法ID3算法存在一個問題，就是偏向于多值特征。例如，如果一個特征是樣本的唯一標識，則ID3會選擇它作為最優(yōu)劃分特征。這樣雖然使得劃分充分純凈，但這種劃分對分類幾乎毫無用處，而且小數(shù)目子集在分類效果上是不如大數(shù)目子集好的（如過擬合、抗噪差等問題）。所以，為了解決這個問題，可以對會產(chǎn)生大量“小數(shù)目”子集的劃分進行懲罰，即劃分后產(chǎn)生的子集越小，它的信息熵要懲罰性的增大。這樣雖然ID3算法中會因為很多劃分后的小數(shù)量子集而產(chǎn)生較低的信息熵，但做懲罰值處理后，熵值就會平衡性的增大。這就是C4.5算法的改進方向，它不再使用信息增益而是改用信息增益率來對最優(yōu)劃分特征進行選擇，克服了使用信息增益選擇特征時偏向于多值特征的不足。此外，C4.5算法還可以處理連續(xù)型特征。193

7.3.1信息增益率

194

7.3.1信息增益率由此看出，劃分的子集越多、子集中樣本數(shù)量越少，懲罰值越大，相除后的信息增益率也就越小，依此做到了一定的平衡。由于“懲罰”了產(chǎn)生小樣本數(shù)量子集的劃分，其由于樣本數(shù)量少帶來信息增益抗噪性差的問題也得到一定程度的解決，這就是C4.5算法的最大好處。另外C4.5和ID3算法還有一個特點，這兩個算法的根本都要計算信息增益，而信息增益的一個大前提就是要先進行劃分，然后才能計算。所以，每計算一次增益也就代表進行了一次劃分，而劃分特征接下來就不能再用了，所以ID3和C4.5算法在分類時會不斷消耗特征。195

7.3.2連續(xù)型特征處理

196

7.3.2連續(xù)型特征處理

197

7.3.2連續(xù)型特征處理

198

7.3.3C4.5算法流程

199

7.3.3C4.5算法流程

200

7.4分類與回歸樹分類與回歸樹（ClassificationAndRegressionTree，CART）算法是目前決策樹算法中最為成熟的一類算法，它既可用于分類，也可用于回歸。其一大特色就是假設最終生成的決策樹為二叉樹，即它在處理離散型和連續(xù)型特征時都會通過二分標準來劃分數(shù)據(jù)。在處理分類問題時，CART算法一般會使用基尼系數(shù)作為劃分優(yōu)劣的度量，算法的其他流程與C4.5算法類似。在處理回歸問題時，CART算法使用平方誤差最小化準則（SquaredResidualsMinimization）。將數(shù)據(jù)集劃分后，利用線性回歸建模，如果每次劃分后的子集仍然難以擬合則繼續(xù)劃分。這樣創(chuàng)建出來的決策樹，每個葉節(jié)點都是一個線性回歸模型。這些線性回歸模型反映了數(shù)據(jù)集中蘊含的模式，也稱為模型樹。因此，CART不僅支持整體預測，也支持局部模式的預測，并有能力從整體中找到模式或根據(jù)模式組合成一個整體。整體與模式之間的相互結合，對于預測分析非常有價值。2017.4.1基尼系數(shù)

2027.4.1基尼系數(shù)

2037.4.2回歸樹

2047.4.2回歸樹

2057.4.2回歸樹

2067.5剪枝策略從直觀上來說，只要決策樹足夠深，劃分標準足夠細，它在訓練集上的表現(xiàn)就能接近完美：但同時也容易想象，由于它可能把訓練集的一些“特性”當作所有數(shù)據(jù)的“特性”來看待，它在未知的測試數(shù)據(jù)上的表現(xiàn)可能就會比較一般，亦即會出現(xiàn)過擬合的問題。模型出現(xiàn)過擬合問題一般是因為模型太過復雜，所以決策樹解決過擬合的方法是采取適當?shù)摹凹糁Α薄?077.5剪枝策略剪枝通常分為兩類：“預剪枝”和“后剪枝”，其中“預剪枝”的概念在前文中已有使用，彼時采取的說法是“停止條件”，如樹的深度超出閾值、當前節(jié)點的樣本數(shù)量小于閾值、信息增益小于閾值等等。但是選取適當?shù)拈撝当容^困難，過高會導致過擬合，而過低會導致欠擬合，因此需要人工反復地訓練樣本才能得到很好的效果。預剪枝也有優(yōu)勢，由于它不必生成整棵決策樹，且算法簡單、效率高，適合大規(guī)模問題的粗略估計。而“后剪枝”是指在完全生成的決策樹上，剪掉樹中不具備一般代表性的子樹，使用葉節(jié)點取而代之，進而形成一棵規(guī)模較小的新樹。換句話說，后剪枝是從全局出發(fā)，通過某種標準對一些節(jié)點進行局部剪枝，這樣就能減少決策樹中節(jié)點的數(shù)目，從而有效地降低模型復雜度。2087.5剪枝策略問題的關鍵在于如何定出局部剪枝的標準。通常來說有兩種做法：1）應用交叉驗證的思想，若局部剪枝能夠使得模型在測試集上的錯誤率降低，則進行局部剪枝（預剪枝中也可應用類似的思想）；2）應用正則化的思想，綜合考慮不確定性和模型復雜度來定出一個新的損失函數(shù)（此前的損失函數(shù)只考慮了誤差），用該損失函數(shù)作為一個節(jié)點是否進行局部剪枝的標準。第二種做法又涉及另一個關鍵問題：如何定量分析決策樹中一個節(jié)點的復雜度？一個直觀且合理的方法是：直接使用該節(jié)點下屬葉節(jié)點的個數(shù)作為復雜度，這種方法稱為代價復雜度剪枝法（CostComplexityPruning）。2097.5剪枝策略

2107.5剪枝策略

211圖7-1決策樹算法原理舉例

7.5.1單一因子策略

212

7.5.1單一因子策略

2137.5.2最優(yōu)因子策略

2147.5.2最優(yōu)因子策略

2157.5.2最優(yōu)因子策略

216

7.6

本章小結本章主要介紹了決策樹算法中的ID3算法、C4.5算法以及CART算法，講解了其算法原理、算法流程以及在Python中的具體實現(xiàn)代碼，最后介紹了決策樹算法中使用的剪枝策略。CART算法與ID3算法和C4.5算法都由最優(yōu)劃分特征選擇、樹的生成、剪枝等流程構成。但ID3算法和C4.5算法用于分類，CART既可用于分類又可用于回歸。ID3算法和C4.5算法生成的決策樹可以是多叉的，每個節(jié)點的子節(jié)點由該節(jié)點特征的取值種類而定，而CART算法為假設決策樹為二叉樹，其等價于遞歸地二分每一個特征。217第八章集成學習在監(jiān)督學習中，傳統(tǒng)方式是按照選定的學習算法，針對某個給定的訓練數(shù)據(jù)集訓練得到一個特定的學習器模型，然后再用它預測未知的樣本。集成學習可以組合多個弱模型以期得到一個更好更全面的強模型，集成學習潛在的思想是即便某一個弱學習器得到了錯誤的預測，其他的弱學習器也可以將錯誤糾正回來。因此，集成學習（EnsembleLearning）是指利用多個獨立的弱學習器來進行學習，組合某輸入樣例在各個弱學習器上的輸出，并由它們按照某種策略共同決定輸出。2188.1集成學習概述集成學習是一種功能十分強大的機器學習方法，其基本思想是先通過一定的規(guī)則生成固定數(shù)量的弱學習器（或稱為基學習器、個體學習器），再采用某種集成策略將這些弱學習器的預測結果組合起來，從而形成最終的結論。弱學習器（WeakLearner）是錯誤概率小于1/2的學習器，也就是說在兩類問題上僅比隨機猜測好，而強學習器（StrongLearner）則具有任意小的錯誤概率。集成學習不是一個單獨的機器學習算法，而是一個將多重或多個弱學習器組合成一個強學習器，從而有效地提升分類效果。一般而言，集成學習中的基學習器可以是同質的“弱學習器”，也可以是異質的“弱學習器”。目前，同質弱學習器的應用最為廣泛，同質弱學習器中使用最多的模型是CART決策樹和神經(jīng)網(wǎng)絡。同質弱學習器按照其間是否存在依賴關系又可以分為兩類。2198.1集成學習概述串行集成方法：參與訓練的弱學習器按照順序執(zhí)行。串行方法的原理是利用弱學習器之間的依賴關系，通過對之前訓練中錯誤標記的樣本賦值較高的權重，可以提高整體的預測效果，其代表算法是提升法（Boosting）。并行集成方法：參與訓練的弱學習器并行執(zhí)行。并行方法的原理是利用弱學習器之間的獨立性，由于弱學習器之間不存在強依賴關系，通過平均可以顯著降低錯誤，其代表算法是投票法（Voting）和裝袋法（Bagging）。2208.1集成學習概述根據(jù)集成學習的用途不同，結論合成的方法也各不相同。當集成學習用于分類時，集成的輸出通常由各弱學習器的輸出投票產(chǎn)生。通常采用絕對多數(shù)投票法（某分類成為最終結果，當且僅當有超過半數(shù)的弱學習器輸出結果為該分類）或相對多數(shù)投票法（某分類成為最終結果，當且僅當輸出結果為該分類的弱學習器的數(shù)目最多）。理論分析和大量實驗表明，后者優(yōu)于前者。當集成學習用于回歸時，集成的輸出通常由各學習器的輸出通過簡單平均或加權平均產(chǎn)生，采用加權平均可以得到比簡單平均更好的泛化能力。

221投票法（Voting）是集成學習里面針對分類問題的一種結合策略?；舅枷胧沁x擇所有機器學習算法當中輸出最多的那個類。分類的機器學習算法輸出有兩種類型，一種是直接輸出類標簽，另外一種是輸出類概率。使用前者進行投票叫做硬投票（Majority/HardVoting），使用后者進行分類叫做軟投票（SoftVoting）。例如，在硬投票中，如果三個算法將特定葡萄酒的顏色預測為“白色”、“白色”和“紅色”，則集成算法將輸出“白色”；在軟投票中，如果算法A以40%的概率預測對象是一塊巖石，而算法B以80%的概率預測它是一塊巖石，那么集成算法將預測該對象是一塊巖石的可能性為(80+40)/2=60%。8.2投票法222

8.2.1投票策略223

8.2.1投票策略224

8.3裝袋法225隨機森林（RandomForest，RF）就是通過裝袋法的思想將多個弱學習器組合在一起，其弱學習器一般采用CART決策樹。隨機森林的“隨機”體現(xiàn)在兩個方面：一是樣本的隨機選取，即通過有放回采樣構造子數(shù)據(jù)集，子數(shù)據(jù)集的樣本數(shù)量和原始數(shù)據(jù)集一致。不同子數(shù)據(jù)集中的樣本可以重復，同一個子數(shù)據(jù)集中的樣本也可以重復。這樣在訓練模型時，每一棵樹的輸入樣本都不是全部的樣本，使森林中的決策樹不至于產(chǎn)生局部最優(yōu)解。二是特征的隨機選取，即隨機森林中的決策樹的每一個分裂過程并未使用所有特征，而是從所有特征中隨機選取一定的特征，之后在隨機選取的特征中選取最優(yōu)劃分特征。最后，將多棵決策樹的輸出進行整合作為最終輸出。隨機森林既可以用于分類問題，也可以用于回歸問題，生成過程中這兩個隨機性可以確保不會出現(xiàn)過擬合的情況。8.3.1隨機森林算法226

8.3.1隨機森林算法227這里我們還要提到一下極端隨機樹（ExtremelyRandomizedTrees）算法，簡稱ExtraTree。它與隨機森林算法十分相似，主要區(qū)別是隨機森林采用對數(shù)據(jù)集有放回隨機采樣的方式生成多個子訓練集，而極端隨機樹使用整個數(shù)據(jù)集作為訓練集，但是節(jié)點的劃分特征是隨機選取的。因為分裂是完全隨機的，所以有時可以得到比隨機森林更好的結果。8.3.2極端隨機樹算法228提升法（Boosting）是一種重要的集成學習技術，能夠將預測精度僅比隨機猜度略高的弱學習器增強為預測精度高的強學習器，這在直接構造強學習器非常困難的情況下，為學習算法的設計提供了一種有效的新思路和新方法。提升法可以提升任意給定學習算法的準確度，主要思想是通過一些簡單的規(guī)則整合得到一個整體，使得該整體具有的性能比任何一個部分都高。其思想受啟發(fā)于Valiant提出的PAC（ProbablyApproximatelyCorrect）學習模型。