基于自步学习的自适应半监督聚类算法

贾乐瑶,马盈仓,邢志伟,蒙莹莹

(西安工程大学 理学院,陕西 西安 710048)

现在正处于一个大数据时代,数据多且繁杂。在数据集中存在少量的标签数据以及大量的无标签数据,人工标记这些无标签数据需要消耗大量的人力及时间。因此,半监督学习被提出用来标记无标签数据。近些年来,半监督聚类算法得到越来越多的关注,并应用到了许多领域[1-3]。

一般情况下, 半监督聚类算法分为以下3类[4]: ①基于约束的半监督聚类算法(简称CBSSC)[5-7],该类算法在传统聚类的基础上加入了必连和不连的成对约束限制,从而达到增强聚类效果的目的。在聚类过程中,具有必连约束条件的样本会被分配到同一个类中,具有不连约束条件的样本会被分配到不同的类中。②基于距离的半监督聚类算法(简称DBSSC)[8-10],该类算法在数据的预处理阶段,通过学习一个自适应度量或构造某种距离度量来刻画样本间的相似性。这个新的度量函数能使数据集的类内样本距离尽可能小,类间样本距离尽可能大。③基于约束和距离相结合的半监督聚类算法(简称CDBSSC)[11-12]，该类算法结合了前2类算法的优点,因而可以获得更好的聚类效果。

自步学习(self-paced learning,SPL)[13]的灵感来源于教师对学生的教学,即先教授简单的概念,后教授复杂的概念,以一种自定节奏的方式,从简单的样本到复杂的样本,逐步地学习模型。自步学习自从被提出以后,就受到了广泛的关注和研究。Wang等提出了一种自步和自一致协同训练的深度学习方法[14],运用自步学习策略来进行协同训练,使得训练后的神经网络能够最先关注较容易分割的区域,然后逐渐考虑较难分割的区域;Shi等提出了一种新的多视图自适应半监督特征选择(MASFS)算法[15],该算法在半监督特征选择中引入自步学习(SPL),使得拉普拉斯权值图能够根据当前预测信息自适应变化;Chen等提出了一种自适应图学习半监督自节奏分类(AGLSSC)方法[16],该方法将自步学习(SPL)和自适应图学习(AGL)集成到一个联合框架中,并增加一个衡量样本重要性的参数来自动选择需要导入的样本。目前自步学习已经成功应用到多个领域且都获得了良好的效果[17-18]。

目前,大多数半监督聚类方法在构建邻域图时忽略了样本间的差异性,即在模型的训练过程中同等对待所有的样本。基于前面的讨论,本文将自步学习的思想运用到半监督聚类中,在聚类的过程中,对样本有顺序地进行聚类。同时,为了提升本文算法的鲁棒性,我们采用了一种自适应损失函数,最终提出了基于自步学习的自适应半监督聚类算法(ASSCSPL)，主要特点表现为:

1)该方法在每次算法更新时,利用自步学习为不同样本赋予不同的权重,使模型更注重可靠样本而不是全部样本。在这种情况下,将噪声对模型的影响减小。因此,该分类器对噪声具有鲁棒性;

2)通过标签传播,将标签信息从有标签数据传播到无标签数据,从而更有效地对无标签数据进行标记,提高了模型的学习性能;

3)使用自适应损失函数,增强了模型对具有较小的或者较大损失的数据的鲁棒性。

1 相关工作

1.1 自步学习

g(νi,λ))，

其中,λ是自步参数,g(ν,λ)是自步函数,用来控制自步学习的进程。

一般自步函数需要满足以下条件[20]:

1)g(ν,λ)关于ν∈[0,1]是凸的;

2)ν*(λ,l)关于l是单调递减的,且当l→0时,ν*(λ,l)→1,当l→∞时，ν*(λ,l)→0;

文献[20]中证明了该函数满足上述自步函数的条件,这里就不加赘述。

1.2 自适应损失函数

(1)

其中，σ为自适应参数,xi为向量x的第i个元素。不同σ值(σ=0.1、5、10)下的自适应损失函数如图1所示。可以看出,σ范数损失函数介于L1范数和L2范数之间,能兼具二者的优势。此外,式(1)中的损失函数具有以下性质：

A σ=0.1; B σ=5; C σ=10

1) ‖x‖σ是二阶可导的;

3) 当xi≥σ时,‖x‖σ→(1+σ)‖x‖1;

4) 当σ→0时,‖x‖σ→‖x‖1;

此外,文献[21]中还将自适应损失函数从向量扩展到矩阵并给出了详细的描述。

2 模型的建立

给定数据集X=[x1,x2,…,xn]∈Rn×d,其中n为样本的个数,d为维数。那么,传统的谱聚类问题描述如下，

