取樣方法與代價敏感方法的比較

摘要： 傳統的方法中，標準的分類器設計一般基于精度，但是許多實際應用問題中，不同的類別對應的錯分代價也不同，往往少數類樣本更加值得關注。對于不平衡的數據集處理，最直接的方法就是改變學習算法的本身使之成為代價敏感算法，當然相對于改變數據集的結構，這也是稍難實現的方法。除此之外，改變數據集的分布也是常用辦法，本文采用的辦法是過取樣和欠取樣。本文將對以上所提到的三種方法在不同的數據集上比較其性能，以了解不同解決策略的特性與適用的環境。

關鍵詞：代價敏感；取樣；不平衡數據集

中圖分類號：TP392文獻標識碼：A文章編號：1009-3044(2008)17-21546-02

1 引言

在數據集各類別數目只是輕微不平衡時的情況比較易于處理，但是當個別類別嚴重不平衡時，許多學習方法都易陷入困境[1]。小類別樣本在學習的過程中更容易被忽略，與此同時，算法在此種情況下不能對未知樣本進行正確的分類。由于數據集不平衡，分類算法對非平衡數據集進行分類的性能不盡人意，因為少數類樣本通常比普通樣本難以識別，而且大多數數據挖掘算法對于處理少數類樣本有很大困難。當對非平衡數據集進行有指導的訓練時，其訓練算法通常對多數類樣本會產生很高的預測準確率，但是對少數類樣本的預測準確性卻很差。通常情況下多數類樣本遠多于少數類樣本，這意味著對所有樣本進行預測，可以在不預測出任何少數類樣本的情況下得到很高的正確率。諸如決策樹歸納系統或者多層感知器等典型分類器被設計為使整體準確率最高，而不考慮每個類的相對分布情況，非平衡數據給這類典型的分類器提出了挑戰。這些分類器在關注于將多數類樣本盡量分類準確時，傾向于忽視少數類，因此傳統算法對于解決非平衡數據的分類問題的能力有限。在圖1中可以看出普通算法與代價敏感算法的不同之處。

有許多方法都可以用來處理不平衡數據集。最直接的方法就是改變學習算法的本身使之成為代價敏感算法，除此之外，改變類分布也是方法之一。本文重點介紹了兩種改變類分布的算法：過取樣（oversampling）和欠取樣(undersampling)[4]。過取樣通過復制小類樣本使數據集達到平衡，欠取樣方法旨在減少低代價類別的樣本數目。本文主要研究評價這兩類不同方法在不平衡數據集上的表現，評估其效能，用以了解不同解決策略的特性與適用的環境。

2 取樣方法

處理非平衡數據的最常用方法就是采樣。采樣方法的基本思想就是通過改變訓練數據的分布來消除或減小數據的不平衡。基本采樣方法包括undersampling和oversampling。Japkowicz在文獻[4]中研究了數據集不平衡所帶來的影響。其中重點評估了這兩種方法。undersampling是通過減少多數類樣本的數量來平衡兩類樣本，而oversampling則是通過復制少數類樣本來完成。這兩種方法都能減小數據整體的不平衡程度，但是他們都存在一些缺點。undersampling忽略了潛在的有用的多數類樣本，因而可能降低分類器的性能。而oversampling引入了額外的訓練數據，這會延長建立分類器所需時間，更不好的是它對樣本進行精確的復制會導致過度擬合。在極端的情況下，分類器會產生只涵蓋一個被復制多次的樣本的規則。同時這種方法也沒有解決本文前面提到的數據缺乏問題。因此undersampling可能是更好的方法。當然如果是使用人工數據進行研究就不會有上述問題出現。

雖然取樣方法存在一些缺陷，但是在處理不平衡數據集上仍得到了廣泛應用[5]。主要原因在于并不是所有的算法都實現了代價敏感，所以取樣方法可以作為實現代價敏感的不錯的選擇。時至今日，雖然實現了代價敏感的算法有所增加，但是仍然是有限的。其次，許多不平衡數據集的樣本數目巨大，為了讓學習更為可行，必須減少訓練集的數目。在這種情況下，欠取樣是一種合理，有效的方法。通常我們并不知道誤分類代價，這也是為什么取樣能夠廣泛應用的原因。

