代價敏感大間隔分布學習機

周宇航　　　周志華

(計算機軟件新技術國家重點實驗室(南京大學)　南京　210023)

?

代價敏感大間隔分布學習機

周宇航周志華

(計算機軟件新技術國家重點實驗室(南京大學)南京210023)

(軟件新技術與產業化協同創新中心(南京大學)南京210023) (zhouyh@lamda.nju.edu.cn)

在現實生活中的很多應用里，對不同類別的樣本錯誤地分類往往會造成不同程度的損失，這些損失可以用非均衡代價來刻畫.代價敏感學習的目標就是最小化總體代價.提出了一種新的代價敏感分類方法——代價敏感大間隔分布學習機(cost-sensitive large margin distribution machine, CS-LDM).與傳統的大間隔學習方法試圖最大化“最小間隔”不同，CS-LDM在最小化總體代價的同時致力于對“間隔分布”進行優化，并通過對偶坐標下降方法優化目標函數，以有效地進行代價敏感學習.實驗結果表明，CS-LDM的性能顯著優于代價敏感支持向量機CS-SVM，平均總體代價下降了24%.

代價敏感學習；間隔分布；支持向量機；表示定理；對偶坐標下降法

在現實生活的很多應用中，對不同類別的樣本錯誤地分類往往會造成不同程度的損失，這些損失可以用非均衡代價來刻畫.例如在醫療診斷中，將病人錯誤地判斷為健康人的代價一般比將健康人誤診為病人的代價大得多，因為前者會延誤疾病的治療，從而可能導致患者的死亡.在這樣的場景中，標準的機器學習技術以最小化錯誤率為目標，也就隱含地假設了2種類型的分類錯誤造成的代價是相同的，因此訓練出來的分類器就會同等地看待病人和健康人，進而增加將病人誤判為健康人的可能性.由此可見，標準的機器學習技術并不適用于此類對代價敏感的應用，因此對代價敏感學習的研究就顯得十分有必要了.

一般而言，代價敏感學習的目標是在給定不同類別的誤分類代價時，使用訓練樣本學習得到一個分類器，使其在對新的未知類別的樣本進行分類時，能有盡可能小的總體代價.代價敏感性廣泛地存在于現實生活的各種應用中，如醫療診斷、垃圾郵件檢測、網絡入侵檢測等等.

本文針對代價敏感問題，提出了一種新的代價敏感學習方法——代價敏感大間隔分布學習機(cost-sensitive large margin distribution machine, CS-LDM).該方法在最小化總體代價的同時對間隔分布進行優化，與傳統的代價敏感支持向量機相比具有更高的性能.

1　相關工作

在過去的十幾年里，研究者們圍繞代價敏感學習問題進行了較為深入的研究，并得到了一系列有效的成果.在學習過程中，由于問題性質的不同，我們可能會遭遇不同類型的代價，如誤分類代價、測試代價、指導代價等.其中，誤分類代價在真實的應用中最為常見.誤分類代價一般由專家給出，且又有2種不同的類型：基于類別的代價和基于樣本的代價.在基于類別的代價中，代價只與類別有關；而在基于樣本的代價中，代價與具體的樣本相關.在實際應用中，基于類別的代價更易獲得，因此在本文中我們也將專注于此類代價敏感問題.

在代價敏感學習中，一類通用的方法是再縮放[1-2].這種方法試圖改變訓練數據的分布，可以將任何以最小化錯誤率為目標的標準分類器轉化為以最小化總體代價為目標的代價敏感分類器.針對代價敏感的二分類問題，再縮放方法已經從理論上得到了支持[1].而最近的研究成果則進一步表明，在代價敏感的多分類問題上，僅當代價矩陣滿足“一致性條件”時，才有類似二分類問題的閉式解，否則需要利用任務分解后的集成學習等其他機制[2].

一般來說,有3種典型的實現再縮放的策略.

1) 加權法.不同類別中的樣本被賦予不同的權值，使得高代價類別的樣本具有更大的權值，從而獲得代價敏感性；然后在帶有權值的數據集上使用可以利用權值信息的學習方法訓練標準分類器[3-4].

