機(jī)器學(xué)習(xí)算法與實(shí)踐 課件 第11章 半監(jiān)督學(xué)習(xí)

第十一章半監(jiān)督學(xué)習(xí)半監(jiān)督學(xué)習(xí)（Semi-SupervisedLearning，SSL）是模式識別和機(jī)器學(xué)習(xí)領(lǐng)域研究的重點(diǎn)問題，是監(jiān)督學(xué)習(xí)與無監(jiān)督學(xué)習(xí)相結(jié)合的一種學(xué)習(xí)方法。許多實(shí)例采用無監(jiān)督標(biāo)記來提高預(yù)測精度和學(xué)習(xí)算法的速度；通過引入加權(quán)系數(shù)動態(tài)調(diào)整無類標(biāo)簽樣例的影響，提高了分類準(zhǔn)確度；建立每類中具有多個(gè)混合部分的模型，使貝葉斯偏差減小。半監(jiān)督學(xué)習(xí)使用大量的未標(biāo)記數(shù)據(jù)，同時(shí)使用標(biāo)記數(shù)據(jù)來進(jìn)行模式識別工作。111.1未標(biāo)記樣本

如果圖中有一個(gè)樣本恰好位于正負(fù)實(shí)例中間，可以在圖中看到大體上類似于隨機(jī)猜測。如果觀察到圖中的未標(biāo)記樣本，則可以基于聚類假設(shè)來利用未標(biāo)記樣本，由于待預(yù)測樣本與正例樣本通過未標(biāo)記樣本的“撮合”聚集在一起，與相對分離的反例樣本相比，可以將該樣本判定為正例。211.1未標(biāo)記樣本

311.2半監(jiān)督學(xué)習(xí)方法半監(jiān)督學(xué)習(xí)可進(jìn)一步劃分為純半監(jiān)督學(xué)習(xí)和直推學(xué)習(xí)，前者假設(shè)訓(xùn)練數(shù)據(jù)中的樣本不顯著，而后者則假定學(xué)習(xí)過程中所考慮的未標(biāo)記樣本恰好是待預(yù)測數(shù)據(jù)，學(xué)習(xí)目的就是在這些未標(biāo)記樣本中獲得最優(yōu)泛化性能。4

11.2.1生成式方法

5

11.2.1生成式方法6

（11-2）

11.2.1生成式方法7

11.2.1生成式方法8

生成式方法簡單，易于實(shí)現(xiàn)，在有標(biāo)記數(shù)據(jù)極少的情形下往往比其他方法性能更好。

然而，此類方法中模型假設(shè)必須準(zhǔn)確，即假設(shè)的生成式模型必須與真是數(shù)據(jù)分布吻合，否則未用未標(biāo)記數(shù)據(jù)反倒會降低泛化性能。現(xiàn)實(shí)任務(wù)中，除非擁有充分可靠的領(lǐng)域知識，否則往往很難事先做出準(zhǔn)確的模型假設(shè)。

11.2.2半監(jiān)督SVM半監(jiān)督支持向量機(jī)（Semi-SupervisedSupportVectorMachine，簡稱S3VM），S3VM是一種在半監(jiān)督學(xué)習(xí)上推廣的廣義支持向量機(jī)。在不考慮未標(biāo)記樣本的情況下，支持向量機(jī)嘗試尋找最大間隔劃分超平面。在考慮未標(biāo)記樣本后，S3VM嘗試尋找能夠劃分開兩類有標(biāo)記樣本，且可以通過低密度區(qū)域分割將它們分開的超平面，如圖所示，其中“+”和“-”分別表示有標(biāo)記的正例和反例，藍(lán)色點(diǎn)表示未標(biāo)記樣本。9

11.2.2半監(jiān)督SVM10

