結合密度峰值和集成過濾器的自訓練算法

摘 要：準確選取高置信度樣本是提升自訓練算法分類性能的關鍵. 針對自訓練迭代過程中的誤分類樣本，提出一種結合密度峰值和集成過濾器的自訓練算法：利用密度峰值聚類計算樣本的密度和峰值，構建初始高置信度樣本集；為了過濾自訓練迭代過程中的誤分類樣本，設計一個集成過濾器，從初始高置信度樣本集進一步選擇高置信度樣本，將其添加進有標簽樣本集中迭代訓練. 在9 個數據集上與4 個相關的自訓練算法進行對比實驗，結果表明，算法的平均準確率和F 分數分別為67.90% 和65.54%，其分類性能顯著優于對比算法.

關鍵詞：自訓練；無標簽樣本；高置信度樣本；密度峰值；集成過濾器

中圖分類號：TP181

DOI： 10.19504/j.cnki.issn1671-5365.2024.06.03

自訓練算法[1]是一種經典的半監督學習算法.半監督學習（Semi-supervised learning， SSL）[2]能夠充分利用大量無標簽數據和少量有標簽數據完成分類任務. 相比較于傳統有監督分類利用獲取困難、成本高昂的有標簽數據進行分類，SSL 降低了數據標簽要求，能夠以較少的標簽成本獲得較高的學習性能[3]. SSL 算法主要包括生成式模型[4]、協同訓練[5]、基于圖的方法[6]和自訓練算法等. 其中，自訓練算法因其簡單、高效且無需考慮數據集的初始假設得到了廣泛的討論和應用[7].

自訓練算法在迭代過程中，利用少量有標簽樣本訓練一個基分類器，再利用基分類器從無標簽樣本中選取出高置信度樣本及其預測標簽，將選取的樣本和標簽加入有標簽樣本集中進行再訓練，不斷優化直到將所有無標簽樣本打上標簽[8]，其中高置信度樣本表示自訓練迭代過程中選擇的更高概率加入有標簽集的樣本. 如果樣本在迭代過程中被預測為錯誤標簽加進了有標簽樣本集，即誤選取高置信度樣本，此錯誤將會在訓練過程中不斷加深，因此選取高置信度樣本的準確度是影響自訓練算法性能的關鍵因素.

為提升自訓練算法分類性能，研究者們提出了不同的高置信度樣本的選取方法[9]. Li[10]和Wang[11]等提出了編輯自訓練算法（Self?training with editing，SETRED）和使用割邊的最近鄰自訓練算法（Self?training nearest rule using cut edges， SNNRCE），兩個算法使用割邊權重統計方法（Cut edge weight statis?tic， CEWS）[12]來選取高置信度點，但當割邊權重不平衡時，訓練效果不佳. Gan 等[13]提出了半監督模糊C 均值聚類的自訓練算法（Self?training with semi?su?pervised fuzzy C?means， STSFCM），在自訓練迭代過程中使用模糊C 均值聚類發現局部數據空間結構，將類簇隸屬度大于設定閾值的樣本作為高置信度樣本，但是當樣本類別數較多時閾值的設定較為困難，同時由于未考慮到數據的全局結構信息，難以處理非球形數據樣本. 為此，Wu 等[14]提出了一種基于密度峰值的自訓練算法（Self?training method based ondensity peaks， STDP）.密度峰值聚類（Density peaksclustering， DPC）[15]使用密度峰值構建二維空間中數據間層次關系，能更好地表達樣本的整體空間結構，并對任意形狀的數據樣本有良好的適應性，是一種簡單、快速、有效的聚類算法. STDP 算法使用DPC算法發現數據的全局空間結構，解決了非球形分布的數據分類問題.

