孫 彩 鋒

(山西大同大學(xué)物理與電子科學(xué)學(xué)院 山西 大同 037009)

0 引 言

半監(jiān)督學(xué)習(xí)由于可以通過(guò)同時(shí)利用未標(biāo)記數(shù)據(jù)和標(biāo)記數(shù)據(jù)來(lái)進(jìn)行數(shù)據(jù)樣本改進(jìn)，降低了對(duì)數(shù)據(jù)樣本的要求，在諸多領(lǐng)域得到了廣泛的應(yīng)用[1-2]。而在半監(jiān)督學(xué)習(xí)分類(lèi)器發(fā)展過(guò)程中，自訓(xùn)練方法也以其簡(jiǎn)單、高效和自適應(yīng)等特點(diǎn)被認(rèn)為是最具代表性的方法之一，因此得到了學(xué)界廣泛的討論和研究[3-4]。

在自我訓(xùn)練方法中，錯(cuò)誤標(biāo)注是一個(gè)非常普遍、棘手甚至不可避免的問(wèn)題[5]。一般情況下，自訓(xùn)練方法將誤標(biāo)記樣本視為噪聲實(shí)例，嚴(yán)重扭曲了數(shù)據(jù)的分布，降低半監(jiān)督學(xué)習(xí)的泛化能力。因此，提出了一系列基于局部噪聲濾波器的自訓(xùn)練算法，其中，剪輯自訓(xùn)練(self-training with editing,SETRED)和鄰域自訓(xùn)練(self-training nearest neighbor rule using cut edges,SNNRCE)使用切邊權(quán)值統(tǒng)計(jì)(cut edge weight statistic,CEWS)來(lái)濾除噪聲實(shí)例[6-7]，多標(biāo)簽剪輯自訓(xùn)練(multi-label self-training with editing,MLSTE)則使用剪輯最近鄰(edited nearest neighbor,ENN)來(lái)濾除噪聲實(shí)例[8-9]。隨后，Triguero等發(fā)現(xiàn)，在自我訓(xùn)練方法中使用的大多數(shù)現(xiàn)有噪聲濾波器的局部方法沒(méi)有很好地執(zhí)行，特別是當(dāng)標(biāo)記數(shù)據(jù)不足時(shí)，即大多數(shù)自訓(xùn)練方法中使用的局部噪聲濾波器需要更多的標(biāo)記數(shù)據(jù)才能工作[10]。另外，自訓(xùn)練方法中的局部噪聲濾波器主要是k近鄰(k-nearest neighbors,KNN)分類(lèi)器，因此，該方法濾波能力很大程度上依賴(lài)于參數(shù)k[11]。除此之外，現(xiàn)有的局部噪聲濾波器都是基于監(jiān)督學(xué)習(xí)的，因此，它們并不完全與半監(jiān)督學(xué)習(xí)兼容，因?yàn)樗鼈冎豢紤]標(biāo)記數(shù)據(jù)的信息。

針對(duì)上述問(wèn)題，提出了一種基于密度峰值和無(wú)參數(shù)局部噪聲濾波器自訓(xùn)練方法。設(shè)計(jì)的一種新的無(wú)參數(shù)局部噪聲濾波器，既能利用標(biāo)記數(shù)據(jù)，又能利用未標(biāo)記數(shù)據(jù)去除噪聲。

1 理論方法

1.1 基于密度峰值的自訓(xùn)練方法

(1)

(2)

(3)

式中：ρ={ρ1,ρ2,…,ρn}是記錄X中所有樣本的局部密度的集合，即ρi是樣本xi的局部密度，δ={δ1,δ2,…,δn}記錄每個(gè)樣本在X中的最小距離，即δi是樣本xi與具有更高局部密度的任何其他樣本之間的最小距離，通過(guò)計(jì)算ρi和δi，每個(gè)樣本xi都有一個(gè)對(duì)應(yīng)的樣本xj，它是xi最接近的具有更高局部密度ρi的樣本，dij是樣本xi和xj之間的距離。這里采用歐氏距離，dc是具有預(yù)設(shè)值的截止距離。然后，使每個(gè)樣本xi指向其對(duì)應(yīng)的唯一樣本xj。

