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

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

（?通信作者電子郵箱wjwang@sxu.edu.cn）

0 引言

噪聲可以被定義為由與產(chǎn)生數(shù)據(jù)分布無關(guān)的外生因素引起的對數(shù)據(jù)項收集的信息的部分或全部改變［1］。對于分類任務(wù)，一般噪聲按照其出現(xiàn)的位置可以劃分為兩類：特征噪聲和標(biāo)簽噪聲［2］。噪聲的存在對建模產(chǎn)生許多影響，其中特征噪聲的分量在統(tǒng)計上彼此更加獨立，并且大多數(shù)的分類器在面對特征噪聲時更加魯棒［3］，而有研究表明，由標(biāo)簽噪聲引入的偏差更大，因此通常情況下它比特征噪聲具有更大的破壞力［4］，會導(dǎo)致模型復(fù)雜度增加，分類精度下降，并且更容易出現(xiàn)過擬合現(xiàn)象［5］。然而，無論是特征中出現(xiàn)噪聲還是標(biāo)簽中出現(xiàn)噪聲，機器學(xué)習(xí)算法都會將其看做標(biāo)簽噪聲［6］。因此，標(biāo)簽噪聲的處理成為近些年來亟待解決的機器學(xué)習(xí)問題之一。

現(xiàn)有的處理標(biāo)簽噪聲的方法可以劃分為三大類：修改現(xiàn)有模型使其對標(biāo)簽噪聲具有魯棒性，構(gòu)建基于模型預(yù)測的標(biāo)簽噪聲過濾器，以及標(biāo)簽噪聲校正方法。雖然對算法本身進(jìn)行魯棒性改進(jìn)可以使學(xué)習(xí)器直接處理帶有標(biāo)簽噪聲的數(shù)據(jù)，但這樣的方式不適用于所有學(xué)習(xí)方法，因此，使用基于模型預(yù)測的標(biāo)簽噪聲過濾器對樣本進(jìn)行預(yù)處理的方式更為常見。過濾器是通過模型預(yù)測的方式識別樣本集中的潛在噪聲并將其移除的方式來提高樣本質(zhì)量。

從模型的角度來看，標(biāo)簽噪聲過濾方法主要通過基于集成的方法、基于迭代的方法和基于分區(qū)的方法來實現(xiàn)。其中多分類器的集成使用最廣泛，集成分類器方法分為同質(zhì)集成和異質(zhì)集成。MVF（Majority Vote Filter）［7］和CVF（Consensus Voting Filter）［8］均屬于異質(zhì)集成分類器；HARF（High Agreement Random Forest Filter）［9］則由多棵C4.5 決策樹集成而得，是同質(zhì)集成分類器的典型代表。迭代方法是將上一次分類結(jié)果作為下一階段訓(xùn)練的輸入，直至達(dá)到事先規(guī)定的迭代跳出條件為止，代表算法有IPF（Iterative Partition Filter）［10］和 INFFC（Iterative Noise Filter based on Fusion of Classifiers）［11］。分區(qū)的思想主要是針對大型數(shù)據(jù)集或分布式數(shù)據(jù)集，將訓(xùn)練集劃分為多個子模塊分別訓(xùn)練，再將訓(xùn)練結(jié)果匯總投票［12］。若將過濾過程抽象為一個抽樣過程，標(biāo)簽噪聲過濾器方法可以分為0-1 抽樣方法和概率抽樣方法?，F(xiàn)有的經(jīng)典過濾算法CVF、MVF 和HARF 等均屬于0-1 抽樣，即給定確定閾值，依據(jù)閾值和集成算法的投票結(jié)果的大小關(guān)系過濾潛在的噪聲樣本。這種傳統(tǒng)的0-1 抽樣方式無法精確表達(dá)不同樣本之間的差異性，因此，近年來有學(xué)者創(chuàng)造性地提出了概率抽樣的思想，即為每一個樣本提供一個概率，這個概率指的是該樣本為干凈樣本的可能性大小，將這個概率作為依據(jù)，抽樣得到干凈樣本集，代表算法有PSAM（Probabilistic Sampling）［13-14］和局部概率抽樣（Local Probability Sampling，LPS）［15］，利用多分類器集成投票獲取樣本置信度，全區(qū)間隨機生成閾值進(jìn)行抽樣。概率抽樣的思想能夠有效利用置信度區(qū)分同一數(shù)據(jù)集內(nèi)部樣本與樣本之間的差異性，但是仍然無法避免人為設(shè)置閾值區(qū)間的主觀性，且現(xiàn)有的概率抽樣方法對不同數(shù)據(jù)集采用相同的過濾策略，忽視了數(shù)據(jù)集之間的差異性，影響了過濾器在不同數(shù)據(jù)集上的噪聲識別性能。

