基于改進的代價敏感決策樹的網(wǎng)絡(luò)貸款分類

郭冰楠 吳廣潮

摘 要：在網(wǎng)絡(luò)貸款用戶數(shù)據(jù)集中，貸款成功和貸款失敗的用戶數(shù)量存在著嚴重的不平衡，傳統(tǒng)的機器學(xué)習(xí)算法在解決該類問題時注重整體分類正確率，導(dǎo)致貸款成功用戶的預(yù)測精度較低。針對此問題，

在代價敏感決策樹敏感函數(shù)的計算中加入類分布，

以減弱正負樣本數(shù)量對誤分類代價的影響，構(gòu)建改進的代價敏感決策樹;以該決策樹作為基分類器并以分類準確度作為衡量標準選擇表現(xiàn)較好的基分類器，將它們與最后階段生成的分類器集成得到最終的分類器。實驗結(jié)果表明，與已有的常用于解決此類問題的算法（如MetaCost算法、代價敏感決策樹、AdaCost算法等）相比，改進的代價敏感決策樹對網(wǎng)絡(luò)貸款用戶分類可以降低總體的誤分類錯誤率，具有更強的泛化能力。

關(guān)鍵詞：不平衡;代價敏感;網(wǎng)絡(luò)貸款;集成學(xué)習(xí);決策樹

中圖分類號：TP181

文獻標志碼：A

Abstract：? In the online loan user data set， there is a serious imbalance between the number of successful and failed loan users. The traditional machine learning algorithm pays attention to the overall classification accuracy when solving such problems， which leads to lower prediction accuracy of successful loan users. In order to solve this problem， the class distribution was added to the calculation of cost-sensitive decision tree sensitivity function， in order to weaken the impact of positive and negative samples on the misclassification cost， and an improvedcost-sensitive decision treebased on ID3 （ID3cs）was constructed. With the improved cost-sensitive decision tree as the base classifier and the classification accuracy as the criterion， the base classifiers with better performance were selected and integrated with the classifier generated in the last stage to obtain the final classifier. Experimental results show that compared with the existing algorithms to solve such problems （such as MetaCost algorithm， cost-sensitive decision tree， AdaCost algorithm）， the improved cost-sensitive decision tree can reduce the overall misclassification rate of online loan users and has stronger generalization ability.Key words： imbalance; cost-sensitive; online loan; integrated learning; decision tree

0 引言

隨著互聯(lián)網(wǎng)金融市場的不斷增長，網(wǎng)絡(luò)貸款也得到了如火如荼的發(fā)展[1-2]。本文以某網(wǎng)絡(luò)貸款征信服務(wù)公司提供的真實數(shù)據(jù)為背景，利用機器學(xué)習(xí)中的分類方法建立分類模型來識別可以給予貸款的用戶，從而減少后續(xù)人工審核篩選用戶的工作量，降低高違約風(fēng)險用戶帶來的損失。

對于本文研究的網(wǎng)絡(luò)貸款用戶分類而言，貸款獲批的人數(shù)較少，屬于小概率事件。對于這樣的小概率事件，主要存在以下問題：一是貸款成功的用戶不容易檢測到;二是將貸款成功的用戶預(yù)測為貸款失敗，比將貸款不合格的用戶預(yù)測為貸款成功，所付出的代價更大。而傳統(tǒng)的分類方法對于這樣的分類問題不具有良好的性能。

在現(xiàn)實的分類場景中，這樣的問題廣泛存在，例如醫(yī)療診斷、信用卡欺詐檢測、廣告點擊率預(yù)測等[3]。因此，基于代價敏感的學(xué)習(xí)成了機器學(xué)習(xí)中的一個熱門研究方向。

