結合密度峰值和切邊權值的自訓練算法

衛丹妮，楊有龍，仇海全，2

1.西安電子科技大學 數學與統計學院，西安710071

2.安徽科技學院 信息與網絡工程學院，安徽 蚌埠233030

數據分類是機器學習領域的一個非常活躍的研究方向。傳統的有監督分類方法為訓練出有效的分類器，往往需要大量的有標記樣本。但在實際應用中，有標記樣本的獲取需要付出較大的代價，不易獲取，而無標記樣本的獲取相對較容易。因此，在有標記樣本量較少時，有監督分類方法難以訓練出有效的分類器。在這種情況下，只需少量的有標記樣本，并充分利用大量無標記樣本的半監督分類方法[1-2]引起越來越多的關注。自訓練[3-4]是半監督分類中常用的方法之一。首先，用少量有標記樣本訓練一個初始分類器，并對無標記樣本分類。然后，選擇置信度較高的無標記樣本及其預測標簽，擴充有標記樣本集，并更新分類器。這兩個過程不斷迭代，直至算法收斂。

自訓練方法不需要任何特定的假設，簡單有效，已經被廣泛應用在文本分類[5]、人臉識別[6]、生物醫學[7]等多個領域。但是自訓練分類算法也存在一些缺陷，比如分類性能受限制于初始標記數據集的大小以及它們在整個數據集上的分布，對標記錯誤樣本的識別改進等。針對自訓練方法的缺點，Gan 等人[8]考慮到數據集的空間分布，提出用半監督模糊c 均值聚類方法來優化自訓練算法（ST-FCM）。該方法把半監督聚類技術作為一個輔助策略融合到自訓練過程，半監督聚類技術能有效地挖掘到無標記樣本含有的內部數據空間結構信息，更好地訓練分類器。但模糊c 均值聚類方法不能很好地發現非高斯分布的數據集的空間結構。針對這一問題，Wu 等人[9]提出了基于密度峰值的自訓練方法（Self-Training based on Density Peak of data，ST-DP）在ST-DP算法中，數據空間結構是用密度峰值聚類[10]的方法發現的。基于密度峰值聚類的方法雖然可以有效利用各種數據分布的空間結構，但是對一些可視化后有較多重疊樣本的數據集，ST-DP的分類效果不好。隨后，Wu等人用差分進化（Differential Evolution，DE）方法來改進自訓練算法，提出了基于差分進化的自訓練算法（ST-DE）[11]。該方法利用DE算法來優化自訓練過程中新添加的有標記樣本[12]。雖然ST-DE算法解決了樣本重疊的問題，但是優化算法在一定程度上帶來了過多的復雜運算，該方法沒有從根本上解決ST-DP 算法的缺陷。主要原因是在自訓練標記過程中，那些可視化后重疊的樣本極其容易被標記錯誤。而ST-DP 算法將這些錯誤標記樣本直接用于后續迭代標記，最終使訓練的分類器性能下降。

在ST-DP 算法[9]的基礎上，本文提出了一個基于密度峰值和切邊權值的自訓練方法（Self-Training method based on Density Peak and Cut Edge Weight，ST-DPCEW）。該方法不僅在選擇未標記樣本時，利用基于密度聚類的方法發現數據集的潛在空間結構，選出具有代表性的樣本進行標簽預測。更重要的是利用切邊權值統計方法識別預測的標簽是否正確，并進行修正或重新預測。切邊權值和密度峰值聚類一起充分利用樣本空間結構和無標記樣本信息，解決了部分樣本被標記錯誤的問題，減少迭代過程中的錯誤累積，能有效提高分類器性能。

1 本文算法

本文從自訓練過程中被錯誤標記的樣本入手來提高自訓練半監督分類算法的分類準確率。在ST-DP 基礎上，提出了ST-DP-CEW算法。首先，用密度聚類方法發現數據集的空間結構，可以在每次迭代過程中優先選擇有代表性樣本進行標簽預測。然后，用切邊權值統計方法判斷樣本是否被標記正確，用標記正確的樣本更新有標記集合。上述過程一直迭代，直到所有無標記樣本標記完全。