本文了提出一種動態(tài)概率抽樣（Dynamic Probability Sampling，DPS）的標(biāo)簽噪聲過濾算法。在本文算法中，通過統(tǒng)計樣本的標(biāo)簽置信度在區(qū)間內(nèi)的分布頻率，分析置信度分布頻率的信息熵走勢變化來決定進(jìn)行概率抽樣的樣本范圍。由于不同數(shù)據(jù)集之間置信度分布差異巨大，置信度分布頻率的信息熵走勢差異明顯，因此本文算法能夠敏銳探測不同數(shù)據(jù)集之間樣本差異性，合理規(guī)劃閾值區(qū)間，以達(dá)到較強的標(biāo)簽噪聲識別能力。

1 DPS算法

1.1 置信度分布分析

對于一個可能存在標(biāo)簽噪聲的樣本集DT，為了獲取每個樣本的可信程度，有效區(qū)分樣本之間的差異性，應(yīng)對其每個樣本合理估計其標(biāo)簽置信度。隨機森林（Random Forest，RF）模型集成了多棵決策樹，其隨機過程有效地解決了決策樹容易產(chǎn)生的過擬合問題，并且置信度的精度可以通過集成決策樹的數(shù)量靈活調(diào)整，模型中集成的決策樹越多，最終估計出的標(biāo)簽置信度精度越高。因此本文推薦使用隨機森林模型對樣本進(jìn)行置信度估計。計算方法為：

其中：confi表示樣本集DT中某一樣本的標(biāo)簽置信度，nTree為模型中集成的決策樹個數(shù)；表示模型對訓(xùn)練集樣本的預(yù)測標(biāo)簽向量，表示向量的第i個元素。

從預(yù)測準(zhǔn)確性來看，隨機森林由多個彼此獨立的決策樹集成，因此，它的預(yù)測結(jié)果比基模型非獨立的集成模型更準(zhǔn)確；其次，隨機森林中的隨機過程可以有效解決單一決策樹中的過擬合問題；除此之外，在評估置信度的過程中，nTree越大，標(biāo)簽置信度的差異就越細(xì)化，因此nTree可以調(diào)節(jié)清潔度差異的細(xì)化程度；最后，對于這樣基于最大似然估計的方法，實驗次數(shù)越多，置信度估計就越準(zhǔn)確。

標(biāo)簽置信度雖然能夠合理展現(xiàn)出樣本標(biāo)簽的可信賴程度，但是由于數(shù)據(jù)集之間的差異性，使得數(shù)據(jù)集的標(biāo)簽置信度分布也具有很大的差異。圖1 和圖2 分別展示了在理想情況下置信度分布和實際情況下各個數(shù)據(jù)集的置信度實際分布（各個數(shù)據(jù)集的詳細(xì)描述見3.1 節(jié)）。在理想條件下，使用集成分類模型計算樣本的標(biāo)簽置信度時，每一個基分類器都能夠準(zhǔn)確預(yù)測樣本的真實標(biāo)簽，因此，干凈樣本的標(biāo)簽置信度均為1，噪聲樣本的標(biāo)簽置信度均為0。然而由于在計算標(biāo)簽置信度時分類器本身存在一定的誤差，且不同的樣本分布情況也影響著分類器的預(yù)測結(jié)果，因此，實際各個數(shù)據(jù)集的標(biāo)簽置信度往往與理想情況相差甚遠(yuǎn)。

