基于局部概率抽樣的標簽噪聲過濾方法

張增輝，姜高霞，王文劍，2*

（1.山西大學計算機與信息技術學院，太原 030006；2.計算智能與中文信息處理教育部重點實驗室（山西大學），太原 030006）

0 引言

在現實生活中，由于數據來源廣泛且復雜、人類認知的有限性，以及硬件故障、輸入錯誤、編程錯誤等意外原因，都會導致數據中包含一定比例的噪聲。對于分類任務，一般噪聲可以分為兩類：特征噪聲和標簽噪聲，前者指的是錯誤數據僅出現在屬性部分，標簽噪聲則指只有標簽部分數據產生損壞。噪聲的存在對建模產生許多影響，而標簽噪聲通常情況下比特征噪聲具有更大的破壞力［1］，它會導致模型復雜度增加，分類精度下降且更容易造成過擬合［2］。標簽噪聲雖然可以采用人工方式去除，但是，如果為保證標簽質量由專家進行標記，則人工代價大、成本高，利用眾包平臺雖然可以解決成本問題，但又無法保證標記數據質量。因此，標簽噪聲的過濾成為近些年來學者們關注的機器學習問題之一。

現有解決標簽噪聲過濾問題的方法主要有兩類：建立對標簽噪聲魯棒的模型和基于模型預測的標簽噪聲過濾器。建立對標簽噪聲魯棒的模型主要通過直接對標簽噪聲建模，或者采用嵌入式的方式在已有的算法中考慮標簽噪聲［3］。但是，用這樣的方式構建的魯棒性模型并不可靠，因為建模時無法判斷所使用的數據是否含標簽噪聲，所以模型的性能并不能得到保障。因此，使用基于模型預測的標簽噪聲過濾器對樣本進行預處理的方式更為常見。

標簽噪聲過濾器主要利用模型預測的方式識別帶有標簽噪聲的樣本，然后將錯誤標簽移除或修正［4］，以達到提高訓練樣本質量的目的。從模型上來看，k最近鄰（kNearest Neighbour，kNN）模型對標簽噪聲非常敏感，尤其當k值較小時，因此，有學者相繼提出一些基于kNN 模型的數據清洗方法，如基于kNN的樣本選擇方法主要基于啟發式算法，壓縮最近鄰（Compressed Nearest Neighbor，CNN）方法［5］建立了一個能夠正確分類所有其他訓練樣本的子集，但是這樣的方法會將標簽錯誤的樣本保留在訓練集中。縮減最近鄰（Reducing Nearest Neighbor，RNN）方法［6］則是依次刪除那些被刪除后不會導致其他樣本分類錯誤的樣本。基于圖論又出現了一些kNN 算法的變體，不同之處在于利用鄰域圖來表示訓練集中樣本點之間的關系［7-8］。此外，由于Adaboost 在后期迭代過程中，錯誤標記樣本的權重會比正常樣本的權重大得多，因此，當存在噪聲樣本時，Adaboost 常常陷入過擬合，有些算法利用了這一特點，通過刪除權重過高樣本或調整異常樣本的權重來降低標簽噪聲的影響［9-10］。從模型結構來看，常見的過濾手段主要有基于集成的過濾方法［11-12］和基于迭代的過濾方法［13-14］，集成過濾方法利用現有模型做橫向的擴展，將多個同質或異質的弱學習器集成為一個強學習器來提高模型的學習能力，代表算法有MF（Majority vote Filter）［15］、CF（Consensus voting Filter）［16］和HARF（High Agreement Random Forest filter）［1］。而迭代則是將模型做縱向的延伸，利用上一個學習器學習的結果作為下一次訓練的輸入樣本，代表算法有IPF（Iterative Partition Filter）［15］和INFFC（Iterative Noise Filter based on Fusion of Classifier）［16］。上述方法均是從模型預測的角度出發，設法提高預測模型的準確性。從過濾機制來看，使用的均為單一閾值控制的0-1 抽樣方式，這種方式不能很準確地區分樣本之間的清潔度，因而導致其分類效果低下。因此，近年來有學者提出一些基于樣本概率采樣方式來增加過濾標簽噪聲的算法，如PSAM（Probabilistic SAMpling）［17-18］利用多重投票機制和概率抽樣方式來提高過濾器的魯棒性。然而概率的估計是基于極大似然估計，利用多重投票會導致其時間復雜度大大增加，且閾值在全區間內隨機取值極易產生極端閾值，這些因素會大大影響過濾器的噪聲識別性能。

