集成最近邻规则的半监督顺序回归算法

摘 要:监督型顺序回归算法需要足够多的有标签样本,而在实践中,标注样本的序数耗时耗力,甚至难以完成。为此,提出一种集成最近邻规则的半监督顺序回归算法。基于最近邻,针对每个有标签样本,在无标签数据集选择与其最近似的若干样本赋以相同序数;再由监督型顺序回归算法训练有标签样本和新标注样本。多个数据集的实验结果显示,该方法能显著改善顺序回归性能。另外,引入折扣因子λ评估新标注样本的可信度,并讨论了λ和有标签数据集大小对方法的影响。

关键词:半监督顺序回归;最近邻;无标签样本;折扣因子

中图分类号: TP181; TP391

文献标志码:A

Towards semi-supervised ordinal regression with nearest neighbor

HE Hai-jiang, HE Wen-de, LIU Hua-fu

(

Department of Computer Science and Technology, Changsha University, Changsha Hunan 410003, China

)

Abstract:

The supervised ordinal regression algorithm often requires large amounts of labeled samples. However, in the real applications, labeling instances is human resources consuming, and sometimes even unrealistic. It was presented that a semi-supervised ordinal regression algorithm which learned from both the labeled and unlabeled examples. The proposed method began by choosing some instances from unlabeled dataset that are most similar to one labeled example in labeled dataset, and assigning them the corresponding ranker. At this stage, the nearest neighbor rule was packed to score similarity of two instances. Then, by using supervised ordinal regression, the ranking model was trained from both the labeled and the newly labeled examples. The experimental results show this method produce statistically significant improvements with respect to ranking measures. In the other hand, discount factor λ was introduced for evaluating creditable degree of new labeled examples, λ and the size of labeled dataset how to affect the method performance were discussed.

The supervised ordinal regression algorithm often requires large amount of labeled samples. However, in the real applications, labeling instances is time and labor consuming, and sometimes even unrealistic. Therefore, a semi-supervised ordinal regression algorithm was proposed, which learned from both the labeled and unlabeled examples. The proposed method began by choosing some instances from unlabeled dataset that are most similar to one labeled example in labeled dataset, and assigning them the corresponding ranker. At this stage, the nearest neighbor rule was packed to score the similarity of two instances. Then, by using supervised ordinal regression, the ranking model was trained from both the labeled and the newly labeled examples. The experimental results show this method produce statistically significant improvements with respect to ranking measures. On the other hand, discount factor λ was introduced for evaluating creditable degree of new labeled examples, and how λ and the size of labeled dataset affected the method performance was discussed.

Key words:

semi-supervised ordinal regression; nearest neighbor; unlabeled sample; discount factor

0 引言

顺序回归能解决介于分类和数值回归之间的问题,广泛应用于协作过滤推荐[1]、自动评级等系统,是信息检索领域的重要课题。在基于统计的学习过程中,给定数据集S={(x,y)},x属于多维的输入空间,y属于输出空间R(往往一维)。在分类问题中,R是一个有限且元素间无序的集合;在数值回归问题中,R位于实数轴,并且连续;而在顺序回归问题中,R是一个有限且元素间存在顺序关系的集合,其元素无法用数值度量,只能两两比较。形式化地,将顺序回归输出值划分为v个序数,即R={r1, r2,…, rv},有rv>*…r2>*r1,其中>*是顺序关系,可解释为“比…优先”或“比…更相关”等。

