一種基于預過濾和聚類處理的眾包標簽噪聲糾正方法

史 偉 李超群

(中國地質大學(武漢)數學與物理學院 湖北 武漢 430074)

0 引 言

為了獲得實例的集成標簽，最簡單的方法就是Ipeirotis等[2]提出的眾數投票法(Majority Voting，MV)，即將實例xi的多標簽集的多數類賦予該實例。但是MV比較粗糙，為了獲得更高質量的集成標簽，很多研究者致力于設計新的標簽真值推理算法。例如Raykar等[3]提出RY，Demartini等[4]提出ZC，Sheng[5]提出MV的兩種變形MV-Freq和MV-Beta，Tian等[6]提出的M3V，Zhang等[7]提出的DEWMV。

毫無疑問，無論使用哪一種真值推理算法，集成標簽中仍存在一定程度的噪聲。這里噪聲是指與專家標簽不同的集成標簽，集成標簽為噪聲的實例本文稱為噪聲實例。在監督學習中，訓練數據集的標簽質量對于模型的構建至關重要。因為錯誤標注的數據可能會降低目標分類器的性能，同時增加模型訓練的復雜度，所以噪聲處理是十分有必要的。在信號處理領域，噪聲處理是一個相對成熟的問題。雖然大多數工作可以直接用于集成標簽進行噪聲過濾或糾正，但這些工作不是針對眾包數據設計的，不能有效利用眾包系統所產生的信息?，F有文獻中，將眾包噪聲處理與機器學習結合的研究并不多。另外，雖然很多噪聲過濾方法可以有效地過濾集成標簽中的噪聲數據，但是簡單拋棄一部分實例無疑是一種數據浪費，而標簽糾正技術可以減少這一浪費?；谝陨蟽牲c，本文致力于眾包數據的標簽噪聲糾正技術，利用實例多標簽集中的信息，提出一個新的標簽噪聲糾正方法，稱為修改的基于聚類的噪聲糾正算法(MCNC)。多標簽集中的信息用于監督標簽噪聲糾正過程。在若干數據集上的實驗結果表明，對比其他標簽噪聲糾正方法，該方法可以更有效地提高數據質量和目標模型質量。

1 相關工作

面向眾包機器學習，研究者們展開了很多工作。其中主要的工作集中在真值推理算法的改進。還有的工作是將眾包學習和主動學習結合，這個方向的核心觀點是如何選擇最不確定的實例[8-9]進行標注；也有一部分工作是將眾包生成的多標簽集和專家標簽結合[10-12]，通過引入小部分專家標簽(黃金數據)來提升集成標簽的質量，本質上仍屬于標簽真值推理的范疇。盡管在提升集成標簽質量方面研究者們做了很大的努力，一個在若干個實際眾包數據集上的實證研究表明這些算法的表現沒有顯著差異[13]。為了進一步提升集成標簽的質量，進行標簽噪聲處理是十分有必要的。

一份關于標簽噪聲的綜述[14]回顧了標簽噪聲魯棒、標簽噪聲清理和標簽噪聲容忍模型。而標簽噪聲清理往往比建立噪聲容忍學習模型[15-17]更加有效。存在很多可行的噪聲清理方法，例如，基于度量和閾值的方法[18]通過一種特殊的度量評價了每一個實例，如果某個實例在某方面的度量超過預定閾值，則這個實例將被視為噪聲被去除。K近鄰(KNN)的方法使用了KNN分類器對標簽噪聲敏感的特點；基于KNN的方法移除被其他實例認為是噪聲的實例。基于模型影響和內省的方法[19-20]，通過分析錯誤標記實例對模型的影響來檢測錯誤標記實例。一種更通用的噪聲過濾的方法是基于模型預測的過濾，其通過訓練一個學習模型去分類實例并發現噪聲，例如，classification filtering(CF)、voting filtering(VF)和partition filtering(PF)[21]。實際上，很少有研究專門針對眾包領域的噪聲處理。Li等[22]驗證了通過噪聲過濾技術可以提高眾包數據的集成標簽質量和目標分類器的性能。

相比噪聲過濾，標簽噪聲糾正的算法要少一些。盡管噪聲過濾器是有效的處理噪聲的方法，但可能會過濾過多實例[14]，使得剩余的實例不足以訓練一個好的分類器，并且對于數據資源是一種極大的浪費。因此，本文致力于通過噪聲糾正技術提升眾包學習的性能。下面將回顧現有文獻中的噪聲糾正技術。

