基于標(biāo)簽進(jìn)行度量學(xué)習(xí)的圖半監(jiān)督學(xué)習(xí)算法

呂亞麗，苗鈞重，胡瑋昕

（1.山西財經(jīng)大學(xué)信息學(xué)院，太原 030006；2.計算智能與中文信息處理教育部重點(diǎn)實驗室（山西大學(xué)），太原 030006）

（?通信作者電子郵箱sxlvyali@126.com）

0 引言

隨著機(jī)器學(xué)習(xí)算法的迅猛發(fā)展，其應(yīng)用領(lǐng)域也越來越廣泛，需要處理的數(shù)據(jù)也越來越復(fù)雜。由于標(biāo)簽數(shù)據(jù)有標(biāo)準(zhǔn)或最優(yōu)的輸出，所以在算法中可以很好地構(gòu)建目標(biāo)函數(shù)用于求解模型參數(shù)。然而，大數(shù)據(jù)環(huán)境下，標(biāo)簽信息有限，許多無標(biāo)簽數(shù)據(jù)唾手可得，但要想獲得它們的標(biāo)簽信息卻需要付出高昂的人工成本［1］。因此，如何同時利用少量標(biāo)簽數(shù)據(jù)與大量無標(biāo)簽數(shù)據(jù)提高模型的分類性能這一問題顯得越來越重要。尤其是在學(xué)習(xí)過程中，如何降低模型學(xué)習(xí)對標(biāo)簽樣本的需求量，同時又可以提高學(xué)習(xí)性能，成為了一個非常重要的研究問題［2-3］。近些年，涌現(xiàn)出大量關(guān)于半監(jiān)督學(xué)習(xí)的研究工作并取得了較好效果［4］，其中包括較為熱點(diǎn)的圖半監(jiān)督學(xué)習(xí)算法，其任務(wù)可以轉(zhuǎn)換為一個凸優(yōu)化問題，從而可以求得全局最優(yōu)解［5］。

半監(jiān)督學(xué)習(xí)算法大致可以分為直推式學(xué)習(xí)和歸納學(xué)習(xí)兩類［4］。直推式學(xué)習(xí)是指根據(jù)標(biāo)簽數(shù)據(jù)推斷數(shù)據(jù)集中無標(biāo)簽樣本的類別的算法。歸納學(xué)習(xí)是指同時利用標(biāo)簽數(shù)據(jù)和無標(biāo)簽數(shù)據(jù)訓(xùn)練出一個分類器，再將其用于分類未知樣本的算法。

基于圖的半監(jiān)督學(xué)習(xí)屬于直推式學(xué)習(xí)的一種，是基于局部假設(shè)和全局假設(shè)來進(jìn)行的，局部假設(shè)為鄰近的樣本應(yīng)該具有相同的類標(biāo)簽［6］，全局假設(shè)是在同一結(jié)構(gòu)中的樣本應(yīng)該具有相同的類標(biāo)簽?；趫D的半監(jiān)督學(xué)習(xí)可以總結(jié)為將數(shù)據(jù)中少數(shù)的標(biāo)簽進(jìn)行傳播，利用大量的無標(biāo)簽數(shù)據(jù)進(jìn)行樣本空間的結(jié)構(gòu)識別［7］。

大多數(shù)基于圖的半監(jiān)督學(xué)習(xí)算法包含兩個步驟：一是通過計算樣本間的距離或相似性度量來構(gòu)建相似度矩陣。每個樣本可以看作是圖中的一個節(jié)點(diǎn)，樣本間的相似度可以看作是圖中節(jié)點(diǎn)間連邊的權(quán)重［8］。權(quán)重越大表示這兩個樣本具有相同標(biāo)簽的概率就越大。二是根據(jù)得出的相似度矩陣來預(yù)測無標(biāo)簽樣本的所屬類別。

