密度峰值隸屬度優化的半監督Self-Training 算法

劉學文，王繼奎+，楊正國，李 冰，聶飛平

1.蘭州財經大學 信息工程學院，蘭州 730020

2.西北工業大學 光學影像分析與學習中心，西安 710072

目前，數據規模大幅增長，但有標簽數據的獲取成本仍然較高，大部分數據只含有少量標簽。不同于監督學習和無監督學習，半監督學習允許利用數據集中的大量無標簽數據和少量有標簽數據。Self-Training 算法是半監督學習算法家族中的一員，其實現方式開放靈活，可以適應多樣的半監督學習任務。

Self-Training 算法在迭代過程中，從無標簽樣本中選取高置信度樣本并由基分類器賦予其標簽，將這些樣本和標簽添加進訓練集，迭代訓練輸出優化后的分類器。然而，如果帶有錯誤標簽的樣本被添加進訓練集，將導致半監督分類性能降低。為降低此類風險，研究者們提出了各種選取高置信度樣本的方法。

文獻[6]提出了編輯自訓練算法（self-training with editing，SETRED），采用割邊權重統計（cut edge weight statistic，CEWS）方法，利用左側檢驗將含有較多割邊的樣本從訓練集中移除，SETRED 算法的計算開銷較大，而且當樣本在相關鄰近圖（relative neighborhood graph，RNG）上的近鄰數量較少或者割邊權重不平衡時，假設檢驗的效果不佳。聚類算法是一種有效的發現樣本潛在信息的方式，它可以從大量無標簽樣本中提取有價值的信息來輔助高置信度樣本的選取。文獻[11]基于聚類假設提出了基于半監督模糊C 均值聚類的自訓練算法（using clustering analysis to improve semi-supervised classification，STSFCM），在Self-Training 迭代過程中嵌入半監督模糊C 均值（semi-supervised fuzzy C-means algorithm，SSFCM）聚類算法，將類簇隸屬度大于設定閾值的樣本作為高置信度樣本。STSFCM 算法從訓練集中移除類簇歸屬確定性低的樣本是一種有效的思路，然而該算法對非球形數據聚類的效果不理想，且易受初始點選擇的影響，因此，有研究者嘗試在Self-Training 算法中嵌入DPC（density peaks clustering）算法。DPC 是一種簡單、快速、有效的聚類算法，它可將任意維度數據映射成二維，利用密度峰值在二維空間內建構數據之間的層次關系，而且對于非球形數據也具有較好的適應性。近年來，DPC 算法的研究熱度不減，文獻[16-20]從密度峰值計算、聚類中心選取和數據點分配等方面提出了改進方法，文獻[21]利用密度峰值對模糊C 均值（fuzzy C-means，FCM）聚類算法中初始聚類中心、類簇數目選擇等過程進行了優化。文獻[22]提出基于數據密度峰值的自訓練半監督分類算法（self-training semi-supervised classification based on density peaks of data，STDP），在DPC 算法發現的層次空間結構中，先標記有標簽樣本的無標簽“前驅”，再標記無標簽“后繼”。文獻[23]通過局部密度閾值將樣本劃分為核心點和邊界點，并依次賦予標簽、添加進訓練集。文獻[24]將STDP 算法與SETRED 算法結合，用CEWS 方法檢驗選取的高置信度樣本，進一步提升了訓練集的質量。

DPC 算法的一個重要創新就是提出“峰值”這一概念，峰值的本質是距離，但峰值帶有密度指示方向——低密度點指向距離其最近的高密度點。密度相對更高的樣本點通常是局部中心點，在Self-Training 迭代過程中，中心點的重要程度比邊緣點更高。因此，本文受DPC 思想的啟發，定義“簇峰值”和“密度峰值隸屬度”，提出密度峰值隸屬度優化的Self-Training 算法（semi-supervised self-training algorithm for density peak membership optimization，STDPM）。STDPM 算法的主要工作如下：

（1）利用DPC 算法密度峰值計算過程中發現的數據潛在空間結構，定義原型樹和近親結點集。

（2）利用近親結點集中的無標簽樣本與不同類別有標簽樣本之間的局部密度與距離關系，定義簇峰值和密度峰值隸屬度。

（3）利用密度峰值隸屬度，選取大于設定閾值的樣本作為高置信度樣本，添加進訓練集，迭代優化分類器。在8 個基準數據集上的實驗結果驗證了STDPM 算法的有效性。

1 相關工作

1.1 符號說明

將本文中常用的符號和相關說明列在表1 中。

表1 STDPM 中的符號Table 1 Notations in STDPM