圖1 理想情況下的置信度分布Fig.1 Confidence distribution in ideal condition

圖2 不同數(shù)據(jù)集置信度分布Fig.2 Confidence distribution of different datasets

顯然，在置信度分布差異巨大的情況下，針對各種置信度分布的數(shù)據(jù)集采用一致的標(biāo)簽噪聲過濾策略是不可行的，因此，本文提出的DPS 算法使用信息熵對樣本的標(biāo)簽置信度分布情況進(jìn)行分析。

信息熵被定義為離散隨機事件的出現(xiàn)頻率，是數(shù)學(xué)上一個用于衡量信源的不確定度的抽象概念，信息熵越小，表示信源不確定性越低。在本文的問題中，將樣本的標(biāo)簽置信度的值看作隨機變量X，X的取值范圍為［0，1］。將［0，1］平均劃分為b份，有b+1，那么P(x∈(xi，1])為b個隨機事件發(fā)生的概率，統(tǒng)計b個隨機事件出現(xiàn)的頻率并計算信息熵，公式為：

隨機變量X的信息熵EQ（X）是一個單調(diào)遞減函數(shù)，隨著i的增加，區(qū)間（xi，1］逐漸減小，此時EQ（X）減小，意味著X事件的確定性逐漸增大，因此，尋找EQ（X）一階差分最小值點e，在e點處EQ（X）下降速度最快，此時將e更新為閾值選擇區(qū)間的右端點。EQ（X）在e點處下降速度最快意味著不確定性流失最快。

然而，此時的e點并不是最終要尋找的最佳臨界點，最佳臨界點應(yīng)該選取信息熵開始大幅下降的瞬間，也就是信息熵EQ（X）的拐點處，因此，最佳臨界點應(yīng)該滿足兩個條件：1）在信息熵EQ（X）產(chǎn)生大幅下降的點（即一階差分最小值點）之前；2）處在EQ（X）的某一拐點處。此時從e點出發(fā)向前搜索，繼續(xù)尋找EQ（X）二階差分最小值，就能夠找到最佳臨界點。事先尋找EQ（X）下降最快的點而不直接尋找拐點的原因是，無法確定拐點只有一個，部分?jǐn)?shù)據(jù)集的信息熵EQ（X）可能存在兩個或多個拐點，先利用一階差分更新點e能夠縮小拐點尋找范圍，避免最佳臨界點的尋找陷入局部最優(yōu)。

尋找到最佳臨界點e后，令e的橫坐標(biāo)xe作為閾值區(qū)間的右端點，xe-w為左端點，w為進(jìn)行概率抽樣的范圍，此時就得到了最優(yōu)閾值區(qū)間[xe，xe-w]，利用局部概率抽樣的方式，在區(qū)間內(nèi)隨機生成閾值r，利用閾值r和每個樣本的標(biāo)簽置信度的大小關(guān)系對樣本進(jìn)行識別。由于概率抽樣方法基于最大似然估計，因此需要進(jìn)行多次的獨立重復(fù)實驗，抽樣過程連續(xù)進(jìn)行SamplingNum次，匯總最終各個樣本的識別結(jié)果進(jìn)行過濾。

1.2 DPS算法

根據(jù)1.1 節(jié)中的描述尋找最佳臨界點后，在閾值區(qū)間中利用概率抽樣的方式進(jìn)行標(biāo)簽噪聲的過濾，得到DPS 算法。DPS算法的主要步驟如下：

輸入 初始樣本集DT；

參數(shù) 隨機森林集成的決策樹個數(shù)nTree，置信度劃分區(qū)間個數(shù)b；

