矩陣型多類代價敏感分類器模型

孟 蕓， 王 喆（華東理工大學計算機科學與工程系，上海 200237）

矩陣型多類代價敏感分類器模型

孟 蕓， 王 喆
（華東理工大學計算機科學與工程系，上海 200237）

目前大部分分類器都是以分類正確率來衡量性能，這種評價標準都是基于理想情況下所有錯誤分類代價都是相同的。但實際生活中往往不同的錯誤分類會帶來不同的損失，因此代價敏感學習成為模式識別中一個熱點研究領域。本文將代價敏感思想與矩陣型學習機相結合，提出了一個矩陣型多類代價敏感分類器模型。通過與其他分類器在常用數據集上的對比實驗證明，該方法降低了錯誤分類代價，提高了少數類或代價高類別的分類正確率，并可以在有效次內收斂，是一個有效且實用的方法。

模式識別；代價敏感；分類器設計

分類器設計是機器學習和模式識別領域重要的一部分。目前大多數分類模型都側重于使用分類正確率來衡量一個算法的性能，并默認這種評價標準都是基于所有錯誤分類代價是相同的。但是實際生活中的分類問題，數據錯誤分類代價往往不相等［1-2］。比如，在門禁系統的家庭成員識別問題上，將一個家庭成員識別錯誤使其不能進入引起的代價遠遠小于將一個不屬于家庭成員的陌生人誤識別使其進入房屋帶來的損失。對于這類錯誤分類代價不同的情況，如在信用卡欺詐檢測、醫療、網絡入侵檢測等領域，僅使用傳統的代價不敏感分類器并不能達到很好的分類效果［3］。而代價敏感學習的目標就是通過最小化錯誤分類總代價做出最優決策，因此，將代價敏感思想引入到分類器設計中具有十分深遠的意義［4］。

本文提出了一種新型的代價敏感學習模型——矩陣型多類代價敏感分類器（Cs Mc Mat MHKS），實驗表明，該方法與矩陣型多類代價不敏感的Mc Mat MHKS分類器相比，有效地降低了錯誤分類總代價并提高了少數類的分類正確率。

1　代價敏感學習

1.1代價敏感研究現狀

代價敏感學習方法是機器學習中的一種新方法，不同于傳統分類方法盡可能降低錯誤分類率，它主要是將各類不同的誤分代價引進到分類決策中以降低錯誤分類的總體代價［3-5］。目前，代價敏感學習算法的研究主要集中在以下幾個方面：

（1）基于重采樣的方法，也叫重構訓練集的方法。根據代價矩陣改變原始樣本分布重構訓練集，再結合一種基于最小錯誤率的分類方法進行訓練并分類［6］。通過不同的采樣方法，如過采樣、欠采樣或者兩者結合的形式［7］將分布不平衡的訓練數據調整為均勻分布的數據。過采樣是通過隨機復制或者其他方式生成少數類樣本，改變訓練集樣本中的分布，達到樣本類別的均衡，也可以根據代價信息過采樣樣本。過采樣的缺點是會增加額外的信息或噪聲，不一定能達到一個較好的結果。欠采樣既也是改變訓練集眾數據分布使各類樣本達到平衡，與過采樣不同的是，它通過降低低代價樣本數目來達到目的，同時，這種方式會損失一部分可能攜帶重要信息的樣本，對分類造成不必要的影響。而混合采樣則是把兩者結合起來以求更佳效果的方法，實驗證明，混合采樣繼承了過采樣與欠采樣的優點，又盡量避免了它們的缺點，已被廣泛采用。

（2）基于對分類結果的后處理，即按照傳統學習方法學習一個分類模型，然后對分類結果按照貝葉斯風險理論進行調整，以達到損失最小。較為著名的MetaCost方法［8］是一個將普通分類器轉化為代價敏感分類器的最普遍方法，它不依賴于所使用的具體分類器，對分類算法不作改變，經過多次取樣，把訓練集分為多個子模型訓練多個分類器，綜合各個分類器給出的分類結果估計樣本的后驗概率，再計算錯誤分類總代價［9-10］，根據最小代價修改類標號。MetaCost方法主要有兩個方面的缺點：一是對訓練集進行重新標記，再利用數據集來反映代價敏感性的有效性還需進一步驗證［1］；二是不能準確地對后驗概率進行估計。