目前，第一步已有工作在構(gòu)建相似度矩陣方面的算法有：k-近鄰（k-Nearest Neighbor，KNN）、ε近鄰（ε-neighbor）［9］、熱核方法（heat kernel）［10］、局部線性表示（local linear representation）［8，11］、低秩表示（Subspace Segmentation by Low Rank Representation，S2LRR）［12］以及稀疏表示（sparse representation）［13-15］等。其中，KNN方法在構(gòu)建相似度矩陣時，選擇距離每個樣本點(diǎn)最近的k個樣本點(diǎn)作為其鄰居，據(jù)此構(gòu)建樣本間相似度矩陣。在該方法中，通常測量的是樣本間的歐氏距離，超參數(shù)k的選擇非常重要，k過大過小均不能正確反映出樣本間的相似性。在ε-neighbor方法中，通過設(shè)定閾值來篩選對應(yīng)樣本的鄰居來構(gòu)建相似度矩陣，該方法中閾值的選擇尤為重要。而heat kernel［10］、local linear representation［8，11］、low rank representation［12］以及sparse representation［13-15］這四種方法基本原理是通過不同的核方法來度量樣本間相似性，對于不同的核方法，均涉及超參數(shù)，這些參數(shù)決定了模型復(fù)雜度從而決定樣本間的相似性度量是否合適。此外，文獻(xiàn)［16］基于非負(fù)矩陣分解與概念分解提出了一種基于數(shù)據(jù)表示的圖半監(jiān)督學(xué)習(xí)算法。然而，上述算法基本采用了歐氏距離作為樣本間相似性度量的核心方法，且其度量方式相對固定，這樣對于不同數(shù)據(jù)采用不同的度量靈活性和適應(yīng)性相對較差。

第二步預(yù)測標(biāo)簽方面的標(biāo)簽傳播算法有：高斯場與調(diào)和函數(shù)（Gaussian Fields and Harmonic Functions，GFHF）［17］、局部和全局一致性（Local and Global Consistency，LGC）方法［6］以及特殊標(biāo)簽傳播（Special Label Propagation，SLP）算法［18］等。其中，GFHF 方法是利用高斯核來度量樣本間的相似度，使用調(diào)和函數(shù)來進(jìn)行標(biāo)簽傳播，在調(diào)和函數(shù)中：對于標(biāo)簽數(shù)據(jù)，函數(shù)值為其標(biāo)簽值；對于無標(biāo)簽數(shù)據(jù)，函數(shù)值為標(biāo)簽其類別歸屬的權(quán)重平均值。這種方法的優(yōu)點(diǎn)在于優(yōu)化問題，具有良好的數(shù)學(xué)性質(zhì)，且具有閉式解。LGC方法基于流形正則化思想，通過構(gòu)造一個相對平滑的分類目標(biāo)函數(shù)，來實現(xiàn)標(biāo)簽傳播過程中盡可能使得處于同一類簇結(jié)構(gòu)中的樣本具有相同的標(biāo)簽。此外，文獻(xiàn)［19］提出了一種基于流形的可解釋性的圖半監(jiān)督學(xué)習(xí)算法；文獻(xiàn)［20］從圖形信號處理的角度考慮了標(biāo)簽傳播，提出了一種廣義標(biāo)簽傳播算法。而這些標(biāo)簽傳播算法的標(biāo)簽傳播過程與第一階段的樣本相似性度量過程是分離的，且對于中間結(jié)果的利用不夠充分。

基于上述問題，本文提出了基于標(biāo)簽進(jìn)行度量學(xué)習(xí)的圖半監(jiān)督學(xué)習(xí)算法（Semi-Supervised Learning algorithm of graph based on label Metric Learning，ML-SSL）。具體地，將在構(gòu)建相似度矩陣與標(biāo)簽傳播過程中均充分利用寶貴的標(biāo)簽信息。同時，利用標(biāo)簽傳播過程中的中間結(jié)果來不斷更新相似性度量方式，通過不斷迭代優(yōu)化調(diào)整相似性度量與標(biāo)簽傳播，進(jìn)而提升標(biāo)簽預(yù)測性能，提高分類準(zhǔn)確率。本文提出的算法不僅使得樣本間相似性度量更加準(zhǔn)確，而且充分利用中間結(jié)果大大降低了對標(biāo)簽數(shù)據(jù)的需求量。最后，通過實驗驗證了本文所提算法在標(biāo)簽數(shù)據(jù)占比極小的情況也可以取得較高的分類準(zhǔn)確率。

1 預(yù)備知識