在傳統(tǒng)的支持向量機(jī)有監(jiān)督學(xué)習(xí)中，我們試圖找到超平面的分割點(diǎn)，使得兩個(gè)半監(jiān)督學(xué)習(xí)點(diǎn)之間的距離很小。S3VM考慮了超平面通過區(qū)域的情況，S3VM的主要思想是將每個(gè)標(biāo)記樣本分為陽性樣本和陰性樣本。首先利用標(biāo)記樣本集和初始支持向量機(jī)進(jìn)行訓(xùn)練，然后利用機(jī)器對未標(biāo)記樣本進(jìn)行標(biāo)記，使所有樣本穩(wěn)定然后采用局部迭代搜索最優(yōu)策略。

11.2.3圖半監(jiān)督學(xué)習(xí)基于圖的半監(jiān)督學(xué)習(xí)方法是一種利用數(shù)據(jù)集的圖結(jié)構(gòu)進(jìn)行學(xué)習(xí)的技術(shù)。其主要思想是通過構(gòu)建一個(gè)圖來表示數(shù)據(jù)集，其中節(jié)點(diǎn)代表標(biāo)記和未標(biāo)記的數(shù)據(jù)點(diǎn)，邊表示數(shù)據(jù)點(diǎn)之間的相似性或關(guān)聯(lián)關(guān)系。通過賦予邊權(quán)重來度量數(shù)據(jù)點(diǎn)的相似性，權(quán)重越大表示相似性越高。在該方法中，如果兩個(gè)樣本之間的相似度較高，就可以將它們映射到相應(yīng)的節(jié)點(diǎn)上。通過給已標(biāo)記的樣本節(jié)點(diǎn)著色，未標(biāo)記的樣本節(jié)點(diǎn)不著色，可以觀察到節(jié)點(diǎn)的顏色分布情況，從而進(jìn)行半監(jiān)督學(xué)習(xí)。11

11.2.3圖半監(jiān)督學(xué)習(xí)基于圖的半監(jiān)督學(xué)習(xí)方法通常包括以下步驟：1）構(gòu)建圖：根據(jù)數(shù)據(jù)集的相似性，構(gòu)建一個(gè)圖結(jié)構(gòu)，其中節(jié)點(diǎn)表示數(shù)據(jù)點(diǎn)，邊表示相似性關(guān)系。2）賦權(quán)重：為圖中的邊賦予權(quán)重，以度量數(shù)據(jù)點(diǎn)之間的相似性，常用的距離度量有歐幾里德距離、馬氏距離、切比雪夫距離等。3）標(biāo)記節(jié)點(diǎn)：將已標(biāo)記的樣本節(jié)點(diǎn)著色，表示其已知類別信息。4）擴(kuò)散過程：通過圖的結(jié)構(gòu)和節(jié)點(diǎn)的顏色信息，將標(biāo)記信息擴(kuò)散到未標(biāo)記的節(jié)點(diǎn)上，以獲得它們的預(yù)測標(biāo)簽。5）分類或回歸：使用已標(biāo)記和預(yù)測標(biāo)記的節(jié)點(diǎn)進(jìn)行分類或回歸任務(wù)。12

11.2.4基于分歧的方法基于分歧的方法使用多學(xué)習(xí)器，而學(xué)習(xí)器之間的“分歧”的決策，就需要用到未標(biāo)記數(shù)據(jù)。在某些應(yīng)用任務(wù)中，一個(gè)數(shù)據(jù)集可能包含多個(gè)屬性集，此時(shí)每個(gè)數(shù)據(jù)樣本同時(shí)擁有多個(gè)特征向量描述；這里的每個(gè)屬性集即被稱為數(shù)據(jù)的一個(gè)“視圖（View）”。基于分歧的半監(jiān)督學(xué)習(xí)的起源、也是最著名的代表性方法是“協(xié)同訓(xùn)練法”，由于最初的設(shè)計(jì)是針對多視圖數(shù)據(jù)的，所以也被看作是多視圖學(xué)習(xí)的代表。協(xié)同訓(xùn)練法要求數(shù)據(jù)具有兩個(gè)充分冗余且滿足條件獨(dú)立性的視圖，“充分”是指每個(gè)視圖都包含足夠產(chǎn)生最優(yōu)學(xué)習(xí)器的信息，此時(shí)對其中任一視圖來說，另一個(gè)視圖則是“冗余”的；同時(shí)，對類別標(biāo)記來說這兩個(gè)視圖條件獨(dú)立。13