传统谱聚类是无监督的,在已知部分标签的情况下,可以将无监督聚类扩展到半监督聚类。本文通过约束原始已知数据点的标签类别Yl与聚类后对应的标签类别Fl保持一致,其中l为已知标签的个数,利用标签矩阵Y调整F,使得F的结构更加规则,从而得到如下半监督标签传播算法，

s.t.Fl=Yl

(2)

矩阵迹的形式可以写成向量的形式,因此式(2)可以写为

s.t.Fl=Yl

(3)

众所周知, 传统的L2范数损失函数对异常值很敏感, 为了提高模型的鲁棒性, 本文在模型中引入对异常值不敏感的自适应损失函数‖X‖σ=

s.t.Fl=Yl

(4)

但上述模型并没有考虑到样本重要性的问题,为此,我们将自步学习的思想引入半监督聚类中,最终,在式(4)的基础上提出了一种基于自步学习的自适应半监督聚类模型，

s.t.Fl=Yl

(5)

式(5)为最终的模型,它不仅考虑了不同样本的重要程度,而且降低了噪声数据在标签预测过程中所产生的影响。

3 模型的求解

参考文献[21]给出了式(1)的优化过程,本文在式(1)优化的基础上给出了式(5)的优化求解算法。

3.1 一般自适应损耗最小化问题算法

由于(1)式难以优化,文献[21]提出了一种有效的算法来求解最优解。首先,提出一种更一般的自适应损失函数形式为

(6)

其中,gi(x)是一个向量输出函数。可以看出式(1)是式(6)的特殊情况。受文献[21]和[22]的启发,本文采用迭代重加权算法求解最小化问题(6)，通过求式(6)对x的导数,并令其导数等于0,可以得到

f′(x)+2(1+σ)

(7)

(8)

由于变量pi依赖于x,因此式(8)很难直接求解,但如果pi是固定的,则求解式(6)等价于求解以下问题，

(9)

其中,pi为过渡权重。因此,求广义问题(6)的最优解在算法1中提出。在算法1中,pi是根据当前的x计算的,而解x是通过求解式(9)来更新的。算法1的收敛性参见文献[21]。

算法1(6)式的优化过程

输入 数据向量x。

重复 1) 计算pi=(1+σ)

2) 通过解式(9)更新x。

直到收敛

输出x。

3.2 求解问题(5)的优化算法

根据算法1,问题(5)中提出的ASSCSPL目标函数可以改写为

s.t.

Fl=Yl

(10)

s.t.Fl=Yl

(11)

式(11)可写为矩阵迹的形式,因此,求解式(10)就等价于求解下式，

s.t.Fl=Yl

(12)

因此,对式(5)的求解就转化为对式(12)的求解,下面,本文将用交替迭代法对式(12)进行求解。

固定ν,更新F:则式(12)关于F的子问题为

s.t.Fl=Yl

(13)

可以得到式(13)的拉格朗日函数为

αTr((F-Y)′V(F-Y))。

对L(F)求关于F的偏导数,可以得到下面的式子，

通过矩阵的乘法准则,将上式展开可以得到

解得

(14)

固定F,更新ν:则(12)式关于ν的子问题为

上式可以写成向量的形式为

(15)

参数λ1和λ2的更新:λ2是自步学习的参数,当λ2较小时,只考虑损失值小的样本,随着λ2的值的增加,才会考虑到损失较大的样本,简单来说,λ2控制着每次迭代中加入学习的样本的个数。而λ1则控制重要程度为1的样本的个数。因此,自步参数λ1与λ2在迭代过程中都是逐步增大的,这样就控制了模型的学习进程。在本文中,我们将通过分别给λ1和λ2乘以μ和ρ来增大λ1和λ2的值,其中μ、ρ均为大于1的数。即λ1=μλ1,λ2=ρλ2,μ,ρ>1。

综上所述,ASSCSPL目标函数的优化求解过程如算法2所示。

4 实验

我们在6个公共数据集上对所提出的ASSCSPL算法进行性能评估,并将其与几种最先进的半监督聚类方法进行比较。

4.1 数据集

本文选取以下6个数据集进行对比实验:COIL20、Umist、YALE、yeast-uni、colon、tr11,其中COIL20为文本数据集,Umist和YALE为人脸图像数据集,yeast-uni为多标签数据集,colon为基因表达数据集,tr11为文本数据集，这些数据集的详细信息如表1所示。

表1 数据集

算法2基于自步学习的自适应半监督聚类算法(ASSCSPL)

输入 相似矩阵S∈R(n×n)，有标签样本的个数m，参数α，σ，λ1，λ2，μ>1，ρ>1