1.1 基于圖的半監(jiān)督學(xué)習(xí)算法

在基于圖的半監(jiān)督學(xué)習(xí)中，第一步計算樣本間相似度時，已有工作經(jīng)常采用高斯核函數(shù)來進(jìn)行［17-18，21］，如樣本xi與xj的相似度被定義為：

這種方法將樣本間的歐氏距離視作樣本間的相似度，其核心還是歐氏距離，這種度量方式并未用到寶貴的標(biāo)簽信息，這樣不僅導(dǎo)致了標(biāo)簽信息的浪費(fèi)，而且使得相似性度量不精確。

基于圖的半監(jiān)督學(xué)習(xí)算法在進(jìn)行標(biāo)簽傳播時采用的思想是：相似度大的樣本應(yīng)該具有相同的標(biāo)簽。通常會先構(gòu)建標(biāo)簽向量，如某一任務(wù)中共有K個類別的數(shù)據(jù)，其中某一樣本屬于第m類，那么該樣本所對應(yīng)的標(biāo)簽向量為(0，0，…，1，…，0)，即向量中除第m個元素為1外，其余元素均為0，同時還規(guī)定標(biāo)簽向量中所有元素之和為1。可以把標(biāo)簽向量中每一個位置上的元素看成是對應(yīng)樣本屬于某一類的概率，當(dāng)兩個樣本間的相似度sij較大時，樣本xi與xj所對應(yīng)的標(biāo)簽向量應(yīng)盡可能地相似，即其歐氏距離要盡可能小。也就是將每一個樣本點(diǎn)看作圖中的一個節(jié)點(diǎn)，樣本間的相似度看作是節(jié)點(diǎn)間連邊的權(quán)重。然后，找到最合適的切割方式把整個圖分成K個子圖，使得各個子圖所包含的邊的權(quán)重之和最大，同時使得被切割掉的邊的權(quán)重之和最小。

1.2 度量學(xué)習(xí)

許多機(jī)器學(xué)習(xí)算法很大程度上依賴于樣本間的度量方式，一個合適的度量方式不僅可以使得學(xué)習(xí)的結(jié)果更加準(zhǔn)確，而且可以使得學(xué)習(xí)過程更加便捷。大多數(shù)算法采用了固定的度量方式，常見的度量方式有歐氏距離、曼哈頓距離、推土機(jī)距離、切比雪夫距離等。還有一些算法是首先在原始樣本空間上進(jìn)行特征選擇，然后在特征空間上進(jìn)行固定形式的距離度量。

那么，如何根據(jù)實際問題或面對不同的數(shù)據(jù)進(jìn)行不同方式的度量？面對這一問題，研究者們提出了很多度量學(xué)習(xí)方法：大邊界最近鄰算法［22］、基于密度加權(quán)的大邊界最近鄰分類算法［23］、基于余弦距離的度量學(xué)習(xí)算法等。

許多度量學(xué)習(xí)方法中采用了馬氏距離作為度量的函數(shù)形式，根據(jù)樣本相似性計算具體的度量參數(shù)值。其度量公式被定義為：

其中，矩陣A滿足半正定。當(dāng)A為單位矩陣時，該距離就變成了歐氏距離。

接下來根據(jù)樣本間的相似度來計算A矩陣［24］。設(shè)M為相似樣本對集合，D為不相似樣本對集合。按相似樣本之間的距離應(yīng)盡可能小的原則，構(gòu)建如下優(yōu)化問題：

約束條件是為了避免所有的數(shù)據(jù)都集中到一個點(diǎn)這種極端情況的出現(xiàn)。該問題為一個凸優(yōu)化問題，可以求得全局最優(yōu)解。

若采用拉格朗日對偶性進(jìn)行求解，其時間復(fù)雜度為O(n6)，空間復(fù)雜度為O(n2)。上述問題也可被轉(zhuǎn)化為如下等價問題［24］來求解：

此時，可以使用梯度下降法對目標(biāo)函數(shù)進(jìn)行求解。用迭代優(yōu)化的方式來使得A滿足約束條件。

具體的距離度量學(xué)習(xí)（Distance Metric Learning，DML）求解思路如算法1所示。