3 代價敏感算法

前文也提到，改變類的分布并不是改進學習算法在不平衡數據集上性能的唯一方法。將兩類分配給不同的誤分類代價也是方法之一。Veropoulos在文獻[6]中提出可以用兩種方法來控制SVM中TP（true positive）和TN（true negative）之間的平衡。下面實現的是其中之一：對兩類別施加不同懲罰系數的方法。

根據對兩個類別施加不同懲罰系數的方法，可以構造如下線性首先二次規劃問題：

4 實驗

本部分為實驗部分，所有的實驗分別用oversampling，undersampling，標準SMO以及經過改進實現了代價敏感的cs-smo在四個數據集上實驗。實驗采用10-cross-validation。

表1為本次實驗所用UCI數據集[3]。實驗結果如圖2所示。

圖2中，各個算法的性能可以又由算法的TP（true positive rate），TN(true negative rate)，和ROC值來綜合評估。ROC(receiver operating characteristic ) 曲線能客觀的反映分類方法的性能。ROC曲線即以“靈敏度”為縱坐標，以“1 - 特異性”為橫坐標所畫的曲線。一般來說，ROC 曲線下面積越大，說明分類性能越好。可以看到在sick數據集中，標準smo算法對以正例的分類精度為0，也就是將小樣本類全部分錯，而其他三種算法則有效改善了這一問題，提高了算法高代價類的分類精度及ROC面積。在diabetes和hepatitis上，cs-smo的ROC值略低于前兩種算法，但是對于正類的分類精度最高。在heart數據集上，undersampling性能好于oversampling。綜合觀察所有數據集情況而言，oversampling算法性能最好，其次是undersampling，cs-smo算法的表現比前兩種算法略差。Undersampling效果略次的原因在于在減少樣本的過程中，刪除了數據集中有用的信息。有一些文獻提到oversampling在不平衡數據集上的表現要好于undersampling[5]，這與本文情況類似。但是需要注意的是，oversampling通常會增加訓練時間，在某些情況的還會導致過擬合。

5 結論

在過去的文獻中也有和本文得出的結論不同的，這也許是由于取樣算法在某種的程度上的好壞也和數據集有直接的關系。關于提高取樣算法的性能，之前人們已經提出過一些方法。例如：在oversampling過程中引進“人造”樣本，在undersampling過程中刪除用處較小的多數類樣本，在undersampling中應用多重子樣本。這些方法已經和oversampling和undersampling做過比較，但是它們的性能還沒有和代價敏感學習算法相比較，這也是未來值的關注的工作之一。也本部分所引出的問題有：oversampling和undersampling有一些已知缺點，為什么代價敏感學習算法的性能會差于這兩種方法；如何才能提高代價敏感學習算法的性能；另外，是否在不平衡數據集中能用取樣方法替代代價敏感學習算法。這些都將是下一步需要研究的內容。另外將本文所做實驗應用到實際生活中的數據集中做實驗，也會是有意義的研究。

參考文獻：

[1] Elkan. C. (2001) The Foundations of Cost-Sensitive Learning. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence (IJCAI'01)， pp. 973-978.

[2] Drummond C， Holte R C. C4.5， class imbalance， and cost sensitivity: why under-sampling beats over-sampling. In: Proceedings of ICML'2003 Workshop on Learning from Imbalanced Data Sets， 2003.

[3] Blake， C.L.， Merz， C.J. (1998). UCI Repository of machine learning databases [http: -- www.ics.uci.edu - ~mlearn - MLRepository.html]. Irvine， CA: University of California， Department of Information and Computer Science.

[4] Japkowicz N. (2000)， The class imbalance problem: Significance and strategies. In Proceedings of the InternationalConference on Artificial Intelligence， Las Vegas.

[5] Estabrooks A， Jo T， Japkowicz N. A multiple resampling method for learning from imbalanced data sets. Computational Intelligence， 2004，20(1): 18-19.

[6] Veropoulos K， Cambell C ， Cristianini N. Controlling the sensitivity of support vector machines [C] . Proceedings of the International Joint Conference on AI ，1999:55-60.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文