本文提出一種基于局部概率抽樣（Local Probability Sampling，LPS）的標簽噪聲過濾算法，利用隨機森林（Random Forest，RF）對訓練樣本的標簽進行了合理的置信度估計，并依據其估計結果利用局部概率抽樣的過濾機制分塊考慮不同置信度樣本進行過濾。與已有算法相比，本文算法不僅考慮了不同樣本之間清潔度的差異，而且可以避免現有的概率抽樣過濾機制中極端閾值情況的出現，從而可以提高過濾器的過濾性能。

1 LPS算法

本文提出的LPS 算法首先對訓練樣本集進行一次預過濾，大致將樣本根據標簽的清潔程度做一個簡單劃分；再通過識別出的干凈樣本訓練模型對全體樣本進行預測并計算置信度；最后通過局部概率抽樣的方式進行噪聲過濾。

1.1 預過濾

對于待過濾訓練樣本集DT，其中可能包含一定比例的標簽噪聲，由于過濾模型是基于這些帶噪聲的樣本建立的，因此這些噪聲會對過濾過程造成一定程度的影響。所以，在建立過濾模型前，首先對訓練樣本DT進行一次預過濾，剔除一部分噪聲樣本，以減少噪聲對過濾器識別能力的影響。

預過濾采用異質集成分類過濾器，結合n折交叉驗證的思想進行過濾。首先將DT隨機均勻劃分為n份，即DT=DT1∪DT2∪…∪DTn，且DTi∩DTj=?(i，j=1，2，…，n，i≠j)，利用m個異質分類算法在任意n-1份樣本上訓練m個分類器，再通過訓練出的m個分類器對剩余一份樣本進行分類。關于投票策略問題，常采用多數投票策略和共識投票策略。由于預過濾的目的僅僅是為了過濾少量比較確定的噪聲樣本，并不要求所有樣本的精確過濾，故使用共識投票策略過濾噪聲樣本，即只過濾被m個分類器都分類錯誤的樣本，以避免過多樣本被過濾的風險。預過濾后，原始訓練樣本DT被劃分為初始干凈樣本集DTC和潛在噪聲樣本集DTN。

1.2 局部概率抽樣

本文所提出LPS 算法，利用了隨機森林對DT中所有樣本的標簽進行評價后獲得各個樣本的標簽置信度，標簽置信度較高或較低的樣本被保留或刪除，其余樣本則基于標簽置信度的大小進行抽樣，置信度越高，被抽樣的概率越高，被保留為干凈樣本的可能性就越大。

1.2.1 基于隨機森林的樣本置信度估計

對于DT中所有的樣本都有一個標簽置信度估計，每一個樣本的標簽置信度取決于評估模型對于該樣本的評估結果。如果樣本當前的標簽置信度較高，則該樣本會有更高的概率被選中并保留為干凈樣本。因此，估計樣本標簽的置信度是本算法的一個重要組成部分。置信度估計應當準確，使得干凈樣本有較高的置信度，噪聲樣本的置信度應當較低。

在LPS中使用隨機森林對樣本建立置信度估計。原始訓練樣本集為DT，樣本量為N，包括C類，因此，有DT=，i=1，2，…，N，yi=1，2，…，C。首先，預測模型是基于預過濾中劃分出的初始干凈樣本集DTC建立的，由于在預過濾中已經過濾了少量比較確定的噪聲，所以基于DTC建立的模型相對更加準確。隨機森林的隨機性體現在：

1）在訓練某一棵樹時，利用bootstrap 取樣從DTC（樣本總量為Nc）中抽取樣本（即有放回地隨機抽取Nc個樣本）進行訓練；

2）隨機抽取所有訓練樣本的部分特征進行訓練。

使用隨機森林估計置信度時，每棵樹獨立預測各個樣本并貼標簽，最后，通過集成這些預測來估計置信度。在LPS中，標簽置信度與該標簽在多棵樹的預測中出現的頻率成正比。設樣本e(xi，yi)∈DT，構建的隨機森林中有nTree棵樹，conf（e）為樣本e的置信度，則：

其中：Tj(e)為第j棵樹對樣本e的預測標簽；I為指示函數，表達式成立時結果為1，不成立時結果為0。例如，100棵樹對樣本（x1，y1）預測，結果中67棵樹預測結果為“y1”，33棵樹預測結果為“y2”，則該樣本的標簽置信度為0.67。