雖然STDP 算法能夠快速有效地發現高置信度無標簽樣本，且迭代優化速度非常快，但在迭代過程中容易產生錯誤標記的樣本. 一些研究者通過使用局部噪聲過濾技術過濾誤分類樣本來改進自訓練算法，如多標簽編輯自訓練算法、編輯最近鄰居和切割邊最近鄰自訓練算法[16]等，在一定程度上解決了錯誤標記的問題，但是這些過濾技術大多是基于單一分類器進行過濾，過濾效果不夠穩定. 為了進一步解決自訓練迭代過程中的誤分類問題，本文提出一種基于密度峰值和集成過濾器的自訓練算法（Self?training algorithms based on density peaks and inte?grated filters， STDPIF）.STDPIF 構造了一個新穎的集成過濾器，由K 近鄰[17]（K?nearest neighbor，KNN）、支持向量機[18]（Support vector machine，SVM）、決策樹[19]（Classification and regression tree，CRAT）三個分類器組成. 當三個分類器的標簽預測結果不一致時，集成過濾器會過濾掉該無標簽樣本，其預測能力相對于單個過濾器更加穩定. 算法利用DPC 算法發現樣本空間結構，將有標簽樣本的前置和后置無標簽樣本結點定義為初始高置信度樣本，集成過濾器對初始高置信度樣本進行過濾，判斷樣本是否被正確標記，將正確標記的樣本組合成為最終的高置信度樣本集，從而提高高置信度樣本的選取準確度，減少迭代過程中的誤分類問題.

1 相關算法

1.1 自訓練算法

自訓練算法是一種高效而簡單的半監督學習方法，能夠有效地利用無標簽樣本對數據進行分類.算法可以采用不同的基分類器和多種選取高置信度樣本的方法對模型進行分類. 自訓練算法的分類性能主要依賴于高置信度樣本選取準確度以及基分類器性能.

定義L 和U 分別為數據集中所有有標簽樣本集合和無標簽樣本集合，算法一般流程如下：

Step1： 將L 作為訓練集訓練得到分類器，使用分類器對U 進行預測；

Step2： 從U 中選取一部分置信度高的樣本，用分類器給它們打上偽標簽；

Step3： 將賦予偽標簽的數據加入訓練集，同時將它們從U 中刪除，用新的訓練集繼續訓練分類器；

Step4： 返回Step1，直到U 中沒有樣本時停止.

由于L 會隨著高置信度樣本的加入而不斷擴充，如果在迭代過程中出現樣本標簽誤分類，并將其加入訓練集，可能會導致L 中的噪聲不斷累積，最終使得算法的分類性能下降. 因此更加準確的選取高置信度樣本是提升自訓練算法分類性能的關鍵.

1.2 DPC 算法

DPC 算法是由Rodriguez 等人提出的一種基于局部密度和峰值確定類簇中心的聚類算法，它假設每一個類簇中心被密度低于它的樣本點包圍并與密度較高的樣本點之間的距離相對較遠[20]，通過計算每一個樣本的局部密度和相對距離確定出樣本的類簇中心.

DPC 算法中有截斷核和高斯核兩種計算樣本局部密度的方法，本文使用截斷核方法，樣本xi 局部密度定義為：

其中，d ij 為樣本xi 到xj 的歐氏距離，dc 為樣本xi 的鄰域截斷距離，局部密度ρi 即為分布在樣本xi 的鄰域截斷距離范圍內的樣本個數.

相對距離是指樣本xi 與周圍最近的密度更大的樣本之間的最小距離，樣本xi 的相對距離定義為：

δi = minj：ρj gt; ρidij （2）

而對于最高局部密度的樣本，其相對距離為：

δi = maxi ≠ jδj， ?j， ρi gt; ρj （3）

通過計算出它們的類簇中心權值來確定類簇中心，中心權值的定義為：

γi = ρi ? δi （4）

γi 的值越大，xi 越可能成為類簇中心；γi 值相對較小，則xi 一定不是類簇中心點. 即選取局部密度大，峰值高的樣本點為可能的類簇中心. 確定類簇中心后，DPC 算法由計算得到的相對距離將其余樣本分配到與它們最接近的中心點，完成類簇劃分.

1.3 STDP 算法

STDP 算法在自訓練迭代過程中加入密度峰值聚類思想，利用密度和峰值揭示數據空間結構，能夠更快速地找到置信度高的無標簽樣本.

STDP 首先使用DPC 算法計算每一個樣本的密度和峰值，找到可能的類簇中心，得到每個樣本點與最近的類簇中心之間的距離. 然后在L 上訓練分類器，在U 中通過DPC 算法揭示的空間結構選擇置信度高的無標簽樣本，由分類器賦予其標簽構成高置信度樣本集，添加進L 中，并在U 中刪除這些樣本，重新訓練分類器；再從U 中重新選取置信度高的無標簽樣本由新訓練的分類器賦予其標簽構成新的高置信度樣本集，繼續添加進L 中，并在U 中刪除這些樣本，重復以上步驟，直到沒有無標簽樣本為止.STDP 算法的優點是迭代速度非常快，能有效地發現高置信度無標簽樣本，但STDP 算法在構建高置信度樣本集時存在錯誤分類且未被去除，錯誤標簽影響算法的分類性能.