满足FTDF=I的F∈R(n×c)；

2) 通过式(14)更新F；

3) 通过式(15)更新v；

4) 更新λ1，λ2；

直到收敛或达到最大迭代次数

输出F∈Rn×c。

4.2 比较方法

在接下来的实验中,ASSCSPL算法将分别与GFHF、SODA、SFS、RGL、SEE、RLSR算法进行比较。下面将简单地对这6种算法进行介绍。

1) GFHF[23],将标记的和未标记的样本数据表示为一个加权图的顶点,用边权编码实例之间的相似性;

2) SODA[24],通过标签传播为无标签数据赋予标签,并且定义了基于标签传播学习的软标签的散射矩阵来进行判别分析;

3) SFS[25],一种广义不相关约束下的半监督特征选择方法,将岭回归扩展到广义不相关约束下的半监督特征选择;

4) RGL[26],一种新的鲁棒图学习方案,从真实数据中学习可靠的图;

5) SEE[21],一种自适应半监督弹性嵌入损失最小化算法,该算法在预测标签矩阵上使用弹性嵌入约束,并运用了一种新的自适应损失函数,使模型学习到更好的图;

6) RLSR[27],用一组度量因子重新调整最小二乘回归中的回归系数,对特征进行排序,使模型学习到投影矩阵的全局解和稀疏解。

4.3 实验设置

4.4 实验结果

本文以均值±标准差的形式展示最终的结果,所有方法在6个数据集上的ACC结果如表2～表4所示。

表2 l=3时所有算法的ACC结果(均值±标准差)

表3 l=5时所有算法的ACC结果(均值±标准差)

表4 l=10时所有算法的ACC结果(均值±标准差)

从表格中可以看出,我们提出的方法在大多数基准数据集上优于其他方法,这证实了我们提出的模型的有效性。

为了进一步验证所提算法的有效性以及标记样本数量对该算法聚类性能的影响,在YALE和colon这2个数据集上,将每个类中的标记样本数量分别设置为1到5个和1到10个,计算本文算法和对比算法的ACC值。在该实验中,其余参数分别设置为:α=1.5,λ1=0.01,λ2=0.02,μ=1.2,ρ=1.5。这些算法在不同标记样本数量下的ACC值如图2所示。从图2中可以看到,本文提出的算法(黑色三角线)总体上优于其他对比算法,且聚类精度也会随着已知标签数量的增加而增加。这证实了本文提出的模型的有效性。显然,我们提出的半监督聚类方法降低了噪声数据的影响,提高了半监督分类性能。

A YALE数据集; B colon数据集

4.5 参数的灵敏度测试

对于提出的ASSCSPL算法,本节将研究参数对实验结果的影响,本文所提出的聚类模型包括λ1、λ2、μ、ρ、α和σ6个调优参数,实验结果通过聚类精度(ACC)来评判。本文通过网格搜索方法,在[10-3，10-2，10-1,1,10,100,1 000]内设置参数α和σ的值,在[10-7,10-6,10-5,10-4，10-3,10-2,10-1]内设置参数λ1的值,λ2的值在[2×10-7，2×10-6，2×10-5，2×10-4，2×10-3，2×10-2，2×10-1]内设置,在[1.1∶0.1∶1.5]内设置参数μ和ρ的值。对YALE和colon数据集进行实验,记录不同参数下ACC的结果,以显示参数λ1、λ2、μ、ρ、α和σ对算法聚类性能的影响程度。值得一提的是,每个参数的ACC值都是在固定其余参数的情况下得到的。在YALE和colon数据集上的ACC结果分别见图3和图4,从这2幅图中可以观察到,当各参数设置为不同值时,ACC的值不会产生较大变化,由此可见,在YALE和colon这2个数据集上,所有参数对实验结果的影响不是很大。

图3 YALE数据集在不同参数值下的聚类精度(ACC)图像

图4 colon数据集在不同参数值下的聚类精度(ACC)图像

5 结语

本文提出了一种新的自适应半监督聚类方法，ASSCSPL可以为不同重要性的样本分配不同的权重,使算法能得到更好的聚类结果。另一方面,通过在模型中运用了σ范数,结合了L1范数和L2范数的优点,增加了模型的鲁棒性能。最后,在公共数据集上的实验表明了该方法的有效性。尽管ASSCSPL相比于其他的方法有一定的优势,能够给出较好的聚类结果,但仍有改进的空间。例如ASSCSPL所包含的参数较多,而对不同的数据集,我们需要通过调整参数来得到最优的结果,这就要花费大量的时间。希望在未来的研究中,能够提出一个参数较少的模型。