2 基于DML的圖半監(jiān)督學(xué)習(xí)方法

本文主要利用標(biāo)簽信息進(jìn)行相似性的度量學(xué)習(xí)，進(jìn)而提出基于標(biāo)簽進(jìn)行度量學(xué)習(xí)的圖半監(jiān)督學(xué)習(xí)算法。因此，本章首先給定相似性度量方式，進(jìn)而構(gòu)建相似度矩陣；其次，基于該相似性矩陣進(jìn)行標(biāo)簽傳播；接著，基于信息熵確定前k個相對確定的樣本標(biāo)簽；然后，再加入新學(xué)出的標(biāo)簽信息進(jìn)行相似性度量學(xué)習(xí)；最后，構(gòu)建相似性矩陣和標(biāo)簽傳播等，如此迭代，直至學(xué)出所有標(biāo)簽信息。

2.1 相似度矩陣的構(gòu)建

給定一個包含n個樣本的數(shù)據(jù)集X={x1，x2，…，xl，xl+1，…，xn}，具體包含l個具有標(biāo)簽的數(shù)據(jù)和u=n-l個無標(biāo)簽數(shù)據(jù)。給定一個標(biāo)簽集Y={1，2，…，C}表示有C個類。其中xi∈Rd（i=1，2，…，n），這里d表示數(shù)據(jù)的維度。

為了構(gòu)建相似度矩陣S={sij}n×n，定義樣本xi與xj的相似度為：

從概率角度看，sij可看作是xi選擇xj作為自己鄰居的概率，若記pj|i=sij，則pj|i為以xi為中心、單位矩陣I為協(xié)方差矩陣的高斯分布的概率密度［25］。

2.2 基于相似度矩陣的標(biāo)簽傳播

當(dāng)確定了樣本間的相似度矩陣后，接下來根據(jù)相似度矩陣進(jìn)行標(biāo)簽傳播，給每個樣本xi一個標(biāo)簽向量fi，若i≤l，則：

即若樣本xi屬于第j類，則標(biāo)簽向量第j個元素為1，其余均為0。若i>l，則fi為零向量。根據(jù)相似度大的樣本的標(biāo)簽向量應(yīng)比相似度小的樣本的標(biāo)簽向量更相似的原則，本文也將標(biāo)簽傳播定義為下述的優(yōu)化問題：

這個最優(yōu)化問題與下述的問題等價［17］：

式中：F∈Rn×c，其第i行表示第i個樣本的標(biāo)簽向量。為方便起見，定義F={Fl，F(xiàn)u}，F(xiàn)l表示標(biāo)簽數(shù)據(jù)所對應(yīng)的標(biāo)簽矩陣，F(xiàn)u表示無標(biāo)簽數(shù)據(jù)的標(biāo)簽矩陣，目標(biāo)是求解Fu。LS=D-S為一個拉普拉斯矩陣，S為相似度矩陣，D為對角矩陣，其第i個對角元素Dii=∑jsij。

現(xiàn)對L矩陣進(jìn)行分塊：

對于樣本xi的標(biāo)簽向量fi={pi1，pi2，…，piC}，其中pij可以看作xi屬于第j類的概率，在標(biāo)簽傳播過程中，樣本的標(biāo)簽向量可以體現(xiàn)出樣本所屬類別的不確定性程度，用標(biāo)簽向量的熵來作為這種不確定性的度量，即：

熵值越小則說明所對應(yīng)樣本的所屬類別更加明確。低熵值樣本將在后續(xù)的標(biāo)簽傳播過程中改進(jìn)樣本間的度量，使得傳播更加準(zhǔn)確。

2.3 迭代更新

在半監(jiān)督標(biāo)簽傳播過程中，每次從學(xué)出的標(biāo)簽中篩選出分類準(zhǔn)確率高的前k個新標(biāo)簽樣本，即前k個低熵樣本信息，利用它們進(jìn)行距離度量矩陣的更新，以此來進(jìn)行下一輪標(biāo)簽傳播。在此過程中，樣本間相似性度量不斷地向著更加準(zhǔn)確的方向變化著。從另一方面考慮，不同的相似性度量方式體現(xiàn)了不同的樣本結(jié)構(gòu)的分布形式。如果樣本的分布更加明確，算法的分類效果就會有大幅提升。本文正是基于這一點(diǎn)設(shè)計了迭代優(yōu)化的算法不斷加強(qiáng)樣本空間的結(jié)構(gòu)識別，從而提升學(xué)習(xí)效果。