PRank[2]是一个基于感知器的在线顺序回归算法,学习过程中,使训练样本的预测序数逐渐靠近真实序数。文献[3]中构造了v-1个平行的超平面(w,b1),…,(w,bv-1),将顺序回归问题归约成支持向量形式,通过决策函数f(x)=┆min1≤i≤v{ri:w*φ(x)-bi

已有的顺序回归算法都要求手工标记大量样本的序数,以构建足够大的训练集。但现实中标记工作耗时耗力,有时甚至难以完成,严重限制了顺序回归的实际应用。近年来,半监督技术在分类、回归、聚类、相关分析等领域得到深入研究,许多研究者用其解决各类学习问题。在文本分类任务中,ssPLSA扩展概率潜在语义分析模型[5],评估无标签样本的可能类别及误差概率,有效改善分类性能。基于近邻传播的半监督聚类算法[6]启发式地引入已知的标签数据或者成对约束,获得较好的聚类结果。Semi-CCA[7]在典型相关分析的应用中加入监督信息,利用样本间的正约束和负约束信息,并考虑大量无标签样本的隐藏信息。

随着Web应用和存储技术的发展,从互联网容易获取大量的无标签样本,如何挖掘这些样本隐藏的序数信息,还未见报道。受到半监督技术的启示,本文提出一种集成最近邻规则的半监督顺序回归算法,先针对每个有标签样本,计算未标注样本和它的欧几里得距离,选择若干最小距离的样本贴上相同标签;接着,由监督型顺序回归算法在有标签样本和新标注样本组成的训练集上学习。多个数据集的实验结果显示,相比只学习有标签数据集,本文的方法能显著改善顺序回归性能。用折扣因子λ评估新标注样本的可信度,探讨了λ对半监督顺序回归算法的影响。当然,本文也讨论了有标签数据集大小对算法性能的影响。

1 多项式平滑型支持向量顺序回归算法

若序数为ri的样本有ni个,n=n1+n2+…+nv是训练集的样本总数。令xi,j是序数为ri的样本集中第j个样本,i=1,2,…,v,j=1,2,…,ni;b=(b1,b2,…,bv-1),bi是第i个决策函数的阈值。依据结构风险最小化原则,在文献[4]的启发下,可求解问题(1):

┆minw,b,ξ,ε12(w2+b2)+C∑v-1i=1(∑ik=1∑nkj=1ξ2i,k,j+∑vk=i+1∑nkj=1ε2i,k,j)(1)

使得:

K(xTk,j,H)w-bi≤-1+ξi,k,j,ξi,k,j≥0;k=1,2,…,i,j=1,2,…,nk

K(xTk,j,H)w-bi≥1-εi,k,j,う弄i,k,j≥0;k=i+1,2,…,v, j=1,2,…,nk(2)

其中i=1,2,…,v-1。

依据通用核[8]的定义,假设A∈Rn×m,B∈Rm×o,则核K(A,B)将Rn×m×Rm×o映射为Rn×o。特别地,若x∈Rm为列向量,即样本x有m维属性,xT是x的转置向量,AT是A的转置矩阵,则K(xT,AT)∈Rn为行向量。由此,H=(x1,1,x1,2,…,x1,n1,…,x2,n2,…,xv,nv)∈Rm×n。

C是模型复杂度和经验风险间的平衡因子,ξ和ε是如图1所示的误差项。每个样本包含v-1个ξ或ε,分别对应v-1个决策函数,式(2)共有(v-1)×n个相关的误差项ξ或ε。

图片

图1 多个平行决策超平面形成的误差ξ和ε

多项式平滑型支持向量顺序回归算法psSVOR(注:该算法的优化方法、性能描述已另文发表。)是求解问题(1)的有效方法,采用psSVOR作为本文的监督型顺序回归算法。

┑4期 ┖魏＝等:集成最近邻规则的半监督顺序回归算法

┆扑慊应用 ┑30卷

平滑支持向量机[9]成功应用于分类和数值回归问题,引入其思路和正号函数(z)+=max (0,z),合并式(1)和式(2),问题(1)成为新的无约束问题(2):

┆minw,bλ(w,b)=12(w2+b2)+C∑v-1i=1(∑ik=1∑nkj=1(1+K(xTk,j,H)w-bi)2++∑vk=i+1∑nkj=1(1-K(xTk,j,H)唱w+bi)2+)(3)

(z)+不可微,为了直接用Newton法求解该问题,借鉴分段多项式光滑函数[10],定义p(z,η)和q(z,η)分别近似(1+z)+和(1-z)+:

p(z,η)=z+1,z≥-1+η

-116η3(z+1+η)3(z-3η+1),-1-η

0,z≤-1-η(4)

q(z,η)=1-z,z≤1-η

-116η3(z+3η-1)(z-1-η)3,1-η

0,z≥1+η(5)

式(4)、(5)中的η∈(0,1)。

将p(z,η)和q(z,η)代入式(3),psSVOR的优化目标为问题(3):

┆minw,b ψη(w,b)=12(w2+b2)+C∑v-1i=1(∑ik=1∑nkj=1p(K(xTk,j,H)w-bi,η)2+ぁvk=i+1∑nkj=1q(K(xTk,j,H)w-bi,η)2)(6)

令bv=+∞,问题对应的决策函数为f(x)=┆min1≤i≤v{ri:K(xT,H)*w-bi

2 允许新标注样本带折扣因子半监督顺序回归

设已标注数据集为XL,无标签数据集为XU。基于最近邻规则,对XL的每个元素,计算XU所有样本和它的欧几里德距离,选择h个最小距离的样本赋以XL元素相同序数,这h×|XL|个样本组成新的有标签数据集XN。引入折扣因子λ作为新标注样本的可信度,λ∈(0,1],半监督顺序回归算法在XL+XN上训练,优化目标为问题(4):

┆minw,b ωη(w,b)=12(w2+b2)+C∑v-1i=1(∑x∈XLErr(x)+う*∑x∈XNErr(x))(7)

其中:

Err(x)=∑ik=1∑x∈RS(k)p(K(xT,H)*w-bi,η)2+ぁvk=i+1∑x∈RS(k)q(K(xT,H)*w-bi,η)2

其中:RS(k)表示序数为k的样本集;Err(x)是x与v-1个超平面形成的误差,如图1所示,虚线表示的新标注样本x┆new与实线表示的有标签样本误差形式相同,除了误差乘以系数λ外。显然,λ=1时,新标注样本与初始已标注样本一视同仁,式(7)退化为式(6)。因为w不可能为零向量,且式(7)各个子项皆为平方项,显然ωη(w,b)是严格的凸函数,问题(4)有唯一最优解。采用类似文献[4]的方法,若问题(4)的最优解为(w*,b*),可证明:

b*1

限于篇幅,证明过程从略。

由于问题(4)的优化函数具有二次可微性,可用结合Newton法和YUAN[11]一维精确搜索的Newton-YUAN[12]算法求解出顺序回归模型。

3 实验结果及分析

平均绝对误差(Mean Absolute Error,MAE)和平均相对误差(Mean Relative Error,MRE)是评估顺序回归算法性能的常用工具。若n个样本的序数为u1,u2,…,un,经顺序回归模型识别为μ1,μ2,…,μn,则:

MAE=1n×∑ni=1μi-ui

MRE=1n×∑ni=1μi-uiui

3.1 实验数据集及实验步骤

表1是9个实验数据集的基本资料,带“*”的来自文献[4],带“#”的从www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets下载得到。MovieLens是一个电影评分数据集,在/taxonomy/term/14下载,所有数据集都经过归一化处理。

表格(有表名)

表1 实验数据集

数据集属性维数序数vа本数Ratio

Wisconsin*32519420

Machine*6520920

Autompg*7539220

Boston*131050620

Stock*95950100

LetterA#1663B443100

Satimage#3664B436100

Bank8FM*8108B192200

MovieLens22526B687500

П疚氖褂孟咝院K(x,H)=x和高斯核K(x,y)=e-g×∑dt=1(xt-yt)2完成实验。为比较算法的性能,设计两种基准算法,都是基于psSVOR的监督型方法,fullSVOR在XL+XU(XU所有样本贴上标签)上训练,subSVOR在XL上训练。而本文提出的半监督顺序回归算法称为hNN-SemiSVOR,其中h=1,2,3,4,5,6。设Ratio是初始已标注样本占总样本数的比例,在表1中,由数据集规模确定Ratio。

全部实验结果取十折交叉的平均值,每折执行相同步骤:将学习样本集划为四份,其中三份为训练集,一份为验证集;先由训练集学习顺序回归模型,再在验证集上检查MAE(MRE);多个参数组合(C和高斯核宽度)条件下执行上述步骤,获得最小MAE(MRE)对应的模型参数后,Ъ扑隳P凸赜诓馐约的性能。所有实验都在Pentium双核2.8@GHz,512@MB内存,Windows 2000环境中完成。

设定不同λ,无标签样本都能指导hNN-SemiSVOR,为简化问题,先令λ=1,Э疾hNN-SemiSVOR的顺序回归性能。

3.2 线性核的半监督顺序回归问题(λ=1)

Я浇锥翁粞∠咝元hNN-SemiSVOR的最优平衡因子C。先实验5个值,lg C=-3,-2,-1,0,1,获得最小MAE(MRE)对应的C*;再在C*、0.5C*、5C*中选择最优C。表2是三种算法在数据集的MRE表现,6NN+表示XU中6×|XL|个样本被标注后加入训练集,由hNN-SemiSVOR从新训练集学习顺序回归模型,其他1NN+,2NN+,…等类似。比subSVOR表现差的MRE值用下划线以示区别。

从表2可得出如下结论。

1)一般来说,挖掘无标签样本隐藏的信息,可辅助hNN-SemiSVOR提高性能。但这在Bank8FM和MovieLens上有些失效,因为在欧氏空间近似的样本其序数并不总是接近,用最近邻规则标注的新训练集包含许多噪声样本。

2)并非h越大,hNN-SemiSVOR性能越好。显而易见,欧氏距离的局限性和数据集样本特征的特殊分布性是这种现象的根源。