使用隨機森林構建預測模型的優勢在于，首先，隨機森林的基模型相互獨立，因此它的模型預測比基模型非獨立的情況下更加準確，且該基模型屬于弱學習器，不易造成過擬合且訓練速度較快；其次，參數nTree越大，標簽置信度差異就越細化，因此nTree可以調節清潔度差異的細化程度，使用一個具有nTree棵樹的隨機森林估計置信度時，每個樣本會有nTree+1 種置信度等級，集成樹的數量越多，樣本間的清潔度差異就越細化；最后，對于這樣基于極大似然估計的估計方法，實驗次數越多，置信度估計越精確，所以，當nTree較大時，隨機森林估計出的樣本標簽置信度會更加準確。

1.2.2 基于置信度的局部概率抽樣

設立閾值區間［l，h］，閾值r為區間內隨機值，當樣本置信度confi高于隨機閾值r時該樣本被保留；否則將其過濾，DPC為過濾后干凈樣本集，DPN為過濾后噪聲樣本集，則對于DT內所有樣本：

圖1 樣本被保留概率P與conf之間的關系Fig.1 Relationship between sample retention probability P and conf

全局概率抽樣無法控制過濾樣本數量，需要設置抽樣比例人為控制，此時樣本被保留概率不完全取決于置信度而是與樣本所在位置也有一定的關系，索引較大的樣本被抽樣的概率更小；而LPS由于只對局部樣本采用抽樣方式過濾，因此無須控制抽樣比例，樣本被抽樣概率僅與置信度confi有關。

由于閾值r是在閾值區間［l，h］內隨機生成的，因此，如果只進行一次抽樣具有一定的隨機性，無法很好地發揮概率抽樣方法的優勢，所以要進行多次抽樣，設抽樣次數SamplingNum，進行多次的獨立重復實驗，讓r在［l，h］區間均勻取值，最終匯總多次實驗結果。抽樣共進行SamplingNum次，基于第i次抽樣所得干凈樣本集訓練出分類器hi，將SamplingNum個基分類器集成，對測試集的標簽進行預測，最終獲得預測標簽集L。

1.3 LPS算法

本文提出的LPS算法的主要步驟總結如下：

輸入 初始樣本集DT。

參數DT劃分子集數n，預過濾集成分類算法個數m，隨機森林構建樹的個數nTree，抽樣次數SamplingNum，閾值區間下限l，閾值區間上限h。

輸出 預測標簽集L。

步驟1 使用k近鄰、樸素貝葉斯和隨機森林集成分類器對初始樣本集DT進行預過濾，投票采用一致投票方式，被識別為噪聲的樣本構成的集合為潛在噪聲樣本集DTN，剩余樣本構成的集合為DTC。

步驟2 基于DTC中的樣本構建包含nTree棵數的隨機森林，對DT中的全體樣本進行預測，并利用式（1）計算所有樣本的conf值。

步驟3 在［l，h］區間內隨機生成閾值r，保留conf值高于r的樣本構成干凈樣本集DPC，剩余樣本被標記為噪聲。基于DPC構建分類器hi。

步驟4 重復步驟2 和步驟3 共SamplingNum次，訓練SamplingNum個分類器對測試集進行預測得到預測標簽集L。

LPS算法的時間主要消耗在估計置信度的過程中，對于N個樣本，C個類別的訓練集，構建一棵樹的時間是O(N·C·log(N))，nTree棵樹做決策的時間為O(nTree·N·C· log(N))，抽樣共進行SamplingNum次，故LPS 的時間復雜度為：O(SamplingNum·nTree·N·C·log(N))。

考慮到構建隨機森林和抽樣過程均可以采用并行方式，因此LPS在并行情況下時間復雜度為：O(N·C· log(N))。

2 實驗與結果分析

2.1 實驗數據及評價指標

本文在14 個經典UCI 數據集上驗證本文提出算法的有效性，數據集描述如表1。為避免不平衡數據對分類性能的影響，對wine 抽取了其中的第5 和第6 類，對segment、australian和spf抽取了其中的第1類和第2類。

在實驗前，將每個數據集劃分為訓練集和測試集兩個部分，其中訓練集占數據集樣本總量的2/3，剩余1/3樣本作為測試集，隨機改變訓練集中一定比例的標簽以模擬噪聲。為了降低實驗結果的隨機性，每個數據集在每個噪聲比例下重復進行10次實驗，并將10次結果求取均值。