2.4 算法描述

基于上述內(nèi)容，本節(jié)給出了迭代優(yōu)化的算法——基于標(biāo)簽進(jìn)行度量學(xué)習(xí)的圖半監(jiān)督學(xué)習(xí)算法（ML-SSL），具體偽代碼描述如算法2所示。

算法2 中，第2）～4）行是初始的各個量的計算，包括初始化距離度量矩陣A、相似樣本對集合M、標(biāo)簽向量矩陣Fu以及計算無標(biāo)簽樣本的熵值。接著，算法進(jìn)行迭代優(yōu)化，通過低熵值樣本與距離度量矩陣的相互作用影響彼此。循環(huán)終止的條件可以是距離度量矩陣A收斂，此時說明樣本間的相似度已達(dá)到了最佳穩(wěn)定狀態(tài)，也可以是根據(jù)實際情況設(shè)定迭代次數(shù)。

3 實驗與結(jié)果分析

本章設(shè)計如下實驗驗證本文所提算法的可行性和分類性能。實驗主要分為三部分：首先，詳細(xì)分析k值的選取情況；然后，在人造數(shù)據(jù)集上進(jìn)行分類性能驗證與分析；最后，在真實數(shù)據(jù)集上進(jìn)行對比分析和驗證。本文采用的對比算法包括LGC、GFHF 和S2LRR 三種，這三種方法均為半監(jiān)督學(xué)習(xí)領(lǐng)域的經(jīng)典算法；然而，在算法執(zhí)行中均未利用中間結(jié)果，且在樣本間相似性度量時未用到標(biāo)簽信息。通過實驗結(jié)果可以看出，本文算法具有很大的競爭優(yōu)勢。

3.1 實驗環(huán)境與數(shù)據(jù)集

本文實驗所用的硬件環(huán)境為：Windows 10，CPU 主頻為2.00 GHz，運(yùn)行內(nèi)存為8 GB，CPU型號為AMD A8-6410。

本文采用的人造數(shù)據(jù)集為一個雙月型數(shù)據(jù)集，該數(shù)據(jù)集有上下兩個半圓形，分別表示由兩個類組成。每類包含100個二維樣本，其中每個樣本由兩個實數(shù)描述其特征。該數(shù)據(jù)集屬于非凸型數(shù)據(jù)集。從算法的二維結(jié)果可以展示其對數(shù)據(jù)空間結(jié)構(gòu)的識別能力，具體如圖1所示。

圖1 雙月型數(shù)據(jù)集Fig.1 Two-moon dataset

采用的真實數(shù)據(jù)集有Breast、German、Ionosphere、Vote、Heart、Monkl 共6 個，全部來自于UCI。詳細(xì)信息如表1所示。

表1 來自于UCI的真實數(shù)據(jù)集Tab.1 Real datasets from UCI

3.2 度量指標(biāo)和參數(shù)

實驗采用分類準(zhǔn)確率作為評價指標(biāo)，即將數(shù)據(jù)集中無標(biāo)簽數(shù)據(jù)的真實標(biāo)簽yi與算法學(xué)習(xí)的預(yù)測標(biāo)簽i作比較，分類準(zhǔn)確率acc為：

其中：Xu為無標(biāo)簽數(shù)據(jù)集；|Xu|為該集合所包含的樣本量。

除了分類準(zhǔn)確率外，還增加了一項標(biāo)簽樣本占比的數(shù)據(jù)。實驗通過這兩項指標(biāo)來說明本文所提算法在提高分類準(zhǔn)確率方面的優(yōu)勢，從不同數(shù)據(jù)集的對比中可以體現(xiàn)所提算法的魯棒性。

實驗中，算法的參數(shù)設(shè)置為最大迭代次數(shù)n=20、判斷度量矩陣A收斂的ε=0.01，即，則認(rèn)為A收斂，設(shè)置低熵樣本個數(shù)k=5。

3.3 k值對分類結(jié)果的影響