Nicholson等[23]提到了三種標簽噪聲糾正方法：Polishing Labels(PL)、Self-Training Correction(STC)和Cluster-based Correction(CC)。PL是由Teng[24]中Polishing方法改進而來，將其從關注屬性噪聲的糾正更改為關注標簽噪聲的糾正。該方法首先將數據集分成十個部分，然后用單一的分類算法在每一個部分上建立一個模型，用十個模型對數據集中每一個實例進行分類，得票多的標簽被賦予這個實例。STC靈感來源于Triguero等[25]的自訓練，具體而言，STC首先在數據集上使用一個噪聲過濾器生成一個干凈數據集和噪聲數據集，然后在干凈數據集上訓練一個模型用于計算噪聲數據集中每個實例是某個標簽的置信度，置信度最高的標簽被賦予這個實例，并將這個實例加入到干凈數據集中。重復這一過程，直到一定比例的噪聲實例被重新標記并加入干凈數據集。不同于上述兩種方法，CC是基于聚類的方法，該方法能形成獨立的簇標簽，無視數據集中的噪聲等級。CC的基本思想是在數據集上執行多次聚類算法，根據每個簇中實例標簽的分布和簇的大小，為每個簇中的所有實例賦予相同的權重，權重反映了實例屬于不同標簽的可能性。最終每個實例對從不同簇中得到的權重求和，并將對應最大權重的標簽賦予該實例。CC因為多次聚類的原因，有較高的時間復雜度，但作者的實驗結果表明，相比于PL和STC，CC的性能更好。

但上面提到的方法都不是為眾包學習特別設計的。據我們所知，只有兩個噪聲糾正方法是特別為眾包學習設計的。一個是自適應投票噪聲糾正方法(Adaptive Voting Noise Correction，AVNC)[26]。AVNC通過真值推理階段得到的信息監督噪聲識別過程，同時在眾包系統中使用工人的標注質量去估計數據集中噪聲的數量。不僅如此，AVNC還對噪聲實例進行排序，以此來決定哪些實例更應該被去除。然后AVNC利用集成學習模型來糾正噪聲實例的標簽。AVNC的優勢是使用了真值推理階段的信息(即工人的標注質量)來監督噪聲的識別和過濾。但是AVNC僅僅關注了數據質量而沒有關注模型質量。另一個是基于類別間隔的噪聲糾正方法(Between-class Margin-based Noise Correction，BMNC)[27]。文章認為如果用于構建過濾器的數據集本身是帶有噪聲的，那么過濾器將不可避免地被噪聲實例影響，導致產生的干凈數據集并不完全干凈。所以BMNC在進行噪聲過濾之前，利用真值推理階段的信息進行一次預過濾，去除一些潛在的噪聲實例；然后訓練一個分類器用于進一步分離出噪聲實例，這是第二步過濾。經過兩步過濾后得到一個干凈數據集和一個噪聲數據集，在干凈數據集上構建分類器，用于對噪聲數據集中的實例進行重新標注。

本文致力于結合眾包系統的信息和聚類算法，設計一個新的標簽噪聲糾正方法，本文算法同時關注標簽質量和模型質量。

2 算法設計

一般而言，一個標簽噪聲糾正方法包括兩個步驟：噪聲識別和噪聲糾正。噪聲識別最常見的一類方法是在數據集上建立分類器，利用分類器的預測標簽與實例本身的標簽進行對照，從而識別哪些實例是噪聲實例。在識別出噪聲標簽后，再進行校正。但由于數據標簽本身帶有噪聲，直接在這樣的數據上建立分類器進行噪聲識別，勢必會限制噪聲識別的性能，導致噪聲識別準確率不理想。面向眾包數據，BMNC算法[27]使用眾包數據的多標簽集信息對噪聲進行了一次預過濾，去除部分潛在噪聲是有效且必要的。

BMNC算法通過使用每個實例的多標簽集合中的信息來對數據集進行預過濾。通過讓不同的工人對同一個實例進行標注，每個實例xi會有一個多標簽集Ii。用Nl表示多標簽集Ii中標簽l的數量，pl表示標簽l出現的比例，則：

式中：L是數據集的標簽集合，包含了數據集中所有可能的標簽取值。

之后，在預過濾后的數據集上再過濾，用于進一步識別出噪聲。具體的做法是在預過濾的數據集上建立分類器，利用分類器對預過濾后的數據集進行分類，若一個實例所獲得的分類器的預測標簽不同于該實例的集成標簽，則該實例被判定為噪聲。經過兩步過濾后，已經識別出所有可能的噪聲實例。

