呂亞麗，苗鈞重，胡瑋昕

（1.山西財經大學信息學院，太原 030006；2.計算智能與中文信息處理教育部重點實驗室（山西大學），太原 030006）

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

0 引言

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

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

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

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

目前，第一步已有工作在構建相似度矩陣方面的算法有：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方法在構建相似度矩陣時，選擇距離每個樣本點最近的k個樣本點作為其鄰居，據此構建樣本間相似度矩陣。在該方法中，通常測量的是樣本間的歐氏距離，超參數k的選擇非常重要，k過大過小均不能正確反映出樣本間的相似性。在ε-neighbor方法中，通過設定閾值來篩選對應樣本的鄰居來構建相似度矩陣，該方法中閾值的選擇尤為重要。而heat kernel［10］、local linear representation［8，11］、low rank representation［12］以及sparse representation［13-15］這四種方法基本原理是通過不同的核方法來度量樣本間相似性，對于不同的核方法，均涉及超參數，這些參數決定了模型復雜度從而決定樣本間的相似性度量是否合適。此外，文獻［16］基于非負矩陣分解與概念分解提出了一種基于數據表示的圖半監(jiān)督學習算法。然而，上述算法基本采用了歐氏距離作為樣本間相似性度量的核心方法，且其度量方式相對固定，這樣對于不同數據采用不同的度量靈活性和適應性相對較差。

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

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

1 預備知識

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

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

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

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

1.2 度量學習

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

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

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

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

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

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

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

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

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

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

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

2.1 相似度矩陣的構建

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

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

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

2.2 基于相似度矩陣的標簽傳播

當確定了樣本間的相似度矩陣后，接下來根據相似度矩陣進行標簽傳播，給每個樣本xi一個標簽向量fi，若i≤l，則：

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

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

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

現對L矩陣進行分塊：

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

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

2.3 迭代更新

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

2.4 算法描述

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

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

3 實驗與結果分析

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

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

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

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

圖1 雙月型數據集Fig.1 Two-moon dataset

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

表1 來自于UCI的真實數據集Tab.1 Real datasets from UCI

3.2 度量指標和參數

實驗采用分類準確率作為評價指標，即將數據集中無標簽數據的真實標簽yi與算法學習的預測標簽i作比較，分類準確率acc為：

其中：Xu為無標簽數據集；|Xu|為該集合所包含的樣本量。

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

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

3.3 k值對分類結果的影響

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

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

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

3.4 人造數據集上的實驗驗證與分析

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

圖2 每類樣本具有1個標簽的分類結果Fig.2 Classification results of each class with one label

由圖2～6可以得出：

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

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

圖3 每類樣本具有3個標簽的分類結果Fig.3 Classification results of each class with three labels

圖4 每類樣本具有5個標簽的分類結果Fig.4 Classification results of each class with five labels

圖5 每類樣本具有7個標簽的分類結果Fig.5 Classification results of each class with seven labels

圖6 每類樣本具有9個標簽的分類結果Fig.6 Classification results of each class with nine labels

3.5 真實數據集上的實驗及其結果分析

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

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

圖7 不同數據集上標簽數量與不同算法分類準確率的關系Fig.7 Relationship between number of labels and classification accuracy of different algorithms on different datasets

表3 真實數據集上的分類準確率Tab.3 Classification accuracy on real datasets

由表3和圖7可以得出：

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

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

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

4 結語

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