本文對k值的選擇是通過在6 個真實數(shù)據(jù)集上進(jìn)行交叉驗證得出，具體是分別在每個數(shù)據(jù)集上隨機(jī)分配12 個標(biāo)簽，然后分別取k=2、k=5、k=10 進(jìn)行交叉驗證，具體結(jié)果如表2所示。

表2 交叉驗證實驗結(jié)果Tab.2 Experimental results of cross-validation

從表2 可以看出，當(dāng)k=5 時分類效果最佳，具體見表中加粗部分。這是由于k的選擇會對低熵值樣本改進(jìn)距離度量矩陣產(chǎn)生影響。具體地，當(dāng)k=2，即取較小的值時，算法將會退化成固定度量方法，每次迭代所選出的確定性樣本基本保持不變。當(dāng)k=10，即取較大的值時，學(xué)習(xí)過程將會引入確定性較低的無標(biāo)簽樣本，這樣的樣本對于距離度量矩陣的學(xué)習(xí)來說屬于噪聲影響。

3.4 人造數(shù)據(jù)集上的實驗驗證與分析

在人造數(shù)據(jù)集上，通過隨機(jī)地為每類樣本分配一定數(shù)量的標(biāo)簽來進(jìn)行對比實驗。這里分別隨機(jī)地給每個類分配1、3、5、7、9 個標(biāo)簽，使用本文所提算法2 進(jìn)行其余標(biāo)簽的學(xué)習(xí)。具體學(xué)習(xí)結(jié)果如圖2～6 所示，每個圖中子圖（a）是初始數(shù)據(jù)集（initial data），圖中正方形和倒三角分別表示兩類標(biāo)簽數(shù)據(jù)點(diǎn)，圓形表示無標(biāo)簽數(shù)據(jù)點(diǎn)；子圖（b）為運(yùn)用所提算法2 的分類結(jié)果（result）。

圖2 每類樣本具有1個標(biāo)簽的分類結(jié)果Fig.2 Classification results of each class with one label

由圖2～6可以得出：

1）本文所提算法在標(biāo)簽樣本占比很小的情況下就可以得出較好的分類結(jié)果。

2）本文算法隨標(biāo)簽樣本數(shù)的增加分類效果明顯增強(qiáng)，尤其是對每類數(shù)據(jù)尾部的樣本分類，即從實驗結(jié)果可以看出，分類錯誤的樣本主要集中在每個類的尾部。隨著標(biāo)簽樣本數(shù)的提升，本文的算法加強(qiáng)了對尾部數(shù)據(jù)的分類能力。

圖3 每類樣本具有3個標(biāo)簽的分類結(jié)果Fig.3 Classification results of each class with three labels

圖4 每類樣本具有5個標(biāo)簽的分類結(jié)果Fig.4 Classification results of each class with five labels

圖5 每類樣本具有7個標(biāo)簽的分類結(jié)果Fig.5 Classification results of each class with seven labels

圖6 每類樣本具有9個標(biāo)簽的分類結(jié)果Fig.6 Classification results of each class with nine labels

3.5 真實數(shù)據(jù)集上的實驗及其結(jié)果分析

在6 個真實數(shù)據(jù)集上對本文算法（ML-SSL）進(jìn)行實驗驗證，并與LGC［6］、GFHF［17］以及S2LRR［2］這3 種半監(jiān)督學(xué)習(xí)算法進(jìn)行實驗對比。每個數(shù)據(jù)集上類別數(shù)為2，隨機(jī)地給每個類分配2、4、6、8、10個標(biāo)簽，則每個數(shù)據(jù)集分別分配4、8、12、16、20。4 種算法在不同數(shù)據(jù)集、不同標(biāo)簽數(shù)下的分類結(jié)果具體如表3 所示。其中，粗體表示每種情況下取得的最高分類準(zhǔn)確率。

另外，隨著標(biāo)簽樣本數(shù)的增加，4 種算法取得的分類準(zhǔn)確率變化如圖7 所示，子圖（a）～（f）分別代表Breast、German、Ionosphere、Vote、Heart以及Monkl數(shù)據(jù)集上二者間的關(guān)系。