在揭示特征空間的結(jié)構(gòu)之后，STDP使用密度峰值聚類(lèi)揭示的基礎(chǔ)結(jié)構(gòu)來(lái)幫助訓(xùn)練給定的分類(lèi)器，定義L={x1,x2,…,xl}是X中所有標(biāo)記樣本的集合，U={xl+1,xl+2,…,xn}是X中所有未標(biāo)記樣本的集合。在該分類(lèi)器中，未標(biāo)記樣本被連續(xù)標(biāo)記并添加到L中。該標(biāo)記過(guò)程分為兩個(gè)步驟。第一步是從U迭代地選擇L樣本的所有“下一個(gè)”點(diǎn)并進(jìn)行標(biāo)記。第二步是從U迭代地選擇L樣本的所有“上一個(gè)”點(diǎn)并進(jìn)行標(biāo)記。

1.2 自然鄰域

自然鄰域是沒(méi)有參數(shù)的鄰域，主要想法來(lái)自對(duì)社交網(wǎng)絡(luò)的理解[13]。一個(gè)人擁有的真正朋友的數(shù)量應(yīng)該是將他或她視為朋友并同時(shí)被他或她視為朋友的人數(shù)。如果每個(gè)人至少都有一個(gè)朋友，則在社交網(wǎng)絡(luò)中將形成一個(gè)相對(duì)穩(wěn)定的結(jié)構(gòu)，稱(chēng)為自然穩(wěn)定結(jié)構(gòu)(natural stable structure,NSS)。

定義1自然穩(wěn)定結(jié)構(gòu)：如果x將z視為鄰域并且z同時(shí)將x視為鄰域，則對(duì)象z是對(duì)象x的自然鄰域。如果每個(gè)對(duì)象都有至少一個(gè)自然鄰域，則數(shù)據(jù)集已形成一個(gè)相對(duì)穩(wěn)定的狀態(tài)，稱(chēng)為自然穩(wěn)定結(jié)構(gòu)[13]。

(?xi)(?xj)(r∈n)∨(xi≠xj)→

(xi∈NNr(xj))∨(xj∈NNr(xi))

(4)

式中：NNr(x)={x1,x2,…,xr}是包含樣本x的r個(gè)最近鄰域的集合。在式(4)中，搜索回合r從1增加到λ(λ≤n)，λ是自然鄰域特征值。當(dāng)r=λ時(shí)，NSS在給定的數(shù)據(jù)集中形成。實(shí)際上，數(shù)據(jù)的復(fù)雜性可以用λ表示。值較小的λ表示數(shù)據(jù)規(guī)則或數(shù)據(jù)大小較小，而值較大的λ表示數(shù)據(jù)大小較大。此外，λ已經(jīng)被用來(lái)解決參數(shù)k的問(wèn)題。根據(jù)上面的描述，數(shù)據(jù)對(duì)象的自然鄰域可以表述為：

定義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.從數(shù)據(jù)集X中創(chuàng)造一個(gè)k-d樹(shù)T

3.for數(shù)據(jù)集X的每一個(gè)xi通過(guò)T找到它的第r個(gè)鄰域xj

4.NNk(xi)=NNk(xi)∪{xj}；

5.Nb(xj)=Nb(xj)+1；

6.RNNk(xj)=RNNk(xj)∪{xi}；

7.end for

8.計(jì)算num

9.ifnum沒(méi)變

10.則λ=r；

11.for數(shù)據(jù)集X的每一個(gè)xi

12.NaN(xi)=RNNλ(xi)∩NNλ{(lán)xi};

13.end for

14.返回NaN,λ;

15.else

16.r=r+1;

17.回到第三步;

18.end if

算法1返回NaN和λ。Nb={t1,t2,…,tn}是記錄數(shù)字的集合，式中ti(i=1,2,…,n)是被視為與其他樣本相鄰的樣本xi的數(shù)目。另外，Nb(xi)記錄被視為與其他樣本相鄰的樣本xi的數(shù)量。在第2-7行中，計(jì)算NaN直到形成自然穩(wěn)定結(jié)構(gòu)。算法中增加了一個(gè)限制，即變量num不會(huì)更改，因?yàn)樵肼晻?huì)影響算法1。num是Nb(xi)==0的樣本xi的數(shù)量，式中Nb(xi)表示被視為其他樣本的鄰域樣本xi的數(shù)量。通常，時(shí)間復(fù)雜度為O(nlogn)，因?yàn)樵诘?行中使用了k-d樹(shù)。k-d樹(shù)是劃分k維數(shù)據(jù)空間的數(shù)據(jù)結(jié)構(gòu)。它主要應(yīng)用于多維空間中關(guān)鍵數(shù)據(jù)的搜索。

2 提出的算法

2.1 特征空間的結(jié)構(gòu)揭示