（3）直接構造一個代價敏感的學習模型或者修改已有的分類算法，將代價的影響嵌入到決策的過程［10-11］。最常用的方法有可以直接處理樣本權重的決策樹、代價敏感人工神經網絡和代價敏感支持向量機等［12-14］。如神經網絡，有多種方法可以使神經網絡轉化為代價敏感算法，如得到測試樣的后驗概率，再使用貝葉斯風險決策，或者改變輸出層每次迭代時的輸出，使其代價敏感等。文獻［15-16］用指數形式表示的極值問題替換用符號函數表示的錯誤分類代價極值問題，結合遞推得到了可以直接應用于多分類問題的代價敏感學習的AdaBoost算法。

1.2矩陣型多類分類模型

面向矩陣的修正Ho-Kashyap分類器（Mat MHKS）［17］是一種可以直接處理矩陣模式的分類器，目前這個方法僅基于兩類情況設計，在多分類問題上使用“一對一”策略實現，時間復雜度較大。矩陣型多類分類器Mc Mat MHKS是一種直接多類矩陣型分類器［18］，在實際的多類分類問題上，傳統的二元分類器將多類分類問題分解成多個兩類分類子問題，通過綜合各個子分類器的分類結果得出最終決策，而Mc Mat MHKS則是直接得出最后的分類結果，相比于傳統的兩類分類方法，直接法與矩陣化思想的結合，在保持了數據分類精度的同時也降低了分類的時間復雜度。

2　矩陣型多類代價敏感分類器Cs Mc Mat MHKS

本文中代價矩陣的設置采用常用的基于類別的代價敏感，即每一類樣本被錯誤分類所帶來的代價相等，而不同類別之間不相等［19-20］。假設C（i，j）為代價矩陣，行表示類別，列表示預測類別，Cij表示第i類樣本被錯誤分類為第j類樣本的代價。為了方便計算，對每一樣本采用以式（1）表示的這一類樣本被錯誤分類的代價，這一類的每個樣本被錯誤分類的代價相同［5，13，21］，即

Mc Mat MHKS的判別函數如下：

單純地把樣本代價嵌入判別函數使代價參與決策面偏移，經實驗證明結果會根據代價的設置不同而比較隨機。現設計加入樣本權重系數，其與樣本錯誤分類代價成反比，如式（3）所示。即當一類樣本被分錯的風險對總體分類結果影響較大時，可能會過擬合，我們試圖減小各樣本錯誤分類誤差在總體中的比重來均衡各樣本對分類結果的總體貢獻，以期獲得分類代價和推廣能力能達到一種平衡［1，5-6］。

根據公式以及代價矩陣為每一樣本設置權重系數，同一類別的樣本權重系數相同［22］。對于判別函數式（2），可以通過轉換為最小化總分類風險求得判別函數中權向量的最優解。

Cs Mc Mat MHKS的準則函數由經驗風險和結構風險兩部分組成。

其中加入權重系數ω后的經驗風險Remp計算如下：

正則化風險Rreg計算如下：

式中：r為正則化系數；S1和S2是兩個單位矩陣，S1=（d1＋1）Id1×d1，S2=（d2＋1）Id2×d2。

可以看出，當所有樣本錯誤分類代價相同時，由式（3）可知，Ci/Cj=1。同時各樣本權重系數比例一致，ωi=ωj，即當系數都為1時，判別函數式（2）就是代價不敏感的Mc Mat MHKS，因此本文方法也是對Mc Mat MHKS的擴展。

將式（5）、式（6）代入到式（4）可以得到

在分類器最終決策階段，假設一個訓練數據（Ai，yi），把它判為第j類，應當滿足式（10）。