2 本文算法

為選取更加準確的高置信度樣本，提高自訓練算法分類性能，本文將DPC 算法用于無標簽初始高置信度樣本集的構建，使用集成過濾器對初始集進行重新分類預測，組成準確率更高的高置信度樣本集.

2.1 密度峰值選取初始高置信度樣本集

算法利用DPC 算法發現樣本空間結構，構建樣本標記順序，找出無標簽初始高置信度樣本集. 首先使用DPC 算法計算出樣本xi 的局部密度ρi 和峰值δi，找到距離樣本xi 最近且有更大局部密度的樣本xj，將xi 指向xj，把被指向的樣本xj 稱為前置結點，樣本xi 稱為被指向樣本xj 的后置結點.

定義1 樣本xi 的前置結點Pxi 為：

Pxi = xj s.t. j，δj = minj：ρj gt; ρidij （5）

計算出每個樣本的前置和后置結點即可構建完成樣本的標記順序，樣本中密度最高的樣本點，其前置結點為自身. 由得到的標記順序選取高置信度樣本點，定義無標簽初始高置信度樣本.

定義2 樣本xi 的無標簽初始高置信度樣本為：

Sxi = {x } k|xk = Pxi ∨ xi = Pxk ，i ≠ k （6）

由定義1 和定義2 可知，樣本xi 的無標簽初始高置信度樣本由其自身的前置結點和后置結點組成.找到所有有標簽樣本的后置無標簽結點和前置無標簽結點，即可組成樣本的無標簽初始高置信度樣本集.

2.2 集成過濾器

本文設計的集成過濾器由KNN、SVM、CRAT三個分類器組成. 利用有標簽數據集訓練三個分類器，將得到的集成過濾器用于無標簽初始高置信度樣本集預測篩選. 為利用集成過濾器分類結果選取準確的高置信度樣本點，定義最終高置信度樣本集.

定義3 最終高置信度樣本集S 為：

S = { Sx - si |KNN （si ） ≠ SVM （si ） ∨ SVM （si ）≠ CRAT（si ） } （8）

其中Sx 為無標簽初始高置信度樣本集，s i 為Sx 中的樣本.

由定義3 可知，訓練過的集成過濾器對無標簽初始高置信度樣本集進行分類并打上標簽，去除集成過濾器中KNN、SVM、CRAT 三個分類器分類標簽不一致的樣本，由此組成帶有偽標簽的最終高置信度樣本集.

2.3 基于密度峰值和集成過濾器的自訓練算法（STDPIF）

STDPIF 算法在迭代過程中由定義1 和定義2 選取出無標簽初始高置信度樣本集，再利用集成過濾器對初始集進行預測，將分類標簽一致的高置信度樣本重新組成準確率更高的高置信度樣本集，將其加入有標簽樣本集中進行分類預測. 重復進行，直到無標簽樣本集中沒有樣本為止. 算法的偽代碼如下：

算法1 STDPIF 算法

輸入：有標簽數據集L ，無標簽數據集U

輸出：分類器H

初始化高置信度樣本集S = ?

利用公式（1）和（2）求出樣本的局部密度ρ 和峰值δ

While U ≠ ? DO

for x i ∈ L

根據定義1 確認樣本x i的無標簽初始高置信度樣本S xi

S = S ? S xi

End for

利用L 訓練KNN、SVM 和CART

for s i ∈ S

if K N N （s i ） ≠ S V M （s i ） or C A R T （s i ） ≠ S V M （s i ）

S = S -s i

End if

End for

L = L ? S ， U = U -S

End while

使用L 訓練KNN

Return H

3 實驗結果與分析

本文實驗環境為Windows 10 64 位操作系統、Intel Core i7 處理器、16 GB 內存、MATLAB R2019b編程環境.

3.1 實驗設置

為驗證本文算法的有效性，選取SETRED[12]、STSFCM[15]、STDP[16]、STDPCEW[20]這4 個算法與本文STDPIF 算法進行對比實驗. 所有算法的參數根據算法的原文進行設置. 為了與STDP 和STDPCEW 算法保持一致，本文STDPIF 算法的截斷距離設置為α = 2. 參數設置如表1 所示.

選取Cars、Glass、Australian、Breast、CMC、Diabe?tes、Heart、Ilpd、Transfuion 這9 個數據集進行實驗，數據集的相關信息如表2 所示，9 個數據集均來源于公開的UCI 數據庫.