11.2.4基于分歧的方法協(xié)同訓(xùn)練法的學(xué)習(xí)過程：首先分別在每個(gè)視圖上利用有標(biāo)記樣本訓(xùn)練一個(gè)分類器，然后，每個(gè)分類器從未標(biāo)記樣本中挑選若干標(biāo)記置信度（即對樣本賦予正確標(biāo)記的置信度）高的樣本進(jìn)行標(biāo)記，并把這些“偽標(biāo)記”樣本（即其標(biāo)記是由學(xué)習(xí)器給出的）加入另一個(gè)分類器的訓(xùn)練集中，以便對方利用這些新增的有標(biāo)記樣本進(jìn)行更新。這個(gè)“互相學(xué)習(xí)、共同進(jìn)步”的過程不斷迭代進(jìn)行下去，直到兩個(gè)分類器都不再發(fā)生變化，或達(dá)到預(yù)先設(shè)定的學(xué)習(xí)輪數(shù)為止。1411.3半監(jiān)督聚類半監(jiān)督聚類是一種結(jié)合了無監(jiān)督學(xué)習(xí)和半監(jiān)督學(xué)習(xí)思想的聚類方法。它利用有限的標(biāo)記數(shù)據(jù)和大量的未標(biāo)記數(shù)據(jù)，通過將樣本分組成不同的簇來發(fā)現(xiàn)隱藏在數(shù)據(jù)中的結(jié)構(gòu)和模式。傳統(tǒng)的聚類算法通常只利用未標(biāo)記數(shù)據(jù)進(jìn)行無監(jiān)督學(xué)習(xí)，而半監(jiān)督聚類則通過引入標(biāo)記數(shù)據(jù)的先驗(yàn)知識或約束條件來指導(dǎo)聚類過程，從而提高聚類的準(zhǔn)確性和魯棒性。15這類方法使用用戶提供的標(biāo)簽或先驗(yàn)知識作為約束條件來指導(dǎo)聚類過程。常見的約束條件包括“必連”和“勿連”關(guān)系，即將兩個(gè)樣本標(biāo)記為必須屬于同一簇或不能屬于同一簇?；诩s束的方法通常通過優(yōu)化目標(biāo)函數(shù)來確保盡量滿足約束條件。具體可以分為如下幾種：

11.3.1基于約束的方法讓樣本無條件滿足給定的約束條件引入懲罰因子（或罰參數(shù)）施加獨(dú)立的類標(biāo)簽（或種子集）作為約束16約束K均值聚類算法的基本過程：1）初始化：選擇初始的K個(gè)聚類中心。2）聚類分配：根據(jù)當(dāng)前的聚類中心，將每個(gè)樣本分配到最近的聚類中心所代表的簇。3）約束調(diào)整：根據(jù)給定的約束信息，對聚類結(jié)果進(jìn)行調(diào)整?？梢愿鶕?jù)約束條件來判斷當(dāng)前的聚類結(jié)果是否滿足要求，并對不符合約束的樣本進(jìn)行調(diào)整。調(diào)整的具體方式可以根據(jù)具體約束的特點(diǎn)而定，例如將不滿足約束的樣本重新分配到合適的簇中。4）更新聚類中心：根據(jù)調(diào)整后的聚類結(jié)果，更新每個(gè)簇的聚類中心。5）重復(fù)步驟2至步驟4，直到滿足停止條件（例如達(dá)到最大迭代次數(shù)或聚類結(jié)果不再變化）。

11.3.1基于約束的方法17基于距離的半監(jiān)督聚類方法是一種常見的半監(jiān)督聚類算法，它結(jié)合了無標(biāo)簽數(shù)據(jù)和有標(biāo)簽數(shù)據(jù)中的距離信息，來指導(dǎo)聚類過程。通常情況下，已知標(biāo)簽數(shù)據(jù)會提供一些關(guān)于簇之間相對位置或距離的先驗(yàn)知識，從而有助于更準(zhǔn)確地分配無標(biāo)簽數(shù)據(jù)到相應(yīng)的簇中。

