计算机科学与应用  >> Vol. 10 No. 11 (November 2020)

半监督支持向量机学习分类方法
Semi-Supervised Support Vector Machine Learn Classification Methods

DOI: 10.12677/CSA.2020.1011221, PDF, HTML, XML, 下载: 119  浏览: 252  科研立项经费支持

作者: 姚 瑞:新疆师范大学,新疆 乌鲁木齐

关键词: 支持向量机半监督学习分类问题Support Vector Machines Semi-Supervised Learning Classification

摘要: 随着社会的不断进步,对于数据处理的要求越来越高,人们需要处理的数据非常庞大,比如工业信息、环境信息,有些数据没有明确的标签供人们进行处理,当存在海量的无标签数据时,如何从海量的无标签数据中获得有用的数据,是需要重点研究的问题。半监督学习不仅能够更好地利用标签进行数据的处理,同时还可以通过无标签数据进行指导以提高分类的精度。因此,本文将重点研究基于支持向量机的半监督学习分类方法。
Abstract: With the continuous progress of the society, the demand for data processing is getting higher and higher, the amount of data that people have to deal with, such as industrial information, environmental information, some data don't have clear labels for people to process, when there are massive unlabeled data, how to get useful data from the massive unlabeled data is a key problem to be studied. Semi-supervised learning can not only make better use of tags for data processing, but also improve the accuracy of classification through the guidance of unlabeled data. Therefore, this paper will focus on the semi-supervised learning classification method based on support vector machine.

文章引用: 姚瑞. 半监督支持向量机学习分类方法[J]. 计算机科学与应用, 2020, 10(11): 2095-2104. https://doi.org/10.12677/CSA.2020.1011221

1. 引言

支持向量机是一种机器学习方法,主要针对小样本分类问题开展的一种学习方法,遵守结构风险极小化原则,获取全局最优解,并在压缩感知、模式识别以及图像处理等热点领域中得到了广泛的应用。半监督支持向量机是一种能够同时兼顾标签与无标签样本的学习方法,因而半监督支持向量机的学习方法在处理大规模数据识别与分类的过程中处理良好。半监督支持向量机的数学模型优化问题较为复杂,在处理非线性分类问题时比较消耗时间,因此对半监督分类的模型与算法进行研究与设计非常重要。

2. 半监督支持向量机

2.1. 支持向量机

训练样本集为 { ( x i , y i ) } i = 1 l ,任意 i = 1 , , l x i R m y i { 1 , 1 } ,m表示样本特征的维数,l表示样本训练的个数。如果训练样本集是线性的,支持向量机需要满足条件 w R m , b R ,则:

w T x i + b > 0 , y i = 1 , w T x i + b < 0 , y i = 1 (1.1)

根据公式(1.1),能够得到 w T x + b = 0 ,如图1所示,图中的三角标志和圆圈表示的是两种不同类型的样本点,实线表示分类超平面,虚线表示支撑超平面 [1],两条虚线支撑超平面分别表示: w T x + b = 1 w T x + b = 1

Figure 1. Linear Separable Support Vector Machine

图1. 线性可分支持向量机

2.2. 半监督支持向量机方法

在半监督支持向量机中,需要考虑到标签训练样本集和无标签样本集两种方式,分别为 { ( x i , y i ) } i = 1 l { x i } i = l + 1 n x i R m , i = 1 , , n y i { 1 , 1 } l , i = 1 , , l ,如图2所示,实心表示标签样本,空心表示无标签样本,无标签样本更能够体现出样本集的实际分布状况 [2]。

Figure 2. Semi-supervised support vector machines

图2. 半监督支持向量机

将未知的样本类标签看成是一种新的变量,能够得到半监督支持向量机的模型:

min w , b , y u 1 2 w 2 + C l i = 1 l max ( 0 , 1 y i o i ) p + C u i = l + 1 n max ( 0 , 1 y i o i ) p s .t . y u = ( y l + 1 , y l + 2 , , y n ) { 1 , 1 } n l w R m , b R (1.2)

其中, o i = w T x i + b C l , C u 表示标签样本与为标签样本之间的惩罚参数。

在半监督分类过程中,为了避免类标签偏差较为明显,可以引入公式:

1 n 1 i = l + 1 n y i = 2 r 1 (1.3)

r表示所占比例。

公式(1.2)的求解方式有组合优化方式和连续优化方式,这两种方式的求解思想为:

