孫 彩 鋒
(山西大同大學物理與電子科學學院 山西 大同 037009)
半監(jiān)督學習由于可以通過同時利用未標記數據和標記數據來進行數據樣本改進,降低了對數據樣本的要求,在諸多領域得到了廣泛的應用[1-2]。而在半監(jiān)督學習分類器發(fā)展過程中,自訓練方法也以其簡單、高效和自適應等特點被認為是最具代表性的方法之一,因此得到了學界廣泛的討論和研究[3-4]。
在自我訓練方法中,錯誤標注是一個非常普遍、棘手甚至不可避免的問題[5]。一般情況下,自訓練方法將誤標記樣本視為噪聲實例,嚴重扭曲了數據的分布,降低半監(jiān)督學習的泛化能力。因此,提出了一系列基于局部噪聲濾波器的自訓練算法,其中,剪輯自訓練(self-training with editing,SETRED)和鄰域自訓練(self-training nearest neighbor rule using cut edges,SNNRCE)使用切邊權值統(tǒng)計(cut edge weight statistic,CEWS)來濾除噪聲實例[6-7],多標簽剪輯自訓練(multi-label self-training with editing,MLSTE)則使用剪輯最近鄰(edited nearest neighbor,ENN)來濾除噪聲實例[8-9]。隨后,Triguero等發(fā)現,在自我訓練方法中使用的大多數現有噪聲濾波器的局部方法沒有很好地執(zhí)行,特別是當標記數據不足時,即大多數自訓練方法中使用的局部噪聲濾波器需要更多的標記數據才能工作[10]。另外,自訓練方法中的局部噪聲濾波器主要是k近鄰(k-nearest neighbors,KNN)分類器,因此,該方法濾波能力很大程度上依賴于參數k[11]。除此之外,現有的局部噪聲濾波器都是基于監(jiān)督學習的,因此,它們并不完全與半監(jiān)督學習兼容,因為它們只考慮標記數據的信息。
針對上述問題,提出了一種基于密度峰值和無參數局部噪聲濾波器自訓練方法。設計的一種新的無參數局部噪聲濾波器,既能利用標記數據,又能利用未標記數據去除噪聲。
(1)
(2)
(3)
式中:ρ={ρ1,ρ2,…,ρn}是記錄X中所有樣本的局部密度的集合,即ρi是樣本xi的局部密度,δ={δ1,δ2,…,δn}記錄每個樣本在X中的最小距離,即δi是樣本xi與具有更高局部密度的任何其他樣本之間的最小距離,通過計算ρi和δi,每個樣本xi都有一個對應的樣本xj,它是xi最接近的具有更高局部密度ρi的樣本,dij是樣本xi和xj之間的距離。這里采用歐氏距離,dc是具有預設值的截止距離。然后,使每個樣本xi指向其對應的唯一樣本xj。
在揭示特征空間的結構之后,STDP使用密度峰值聚類揭示的基礎結構來幫助訓練給定的分類器,定義L={x1,x2,…,xl}是X中所有標記樣本的集合,U={xl+1,xl+2,…,xn}是X中所有未標記樣本的集合。在該分類器中,未標記樣本被連續(xù)標記并添加到L中。該標記過程分為兩個步驟。第一步是從U迭代地選擇L樣本的所有“下一個”點并進行標記。第二步是從U迭代地選擇L樣本的所有“上一個”點并進行標記。
自然鄰域是沒有參數的鄰域,主要想法來自對社交網絡的理解[13]。一個人擁有的真正朋友的數量應該是將他或她視為朋友并同時被他或她視為朋友的人數。如果每個人至少都有一個朋友,則在社交網絡中將形成一個相對穩(wěn)定的結構,稱為自然穩(wěn)定結構(natural stable structure,NSS)。
定義1自然穩(wěn)定結構:如果x將z視為鄰域并且z同時將x視為鄰域,則對象z是對象x的自然鄰域。如果每個對象都有至少一個自然鄰域,則數據集已形成一個相對穩(wěn)定的狀態(tài),稱為自然穩(wěn)定結構[13]。
(?xi)(?xj)(r∈n)∨(xi≠xj)→
(xi∈NNr(xj))∨(xj∈NNr(xi))
(4)
式中:NNr(x)={x1,x2,…,xr}是包含樣本x的r個最近鄰域的集合。在式(4)中,搜索回合r從1增加到λ(λ≤n),λ是自然鄰域特征值。當r=λ時,NSS在給定的數據集中形成。實際上,數據的復雜性可以用λ表示。值較小的λ表示數據規(guī)則或數據大小較小,而值較大的λ表示數據大小較大。此外,λ已經被用來解決參數k的問題。根據上面的描述,數據對象的自然鄰域可以表述為:
定義2自然鄰域(Natural Neighbor,NaN):xi的自然鄰域定義如下[14]:
xj∈NaN(xi)?xi∈NNλ(xj)&&xj∈NNλ(xi)
(5)
式中:NaN(x)={x1,x2,…}是包含樣本x的自然鄰居的集合。算法1描述了自然鄰域搜索算法。
算法1自然鄰域搜索算法
輸入:X
輸出:NaN,λ
1.r=1,?xi∈X,Nb(xi)=?,NNk(xi)=?,RNNk(xi)=?,NaN(xi)=?;
2.從數據集X中創(chuàng)造一個k-d樹T
3.for數據集X的每一個xi通過T找到它的第r個鄰域xj
4.NNk(xi)=NNk(xi)∪{xj};
5.Nb(xj)=Nb(xj)+1;
6.RNNk(xj)=RNNk(xj)∪{xi};
7.end for
8.計算num
9.ifnum沒變
10.則λ=r;
11.for數據集X的每一個xi
12.NaN(xi)=RNNλ(xi)∩NNλ{xi};
13.end for
14.返回NaN,λ;
15.else
16.r=r+1;
17.回到第三步;
18.end if
算法1返回NaN和λ。Nb={t1,t2,…,tn}是記錄數字的集合,式中ti(i=1,2,…,n)是被視為與其他樣本相鄰的樣本xi的數目。另外,Nb(xi)記錄被視為與其他樣本相鄰的樣本xi的數量。在第2-7行中,計算NaN直到形成自然穩(wěn)定結構。算法中增加了一個限制,即變量num不會更改,因為噪聲會影響算法1。num是Nb(xi)==0的樣本xi的數量,式中Nb(xi)表示被視為其他樣本的鄰域樣本xi的數量。通常,時間復雜度為O(nlogn),因為在第2行中使用了k-d樹。k-d樹是劃分k維數據空間的數據結構。它主要應用于多維空間中關鍵數據的搜索。
圖1顯示了基于密度峰值和無參數局部噪聲濾波器自訓練方法(self-training method based on density peaks and an local noise filter,STDPNF)的一般框架,該框架由三部分組成。第一步中,使用密度峰值聚類發(fā)現特征空間的基礎結構。然后,將此結構轉換為所有樣本的標記順序。第二步是一個標準的自訓練過程,根據標記順序預測未標記樣本并將其添加到中。此外,擴展的自然鄰域剪輯濾波器(extended natural neighbor editing,ENaNE)可以刪除噪聲實例。第三步用擴展的重新訓練KNN分類器。此后,可以更好地克服標記錯誤的問題,并且可以訓練分類器。
圖1 STDPNF的框架
在此將重新設計密度峰值聚類在STDP中顯示的結構,以使其有利于結合提出的局部噪聲濾波器。STDP存在標記錯誤的問題。因此,打算使用局部噪聲濾波器來去除STDP中標記錯誤的樣本。但是,一旦將錯誤預測的樣本作為噪聲實例丟棄,與丟棄的樣本關聯的幾個未標記樣本將沒有機會被標記。圖2給出了一個例子來說明這種情況。
(a) 揭示特征空間的結構
(b) 錯誤標記示意圖圖2 標記示例
在圖2(a)中,密度峰值聚類揭示了特征空間的結構,其中每個樣本都指向具有更高局部密度的相應最近樣本。如圖2(b)所示,樣本x1被錯誤地預測。如圖2(a)所示,樣本x1應屬于類1。如果樣本x1作為噪聲實例被丟棄,則樣本x1將不會添加到L中。根據STDP的標記過程,一些樣本例如樣本x2和x3,將沒有機會被標記。實際上,這種情況破壞了密度峰值聚類發(fā)現的結構。
為了在不影響密度峰值聚類發(fā)現的結構的情況下過濾出噪聲實例,深入分析了密度峰值聚類在STDP中的作用。實際上,密度峰值聚類揭示的結構的功能是在STDP中提供帶有標記順序的未標記樣本。因此,重新設計了密度峰值聚類揭示的結構。同時通過密度峰值聚類而不是X之間的連接關系的結構來獲取所有樣本的標記順序。詳細算法描述如下:
算法2結構揭示算法(DS)
輸入:dc,L,U。
輸出:order。
1.X=[L;U],count=1,order=?;
2.arrows=密度峰值聚類算法(X,dc);
3.for數據集X的每一個xi
4.order(i)=0;
5.end;
6.重復上述步驟,直到從U中選擇所有L樣本的“下一個”點;
7.if未標記樣本xi是L樣本的“下一個”點
8.order(i)=count,L=L∪xi,U=U-xi;
9.end if
10.count=count+1;
11.重復上述步驟,直到從U中選擇所有L的樣本點;
12.if未標記樣本xi是L樣本的“前一個”點
13.order(xi)=count,L=L∪xi,U=U-xi;
14.end if;
15.count=count+1;
算法2返回變量order,該變量記錄X中所有樣本的標記順序。例如,如果樣本xi在第一次迭代中被標記,則order(xi)=1。此策略避免了圖2中描述的問題。詳細地說,第1行是初始化變量,第2行是運行密度峰值聚類。密度峰值聚類的算法返回arrows。如果樣本xi指向樣本xj,則arrows(i)=j。第3-第5行將初始化order。第6-第15行將根據arrows中隱含的結構和STDP的標記過程來計算order。算法2的時間復雜度為O(n2),因為算法2中最耗時的步驟是時間復雜度為O(n2)的第2行。
圖3顯示了算法2的示例,其中每個樣本旁邊都有一個數字。這些數字表示何時標記了相應的樣本,通過算法2獲得的結構更加清晰和易于理解。其中max(order)表示STDPNF中的最大迭代次數,另外每個樣本在初始L中的order為0,因為它們不需要預測。
圖3 算法2揭示的樣本標記序列
ENaNE是一個局部噪聲濾波器,用于刪除噪聲實例,由于NaN是無參數的,使用NaN(x)表示樣本x的局部鄰域[15]。為了量化樣本x及其局部鄰域之間的差異,定義了樣本x的負面影響度和正面影響度。
定義3x的負面影響度:樣本x的負面影響度可定義如下,表示樣本對于分類作用的負面影響程度。
Harmfulness(x)=|{z|z∈NaN(x) and label(z)≠label(x)}|
(6)
定義4x的正面影響度:樣本x的正面影響度可以定義如下,表示樣本對于分類作用的正面影響程度。
Usefulness(x)=|{z|z∈NaN(x) and label(z)==label(x)}|
(7)
式中:label(x)是返回樣本x的類標簽的函數。在定義3和定義4中,|·|表示集合的元素編號。例如,|{y|y∈
NaN(x) andl(z)≠l(x)}|表示集合{z|z∈NaN(x) andl(z)≠l(x)}的元素編號。已知樣本x的正面影響度是實例z的數量,式中NaN(x)包含z且z的標簽與樣本x的標簽相同。相比之下,樣本x的有害性是實例z的數量,式中NaN(x)包含z且z的標簽與樣本x的標簽不同。如果一個樣本x是一個噪聲實例,它的類標簽與其在一個局部鄰域即NaN(x)中的大多數周圍樣本不同,那么它的負面影響度自然大于它的正面影響度。
定義5噪聲實例:如果樣本x是一個噪聲實例,它應該滿足以下條件:
Harmfulness(x)>Usefulness(x)
(8)
根據定義5,可以濾除噪聲實例而無需任何其他參數,因為NaN是無參數的。但是在半監(jiān)督學習中,L通常非常稀缺,而U豐富且易于使用。當計算給定樣本的正面影響度和負面影響度時,大量樣本都沒有被標記。因此,使用一種自訓練方法來預測這些未標記的樣本,這些樣本將用于計算給定樣本的正面影響度和負面影響度。
算法3返回沒有噪聲實例的剪輯集。ENaNE也可以刪除異常值,因為異常值的NaN數通常為0,如第2行所示。在第3行中,將使用自訓練方法來預測這些未標記樣本,該方法將用于計算給定樣本的正面影響度和負面影響度,其中未標記樣本的預測順序是基于變量order的。第4-第6行用于過濾噪聲實例。本文中ENaNE中使用的自訓練方法的基分類器是KNN,其中k=λ由算法1計算。λ已經被用來解決實例約簡、聚類和離群值檢測中選擇參數k的問題。
算法3擴展的自然鄰域剪輯算法(ENaNE)
輸入:濾波樣本,order,NaN,λ。
輸出:剪輯的數據集ES。
1.ES=?;
2.for所有濾波樣本的每一個xi
3.計算給定樣本的正面影響度和負面影響度,其中未標記樣本的預測順序是基于變量order,然后使用自訓練方法來預測這些未標記樣本;
4.ifHarmfulness(x)>Usefulness(x);
5.ES=ES∪xi;
6.end if
7.end for
結果顯示,ENaNE克服了參數依賴性的問題,原因如下:(1) 局部鄰域沒有參數;(2) NaNs和λ在算法1中自動計算,而order在算法2中自動計算。此外,ENaNE更適合半監(jiān)督學習,因為它可以利用標記和未標記的數據。圖4顯示了算法3的過濾過程的示例。圖4(a)顯示了數據的分布,其中每個樣本都具有由密度峰值聚類顯示的相應標記順序。在圖4(b)中,當標記樣本x1時,運行算法3來確定樣本x1是否為噪聲實例。首先,發(fā)現NaN(x1)包含樣本x2和x3,其中樣本x2和x3未標記,并分別被綠色矩形包圍。接下來,使用具有KNN(k=λ)分類器的自訓練方法,根據樣本x2和x3對應的標記順序來預測這兩個樣本。如果正確預測了樣本x2和x3,則將通過ENaNE將x1作為噪聲實例刪除。
(a) 數據的分布
(b) 過濾結果圖4 描述算法3的過濾過程示例
算法4給出了本文提出的自訓練方法。在第1行中,找到所有樣本的標記順序。在第2行中,搜索自然鄰域。在第3-第10行中,通過連續(xù)標記未標記的樣本、濾除噪聲實例并更新L和U來迭代訓練給定的KNN分類器C。最終,可以在第13行訓練所需的分類器C并輸出。
算法4SDTPNF
輸入:dc,L,U。
輸出:訓練的KNN分類器C。
1.order=DS(L,U,dc);
2.[NaN,λ]=NaN_Search(L∪U);
3.通過L訓練KNN分類器C;
4.count=1;
5.重復上述步驟,直到count>max;
6.從U中選擇數據集TS,其中order=count;
7.用分類器C標記樣本TS;
8.Filter_TS=ENaNE(TS,order,NaN,λ);
9.更新標記數據集L;
10.更新未標記數據集U;
11.通過L再次訓練分類器C;
12.count=count+1;
13.通過L再次訓練分類器C;
本文使用具有8 GB內存、Core i7 CPU和64位操作系統(tǒng)的PC進行實驗,以驗證本節(jié)中提出的算法的效率。另外,使用MATLAB2015編寫所有算法的代碼。從加州大學歐文分校存儲庫中選擇了18個實驗基準數據集。表1中列出了數據集的描述。在所有實驗中,均使用10倍交叉驗證策略來確定ACC和STD的最終實驗結果。
(9)
(10)
(11)
表1 數據集描述
訓練集占了所有數據的90%,測試集占10%。在訓練集中,使用隨機分層選擇將訓練集分為標記部分L和未標記部分U??偣策M行4個實驗以驗證所提出算法。簡要說明如下:
(1) 實驗一是將該算法與現有的代表性工作進行比較,其中L的比率為10%。
(2) 實驗二是通過將其與現有代表性的局部噪聲濾波器,其中L的比率為10%,通過比較,來驗證提出的STDPNF中使用的局部噪聲濾波器的優(yōu)勢。
(3) 在實驗三中,討論了L的比率的影響,其中將L的百分比從10%增加到90%。
(4) 在實驗四中,比較了僅執(zhí)行10次的所有代表性算法的運行時間。同樣,L的比例為10%。
在所有的實驗中,都把KNN作為基分類器,因為在KNN中通常使用局部噪聲濾波器來去除噪聲實例。
實驗一:自訓練算法比較。選擇的代表性算法如表2所示,其中比較算法的參數按建議設置。請注意,所提出的算法STDPNF具有參數dc。此外,每種算法的解釋如下:
(1) 文獻[6]提出了SETRED,它結合了CEWS以自訓練方法過濾掉噪聲實例。
(2) 文獻[8]提出了MLSTE,其中ENN用于通過自訓練方法濾除噪聲實例。盡管提出將MLSTE應用于多標簽任務,但也可以將其應用于單標簽任務。
(3) 文獻[16]提出了采用半監(jiān)督模糊C均值自訓練(self-training with semi-supervised fuzzy C means,STSFCM),其中使用模糊C均值聚類指導自訓練方法來訓練有效的分類器。
(4) 文獻[17]提出了STDP。STDP可以訓練有效的分類器,將密度峰值聚類揭示的特征空間結構集成到自訓練過程中以訓練有效的分類器。
表2 比較算法和參數
表3和圖5顯示了實驗結果。表3顯示,與比較算法相比,STDPNF通常可以訓練更好的KNN。另外提出的算法3中獲得了18個數據集中的15個的最高ACC。此外,表3中所有數據集上STDPNF的平均ACC也是最高的。在ILPD的數據集上,STDPNF的ACC低于STDP??赡艿脑蚴荅NaNE中的自訓練方法會錯誤地預測未標記樣本的類標簽,從而削弱了ENaNE的能力。但是,在大多數數據集中,STDPNF的ACC都高于STDP,這表明STDPNF可以使用ENaNE有效地去除具有錯誤預測的樣本。圖5是所有數據集的ACC直方圖,表明STDPNF明顯達到了最佳ACC。綜上所述,STDPNF在改善KNN性能方面比現有工作表現更好,并且可以有效去除標記錯誤樣本。
表3 分類準確率實驗結果(%)
續(xù)表3
圖5 18個UCI數據集的準確性直方圖
實驗二:局部噪聲濾波器的比較。為了比較,選擇5個代表性的局部噪聲濾波器,例如ENN[8]、規(guī)則剪輯近鄰(edited nearest-neighbor rule,RENN)[18]、自適應K近鄰(adaptive K nearest-neighbor,AKNN)[19]、多標簽剪輯近鄰(multi-labled edited nearest-neighbor,MENN)[20]和CEWS。上述濾波器已被應用于自訓練方法,以解決標記錯誤問題。然后,分別使用這5個代表性的局部噪聲濾波器來消除STDP中的噪聲實例(STDP_ENN、STDP_RENN、STDP_AKNN、STDP_MENN和STDP_CEWS)。表4給出了這些比較算法及其參數。
表4 濾波器比較算法和參數
根據相關文獻令所有比較算法中的Pa=2。同樣,將所有比較算法中的參數設置與先前使用一致。表5和表6給出了一些實驗結果,以驗證STDPNF中使用的ENaNE的優(yōu)越性。表5中的ENN、RENN、AKNN和MENN的k為3,而表6中的ENN、RENN、AKNN和MENN的k為5。
表5 STDP結合局部噪聲濾波器的比較結果(ACC和STD,k=3)(%)
續(xù)表5
表6 STDP結合局部噪聲濾波器的比較結果(ACC和STD,k=5)(%)
從表5和表6中可以看出,STDPNF實現了最佳性能。所提出的算法在表5和表6中的13個數據集中有8個達到了最高的ACC。STDPNF中所有數據集的平均ACC也是最高的。此外,可以發(fā)現,STDP中所有數據集的平均ACC均高于STDP_ENN、STDP_RENN、STDP_AKNN、STDP_MENN和STDP_CEWS。原因可能是另外5個代表性的局部噪聲濾波器僅通過利用L的信息來濾除噪聲,因此使得跟蹤準確率不高。綜合結果可知,這5個代表性的局部噪聲濾波器可以濾除STDP中具有正確預測的樣本。與5個代表性的局部噪聲濾波器相比,ENaNE可以通過利用L和U的信息來濾除噪聲實例。因此,STDPNF獲得最佳結果。此外,ENaNE是無參數的。所有這些證據證明,所提出算法中使用的ENaNE優(yōu)于自訓練方法中使用的現有局部噪聲濾波器。
實驗三:標記樣本比例的影響。本節(jié)將進一步討論實驗中不同比例L的影響。同時,選擇STSFCM、STDP、STDP_ENN和STDP_AKNN作為比較算法,因為它們在實驗一和實驗二中的性能相對較高。STDP_ENN和STDP_AKNN中的局部噪聲濾波器的k為3。圖6顯示了關于6個數據集上L的不同百分比的不同算法的ACC。
(a) 數據集:IMS
(b) 數據集:LIV
(c) 數據集:ION
(d) 數據集:ECO
(e) 數據集:WIL
(f) 數據集:BRT圖6 算法ACC與標記樣本比例的關系
從圖6可以看出,所有算法的ACC隨L的比例的增加而增加。當L的比例相對較高時,所有算法均獲得相似的結果。此外,在L比例不同的情況下,提出的算法在LIV、LON、ECO和WIL數據集上也取得了良好的結果。具體地,還可以發(fā)現,當L的比例相對較低時,提出的算法在LIV、LON、ECO和WIL的數據集上都能取得更好的效果。原因是當L較小時,提出的算法可以用ENaNE通過利用U的附加信息來濾除噪聲實例。根據先前工作的介紹,大多數現有的局部噪聲濾波器需要更多的L才能更好地工作。相比之下,即使L不足夠,提出的算法中使用的ENaNE也可以有效地刪除標記錯誤的實例。因此該算法具有明顯的優(yōu)勢。
盡管所提出的算法在BRT和IMS數據集上的效果不佳,但是所有算法在具有不同L值的BRT和IMS數據集上都具有相似的結果。另外,當將數據集ION上的L的百分比從20%增加到40%時,STDP_ENN、STDP_AKNN、STSFCM、STDP和STDPNF的準確性會大大降低。這是因為STDPNF的ENaNE中的自訓練方法錯誤地預測了未標記樣本的類標簽,這削弱了STDPNF的ENaNE的能力,另外STDP、STSFCM、STDP_ENN和STDP_ALLENN向L添加了錯誤預測的未標記樣本。
實驗四:訓練時間測試。很難分析自訓練方法的時間復雜度。因此,本節(jié)將通過在9個數據集上比較表2中列出的所有自標記算法中的中央處理器(CPU)運行時間來說明STDPNF的計算效率。在STDPNF中發(fā)現結構的時間復雜度為O(n2),在STDPNF中搜索NaNs的時間復雜度為O(nlogn)。STDPNF中ENaNE的運行時間取決于ENaNE中自訓練方法的運行時間。
表7中給出了相應的算法執(zhí)行時間對比結果。盡管STDPNF比STDP消耗更多的時間,但它并不是最耗時的算法。實際上,因為MLSTE中的ENN和SETRED中的CEWS具有較高的時間復雜度(O(n3)),所以SETRED和MLSTE比STDPNF消耗更多的時間。此外,在某些數據集,例如UKM、SPH和LIV上,STSFCM還比STDPNF消耗更多的時間,因為SFCM需要在自訓練過程的每次迭代中運行。權衡STDPNF的優(yōu)缺點,STDPNF的計算效率是可以接受的。
表7 不同算法訓練時間對比結果 單位:s
針對自訓練方法中局部噪聲濾波器存在的參數依賴性以及僅使用標記數據來刪除標記錯誤樣本等局限性,提出了一種基于密度峰值和無參數局部噪聲濾波器自訓練方法。通過四個對比試驗可得出如下結論:
(1) 所提出算法在提高基分類器KNN的分類精度方面比現有工作更有效。
(2) 所提出算法中使用的局部噪聲濾波器克服了現有局部噪聲濾波器的技術缺陷。它能夠不依賴參數選取,更具有自適應性。即使標記數據不足,它也可以通過利用未標記數據的附加信息來刪除標記錯誤的樣本,驗證了該算法具有更好的泛化能力。
(3) 所提出算法的計算效率和執(zhí)行時間處在可接受的范圍內。
下一步應將所提出的算法應用于多標簽分類任務。