對噪聲實例的糾正，比較普遍的做法之一也是在數據集上建立分類器，用分類器對噪聲實例進行預測，將預測的標簽賦予噪聲實例，達到對噪聲實例的標簽進行糾正的目的，比如STC方法。但本文擬采用聚類方法CC，在原始數據集上進行多次聚類，利用CC的思想對噪聲實例賦予新的標簽。之前的工作已經表明，相較于STC，CC的效果更好?？赡艿脑蛟谟冢?1) CC的方法是基于聚類的方法，因此方法的性能本身與數據的標簽質量無關；(2) CC的方法進行了多次聚類，形成了許多簇，因此是一個類似集成學習的思路。關于監督學習的研究已經表明，基于集成學習的分類器往往比單分類器要顯示出更好的分類性能。CC可以看成是基于聚類的集成學習，利用多次聚類的思路，既克服了單次k均值算法對k值大小敏感的問題，也在多次聚類中利用大小不同的簇對實例的可能類標賦予不同的權值，通過權值求和得到實例的最終標簽。

基于上述討論，本文在構建過濾器去識別噪聲之前，對數據集進行一個預過濾。通過預過濾，去除一些潛在的噪聲實例。之后，在預過濾后的數據集上訓練一個分類器，用于進一步識別出噪聲實例。經過兩步過濾后，已經識別出所有可能的噪聲實例。接下來是對噪聲實例的糾正，使用原始數據集中所有的實例進行多次聚類，利用聚類結果對前兩步識別出的噪聲實例進行重新標注。將本文算法稱為修改的基于聚類的噪聲糾正算法(MCNC)。

MCNC方法細節如算法1和算法2所示。算法1中，1-7行使用熵對數據集中的實例進行初步過濾。8-9行進行了第二次過濾。為了解決數據集中標簽不均衡問題，10-12行計算了數據集中指定標簽的分布，該信息被用于算法2中，計算每個實例的聚類標簽權重。13-21行給出了所有需要的聚類算法，這里使用k均值聚類，k取值從2到集合中實例數的一半不等。這個過程會產生大量不同大小的簇，用于增加聚類得到的簇的多樣性。在每次聚類結果中，按照簇的不同，依據簇中所有實例的標簽分布，計算該簇整體是各個類標的可能性，即算法2計算的權值。18行對簇中每個實例進行一個權值的累加，即每個實例是各標簽的可能性。22-25行使用聚類產生的標簽權重對噪聲實例進行重新標注。算法2對算法1中的18行的CalcWeights進行了詳細解釋，說明了如何根據數據集中標簽分布和具體簇中的標簽分布計算各標簽權重。第1行計算了具體簇中的標簽分布，第2行計算各標簽的預期分布，第3行是一個乘數，用于給較大的簇更大的重要級，但包含100個實例以上的簇獲得最大的重要級是2，是為了不讓非常大的簇淹沒較小的簇。4-6行計算了該簇是各個標簽的權重，簇中標簽的實際分布減去標簽的預期分布，并按照數據集中的標簽分布進行縮放，乘以乘數得到權重。

算法1MCNC流程

1.一個空的集合A；

2.fori=1 toNdo

3.計算多標簽集合Ii中每個標簽的比例pl；

6.endif

7.endfor

10.fori=1 toNdo

12.endfor

13.fori=1 toado

16.for聚類結果C中所有的簇cdo

17.forc中全部的實例xdo

18.InsWeightsx=InsWeightsx+

CalcWeights(cj,LabelTotals,L)；

19.endfor

20.endfor

21.endfor

22.forA+B中所有實例xdo

25.endfor

算法2CalcWeights

輸入：簇c，標簽分布向量v，標簽集合L。

輸出：權重向量w。

1.d=簇c中的標簽分布

2.u=1/|L|；

3.multiplier= min(log10(sizeof(c)),2)；

4.fori=1 to |L|do

6.endfor

7.returnw

3 實驗與結果分析

3.1 設置基準

依據數據質量和模型質量兩個指標，將MCNC與MV、PL、STC、CC、BMNC進行比較。其中，MV是指沒有應用噪聲糾正方法，僅使用多數投票算法來產生實例的集成標簽。MV的結果被作為基準與其余五種噪聲糾正算法進行比較。數據質量的定義為：數據集中集成標簽與真實標簽相同的實例比例。模型質量定義為：在糾正后的數據集上訓練目標分類器獲得的分類精度。這里使用C4.5作為目標分類器。

本文在人群環境及其知識分析平臺(CEKA)[28]上實現MCNC和BMNC，使用CEKA平臺現有的算法MV、PL、STC和CC的代碼；使用懷卡托知識分析平臺(WEKA)[29]的C4.5(J48)代碼。實驗中的五種噪聲糾正方法的設置如下：

(1) PL：C4.5作為PL分類器。

(2) STC：用分類過濾器(CF)作為STC的過濾器，糾正的噪聲實例比例設置為0.8，C4.5作為STC分類器。

(3) CC：聚類次數a=10，采用k均值聚類，k值從2到實例數的一半不等。

(4) BMNC：CF為過濾器，閾值δ=0.95，C4.5為BMNC的分類器。

(5) MCNC：CF為過濾器，閾值δ=0.95，聚類次數a=10，采用k均值聚類為CC的聚類方法，k值從2到實例數的一半不等。