3)在大部分数据集上,h=1时,相对其他h值hNN-SemiSVOR的性能明显差些。因此,h可从2到6中任意选择。以MAE作为性能评估测度时,所得结果与此类似。

表格(有表名)

表2 线性顺序回归问题MRE的比较(Е霜=1)

数据集fullSVORsubSVOR1NN+2NN+3NN+4NN+5NN+6NN+

Wisconsin0.4280.6740.6390.6240.6550.5620.5940.593

Machine0.0720.1530.1330.0850.0830.0880.0800.082

Autompg0.1140.1800.1650.1680.1720.1780.1690.173

Boston0.1680.2900.2790.2570.2410.2210.2380.237

Stock0.1370.2620.2530.2120.2040.2060.1980.186

LetterA0.2510.3380.3300.3160.3140.3160.3140.311

Satimage0.1830.2020.1960.1910.1980.1910.1880.192

Bank8FM0.1080.1530.1400.1550.1500.1430.1480.159

MovieLens0.3060.3450.3410.3480.3440.3470.3450.345

3.3 高斯核的半监督顺序回归问题(λ=1)

Р捎们短椎木匀设计实验方法[13]搜索高斯核顺序回归模型的最优参数。假设β1和β2是数据集两个最靠近的样本,令ρ=┆min│陋1≠β2(β1,β2)2,高斯核宽度g的范围设为10-3/ρ~1.9/ρ。平衡因子C的范围为10-2~104。依据www.math.hkbu.edu.hk/UniformDesign提供的均匀设计模式,首阶段实验9个参数,从中选择使得MAE(MRE)最小的(C*,g*)后,第二阶段再以(C*,g*)为中心,实验其周围的4个参数,最后从5个参数对中选择使得MAE(MRE)最小的(C**,g**)作为模型的最优参数。表3是三种算法在数据集上的MAE表现,每种算法都取各自的最优结果。依据3.2节的结论,未考虑1NN+的情形。

