加權投票采樣學習在用戶信用評級中的應用

陳念，唐振民

1.池州學院數學與計算機科學系，安徽池州 247000

2.南京理工大學計算機科學與工程學院，南京 210094

加權投票采樣學習在用戶信用評級中的應用

陳念1，2，唐振民2

1.池州學院數學與計算機科學系，安徽池州 247000

2.南京理工大學計算機科學與工程學院，南京 210094

以委員會投票查詢算法為基礎，提出在采樣過程中動態修正分類器成員權值的加權投票方法。在對無標簽樣本標注價值評估中，該方法能夠強化高精度分類器成員的查詢貢獻，降低高誤差成員的投票影響，減少機器訓練過程中的標注學習次數。通過在UCI的Statlog（Australian Credit Approval）數據集上對用戶信用度級別進行識別，并比較于其他采樣方法，證明該方法能夠用較小的采樣標注代價獲取穩定的泛化精度。

主動學習；采樣查詢；加權投票；熵；標注門檻

金融用戶信用評級是一種為金融組織或企業提供決策參考的社會服務，它揭示了受評對象按合同履行金融義務的能力、意愿及違約風險的大小。由于用戶數量龐大，信用等級完全用人工方式評價較為困難，且在批量標注前提下精準度得不到保證，機器標注已成必然，如何有效利用無標簽信息增強機器學習效果成為研究的要點。近年發展起來的主動學習（Active Learning）方法，在已標注樣本數量不足，分類器得不到充分訓練的條件下，通過選取一些無標簽樣本交由專家系統或人工進行標注，以此獲得訓練用數據。主動學習方式下，學習過程不再是被動接受由用戶提供的數據[1]，而是自主選擇一些包含信息量大，針對性強的高價值樣本經過標注后再進行學習。

主動學習的數據場景常見的有基于池的和基于流的兩種，前者假設有兩個信息池的存在：能提供前期訓練的有標簽樣本池，和擁有大量可供選擇樣本的無標簽池；后者中無標簽樣本則依照時間節點順序到達。池場景機器學習的研究成果已在文本分類[2]、信息提取[3]、視頻分類與檢索[4]等諸多領域得到有效應用，基于流場景的研究也取得了較大進展，如在不良用戶評論過濾[5]、網頁廣告點擊預測[6]等網絡問題的處理上。已有的無標簽樣本評價采集方法主要分三種[7]：一是基于不確定性的采樣，即選擇類別劃分不確定性大的樣本標注后加入訓練集，如邊界采樣（Margin sampling）[8]，最小-最大視圖采樣（QUIRE）[9]等。二是基于版本空間縮減的采樣，委員會投票方法QBC[10]就是其中最具代表性的算法，如某個無標簽樣本在經過多個分類器投票后，熵值較大，那么它應標注后去訓練分類器。在此基礎上改進的Boosting_QBC[11]和Bagging_QBC[12]算法都能很好適應復雜的數據環境和分類模型。三是基于誤差縮減的采樣，它可以有效避免野值點對分類器的干擾，如Fisher信息法等。

本文的討論是基于樣本池場景和委員會投票QBC算法之上的。首先用Bagging算法生成多個投票弱分類器（委員會），再通過對各分類器加權的方法調整不同成員投票對樣本熵值的影響。在采集標注到一個訓練用樣本后，進行類別預測投票，并依據各分類器的投票誤差修正相應權值，運用到下一輪樣本評價中。該方法可以更有效收集到高信息量無標簽樣本用于訓練，減少機器學習過程中與外部的交互次數，節約標注成本，同時不會影響到分類器精度。通過在UCI的Statlog（Australian Credit Approval）集上對用戶信用度等級進行仿真識別，證明了該方法的有效性。

1 委員會投票算法

1.1 投票委員會的產生

設樣本空間X被分成有標簽集L={＜xi，yk＞}和無標簽集UL={＜xj＞}，其中yk∈Y，Y為類標識空間。Bagging算法每輪用隨機方式在L中抽取m個樣本構成子集SL，用SL訓練分類器f獲得模型參數ω，其中若干樣本可以重復出現在不同輪次的訓練子集中，經過p輪訓練后即可產生p個參數，如圖1。

圖1 用Bagging方法產生投票委員會