1.1 密度聚類發現數據空間結構

聚類是一種典型的無監督學習方法，聚類的過程可以發現數據空間結構。基于密度聚類的方法[10]可以發現非高斯分布的數據集的空間結構，并且可以自動確定簇的個數。

本文中設L={(xi,yi)}是有標記樣本集，其中xi是訓練樣本，yi是它的標簽，yi∈{ω1,ω2,…,ωs} ，i=1,2,…,m ，s 是類別數。U={xm+1,xm+2,…,xn}是無標記樣本集。則樣本xi的局部密度定義如下：

其中：

dij為樣本xi和樣本xj的歐式距離，dc被稱為截斷距離，它是一個沒有固定值，與數據集本身有關的常數[9，13]。顯然，樣本的ρi值等于到xi距離小于dc的樣本個數。

計算每個樣本xi的ρi值后，找到距離樣本xi最近且有更大局部密度的樣本xj，將xi指向xj，即可找到數據集的空間結構。把被指向的樣本xj稱為“下一個”樣本，樣本xi稱為被指向樣本xj的“上一個”樣本。

1.2 切邊權值統計方法

切邊權值統計[14]是一個識別和處理錯誤標記樣本的方法。首先，為了說明樣本的相似性，在數據集上建立一個相對鄰接圖。兩個樣本xi和xj有邊相連，若滿足如下條件：

其中，d(xi,xj)表示樣本xi和xj之間的距離。在鄰接圖中，如果有邊相連的兩個樣本的標簽不同，則這條邊被稱為切邊。

直觀上，對于給定的樣本xi，在它鄰域內的所有樣本應該屬于同一類。因此，如果xi有很多的切邊，即xi鄰域內大部分樣本的標簽與xi的標簽不同，則認為它可能被標記錯誤。因此，切邊在識別錯誤標記樣本中起著重要的作用。對于不同的樣本，它們可能有相同切邊的數量，但是每條切邊的重要性不同，因此為鄰接圖中的每條邊賦予權值。設wij為連接樣本xi和xj的邊的權值。

最后用假設檢驗的方法識別樣本xi是否被標記錯誤。樣本xi的切邊權值之和Ji定義如下：

其中：

這里，ni為與樣本xi有邊相連的樣本個數，yi是樣本xi的標簽。如果待檢驗樣本xi的Ji值很大，認為該樣本有可能標記錯誤。為了進行假設檢驗，要定義原假設如下：

H0，鄰接圖中的所有樣本根據相同的概率分布proy彼此相互獨立地被標記。這里proy表示樣本標簽為y 的概率。

在原假設H0下，樣本xi鄰域內所有樣本的標簽不是yi的概率不超過1-proyi。如果xi的Ji值明顯低于H0下期望，則標記正確。否則樣本可能標記錯誤。為了做雙邊檢驗，必須首先分析Ji在H0下的分布。在原假設下，Ii(j)是服從布爾參數為1-proyi的獨立同分布隨機變量。從而Ji在H0下的期望μ0和方差σ2分別為：

Ji在原假設H0下服從正態分布Ji～N(μ0,σ2)，故選用的檢驗統計量為：

則有u～N(0,1)，給定顯著性水平α，可得出拒絕域為：

從而得到切邊權值之和Ji的拒絕域為：

對于待測樣本xi，如果其Ji值明顯低于在H0下的期望，即在左側拒絕域，則該樣本標記正確，否則有可能標記錯誤。用切邊權值統計方法識別錯誤標記樣本的算法主要步驟如下：

步驟1 對樣本集S 建立一個相對鄰接圖，并初始化正確標記樣本集T={?}和錯誤標記樣本集T′={?}。