輸出 預(yù)測標(biāo)簽集L。

步驟1 利用隨機森林模型構(gòu)建nTree棵決策樹投票獲得訓(xùn)練集DT中每個樣本的標(biāo)簽置信度confi。

步驟2 將置信度區(qū)間［0，1］平均劃分成b個子區(qū)間[xi，xi+1]，統(tǒng)計置信度處于各個子區(qū)間的概率，并通過式（2）計算置信度處于不同區(qū)間的信息熵EQ(xi)。

步驟3 計算EQ在每個xi處的一階差分FD(xi)，將最佳臨界點e更新為FD的最小值點。

步驟4 計算EQ在每個xi處的二階差分SD(xi)，從e出發(fā)向前搜索，尋找到SD的極小值點xe，此時最佳閾值區(qū)間為[xe-0.2，xe]。

步驟5 在[xe-0.2，xe]區(qū)間內(nèi)隨機生成閾值r，保留conf值高于r的樣本構(gòu)成干凈樣本集CT，剩余樣本被標(biāo)記為噪聲。基于CT構(gòu)建分類器hj。

步驟6 重復(fù)步驟1～5 共SamplingNum次，最終構(gòu)建SamplingNum個分類器hj，對訓(xùn)練集樣本進(jìn)行過濾。

在DPS 算法中，構(gòu)建隨機森林模型的時間復(fù)雜度為O(nTree?N?C?log(N))，置信度計算的時間復(fù)雜度為O(nTree?N)，在對置信度分布分析的過程中，時間復(fù)雜度為O(b)，最終過濾過程的時間復(fù)雜度為O(N)，上述的各個過程均為串行，且重復(fù)進(jìn)行了SamplingNum次，因此，DPS 算法總體時間復(fù)雜度為O(SamplingNum?nTree?N?C?log(N))。

2 實驗結(jié)果與分析

2.1 實驗數(shù)據(jù)與實驗環(huán)境

本文在14 個經(jīng)典UCI 數(shù)據(jù)集上驗證本文DPS 算法的有效性，數(shù)據(jù)集描述見表1。為避免不平衡數(shù)據(jù)對分類性能的影響，對winequality_red 和winequality_white 抽取了其中的第5 和第6 類，對abalone 抽取了其中的第9 類和第10 類。數(shù)據(jù)的平滑、擬合以及實驗部分均在Matlab環(huán)境下實現(xiàn)。

表1 實驗數(shù)據(jù)集描述Tab.1 Experimental dataset description

2.2 數(shù)據(jù)設(shè)計

實驗前先將數(shù)據(jù)集劃分為兩個部分，取其中2/3作為訓(xùn)練集，剩余1/3作為測試集。將訓(xùn)練集按照實驗要求隨機加入噪聲，即隨機改變一定比例樣本的原始標(biāo)簽。在對比實驗中，選取四種標(biāo)簽噪聲過濾算法與DPS 算法進(jìn)行比較，分別是隨機森林（RF）、MVF、HARF和LPS，其中：RF、HARF和LPS都是基于隨機森林提出的方法，在構(gòu)建森林時構(gòu)建決策樹的數(shù)量均為500；MVF 是異質(zhì)集成分類器，由3NN、樸素貝葉斯、隨機森林三種模型集成而得；HARF的閾值設(shè)置為0.7；LPS和DPS的抽樣次數(shù)設(shè)置為11。在標(biāo)簽噪聲過濾后將保留下的樣本利用隨機森林訓(xùn)練為一個分類器對測試集進(jìn)行分類，以該分類結(jié)果判斷該標(biāo)簽噪聲過濾算法的分類泛化性能。為避免實驗隨機性的影響，實驗結(jié)果均為重復(fù)10次求取的平均值。

本文中對比實驗指標(biāo)使用了識別準(zhǔn)確率Acc（Accuracy）、召回率Re（Recall）、查準(zhǔn)率Pre（Precision）、F1和Classif（分類準(zhǔn)確率），具體計算方式如下：

