機器學習算法與實踐 課件 第3、4章 K近鄰、貝葉斯

第三章K近鄰K-近鄰算法（K-NearestNeighbor，KNN）是一種基于一定距離測度的抽樣檢驗方法，屬于監(jiān)督學習，所以使用算法時必須有已知標記的訓練集。K-近鄰算法既可用于分類也可用于回歸。在處理分類問題時，該方法只依據(jù)最鄰近的一個或者幾個樣本的類別來決定待分類樣本所屬的類別。處理回歸問題的流程與分類問題相似，區(qū)別在于樣本的輸出標記為距離其最近的一個或者幾個樣本的標記的加權(quán)平均值。13.1算法原理在分類問題中，給定一個訓練數(shù)據(jù)集，對于任何一個待分類樣本，在訓練數(shù)據(jù)集中找到與該樣本最鄰近的K個樣本（也就是最近的K個鄰居），那么即可以使用這K個樣本中的多數(shù)類別標記作為待分類樣本的類別標記。特別的，必須保證訓練數(shù)據(jù)集中的每個樣本都有類別標記。在回歸問題中，樣本的標記為連續(xù)變量，因此一般將待處理樣本的K個最近鄰的標記的加權(quán)平均值作為輸出（以距離的倒數(shù)為權(quán)重）。除此之外，還可以指定一個半徑，將半徑范圍內(nèi)的全部鄰居的標記的加權(quán)平均值作為輸出。23.1算法原理圖中的樣本有兩個類別，分別以正方形和三角形表示，而圖正中間的圓形代表待分類樣本。

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

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

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

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

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

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

3.2距離度量方法

7

3.2距離度量方法

8

3.2距離度量方法

9

3.2距離度量方法

10

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

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

3.3.1

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

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

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樹算法確定樣本點的劃分空間分割線。

13

3.3.1

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

3.3.1

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

3.3.1

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

3.3.1

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

3.3.1

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

18

3.3.1

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

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

3.3.1

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

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

3.3.1

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

21

3.3.1

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

22

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

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

3.3.2球樹

24

3.3.2球樹

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

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

3.4本章小結(jié)本章主要介紹了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ù)，雖然球樹構(gòu)建數(shù)據(jù)結(jié)構(gòu)的時間花費大于k-d樹，但在高維數(shù)據(jù)上表現(xiàn)得很高效。27第四章貝葉斯貝葉斯系列算法是基于貝葉斯定理和概率統(tǒng)計原理的一類算法。它們通過對特征之間的條件概率進行建模，從而進行分類、回歸、聚類等任務。貝葉斯模型作為一種重要的機器學習模型已在數(shù)據(jù)挖掘、計算機視覺、自然語言理解、經(jīng)濟統(tǒng)計與預測等領域得到廣泛應用。貝葉斯系列算法在處理小樣本問題、噪聲數(shù)據(jù)以及不確定性建模方面具有優(yōu)勢，并且能夠有效利用先驗知識進行模型推理與預測。284.1貝葉斯方法概述貝葉斯方法提供了一種基于主觀概率的數(shù)理統(tǒng)計分析方法，使用概率分布表示和理解樣本數(shù)據(jù)，根據(jù)樣本的先驗概率分布和訓練樣本的標記數(shù)據(jù)計算出相應的后驗概率分布，以貝葉斯風險為優(yōu)化目標實現(xiàn)對樣本數(shù)據(jù)的分類或回歸。294.1.1貝葉斯公式

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

因此可求得314.1.1貝葉斯公式

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

354.2樸素貝葉斯算法

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

條件概率分布為

374.2樸素貝葉斯算法

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

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

394.2.1高斯樸素貝葉斯

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

404.2.1高斯樸素貝葉斯

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

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

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

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

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

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

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

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

454.3半樸素貝葉斯算法

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

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

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

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

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

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

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

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

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

544.4.3貝