圖1顯示了基于密度峰值和無(wú)參數(shù)局部噪聲濾波器自訓(xùn)練方法(self-training method based on density peaks and an local noise filter,STDPNF)的一般框架，該框架由三部分組成。第一步中，使用密度峰值聚類(lèi)發(fā)現(xiàn)特征空間的基礎(chǔ)結(jié)構(gòu)。然后，將此結(jié)構(gòu)轉(zhuǎn)換為所有樣本的標(biāo)記順序。第二步是一個(gè)標(biāo)準(zhǔn)的自訓(xùn)練過(guò)程，根據(jù)標(biāo)記順序預(yù)測(cè)未標(biāo)記樣本并將其添加到中。此外，擴(kuò)展的自然鄰域剪輯濾波器(extended natural neighbor editing,ENaNE)可以刪除噪聲實(shí)例。第三步用擴(kuò)展的重新訓(xùn)練KNN分類(lèi)器。此后，可以更好地克服標(biāo)記錯(cuò)誤的問(wèn)題，并且可以訓(xùn)練分類(lèi)器。

圖1 STDPNF的框架

在此將重新設(shè)計(jì)密度峰值聚類(lèi)在STDP中顯示的結(jié)構(gòu)，以使其有利于結(jié)合提出的局部噪聲濾波器。STDP存在標(biāo)記錯(cuò)誤的問(wèn)題。因此，打算使用局部噪聲濾波器來(lái)去除STDP中標(biāo)記錯(cuò)誤的樣本。但是，一旦將錯(cuò)誤預(yù)測(cè)的樣本作為噪聲實(shí)例丟棄，與丟棄的樣本關(guān)聯(lián)的幾個(gè)未標(biāo)記樣本將沒(méi)有機(jī)會(huì)被標(biāo)記。圖2給出了一個(gè)例子來(lái)說(shuō)明這種情況。

(a) 揭示特征空間的結(jié)構(gòu)

(b) 錯(cuò)誤標(biāo)記示意圖圖2 標(biāo)記示例

在圖2(a)中，密度峰值聚類(lèi)揭示了特征空間的結(jié)構(gòu)，其中每個(gè)樣本都指向具有更高局部密度的相應(yīng)最近樣本。如圖2(b)所示，樣本x1被錯(cuò)誤地預(yù)測(cè)。如圖2(a)所示，樣本x1應(yīng)屬于類(lèi)1。如果樣本x1作為噪聲實(shí)例被丟棄，則樣本x1將不會(huì)添加到L中。根據(jù)STDP的標(biāo)記過(guò)程，一些樣本例如樣本x2和x3，將沒(méi)有機(jī)會(huì)被標(biāo)記。實(shí)際上，這種情況破壞了密度峰值聚類(lèi)發(fā)現(xiàn)的結(jié)構(gòu)。

為了在不影響密度峰值聚類(lèi)發(fā)現(xiàn)的結(jié)構(gòu)的情況下過(guò)濾出噪聲實(shí)例，深入分析了密度峰值聚類(lèi)在STDP中的作用。實(shí)際上，密度峰值聚類(lèi)揭示的結(jié)構(gòu)的功能是在STDP中提供帶有標(biāo)記順序的未標(biāo)記樣本。因此，重新設(shè)計(jì)了密度峰值聚類(lèi)揭示的結(jié)構(gòu)。同時(shí)通過(guò)密度峰值聚類(lèi)而不是X之間的連接關(guān)系的結(jié)構(gòu)來(lái)獲取所有樣本的標(biāo)記順序。詳細(xì)算法描述如下：

算法2結(jié)構(gòu)揭示算法(DS)

輸入：dc,L,U。

輸出：order。

1.X=[L;U],count=1,order=?;

2.arrows=密度峰值聚類(lèi)算法(X,dc);

3.for數(shù)據(jù)集X的每一個(gè)xi

4.order(i)=0；

5.end；

6.重復(fù)上述步驟，直到從U中選擇所有L樣本的“下一個(gè)”點(diǎn)；

7.if未標(biāo)記樣本xi是L樣本的“下一個(gè)”點(diǎn)

8.order(i)=count,L=L∪xi,U=U-xi;

9.end if

10.count=count+1；

11.重復(fù)上述步驟，直到從U中選擇所有L的樣本點(diǎn)；

12.if未標(biāo)記樣本xi是L樣本的“前一個(gè)”點(diǎn)

13.order(xi)=count,L=L∪xi,U=U-xi；

14.end if;

15.count=count+1;