11.3.2基于距離的方法18基于距離的半監(jiān)督聚類方法的一般步驟：1）初始化：選擇初始的聚類中心。2）聚類分配：根據(jù)當(dāng)前的聚類中心，將每個(gè)無標(biāo)簽樣本分配到最近的聚類中心所代表的簇。3）標(biāo)簽約束：使用已知標(biāo)簽數(shù)據(jù)來調(diào)整聚類結(jié)果。可以通過計(jì)算帶標(biāo)簽數(shù)據(jù)和無標(biāo)簽數(shù)據(jù)之間的距離，然后將這些距離作為約束引入聚類過程。可以根據(jù)已知標(biāo)簽數(shù)據(jù)的信息，對聚類中心進(jìn)行調(diào)整，或者調(diào)整樣本之間的距離度量方式，以更好地滿足先驗(yàn)的標(biāo)簽約束。4）更新聚類中心：根據(jù)調(diào)整后的聚類結(jié)果，更新每個(gè)簇的聚類中心。5）重復(fù)步驟2至步驟4，直到滿足停止條件（例如達(dá)到最大迭代次數(shù)或聚類結(jié)果不再變化）。

11.3.2基于距離的方法19常見的基于距離的半監(jiān)督聚類方法可以分為以下三種：基于凸優(yōu)化問題調(diào)整樣本間的距離基于最短路徑算法調(diào)節(jié)樣本之間的距離基于譜聚類方法，通過約束信息來控制樣本之間的距離

11.3.2基于距離的方法20

11.3.2基于約束和距離的方法快速K均值算法（FastK-means）該方法使用已知標(biāo)簽數(shù)據(jù)的信息來調(diào)整樣本之間的距離，從而改善聚類結(jié)果。具體而言，該方法通過引入距離約束，將已知標(biāo)簽數(shù)據(jù)限制在其對應(yīng)的簇附近，并根據(jù)這些約束來更新聚類中心。這樣可以更好地利用已知標(biāo)簽的信息，提高聚類的準(zhǔn)確性。21

11.3.2基于約束和距離的方法快速K均值算法的基本過程：

1）隨機(jī)選擇k個(gè)樣本作為初始聚類中心；2）根據(jù)當(dāng)前的聚類中心，計(jì)算每個(gè)樣本與聚類中心的距離，并將樣本分配給距離最近的聚類中心所對應(yīng)的簇；3）對每個(gè)簇，計(jì)算簇內(nèi)所有樣本的均值，并將該均值作為新的聚類中心；4）重復(fù)執(zhí)行步驟2，步驟3直到收斂，即簇的分配不再改變或達(dá)到最大迭代次數(shù)5）在步驟4中將每個(gè)樣本的簇分配結(jié)果進(jìn)行記錄。22

11.3.2基于約束和距離的方法度量學(xué)習(xí)半監(jiān)督聚類（MetricLearningforSemi-SupervisedClustering）

該方法旨在通過學(xué)習(xí)一個(gè)合適的距離度量來改善聚類質(zhì)量。該方法使用已知標(biāo)簽數(shù)據(jù)的信息來訓(xùn)練一個(gè)度量函數(shù)，使得同一類別樣本之間的距離較小，不同類別樣本之間的距離較大。通過優(yōu)化度量函數(shù)，可以調(diào)整樣本之間的距離，從而更好地聚類數(shù)據(jù)。23

11.3.2基于約束和距離的方法度量學(xué)習(xí)半監(jiān)督聚類算法的基本過程：

1）根據(jù)樣本距離矩陣D構(gòu)建簇關(guān)聯(lián)矩陣A；2）將簇關(guān)聯(lián)矩陣A規(guī)范化得到拉普拉斯矩陣L；3）對拉普拉斯矩陣L進(jìn)行特征分解，得到特征值和特征向量；4）根據(jù)前k個(gè)最小的特征值對應(yīng)的特征向量構(gòu)建新的數(shù)據(jù)表示Z；5）使用K-means聚類算法對新的數(shù)據(jù)表示Z進(jìn)行聚類，得到聚類結(jié)果C。24

11.4