其中：TP表示實際標(biāo)簽和預(yù)測標(biāo)簽均為正類的樣本數(shù)；FP表示實際標(biāo)簽為負(fù)類，預(yù)測標(biāo)簽為正類的樣本數(shù)；TN表示實際標(biāo)簽和與預(yù)測標(biāo)簽均為負(fù)類的樣本數(shù)；FN表示實際標(biāo)簽為正類，預(yù)測標(biāo)簽為負(fù)類的樣本數(shù)。

2.3 實驗結(jié)果與分析

2.3.1 信息熵走勢分析

本組實驗主要驗證信息熵走勢對探索最佳臨界點的有效性。圖3展示了在14個數(shù)據(jù)集下，由式（2）計算出的信息熵的一階差分圖隨置信度的變化情況，為避免局部內(nèi)的微小波動對實驗造成的影響，將原信息熵一階差分函數(shù)利用三次樣條插值進(jìn)行平滑處理，圖3為處理后的一階差分曲線。從圖3中可以看出，不同數(shù)據(jù)集的信息熵差分的走勢差異很大，但它們也存在一些共同點：在所有數(shù)據(jù)集的信息熵一階差分圖像中，函數(shù)值在某一點或某個小區(qū)間內(nèi)會出現(xiàn)至少一次大幅度下降。這是因為橫坐標(biāo)每向右移動一個點，就會損失一個置信度子區(qū)間中所包含的信息量，當(dāng)移動到某點，函數(shù)值出現(xiàn)大幅下降時，說明當(dāng)損失該置信度子區(qū)間的信息量時，獲取到的信息的不確定性驟降，因此，最佳臨界點應(yīng)當(dāng)出現(xiàn)在該點附近。然而，對于部分?jǐn)?shù)據(jù)集，信息熵差分極小值點不止一個，針對這樣的情況，則選取最小值點，即信息熵下降最快的點作為探索最佳臨界點的起點。

圖3 14個數(shù)據(jù)集的一階差分圖Fig.3 First-order difference graphs of 14 datasets

若直接將信息熵一階差分最小值點作為最佳臨界點，帶來的問題是損失大量有效信息。因為從圖3 中可以看出，對于部分?jǐn)?shù)據(jù)集（如sonar、heart、diabetic、winequality_white 等），一階差分值都不是在某一點突然下降的，而是在某個區(qū)間內(nèi)連續(xù)下降，且下降幅度都比較明顯，當(dāng)一階差分下降到最小值時，信息已經(jīng)產(chǎn)生較大損失。因此，為解決這樣的問題，應(yīng)當(dāng)利用二階差分尋找一階差分圖像的拐點作為最佳臨界點。

2.3.2 噪聲識別性能

本組實驗主要對比了DPS與RF、MVF、HARF 及LPS的噪聲識別能力，噪聲比例ratio從5%到30%，每次以5%的幅度遞增。圖4（a）展示了五個算法在14 個數(shù)據(jù)集下的噪聲識別準(zhǔn)確率Acc的匯總結(jié)果，結(jié)果由不同噪聲比例下14 個數(shù)據(jù)集實驗結(jié)果的均值得來。五個算法中，RF、MVF、HARF為0-1抽樣算法，LPS、DPS是概率抽樣算法。從噪聲識別率來看，概率抽樣算法的噪聲識別能力明顯高于0-1 抽樣算法。DPS 算法因采用了動態(tài)過濾策略，其噪聲識別能力相比LPS 也有一定的提高，尤其在噪聲比例較低的情況下，噪聲識別能力的優(yōu)勢更加明顯。