1.2 Self-Training 算法

Self-Training 算法是一種簡單高效的利用無標簽數據的半監督學習框架，通過在迭代過程中生成“偽標簽”替代真實標簽，達到優化模型的目標。標準的Self-Training 算法通常利用基分類器生成“偽標簽”，最后輸出優化后的分類器，主要過程如下：

（1）在有標簽樣本集中訓練分類器；

（2）從無標簽樣本集中選取一部分高置信度樣本集，并由賦予“偽標簽”；

（3）將添加進中，并從中移除；

（4）返回（1），直至穩定或中沒有樣本時停止，輸出。

在Self-Training 算法中，涉及一個關鍵的問題，即如何選取高置信度樣本，本文主要針對這個問題進行研究。如果高置信度樣本選取不當，“偽標簽”變成“錯誤標簽”會污染訓練集，進而使得分類性能下降。接下來簡要介紹兩種具有代表性的、采用不同高置信度樣本選取方法的Self-Training 算法。

1.3 STSFCM 算法

STSFCM算法利用半監督聚類SSFCM隸屬度選取高置信度樣本，最小化以下目標函數：

其中，有標簽樣本′∈，無標簽樣本″∈，為類簇數，v為第個類簇中心，′為有標簽樣本的隸屬度矩陣，″為無標簽樣本的隸屬度矩陣。

用拉格朗日乘子法，獲得無標簽樣本x″的隸屬度：

SSFCM 基于FCM 算法，利用有標簽樣本的先驗知識改善聚類效果，STSFCM 則通過設定一個閾值，利用SSFCM 的隸屬度改善分類效果，將ξ″≥的無標簽樣本作為高置信度樣本集′，然后在′中訓練支持向量機（support vector machine，SVM），選取SVM 分類器輸出的概率值f≥的樣本作為更高置信度的樣本集″。

1.4 STDPCEW 算法

結合密度峰值和切邊權值的自訓練算法（selftraining algorithm combining density peak and cut edge weight，STDPCEW）在STDP算法的基礎上，結合SETRED算法，采用假設檢驗的方式選取高置信度樣本。

首先，利用DPC 發現樣本的潛在空間結構，找到有標簽樣本的“前驅”樣本集和“后繼”樣本集。

其次，在?中構造相關鄰近圖，圖中頂點滿足條件d≤max(d,d),?≠,，計算內樣本點的割邊權重和J：

其中，W為割邊權重，I的值為0 或1，當x的標簽Y等于x的標簽Y時I=0，否則I=1。J在零假設下服從正態分布(,)，和的計算如下：

其中，p表示樣本標簽為Y的概率。

2 密度峰值隸屬度優化的Self-Training 算法

2.1 原型樹

根據文獻[14]中DPC 算法的定義，給定樣本x的局部密度（截斷核）計算如下：

樣本x的局部密度（高斯核）計算如下：

樣本x的峰值計算如下：

由公式知，峰值是低密度點與距其最近的高密度點之間的距離，其融合了密度與距離信息，由峰值的計算引出原型的定義。

樣本x的原型P定義為：

由公式知，低密度點的原型即為離其最近的高密度點。對于密度最高的點，由于沒有比它密度更高的點，其原型為自身，即P=x,?≠,ρ＞ρ。

由樣本與其原型之間的聯系可以遞歸構造出原型樹，主要過程如下：

（1）確定原型樹的根結點：密度最高的點作為根結點，根結點x須滿足條件?≠,ρ≥ρ。

（2）確定除根結點之外的父結點：x的原型P為其父結點，即x的父結點滿足條件x=P。

隨機生成3 類別的高斯分布樣本，每個類別包含5 個樣本，表2 為樣本的密度峰值和原型等信息。

由表2 中的樣本繪制圖1 中的原型樹。表2 中數值精確到小數點后3 位，為便于比較，每個樣本的和值已經歸一化。根據文獻[14]中的定義，類簇中心為和值均較大的樣本點，因此，和的乘積值較大的點可作為類簇中心。

表2 樣本信息Table 2 Samples information

圖1 樣本分布和原型樹示意圖Fig.1 Samples distribution and illustration of prototype tree

圖1（a）中圓、矩形和六邊形表示不同類別的樣本，箭頭指示樣本點的原型，如樣本13 的原型為樣本11。虛線橢圓內區域為類簇中心區域，由表2 知樣本1、樣本2 和樣本3 的值較大，因此它們分別為各自所在類簇的中心點。