Cs Mc Mat MHKS算法步驟如下：

（1）根據樣本每一類別樣本數目，設置代價矩陣C；根據式（3）設置樣本的權重系數ωi，同一類別樣本的權重系數相同。

3　實 驗

3.1實驗設置

實驗過程中，代價矩陣是自定義的，為了證明不同代價矩陣情況下算法的有效性，設置了兩種不同的代價矩陣進行實驗。本文采用的數據集來自UCI基準數據集［23］中常用的兩個平衡數據集Banana和Water，以及不平衡數據集Breast Cancer Wisconsin （BCW）、Ionosphere和Ecoli。表1示出了各數據集的具體相關信息，表2示出了具體的代價設置。

表1　數據集具體信息Table 1 Information of the datasets

實驗中設定數據集中的一半數據用于訓練，另一半用于測試。正則化系數來自集合｛10－3，10－2，10－1，1，10，102｝。對比算法來自同一分類器家族，分別是本文方法Cs Mc Mat MHKS、Cost-blind Mc Mat MHKS、面向矩陣的修正Ho-Kashyap分類器（Mat MHKS）和修正Ho-Kashyap分類器（MHKS）［17］。針對UCI數據形式，同時也將向量型樣本轉換成多個矩陣型數據并從中選擇最優的表示形式。例如BCW樣本維度為10，則轉化為矩陣形式有1×10，2×5，5×2和10×1共4種，其他數據集進行同樣處理。因數據集不同，每個對應的預設代價矩陣也不相同，遵循的基本規則是不平衡數據集中少數類樣本被錯誤分類代價高于多數類樣本代價，而平衡數據集中根據類別可隨機自定義。實驗過程中，采用10輪Monte Carlo交叉驗證（MCCV）［24］，即每一個參數重復10次實驗，最終求得平均值，以保證實驗的準確度。MCCV與一般的交叉驗證不同的是，每次循環它從整個數據集中無放回的選擇數據構建訓練集，剩余的做測試集，這樣能夠保證訓練測試集都是有變化的并且每個劃分不重復。MCCV能夠避免訓練規模過大，減少過擬合，因此，選用MCCV來驗證本文方法的穩定性和可信性。對于不平衡數據集，單純的分類正確率并不能很好地評估分類器性能，因此在不平衡數據集上采用了常用的G-means［25］作為評價標準。

表2　各數據集對應錯誤分類代價比例設置的代價矩陣（第1類/第2類/…/第n類）Table 2 Settings of cost matrix on the datasets（Costclass1/ Costclass2/…/Costclass n）

其中：Ri表示每一類的分類正確率；k表示類別總數。

3.2實驗結果

表3和表4示出了代價敏感Cs Mc Mat MHKS （Cs）、代價不敏感Cost-blind Mc Mat MHKS（Cb）、Mat MHKS和MHKS在4個數據集Banana、Water、BCW和Ionosphere上的實驗結果，評價指標包括分類總代價SumCost、G-means、分類正確率，并列出了達到最優結果時對應的矩陣表示形式和正則化系數r的值，其中分類總代價最低的算法數據用黑體表示，G-means最高的值以下劃線標出。圖1示出了Cs與Cb在Ecoli數據集上各類別的分類正確率對比結果。

本文在Banana和Ecoli數據集上對式（7）進行了收斂性分析，收斂曲線如圖2所示。圖2中橫坐標表示迭代次數，縱坐標表示目標函數的對數值。

表3　第1種代價矩陣下Cs，Cb，Mat MHKS，MHKS在4個數據集上的實驗結果Table 3 Experimental results of Cs，Cb，Mat MHKS and MHKS on Banana，Water，BCW and Ionosphere

表4　第2種代價矩陣下Cs，Cb，Mat MHKS，MHKS在4個數據集上的實驗結果Table 4 Experimental results of Cs，Cb，Mat MHKS and MHKS on Banana，Water，BCW and Ionosphere