另外，當CF作為STC、BMNC和MCNC的噪聲過濾器時，需要設置一個參數n(n是對訓練數據進行分區的數量)和用于過濾的分類器。在本文實驗中，n=10，分類器同樣是C4.5。

3.2 模擬數據集和實驗設置

在22個數據集上進行實驗，表1展示了22個數據集的詳細信息。為了模擬每個實例獲得多標簽集合的過程，隱藏了每個實例原本的真實標簽，并使用9個模擬工人對每個實例進行標注。每個標注者的標注質量是pj∈[0,1](j=1,2,…,9)，即對于每個工人來說，有pj的概率給實例標注原本的真實標簽，有1-pj的概率標注其他可能的標簽。為了確定實驗結果對于不同標注質量的穩定性，本文實驗設置了兩種不同的標注質量：

(1) 在第一系列實驗中，設置所有工人的標注質量為0.6。即pj=0.6(j=1,2,…,9)。

(2) 在第二系列實驗中，每個工人的標注質量均勻分布在[0.55,0.75]上，即pj∈[0.55,0.75](j=1,2,…,9)。

表1 數據集信息

續表1

在每個實例獲得9個工人標注的標簽后，使用真值推理算法MV推理集成標簽，然后應用五種噪聲糾正算法識別并糾正集成標簽中的噪聲。在糾正后的數據集上計算數據質量，并在糾正后的數據集上訓練目標分類器獲得模型質量。所有實驗結果都采用十折交叉驗證得到，測試集不參與數據質量的計算。

3.3 實驗結果

表2和表3給出了第一系列實驗的結果，該實驗中所有工人的標注質量都是相同的。表2展示了原始集成標簽的標簽質量和每個數據集分別應用五種噪聲糾正算法后的標簽質量。表3展示了應用不同糾正算法后的模型質量。

表2 第一系列實驗的標簽質量結果(%)

表3 第一系列實驗的模型質量結果(%)

從表2中可以看出，所有的噪聲糾正方法都可以在大部分數據集上提升標簽質量。MCNC在13個數據集上的效果最好，即在13個數據集上提升標簽質量最多(例如：iris、labor和segment等)。其次是BMNC，在6個數據集上提升標簽質量最多。后面分別是PL和CC，分別在2個和1個數據集上取得最好的效果。而STC沒有在任何一個數據集上取得最好的效果。從表3可以看出，在一些情況下，提升標簽質量可以提高目標分類器的性能。MCNC在9個數據集上性能最優，其次是STC和CC的4個，PL在3個數據集表現最好，BMNC只有2個。

表4和表5給出了第二系列實驗的結果，該實驗中所有工人的標注質量均勻分布在[0.55，0.75]之間。表4展示了原始集成標簽的標簽質量和每個數據集分別應用五種噪聲糾正算法后的標簽質量。表5展示了應用不同糾正算法后的模型質量。

表4 第二系列實驗的數據質量結果(%)

表5 第二系列實驗的模型質量結果(%)

續表5

從表4可以看出，MCNC的性能依然是最優的，在14個數據集上取得最好效果，BMNC和PL在3個數據集上性能最優，CC只有2個，STC依舊沒有突出性能的數據集。表5顯示，MCNC在7個數據集上性能最優，PL有5個，CC和BMNC都有4個，STC僅有3個。

結合兩個系列的實驗結果，在大部分數據集上，改善眾包數據的標簽質量，可以在一定程度上提升相應的目標模型質量。但不同位置的實例對于模型建立的貢獻度是不同的，直觀而言，分類決策面的邊界數據點的貢獻度要高于類內部的數據點，所以數據標簽質量的提升并不必然導致目標模型質量的提升。

通過上面兩個系列的實驗，相比較PL、STC、CC和BMNC，本文方法MCNC更能有效地提升眾包數據的標簽質量和目標模型質量。

4 結 語

本文提出一種新的針對眾包學習的標簽噪聲糾正方法MCNC。本文方法使用了真值推理階段的信息來監督噪聲的識別，使用了無視原本噪聲等級的基于聚類的算法進行噪聲糾正。相對于被比較的各種方法，MCNC能夠有效地提升標簽質量和模型質量。

后續工作將針對提升數據標簽質量并非一定提升目標模型質量的現象，研究分類決策面的邊界數據點的標簽噪聲糾正。期望可以通過提升分類決策面的邊界數據點標簽質量，使得目標模型質量獲得較大提升。然而哪些實例更有可能是分類決策面的邊界點數據，對模型建立有更高的貢獻度，是需要仔細考慮的問題。同時，基于聚類的集成方法對計算資源消耗較大，運行時間較長，后續會對該方法進一步優化，以減少運行時間。