算法2返回變量order，該變量記錄X中所有樣本的標(biāo)記順序。例如，如果樣本xi在第一次迭代中被標(biāo)記，則order(xi)=1。此策略避免了圖2中描述的問(wèn)題。詳細(xì)地說(shuō)，第1行是初始化變量，第2行是運(yùn)行密度峰值聚類(lèi)。密度峰值聚類(lèi)的算法返回arrows。如果樣本xi指向樣本xj，則arrows(i)=j。第3-第5行將初始化order。第6-第15行將根據(jù)arrows中隱含的結(jié)構(gòu)和STDP的標(biāo)記過(guò)程來(lái)計(jì)算order。算法2的時(shí)間復(fù)雜度為O(n2)，因?yàn)樗惴?中最耗時(shí)的步驟是時(shí)間復(fù)雜度為O(n2)的第2行。

圖3顯示了算法2的示例，其中每個(gè)樣本旁邊都有一個(gè)數(shù)字。這些數(shù)字表示何時(shí)標(biāo)記了相應(yīng)的樣本，通過(guò)算法2獲得的結(jié)構(gòu)更加清晰和易于理解。其中max(order)表示STDPNF中的最大迭代次數(shù)，另外每個(gè)樣本在初始L中的order為0，因?yàn)樗鼈儾恍枰A(yù)測(cè)。

圖3 算法2揭示的樣本標(biāo)記序列

2.2 擴(kuò)展的無(wú)參數(shù)局部噪聲濾波器

ENaNE是一個(gè)局部噪聲濾波器，用于刪除噪聲實(shí)例，由于NaN是無(wú)參數(shù)的，使用NaN(x)表示樣本x的局部鄰域[15]。為了量化樣本x及其局部鄰域之間的差異，定義了樣本x的負(fù)面影響度和正面影響度。

定義3x的負(fù)面影響度：樣本x的負(fù)面影響度可定義如下，表示樣本對(duì)于分類(lèi)作用的負(fù)面影響程度。

Harmfulness(x)=|{z|z∈NaN(x) and label(z)≠label(x)}|

(6)

定義4x的正面影響度：樣本x的正面影響度可以定義如下，表示樣本對(duì)于分類(lèi)作用的正面影響程度。

Usefulness(x)=|{z|z∈NaN(x) and label(z)==label(x)}|

(7)

式中：label(x)是返回樣本x的類(lèi)標(biāo)簽的函數(shù)。在定義3和定義4中，|·|表示集合的元素編號(hào)。例如，|{y|y∈

NaN(x) andl(z)≠l(x)}|表示集合{z|z∈NaN(x) andl(z)≠l(x)}的元素編號(hào)。已知樣本x的正面影響度是實(shí)例z的數(shù)量，式中NaN(x)包含z且z的標(biāo)簽與樣本x的標(biāo)簽相同。相比之下，樣本x的有害性是實(shí)例z的數(shù)量，式中NaN(x)包含z且z的標(biāo)簽與樣本x的標(biāo)簽不同。如果一個(gè)樣本x是一個(gè)噪聲實(shí)例，它的類(lèi)標(biāo)簽與其在一個(gè)局部鄰域即NaN(x)中的大多數(shù)周?chē)鷺颖静煌敲此呢?fù)面影響度自然大于它的正面影響度。

定義5噪聲實(shí)例：如果樣本x是一個(gè)噪聲實(shí)例，它應(yīng)該滿(mǎn)足以下條件：

Harmfulness(x)>Usefulness(x)

(8)

根據(jù)定義5，可以濾除噪聲實(shí)例而無(wú)需任何其他參數(shù)，因?yàn)镹aN是無(wú)參數(shù)的。但是在半監(jiān)督學(xué)習(xí)中，L通常非常稀缺，而U豐富且易于使用。當(dāng)計(jì)算給定樣本的正面影響度和負(fù)面影響度時(shí)，大量樣本都沒(méi)有被標(biāo)記。因此，使用一種自訓(xùn)練方法來(lái)預(yù)測(cè)這些未標(biāo)記的樣本，這些樣本將用于計(jì)算給定樣本的正面影響度和負(fù)面影響度。

算法3返回沒(méi)有噪聲實(shí)例的剪輯集。ENaNE也可以刪除異常值，因?yàn)楫惓Ｖ档腘aN數(shù)通常為0，如第2行所示。在第3行中，將使用自訓(xùn)練方法來(lái)預(yù)測(cè)這些未標(biāo)記樣本，該方法將用于計(jì)算給定樣本的正面影響度和負(fù)面影響度，其中未標(biāo)記樣本的預(yù)測(cè)順序是基于變量order的。第4-第6行用于過(guò)濾噪聲實(shí)例。本文中ENaNE中使用的自訓(xùn)練方法的基分類(lèi)器是KNN，其中k=λ由算法1計(jì)算。λ已經(jīng)被用來(lái)解決實(shí)例約簡(jiǎn)、聚類(lèi)和離群值檢測(cè)中選擇參數(shù)k的問(wèn)題。

