宋磊磊

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都　610065）

類標(biāo)噪聲研究綜述

宋磊磊

（四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065）

0　引言

文本分類被廣泛應(yīng)用于信息檢索與其他知識(shí)管理系統(tǒng)中。一些常用的用于解決文本分類的有監(jiān)督方法包括：樸素貝葉斯[1-2]、支持向量機(jī)[3-4]、K近鄰[5]和最大熵模型[6]。

文本分類任務(wù)需要大量的被正確標(biāo)注的訓(xùn)練數(shù)據(jù)集，這些標(biāo)注數(shù)據(jù)集往往來(lái)自人工標(biāo)注或者遠(yuǎn)距離監(jiān)督方法。然后，不管是人工還是自動(dòng)的標(biāo)注，都會(huì)不可避免地引入類標(biāo)噪聲，對(duì)分類器的構(gòu)建產(chǎn)生嚴(yán)重的影響。因此，研究有效地處理噪聲方法就變得十分重要。主流的方法主要分為兩種，第一種是去噪研究，即首先識(shí)別噪聲實(shí)例，進(jìn)而直接刪除噪聲數(shù)據(jù)以保證數(shù)據(jù)的“純度”；第二種是容噪研究，與去噪算法不同的是，該思路假設(shè)噪聲實(shí)例同樣可以對(duì)分類器提供積極影響，前提是從模型的角度合理的挖掘其積極因素。

1　類標(biāo)噪聲處理策略

1.1去噪算法研究

早期的類標(biāo)噪聲處理思路主要集中在如何準(zhǔn)確的識(shí)別出噪聲實(shí)例，借用的模型有最近鄰算法[7]、C4.5[8]、概率主題模型[9]和類別數(shù)據(jù)分布[10]。以下對(duì)前兩個(gè)方法進(jìn)行介紹：

（1）最近鄰算法去噪

該方法利用最近鄰算法制定啟發(fā)式規(guī)則識(shí)別噪聲實(shí)例?？偟臄?shù)據(jù)集為T，包括n個(gè)實(shí)例P1…n，每個(gè)實(shí)例P 有K個(gè)最近的鄰居P.N1...k。P的“敵對(duì)”近鄰集P.E被定義為與P具有不同類標(biāo)的最近實(shí)例。P.A1...a表示包括最近鄰集中包括P的實(shí)例的集合。那么，假如實(shí)例P被刪除時(shí)，P.A1...a中的實(shí)例被分類判斷正確，則說(shuō)明實(shí)例P是噪聲數(shù)據(jù)，應(yīng)該被去除。具體的算法如圖1所示。

圖1　最近鄰算法去噪

（2）C4.5去噪

該方法利用C4.5決策樹算法來(lái)進(jìn)行噪聲識(shí)別，它的直觀假設(shè)是當(dāng)我們獲得可靠的規(guī)則時(shí)，噪聲實(shí)例與正常實(shí)例表現(xiàn)出了不同的特點(diǎn)，通常噪聲實(shí)例會(huì)被可靠規(guī)則所覆蓋，但是卻產(chǎn)生錯(cuò)誤的類標(biāo)?；谝陨系募僭O(shè)，該方法首先將整個(gè)數(shù)據(jù)集E分成若干個(gè)子集。對(duì)于每個(gè)子集，學(xué)習(xí)一個(gè)決策樹模型Ri并從中選擇可靠的規(guī)則集GRi，接著利用GRi評(píng)價(jià)整個(gè)數(shù)據(jù)集E。對(duì)于具體某個(gè)實(shí)例Ik，定義兩個(gè)錯(cuò)誤計(jì)數(shù)變量和，它們共同決定改實(shí)例是否為噪聲數(shù)據(jù)。具體的框架流程如圖2所示。

1.2容噪算法研究

去噪算法存在著潛在的風(fēng)險(xiǎn)，特別是當(dāng)模型錯(cuò)誤的識(shí)別了噪聲數(shù)據(jù)，而把真正的噪聲實(shí)例保留下來(lái)作為標(biāo)準(zhǔn)訓(xùn)練集時(shí)?？上攵?，此時(shí)的去噪算法不但沒(méi)有達(dá)到清理噪聲的目的，而且還加劇了噪聲數(shù)據(jù)對(duì)分類模型的影響。因此，噪聲處理的重心開始向容噪研究方法轉(zhuǎn)移。其中，比較典型的容噪算法包括改進(jìn)的支持向量機(jī)[11]、BayesANIL[12]和Probabilistic Kernel Fisher method[13]。以下介紹前兩個(gè)方法：

（1）改進(jìn)的支持向量機(jī)

該方法在原有支持向量機(jī)的基礎(chǔ)上僅僅對(duì)核矩陣進(jìn)行修改，達(dá)到了容忍噪聲的目的。我們知道，標(biāo)準(zhǔn)的SVM優(yōu)化函數(shù)可以表示為：

圖2　C4.5去噪

其中，Q=KoyyT，K為核矩陣。本文對(duì)每個(gè)實(shí)例xi引入了翻轉(zhuǎn)變量εi，從而使得Q發(fā)生變化，最終影響SVM的優(yōu)化函數(shù)為如下所示：

（2）BayesANIL

該方法對(duì)生成的角度對(duì)噪聲數(shù)據(jù)進(jìn)行建模，模型可簡(jiǎn)單表示成Z→D→W，三個(gè)變量分別表示實(shí)例類標(biāo)、實(shí)例以及實(shí)例的詞袋子。其中P（w|d）與＜d，z＞為可觀測(cè)值，P（d，z）為潛在變量值，也是本文需要估計(jì)的變量值，該值可以直觀地理解為實(shí)例d在多大程度上屬于z類。因此，本文利用EM算法對(duì)潛在變量進(jìn)行估計(jì)，最終將P（d，z）運(yùn)用到樸素貝葉斯和支持向量機(jī)分類器中，取得了不錯(cuò)的效果。