表格(有表名)

表3 高斯核顺序回归问题MAE的比较(Е霜=1)

数据集fullSVORsubSVOR2NN+3NN+4NN+5NN+6NN+

Wisconsin1.0651.2331.2851.1691.3421.1301.208

Machine0.1700.3890.2120.2480.2850.2570.234

Autompg0.2340.3720.4020.4340.3950.4160.374

Boston0.4561.1351.0451.0381.1181.1371.129

Stock0.1110.5700.5230.4160.4450.4480.478

相比线性问题,非线性的hNN-SemiSVOR表现要差些,因为最近邻规则是基于线性空间的。尽管如此,hNN-SemiSVOR在总体上仍然优于subSVOR。由于psSVOR的局限,其余几个数据集训练时间过长,无法得到fullSVOR的结果。从算法在Autompg上的表现看,半监督技术并不总是有效,无标签数据并不保证提高学习能力,这与半监督技术在分类、数值回归等领域得到的结论相同。以MRE作为性能评估测度时,得到相同结论。

3.4 λ对算法的影响

图2是λ对hNN-SemiSVOR的影响,λ∈(0.1,1),h则固定为5,Ratio为表1的值,搭配数据集、核类型、性能测度后,随机选择了6种组合的实验数据。图例项的说明以组合Stock+Line+MAE为例,它表示:在数据集Stock上,用线性的hNN-SemiSVOR(Kernel对应高斯核),以MAE为性能测度。从图2可看出,大部分组合下λ对算法影响较大,每种组合的最合适λ各不相同,多数情况下λ=1并非最佳。如果λ的训练不方便,从0.5~0.9中任意选择不失为一个简单有效的方法,以图2为例,除Bank8FM+Line+MAE外,λ∈(0.5,0.9),使得算法hNN-SemiSVOR的性能相对较优。