圖7 不同數(shù)據(jù)集上標(biāo)簽數(shù)量與不同算法分類準(zhǔn)確率的關(guān)系Fig.7 Relationship between number of labels and classification accuracy of different algorithms on different datasets

表3 真實數(shù)據(jù)集上的分類準(zhǔn)確率Tab.3 Classification accuracy on real datasets

由表3和圖7可以得出：

1）除German 數(shù)據(jù)集上已知標(biāo)簽數(shù)是4 的情況外，其余情況下本文所提算法均取得了最高的分類準(zhǔn)確率，即本文所提算法在6 個數(shù)據(jù)集上準(zhǔn)確率最高的情況占比達(dá)到96.7%（29/30）。具體的，在Breast數(shù)據(jù)上，本文算法相較其他3種算法在準(zhǔn)確率上平均提高了16.72 個百分點(diǎn)；在German 數(shù)據(jù)集上提高了14.79 個百分點(diǎn)；在Ionosphere 數(shù)據(jù)集上提高了11.84 個百分點(diǎn)；在Vote 數(shù)據(jù)集上提高了26.37 個百分點(diǎn)；在Heart 數(shù)據(jù)集上提高了16.55 個百分點(diǎn)；在Monkl 數(shù)據(jù)集上提高了9.62 個百分點(diǎn)。由此可見，本文所提算法在絕大多數(shù)情況下的分類準(zhǔn)確率均優(yōu)于其他3種算法。

2）每個數(shù)據(jù)集上已知標(biāo)簽比例范圍為［0.001 7，0.074 1］，可見本文所提算法在已知標(biāo)簽比例很低的情況下便可取得相較于其他3 種算法更高的分類準(zhǔn)確率。在Breast數(shù)據(jù)集上當(dāng)標(biāo)簽數(shù)為20、標(biāo)簽占比僅為0.029 3 時，分類準(zhǔn)確率達(dá)到了0.965 3；在German 數(shù)據(jù)集中，最高分類準(zhǔn)確率達(dá)到了0.731 6，此時標(biāo)簽占比僅為0.02；在Vote 數(shù)據(jù)集中，在標(biāo)簽占比僅為0.009 2 即不到1%的情況下，本文所提算法的分類準(zhǔn)確率達(dá)到了0.874 7。從上述分析可知，在標(biāo)簽數(shù)極少的情況下，本文所提算法也能實現(xiàn)較高準(zhǔn)確率的分類效果。

3）從圖7 的子圖（a）、（c）、（e）、（f）可以看出，本文所提算法在Breast 數(shù)據(jù)集、Ionosphere 數(shù)據(jù)集、Heart 數(shù)據(jù)集以及Monkl 數(shù)據(jù)集上的分類準(zhǔn)確率隨標(biāo)簽數(shù)的增加而增加。而其他3 種半監(jiān)督學(xué)習(xí)算法，分類準(zhǔn)確率并不隨著標(biāo)簽數(shù)的增加而直線提高，尤其S2LRR 算法，起伏很大。在German 數(shù)據(jù)集和Vote 數(shù)據(jù)集上，通過對比4 種算法所對應(yīng)的曲線也可以明顯看出，本文所提算法比其他3 個算法更加平穩(wěn)，表明了本文算法具有較好的魯棒性。

4 結(jié)語

為更準(zhǔn)確地反映樣本間相似性關(guān)系以及充分利用中間結(jié)果來提高半監(jiān)督學(xué)習(xí)的分類準(zhǔn)確率，本文提出了一種基于標(biāo)簽進(jìn)行度量學(xué)習(xí)的圖半監(jiān)督學(xué)習(xí)算法，利用標(biāo)簽傳播過程中確定性標(biāo)簽樣本來不斷修正樣本間的相似性度量方式。然后，通過迭代算法使得以樣本為節(jié)點(diǎn)、相似度為邊權(quán)重的圖不斷得以優(yōu)化，從而使得標(biāo)簽傳播更加準(zhǔn)確，并通過實驗驗證了所提算法的良好分類性能。接下來，我們進(jìn)一步的研究工作包括該算法的合理性理論分析、計算效率的提高、算法中參數(shù)k的選取方法以及該算法的實際應(yīng)用研究等方面。