步驟2 為鄰接圖中每條邊賦予權值，計算每個樣本xi的切邊權值和Ji、原假設H0下Ji的期望μi和方差δi2。

步驟3 給定顯著性水平α，計算xi的拒絕域。

步驟4 如果Ji值在左側的拒絕域，則標記正確，更新正確標記集合T ←T ?xi；如果不在左側的拒絕域，看它的近鄰樣本，若近鄰樣本全在T 內則用大多數標簽標記重新標記xi，更新T ←T ?xi。否則xi標記錯誤，更新錯誤標記集合T′←T′?xi。

步驟5 重復上述步驟，直到所有樣本檢驗完，將數據集S 劃分為T、T′。

1.3 權值的選擇

每條邊的權值在切邊權值統計方法中具有很重要的作用。本文中，權值是先利用每個樣本的最大近鄰距離來標準化鄰域內的其他近鄰距離[15]。再計算樣本與每個近鄰樣本標簽相同的概率，即為邊的權值。

設樣本集{xi,1,xi,2,…,xi,k}是樣本(xi,yi)的k 個鄰接樣本，即它們與xi有邊相連。xi為訓練樣本，yi是xi的標簽，各個鄰接樣本與xi的距離滿足條件d(xi,1,xi)≤d(xi,2,xi)≤…≤d(xi,k,xi)。用xi的第k 個近鄰樣本距離來標準化前k-1 個鄰接樣本到xi的距離，則標準化后的距離為：

然后將標準化距離轉化為xi和樣本xi,j有相同標簽的概率P(xi,j|xi)，即為鄰接圖中每條邊的權值wij。

1.4 基于密度和切邊權值的自訓練算法

由于自訓練算法在每步迭代時容易將無標記的樣本標記錯誤，這些錯誤會參與到下一步迭代中，從而影響分類器的訓練，降低算法性能。因此，在自訓練過程中，識別標記錯誤樣本對算法性能起著重要的作用。識別樣本標簽的方法有很多，常見的是基于分類器的過濾方法和基于最近鄰規則的數據剪輯技術[14]。

基于分類器的過濾方法主要是在每次迭代訓練時先把現有的有標記樣本集平分成n 個子集，用相同的學習算法如C4.5在所有可能的n-1 個子集中訓練得到n個不同的分類器。然后用n 個分類器對無標記樣本進行分類，根據一致或多數投票原則選擇樣本的標簽。基于最近鄰規則的數據剪輯技術 主要依賴距離，根據k個近鄰樣本的標簽來判斷待預測樣本標簽是否正確。對于待預測樣本xi，如果xi的標簽和其k 個最近鄰樣本的所有或大多數標簽不一致，則xi標記錯誤。

基于分類器的方法對樣本集的劃分和學習算法的選取要求極高。基于最近鄰的方法對距離度量和k 值的選取都需要提前設定。如果提前選取不當會造成判斷錯誤，影響最終的分類效果。而且這兩種方法在識別過程中都沒有利用到無標記樣本所攜帶的大量有價值的信息，使得識別的準確率降低。

切邊權值統計識別錯誤標記樣本的方法不需要預先設定任何參數，也能夠充分利用無標記樣本的信息。因此，為提高自訓練算法的分類準確率，本文將切邊權值統計識別錯誤標記樣本的方法融合到ST-DP算法中，提出了ST-DP-CEW算法。該算法先通過密度聚類方法發現數據集的空間結構，利用空間結果信息在迭代過程中優先選取有代表性的無標記樣本進行標簽預測，提高了預測標簽的準確性。然后用切邊權值統計的方法判斷預測標簽是否正確。將標記正確的樣本用于下一次訓練。算法的具體步驟描述如下：

步驟1 用密度聚類方法找到整個數據集的真空間結構，同時找到了每個樣本xi的“下一個”和“上一個”樣本。

步驟2（1）用KNN 或SVM 作為基分類器，用初始有標記樣本集L 訓練一個初始分類器；