圖1　Cs和Cb在Ecoli上每一類對應的分類正確率Fig.1 Accuracy of Cs Mc Mat MHKS and Cost-blind Mc Mat MHKS on Ecoli classes

圖2　Cs在Banana和Ecoli上的收斂曲線Fig.2 Convergence analysis of Cs Mc Mat MHKS on Banana and Ecoli

3.3實驗結果分析

從表3和表4中可以看出：

（1）本文方法在大部分數據集上與代價不敏感的Mc Mat MHKS、Mat MHKS和MHKS相比達到了最小錯誤分類總代價，尤其是當樣本類別之間的代價比例差別變大時，效果更為明顯。例如，Banana數據集在第1種代價比為1/2時，本文方法與最大錯誤分類代價之差為10.80，而在第2種代價比為1/5時，本文方法與最大錯誤分類代價之差為54。實驗數據充分證明了代價敏感方法與其他方法相比，尤其是與代價不敏感原型相比，在降低分類總代價方面的有效性。

（2）針對不平衡數據集BCW和Ionosphere的G-means評價指標，本文方法明顯好于Mc Mat MHKS，并且優于或者與Mat MHKS、MHKS相當。例如表4中，在Ionosphere上的G-means值約為Mc Mat MHKS的兩倍。G-means值的提高表明代價敏感模型在少數類或者代價高的類別上的分類正確率有提升。

（3）從實驗數據上看，矩陣形式不盡相同。有的在向量型數據上表現良好，有的在矩陣型數據上表現良好。這充分說明，針對最原始的向量型數據進行不同的矩陣變換是十分必要的。

（4）從圖1中可以看到，Cs Mc Mat MHKS在Ecoli除第7、8類因僅有一個測試樣本而數量太少影響不大外，其他多數類與少數類上的分類正確率均有所提高。

（5）從圖2中可以看到本文方法均在有效次內收斂，證明了該算法具有較好的學習效率。

4　結束語

針對大多數實際問題中不同的分類會帶來不同的損失，本文將代價敏感思想和相較于傳統向量型學習機有更優性能的矩陣型學習機相結合，提出了矩陣型多類代價敏感分類器Cs Mc Mat MHKS。與代價不敏感的原型以及同一家族的分類器在數據集上的對比實驗證明，本文方法可以有效降低錯誤分類總代價并提高分類器在少數類或者代價較高類別上的分類正確率，且可以快速收斂。實驗證明，本文方法有著較優的分類性能，是一個有效且實用的模型。

［1］ ZHANG Yin，ZHOU Zhihua.Cost-sensitive face recognition ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（10）：1758-1769.

［2］ 葉志飛，文益民，呂寶糧.不平衡分類問題研究綜述［J］.智能系統學報，2009，4（2）：148-156.

［3］ 楊明，尹軍梅，吉根林.不平衡數據分類方法綜述［J］.南京師范大學學報（工程技術版），2009，8（4）：7-12.

［4］ LI YUFENG，KWOK JAMES T，ZHOU Zhihua.Costsensitive semi-supervised support vector machine［C］// Proceedings of the National Conference on Artificial Intelligence.Atlanta，Georgia，USA：DBLP，2010：500-505.

［5］ SAHARE M，GUPTA H.A review of multi-class classification for imbalanced data［J］.International Journal of Advanced Computer Research，2012，2（3）：160-164.

［6］ 谷瓊，袁磊，寧彬，等.一種基于重取樣的代價敏感學習算法［J］.計算機工程與科學，2011，33（9）：130-135.

［7］ 程險峰，李軍，李雄飛.一種基于欠采樣的不平衡數據分類算法［J］.計算機工程，2011，37（13）：147-149.

［8］ DOMINGOS P.Metacost：A general method for making classifiers cost-sensitive［C］//Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.USA：ACM，1999：155-164.

［9］ 凌曉峰，SHENG VICTOR S.代價敏感分離器的比較研究［J］.計算機學報，2007，30（8）：1203-1211.