3.2 實驗結果及分析

將初始有標簽樣本比例設為10%，在每一次試驗中隨機選取，其余的90% 作為無標簽樣本，將準確率（Accuracy）和 F 分數（F-score）作為算法分類性能的評價標準. 5 個算法按照表1 設定參數分別在9 個數據集上運行50 次，計算每個算法50 次實驗結果后的兩種評價指標的平均值與標準差，實驗結果如表3 和表4 所示，為直觀顯示，對5 個算法在每個數據集上的最佳性能加粗顯示.

表3 的結果表明，對所選取的9 個數據集，本文算法在8 個數據集上的準確率要優于4 個對比算法，僅在Transfusion 數據集上，本文算法的準確率低于SETRED、STSFCM、STDPCEW 這三個對比算法，但要高于STDP 算法. 在Cmc 數據集上，STDPIF 算法的準確率與第二名STSFCM 算法的差距最大，高出了6.58 個百分點；在Heart 數據集上，STDPIF 算法的準確率與第二名STDPCEW 算法的差距最小，僅高出0.48 個百分點.

表4 的結果表明，在多數數據集上本文算法的F分數也取得最高. 在Cars 數據集上，STDPIF 算法的F 分數低于STSFCM、STDP 算法，但要高于SETRED 和STDPCEW 算法；在Glass 數據集上，STDPIF 算法的F 分數低于STSFCM 算法，但高于其他3 個對比算法. 在其他6 個數據集上，STDPIF 算法的F 分數均為最高. 從表4 和表5 可知， 4 個對比算法在不同數據集上的性能差異很大，僅在個別數據集上的準確率和F 分數超過本文算法，本文算法在多數數據集上的分類性能均取得最優. 實驗結果表明，本文算法利用DPC 和集成過濾器能夠有效地提升選取高置信度樣本的準確率，降低誤分類風險，提高自訓練算法的分類性能.

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

自訓練算法的高效在于可以利用少量有標簽樣本進行訓練，但有標簽的比例過低會導致獲取到的信息太少，難以進行訓練；而過多的有標簽數據不一定會增加有用信息，還會影響其高效性能. 因此，本文設置了不同比例的有標簽樣本進行實驗，分析其對算法分類性能的影響.

將初始有標簽樣本比例最低設置為10%，最高設置為50%，每次實驗比例增加5%. 記錄5 個算法在每個數據集上運行50 次的準確率平均值，實驗結果如圖1 所示.

結果表明，隨著有標簽樣本比例的增加，5 個算法的準確率也會逐漸增加，在Glass 數據集上5 個算法的性能表現波動比較大，這是因為Glass 數據集的類別數較多，每個類的初始有標記樣本較少，5 個算法在每次實驗中都無法有效地訓練出良好的分類器，導致了實驗結果的不穩定. 由圖1 整體可知，當有標簽樣本的比例較低時，本文算法的性能優于其他對比算法，這表明本文算法能夠在有標簽樣本較少的情況下，利用集成過濾器更好的選取無標簽高置信度樣本進行訓練.

3.4 實驗運行時間分析

表6 為5 個算法在9 個數據集上的平均運行時間，各算法按表3 設定的參數以10% 的初始有標簽樣本比例運行10 次. 由表6 可知， STSFCM 和STDP的耗時遠低于另外3 個算法，這是因為兩個算法的復雜度都為O （n2 ），SETRED、STDPDCEW 的耗時高是因為其復雜度都為O （n3 ）. STDPIF 在7 個數據集上的耗時只高于STDP 和STSFCM，因為STDPIF與STDP 的復雜度相同. 由上述分析可知，STDPIF能夠以較短的訓練時間得到更高的分類性能.

4 結語

針對自訓練迭代過程中選取的高置信度樣本可能被誤分類的問題，提出一種基于密度峰值和集成過濾器的自訓練算法（STDPIF）.算法首先利用密度峰值計算得到初始高置信度樣本集，再構建集成過濾器對初始集進行過濾得到最終高置信度樣本集，降低了樣本被誤分類的風險. 在9 個數據集上和4個對比算法進行了大量的實驗并選取準確率和F 分數作為評價指標，結果表明STDPIF 算法的平均準確率和F 分數高于4 個對比算法. 同時對有標簽樣本比例對算法的性能影響進行了實驗分析，實驗結果表明在初始有標簽樣本比例較低的情況下，本文算法的性能與對比算法相比有較大的提升. 后續的工作將繼續研究提高選取高置信度樣本準確度的方法，尤其是在有標簽樣本較少的情況下選取無標簽高置信度樣本的方法，構建更加準確的高置信度樣本集.