2) 取樣法.對訓練樣本集進行重采樣，增加高代價類別的樣本數量，或減少低代價類別的樣本數量，以使數據集獲得代價敏感性；然后同樣在改變后的數據集上訓練標準分類器[1,5].

3) 閾值移動法.通過應用貝葉斯風險最小化原理，改變后驗概率的決策閾值使得高代價樣本不易被分錯[4,6].

除了上面介紹的通用的再縮放方法外，還有一些其他的嵌入式方法通過對具體的方法進行代價敏感性設計來應對代價敏感性問題.一些常見的分類方法，如決策樹、神經網絡、Adaboost和支持向量機等都有其代價敏感版本[7-10].近幾年，代價敏感的多類分類問題也得到了研究[2,11].

代價敏感支持向量機CS-SVM[10,12]根據不同類別的誤分類代價調整形式化目標中的損失函數，從而使支持向量機的判決邊界盡可能遠離誤分類代價較大的訓練樣本，以期減少高代價樣本被錯誤地判斷為其他類別的概率.

傳統的支持向量機包括代價敏感支持向量機的核心思想在于最大化“最小間隔”.然而最新的研究結果顯示，相比最小間隔，“間隔分布”對于降低分類器的泛化誤差更加重要[13]，這一點也已經得到了證明[14].受此啟發，大間隔分布學習機LDM通過同時最大化間隔均值并最小化間隔方差來優化間隔的分布，得到了更好的性能[15].

本文將大間隔分布思想應用到代價敏感學習中,提出了一種新的代價敏感分類方法CS-LDM.與CS-SVM不同的是，CS-LDM在最小化總體代價的同時，致力于對間隔的分布進行優化，并通過對偶坐標下降方法優化目標函數，以有效地進行代價敏感學習.

2　CS-LDM方法

本節首先提出CS-LDM的形式化目標，然后給出對該目標進行優化求解的算法.

2.1形式化目標

在代價敏感學習中，記輸入空間為X?d，輸出空間為Y={+1,-1}，數據則根據分布D(X,Y)獨立地從樣本空間中抽取.

支持向量機SVM是一類傳統的大間隔學習方法，其核心思想在于最大化“最小間隔”.對于支持向量機y=wTφ(x)，樣本(xi,yi)的間隔被定義為[16-17]

γi=yiwTφ(xi),?i=1,2,…,n.

(1)

而最小間隔則是訓練集中所有樣本間隔的最小值.

在SVM的基礎上，CS-SVM根據不同類別的誤分類代價調整形式化目標中的損失函數，使誤分類代價較大的訓練樣本擁有更大的損失函數.也就是說，CS-SVM的形式化目標如下：

(2)

在這里，ci即為第i個訓練樣本的誤分類代價，而ciεi則是將該訓練樣本分錯造成的損失.參數C用于權衡模型復雜度和損失.

正如第1節提到的，傳統的支持向量機(包括CS-SVM)的核心思想在于最大化最小間隔.然而最新的研究結果顯示，相比最小間隔，“間隔分布”對于降低分類器的泛化誤差更加重要[13]，這一點也已經得到了證明[14].因此，可以利用大間隔分布思想來設計一種新的代價敏感分類方法，能夠獲得比代價敏感支持向量機更高的性能.

最直接的能夠表示間隔分布的統計量顯然應該是間隔均值和間隔方差.為了方便公式的推導，令X=[φ(x1),φ(x2),…,φ(xn)],y=[y1,y2,…,yn]T，同時令Y為n階對角矩陣，且其對角元素為yi,…,yn.這樣，可以根據式(1)計算得到訓練集的間隔均值為

(3)

而間隔方差為

(4)

根據關于大間隔分布的最新理論成果[14]，可以通過同時最大化間隔均值并最小化間隔方差來優化間隔的分布.因此，在CS-SVM的基礎上，我們能夠進一步得到CS-LDM的形式化目標：

(5)

其中，λ1和λ2分別是用于權衡模型復雜度與間隔方差和間隔均值的參數.

2.2優化求解

將式(3)(4)代入式(5)中，可以得到

(6)

由于式(6)中包含了對間隔方差的優化，因此無法像傳統的SVM那樣，直接使用拉格朗日乘子法簡單地求得可以應用核技巧進行優化的對偶式.幸運的是，根據表示定理[18]，式(6)的最優解應具有下面的形式：