算法3擴(kuò)展的自然鄰域剪輯算法(ENaNE)

輸入：濾波樣本，order，NaN,λ。

輸出：剪輯的數(shù)據(jù)集ES。

1.ES=?；

2.for所有濾波樣本的每一個(gè)xi

3.計(jì)算給定樣本的正面影響度和負(fù)面影響度，其中未標(biāo)記樣本的預(yù)測(cè)順序是基于變量order，然后使用自訓(xùn)練方法來(lái)預(yù)測(cè)這些未標(biāo)記樣本；

4.ifHarmfulness(x)>Usefulness(x)；

5.ES=ES∪xi；

6.end if

7.end for

結(jié)果顯示，ENaNE克服了參數(shù)依賴(lài)性的問(wèn)題，原因如下：(1) 局部鄰域沒(méi)有參數(shù)；(2) NaNs和λ在算法1中自動(dòng)計(jì)算，而order在算法2中自動(dòng)計(jì)算。此外，ENaNE更適合半監(jiān)督學(xué)習(xí)，因?yàn)樗梢岳脴?biāo)記和未標(biāo)記的數(shù)據(jù)。圖4顯示了算法3的過(guò)濾過(guò)程的示例。圖4(a)顯示了數(shù)據(jù)的分布，其中每個(gè)樣本都具有由密度峰值聚類(lèi)顯示的相應(yīng)標(biāo)記順序。在圖4(b)中，當(dāng)標(biāo)記樣本x1時(shí)，運(yùn)行算法3來(lái)確定樣本x1是否為噪聲實(shí)例。首先，發(fā)現(xiàn)NaN(x1)包含樣本x2和x3，其中樣本x2和x3未標(biāo)記，并分別被綠色矩形包圍。接下來(lái)，使用具有KNN(k=λ)分類(lèi)器的自訓(xùn)練方法，根據(jù)樣本x2和x3對(duì)應(yīng)的標(biāo)記順序來(lái)預(yù)測(cè)這兩個(gè)樣本。如果正確預(yù)測(cè)了樣本x2和x3，則將通過(guò)ENaNE將x1作為噪聲實(shí)例刪除。

(a) 數(shù)據(jù)的分布

(b) 過(guò)濾結(jié)果圖4 描述算法3的過(guò)濾過(guò)程示例

2.3 提出的自訓(xùn)練方法

算法4給出了本文提出的自訓(xùn)練方法。在第1行中，找到所有樣本的標(biāo)記順序。在第2行中，搜索自然鄰域。在第3-第10行中，通過(guò)連續(xù)標(biāo)記未標(biāo)記的樣本、濾除噪聲實(shí)例并更新L和U來(lái)迭代訓(xùn)練給定的KNN分類(lèi)器C。最終，可以在第13行訓(xùn)練所需的分類(lèi)器C并輸出。

算法4SDTPNF

輸入：dc,L,U。

輸出：訓(xùn)練的KNN分類(lèi)器C。

1.order=DS(L,U,dc);

2.[NaN,λ]=NaN_Search(L∪U);

3.通過(guò)L訓(xùn)練KNN分類(lèi)器C；

4.count=1；

5.重復(fù)上述步驟，直到count>max；

6.從U中選擇數(shù)據(jù)集TS，其中order=count；

7.用分類(lèi)器C標(biāo)記樣本TS；

8.Filter_TS=ENaNE(TS,order,NaN,λ);

9.更新標(biāo)記數(shù)據(jù)集L；

10.更新未標(biāo)記數(shù)據(jù)集U；

11.通過(guò)L再次訓(xùn)練分類(lèi)器C；

12.count=count+1；

13.通過(guò)L再次訓(xùn)練分類(lèi)器C；

3 實(shí)驗(yàn)與結(jié)果分析

3.1 數(shù)據(jù)集和實(shí)驗(yàn)設(shè)置

本文使用具有8 GB內(nèi)存、Core i7 CPU和64位操作系統(tǒng)的PC進(jìn)行實(shí)驗(yàn)，以驗(yàn)證本節(jié)中提出的算法的效率。另外，使用MATLAB2015編寫(xiě)所有算法的代碼。從加州大學(xué)歐文分校存儲(chǔ)庫(kù)中選擇了18個(gè)實(shí)驗(yàn)基準(zhǔn)數(shù)據(jù)集。表1中列出了數(shù)據(jù)集的描述。在所有實(shí)驗(yàn)中，均使用10倍交叉驗(yàn)證策略來(lái)確定ACC和STD的最終實(shí)驗(yàn)結(jié)果。

