一种新的半监督支持向量机

王红蔚 ， 席红旗 ， 孔 波

(1.河南教育学院 数学系 河南 郑州 450046；2. 河南教育学院 信息技术系 河南 郑州 450046)

0 引言

半监督学习是近年来模式识别和机器学习领域研究的重点问题，主要考虑如何利用少量的标签样本和大量无标签样本进行训练和分类的问题[1].半监督学习对于减少标注代价，提高学习机器性能具有重要的实际意义.最早的一种半监督算法应用于网页分类[2]；文献[3]利用混合整数规划的方法提出了一种半监督支持向量机(S3VM)，但是该算法很难解决有大量无类别标签样本的问题；为了解决这个问题，文献[4]提出了一种凸半监督支持向量机(VS3VM)，该算法先对无类别标签样本进行类别标示，再使用监督学习算法.但标注过程本身就非常复杂，而且准确率难以保证；为解决该问题，文献[5]提出了一种新的思路，直接对无类别标签样本进行分类，使得聚类分类一次完成，并得到了无监督支持向量机和半监督支持向量机，不过在这个方法中，要求最优分划超平面必须过训练样本集的质心，这显然不适合解决所有问题.文献[6]通过不断地对无标签样本进行标记提出了一种半监督支持向量机，显然这不易于处理大样本情形.文献[7]提出了一种借助径向基核函数求解球类数据的半监督支持向量机，这也仅适用于特殊的问题.

综合利用有类别标签和无类别标签样本信息构造目标函数和约束条件，本文借助二次规划模型提出了一种新的半监督支持向量机.

1 半监督支持向量机

已知训练集T={x1,y1,…,xl,yl,xl+1,…,xl+k}, 其中xi∈X=Rn，前l个属于有类别标签样本，即i=1,2,…,l时，已知yi∈Y={-1,1}；后k个属于无类别标签样本.寻找X=Rn上的决策函数f(x)=sgn(ωTφ(x)+b)(其中，ω为权向量，φ(·)为映射函数，b为常数，核函数Kxi,xj=〈φ(xi),φ(xj)〉)来推断任一模式x的类别(正类或者负类).由此可见，求解分类问题，实质上就是找到一个把Rn上的点分成2部分的规则.

显然存在ω∈Rn，b∈R，对于任一有类别标签样本xi(i=1,…,l)，都有yiωTφ(xi)+b+ξi≥1,ξi≥0,i=1,…,l.对于任一无类别标签样本xj(j=l+1,…,l+k)，都有ωTφ(xj)+b+rj≥1，ωTφ(xj)+b-sj≤-1，rj,sj≥0,j=l+1,…,l+k.

这样求解最佳分划超平面的问题就转化为最优化问题：

令

(1)

(2)

新的半监督支持向量机算法为：

a)已知训练集T={(x1,y1),…,(xl,yl),xl+1,…,xl+k}，其中xi(i=1,…,l)属于有类别标签样本，且yi∈Y={-1,1},xj(j=l+1,…,l+k)属于无类别标签样本；

为了有效地突出2种样本的区别，惩罚参数可根据样本容量的比例进行选取，核函数可根据样本分布选取.

2 实验分析

UCI数据库是机器学习的一个标准数据库，可以用来衡量各种模式识别算法的有效性.为了验证所提出算法的有效性，特选取UCI数据库上breast cancer wisconsin (original)(BCW)数据[9]分别使用支持向量机(C-SVM)和新半监督支持向量机(NS3VM)算法进行了对比实验.

表1 BCW数据准确率比较Tab.1 Comparison of accuracy about BCW database %

由表1可以看出，利用了未知标签样本的半监督支持向量机的测试准确率优于仅使用已知标签样本的支持向量机,而且已知类别样本个数越少，新的半监督支持向量机的性能越优越.

3 结论

为了有效地利用未知类别样本进行训练，提高学习机器性能，通过构造新的目标函数和约束条件，提出了一个新的半监督学习支持向量机.该算法具有3个优点：同传统的支持向量一样利用二次规划求解问题，具有解的优良性，并适合处理大量数据样本；可以一次完成求解最优分划超平面，简化了标注未知类别样本的复杂性；有效地解决了文献[5]要求最优分划超平面过训练样本质心的问题，实用性得到了提高.实验结果印证了该算法可以有效地提高仅利用有类别标签样本的支持向量机的分类准确率.

参考文献：

[1] Vapnik V. The Nature of Statistical Learning Theory[M]. New York: Springer-Verlag，1995.

[2] Blum A, Mitchell T. Combining labeled and unlabeled data with cotraining[C]//Proceedings of the 11th Annual Conference on Computational Learning Theory. Madison, 1998: 92-100.

[3] Bennett K P, Demiriz A. Semi-supervised Support Vector Machines[C]//Advances in Neural Information Proceeing Systems 11. Cambridge, 1998: 368-374.

[4] Fung G, Mangasarian O L. Semi-supervised support vector machines for unlabeled data classification[J]. Optimization Methods and Software，2001,15: 29-44.

[5] Wu Tao, Zhao Hanqing. Classifying unlabeled data with SVMs[J]. Advances in Intelligent and Soft Computing, 2006,34: 695-702.

[6] 门昌骞，王文剑. 一种基于多学习器标记的半监督SVM学习方法[J] . 广西师范大学学报：自然科学版， 2008, 26(1): 186-189.

[7] 朱美琳, 杨佩. 半监督支持向量机的多分类学习算法[J]. 郑州大学学报：理学版，2008，40(4): 35-38.

[8] Hsu C W，Lin C J. A simple decomposition method for support vector machines[J]. Machine Learning,2002，46(1/2/3)：291-314.

[9] Blake C L, Merz C J. UCI Repository of machine learning databases[EB/OL]. [2011-01-11] .http://www.ics.uci.edu/～mlearn/databases/.