圖1（b）為圖1（a）中樣本的原型樹結構的樹狀示意圖，由表2 知樣本1 的值最大，因此其作為根結點，樣本5 和樣本12 的原型為樣本1，樣本8 的原型為樣本5，樣本2 的原型為樣本12，根據表2 中每個樣本的原型，可以遞歸構造原型樹。

2.2 近親結點集

在原型樹中，任意結點至少存在父結點、子結點或兄弟結點中的一種結點。不同于一般的近鄰關系，由圖1 可知，原型樹上結點的“近鄰”關系是基于峰值的，本文將這種特殊的“近鄰”關系定義為“近親”關系，原型樹中的所有近親構成其近親結點集，給出如下定義。

樣本x的近親結點集R定義為：

由公式知，x的近親結點集即為其父結點、子結點和兄弟結點構成的一個集合。如圖1（b）所示，樣本3 的父結點為樣本2，兄弟結點為樣本9 和15，子結點為樣本7 和11，則樣本3 的近親結點集={,,,,}。

在原型樹上搜索每一個有標簽樣本的近親，獲得近親結點集=??…?R，其中為有標簽樣本的個數。從中移除所有的有標簽樣本，得到有標簽樣本的無標簽近親結點集R=-。

2.3 密度峰值隸屬度

在硬聚類算法中，每個樣本隸屬于某個類簇是確切的，要么屬于某個類簇要么不屬于某個類簇，隸屬度取值為0 或1。而在軟聚類算法中，樣本隸屬于某類簇的隸屬度是模糊的，其取值范圍為[0,1]。

在對類別的數據進行聚類的過程中，如果樣本x的隸屬度U?U,≠,?∈[1,]，則x具有更確切的歸屬，x被分類器誤分的可能性也會更小。反之，如果樣本的隸屬度之間相差較小，則其被誤分的可能性更大。因此，STDPM 通過設定一個閾值，將密度峰值隸屬度大于閾值的樣本作為高置信度樣本，密度峰值隸屬度由簇峰值權重歸一化后得到，先定義簇峰值：

給定樣本x是無標簽近親結點集R內的點，樣本x是有標簽樣本集中的點。樣本x的簇峰值ζ定義為：

其中，表示類簇的個數；y表示樣本x的標簽；C表示第個類的標簽；d表示樣本x與樣本x的歐式距離。

圖2 為簇峰值的計算示意圖。圖2 中不同形狀表示不同的類簇C，有顏色填充形狀表示有標簽樣本，無顏色填充表示無標簽樣本。如圖2 所示，在簇、和中，距樣本11 最近且密度更大的有標簽樣本分別為樣本2、樣本3 和樣本12，則樣本11 對應的簇峰值分別為=，=，=。

圖2 簇峰值計算示意圖Fig.2 Illustration of calculating clusters-peak

由簇峰值計算簇峰值權重，其中為中的最大值，給定樣本x對應第類的簇峰值權重W計算如下：

由公式知，ζ越大，W就越小，樣本x隸屬于第類的概率就越小。將簇峰值權重按行歸一化后得到密度峰值隸屬度，給出如下定義：

給定樣本x是無標簽近親結點集R內的點，樣本x的密度峰值隸屬度ξ定義為：

其中，為ζ中最大值，為ζ中最小值。

無標簽樣本的密度峰值隸屬度，取決于在各類簇中密度比它更高且距離它最近的有標簽樣本，而不是僅取決于離它最近的或者密度比它高的樣本。密度峰值隸屬度充分地利用了樣本的密度和峰值信息，兼顧了數據的全局與局部特性。

2.4 算法描述

密度峰值隸屬度優化的Self-Training算法（STDPM）從無標簽近親結點集中，選取隸屬度值較高的樣本作為高置信度樣本，將其添加到訓練集，迭代訓練分類器。STDPM 算法描述如算法1 所示。

STDPM 算法

2.5 算法分析與討論

令表示輸入樣本的個數，表示維度，表示迭代次數。STDPM 算法計算密度峰值的時間復雜度為()，構造原型樹的時間復雜度為()，計算簇峰值、簇峰值權重和密度峰值隸屬度的時間復雜度為()，因此，STDPM 算法的整體時間復雜度為()。SETRED 和STDPCEW 算法的時間復雜度主要在于構造相關鄰近圖，其整體時間復雜度為()。STDP 算法的時間復雜度主要在于計算密度峰值，其整體時間復雜度為()，STSFCM 算法計算模糊隸屬度的時間復雜度為()，訓練SVM 分類器的復雜度為()，其整體時間復雜度為()。因此，由上述分析可得結論：STDPM 算法的時間復雜度低于SETRED、STSFCM 和STDPCEW 算法，但與STDP 算法一致。STDP、STDPCEW 和STDPM 算法的空間復雜度主要在于計算密度峰值，整體空間復雜度均為()，SETRED 的空間復雜度主要在于構造相關鄰近圖，其整體空間復雜度為()，STSFCM算法的空間復雜度主要在于計算模糊隸屬度和SVM分類器的訓練、預測，其整體空間復雜度為()。

