基于加權(quán)策略的SVM多元分類(lèi)器

1、 華南理工大學(xué)信息網(wǎng)絡(luò)工程研究中心華南理工大學(xué)信息網(wǎng)絡(luò)工程研究中心 廣東省計(jì)算機(jī)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室廣東省計(jì)算機(jī)網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室 曹鴻曹鴻 董守斌董守斌 張凌張凌全國(guó)搜索引擎與網(wǎng)上信息學(xué)術(shù)研討會(huì)目錄 算法描述算法描述 傳統(tǒng)一對(duì)多（傳統(tǒng)一對(duì)多（OVA）方法）方法 加權(quán)閾值策略（OVA-WWT） 系統(tǒng)模塊 實(shí)驗(yàn)結(jié)果 結(jié)論傳統(tǒng)OVA（One-Vs-All）方法：主要思路 主要思路 訓(xùn)練N個(gè)不同的二元分類(lèi)器，第i個(gè)分類(lèi)器用第i類(lèi)中的訓(xùn)練樣本作為正的訓(xùn)練樣本，而將其他樣本作為負(fù)的訓(xùn)練樣本 當(dāng)對(duì)一個(gè)新文檔進(jìn)行分類(lèi)時(shí)，分別運(yùn)行N個(gè)二元分類(lèi)器，選擇輸出相似度值最大的那個(gè)分類(lèi)器的結(jié)果 傳統(tǒng)一對(duì)多（OVA）方法：形式化描

2、述 給定個(gè)l訓(xùn)練樣例( , ), ( , )，其中 , i =1, l, 且 是xi的類(lèi)標(biāo)簽，則第i個(gè)SVM分類(lèi)器要解決下面的最優(yōu)化問(wèn)題: 用下面的k個(gè)決策方程計(jì)算x與k個(gè)類(lèi)別的相似度： 最終判定x隸屬于決策方程輸出相似度最高的那個(gè)類(lèi)別： Class of x = 1x1ylxlyniRx ,.1kyiljijiiiibiwCww1T)(21minl,jiybxiwi ybxiwijiijijiijij.10, if,1-)()(if,1)()(s.t.TTkibxiwxfii,.1,)()()(T)()(maxargT,.1ikibxiw閾值策略 閾值策略：把一篇文檔歸屬到某些相關(guān)類(lèi)別中的方

3、法 RCut、PCut和SCut 傳統(tǒng)OVA使用的是RCut策略傳統(tǒng)一對(duì)多（OVA）方法：缺點(diǎn)1）比較文檔對(duì)N個(gè)類(lèi)別的相似度，簡(jiǎn)單地取相似度最大的那個(gè)類(lèi)別，由于這N個(gè)相似度是由N個(gè)不同的分類(lèi)器產(chǎn)生，簡(jiǎn)單地取最大值作為閾值策略并不合適；2）對(duì)所有類(lèi)別一視同仁，而實(shí)際上，有些類(lèi)別屬于“弱勢(shì)類(lèi)”，其類(lèi)別信息容易被“強(qiáng)勢(shì)類(lèi)”所淹沒(méi)，導(dǎo)致“弱勢(shì)類(lèi)”文檔被誤分到“強(qiáng)勢(shì)類(lèi)”中的不公平現(xiàn)象。本文對(duì)OVA的改進(jìn) 提出加權(quán)閾值策略(Weighted RCut: WRCut) 通過(guò)給不同類(lèi)別的相似度結(jié)果賦以一定的權(quán)重值后再進(jìn)行比較，實(shí)現(xiàn)“弱勢(shì)類(lèi)”和“強(qiáng)勢(shì)類(lèi)”之間的勢(shì)力均衡，以消除使用單一的RCut策略所造成的不公平

4、現(xiàn)象 目錄 算法描述 傳統(tǒng)一對(duì)多（OVA）方法 加權(quán)閾值策略（加權(quán)閾值策略（OVA-WWT） 系統(tǒng)模塊 實(shí)驗(yàn)結(jié)果 結(jié)論加權(quán)閾值策略（OVA-WWT）算法描述算法描述： 先解SVM最優(yōu)化問(wèn)題，用決策方程計(jì)算出文檔對(duì)N個(gè)類(lèi)別的相似度，再對(duì)各類(lèi)別運(yùn)用WRCut閾值策略，文檔x屬于加權(quán)相似度最大的類(lèi)別 Class of x = ai也可以通過(guò)對(duì)訓(xùn)練集的學(xué)習(xí)而得。)()(maxargT,.1iikibxiwaiiiECa 目錄 傳統(tǒng)一對(duì)多（OVA）方法 加權(quán)閾值策略（OVA-WWT） 系統(tǒng)模塊系統(tǒng)模塊 實(shí)驗(yàn)結(jié)果 結(jié)論系統(tǒng)模塊結(jié)構(gòu)目錄 算法描述 傳統(tǒng)一對(duì)多（OVA）方法 加權(quán)閾值策略（OVA-WWT） 系

5、統(tǒng)模塊 實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)結(jié)果 結(jié)論實(shí)驗(yàn)結(jié)果 數(shù)據(jù)集：北京大學(xué)網(wǎng)絡(luò)實(shí)驗(yàn)室提供的CWT100G數(shù)據(jù)集之200M訓(xùn)練集（11個(gè)類(lèi)別） 模型：200M數(shù)據(jù)的2/3用于構(gòu)建分類(lèi)器模型，剩余1/3作開(kāi)放測(cè)試集進(jìn)行分類(lèi)測(cè)試。SVM使用線(xiàn)性核函數(shù)。 評(píng)測(cè)標(biāo)準(zhǔn)：微平均準(zhǔn)確率、宏平均準(zhǔn)確率、宏平均召回率、宏平均F1值和時(shí)間，其中時(shí)間是包括訓(xùn)練和分類(lèi)的總時(shí)間 實(shí)驗(yàn)結(jié)果1：分類(lèi)器的比較(1)分類(lèi)方法微平均準(zhǔn)確率（）宏平均準(zhǔn)確率（）宏平均召回率（）宏平均F1（）時(shí)間（s)SVMmultic64.3527.1925.6526.401795.53SVMTorch44.3575.6135.9548.7325034.3Rainbo