组合优化方式中需要考虑 y u 的取值可能性,对每一组固定的 y u 进行取值,将公式(1.2)转化为标准的求解支持向量机的问题。对 y u 的所有取值可能性进行遍历,得到相应的优化求解方式:

min w , b , ξ , y u 1 2 w 2 2 + C l i = 1 l ξ i p + C u i = l + 1 n ξ i p s .t . y i ( w T x i + b ) 1 ξ i , i = 1 , 2 , , n ξ = ( ξ 1 , ξ 2 , , ξ n ) T 0 l y u = ( y l + 1 , y l + 2 , , y n ) { 1 , 1 } n 1 w R m , b R (1.4)

公式(1.4)属于混合正数规划问题,求解的方式较为困难。

在连续优化方法中,固定的数值在面对任意的 i = l + 1 , , n 时,都可以使用 sgn ( w T x i + b ) 表示,得到关于固定数值的连续优化问题:

min w , b 1 2 w 2 + C l i = 1 l max ( 0 , 1 y i o i ) p + C u i = l + 1 n max ( 0 , 1 | o i | ) p s .t . w R m , b R (1.5)

其中 o i = w T x i + b ,公式(1.5)属于一个非凸优化问题,该问题中的平衡约束可以表示为:

1 n 1 i = l + 1 n w T x i + b = 2 r 1 (1.6)

3. 半监督支持向量机的锥松弛方法

锥规划问题有着其特殊的结构方式,有较好的表述能力,在实际问题的解决中得到了广泛的应用于推广。本节介绍的半监督支持向量机的锥松弛方法,在原问题的基础上提出新的问题,并估计原问题的最优质与最新半正定松弛问题的比值,同时数值实验的结果证明松弛方法所取得的分类效果。

3.1. 半正定松弛

根据引理结论“若 y { 1 , 1 } n K ^ S + n 成立,则 ( K ^ y y T ) 1 = K ^ 1 y y T ”,则

min y u max α 1 n T α 1 2 α T ( K ^ y y T ) α s .t . y u = ( y l + 1 , y l + 2 , , y n ) { 1 , 1 } n 1 , α R + n (2.1)

将公式(2.1)的目标函数进行转化,为:

1 2 ( ( 1 n + μ ) y ) T K ^ 1 ( ( 1 n + μ ) y ) (2.2)

引入变量 v : = ( 1 n + μ ) y ,公式(2.1)等价于 [3]:

min v 1 2 v T K 1 v s .t . y i v i 1 , i = 1 , , l v j 2 1 , j = l + 1 , , n v R n (2.3)

该问题是含有凸与非凸的二次规划问题。

3.2. 双非负松弛

公式(2.1)的双非负松弛问题,在解决这类较难的非凸二次规划问题时,首先需要给出问题的完全正松弛。

z : = ( y + 1 n ) / 2 R n , δ : = μ + 1 n R n ,问题(2.1)能够被等价转换为 [4]:

min δ , z n 1 2 ( δ ( 2 z 1 n ) ) T K ^ 1 ( δ ( 2 z 1 n ) ) s .t . δ 1 n z u = { z l + 1 , z l + 2 , , z n } { 0 , 1 } n l , δ R n (2.4)

其中, z = { z 1 , z 2 , , z n } ,则:

u : = ( δ z δ 1 n ) R 2 n , K ˜ : = ( 4 K ^ 1 2 K ^ 1 2 K ^ 1 K ^ 1 ) (2.5)

公式(10)的目标函数可以进行转化,相应的等价问题为:

min u 1 2 u T K ˜ u s .t . y i ( 2 u i u i + n ) 1 , i = 1 , , l u j + n 1 , u j u j + n u j 2 = 0 , j = 1 , , n u = { u 1 , u 2 , , u 2 n } R 2 n (2.6)

3.3. 数值实验

通过数值实验测试的方式对上述两种方法的分类表现进行记录,并将测得的试验结果与半监督支持向量机进行比较,对标签样本个数的分类精度影响进行重点的分析与实验。

选择两组人工数据,四组基准数据这六组数据集进行试验,如图3所示。具体的数据集信息如表1所示。

Table 1. The date set

表1. 数据集

Figure 3. Artificial Data Set Sample Point Distribution and Classification Hyperplane

图3. 人工数据集样本点分布与分类超平面