STSFCM 算法在非球形數據上的分類效果不佳，STDPCEW 利用密度峰值發現數據結構，在球形數據上的分類效果較好，但是對于大數據集，其構造相關鄰近圖的時間復雜度高。STDPM 算法也利用密度峰值信息構造原型樹，利用密度峰值隸屬度選取高置信度樣本，不僅適用于非球形數據，而且沒有增加時間復雜度。

3 實驗結果與分析

所有實驗基于64 位的Windows 10 系統、Matlab 2019b，處理器為Intel Core i5，內存為8 GB。實驗涉及的對比算法均參照原文實現，所使用的其他算法均來自Matlab 工具箱。

3.1 對比算法與數據集

選取4 個相關的Self-Training 算法與STDPM 算法進行對比，分別為SETRED、STDP、STDPCEW、STSFCM。

5 個算法均采用最近鄰分類器（nearest neighbor，NN）作為基分類器，各個算法的參數設置如表3所示。因為STSFCM 采用了NN 作為基分類器，所以，其閾值參數只有一個。

表3 參數設置Table 3 Parameters setting

為驗證STDPM 算法的有效性，在選取的8 個基準數據集上進行實驗，數據集信息如表4 所示。其中Banknote、Breast、Hepatitis、Ionosphere、Palm、Segment和Zoo數據集均來源于公開的UCI數據庫（http://archive.ics.uci.edu/ml/index.php），Yale（32×32）數據集來源于公開的耶魯大學人臉數據庫（http://cvc.cs.yale.edu/cvc/prjects/yalefaces/yalefaces.html）。

表4 數據集信息Table 4 Datasets information

表4 中，大部分數據集的維度較高，為便于實驗對比，先將維度大于10 的數據集用PCA 降到10 維，小于10 維的數據集則保持不變。

3.2 分類性能分析

為驗證STDPM 算法的有效性，表3 中5 個對比算法按照設定參數，在表4 的8 個基準數據集上進行實驗。

5 個算法在每個數據集上運行30 次：隨機抽取10%的數據作為有標簽數據，其余90%作為無標簽數據，將這兩類數據作為算法的輸入數據；將不做劃分的原始數據集作為固定測試集，記錄算法最終輸出分類器的測試準確率（Accuracy）和F 分數（F-score）。

計算5 個算法在對應的數據集上的測試準確率和F 分數的均值（mean）與標準差（std），實驗結果如表5 和表6 所示，每個數據集上的最高性能以加粗字體顯示。

由表5 可知，STDPM 在Banknote、Breast、Hepatitis、Ionosphere 數據集上都獲得了最高的分類性能，Accuracy 值分別高出第2 名0.18 個百分點、0.10 個百分點、2.10 個百分點和0.78 個百分點，F-score 值分別高出第2 名0.14 個百分點、0.09 個百分點、2.44 個百分點和0.62 個百分點。因為4 個數據集的數據分布較平衡，所以Accuracy 值和F-score值趨于一致。

表5 在數據集Banknote、Breast、Hepatitis和Ionosphere上的性能（mean±std）Table 5 Performance on Banknote,Breast,Hepatitis and Ionosphere datasets(mean±std) 單位：%

由 表6 可知，STDPM 在Palm、Segment、Yale 和Zoo 數據集上都獲得了最高的分類性能，Accuracy 值分別高出第2 名0.04 個百分點、0.10 個百分點、0.29個百分點和2.81 個百分點，F-score 值分別高出第2 名0.13 個百分點、0.11 個百分點、1.83 個百分點和5.33個百分點。

表6 在數據集Palm、Segment、Yale和Zoo 上的性能（mean±std）Table 6 Performance on Palm,Segment,Yale and Zoo datasets(mean±std) 單位：%

雖然Zoo數據集的數據分布不平衡，但是STDPM的分類性能卻顯著高于其他算法，這表明STDPM 能充分利用密度峰值發現樣本的局部結構信息，提升分類性能。

3.3 有標簽樣本比例對性能的影響

有標簽比例過低會導致監督信息太少，但是增加有標簽數據并不一定會增加有用信息，因此，需要分析有標簽樣本比例對性能的影響。