由這些參數對應的分類器組成的集合稱為委員會committee，其間每位成員對UL中的樣本都能預測其類別，即=f(ω，x)，由于單個ω是部分樣本訓練產生的，因此它對應的分類器的判斷能力是較弱的。投票算法的思路在于：對xj∈UL，統計所有成員對它的投票結果V(y，xj)，樣本最終劃分到得票數最多的類，即

這種將多個弱分類器集成的做法，可以有效克服單個分類器預測的不足，但它并未考慮委員會成員間的精度差異，沒有合理利用分類器樣本預測過程中的經驗，導致在不確定性高的樣本投票上缺乏參考性，需要更多依賴外部決策。

1.2 熵度量的引入

熵值是度量不確定性的有效指標，投票結果用熵值反映更利于理解和處理，熵值越大說明樣本類別歸屬的不確定性越高，需要高一級的判別系統（專家系統或人工）介入。Argamon提出了投票熵的概念[13]。

其中，|Y|為類別數，V(y，xj)是s個委員會成員對無標簽樣本xj的投票結果，ε為微調量，當某類得票數為0時，防止lb0情況的出現。投票熵是根據“硬性”投票方式進行計算的，即對樣本的類別投票只有屬于（1）或不屬于（0）兩種可能。相對熵，又稱KL散度，是另一種不確定性度量形式，樣本的類別劃分用概率的形式描述。

相對熵度量的是樣本xj屬于某一類yi的概率，與屬于各類平均概率間的差異，體現了樣本歸類的概率相對性。

2 基于投票查詢的采樣

基于委員會投票的采樣方法（Query By Committee）由Seung和Freund等人提出[14-15]，是一種基于版本空間縮減的算法，通過在無標簽樣本池UL中采集樣本，在委員會投票之后，計算其熵值，將熵值是否超過標注門檻作為標注學習與否的依據。圖2給出了流程簡圖。

圖2 投票采樣方法流程簡圖

2.1 加權投票采樣方法

在1.1節中提到，用Bagging方法產生的投票委員會，其成員對任一無標簽樣本的熵值影響是相同的。但實際情況是：對UL中的樣本，委員會部分成員的預測準確率較高，而另外一些則相對較低，若這些前期經驗沒有得到合理利用，對后續一些分類難度偏高的樣本，不能由投票方式直接決定其類別，需要更多次數的專家或人工標注，這無疑增加了學習的成本。本文通過對委員會成員的投票加權的方式，來調整不同精度的弱分類器對熵值的影響，并在后續的學習中動態修正權值，以達到降低主動學習中與外部交互次數的目標。

用委員會F={f(ω1)，f(ω2)，…，f(ωp)}對有標簽測試集L中的n樣本分別進行類別投票，計算預測誤差：

式中，yk為樣本xi的真實標簽。依據誤差e給對應的分類器賦予權值wj：

微調常量ε的作用同樣是為防止誤差為0時，除0情況的出現。為使wj＞0，則區別于一般委員會，加權分類器成員誤差需滿足據此，委員會對樣本xi屬于某類y的投票結果可表示為：

用式（7）的投票結果計算樣本的熵值，更能發揮高精度分類器在無標簽樣本類別判定中的作用，使一部分樣本的歸類由機器自行解決，而不需要專家系統或人工的介入。若投票熵值仍然超過預先設定的閾值θ，則該樣本需進行類別標注，作為學習樣本加入訓練集L。

2.2 投票權值的更新

在采集標注一個新樣本后，委員會中所有的成員要對它進行學習，學習的方式仍然是對該新樣本進行類別預測。預測結果同樣會出現正確和錯誤兩種情況，據此進一步調整委員會成員的權重，來獲得泛化性能更強的分類器集合。本文提出一種權值調整方法，設分類器f(ωj)在時刻t的權值為，則對一個新樣本xi的類標預測后，其權值調整為，令

3 實驗與結果分析

實驗用隨機標注（Random Choice）、委員會投票標注（Query By Committee）及加權委員會投票標注（weighted QBC）三種采樣算法采集到的樣本進行分類器訓練，對比采樣標注數量與訓練精度，證明加權投票方法的高效性。用Matlab的SVM工具在UCI的Statlog（Australian Credit Approval）數據集上進行仿真。該數據集收集了用戶信用卡的相關使用情況數據，并依此對持卡用戶做出信用評級以作為信貸審批的依據，用戶被分成兩類：+（信譽度較好）和-（信譽度較差）。對多級信用評定的多類分類問題，可將其分解成若干個二分類問題加以解決。