對(duì)于樸素貝葉斯分類器，關(guān)鍵在于估計(jì)詞在類別條件下的概率：

其中，P（w|d）為可觀測(cè)值，而P（d|z）可由EM估計(jì)的P（d，z）得到。此種方法的優(yōu)勢(shì)還在于P（w|z）不需要平滑處理。

對(duì)于支持向量機(jī)分類器，我們可以改變每個(gè)實(shí)例的損失代價(jià)，讓那些值得信賴的類標(biāo)數(shù)據(jù)盡量被判別正確，而對(duì)于那些潛在的噪聲數(shù)據(jù)設(shè)置一個(gè)較小的損失代價(jià)。形式化表示如下，Ci為損失代價(jià)。

2　結(jié)語(yǔ)

隨著網(wǎng)絡(luò)數(shù)據(jù)量的爆炸式增長(zhǎng)，如何利用大數(shù)據(jù)，從中挖掘出有價(jià)值的資源變得更加迫切。機(jī)器學(xué)習(xí)作為一種行之有效的方法在實(shí)際運(yùn)用中需要大量的人工參與，例如為分類器標(biāo)注大量的數(shù)據(jù)。而人工參與不可避免帶來(lái)數(shù)據(jù)噪聲，這是現(xiàn)有分類算法所不能容忍的。因此，大量的研究者開始設(shè)計(jì)不同的策略消除噪聲的影響。早期的研究主要關(guān)注如何正確識(shí)別噪聲實(shí)例。遺憾的是，去噪思路在實(shí)際運(yùn)用中引入了潛在的風(fēng)險(xiǎn)，這才將研究的重心向容噪算法轉(zhuǎn)移。但即使同是容噪算法，在處理不同問(wèn)題、噪聲水平不同時(shí)也表現(xiàn)不一。

[1]Lewis D D.Naive（Bayes）at Forty:The Independence Assumption in Information Retrieval[M].Machine Learning:ECML-98.Springer Berlin Heidelberg，1998:4-15.

[2]McCallum A，Nigam K.A Comparison of Event Models for Naive Bayes Text Classification[C].AAAI-98 Workshop on Learning for Text Categorization，1998，752:41-48.

[3]Joachims T.Text Categorization with Support Vector Machines:Learning with Many Relevant Features[M].Springer Berlin Heidelberg，1998.

[4]丁世飛，齊丙娟，譚紅艷.支持向量機(jī)理論與算法研究綜述[J].電子科技大學(xué)學(xué)報(bào)，2011，40（1）:2-10.

[5]Yang Y.An Evaluation of Statistical Approaches to Text Categorization[J].Information Retrieval，1999，1（1-2）:69-90.

[6]Nigam K，Lafferty J，McCallum A.Using Maximum Entropy for Text Classification[C].IJCAI-99 Workshop on Machine Learning forInformation Filtering，1999，1:61-67.

[7]Wilson D R，Martinez T R.Instance Pruning Techniques[C].ICML.1997，97:403-411.

[8]Zhu X，Wu X，Chen Q.Eliminating Class Noise in Large Datasets[C].ICML.2003，3:920-927.

[9]林洋港，陳恩紅.文本分類中基于概率主題模型的噪聲處理方法[J].計(jì)算機(jī)工程與科學(xué)，2010，32（7）:89-92.

[10]李湘東，巴志超，黃莉.文本分類中基于類別數(shù)據(jù)分布特性的噪聲處理方法[J].現(xiàn)代圖書情報(bào)技術(shù)，2014，30（11）:66-72.

[11]Biggio B，Nelson B，Laskov P.Support Vector Machines Under Adversarial Label Noise[C].ACML.2011:97-112.

[12]Ramakrishnan G，Chitrapura K P，Krishnapuram R，et al.A Model for Handling Approximate，Noisy or Incomplete Labeling in Text Classification[C].Proceedings of the 22nd International Conference on Machine Learning.ACM，2005:681-688.

[13]Li Y，Wessels L F A，de Ridder D，et al.Classification in the Presence of Class Noise Using a Probabilistic Kernel Fisher Method [J].Pattern Recognition，2007，40（12）:3349-3357.

Class Label Noise;Denoising Algorithm;Robustness Algorithm

Research Overview of Class Label Noise

SONG-Lei-lei
（College of Computer Science,Sichuan University,Chengdu 610065）

1007-1423（2016）03-0020-04

10.3969/j.issn.1007-1423.2016.03.005

宋磊磊（1991-），男，貴州貴陽(yáng)人，碩士研究生，研究方向?yàn)閿?shù)據(jù)挖掘

2015-12-15

2016-01-10

在機(jī)器學(xué)習(xí)中，類標(biāo)噪聲難以避免的存在于標(biāo)注數(shù)據(jù)里，這樣的噪聲數(shù)據(jù)會(huì)對(duì)分類器等模型的建構(gòu)產(chǎn)生嚴(yán)重的影響。因此，越來(lái)越多的研究者把類標(biāo)噪聲算法研究作為分類器效果提升的一個(gè)突破口。針對(duì)解決問(wèn)題思路的不同，提出并改進(jìn)許多行之有效的噪聲處理模型。其中，按照解決思路的不同，可將噪聲處理算法分為去噪算法與容噪算法。

類標(biāo)噪聲；去噪算法；容噪算法

In machine learning，the class label problem is unlikely to be completely excluded in labelled dataset which would deteriorate classifier construction.Therefore，most of researchers are focusing on this problem for more reliable classification algorithms.There are lots of effective approaches for the class label problem according to different solutions.We can divide them into denoising and robustness directions.