3.5 初始标注样本集大小对算法的影响

图3是初始标注样本集大小对算法的影响,λ=1,h=2,随机选择了6种组合的实验数据,图例项的组合与3.4节相同。针对Boston、Autompg,设step=2,其他数据集step=10,对应初始标注集指标rts的Ratio=表1的Ratio×1.5-step×rts;对Bank8Fm来说,当rts=4时,初始标注集是数据集的1/(200-10×4),Ratio=160。一般来说,Ratio越小,初始标注样本越多,hNN-SemiSVOR的性能越好;但另一方面,初始标注样本越多,就越难找到与其近似且序数相同的样本,h越大,进入XN的噪声就越多,性能越可能下降。图3验证了这一点。

图片

图2 λ影响hNN-SemiSVOR的性能

图片

图3 初始标注样本集大小对算法的影响

4 结语

本文提出了一种集成最近邻规则的半监督顺序回归算法,利用大量容易获取的无标签数据集改善顺序回归性能,降

低标注训练集的成本。Р还新标注样本并非完全可信任,用折扣因子λ评估新标注样本的可信度时,大部分数据集受λ

的影响。当然,初始标注样本集大小对算法也有影响,它和算法的另一重要参数h共同影响算法的性能。

参考文献:

[1]YEHUDA K. Collaborative filtering with temporal dynamics [C]// Proceedings of 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM Press, 2009: 447-456

.

[2]CRAMMER K, SINGER K. Pranking with ranking [C]// Proceedings of the 15th Annual Conference on Neural Information Processing Systems. Cambridge, MA: MIT Press, 2001: 641-647

.

[3]SHASHUA A, LEVIN A. Ranking with large margin principle: Two approaches [C]// Proceedings of 16th Annual Conference on Neural Information Processing Systems. Cambridge, MA: MIT Press, 2002: 937-944

.

[4]CHU WEI, KEERTHI S S. Support vector ordinal regression [J]. Neural Computation, 2007, 19(3): 792-815

.

[5]KRITHARA A, AMINI M R, RENDERS J M, et al. Semi-supervised document classification with a mislabeling error model [C]// Proceedings of the 30th European Conference on IR Research. Heidelberg, Berlin: Springer, 2008: 370-381

.

[6]肖宇,于剑.基于近邻传播算法的半监督聚类[J].软件学报,2008,19(11):2803-2813

.

[7]彭岩,张道强.半监督典型相关分析算法[J].软件学报,2008,19(11):2822-2832

.

[8]MANGASARIAN O L. Generalized support vector machines [C]// Advances in Large Margin Classifiers. Cambridge, MA: MIT Press, 2000: 135-146

.

[9]LEE Y J, MANGASARIAN O L. SSVM: A smooth support vector machine [J]. Computational Optimization and Applications, 2001, 20(1): 5-22

.

[10]袁玉波,严杰,徐成贤.多项式光滑的支撑向量机[J].计算机学报,2005,28(1):9-17

.

[11]YUAN YA-XIANG. Step-sizes for the gradient method [C]// Proceedings of the 3rd International Congress of Chinese Mathematicians. Providence, RI: American Mathematical Society, 2004: 785-796

.

[12]何海江.代价与样本相关的简约核支持向量机[J].计算机应用, 2008,28(11):2863-2866

.

[13]HUANG C-M, LEE Y-J, LIN D K J, et al. Model selection for support vector machines via uniform design [J]. Computational Statistics and Data Analysis, 2007, 52(1): 335-346