（2）對L 中所有樣本的“下一個”無標記樣本進行標簽預測；

（3）用切邊權值統計方法識別“下一個”樣本是否標記正確，得到正確標記的樣本，更新L 和U ，接著更新分類器；

（4）重復（1）到（3），直到L 的所有“下一個”樣本標記完。

步驟3（1）對已更新的L 中所有樣本的“上一個”無標記樣本進行標簽預測；

（2）用切邊權值統計方法識別“上一個”樣本是否標記正確，得到正確標記的樣本，更新L 和U ，接著更新分類器；

（3）重復（1）和（2），直到L 的所有“上一個”樣本標記完。

顯然，步驟3 和步驟2 類似，只是把步驟2 中的“下一個”換成“上一個”。ST-DP-CEW算法的偽代碼如下：

輸入：有標簽樣本集L，無標簽樣本集U 。

輸出：分類器C。

1.for L ?U 中每個樣本xido

2.利用公式（1）計算ρi

3.end for

4.找到所有樣本的“下一個”和“上一個”樣本；

5.用L 訓練分類器C；

6.令L′為U 中有L 的所有“下一個”樣本集；

7.while L′≠? do

8.用C 對L′中樣本分類；

9.S=L ?L′，T=L，T′=?；

10.在S 中根據公式（2）建立相對鄰接圖；

11.for L′中的每個樣本xido

12.根據公式（3）、（4）、（5）計算切邊權值和Ji以及原假設H0下Ji的期望μi和方差δi2；

13.給定顯著性水平α，根據公式（6）、（7）、（8）計算拒絕域W ；

14.if Ji值在左側拒絕域then

15.T ←T ?xi

16.else if xi鄰域內所有樣本在T 中then

17.重新標記xi，T ←T ?xi

18.else

19.T′←T′?xi

20.end for

21.更新L 和U ，L ←L ?T ，U ←UT ；

22.更新分類器C；

23.end while

24.令L′為U 中有L 的所有“上一個”樣本集；

25.while L′≠? do

26.用C 對L′中樣本分類；

27.S=L ?L′，T=L，T′=?；

28.for L′中的每個樣本xido

29.根據公式（3）、（4）、（5）計算切邊權值和Ji以及原假設H0下Ji的期望μi和方差δi2；

30.給定顯著性水平α，根據公式（6）、（7）、（8）計算拒絕域W ；

31.if Ji值在左側拒絕域then

32.T ←T ?xi

33.else if xi鄰域內所有樣本在T 中then

34.重新標記xi，T ←T ?xi

35.else

36.T′←T′?xi

37.end for

38.更新L 和U ，L ←L ?T ，U ←UT ；

39.更新分類器C；

40.end while

41.return 分類器C

2 實驗結果及分析

為了說明算法的有效性，將提出的算法與已有的自訓練算法在8 個真實數據集上作了對比實驗。數據集均來源于KEEL 數據庫[16]，相關信息如表1 所示。對Cleveland 和Dermatology 數據集刪除有缺失值的樣本，其余數據集不做任何處理。

表1 實驗數據集

采用的對比算法有：以KNN、SVM做分類器的傳統自訓練算法、基于模糊c 均值聚類的自訓練分類算法（ST-FCM）[8]、基于密度峰值的自訓練分類算法（ST-DP）[9]和基于差分進化的自訓練分類算法（ST-DE）[11]。具體參數設置如表2所示。

表2 實驗中相關算法的參數設置

2.1 實驗的實施

采用十折交叉驗證的策略，利用KNN和SVM作為基分類器對數據集進行實驗。把其中的一折作為測試集TS，其余九折作為訓練集TR。每次實驗都隨機選取訓練集中10%的樣本作為初始有標記樣本集L，其余的為無標記集U 。因此，數據集被劃分為有標記集L、無標記集U 和測試集TS。其中L 和U 共同組成訓練集TR。為了確保實驗的準確性，重復做十次十折交叉驗證實驗，最后選取十次實驗平均值作為最后實驗結果。選用分類準確率（Accuracy Rate，AR）、平均準確率（Mean Accuracy Rate，MAR）和標準差（SD-AR）作為算法的分類性能的比較標準。計算公式如下：