目前對于代價敏感學(xué)習(xí)的研究大致可以分為以下幾個方面：1）對數(shù)據(jù)集采樣的代價敏感學(xué)習(xí)，通過改變原始數(shù)據(jù)集的分布，訓(xùn)練分類器得到具有代價敏感性的模型。在采樣的過程中主要依據(jù)代價因子，插入或刪除部分樣本來調(diào)整數(shù)據(jù)集的分布，例如隨機欠采樣[4]、隨機過采樣[5]、合成少數(shù)類過采樣技術(shù)（Synthetic Minority Oversampling Technique， SMOTE）[6]等方法;2）在學(xué)習(xí)過程中引入分類代價，使得生成的分類器給予誤分類代價更高的類別更多的關(guān)注，使其更容易被正確分類，針對不同的分類方法提出了不同的代價敏感模型，如Drummond等[7]提出的代價敏感決策樹;3）對分類結(jié)果的處理，主要包括決策閾值的修改以及對分類器的集成，如AdaCost算法[8]、Meta-Cost算法[9]等。文獻[4-6]中提出的隨機欠采樣、隨機過采樣、合成少數(shù)類過采樣（SMOTE）方法，會改變數(shù)據(jù)集的樣本分布，影響分類器的性能。文獻[7]提出的代價敏感決策樹（cost-sensitive decision tree based on ID3， ID3cs）算法在分類過程中加入了誤分類代價，使決策樹在選擇分裂屬性時，選擇能使誤分類代價下降最快的。本文在文獻[7]算法的基礎(chǔ)上，引入了樣本的類分布，考慮在分類節(jié)點上樣本分布對分類代價的影響，以此作為選擇分裂屬性的依據(jù)，構(gòu)造決策樹;進而在形成的決策樹的基礎(chǔ)上進行分類器集成，以此得到最終的代價敏感決策樹。

1 相關(guān)工作

1.1 機器學(xué)習(xí)中的代價敏感學(xué)習(xí)

傳統(tǒng)的分類算法一般基于分類代價相等的假設(shè)，目標是最小化分類錯誤率，而代價敏感學(xué)習(xí)的目標是最小化總期望的誤分類代價，也就是說代價敏感學(xué)習(xí)是在給定不同類別的誤分類代價后，使用訓(xùn)練集樣本學(xué)習(xí)得到一個分類器，使其在測試集上預(yù)測類別時，具有盡量小的總期望誤分類代價[10]。

代價敏感學(xué)習(xí)中一般使用代價矩陣[11]（見表1）表示分類器的誤分類代價，其中cij表示把第i類誤分為第j類所造成的損失。

1.2 代價敏感決策樹

在文獻[13]中，提出基于ID3決策樹的代價敏感決策樹ID3cs算法，主要思想是依據(jù)不同類別具有不同的誤分類代價，在損失函數(shù)中加入了誤分類代價，分裂屬性的選擇準則是使誤分類代價下降最快的屬性。具體描述如下：

對于一個二分類問題，數(shù)據(jù)集S包含特征Aj（j=1，2，…，n），對于每一個類別特征Aj，都含有m個不同的值A(chǔ)ji（i=1，2，…，m）。在Aj處的誤分類代價為：

其中： p（i）表示分支i的比例;C（i）是分支i的代價。對非葉子節(jié)點i，它的代價是所有分支代價的加權(quán)和。對于葉子節(jié)點i，它的代價C（i）可以表示為：

其中： p（Pnodei）=PSi表示正樣本在nodei處比例，Si表示在nodei處樣本的總數(shù)目; p（Nnodei）=NSi表示負樣本在nodei處比例;CP是在葉子節(jié)點nodei處正樣本（貸款成功的用戶）的代價;CN是在葉子節(jié)點nodei處負樣本（貸款失敗的用戶）的代價。決策樹的目標是最小化葉子節(jié)點{CP，CN}處的總代價。換句話說，如果CP≥CN，則葉子節(jié)點被標記為正;否則為負。

2.1 加入類分布的代價敏感決策樹

受到C4.5算法的影響，以及文獻[14]中提到類分布會影響到分裂節(jié)點的選擇，因此為減弱正負類樣本數(shù)量對誤分類代價的影響，本文在代價敏感函數(shù)的計算中加入類分布，代價敏感函數(shù)CP、CN的計算方法修改為：

ID3決策樹算法使用準確率作為剪枝的評判準則。在算法IID3cs中，樹的生成和剪枝都是基于新定義的代價函數(shù)式（9）、（10），即若刪除該某分支后，誤分類代價減小，則進行剪枝操作;反之亦然。

2.2 代價敏感決策樹的集成文獻[13]中針對單一模型的不穩(wěn)定性，提出對基分類器集成的思想，本文在對模型集成的過程中，采用的集成策略大致過程如下：

1）從原數(shù)據(jù)集中有放回地重采樣獲得L個不同的子訓(xùn)練集，以IID3cs作為基分類器進行訓(xùn)練，得到不同的、具有差異性的L個分類器[16]，并計算這L個分類器的AUC值。

