陳念，唐振民

1.池州學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，安徽池州 247000

2.南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 210094

加權(quán)投票采樣學(xué)習(xí)在用戶信用評級中的應(yīng)用

陳念1，2，唐振民2

1.池州學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)系，安徽池州 247000

2.南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，南京 210094

以委員會投票查詢算法為基礎(chǔ)，提出在采樣過程中動態(tài)修正分類器成員權(quán)值的加權(quán)投票方法。在對無標(biāo)簽樣本標(biāo)注價(jià)值評估中，該方法能夠強(qiáng)化高精度分類器成員的查詢貢獻(xiàn)，降低高誤差成員的投票影響，減少機(jī)器訓(xùn)練過程中的標(biāo)注學(xué)習(xí)次數(shù)。通過在UCI的Statlog（Australian Credit Approval）數(shù)據(jù)集上對用戶信用度級別進(jìn)行識別，并比較于其他采樣方法，證明該方法能夠用較小的采樣標(biāo)注代價(jià)獲取穩(wěn)定的泛化精度。

主動學(xué)習(xí)；采樣查詢；加權(quán)投票；熵；標(biāo)注門檻

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

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

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

1 委員會投票算法

1.1 投票委員會的產(chǎn)生

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

圖1 用Bagging方法產(chǎn)生投票委員會

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

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

1.2 熵度量的引入

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

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

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

2 基于投票查詢的采樣

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

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

2.1 加權(quán)投票采樣方法

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

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

式中，yk為樣本xi的真實(shí)標(biāo)簽。依據(jù)誤差e給對應(yīng)的分類器賦予權(quán)值wj：

微調(diào)常量ε的作用同樣是為防止誤差為0時(shí)，除0情況的出現(xiàn)。為使wj＞0，則區(qū)別于一般委員會，加權(quán)分類器成員誤差需滿足據(jù)此，委員會對樣本xi屬于某類y的投票結(jié)果可表示為：

用式（7）的投票結(jié)果計(jì)算樣本的熵值，更能發(fā)揮高精度分類器在無標(biāo)簽樣本類別判定中的作用，使一部分樣本的歸類由機(jī)器自行解決，而不需要專家系統(tǒng)或人工的介入。若投票熵值仍然超過預(yù)先設(shè)定的閾值θ，則該樣本需進(jìn)行類別標(biāo)注，作為學(xué)習(xí)樣本加入訓(xùn)練集L。

2.2 投票權(quán)值的更新

在采集標(biāo)注一個(gè)新樣本后，委員會中所有的成員要對它進(jìn)行學(xué)習(xí)，學(xué)習(xí)的方式仍然是對該新樣本進(jìn)行類別預(yù)測。預(yù)測結(jié)果同樣會出現(xiàn)正確和錯(cuò)誤兩種情況，據(jù)此進(jìn)一步調(diào)整委員會成員的權(quán)重，來獲得泛化性能更強(qiáng)的分類器集合。本文提出一種權(quán)值調(diào)整方法，設(shè)分類器f(ωj)在時(shí)刻t的權(quán)值為，則對一個(gè)新樣本xi的類標(biāo)預(yù)測后，其權(quán)值調(diào)整為，令

3 實(shí)驗(yàn)與結(jié)果分析

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

實(shí)驗(yàn)將數(shù)據(jù)集按9∶1的比例隨機(jī)分離出訓(xùn)練樣本和測試樣本，做10重交叉驗(yàn)證。在訓(xùn)練集中有標(biāo)簽池和無標(biāo)簽池的樣本比例按1∶5進(jìn)行設(shè)置。表1列出了實(shí)驗(yàn)數(shù)據(jù)組成及配置情況。

3.1 不同采樣方法效率比較

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

表1 實(shí)驗(yàn)數(shù)據(jù)組成及配置情況

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

表3 不同委員會成員數(shù)對應(yīng)的投票熵

圖3 不同采樣方法對應(yīng)的精度比較

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

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

3.2 參數(shù)設(shè)置對算法的影響

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

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

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

表4 不同的閾值θ對應(yīng)的樣本采集次數(shù)

4 結(jié)束語

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

[1]陳榮，曹永鋒，孫洪.基于主動學(xué)習(xí)和半監(jiān)督學(xué)習(xí)的多類圖像分類[J].自動化學(xué)報(bào)，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]吳偉寧，劉揚(yáng)，郭茂祖，等.基于采樣策略的主動學(xué)習(xí)算法研究進(jìn)展[J].計(jì)算機(jī)研究與發(fā)展，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.

安徽省教育廳高等學(xué)校自然科學(xué)研究重點(diǎn)項(xiàng)目（No.KJ2012A211）。

陳念（1978—），男，副教授，主研方向：機(jī)器學(xué)習(xí)與人工智能；唐振民，教授，博導(dǎo)。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