6、wSVM80.1376.9575.7376.3313205.5MSVMlight88.6490.7085.9988.311108.5實(shí)驗(yàn)結(jié)果1：分類(lèi)器的比較(2) 性能曲線(xiàn)圖 時(shí)間柱狀圖實(shí)驗(yàn)2：閾值策略的比較（1） 對(duì)WRCut中各類(lèi)別的權(quán)重值，本文將訓(xùn)練集隨機(jī)劃分為訓(xùn)練-訓(xùn)練集(占3/4)和訓(xùn)練-測(cè)試集（占1/4），從經(jīng)驗(yàn)值出發(fā)，在反復(fù)訓(xùn)練的過(guò)程中自動(dòng)調(diào)整權(quán)重值。 權(quán)重調(diào)整范圍為0.91.9，每個(gè)類(lèi)的權(quán)重分別遞增0.1，當(dāng)權(quán)重的增加使得精度下降時(shí)，該權(quán)重減0.1，取宏觀F1達(dá)到最大值時(shí)各類(lèi)別所得權(quán)重，總訓(xùn)練時(shí)間為58.587秒，這個(gè)時(shí)間對(duì)總訓(xùn)練時(shí)間而言是可忽略的。 實(shí)驗(yàn)2：閾值策略的比較（2

7、）類(lèi)別編號(hào)類(lèi)別權(quán)重值01人文與藝術(shù)1.903商業(yè)與經(jīng)濟(jì)1.704娛樂(lè)與休閑1.905計(jì)算機(jī)與因特網(wǎng)1.907教育1.908各國(guó)風(fēng)情0.910自然科學(xué)0.911政府與政治1.912社會(huì)科學(xué)1.913醫(yī)療與健康1.914社會(huì)與文化1.1經(jīng)過(guò)學(xué)習(xí)得到的11個(gè)類(lèi)別各自的權(quán)重值 實(shí)驗(yàn)2：閾值策略的比較（3）RCut策略與WRCut策略精度比較曲線(xiàn) 目錄 算法描述 傳統(tǒng)一對(duì)多（OVA）方法 加權(quán)閾值策略（OVA-WWT） 系統(tǒng)模塊 實(shí)驗(yàn)結(jié)果 結(jié)論結(jié)論結(jié)論 本文提出了一對(duì)多算法的改進(jìn)版本OVA-WWT算法 基于OVA-WWT和SVMlight二元分類(lèi)算法，實(shí)現(xiàn)了SVMlight的多元分類(lèi)器MSVMlight。 在CWT100G上進(jìn)行了一系列開(kāi)放性實(shí)驗(yàn)，通過(guò)與多種分類(lèi)器進(jìn)行性能比較，證明對(duì)CWT100G數(shù)據(jù)集而言，MSVMlight在準(zhǔn)確率和時(shí)間性能要優(yōu)于其他三種分類(lèi)