(9)

(10)

(11)

表1 數(shù)據(jù)集描述

訓(xùn)練集占了所有數(shù)據(jù)的90%，測(cè)試集占10%。在訓(xùn)練集中，使用隨機(jī)分層選擇將訓(xùn)練集分為標(biāo)記部分L和未標(biāo)記部分U?？偣策M(jìn)行4個(gè)實(shí)驗(yàn)以驗(yàn)證所提出算法。簡(jiǎn)要說(shuō)明如下：

(1) 實(shí)驗(yàn)一是將該算法與現(xiàn)有的代表性工作進(jìn)行比較，其中L的比率為10%。

(2) 實(shí)驗(yàn)二是通過(guò)將其與現(xiàn)有代表性的局部噪聲濾波器，其中L的比率為10%，通過(guò)比較，來(lái)驗(yàn)證提出的STDPNF中使用的局部噪聲濾波器的優(yōu)勢(shì)。

(3) 在實(shí)驗(yàn)三中，討論了L的比率的影響，其中將L的百分比從10%增加到90%。

(4) 在實(shí)驗(yàn)四中，比較了僅執(zhí)行10次的所有代表性算法的運(yùn)行時(shí)間。同樣，L的比例為10%。

在所有的實(shí)驗(yàn)中，都把KNN作為基分類(lèi)器，因?yàn)樵贙NN中通常使用局部噪聲濾波器來(lái)去除噪聲實(shí)例。

3.2 實(shí)驗(yàn)結(jié)果對(duì)比分析

實(shí)驗(yàn)一：自訓(xùn)練算法比較。選擇的代表性算法如表2所示，其中比較算法的參數(shù)按建議設(shè)置。請(qǐng)注意，所提出的算法STDPNF具有參數(shù)dc。此外，每種算法的解釋如下：

(1) 文獻(xiàn)[6]提出了SETRED，它結(jié)合了CEWS以自訓(xùn)練方法過(guò)濾掉噪聲實(shí)例。

(2) 文獻(xiàn)[8]提出了MLSTE，其中ENN用于通過(guò)自訓(xùn)練方法濾除噪聲實(shí)例。盡管提出將MLSTE應(yīng)用于多標(biāo)簽任務(wù)，但也可以將其應(yīng)用于單標(biāo)簽任務(wù)。

(3) 文獻(xiàn)[16]提出了采用半監(jiān)督模糊C均值自訓(xùn)練(self-training with semi-supervised fuzzy C means,STSFCM)，其中使用模糊C均值聚類(lèi)指導(dǎo)自訓(xùn)練方法來(lái)訓(xùn)練有效的分類(lèi)器。

(4) 文獻(xiàn)[17]提出了STDP。STDP可以訓(xùn)練有效的分類(lèi)器，將密度峰值聚類(lèi)揭示的特征空間結(jié)構(gòu)集成到自訓(xùn)練過(guò)程中以訓(xùn)練有效的分類(lèi)器。

表2 比較算法和參數(shù)

表3和圖5顯示了實(shí)驗(yàn)結(jié)果。表3顯示，與比較算法相比，STDPNF通?？梢杂?xùn)練更好的KNN。另外提出的算法3中獲得了18個(gè)數(shù)據(jù)集中的15個(gè)的最高ACC。此外，表3中所有數(shù)據(jù)集上STDPNF的平均ACC也是最高的。在ILPD的數(shù)據(jù)集上，STDPNF的ACC低于STDP?？赡艿脑蚴荅NaNE中的自訓(xùn)練方法會(huì)錯(cuò)誤地預(yù)測(cè)未標(biāo)記樣本的類(lèi)標(biāo)簽，從而削弱了ENaNE的能力。但是，在大多數(shù)數(shù)據(jù)集中，STDPNF的ACC都高于STDP，這表明STDPNF可以使用ENaNE有效地去除具有錯(cuò)誤預(yù)測(cè)的樣本。圖5是所有數(shù)據(jù)集的ACC直方圖，表明STDPNF明顯達(dá)到了最佳ACC。綜上所述，STDPNF在改善KNN性能方面比現(xiàn)有工作表現(xiàn)更好，并且可以有效去除標(biāo)記錯(cuò)誤樣本。

表3 分類(lèi)準(zhǔn)確率實(shí)驗(yàn)結(jié)果(%)

續(xù)表3