本實驗中使用了多種度量指標對上述幾種過濾算法的噪聲識別能力和分類泛化能力進行衡量，分別是Classif（分類準確率）、Acc（識別準確率）、NoiFiltAcc（過濾噪聲準確率）、Re（召回率）、Spec（特異度）、Pre（查準率）和F1分數，定義如下：

表1 數據集描述Tab.1 Dataset description

其中：TP（True Positive）、FP（False Positive）、FN（False Negative）、TN（True Negative）的定義如表2所示。

實驗中將LPS 同一些具有代表性的算法進行比較，其中包括隨機森林（RF）、多數投票過濾器（MF）、高一致度隨機森林（HARF）、全局概率抽樣（PSAM）。HARF 閾值設置為0.7；LPS 和PSAM 中抽樣次數為11 次。此外，RF、MF、PSAM 和LPS 的預過濾將樣本劃分為5 個子集，MF、PSAM 和LPS 預過濾中集成了3 種學習算法(m=3)：3NN、樸素貝葉斯、隨機森林，HARF 和LPS 均構建了500 棵樹。在標簽噪聲過濾后，均采用隨機森林作為基本分類器輸出分類精度。

表2 混淆矩陣Tab.2 Confusion matrix

2.2 實驗結果與分析

2.2.1 閾值的確定

本節中的實驗主要探究閾值r對算法識別性能的影響。令r在［0，1］區間內隨機生成，每個數據集在同一噪聲比例下實驗100 次，使r在［0，1］區間隨機均勻取值。圖2 為在部分數據集上實驗得到的不同噪聲比例（ratio）下Acc隨r的變化趨勢。從圖中可以看出，在大部分數據集下，當r值小于0.2時，由于閾值過低，刪除的樣本較少，大部分噪聲仍然保留在數據集中，因此識別準確率基本維持不變；當r值增長到0.4時，過濾器的識別能力開始顯現，Acc逐漸上升；當r值處在［0.5，0.7］時，過濾器的識別能力處于較高水平，直到r值大于0.7后，由于過量正確樣本被刪除，此時過濾器識別能力開始下降。因此，本文在后續實驗中，將使用l=0.5，h=0.7 作為LPS的默認參數。

圖2 閾值r對Acc的影響Fig.2 Effect of threshold r on Acc

在LPS 算法中，抽樣概率的大小是由樣本的標簽置信度決定的，為了保證LPS算法的有效性，要求置信度的估計必須合理且有效，干凈樣本應當比噪聲樣本有更高的置信度。表3展示了各個數據集在不同噪聲比例下干凈樣本置信度均值RCC（Clean Confidence，CC）、噪聲樣本置信度均值RNC（Noise Confidence，NC）和分離度RSC（Separation of Confidence，SC）的實驗結果，其中：噪聲比例設置從10%到40%，以10%為間隔；RSC=RCC-RNC。可以看出在所有噪聲比例下，所有數據集中的RCC均大于RNC，且隨著噪聲比例的增加，RCC與RNC的差距逐漸減小，驗證了前文中“樣本置信度與被保留概率成正比”的合理性。除此之外，大部分RSC都表示出了隨噪聲比例增加而減小的變化趨勢，換句話說，在噪聲比例較高的情況下，干凈樣本的置信度和噪聲樣本的置信度更接近，這時通過置信度識別噪聲變得更難，這一結果符合對置信度估計的預期。

表3 各個數據集上在不同噪聲比例下RCC、RNC、RSC的實驗結果Tab.3 Experimental results of RCC，RNC and RSC under different noise ratios on different datasets

2.2.2 噪聲識別性能

本節對比了LPS 較RF、MF、HARF、PSAM 的噪聲識別能力，噪聲比例由5%到40%，每次遞增5%。圖3 包含了5 種算法在Acc、NoiFiltAcc、Re、Spec、Pre和F1分數下的實驗比較結果，該實驗結果取自5 種算法在14 個數據集下實驗結果的平均值。

圖3 5種算法的性能指標比較Fig.3 Performance indicators comparison of five algorithms