實驗將數據集按9∶1的比例隨機分離出訓練樣本和測試樣本，做10重交叉驗證。在訓練集中有標簽池和無標簽池的樣本比例按1∶5進行設置。表1列出了實驗數據組成及配置情況。

3.1 不同采樣方法效率比較

圖3中反應出三種方法的共同點在于：隨著新采集樣本的加入，分類器的訓練效果都在不斷增強，精度呈現上升趨勢。隨機方法在無標簽池中的采樣具有盲目性，獲取樣本的訓練效果在三種算法中是最差的。QBC只選擇投票熵值超過設定門檻θ的樣本加入訓練集，同等采集規模下其泛化精度是優于隨機采樣的，如圖3在num=60時，兩者精度差值接近5%。Weighted QBC方法在采樣過程中，區分了不同精度分類器對樣本熵值的影響，讓更高信息量的樣本通過標注方式進入訓練集，因而能用相同的訓練代價獲得更高的識別準確率。

表1 實驗數據組成及配置情況

表2 三種采樣算法效率比較（%）

表3 不同委員會成員數對應的投票熵

圖3 不同采樣方法對應的精度比較

表2給出了三種算法在不同采樣規模下的效率對比，其中Δnum=20。

表2中數據反映出訓練樣本采集的后期效率要明顯低于前階段，識別率提升幅度呈現出明顯的放緩。三種方法中隨機采樣不加選擇地采集標注樣本，部分樣本采集對分類器精度的提升貢獻不大，因此在各種規模下效率都是相對較低的。Weighted QBC在QBC采樣的基礎上不斷分化不同精度分類器對新樣本評價的影響，有效減少了需要標注學習的樣本數量，因而能體現出更高的工作效率。

3.2 參數設置對算法的影響

初始的參數設置會對Weighted QBC算法的性能產生影響，它們包括投票成員的數量（Bagging訓練的輪次），初始預測能力（Bagging每輪訓練所用的樣本數），標注門檻值θ。投票成員需滿足一定的數量才能為樣本的標注與否提供有價值的參考，表3列出了二分類模型下，四種不同的委員會成員數對應的可能熵值。

可以看出，在投票成員數目偏小時，熵的可能取值也會相應較少，為樣本提供標注參考的能力就會相對較弱。如在只有3個成員進行投票的情形下，熵的取值只有0和0.918 3兩種可能性，導致會有大量的樣本不能通過分類器直接決定其類別，而需要通過專家或人工標注獲取其標簽。同樣，Bagging初始訓練所使用的樣本數多少決定了投票成員的預測能力強弱，強分類器在一般樣本的類別預測上，會體現出較高的一致性，降低熵值，減少標注學習的次數，而初始訓練能采用的樣本數取決于有標簽集的規模|L|。

閾值θ也是影響標注次數的重要因素，采樣次數會隨著該參數值的增加而遞減，當θ=0時，QBC采樣就退化成隨機采樣，θ過小的取值會導致信息量近似的樣本被冗余標注，增大機器學習負擔；而過大的值則會讓采樣過程中一些學習價值較高的樣本被遺漏，分類器得不到有效的訓練。表4給出了不同的標注門檻下，Weighted QBC在無標簽池中的采樣次數。

表4 不同的閾值θ對應的樣本采集次數

4 結束語

本文在分析委員會投票采樣QBC算法的基礎上，針對投票過程中各分類器對無標簽樣本熵值的貢獻相同，前期學習經驗沒有得到合理利用的情況，提出了加權投票采樣方法Weighted QBC。統計委員會中成員對有標簽樣本的預測精度，并據此為不同的分類器賦予相應的權重；在每次采集標注到一個新樣本后，根據現有成員對該樣本類別預測的對錯，調高或降低其權值，并運用到下一次的學習中去。該方法能夠更好地發揮委員會中高精度成員的判別作用，減少機器學習過程中需要專家或人工標注的樣本數量，壓縮訓練成本。通過在UCI的Statlog（Australian Credit Approval）數據集進行仿真，并與其他采樣方法進行效率對比，證明了該方法的有效性。