圖5 18個(gè)UCI數(shù)據(jù)集的準(zhǔn)確性直方圖

實(shí)驗(yàn)二：局部噪聲濾波器的比較。為了比較，選擇5個(gè)代表性的局部噪聲濾波器，例如ENN[8]、規(guī)則剪輯近鄰(edited nearest-neighbor rule,RENN)[18]、自適應(yīng)K近鄰(adaptive K nearest-neighbor,AKNN)[19]、多標(biāo)簽剪輯近鄰(multi-labled edited nearest-neighbor,MENN)[20]和CEWS。上述濾波器已被應(yīng)用于自訓(xùn)練方法，以解決標(biāo)記錯(cuò)誤問(wèn)題。然后，分別使用這5個(gè)代表性的局部噪聲濾波器來(lái)消除STDP中的噪聲實(shí)例(STDP_ENN、STDP_RENN、STDP_AKNN、STDP_MENN和STDP_CEWS)。表4給出了這些比較算法及其參數(shù)。

表4 濾波器比較算法和參數(shù)

根據(jù)相關(guān)文獻(xiàn)令所有比較算法中的Pa=2。同樣，將所有比較算法中的參數(shù)設(shè)置與先前使用一致。表5和表6給出了一些實(shí)驗(yàn)結(jié)果，以驗(yàn)證STDPNF中使用的ENaNE的優(yōu)越性。表5中的ENN、RENN、AKNN和MENN的k為3，而表6中的ENN、RENN、AKNN和MENN的k為5。

表5 STDP結(jié)合局部噪聲濾波器的比較結(jié)果(ACC和STD，k=3)(%)

續(xù)表5

表6 STDP結(jié)合局部噪聲濾波器的比較結(jié)果(ACC和STD，k=5)(%)

從表5和表6中可以看出，STDPNF實(shí)現(xiàn)了最佳性能。所提出的算法在表5和表6中的13個(gè)數(shù)據(jù)集中有8個(gè)達(dá)到了最高的ACC。STDPNF中所有數(shù)據(jù)集的平均ACC也是最高的。此外，可以發(fā)現(xiàn)，STDP中所有數(shù)據(jù)集的平均ACC均高于STDP_ENN、STDP_RENN、STDP_AKNN、STDP_MENN和STDP_CEWS。原因可能是另外5個(gè)代表性的局部噪聲濾波器僅通過(guò)利用L的信息來(lái)濾除噪聲，因此使得跟蹤準(zhǔn)確率不高。綜合結(jié)果可知，這5個(gè)代表性的局部噪聲濾波器可以濾除STDP中具有正確預(yù)測(cè)的樣本。與5個(gè)代表性的局部噪聲濾波器相比，ENaNE可以通過(guò)利用L和U的信息來(lái)濾除噪聲實(shí)例。因此，STDPNF獲得最佳結(jié)果。此外，ENaNE是無(wú)參數(shù)的。所有這些證據(jù)證明，所提出算法中使用的ENaNE優(yōu)于自訓(xùn)練方法中使用的現(xiàn)有局部噪聲濾波器。

實(shí)驗(yàn)三：標(biāo)記樣本比例的影響。本節(jié)將進(jìn)一步討論實(shí)驗(yàn)中不同比例L的影響。同時(shí)，選擇STSFCM、STDP、STDP_ENN和STDP_AKNN作為比較算法，因?yàn)樗鼈冊(cè)趯?shí)驗(yàn)一和實(shí)驗(yàn)二中的性能相對(duì)較高。STDP_ENN和STDP_AKNN中的局部噪聲濾波器的k為3。圖6顯示了關(guān)于6個(gè)數(shù)據(jù)集上L的不同百分比的不同算法的ACC。

(a) 數(shù)據(jù)集：IMS

(b) 數(shù)據(jù)集：LIV

(c) 數(shù)據(jù)集：ION

(d) 數(shù)據(jù)集：ECO

(e) 數(shù)據(jù)集：WIL

(f) 數(shù)據(jù)集：BRT圖6 算法ACC與標(biāo)記樣本比例的關(guān)系