首先,对半正定松弛与双非负松弛进行分类,根据图3所示的平面得到两组人工数据集的分类决策函数。其次,使用半正定松弛与双飞负松弛这两种方法对基准数据进行分类,记录使用这两种方式对采集到的数据集分类精度的最佳数值,其数值对比结果如表2所示,从表2可以看出,双非负松弛问题比半正定松弛所得到的分类精度更好更准确 [5]。

Table 2. Comparison results of positive semi-definite relaxation method and twin non-negative relaxation method

表2. 半正定松弛方法和双非负松弛方法对比结果

结果UCI数据集,对比半监督支持向量机与半正定松弛、双非负松弛,在对比的过程中采取的方法有梯度下降法、凹凸过程法等,不同对比方法的错分率结果如图4所示。

Figure 4. The influence of the number of labeled sample points on the error rate

图4. 有标签样本点个数对错分率的影响

本节提出的半监督支持向量机所对应的规划问题,其中介绍的两种锥松弛方法都能够得到元混合正数规划问题,通过进一步的分析能够得到更好的下届,通过数值实验的数据结果显示,这两种松弛方法都能够得到较好的分类效果,且双非负松弛比半正定松弛的分类精度更高更准确。

4. 多视角双平面支持向量机

将双平面支持向量机进行扩展,升级为多视角双平面支持向量机,在同一视角中,正样本与负样本由矩阵 A 1 , B 1 表示,在另一个视角中,正样本与负样本 A 2 , B 2 表示,为了使公式变得更加简洁,将所有的e表示为1的向量,都是合适维数的数值 [6]。即:

A 1 = ( A 1 , e ) , B 1 = ( B 1 , e ) , A 2 = ( A 2 , e ) , B 2 = ( B 2 , e ) v 1 = ( w 1 b 2 ) , v 2 = ( w 2 b 2 ) , u 1 = ( w 3 b 3 ) , u 2 = ( w 4 b 4 ) (3.1)

公式(3.1)中的 ( w 1 , b 1 ) , ( w 2 , b 2 ) 表示+1参数, ( w 3 , b 3 ) , ( w 4 , b 4 ) 是−1参数。

多视角双平面支持向量机的优化问题可以表示为:

min v 1 , v 2 , q 1 , q 2 , η 1 2 A 1 v 1 2 + 1 2 A 2 v 2 2 + c 1 e 2 T q 1 + c 2 e 2 T q 2 + D e 1 T η s .t . | A 1 v 1 A 2 v 2 | η B 1 v 1 + q 1 e 2 , B 2 v 2 + q 2 e 2 , q 1 0 , q 2 0 , η 0 (3.2)

e 1 , e 2 是全为1的向量,这些向量均是合适维数的数值, v 1 , v 2 , u 1 , u 2 表示分类器参数, c 1 , c 2 , d 1 , d 2 , D 表示非负参数。对公式(3.2)用拉格朗日公式表示为:

L = 1 2 A 1 v 1 2 + 1 2 A 2 v 2 2 + c 1 e 2 T q 1 + c 2 e 2 T q 2 + D e 1 T η β 1 T ( η A 1 v 1 + A 2 v 2 ) β 2 T ( A 1 v 1 A 2 v 2 + η ) α 1 T ( B 1 v 1 + q 1 e 2 ) α 2 T ( B 2 v 2 + q 2 e 2 ) λ 1 T q 1 λ 2 T q 2 σ T η (3.3)

α 1 , α 2 , β 1 , β 2 , λ 1 , λ 2 , σ 表示拉格朗日向量。对公式(3.3)求偏导,使公式结果等于0,可以得到:

v 1 = ( A 1 T A 1 ) 1 [ A 1 T ( β 2 β 1 ) B 1 T α 1 ] , v 2 = ( A 2 T A 2 ) 1 [ A 2 T ( β 1 β 2 ) B 2 T α 2 ] (3.16)

得到对偶问题:

min ξ 1 , ξ 2 , a 1 , a 2 1 2 ξ 1 T ( A 1 T A 1 ) 1 ξ 1 + 1 2 ξ 2 T ( A 2 T A 2 ) 1 ξ 2 ( α 1 + α 2 ) T e 2 s .t . ξ 1 = A 1 T ( β 2 β 1 ) B 1 T α 1 , ξ 2 = A 2 T ( β 1 β 2 ) B 2 T α 2 , 0 β 1 , β 2 , β 1 + β 2 D e 1 0 α 1 / 2 c 1 / 2 e 2 (3.4)