2）計算訓(xùn)練集中每個樣本屬于每個類別的概率和期望代價，以期望代價最小的準則將樣本重標記。

3）運用IID3cs算法訓(xùn)練重標記的數(shù)據(jù)集，得到新的分類器M。

4）選擇AUC值較高的幾個基分類器（在本文選擇AUC高于0.6的基分類器）與模型M進行加權(quán)，權(quán)重計算方式如式（11）所示，得到最終的分類器。將該算法稱為IID3cs_Bagging。

其中第k個分類器的AUC值記為AUCk，權(quán)重為wk：

其中：l代表基分類器中AUC值超過0.6的基分類器個數(shù);AUCM表示分類器M的AUC值;k=1，2，…，l，M。

IID3cs_Bagging算法可描述為：

從圖2中可以看到，雖然不同算法的ROC曲線出現(xiàn)了交叉，但是IID3cs_Bagging算法的ROC曲線位于最左上角，完全“包住”了其他算法的ROC曲線，說明在網(wǎng)絡(luò)貸款用戶分類數(shù)據(jù)集中該算法優(yōu)于其他算法;ID3cs_Bagging算法和MetaCost算法的ROC曲線出現(xiàn)了交叉，交叉點在fpr≈0.28的位置，該點之前ID3cs_Bagging算法優(yōu)于MetaCost算法，但之后MetaCost優(yōu)于ID3cs_Bagging算法，進一步說明單一的代價敏感決策樹在一定情況下已具有一定優(yōu)勢;IID3cs和ID3cs出現(xiàn)交叉，根據(jù)文獻[15]提到，此時應(yīng)比較兩曲線下的面積，即AUC值的大小，根據(jù)表3，IID3cs、ID3cs算法的AUC值分別為0.684、0.629，IID3cs算法優(yōu)于ID3cs算法。因此，在網(wǎng)絡(luò)貸款用戶分類數(shù)據(jù)集上，代價敏感決策樹，尤其是集成后的呈現(xiàn)出明顯的優(yōu)勢，說明了改進的IID3cs_Bagging算法的有效性。

從時間效率上來說，雖然在代價敏感算法中加入了代價矩陣的計算，但是它的運行效率并沒有比ID3cs、ID3cs_Bagging以及MetaCost算法明顯降低，因此從時間效率上分析，IID3cs以及IID3cs_Bagging算法也有一定的優(yōu)越性。

3.3.3 ID3cs_Bagging中權(quán)重公式的選擇

在2.1節(jié)中提出在最后由基分類器組成最后的分類器時，是先計算出各分類器的AUC值之后按照式（11）計算出各個基分類器的權(quán)重，進而合成最后的分類器。在轉(zhuǎn)化中常用的轉(zhuǎn)化方式主要有以下幾種：

從表4和圖3可以看出：在網(wǎng)絡(luò)貸款用戶分類數(shù)據(jù)集中，本文所采用的權(quán)重轉(zhuǎn)換方式相對其他方式而言，具有較大優(yōu)勢，表現(xiàn)效果較好。

對于該數(shù)據(jù)集，集成分類器的大小為6，各分類器的權(quán)重為9.8%、10.3%、13.2%、14.9%、20.1%、31.7%。

以上實驗結(jié)即使表明，改進的代價敏感決策樹IID3cs_Bagging算法相對其他已有的代價敏感學(xué)習(xí)而言，在網(wǎng)絡(luò)貸款用戶分類數(shù)據(jù)集上具有更好的效果，而且IID3cs_Bagging算法的時間效率并不差于已有的算法。因此，在網(wǎng)絡(luò)貸款用戶分析中，本文所提代價敏感決策樹IID3cs_Bagging算法具有較強的魯棒性和泛化能力。

4 結(jié)語

本文通過對已有代價敏感決策樹ID3cs算法的研究，考慮到正負類樣本數(shù)量對期望誤分類總代價的影響，在代價的計算過程中引入了樣本的類別分布，即IID3cs算法。為進一步提高分類器的性能，以IID3cs算法作為基分類器進行集成。在網(wǎng)絡(luò)貸款分類數(shù)據(jù)集的應(yīng)用中，該算法與已有的常用于處理類別不平衡、代價敏感的算法相比，具有較好的表現(xiàn)，在最小化誤分類總代價的同時，提高了分類準確率，尤其是少數(shù)類樣本的分類準確率。