其中：

這里，f(xi)是樣本xi的預測標簽，NTS是測試集的大小，n 是實驗重復次數，MAR 代表算法的分類性能，SD-AR 代表算法的魯棒性。選用MAR±SD-AR作為判斷算法性能好壞的依據。

表3和表4分別給出了數據集以KNN和SVM作為基分類器的實驗結果，其中加粗的數據說明在該算法上分類效果比較好。如表3 和表4 所示，當初始標記樣本為10%時，在多數據集上ST-DP-CEW 的平均分類準確率明顯優于其他對比算法。但是在算法以SVM為基分類器時，ST-DP-CEW 在數據集Cleveland 上的分類準確率基本沒有提高，這主要是由于數據集中大部分屬性的數值接近于0，對同一屬性而言，各樣本差異性較小，導致整體上樣本間差異性小，各類別可區分性降低，影響最終的分類效果。

2.2 有標記樣本比例的影響

另外，分析了初始標記樣本比例對算法分類性能的影響，圖1 和圖2 分別給出了基分類器為KNN 和SVM時，幾個算法的平均均分類準確率在初始標記樣本比例為10%、15%、20%、25%、30%、35%、40%、45%以及50%時的變化趨勢。

從圖1 和圖2 可以看出，在8 個數據集上無論是以KNN為基分類器還是以SVM為基分類器，本文提出的算法整體上優于其他對比算法。若以KNN作為基分類器，在8個真實數據集上本文算法在有標記樣本比例極少的情況下平均分類準確率明顯高于其他對比算法。若以SVM 作為基分類器，在Bupa、Dermatology、Glass、Ionosphere、pima、yeast 這6 個數據集上，本文的算法在有標記樣本比例極少的情況下平均分類準確率明顯高于其他對比算法。這是因為ST-DP-CEW在逐步添加無標記樣本時，用切邊權值統計的方法判斷樣本是否被標記正確，并進行修正或重標記。減少了迭代過程中的樣本標記錯誤帶來的負影響，從而提高了分類準確率。觀察圖1 和圖2 還可以發現，隨著初始標記樣本比例逐漸增加，ST-DP-CEW 的平均分類準確率與其他對比算法整體上逐漸接近。這是因為有標記樣本數量比較充足時，這些算法的平均分類準確率都相對比較穩定。提出的算法是基于有標記樣本極其少的情況下提出的，主要應用于半監督分類，更適合在有標記樣本比例較低的環境中進行分類。

表3 基分類器為KNN時的實驗結果（MAR±SD-AR） %

表4 基分類器為SVM時的實驗結果（MAR±SD-AR） %

圖1 基分類器為KNN時算法的MAR值與初始標記樣本比例的關系

圖2 基分類器為SVM時算法的MAR值與初始標記樣本比例的關系

3 結束語

本文從自訓練迭代過程中有可能被錯誤標記樣本出發，在ST-DP算法基礎上提出了基于密度峰值和切邊權值的自訓練算法。即將切邊權值統計識別錯誤標記樣本的方法融合到ST-DP 算法中。既考慮了數據集的空間結構，又解決了樣本被錯誤標記的問題。另外，對鄰接圖中權值的計算也更好地利用數據集的空間結構以及無標記樣本所攜帶的信息。在真實數據集上充分分析了ST-DP-CEW算法的有效性。特別是在初始有標記樣本比例較低的情況下提出的算法較之已有算法，性能上有很大的提升。在后續工作中，將討論如何更好地構建鄰接圖，并在識別過程中引入度量標簽錯誤可能性大小的函數，使標簽識別更精確。