在进行计算的过程中要注意一个分类准则 [7],对于同一个样本x,有两个不同的视角,如果 x 1 = ( x 1 , 1 ) x 2 = ( x 2 , 1 ) ,则该公式属于+1类,否则为−1类,多视角半监督双平面支持向量机能够解决二次优化问题,但是它的复杂度较高,有两个不同视角的维数。

5. 半监督支持向量机学习分类方法

5.1. 优化方式分类

5.1.1. 组合优化方式

组合优化方式能够同时优化三个参数,分别为 w , b , y u * ,其中 y u * 的值能够通过人为的方式进行指定。即:

Ψ ( y u * ) = min w , b I ( w , b , y u * ) (4.1)

采用指定的方式就可以像优化标准的支持向量机一样,对组合方程进行优化。这种组合的方式可以供很多的优化算法进行使用,将组合优化方式应用在文本分类中,但是这些都是局部优化,无法对全局最优化起到一定的作用。

5.1.2. 连续优化方式

连续优化方式首先需要通过固定的参数 ( w , b ) ,寻找到代价函数最小的值: arg min y u * V ( y u * , o ) = sign ( o ) ,用指定标签值符号 o i = w T x i + b 进行表示,然后重复步骤标注其他的符号。即:

1 2 w 2 + C l = 1 n max ( 0 , 1 y l o l ) + C * u = 1 m max ( 0 , 1 | O u | ) 2 (4.2)

通过公式(4.2)能够看出,前两项是标准的支持向量机,最后一项是用二次代价函数进行代替,是一个非凸优化,如图5所示。

Figure 5. Symbolic output of decision function

图5. 决策函数的符号输出

5.2. 凹凸优化过程

凹凸优化过程采用的是半监督连续优化的方式,优化的方式就是将方程 min ( w , b ) , y u * I ( w , b , y u * ) = 1 2 w 2 + C l = 1 n V ( y l , o l ) + C * u = 1 m V ( y u * , o u ) 中的最后一项进行分解,将其分解成凸函数与凹函数,在后面的迭代过程中,将这个凸函数替换为线性函数 [8],这种替换的方法叫做切线近似法,这样在迭代的过程中就只是一个凸函数和线性函数的计算,在进行求解的过程中较为简单。即:

max ( 0 , 1 | t | ) 2 = max ( 0 , 1 | t | ) 2 + 2 | t | 2 | t | (4.3)

为了可以达到优化的最终目的,可以将代价函数的值应用在目标方程中,这样就可以通过迭代的方式进行求解,从而得到最优解。对方程式作进一步的分类过程中,可以指定其中一个无标签的值为正数,并将其应用到训练的下一次迭代中,对结果目标方程所造成的影响为:

L ( t ) = { 0 , if t 1 ( 1 t ) 2 , if | t | < 1 4 t , if t 1 (4.4)

使用凹凸优化方法应用在半监督算法计算中,可以按照以下流程进行计算:

首先用监督支持向量机标签样本得到参数值 w , b

repeat y i * sign ( w x i + b ) , n + 1 i n + m ( w , b ) = are min 1 2 w 2 + C l = 1 n max ( 0 , 1 y l ( w x l + b ) ) 2 + C * u = 1 m L ˜ ( y u ( w x u + b ) ) until convergence of y i * , n + 1 i n + m (4.5)

使用凹凸优化方法的优势就是能够对原来的非凸函数进行替换,将其替换成凹凸函数之和,大大简化了求解的复杂程度;但是存在的缺陷就是无法更好的利用原有的样本分布信息。

5.3. 基于标签传递的分类方法

采用标签传递的方式进行分类,标签传递的分类方法相当于聚类方式直接进行无标签样本分类,并与原数据进行训练,从而得到最终的决策函数,其主要的思想可以表示为 [9]:

对所有有标签的样本和无标签的样本进行构图,如果构建的图距离原来的标签样本越来越近,则说明与标签样本的类别相似,可以表示为:

T i j = P ( j i ) = w i j k = 1 l + u w k j (4.6)

w i j 表示图中样本点距离。

repeat Y T Y

Y U 表示无标签样本,通过迭代求解的方式让其收敛,然后在 Y U 中选择其他类的无标签样本,并指定为该类别。其优势就是考虑到训练样本中存在的流形,采用构图的方式进行聚类,然后使用分类器进行整体分类;但是缺陷就是构图完成后,这张图的效果是影响整个作品的关键,只能够通过寻找这种流形的方式进行聚类,在构图的过程中选择相邻点容易出现模糊的情况,对分类精度的标签样本影响较大。

基于相似度标签传递的半监督支持向量机

半监督分类算法有聚类假设和流形假设两种方式,有标签的训练样本无法更好的描述整个样本空间的实际情况,如果只是用标签样本进行训练则分类的精度较低,不能更好的更新更多的数据。而大量的无标签样本则有可能更好的反映出整个样本空间的真实情况。因此,引入无标签样本能够更好的指导分类器的整个训练过程,从而提高分类器的精度。在进行标注的过程中,如何选择无标签样本则是需要重点考虑的问题。可以通过迭代的方式进行标注,通过其纠错能力解决这个问题。

用训练样本构建一个相似度图,数据表示节点,对所有的数据进行连接,如果两点之间的相似度较大,则相应的权值就越高,计算方法为 [10]:

d i , j = e x i x j 2 t (4.7)

Figure 6. Approximately filter points with the same label according to similarity

图6. 按照相似度近似筛选可能相同标签的点

通过该公式构建了一个含有所有样本点的矩阵,该矩阵会受到t的影响,在取值的过程中需要适当的考虑向量机中径向基核函数的参数。

在进行标签传递的过程中,可以使用相似度的方式进行数据点的筛选,类似于聚类思想中的标签,但是与聚类思想不同的是在开始时没有使用聚类思想进行类别的划分,而是通过归纳式的支持向量机的方式进行结果的训练,将其作为标签传递的方向,并找到所有与其类别相同的数据点,这样做的目的就在于必须限定正负类比例的问题,才能够更好的完成数据的分类。通过新的标签样本重新定义决策函数,这种逐渐加入的样本信息,能够让决策函数变得更加完善。如图6所示。

6. 结束语

对提出的半监督支持向量机规划问题中所采用的两种凸锥松弛方法,能够更好地得到原混合正数规划问题的下界,从而得到更为准确的下界。对半监督支持向量机的分类方法进行了讨论与研究,在标签样本较少的情况下,可以使用无标签样本的方式提高分类的准确度,并在支持向量机的基础上进一步学习半监督学习方法。改进的半监督学习分类算法在失去平衡的情况下依旧能够发挥出其作用,用标签传递的方式对无标签样本进行标记,并在可能出现错误的地方进行标注和纠错,从而寻找到无标签样本中更合适的比例。

基金项目

新疆师范大学优秀青年教师科研启动基金资助项目(XJNU202012)。

参考文献

[1] 李村合, 朱红波. 基于半监督学习的多示例多标记E-MIMLSVM+算法[J]. 计算机工程与应用, 2018, 54(2): 149-154.
[2] 尤辉. 基于多示例多标记支持向量机的网页分类技术研究[D]: [硕士学位论文]. 杭州: 浙江理工大学, 2018.
[3] 卢纪丽. 基于半监督学习的木材识别研究[D]: [博士学位论文]. 济南: 山东大学, 2015.
[4] 李宇峰. 半监督支持向量机学习方法的研究[D]: [博士学位论文]. 南京: 南京大学, 2013.
[5] 孙云霄, 方健, 马小平. 基于半监督学习和支持向量机的煤与瓦斯突出预测研究[J]. 工矿自动化, 2012, 38(11): 40-42.
[6] 徐庆伶, 汪西莉. 一种基于支持向量机的半监督分类方法[J]. 计算机技术与发展, 2010, 20(10): 115-117.
[7] 林宣民. 基于局部敏感哈希和支持向量机的半监督增量学习研究[D]: [硕士学位论文]. 杭州: 浙江工业大学, 2017.
[8] 袁春琦, 徐佳, 程圆娥, 等. 基于协同训练与集成学习的极化SAR图像半监督分类[J]. 遥感技术与应用, 2017, 32(2): 380-385.
[9] 张艳丽. 基于多示例多标签支持向量机的网页分类方法[D]: [硕士学位论文]. 青岛: 中国石油大学(华东), 2014.
[10] 李远肇, 王少博, 李宇峰. 面向类别比例偏移的半监督支持向量机方法[J]. 模式识别与人工智能, 2016, 29(7): 625-632.