從圖6可以看出，所有算法的ACC隨L的比例的增加而增加。當(dāng)L的比例相對(duì)較高時(shí)，所有算法均獲得相似的結(jié)果。此外，在L比例不同的情況下，提出的算法在LIV、LON、ECO和WIL數(shù)據(jù)集上也取得了良好的結(jié)果。具體地，還可以發(fā)現(xiàn)，當(dāng)L的比例相對(duì)較低時(shí)，提出的算法在LIV、LON、ECO和WIL的數(shù)據(jù)集上都能取得更好的效果。原因是當(dāng)L較小時(shí)，提出的算法可以用ENaNE通過(guò)利用U的附加信息來(lái)濾除噪聲實(shí)例。根據(jù)先前工作的介紹，大多數(shù)現(xiàn)有的局部噪聲濾波器需要更多的L才能更好地工作。相比之下，即使L不足夠，提出的算法中使用的ENaNE也可以有效地刪除標(biāo)記錯(cuò)誤的實(shí)例。因此該算法具有明顯的優(yōu)勢(shì)。

盡管所提出的算法在BRT和IMS數(shù)據(jù)集上的效果不佳，但是所有算法在具有不同L值的BRT和IMS數(shù)據(jù)集上都具有相似的結(jié)果。另外，當(dāng)將數(shù)據(jù)集ION上的L的百分比從20%增加到40%時(shí)，STDP_ENN、STDP_AKNN、STSFCM、STDP和STDPNF的準(zhǔn)確性會(huì)大大降低。這是因?yàn)镾TDPNF的ENaNE中的自訓(xùn)練方法錯(cuò)誤地預(yù)測(cè)了未標(biāo)記樣本的類(lèi)標(biāo)簽，這削弱了STDPNF的ENaNE的能力，另外STDP、STSFCM、STDP_ENN和STDP_ALLENN向L添加了錯(cuò)誤預(yù)測(cè)的未標(biāo)記樣本。

實(shí)驗(yàn)四：訓(xùn)練時(shí)間測(cè)試。很難分析自訓(xùn)練方法的時(shí)間復(fù)雜度。因此，本節(jié)將通過(guò)在9個(gè)數(shù)據(jù)集上比較表2中列出的所有自標(biāo)記算法中的中央處理器(CPU)運(yùn)行時(shí)間來(lái)說(shuō)明STDPNF的計(jì)算效率。在STDPNF中發(fā)現(xiàn)結(jié)構(gòu)的時(shí)間復(fù)雜度為O(n2)，在STDPNF中搜索NaNs的時(shí)間復(fù)雜度為O(nlogn)。STDPNF中ENaNE的運(yùn)行時(shí)間取決于ENaNE中自訓(xùn)練方法的運(yùn)行時(shí)間。

表7中給出了相應(yīng)的算法執(zhí)行時(shí)間對(duì)比結(jié)果。盡管STDPNF比STDP消耗更多的時(shí)間，但它并不是最耗時(shí)的算法。實(shí)際上，因?yàn)镸LSTE中的ENN和SETRED中的CEWS具有較高的時(shí)間復(fù)雜度(O(n3))，所以SETRED和MLSTE比STDPNF消耗更多的時(shí)間。此外，在某些數(shù)據(jù)集，例如UKM、SPH和LIV上，STSFCM還比STDPNF消耗更多的時(shí)間，因?yàn)镾FCM需要在自訓(xùn)練過(guò)程的每次迭代中運(yùn)行。權(quán)衡STDPNF的優(yōu)缺點(diǎn)，STDPNF的計(jì)算效率是可以接受的。

表7 不同算法訓(xùn)練時(shí)間對(duì)比結(jié)果 單位:s

4 結(jié) 語(yǔ)

針對(duì)自訓(xùn)練方法中局部噪聲濾波器存在的參數(shù)依賴(lài)性以及僅使用標(biāo)記數(shù)據(jù)來(lái)刪除標(biāo)記錯(cuò)誤樣本等局限性，提出了一種基于密度峰值和無(wú)參數(shù)局部噪聲濾波器自訓(xùn)練方法。通過(guò)四個(gè)對(duì)比試驗(yàn)可得出如下結(jié)論：

(1) 所提出算法在提高基分類(lèi)器KNN的分類(lèi)精度方面比現(xiàn)有工作更有效。

(2) 所提出算法中使用的局部噪聲濾波器克服了現(xiàn)有局部噪聲濾波器的技術(shù)缺陷。它能夠不依賴(lài)參數(shù)選取，更具有自適應(yīng)性。即使標(biāo)記數(shù)據(jù)不足，它也可以通過(guò)利用未標(biāo)記數(shù)據(jù)的附加信息來(lái)刪除標(biāo)記錯(cuò)誤的樣本，驗(yàn)證了該算法具有更好的泛化能力。

(3) 所提出算法的計(jì)算效率和執(zhí)行時(shí)間處在可接受的范圍內(nèi)。

下一步應(yīng)將所提出的算法應(yīng)用于多標(biāo)簽分類(lèi)任務(wù)。