在表4 中的8 個數據集上進行實驗，初始有標簽比例取值范圍為5%～50%，步長為5%，每個算法均運行30次，記錄Accuracy的平均值。實驗結果如圖3所示，圖中藍色十字實線為STDPM算法的性能表現。

從圖3 可以看出，當有標簽樣本比例小于20%時，在Banknote、Hepatitis、Ionosphere、Yale 數據集上STDPM 能獲得較高的準確率，這是因為STDPM 能在有標簽數據較少的情況下，利用密度峰值信息構造更接近真實數據結構的原型樹，利用密度峰值隸屬度選取出質量更高的樣本添加進訓練集。對于不同的有標簽樣本比例，在Breast、Palm 和Segment 數據集上各個算法的性能表現較為穩定，在Hepatitis、Ionosphere、Yale 和Zoo 數據集上，大部分算法的性能表現波動較大，而STDPM 在8 個數據集上的性能表現相較于對比算法更加平穩。

圖3 不同有標簽樣本比例數據集上的準確率Fig.3 Accuracy on different ratios of labeled datasets

3.4 運行時間分析

表7 為5 個算法在8 個數據集上的平均運行時間（ms）和迭代次數，基分類器均為最近鄰（NN），每個算法按照表3 設定的參數運行30 次。

由表7 可知，在樣本量較多的Banknote、Breast、Palm 和Segment 數據集上，STDPCEW 算法的耗時高、迭代次數多，而SETRED 算法的耗時僅低于STDPCEW 算法但是高于其他3 個算法，因此，這兩個算法并不適用于大規模數據。STSFCM 算法在7個數據集上耗時最低并且迭代次數較少，在較大的數據集上的耗時明顯低于另外4 個算法，這是因為STSFCM 算法在不采用SVM 而采用NN 作為基分類器的情況下復雜度低于其他算法。STDP 算法在7 個數據集上的耗時僅高于STSFCM 算法，而STDPM 算法在7 個數據集上的運行時間略高于STDP 算法。由上述分析可知，STDPM 算法能以較少的迭代次數和較短的運行時間獲得更高的分類性能。

表7 運行時間對比Table 7 Comparison of running time

3.5 參數分析

STDPM 算法需要輸入兩個超參數：截斷距離比例閾值和密度峰值隸屬度閾值。取值的變化會影響截斷距離的取值，使構造的原型樹發生變化，最終對隸屬度的計算產生影響。取值過大會導致類簇合并，取值過小會導致局部中心點過多，不合適的取值會導致原型樹偏離數據的真實結構。

取值的變化會影響高置信度樣本的選取，取值過大會導致迭代過程中選取高置信度樣本過少，使迭代次數增加，取值過小會導致較低置信度的樣本被添加進訓練集，增加了誤分類風險。

圖4所示三維圖展示了超參數和在不同數據集上的不同取值對準確率的影響，的取值范圍為[1,10]，步長為1，的取值范圍為[0.1,1.0]，步長為0.1。

如圖4 所示，在8 個數據集上，取值小于5 能獲得最高的準確率，在Banknote、Breast、Hepatitis、Ionosphere 和Yale 數據集上，取值較大時準確率較低，這是因為截斷距離不合適，導致原型樹不能反映真實類簇結構。因此，根據實驗結果，的建議取值范圍為(0,5]。在Banknote、Breast、Hepatitis、Yale和Zoo數據集上，取值小于0.5 能獲得較高的準確率，在Ionosphere、Palm 和Segment 數據集上，取值大于0.5 能獲得較高的準確率。由圖4 可知，的合適取值取決于具體的數據集。

圖4 不同參數α 和β 在不同數據集上的準確率Fig.4 Accuracy on different datasets with different parameters α and β

4 結束語

針對Self-Training 過程中高置信度樣本選取問題，提出一種密度峰值隸屬度優化的Self-Training 算法。首先利用密度峰值信息構造原型樹，在原型樹中搜索有標簽樣本的無標簽近親結點集。其次利用近親結點集中無標簽樣本與每個類簇中有標簽樣本的簇峰值信息，計算密度峰值隸屬度。最后設定密度峰值隸屬度閾值，選取隸屬度大于閾值的高置信度樣本。在8 個基準數據集上的對比實驗結果表明，STDPM 算法的分類性能優于對比算法，驗證了利用密度峰值信息能更好地發現數據的潛在空間結構，利用密度峰值隸屬度能選取更高質量的高置信度樣本，從而提升Self-Training 算法的性能。

在今后的工作中，將在距離學習等方面更深入地研究密度峰值與原型樹，重點探索更高效地發現高維數據、復雜數據的潛在空間結構的方法，并將其應用在半監督學習中。