(7)

其中，α=[α1,α2,…,αn]T是w*關于訓練樣本的線性表示的系數.因此有

(8)

其中K=XTX即為訓練樣本的核矩陣.令K:i為矩陣K的第i列向量，則式(6)可進一步改寫為

(9)

其中，Q=K+4λ1(nKTK+(Ky)(Ky)T)n2，且q=-2λ2Kyn.

為式(9)中的2個約束條件分別引入拉格朗日乘子β=[β1,β2,…,βn]和μ=[μ1,μ2,…,μn]后，可以得到相應的拉格朗日函數：

(10)

對式(10)中的α和ε求偏導數，并置為0，有

(11)

(12)

將式(11)(12)代入式(10)中，即可得到式(9)的對偶形式如下:

(13)

其中，H=YKQ-1KY，Q-1是Q的逆矩陣，e為全1向量.由于式(13)中的目標優化公式為凸函數, 且約束條件為簡單的箱型約束，所以能夠有效地通過對偶坐標下降方法得到式(13)的最優解β*[19-20].

在得到β*后，可以根據式(11)計算出系數

α=Q-1(KYβ*-q).

(14)

由此，在對測試樣本z進行分類時，其標記可以通過式(15)獲得：

(15)

其中,k(·)為訓練時所使用的核函數.

3　實驗測試

本節首先介紹實驗的設置，然后給出實驗的結果，并對結果進行簡單的分析.

3.1實驗設置

我們在15個UCI數據集上進行了對比實驗，關于數據集的具體信息由表1給出.所有樣本的特征值都被規范化到[0,1]區間上.負類樣本的誤分類代價為1，正類樣本的誤分類代價取值范圍為{5,10,20}.

在每個數據集上，針對每個代價取值進行10次實驗.在每次測試中，將數據集中的樣本隨機分成3份，其中的2份用作訓練集，另外1份用作測試集.我們首先在訓練集上進行5-折交叉驗證實驗以選擇參數，參數的取值范圍為{0.1,1,10}，然后使用選取的參數重新訓練分類器并對測試集進行分類, 最后根據分類結果計算總體代價.最終的總體代價取10次實驗的均值.所有的方法都使用線性核.

Table1　Characteristics of Experimental Data Sets

在實驗中，將提出的CS-LDM與以下3種分類器進行比較：1)SVM；2)LDM；3)CS-SVM.3.2節會給出這些方法的實驗結果，并對結果進行分析.

3.2實驗結果

表2總結了全部實驗結果，并用粗體標出了在95%的置信度下進行成對t檢驗表現最佳的分類器.為了更直觀地對實驗結果進行觀察，圖1對CS-LDM與對比分類器在不同代價設定下的平均總體代價進行了可視化比較.其中X軸表示不同的數據集；Y軸表示不同分類器與SVM的總體代價的比值，比值越低，分類器的性能越好.最后，表3統計了CS-LDM與對比分類器進行比較的WinTieLoss結果.

從圖1可以直觀地看到，總體來說，2個考慮了代價的分類器CS-SVM和CS-LDM表現得顯著優于傳統的SVM和LDM.其中，CS-LDM的性能更加穩定，不僅在多數數據集上都有最佳表現，而且從來沒有輸給過其他3種分類器.

從表2可以看出，在數據集promoters，vote，haberman，isolet上，CS-LDM的結果都是一枝獨秀的.但是在數據集colic.ORIG，wdbc，credit-a，german上，CS-LDM和CS-SVM的區別卻并不明顯.其原因可能是在這些數據集上，CS-SVM的性能已經足夠好，因而CS-LDM也無法取得更好的成績.

Table2　Total Costs of CS-LDM and Compared Methods

Fig. 1　Total costs of CS-LDM and compared methods.圖1　CS-LDM與其他對比分類器在不同代價設定下的平均總體代價比較

Table 3WinTieLoss Counts of CS-LDM vs Compared Methods

表3CS-LDM與對比分類器進行比較的WinTieLoss結果

CostCS-LDM:Win∕Tie∕LossSVMLDMCS-SVM57∕8∕011∕4∕010∕5∕01011∕4∕011∕4∕010∕5∕0209∕6∕011∕4∕09∕6∕0

