基于加权策略的SVM多元分类器

基于加权策略的SVM多元分类器华南理工大学信息网络工程研究中心广东省计算机网络重点实验室曹鸿董守斌张凌全国搜索引擎与网上信息学术研讨会目录•算法描述–传统一对多（OVA）方法–加权阈值策略（OVA-WWT）•系统模块•实验结果•结论传统OVA（One-Vs-All）方法：主要思路•主要思路–训练N个不同的二元分类器，第i个分类器用第i类中的训练样本作为正的训练样本，而将其他样本作为负的训练样本–当对一个新文档进行分类时，分别运行N个二元分类器，选择输出相似度值最大的那个分类器的结果传统一对多（OVA）方法：形式化描述•给定个l训练样例(,),…(,)，其中,i=1,…l,且是xi的类标签，则第i个SVM分类器要解决下面的最优化问题:––•用下面的k个决策方程计算x与k个类别的相似度：•最终判定x隶属于决策方程输出相似度最高的那个类别：Classofx=1x1ylxlyniRx},...1{kyiljijiiiibiwCww1T)(21minl,jiybxiwiybxiwijiijijiijij...10,if,1-)()(if,1)()(s.t.TT　　kibxiwxfii,...1,)()()(T))()((maxargT,...1ikibxiw阈值策略•阈值策略：把一篇文档归属到某些相关类别中的方法•RCut、PCut和SCut•传统OVA使用的是RCut策略传统一对多（OVA）方法：缺点1）比较文档对N个类别的相似度，简单地取相似度最大的那个类别，由于这N个相似度是由N个不同的分类器产生，简单地取最大值作为阈值策略并不合适；2）对所有类别一视同仁，而实际上，有些类别属于“弱势类”，其类别信息容易被“强势类”所淹没，导致“弱势类”文档被误分到“强势类”中的不公平现象。本文对OVA的改进•提出加权阈值策略(WeightedRCut:WRCut)•通过给不同类别的相似度结果赋以一定的权重值后再进行比较，实现“弱势类”和“强势类”之间的势力均衡，以消除使用单一的RCut策略所造成的不公平现象目录•算法描述–传统一对多（OVA）方法–加权阈值策略（OVA-WWT）•系统模块•实验结果•结论加权阈值策略（OVA-WWT）算法描述：•先解SVM最优化问题，用决策方程计算出文档对N个类别的相似度，再对各类别运用WRCut阈值策略，文档x属于加权相似度最大的类别•Classofx=••ai也可以通过对训练集的学习而得。))()((maxargT,...1iikibxiwaiiiECa目录•传统一对多（OVA）方法•加权阈值策略（OVA-WWT）•系统模块•实验结果•结论系统模块结构……测试数据N个SVMlight格式的测试文件SVMlight分类模块testModel1Model2ModelnModel3　　　……结果处理模块训练样本N个SVMlight格式的训练文件SVMlight训练模块train分类结果1分类结果2分类结果3分类结果n最终结果数据转换模块目录•算法描述–传统一对多（OVA）方法–加权阈值策略（OVA-WWT）•系统模块•实验结果•结论实验结果•数据集：北京大学网络实验室提供的CWT100G数据集之200M训练集（11个类别）•模型：200M数据的2/3用于构建分类器模型，剩余1/3作开放测试集进行分类测试。SVM使用线性核函数。•评测标准：微平均准确率、宏平均准确率、宏平均召回率、宏平均F1值和时间，其中时间是包括训练和分类的总时间实验结果1：分类器的比较(1)分类方法微平均准确率（％）宏平均准确率（％）宏平均召回率（％）宏平均F1（％）时间（s)SVMmultic64.3527.1925.6526.401795.53SVMTorch44.3575.6135.9548.7325034.3RainbowSVM80.1376.9575.7376.3313205.5MSVMlight88.6490.7085.9988.311108.5实验结果1：分类器的比较(2)性能曲线图时间柱状图0%20%40%60%80%100%micro_pMacro_pMacro_rMacro_F1SVMmulticlassSVMTorchRainbowSVMMSVMlight050001000015000200002500030000SVMmulticSVMTorchRainbowSVMMSVMlight实验2：阈值策略的比较（1）•对WRCut中各类别的权重值，本文将训练集随机划分为训练-训练集(占3/4)和训练-测试集（占1/4），从经验值出发，在反复训练的过程中自动调整权重值。•权重调整范围为0.9~1.9，每个类的权重分别递增0.1，当权重的增加使得精度下降时，该权重减0.1，取宏观F1达到最大值时各类别所得权重，总训练时间为58.587秒，这个时间对总训练时间而言是可忽略的。实验2：阈值策略的比较（2）类别编号类别权重值01人文与艺术1.903商业与经济1.704娱乐与休闲1.905计算机与因特网1.907教育1.908各国风情0.910自然科学0.911政府与政治1.912社会科学1.913医疗与健康1.914社会与文化1.1经过学习得到的11个类别各自的权重值实验2：阈值策略的比较（3）RCut策略与WRCut策略精度比较曲线80%82%84%86%88%90%92%micro_pMacro_pMacro_rMacro_F1RCutWRCut目录•算法描述–传统一对多（OVA）方法–加权阈值策略（OVA-WWT）•系统模块•实验结果•结论结论•本文提出了一对多算法的改进版本OVA-WWT算法•基于OVA-WWT和SVMlight二元分类算法，实现了SVMlight的多元分类器MSVMlight。•在CWT100G上进行了一系列开放性实验，通过与多种分类器进行性能比较，证明对CWT100G数据集而言，MSVMlight在准确率和时间性能要优于其他三种分类器。•针对CWT100G数据集进行阈值策略选择实验，结果表明，OVA-WWT算法比OVA算法精度要高•缺点：类别权重的训练需要花费额外时间，但是对于大规模数据的训练和分类而言，以可忽略的时间换来精度的显著提高是值得的谢谢大家！