代價敏感學(xué)習(xí)仍然未能解決過擬合的問題，而且在考慮代價的過程中只是分析了誤分代價，在未來的研究中，將會在這些方面進行更多的嘗試。

參考文獻（References）

[1] GUO Y， ZHOU W， LUO C， et al. Instance-based credit risk assessment for investment decisions in P2P lending[J]. European Journal of Operational Research， 2016， 249（2）： 417-426.

[2] ANGELINI E， CAMBA-MENDEZ G， GIANNONE D， et al. Short term forecasts of euro area GDP growth[J]. The Econometrics Journal， 2011， 14（1）： 25-44.

[3] ZHOU Z， LIU X. Training cost-sensitive neural networks with methods addressing the class imbalance problem[J]. IEEE Transactions on Knowledge and Data Engineering， 2006， 18（1）： 63-77.

[4] LIU A， GHOSH J， MARTIN C E. Generative oversampling for mining imbalanced datasets[EB/OL]. [2018-12-10]. http：//wwwmath1.uni-muenster.de/u/lammers/EDU/ws07/Softcomputing/Literatur/4-DMI5467.pdf.

[5] JAPKOWICZ N. Concept-learning in the presence of between-class and within-class imbalances[C]// Proceedings of the 14th Biennial Conference of the Canadian Society for Computational Studies of Intelligence， LNCS 2056. Berlin： Springer， 2001： 67-77.

[6] CHAWLA N V， BOWYER K W， HALL L O， et al. SMOTE： synthetic minority over-sampling technique[J]. Journal of Artificial Intelligence Research， 2002， 16： 321-357.

[7] DRUMMOND C， HOLTE R C. Exploiting the cost （in） sensitivity of decision tree splitting criteria[C]// Proceedings of the 17th International Conference on Machine Learning. San Francisco： Morgan Kaufmann， 2000： 239-246.

[8] FAN W， STOLFO S J， ZHANG J， et al. AdaCost： misclassification cost-sensitive boosting[C]// Proceedings of the 16th International Conference on Machine Learning. San Francisco， CA： Morgan Kaufmann， 1999： 97-105.

[9] DOMINGOS P. MetaCost： a general method for making classifiers cost-sensitive[C]// Proceedings of the 5th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 1999： 155-164.

[10] 周宇航， 周志華. 價敏感大間隔分布學(xué)習(xí)機[J]. 計算機研究與發(fā)展， 2016， 53（9）： 1964-1970. （ZHOU Y H， ZHOU Z H. Cost-sensitive large margin distribution machine[J]. Journal of Computer Research and Development， 2016， 53（9）： 1964-1970.）

[11] 李航. 統(tǒng)計學(xué)習(xí)方法[M]. 北京： 清華大學(xué)出版社， 2012： 22-24. （LI H. Statistical Learning Methods[M]. Beijing： Tsinghua University Press， 2012： 22-24.）

[12] BANBURA M， MODUGNO M. Maximum likelihood estimation of factor models on datasets with arbitrary pattern of missing data[J]. Journal of Applied Econometrics， 2014， 29（1）： 133-160.

[13] 鄒鵬， 莫佳卉， 江亦華， 等.基于代價敏感決策樹的客戶價值細分[J]. 管理科學(xué)， 2011， 24（2）： 20-29. （ZOU P， MO J H， KIANG M， et al. A cost-sensitive decision tree learning model — an application to customer-value based segmentation[J]. Journal of Management Science， 2011， 24（2）： 20-29.）

[14] 李秋潔， 趙雅琴， 顧洲. 代價敏感學(xué)習(xí)中的損失函數(shù)設(shè)計[J]. 控制理論與應(yīng)用， 2015， 32（5）： 689-694. （LI Q J， ZHAO Y Q， GU Z. Design of loss function for cost-sensitive learning[J]. Control Theory & Applications， 2015， 32（5）： 689-694.）

[15] 周志華. 機器學(xué)習(xí)[M]. 北京： 清華大學(xué)出版社， 2016： 86-128. （ZHOU Z H. Machine Learning[M]. Beijing： Tsinghua University Press， 2016： 86-128.）

[16] 付忠良. 不平衡多分類問題的連續(xù)AdaBoost算法研究[J]. 計算機研究與發(fā)展， 2011， 48（12）： 2326-2333. （FU Z L. Real AdaBoost algorithm for multi-class and imbalanced classification problems[J]. Journal of Computer Research and Development， 2011， 48（12）： 2326-2333.）