此外，通過觀察圖1可以發現，CS-LDM與CS-SVM的差別同LDM與SVM的差別在數據集promoters，heart，clean，isolet上并不一致.也就是說，在這些數據集上，LDM的性能要比SVM更差.之所以會出現這種現象，其原因可能在于LDM和SVM的學習目標是最小化錯誤率，也就隱含地假設了2類樣本的誤分類代價是相同的.因此，在某些數據集上，LDM為了更好地降低2類樣本的整體錯誤率，可能會將較多的正類樣本分錯.然而在本文的代價敏感實驗中，正類樣本擁有更高的誤分類代價，從而使得LDM的總體代價高于SVM.而考慮了代價敏感性的CS-LDM卻不會犯同樣的錯誤.

關于CS-LDM的性能總體上優于CS-SVM的原因，我們認為是盡管CS-LDM在代價較高的正類樣本上的誤分類次數與CS-SVM相差不多，但是由于CS-LDM考慮了樣本間隔的分布，所以它在負類樣本上的分類情況更好，進而擁有了更優的性能.根據表2中的結果可以計算得出，CS-LDM的平均總體代價比CS-SVM下降了24%.

4　結束語

在現實生活的很多應用中，對不同類別的樣本錯誤地分類往往需要承擔不同的代價.代價敏感學習的目標就是在給定不同類別的誤分類代價時，使用訓練樣本集學習得到一個分類器，使其在對新樣本進行分類時能有盡可能小的總體代價.

傳統的大間隔學習方法的核心思想在于最大化最小間隔.然而最新的研究結果顯示，相比最小間隔，間隔分布對于降低分類器的泛化誤差更加重要.因此，本文希望用大間隔分布思想來解決代價敏感分類問題，并為此提出了CS-LDM方法.與CS-SVM不同的是，CS-LDM在最小化總體代價的同時，致力于對間隔的分布進行優化，并通過對偶坐標下降方法優化求解目標函數，以有效地進行代價敏感學習.實驗結果表明，CS-LDM的性能要顯著優于CS-SVM，平均總體代價下降了24%.

[1]Elkan C. The foundations of cost-sensitive learning[C]Proc of Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2001: 973-978[2]Zhou Zhihua, Liu Xuying. On multi-class cost-sensitive learning[J]. Computational Intelligence, 2010, 26(3): 232-257[3]Ting K M. An instance-weighting method to induce cost-sensitive trees[J]. IEEE Trans on Knowledge and Data Engineering, 2002, 14(3): 659-665[4]Zhou Zhihua, Liu Xuying. Training cost-sensitive neural networks with methods addressing the class imbalance problem[J]. IEEE Trans on Knowledge and Data Engineering, 2006, 18(1): 63-77[5]Maloof M A. Learning when data sets are imbalanced and when costs are unequal and unknown[C]Proc of ICML-2003 Workshop on Learning from Imbalanced Data Sets II. Menlo Park, CA: AAAI Press, 2003[6]Jiang Shengyi, Xie Zhaoqing, Yu Wen. Naive Bayes classification algorithm based on cost sensitive for imbalanced data distribution[J]. Journal of Computer Research and Development, 2011, 48(Suppl Ⅰ): 387-390 (in Chinese)(蔣盛益, 謝照青, 余雯. 基于代價敏感的樸素貝葉斯不平衡數據分類研究[J]. 計算機研究與發展, 2011, 48(增刊Ⅰ): 387-390)[7]Bahnsen A C, Aouada D, Ottersten B. Example-dependent cost-sensitive decision trees[J]. Expert Systems with Applications, 2015, 42(19): 6609-6619[8]Ghazikhani A, Monsefi R, Yazdi H S. Online cost-sensitive neural network classifiers for non-stationary and imbalanced data streams[J]. Neural Computing & Applications, 2013, 23(5): 1283-1295[9]Fu Zhongliang. Real AdaBoost algorithm for multi-class and imbalanced classification problems[J]. Journal of Computer Research and Development, 2011, 48(12): 2326-2333 (in Chinese)(付忠良. 不平衡多分類問題的連續AdaBoost算法研究[J]. 計算機研究與發展, 2011, 48(12): 2326-2333)[10]Brefeld U, Geibel P, Wysotzki F. Support vector machines with example dependent costs[C]Proc of European Conf on Machine Learning. Berlin: Springer, 2003: 23-34[11]Raudys S, Raudys A. Pairwise costs in multiclass perceptrons[J]. IEEE Trans on Pattern Analysis and Machine Intelligence, 2010, 32(7): 1324-1328[12]Qi Z, Tian Y, Shi Y, et al. Cost-sensitive support vector machine for semi-supervised learning[J]. Procedia Computer Science, 2013, 18: 1684-1689[13]Zhou Zhihua. Large margin distribution learning[M]Artificial Neural Networks in Pattern Recognition. Berlin: Springer, 2014: 1-11