參考文獻：

[1] LI B， WANG J K， YANG Z G， et al. Fast semi-supervised selftrainingalgorithm based on data editing[J]. Information Sciences，2023（626）： 293-314. doi：10.1016/J.INS.2023.01.029.

[2] Yoon H， Kim H. Label-noise robust deep generative modelfor semi-supervised learning[J]. Technometrics， 2023， 65（1）：83-95. doi：10.1080/00401706.2022.2078413.

[3] 劉學文， 王繼奎， 楊正國， 等. 近親結點圖編輯的Self-Training 算法[J]. 計算機工程與應用，2022，58（14）：144-152.

[4] 曹衛東，許志香，王靜. 基于深度生成模型的半監督入侵檢測算法[J]. 計算機科學，2019，46（3）：197-201.

[5] 龔彥鷺，呂佳. 結合主動學習和密度峰值聚類的協同訓練算法[J]. 計算機應用，2019，39（8）：2297-2301.

[6] CHONG Y， DING Y， YAN Q， et al. Graph-based semisupervised learning： A review[J]. Neurocomputing， 2020（408）：216-230. doi：10.1016/j.neucom.2019.12.130.

[7] 呂佳，劉強，李帥軍. 結合密度峰值和改進自然鄰居的自訓練算法[J]. 南京大學學報（自然科學），2022，58（5）：805-815.

[8] 衛丹妮，楊有龍，仇海全. 結合密度峰值和切邊權值的自訓練算法[J]. 計算機工程與應用，2021，57（2）：70-76.

[9] 劉學文，王繼奎，楊正國，等. 密度峰值隸屬度優化的半監督Self-Training 算法[J]. 計算機科學與探索，2022，16（9）：2078-2088.

[10] LI M， ZHOU Z H. SETRED： Self-training with editing[C]//Ho T B， Cheung D， Liu H. Advances in KnowledgeDiscovery and Data Mining. Berlin， Heidelberg： Springer，2005： 611-621. doi：10.1007/11430919_71.

[11] WEI Z H， WANG H L， RU Z. Semi-supervised multilabelimage classification based on nearest neighbor editing[J].Neurocomputing， 2013（119）： 462-468. doi： 10.1016/j. neu?com.2013.03.011.

[12] 孫彩鋒. 基于密度峰值聚類和無參數濾波器的自訓練方法[J]. 計算機應用與軟件，2022，39（12）：318-327.

[13] GAN H， TONG X， JIANG Q， et al. Discussion of FCM al?gorithm with partial supervision[C]//Proceedings of the 8thInternational Symposium on Distributed Computing and Ap?plications to Business， Engineering and Science. Beijing： Pub?lishing House of Electronics Industry， 2009： 27-31.

[14] WU D， SHANG M， LUO X， et al. Self-training semisupervisedclassification based on density peaks of data[J].Neurocomputing， 2018（275）： 180-191. doi： 10.1016/j. neu?com.2017.05.072.

[15] RODRIGUEZ A， LAIO A. Clustering by fast search andfind of density peaks[J]. Science， 2014，344（6191）： 1492-1496.doi：10.1126/science.1242072.

[16] 李帥軍，呂佳. 結合合成實例與adaboostENN 密度峰值自訓練算法[J]. 重慶師范大學學報（ 自然科學版）， 2022， 39（4）：105-113.

[17] 吳強. 基于局部均值k 近鄰和密度峰值的實例約簡[J]. 統計與決策，2022，38（24）：10-16.

[18] 李福祥，王雪，張馳，等. 基于邊界點的支持向量機分類算法[J]. 陜西理工大學學報（自然科學版），2022，38（3）：30-38.

[19] 張亮，寧芊.CART 決策樹的兩種改進及應用[J]. 計算機工程與設計，2015，36（5）：1209-1213.

[20] 徐鑫，曹原. 基于加權直覺模糊蘭氏距離的密度峰值聚類算法[J]. 陜西師范大學學報（自然科學版），2023，51（1）： 101-110.

【編校：王露】

基金項目：甘肅省自然科學基金項目“深度學習在高原夏菜質量分級中的應用研究”（21JR1RA283）