從圖3 中可以看出，隨著噪聲比例的增加，除NoiFiltAcc外，其余5 個指標基本呈下降趨勢。其中PSAM 的Pre較高而Re和NoiFiltAcc較低，說明PSAM 存在一定的過度過濾的問題，即過多正確樣本被過濾，然而從Spec來看，PSAM 在過度過濾的同時，仍然將35%左右的噪聲樣本保留，因此，PSAM的噪聲識別能力一般。RF 算法使用了單一的隨機森林分類器，Acc、NoiFiltAcc和F1值都比較低。MF 和HARF 兩種算法的側重點不同，HARF 更傾向將干凈樣本盡可能多地召回，故而它的Re和NoiFiltAcc值表現更好，而MF 更傾向盡可能將噪聲樣本過濾，故而它的Spec和Pre的值相對表現更好。從HARF 和MF 最終實驗結果來看，就識別準確率和F1值來看，HARF更好一些。LPS同上述幾種算法相比，雖然Re同HARF相差不大，且Pre同MF 相差不大，但是綜合來看，LPS 的F1和Acc明顯更有優勢。且從Acc表現來看，當噪聲比例大于10%時，LPS 的噪聲識別能力也明顯優于其他算法。另外LPS 的Spec略低于MF，意味著會有少量的噪聲被保留在干凈樣本集中，但是由于同時有更多的干凈樣本被保留，所以少量保留的噪聲并不會對LPS 的泛化能力產生太大的影響。圖4 對比了在不同噪聲比例下，5種算法在14個數據集中Acc、NoiFiltAcc、Re、Spec、Pre和F1指標最優情況占所有數據集的比例，LPS 在Acc、F1值下，比較其他算法有明顯的優勢，MF 的Re指標在大多數情況下比別的算法更好，而HARF的Pre值在數據集中表現最優的占比比其他算法更高。當噪聲比例較低時，HARF的NoiFiltAcc值相較其他算法來說更具優勢，而隨著噪聲比例的增大，LPS 的NoiFiltAcc逐漸超越HARF，成為NoiFiltAcc值最優的算法。

圖4 所有數據集中各算法識別性能指標最優占比Fig.4 Optimal proportion of each algorithm index in all datasets

2.2.3 分類性能比較

圖5 對比了14 個數據集在5 種算法下的分類泛化性能，其中None 表示不使用任何過濾算法，直接分類的結果，噪聲比例從5%到40%，每次遞增5%，Classif值越高，表示數據集經由該算法過濾后，在測試集上的分類性能表現越好。對于不同數據集，各個過濾方法的分類泛化性能差異較大，但對于所有數據集，分類結果隨著噪聲比例的增長局部有小范圍的波動，但整體基本呈現下降趨勢。其中，除german、haberman兩個數據集外，在其余12個數據集下，LPS都展示出了較高的分類準確率。而None 和PSAM 情況下，分類性能最差。圖6展示了5 種算法的分類性能的臨界差異（Critical Difference，CD）。由圖6可知，在顯著性水平α=0.05時，此時臨界距離為2.156 7，也就是說，當算法之間的距離大于2.156 7 時，它們的分類性能展現出明顯差異。從圖6 中可以看出，就分類能力來看，LPS＞MF＞HARF＞RF＞PSAM，其中LPS 相較于HARF、RF、和PSAM表現出顯著差異。

圖5 各個數據集上5種算法的Classif比較Fig.5 Comparison of Classif of five algorithms on different datasets

圖6 5種算法的分類性能排序Fig.6 Classification performance ranking of five algorithms

2.2.4 運行時間比較

圖7展示了5種算法在部分數據集上的時間效率比較，由于各種算法在小型數據集上的運行時間差異不明顯，因此，本節選取了幾個較大規模數據集進行實驗，其中wine 和german數據集樣本數較大，qadc 類別數較大。由圖7 可以看出，PSAM 的運行時間遠大于其他算法，其次是MF，RF、HARF、LPS的時間效率較高。此外，從qadc的實驗結果來看，類別數的陡增也會大大影響HARF的時間效率。

圖7 5種算法的運行時間比較Fig.7 Comparison of running time of five algorithms

3 結語

本文提出的LPS 標簽噪聲過濾算法，利用分類器對樣本標簽進行置信評價獲得標簽置信度，再利用置信度同隨機閾值之間的關系對樣本進行過濾。與現有的算法相比，能夠更大程度上考量樣本之間的清潔度差異，且避免了傳統概率抽樣算法中極端情況的出現，使得過濾器具有更好的穩定性。對于如何更合理地劃分易識別樣本和難識別樣本，即閾值區間如何設置能夠更大程度上提高標簽噪聲的識別能力，還有待于進一步探索。此外，該算法在低噪聲環境下的噪聲識別能力，也有待于進一步提高。