［10］ 閆明松，周志華.代價敏感分類算法的實驗比較［J］.模式識別與人工智能，2006，18（5）：628-635.

［11］ 王瑞.針對類別不平衡和代價敏感分類問題的特征選擇和分類算法［D］.合肥：中國科學技術大學，2013.

［12］ 程學云，吉根林，凌霄漢.基于SVM的多類代價敏感學習及其應用［J］.南京師范大學學報（工程技術版），2007，6（4）：79-82.

［13］ 李剛.代價敏感的支持向量機監督學習研究［D］.南京：南京師范大學，2007.

［14］ ZHOU Zhihua，ZHANG Minling，HUANG Shengjun，et al. Multi-instance multi-label learning［J］.Artificial Intelligence，2012，176（1）：2291-2320.

［15］ 付忠良.多分類問題代價敏感AdaBoost算法［J］.自動化學報，2011，37（8）：973-983.

［16］ 付忠良.多標簽代價敏感分類集成學習算法［J］.自動化學報，2014，40（6）：1075-1085.

［17］ CHEN Songcan，WANG Zhe，TIAN Yongjun.Matrixpattern-oriented Ho-Kashyap classifier with regularization learning［J］.Pattern Recognition，2005，40（5）：1533-1543.

［18］ WANG Zhe，MENG Yun，ZHU Yujin，et al.Mc Mat MHKS：A direct multi-class matrixized learning machine［J］. Knowledge-Based Systems，2015，88：184-194.

［19］ 李勇，劉戰東，張海軍.不平衡數據的集成分類算法綜述［J］.計算機應用研究，2014，31（5）：1287-1291.

［20］ RAUDYS S，RAUDYS A.Pairwise costs in multiclass perceptrons［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（7）：1324-1328.

［21］ LU Jiwen，ZHOU Xiuzhuang，TAN Yap-Peng，et al.Costsensitive semi-supervised discriminant analysis for face recognition［J］.IEEE Transactions on Information Forensics and Security，2012，7（3）：944-953.

［22］ TING Kaiming.An instance-weighting method to induce costsensitive trees［J］.IEEE Transactions on Knowledge and Data Engineering，2002，14（3）：659-665.

［23］ ASUNCION A，NEWMAN D.UCI machine learning repository［D］.California：University of California Irvine of Information and Computer，2007：148-156.

［24］ XU Qingsong，LIANG Yizeng.Monte Carlo cross validation ［J］.Chemometrics and Intelligent Laboratory Systems，2001，56（1）：1-11.

［25］ WANG Shuo，YAO Xin.Multiclass imbalance problems：Analysis and potential solutions［J］.IEEE Transactions on Systems，Man，and Cybernetics，Part B：Cybernetics，2012，42 （4）：1119-1130.

Matrixized Multi-class Cost Sensitive Classification Mode

MENG Yun， WANG Zhe
（Department of Computer Science and Engineering，East China University of Science and Technology，Shanghai 200237，China）

At present，most of the classifiers are evaluated by classification accuracy，which assumes that all the misclassification costs are the same.Actually，different misclassification may bring different loss.Therefore，the cost sensitive learning has been becoming a hot research area in pattern recognition.By combining the cost sensitive and matrixized learning thoughts，this paper proposes a matrixized multi-class cost sensitive classification mode.The experimental results on the data show that the proposed method can reduce the classification costs and improve the classification accuracy of the minority or higher cost classes. Meanwhile，the proposed method has a better convergence，which illustrates the effectiveness and practice of the proposed method.

pattern recognition；cost sensitive；classifier design

TP391

A

1006-3080（2016）01-0119-06 DOI：10.14135/j.cnki.1006-3080.2016.01.019

2015-05-07

國家自然科學基金面上項目（61272198）；上海市教育委員會科研創新項目（14ZZ054）；中央高校基本科研業務費專項資金

孟 蕓（1990-），女，河北保定人，碩士生，研究方向為模式識別。E-mail：mengyun_aijia@126.com

王 喆，E-mail：wangzhe@ecust.edu.cn