[1]陳榮，曹永鋒，孫洪.基于主動學習和半監督學習的多類圖像分類[J].自動化學報，2011，37（8）：954-962.

[2]Hoi S C H，Jin R，Lyu M R.Large-scale text categorization by batch mode active learning[C]//Proceedings of the International Conference on World Wide Web.[S.l.]：ACM Press，2006：633-642．

[3]Settles B，Craven M.An analysis of active learning strategies for sequence labeling tasks[C]//Proceedings of the Conference on Empirical Methods in Natural Language Processing.[S.l.]：ACL Press，2008：1069-1078.

[4]Hauptmann，Lin W，Yan R，et al.Extreme video retrieval：joint maximization of human and computer performance[C]// Proceedings of ACM Workshop on Multimedia Image Retrieval.[S.l.]：ACM Press，2006：385-394.

[5]Chu W，Zinkevich M，Li L，et al.Unbiased online active learning in data streams[C]//Proceedings of the 17th ACM SIGKDDInternational Conference on Knowledge Discovery and Data Mining.[S.l.]：ACM Press，2011：195-203.

[6]Graepel T，Candela J Q，Borchert T，et al.Web-scale Bayesian click-through rate prediction for sponsored search advertising in Microsoft’s Bing search engine[C]//Proceedings of the 27th International Conference on Machine Learning，2010：13-20.

[7]吳偉寧，劉揚，郭茂祖，等.基于采樣策略的主動學習算法研究進展[J].計算機研究與發展，2012，49（6）：1162-1173.

[8]Tong S，Koller D.Support vector machine active learning with applications to text classification[J].The Journal of Machine Learning Research，2001（2）：45-66.

[9]Huang Shengjun，Jin Rong，Zhou Zhihua.Active learning by querying informative and representative examples[C]// Proc of NIPS 2010.Cambridge，MA：MIT Press，2010：892-900.

[10]Dagan I，Engelson S P.Committee based sampling for training probabilistic classifiers[C]//Proceedings of the 12th International Conference on Machine Learning，1995：150-157.

[11]Freund Y，Schapire R E.A decision-theoretic generalization of on-line learning and an application to boosting[J]. Journal of Computer and System Sciences，1997，55（1）：119-139.

[12]Breiman L.Bagging predictors[J].Machine Learning，1996，24（2）：123-140.

[13]Argamon E S，Dagan I.Committee-based sample selection for probabilistic classifiers[J].Journal of Artificial Intelligence Research，1999（11）：335-360.

[14]Seung H S，Opper M，Sompolinsky H.Query by committee[C]//Proceedings of the 15th Annual ACM Workshop on Computational Learning Theory，California，1992：287-294.

[15]Freund Y，Seung H S，Samir E，et al.Selective sampling usingthequerybycommitteealgorithm[J].Machine Learning，1997，28（23）：133-168.

CHEN Nian1，2,TANG Zhenmin2

1.Department of Mathematics and Computer Science,Chizhou University,Chizhou,Anhui 247000,China
2.Computer Science and Engineering College,Nanjing University of Science and Technology,Nanjing 210094,China

In this paper,a method of weighted voting is proposed which can adjust weights of classifiers in committee during the sampling process and it is based on query by committee algorithm.In process of unlabeled sample’s quality evaluation,the method can strengthen the contribution of high precision members,reduce the influence of high error members and decrease the times of learning which is needed in machine training.By experiment on dataset of Statlog（Australian Credit Approval）and compared results with other methods,the effectiveness has been proved that the algorithm can gain stable generalization accuracy with smaller costs of samples labeling.

active learning;sampling query;weighted voting;entropy;labeling threshold

A

TP391

10.3778/j.issn.1002-8331.1212-0281

CHEN Nian,TANG Zhenmin.Application of user credit rating based on weighted voting sampling algorithm.Computer Engineering and Applications,2014,50（21）：259-263.

安徽省教育廳高等學校自然科學研究重點項目（No.KJ2012A211）。

陳念（1978—），男，副教授，主研方向：機器學習與人工智能；唐振民，教授，博導。E-mail：njustchennian@gmail.com

2012-12-24

2013-02-22

1002-8331（2014）21-0259-05

CNKI出版日期：2013-03-13，http://www.cnki.net/kcms/detail/11.2127.TP.20130313.0955.023.html