[14]Gao Wei, Zhou Zhihua. On the doubt about margin explanation of boosting[J]. Artificial Intelligence, 2013, 203:1-18[15]Zhang Teng, Zhou Zhihua. Large margin distribution machine[C]Proc of ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2013: 313-322[16]Cortes C, Vapnik V. Support-vector networks[J]. Machine Learning, 1995, 20(3): 273-297[17]Vapnik V. The Nature of Statistical Learning Theory[M]. Berlin: Springer, 2000[18]Scholkopf B, Smola A J. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond[M]. Cambridge, MA: MIT Press, 2001[19]Yuan G X, Ho C H, Lin C J. Recent advances of large-scale linear classification[J]. Proceedings of the IEEE, 2012, 100(9): 2584-2603[20]Hsieh C J, Chang K W, Lin C J, et al. A dual coordinate descent method for large-scale linear SVM[C]Proc of Int Conf on Machine Learning. New York: ACM, 2008: 408-415

Zhou Yuhang, born in 1991. Received his BSc degree in computer science and technology from Nanjing University, Nanjing, China, in 2015. MSc candidate in Nanjing University. Member of the LAMDA Group. His main research interests include machine learning and data mining.

Zhou Zhihua, born in 1973. Received his BSc, MSc and PhD degrees in computer science from Nanjing University, China, in 1996, 1998 and 2000, respectively. Professor and PhD supervisor. ACM distinguished scientist, IEEE fellow, IAPR fellow, IETIEE fellow, AAAI fellow and China Computer Federation fellow. His main research interests include artificial intelligence, machine learning, data mining, pattern recognition and multimedia information retrieval.

Cost-Sensitive Large Margin Distribution Machine

Zhou Yuhang and Zhou Zhihua

(NationalKeyLaboratoryforNovelSoftwareTechnology(NanjingUniversity),Nanjing210023)(CollaborativeInnovationCenterofNovelSoftwareTechnologyandIndustrialization,Nanjing210023)

In many real world applications, different types of misclassification often suffer from different losses, which can be described by costs. Cost-sensitive learning tries to minimize the total cost rather than minimize the error rate. During the past few years, many efforts have been devoted to cost-sensitive learning. The basic strategy for cost-sensitive learning is rescaling, which tries to rebalance the classes so that the influence of different classes is proportional to their cost, and it has been realized in different ways such as assigning different weights to training examples, resampling the training examples, moving the decision thresholds, etc. Moreover, researchers integrated cost-sensitivity into some specific methods, and proposed alternative embedded approaches such as CS-SVM. In this paper, we propose the CS-LDM (cost-sensitive large margin distribution machine) approach to tackle cost-sensitive learning problems. Rather than maximize the minimum margin like traditional support vector machines, CS-LDM tries to optimize the margin distribution and efficiently solve the optimization objective by the dual coordinate descent method, to achieve better generalization performance. Experiments on a series of data sets and cost settings exhibit the impressive performance of CS-LDM; in particular, CS-LDM is able to reduce 24% more average total cost than CS-SVM.

cost-sensitive learning; margin distribution; support vector machine (SVM); representer theorem; dual coordinate descent method

2015-06-08；

2015-09-16

國家自然科學基金項目(61333014,61321491)

周志華(zhouzh@lamda.nju.edu.cn)

TP181

This work was supported by the National Natural Science Foundation of China (61333014, 61321491).