圖4（b）和（c）分別展示了五個算法在14個訓(xùn)練集下噪聲識別的召回率和精確率，從圖中可以看出，DPS的召回率遠(yuǎn)高于HARF 和LPS，且這三個算法的召回率幾乎不隨噪聲比例ratio的增長而變化，RF 和MVF 召回率較低且不夠穩(wěn)定，隨ratio的變化比較明顯。從精確率來看，五個算法在噪聲比例為5%時幾乎沒有表現(xiàn)出差異，隨著ratio的增加，各個算法的精確率逐漸顯現(xiàn)出差異，其中，HARF 和DPS 下降速度較快，而MVF 的Pre指標(biāo)在此時顯示出一定的穩(wěn)定性，下降速度相比其他算法更加緩慢。從圖4（b）和（c）可以看出：DPS 和HARF 更傾向于保留干凈樣本，會不可避免地保留部分噪聲，因此精確率較低；而MVF 更傾向于過濾噪聲樣本，在過濾的過程中也會過濾掉部分干凈樣本，嚴(yán)重時還會造成過度過濾現(xiàn)象。

圖4 五種算法的Acc、Re和Pre指標(biāo)對比Fig.4 Comparison of Acc Re and Pre of 5 algorithms

為綜合Re和Pre的實驗結(jié)果，圖5 展示了五個算法在14個數(shù)據(jù)集上的F1值，從圖中可以看出，在絕大部分情況下，HARF、LPS 和DPS 的F1值在不同的數(shù)據(jù)集上表現(xiàn)各有優(yōu)勢，且明顯優(yōu)于其他兩種算法。

圖5 五種算法的F1指標(biāo)對比Fig.5 Comparison of F1 of 5 algorithms

為了更好地比較五種方法的F1指標(biāo)，圖6 對14 個數(shù)據(jù)集的F1指標(biāo)求取平均值，總體來看，在F1指標(biāo)下，概率抽樣方法仍然具有較大的優(yōu)勢，其中DPS 的F1指標(biāo)在各個噪聲比例下均能夠保持較高水平。

圖6 五種算法的F1均值對比Fig.6 Comparison of F1 mean value of 5 algorithms

2.3.3 分類性能比較

圖7 對比了五種算法在14 個數(shù)據(jù)集下的分類泛化能力，Classif越高，表示數(shù)據(jù)集在經(jīng)由該算法過濾后，訓(xùn)練出的分類器分類能力越好。從圖7 中可以看出，DPS 的分類準(zhǔn)確率在大多數(shù)情況下比其他算法表現(xiàn)更好，在低噪聲的情況下，DPS更具優(yōu)勢。除了DPS 外，LPS 在少部分?jǐn)?shù)據(jù)集下的分類準(zhǔn)確率也表現(xiàn)出了一定的優(yōu)勢，而HARF 的分類能力相比其他算法表現(xiàn)最差。

圖7 五種算法的Classif指標(biāo)對比Fig.7 Comparison of Classif of 5 algorithms

14 個數(shù)據(jù)集Classif的平均值如圖8 所示，可以看出，隨著噪聲比例的增大，五個算法的Classif基本呈下降趨勢，其中DPS 下降速度最慢，且Classif指標(biāo)最高，說明其概率抽樣方法受噪聲影響更小，魯棒性更高。

圖8 五種算法的Classif均值對比Fig.8 Comparison of Classif mean value of 5 algorithms

3 結(jié)語

本文主要針對置信度分布差異較大的各類數(shù)據(jù)集無法適應(yīng)統(tǒng)一的標(biāo)簽噪聲過濾策略的問題，提出了一種基于動態(tài)概率抽樣的標(biāo)簽噪聲過濾方法，該方法通過統(tǒng)計不同數(shù)據(jù)集的樣本置信度出現(xiàn)的頻率來分析置信度的分布特點，利用此概率的信息熵尋找過濾的最佳臨界點，再結(jié)合概率抽樣的思想，在使得過濾器達(dá)到高識別率、高分類準(zhǔn)確率的目標(biāo)的同時，也增強了過濾器在不同數(shù)據(jù)集上的普適性。