衛(wèi)丹妮,楊有龍,仇海全,2
1.西安電子科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院,西安710071
2.安徽科技學(xué)院 信息與網(wǎng)絡(luò)工程學(xué)院,安徽 蚌埠233030
數(shù)據(jù)分類是機器學(xué)習(xí)領(lǐng)域的一個非常活躍的研究方向。傳統(tǒng)的有監(jiān)督分類方法為訓(xùn)練出有效的分類器,往往需要大量的有標(biāo)記樣本。但在實際應(yīng)用中,有標(biāo)記樣本的獲取需要付出較大的代價,不易獲取,而無標(biāo)記樣本的獲取相對較容易。因此,在有標(biāo)記樣本量較少時,有監(jiān)督分類方法難以訓(xùn)練出有效的分類器。在這種情況下,只需少量的有標(biāo)記樣本,并充分利用大量無標(biāo)記樣本的半監(jiān)督分類方法[1-2]引起越來越多的關(guān)注。自訓(xùn)練[3-4]是半監(jiān)督分類中常用的方法之一。首先,用少量有標(biāo)記樣本訓(xùn)練一個初始分類器,并對無標(biāo)記樣本分類。然后,選擇置信度較高的無標(biāo)記樣本及其預(yù)測標(biāo)簽,擴充有標(biāo)記樣本集,并更新分類器。這兩個過程不斷迭代,直至算法收斂。
自訓(xùn)練方法不需要任何特定的假設(shè),簡單有效,已經(jīng)被廣泛應(yīng)用在文本分類[5]、人臉識別[6]、生物醫(yī)學(xué)[7]等多個領(lǐng)域。但是自訓(xùn)練分類算法也存在一些缺陷,比如分類性能受限制于初始標(biāo)記數(shù)據(jù)集的大小以及它們在整個數(shù)據(jù)集上的分布,對標(biāo)記錯誤樣本的識別改進等。針對自訓(xùn)練方法的缺點,Gan 等人[8]考慮到數(shù)據(jù)集的空間分布,提出用半監(jiān)督模糊c 均值聚類方法來優(yōu)化自訓(xùn)練算法(ST-FCM)。該方法把半監(jiān)督聚類技術(shù)作為一個輔助策略融合到自訓(xùn)練過程,半監(jiān)督聚類技術(shù)能有效地挖掘到無標(biāo)記樣本含有的內(nèi)部數(shù)據(jù)空間結(jié)構(gòu)信息,更好地訓(xùn)練分類器。但模糊c 均值聚類方法不能很好地發(fā)現(xiàn)非高斯分布的數(shù)據(jù)集的空間結(jié)構(gòu)。針對這一問題,Wu 等人[9]提出了基于密度峰值的自訓(xùn)練方法(Self-Training based on Density Peak of data,ST-DP)在ST-DP算法中,數(shù)據(jù)空間結(jié)構(gòu)是用密度峰值聚類[10]的方法發(fā)現(xiàn)的?;诿芏确逯稻垲惖姆椒m然可以有效利用各種數(shù)據(jù)分布的空間結(jié)構(gòu),但是對一些可視化后有較多重疊樣本的數(shù)據(jù)集,ST-DP的分類效果不好。隨后,Wu等人用差分進化(Differential Evolution,DE)方法來改進自訓(xùn)練算法,提出了基于差分進化的自訓(xùn)練算法(ST-DE)[11]。該方法利用DE算法來優(yōu)化自訓(xùn)練過程中新添加的有標(biāo)記樣本[12]。雖然ST-DE算法解決了樣本重疊的問題,但是優(yōu)化算法在一定程度上帶來了過多的復(fù)雜運算,該方法沒有從根本上解決ST-DP 算法的缺陷。主要原因是在自訓(xùn)練標(biāo)記過程中,那些可視化后重疊的樣本極其容易被標(biāo)記錯誤。而ST-DP 算法將這些錯誤標(biāo)記樣本直接用于后續(xù)迭代標(biāo)記,最終使訓(xùn)練的分類器性能下降。
在ST-DP 算法[9]的基礎(chǔ)上,本文提出了一個基于密度峰值和切邊權(quán)值的自訓(xùn)練方法(Self-Training method based on Density Peak and Cut Edge Weight,ST-DPCEW)。該方法不僅在選擇未標(biāo)記樣本時,利用基于密度聚類的方法發(fā)現(xiàn)數(shù)據(jù)集的潛在空間結(jié)構(gòu),選出具有代表性的樣本進行標(biāo)簽預(yù)測。更重要的是利用切邊權(quán)值統(tǒng)計方法識別預(yù)測的標(biāo)簽是否正確,并進行修正或重新預(yù)測。切邊權(quán)值和密度峰值聚類一起充分利用樣本空間結(jié)構(gòu)和無標(biāo)記樣本信息,解決了部分樣本被標(biāo)記錯誤的問題,減少迭代過程中的錯誤累積,能有效提高分類器性能。
本文從自訓(xùn)練過程中被錯誤標(biāo)記的樣本入手來提高自訓(xùn)練半監(jiān)督分類算法的分類準(zhǔn)確率。在ST-DP 基礎(chǔ)上,提出了ST-DP-CEW算法。首先,用密度聚類方法發(fā)現(xiàn)數(shù)據(jù)集的空間結(jié)構(gòu),可以在每次迭代過程中優(yōu)先選擇有代表性樣本進行標(biāo)簽預(yù)測。然后,用切邊權(quán)值統(tǒng)計方法判斷樣本是否被標(biāo)記正確,用標(biāo)記正確的樣本更新有標(biāo)記集合。上述過程一直迭代,直到所有無標(biāo)記樣本標(biāo)記完全。
聚類是一種典型的無監(jiān)督學(xué)習(xí)方法,聚類的過程可以發(fā)現(xiàn)數(shù)據(jù)空間結(jié)構(gòu)?;诿芏染垲惖姆椒╗10]可以發(fā)現(xiàn)非高斯分布的數(shù)據(jù)集的空間結(jié)構(gòu),并且可以自動確定簇的個數(shù)。
本文中設(shè)L={(xi,yi)}是有標(biāo)記樣本集,其中xi是訓(xùn)練樣本,yi是它的標(biāo)簽,yi∈{ω1,ω2,…,ωs} ,i=1,2,…,m ,s 是類別數(shù)。U={xm+1,xm+2,…,xn}是無標(biāo)記樣本集。則樣本xi的局部密度定義如下:
其中:
dij為樣本xi和樣本xj的歐式距離,dc被稱為截斷距離,它是一個沒有固定值,與數(shù)據(jù)集本身有關(guān)的常數(shù)[9,13]。顯然,樣本的ρi值等于到xi距離小于dc的樣本個數(shù)。
計算每個樣本xi的ρi值后,找到距離樣本xi最近且有更大局部密度的樣本xj,將xi指向xj,即可找到數(shù)據(jù)集的空間結(jié)構(gòu)。把被指向的樣本xj稱為“下一個”樣本,樣本xi稱為被指向樣本xj的“上一個”樣本。
切邊權(quán)值統(tǒng)計[14]是一個識別和處理錯誤標(biāo)記樣本的方法。首先,為了說明樣本的相似性,在數(shù)據(jù)集上建立一個相對鄰接圖。兩個樣本xi和xj有邊相連,若滿足如下條件:
其中,d(xi,xj)表示樣本xi和xj之間的距離。在鄰接圖中,如果有邊相連的兩個樣本的標(biāo)簽不同,則這條邊被稱為切邊。
直觀上,對于給定的樣本xi,在它鄰域內(nèi)的所有樣本應(yīng)該屬于同一類。因此,如果xi有很多的切邊,即xi鄰域內(nèi)大部分樣本的標(biāo)簽與xi的標(biāo)簽不同,則認(rèn)為它可能被標(biāo)記錯誤。因此,切邊在識別錯誤標(biāo)記樣本中起著重要的作用。對于不同的樣本,它們可能有相同切邊的數(shù)量,但是每條切邊的重要性不同,因此為鄰接圖中的每條邊賦予權(quán)值。設(shè)wij為連接樣本xi和xj的邊的權(quán)值。
最后用假設(shè)檢驗的方法識別樣本xi是否被標(biāo)記錯誤。樣本xi的切邊權(quán)值之和Ji定義如下:
其中:
這里,ni為與樣本xi有邊相連的樣本個數(shù),yi是樣本xi的標(biāo)簽。如果待檢驗樣本xi的Ji值很大,認(rèn)為該樣本有可能標(biāo)記錯誤。為了進行假設(shè)檢驗,要定義原假設(shè)如下:
H0,鄰接圖中的所有樣本根據(jù)相同的概率分布proy彼此相互獨立地被標(biāo)記。這里proy表示樣本標(biāo)簽為y 的概率。
在原假設(shè)H0下,樣本xi鄰域內(nèi)所有樣本的標(biāo)簽不是yi的概率不超過1-proyi。如果xi的Ji值明顯低于H0下期望,則標(biāo)記正確。否則樣本可能標(biāo)記錯誤。為了做雙邊檢驗,必須首先分析Ji在H0下的分布。在原假設(shè)下,Ii(j)是服從布爾參數(shù)為1-proyi的獨立同分布隨機變量。從而Ji在H0下的期望μ0和方差σ2分別為:
Ji在原假設(shè)H0下服從正態(tài)分布Ji~N(μ0,σ2),故選用的檢驗統(tǒng)計量為:
則有u~N(0,1),給定顯著性水平α,可得出拒絕域為:
從而得到切邊權(quán)值之和Ji的拒絕域為:
對于待測樣本xi,如果其Ji值明顯低于在H0下的期望,即在左側(cè)拒絕域,則該樣本標(biāo)記正確,否則有可能標(biāo)記錯誤。用切邊權(quán)值統(tǒng)計方法識別錯誤標(biāo)記樣本的算法主要步驟如下:
步驟1 對樣本集S 建立一個相對鄰接圖,并初始化正確標(biāo)記樣本集T={?}和錯誤標(biāo)記樣本集T′={?}。
步驟2 為鄰接圖中每條邊賦予權(quán)值,計算每個樣本xi的切邊權(quán)值和Ji、原假設(shè)H0下Ji的期望μi和方差δi2。
步驟3 給定顯著性水平α,計算xi的拒絕域。
步驟4 如果Ji值在左側(cè)的拒絕域,則標(biāo)記正確,更新正確標(biāo)記集合T ←T ?xi;如果不在左側(cè)的拒絕域,看它的近鄰樣本,若近鄰樣本全在T 內(nèi)則用大多數(shù)標(biāo)簽標(biāo)記重新標(biāo)記xi,更新T ←T ?xi。否則xi標(biāo)記錯誤,更新錯誤標(biāo)記集合T′←T′?xi。
步驟5 重復(fù)上述步驟,直到所有樣本檢驗完,將數(shù)據(jù)集S 劃分為T、T′。
每條邊的權(quán)值在切邊權(quán)值統(tǒng)計方法中具有很重要的作用。本文中,權(quán)值是先利用每個樣本的最大近鄰距離來標(biāo)準(zhǔn)化鄰域內(nèi)的其他近鄰距離[15]。再計算樣本與每個近鄰樣本標(biāo)簽相同的概率,即為邊的權(quán)值。
設(shè)樣本集{xi,1,xi,2,…,xi,k}是樣本(xi,yi)的k 個鄰接樣本,即它們與xi有邊相連。xi為訓(xùn)練樣本,yi是xi的標(biāo)簽,各個鄰接樣本與xi的距離滿足條件d(xi,1,xi)≤d(xi,2,xi)≤…≤d(xi,k,xi)。用xi的第k 個近鄰樣本距離來標(biāo)準(zhǔn)化前k-1 個鄰接樣本到xi的距離,則標(biāo)準(zhǔn)化后的距離為:
然后將標(biāo)準(zhǔn)化距離轉(zhuǎn)化為xi和樣本xi,j有相同標(biāo)簽的概率P(xi,j|xi),即為鄰接圖中每條邊的權(quán)值wij。
由于自訓(xùn)練算法在每步迭代時容易將無標(biāo)記的樣本標(biāo)記錯誤,這些錯誤會參與到下一步迭代中,從而影響分類器的訓(xùn)練,降低算法性能。因此,在自訓(xùn)練過程中,識別標(biāo)記錯誤樣本對算法性能起著重要的作用。識別樣本標(biāo)簽的方法有很多,常見的是基于分類器的過濾方法和基于最近鄰規(guī)則的數(shù)據(jù)剪輯技術(shù)[14]。
基于分類器的過濾方法主要是在每次迭代訓(xùn)練時先把現(xiàn)有的有標(biāo)記樣本集平分成n 個子集,用相同的學(xué)習(xí)算法如C4.5在所有可能的n-1 個子集中訓(xùn)練得到n個不同的分類器。然后用n 個分類器對無標(biāo)記樣本進行分類,根據(jù)一致或多數(shù)投票原則選擇樣本的標(biāo)簽?;谧罱徱?guī)則的數(shù)據(jù)剪輯技術(shù) 主要依賴距離,根據(jù)k個近鄰樣本的標(biāo)簽來判斷待預(yù)測樣本標(biāo)簽是否正確。對于待預(yù)測樣本xi,如果xi的標(biāo)簽和其k 個最近鄰樣本的所有或大多數(shù)標(biāo)簽不一致,則xi標(biāo)記錯誤。
基于分類器的方法對樣本集的劃分和學(xué)習(xí)算法的選取要求極高?;谧罱彽姆椒▽嚯x度量和k 值的選取都需要提前設(shè)定。如果提前選取不當(dāng)會造成判斷錯誤,影響最終的分類效果。而且這兩種方法在識別過程中都沒有利用到無標(biāo)記樣本所攜帶的大量有價值的信息,使得識別的準(zhǔn)確率降低。
切邊權(quán)值統(tǒng)計識別錯誤標(biāo)記樣本的方法不需要預(yù)先設(shè)定任何參數(shù),也能夠充分利用無標(biāo)記樣本的信息。因此,為提高自訓(xùn)練算法的分類準(zhǔn)確率,本文將切邊權(quán)值統(tǒng)計識別錯誤標(biāo)記樣本的方法融合到ST-DP算法中,提出了ST-DP-CEW算法。該算法先通過密度聚類方法發(fā)現(xiàn)數(shù)據(jù)集的空間結(jié)構(gòu),利用空間結(jié)果信息在迭代過程中優(yōu)先選取有代表性的無標(biāo)記樣本進行標(biāo)簽預(yù)測,提高了預(yù)測標(biāo)簽的準(zhǔn)確性。然后用切邊權(quán)值統(tǒng)計的方法判斷預(yù)測標(biāo)簽是否正確。將標(biāo)記正確的樣本用于下一次訓(xùn)練。算法的具體步驟描述如下:
步驟1 用密度聚類方法找到整個數(shù)據(jù)集的真空間結(jié)構(gòu),同時找到了每個樣本xi的“下一個”和“上一個”樣本。
步驟2(1)用KNN 或SVM 作為基分類器,用初始有標(biāo)記樣本集L 訓(xùn)練一個初始分類器;
(2)對L 中所有樣本的“下一個”無標(biāo)記樣本進行標(biāo)簽預(yù)測;
(3)用切邊權(quán)值統(tǒng)計方法識別“下一個”樣本是否標(biāo)記正確,得到正確標(biāo)記的樣本,更新L 和U ,接著更新分類器;
(4)重復(fù)(1)到(3),直到L 的所有“下一個”樣本標(biāo)記完。
步驟3(1)對已更新的L 中所有樣本的“上一個”無標(biāo)記樣本進行標(biāo)簽預(yù)測;
(2)用切邊權(quán)值統(tǒng)計方法識別“上一個”樣本是否標(biāo)記正確,得到正確標(biāo)記的樣本,更新L 和U ,接著更新分類器;
(3)重復(fù)(1)和(2),直到L 的所有“上一個”樣本標(biāo)記完。
顯然,步驟3 和步驟2 類似,只是把步驟2 中的“下一個”換成“上一個”。ST-DP-CEW算法的偽代碼如下:
輸入:有標(biāo)簽樣本集L,無標(biāo)簽樣本集U 。
輸出:分類器C。
1.for L ?U 中每個樣本xido
2.利用公式(1)計算ρi
3.end for
4.找到所有樣本的“下一個”和“上一個”樣本;
5.用L 訓(xùn)練分類器C;
6.令L′為U 中有L 的所有“下一個”樣本集;
7.while L′≠? do
8.用C 對L′中樣本分類;
9.S=L ?L′,T=L,T′=?;
10.在S 中根據(jù)公式(2)建立相對鄰接圖;
11.for L′中的每個樣本xido
12.根據(jù)公式(3)、(4)、(5)計算切邊權(quán)值和Ji以及原假設(shè)H0下Ji的期望μi和方差δi2;
13.給定顯著性水平α,根據(jù)公式(6)、(7)、(8)計算拒絕域W ;
14.if Ji值在左側(cè)拒絕域then
15.T ←T ?xi
16.else if xi鄰域內(nèi)所有樣本在T 中then
17.重新標(biāo)記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.根據(jù)公式(3)、(4)、(5)計算切邊權(quán)值和Ji以及原假設(shè)H0下Ji的期望μi和方差δi2;
30.給定顯著性水平α,根據(jù)公式(6)、(7)、(8)計算拒絕域W ;
31.if Ji值在左側(cè)拒絕域then
32.T ←T ?xi
33.else if xi鄰域內(nèi)所有樣本在T 中then
34.重新標(biāo)記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
為了說明算法的有效性,將提出的算法與已有的自訓(xùn)練算法在8 個真實數(shù)據(jù)集上作了對比實驗。數(shù)據(jù)集均來源于KEEL 數(shù)據(jù)庫[16],相關(guān)信息如表1 所示。對Cleveland 和Dermatology 數(shù)據(jù)集刪除有缺失值的樣本,其余數(shù)據(jù)集不做任何處理。
表1 實驗數(shù)據(jù)集
采用的對比算法有:以KNN、SVM做分類器的傳統(tǒng)自訓(xùn)練算法、基于模糊c 均值聚類的自訓(xùn)練分類算法(ST-FCM)[8]、基于密度峰值的自訓(xùn)練分類算法(ST-DP)[9]和基于差分進化的自訓(xùn)練分類算法(ST-DE)[11]。具體參數(shù)設(shè)置如表2所示。
表2 實驗中相關(guān)算法的參數(shù)設(shè)置
采用十折交叉驗證的策略,利用KNN和SVM作為基分類器對數(shù)據(jù)集進行實驗。把其中的一折作為測試集TS,其余九折作為訓(xùn)練集TR。每次實驗都隨機選取訓(xùn)練集中10%的樣本作為初始有標(biāo)記樣本集L,其余的為無標(biāo)記集U 。因此,數(shù)據(jù)集被劃分為有標(biāo)記集L、無標(biāo)記集U 和測試集TS。其中L 和U 共同組成訓(xùn)練集TR。為了確保實驗的準(zhǔn)確性,重復(fù)做十次十折交叉驗證實驗,最后選取十次實驗平均值作為最后實驗結(jié)果。選用分類準(zhǔn)確率(Accuracy Rate,AR)、平均準(zhǔn)確率(Mean Accuracy Rate,MAR)和標(biāo)準(zhǔn)差(SD-AR)作為算法的分類性能的比較標(biāo)準(zhǔn)。計算公式如下:
其中:
這里,f(xi)是樣本xi的預(yù)測標(biāo)簽,NTS是測試集的大小,n 是實驗重復(fù)次數(shù),MAR 代表算法的分類性能,SD-AR 代表算法的魯棒性。選用MAR±SD-AR作為判斷算法性能好壞的依據(jù)。
表3和表4分別給出了數(shù)據(jù)集以KNN和SVM作為基分類器的實驗結(jié)果,其中加粗的數(shù)據(jù)說明在該算法上分類效果比較好。如表3 和表4 所示,當(dāng)初始標(biāo)記樣本為10%時,在多數(shù)據(jù)集上ST-DP-CEW 的平均分類準(zhǔn)確率明顯優(yōu)于其他對比算法。但是在算法以SVM為基分類器時,ST-DP-CEW 在數(shù)據(jù)集Cleveland 上的分類準(zhǔn)確率基本沒有提高,這主要是由于數(shù)據(jù)集中大部分屬性的數(shù)值接近于0,對同一屬性而言,各樣本差異性較小,導(dǎo)致整體上樣本間差異性小,各類別可區(qū)分性降低,影響最終的分類效果。
另外,分析了初始標(biāo)記樣本比例對算法分類性能的影響,圖1 和圖2 分別給出了基分類器為KNN 和SVM時,幾個算法的平均均分類準(zhǔn)確率在初始標(biāo)記樣本比例為10%、15%、20%、25%、30%、35%、40%、45%以及50%時的變化趨勢。
從圖1 和圖2 可以看出,在8 個數(shù)據(jù)集上無論是以KNN為基分類器還是以SVM為基分類器,本文提出的算法整體上優(yōu)于其他對比算法。若以KNN作為基分類器,在8個真實數(shù)據(jù)集上本文算法在有標(biāo)記樣本比例極少的情況下平均分類準(zhǔn)確率明顯高于其他對比算法。若以SVM 作為基分類器,在Bupa、Dermatology、Glass、Ionosphere、pima、yeast 這6 個數(shù)據(jù)集上,本文的算法在有標(biāo)記樣本比例極少的情況下平均分類準(zhǔn)確率明顯高于其他對比算法。這是因為ST-DP-CEW在逐步添加無標(biāo)記樣本時,用切邊權(quán)值統(tǒng)計的方法判斷樣本是否被標(biāo)記正確,并進行修正或重標(biāo)記。減少了迭代過程中的樣本標(biāo)記錯誤帶來的負(fù)影響,從而提高了分類準(zhǔn)確率。觀察圖1 和圖2 還可以發(fā)現(xiàn),隨著初始標(biāo)記樣本比例逐漸增加,ST-DP-CEW 的平均分類準(zhǔn)確率與其他對比算法整體上逐漸接近。這是因為有標(biāo)記樣本數(shù)量比較充足時,這些算法的平均分類準(zhǔn)確率都相對比較穩(wěn)定。提出的算法是基于有標(biāo)記樣本極其少的情況下提出的,主要應(yīng)用于半監(jiān)督分類,更適合在有標(biāo)記樣本比例較低的環(huán)境中進行分類。
表3 基分類器為KNN時的實驗結(jié)果(MAR±SD-AR) %
表4 基分類器為SVM時的實驗結(jié)果(MAR±SD-AR) %
圖1 基分類器為KNN時算法的MAR值與初始標(biāo)記樣本比例的關(guān)系
圖2 基分類器為SVM時算法的MAR值與初始標(biāo)記樣本比例的關(guān)系
本文從自訓(xùn)練迭代過程中有可能被錯誤標(biāo)記樣本出發(fā),在ST-DP算法基礎(chǔ)上提出了基于密度峰值和切邊權(quán)值的自訓(xùn)練算法。即將切邊權(quán)值統(tǒng)計識別錯誤標(biāo)記樣本的方法融合到ST-DP 算法中。既考慮了數(shù)據(jù)集的空間結(jié)構(gòu),又解決了樣本被錯誤標(biāo)記的問題。另外,對鄰接圖中權(quán)值的計算也更好地利用數(shù)據(jù)集的空間結(jié)構(gòu)以及無標(biāo)記樣本所攜帶的信息。在真實數(shù)據(jù)集上充分分析了ST-DP-CEW算法的有效性。特別是在初始有標(biāo)記樣本比例較低的情況下提出的算法較之已有算法,性能上有很大的提升。在后續(xù)工作中,將討論如何更好地構(gòu)建鄰接圖,并在識別過程中引入度量標(biāo)簽錯誤可能性大小的函數(shù),使標(biāo)簽識別更精確。