基于标记特定特征和相关性的ML-KNN改进算法①

李 永,许 鹏

(北京工业大学 软件学院,北京 100124)

传统监督学习认为一个对象只具有一个标记类别,属于“单示例,单标记”类型.在上述单一语义的情境中,监督学习已经取得了巨大的发展成果.然而在真实世界中,一个对象往往同时具有多种语义信息,属于“单示例,多标记”类型.例如在一篇新闻稿中可同时包含改革和经济两个主题,一张风景图中天空和云朵往往会伴随出现,在这种情况下很难用单一语义标记去描述对象信息.为此,多标记学习框架应运而生,用于解决真实世界中一个对象同时具有多个语义标记的问题.因其可以良好的反映真实世界中包含的多语义信息,目前在文本分类[1],图像标注[2],生物基因分析[3]等领域得到了广泛应用.同时众多学者也提出了一些多标记学习算法,并取得了一定的成功.但是目前大部分已有的多标记学习算法所采用的共同策略是基于同一特征属性空间预测所有标记类别,忽略了每个标记独有的特征信息,因此这种思路存在改进优化的空间.其中ML-KNN[4]作为一种使用简单,分类性能优异的多标记学习算法,其数学形式相对简单,模型易于优化,在实际应用和学术科研中得到了广泛应用.但是ML-KNN算法在模型训练过程中并没有考虑标记之间的相关性,同时也忽略了标记特定特征信息.因此,在模型训练过程中考虑标记相关性和引入标记特定特征信息,可以进一步提高算法的分类性能,基于此提出了本文算法.本文的整体组织结构如下:第1 部分介绍相关工作,第2 部分描述本算法的实现,第3 部分给出实验以及实验结果,最后进行了总结.

1 相关工作

在传统“单示例,单标记”的单语义环境中,传统监督学习已经取得了巨大的发展[5–8].然而在真实世界中,语义信息往往是丰富多彩的,传统监督学习已经不能对同时从属于多个标记类别下的单个示例进行很好的语义表达.相比于传统监督学习,多标记学习可以更好的反映真实世界中包含的语义信息.不同于传统监督学习所假设的“单示例,单标记”情形,多标记学习所研究的任务场景属于“单示例,多标记”类型.我们假设X=Rd代表d维特征空间,Y={l1,l2,···,lq}代表包含q个标记类别的标记空间.多标记学习的任务是在训练集D={(xi,Yi)|1≤i≤m} 中训练一个分类器h:X→2Y,预测未知示例x∈X 所从属的标记集合h(x)⊆Y,其中xi∈X为特征空间中的一个示例,是一个d维特征向量,Yi∈Y 为示例xi所从属的标记集合,是标记空间 Y中的一个子集.

目前多标记学习研究所面临的主要挑战是标记空间爆炸性增长的问题[9].即类别标记集合数随着标记种类的增加而呈指数级增长,假设样本中包含有q个类别标记信息,则标记输出空间规模即可达到 2q级别的大小,为每个标记子集单独训练一个分类器是不切实际的.为了解决这个标记空间爆炸的问题,目前关于多标记学习的研究大都集中在通过挖掘标记之间的相关性来降低指数级别增长的标记空间.根据标记相关性的利用策略,可以将多标记学习算法分为3 类:(1)一阶策略,完全忽略标记之间的相关性,只是将一个多分类问题转换为多个独立的二分类问题,这类方法虽然实现简单但是缺少良好的泛化性能.(2)二阶策略,考虑标记之间的成对关联,例如相关标记与无关标记之间的排序关系,两两标记之间的交互关系等构造多标记学习框架.这类算法具有一定的泛化性能,但是无法很好的解决标记之间的关系超过二阶时的问题.(3)高阶策略,考虑单个标记与其它全部标记之间的相关性,这类算法可以很好的反映真实世界的标记相关性,但同时模型复杂度往往较高.目前众多学者也提出了一些多标记学习算法,例如由Boutell 等提出的一阶策略算法BR (Binary Relevance)[10],由Fürnkranz 等提出的二阶策略算法Calibrated Label Ranking[11],由Read 等提出的高阶策略算法Classifer Chains[12]等.上述算法的共同点是将多分类问题分解为多个二分类问题进行解决,属于问题转换型.由Clare 等提出的一阶策略算法ML-KNN,ML-DT[13]和Elisseeff A 提出的二阶策略算法Rank-SVM[14]等算法是采用当前的机器学习算法直接处理多分类问题,属于算法适应型.但无论是问题转换型算法还是算法适应型算法,上述提到的算法在预测标记时都是假设所有标记共享同一特征空间,并未对每种类别标记独有的特征信息进行考虑.即多标记学习框架得到的q个实值函数 {f1,f2,···,fq}都是基于相同的属性特征空间训练而来.但是这种思路可能并不是最优的,例如在图像识别领域,在判断“天空”和“沙漠”时,颜色特征是需要优先考虑的,而在判断“蓝天”和“大海”时,考虑纹理特征相关属性会大大提高分类器的性能.由此可见,每个标记都可能具有与其最大相关性的属性特征,考虑每个标记独有的属性特征对于提高算法分类性能具有一定的帮助,这些属性特征是对该标记最有区别度的特征,称为标记特定特征信息.

其中,ML-KNN 作为一种使用简单,分类性能高效的算法,在实际应用中得到了广泛应用.但是ML-KNN算法属于一阶策略,并未对标记之间相关性进行考虑,同时也没有考虑标记特定特征信息.虽然该算法取得了巨大的成果,但是并未对标记相关性和标记特定特征信息加以利用,存在优化改进的空间.由Zhang 等提出了LIFT 算法[15]首次提出从引入标记特定特征信息这一角度出发的研究思路,针对每一个标记信息提取其特征信息,从而构建标记特征空间,之后基于标记特征空间进行模型训练.该算法基于多种公开数据集证明了其思路的有效性,为多标记学习指明了一个新的研究方向.但是该算法并未考虑标记之间的相关性,属于一阶策略算法.基于此,我们通过融入标记相关性和引入标记特定特征信息对ML-KNN 算法进行改进,进一步提高算法分类性能.

2 ML-KNN 算法以及改进算法

2.1 ML-KNN 算法

ML-KNN 算法是在k近邻算法的基础上,综合贝叶斯理论提出的能够处理多标记分类问题的KNN 算法.在此引入一些符号用于对该算法进行说明.在多标记训练数据集D={(xi,Yi)|1≤i≤m} 中,xi∈X,Yi∈Y,Yx为示例xi所对应的q维标记向量.如果示例x具有类别标记l(1≤l≤q),则定义Yx(l)=1,否则Yx(l)=0.另外假设N(x)代表示例x在训练集D中的k个近邻集合,对这k个近邻集合中拥有标记l的样本数量用Cx(l)表示,其中:

其中,Cx代表了示例x所对应的k个近邻集合中所包含的标记信息.ML-KNN 算法为懒惰算法,当有新的测试示例t需要进行预测分类时,ML-KNN 首先识别示例t在训练数据集D中的k个近邻集合N(t),在这里设定H1l代表示例t拥有标记l,相反,当示例t没有标记l时用H0l表示.另外引入Elj表示在N(t)中有j个示例拥有标记l,其中j∈{0,1,···,k},基于向量Ct,示例t所对应的类别向量Yt可以使用如下最大后验概率来计算.

该式所代表的含义为已知在测试示例t的k个近邻集合中有Ct(l)个样本与标记l相关,示例t与标记l是否相关取决于N(t)中是否与标记l相关的最大概率.根据贝叶斯规则,上式可以进一步变换为:

由上述公式可知,计算Yt(l)需要得到先验概率和条件概率这两个值都是可以从训练数据样本计算得到的.

2.2 基于ML-KNN 算法的改进算法

LIFT 算法是由张敏灵等学者在研究多标记学习算法时提出的一种全新的算法.该算法不同于之前研究点集中于挖掘标记之间相关性上,而忽略了标记特定特征信息.LIFT 算法从挖掘标记特征这一角度出发,针对每一个标记类别,通过挖掘其特征信息构建标记特征空间,在模型训练过程中引入标记特征,并且经过大量实验表明LIFT 算法分类性能在公开数据集上优于其它多标记学习算法,同时也证明了在模型训练过程中引入标记特定特征信息提高算法分类性能这一思路的有效性,为后续多标记学习研究提供了一种新的思路.

2.2.1 LIFT 算法基本模型

LIFT 算法通过对训练样本中的每个类别标记进行聚类操作,分析每个标记的特征信息,将原始样本集合根据特征标记划分为与当前标记呈正相关的样本和负相关的样本.具体来说,对于标记lj∈Y,根据式(4)和式(5)分别计算其正相关的示例集合Pj和负相关示例集合Nj.

其中,Yi表示实例xi所对应的标记向量,D为训练数据集,Pj代表包含标记lj的示例集合,Nj代表不包含标记lj的示例集合.之后采用K-means 聚类算法分别对两个示例集合进行聚类操作,得到在Pj上的个聚类中心和在Nj上的个聚类中心为了解决聚类中心不平衡的问题,LIFT算法设定mj==,其中这两个聚类中心集合分别代表着正负相关示例集合的内在特征结构,可作为构建标记特定特征空间的基础.为了构建标记lj的特定特征空间Zj,采用如下映射φj:X→Zj,φj表达如下:

其中,d(·,·)代表两个向量之间的欧式距离.根据映射φj,可以将原始训练数据集D转换为标记lj对应的二分类训练集Z.之后在新的训练集Z上进行模型的训练,可以构建出一个基于标记特定特征推导出的二分类器簇一般地,对于标记lj∈Y,其对应的二分类训练数据集可由映射φj表示为:

其中,如果标记lj∈Yi,Yi(j)=1,否则Yi(j)=0.基于训练数据集,可推导出一个分类器:Zj→R.对于未知示例u,其对应的标记集合可以形式化的表示为其中t代表一个阙值函数,一般设置为常数0.

2.2.2 MLF-KNN 算法

ML-KNN 算法属于一阶策略算法,在模型训练过程中没有考虑标记之间的相关性信息,同时在预测标记时是基于相同的属性特征集合,忽略了每个标记所独有的属性特征信息,因此ML-KNN 算法存在优化改进的空间.LIFT 算法经过大量实验表明该算法的分类性能与其它多标记学习算法相比具有一定的竞争力,证明了在模型训练过程中引入标记特定特征信息可以提高算法分类性能这一思路的可行性和有效性.为此,我们借鉴该思路,对ML-KNN 算法进行改进,并且融入标记相关性信息,提出基于标记特定特征新的多标记分类新算法MLF-KNN (Multi-Label Feature-K Nearest Neighbor).本算法首先对多标记训练样本集合进行预处理,通过对每个类别标记进行聚类分析构建基本标记特征,之后通过稀疏正则化的方式协同增强与其它类别标记的信息从而增强对每个标记特征信息的表述,进而引入当前标记与其它标记之间的相关性.基于得到的标记特定特征,使用改进后的ML-KNN 算法进行分类.不失一般性,引入一些符号进行本算法的说明.在模型训练之前,首先需要构建每个标记所对应的正负相关示例集合.对于训练样本中的每个标记lk∈Y(1≤k≤q),MLF-KNN 算法根据式(4)和式(5)将原始示例集合分为mk个 正相关特征集合Pk和mk个负相关特征集合Nk,其中mk=r·min(|lk∈Yk|,|lk∉Yk|).之后在集合Pk>和Nk中采用K-means 聚类算法构建聚类中心,用于构建基本标记特征空间.在正相关示例集合Pk中聚类中心可以通过表示,负相关特征集合Nk中聚类中心可以通过表示.对于示例x∈X,可通过计算示例x与聚类中心之间的距离构建其基本标记特征,最终生成的基本标记特征空间是一个大小为2mk的矩阵φk:X→R2mk.

其中,d(·,·)不在采用LIFT 算法中的欧式距离进行度量,而是采用标准欧式距离进行计算,相比于欧式距离,标准欧式距离对于两个向量中的维度不一致的情况进行了考虑,对于维度不一致的示例具有更好的包容性,根据式(7),生成标记lk的基本特定特征空间.此时基本标记特定特征空间只是针对标记lk所构建,并未考虑lk与其它标记之间的相关性.假设代表标记向量lk,类似的,如果lk∈Yi,则yki=1,否则yki=0.进一步,设定:

其中,φk(x)表示除标记lk以外的其它所有类别标记的特定特征信息,是一个维度为dk的特征向量,其中dk=将映射 φk应用于全部训练样本上,从而可以构建出关于标记lk并且维度为m×dk的标记特定特征矩阵Xk,其中为了解决ML-KNN 算法并未考虑标记之间相关性的问题,我们需要对标记之间相关性进行挖掘并将相关性信息引入标记特定特征空间中.具体来说,需要通过引入标记lk与其它类别标记之间的相关性对之前生成的基本标记特征空间Xk进行增强.在本方法中将标记之间相关性问题转换为最小二乘法优化问题,通过引入L1正则化项对其进行优化求解从而引入标记lk与其它类别标记之间的相关性,优化最小二乘法问题如下:

根据之前生成的基本标记特征空间 φk中的数值取值介于0 到1 之间,在此我们将阙值 γ设定为常数值0.5.对于标记lk,通过融合标记相关性信息后对基本标记特征进行增强,即可生成最终标记特定特征ψk:X→Zk,其中ψk(x)表示形式如下:

针对训练样本中的每一个标记类别分别构造其特定特征空间,在标记空间集合中应用改进后的ML-KNN算法进行模型训练,其中在计算两个标记之间距离时MLF-KNN 算法不同于ML-KNN 采用欧式距离直接计算,而是采用如下r阶Minkowski 距离进行计算[16].

其中,xl代表示例x的第l维,||·||表示取该实数值的绝对值.在计算两个样本之间的距离时采用Minkowski距离度量方法的主要出发点是考虑到不同数据集内数据可能具有不同分布从而需要采取不同的距离计算方法,采用Minkowski 方法可以提高本算法对不同数据集的包容性.当阶数取值为1 时,可以转换为曼哈顿距离.当阶数取值为2 时,可以转换为欧氏距离.当阶数继续增大到无穷大时可转换为切比雪夫距离.在本实验中所采用的数据集中的数据取值规范,分布较为独立,因此设定r值为2 转换为欧式距离进行试验.当数据集中的数据分布具有关联性或者局限性时,可以改变r值的取值以适配不同的数据分布.MLF-KNN 算法描述如算法1 所示.

算法1.MLF-KNN 算法步骤1.构造基本标记特征集.lk Y={l1,l2,···,lq}For in do利用式(4)和式(5)构建标记正相关样本集 和负相关样本集;End for lk Y={l1,l2,···,lq}For in do Pk Nk通过式(8)构建针对 的标记特征映射;lk φk End for

步骤2.增强基本标记特征集,构建标记特征.lk Y={l1,l2,···,lq}For in do通过对式(10)进行L1-范数正则化计算权重向量;βk通过式(11),式(12),构建最终标记特征;End for步骤3.构建二分类训练集.lk Y={l1,l2,···,lq}For in do Dk根据式(13)构建标记 的二分类训练集;End for步骤4.计算先验概率.lk Y={l1,l2,···,lq}For in do lk Dk计算标记 的先验概率:P(Hlb)(b∈{0,1},l∈Y)lk;End for步骤5.计算示例在标记特定特征空间中的k 近邻集合.xki Dk For in do通过式(14)计算k 近邻集合,从而根据式(1)计算N(x)Cx(l)End for P(ElCx(l)|Hl1)P(ElCx(l)|Hl0)步骤6.计算各类标记条件概率 和条件概率.步骤7.对待测样例t 进行分类,通过式(8)构建新的样本表达,分别在计算和,利用式(3)计算其对应的标记向量.tk DkN(t)Ct(l)Yt

3 实验

为了检验MLF-KNN 算法的分类效果,将本算法与ML-KNN,LIFT,Rank-SVM 等3 个多标记学习算法在公开酵母数据集yeast 和图像数据集image 上进行比较.其中ML-KNN 算法基于传统k近邻技术处理多标记问题,基于已有样本的先验概率,通过在训练样本中寻找距离最近的k个实例从而对未知示例进行标记预测.但是该方法没有考虑标记之间的关联信息,属于算法适应型一阶策略算法.LIFT 算法通过构造每一个标记独有的特征信息,基于标记独有的示例集合进行模型训练,是从标记特征信息研究的新型算法,但是同样没有引入标记之间的相关信息,也属于一阶策略算法.Rank-SVM 算法使用最大化间隔思想处理多标记问题,该算法的核心是通过一组线性分类器对Ranking Loss 指标进行优化,并通过引入“核技巧”处理非线性分类问题[9],属于算法适应型二阶策略算法.实验所采用的数据集yeast 和image 在多标记学习领域是两个公开的数据集,分别在生物领域和图像领域具有一定的代表性,两个数据集详细信息如表1所示.

表1 数据集详细信息

由于每个示例同时类属于多个标记,因此传统的单标记评价指标例如精度(accuracy)、查准率(precision)和查全率(recall)等指标不再适用.本文评价指标基于Haming Loss,One-error,Coverage,Ranking Loss,Average Precision[17]等5 种在多标记学习领域广泛使用的评价指标.其中,对于Average Precision 指标信息,数值越大代表分类性能越好,在表中使用 ↑表示,其余评价指标数值越小则代表其分类性能越好,在表中使用 ↓表示.表2为各个算法在数据集yeast 上的测试结果,表3为在数据集image 上的测试结果.本文提出的算法基于ML-KNN 改进而来,图1为MLF-KNN 算法与ML-KNN 算法在数据集yeast 上的随k值变化的Coverage 评价指标对比结果图

表2 本文算法与其它算法在数据集yeast 上的实验结果对比

表3 本文算法与其它算法在数据集image 上的实验果对比

图1 MLF-KNN 与ML-KNN 算法在数据集yeast 数据集随k 值变化的Coverage 变化曲线图

由图1可以看出,本文提出的算法相比于ML-KNN算法在Coverage 评价指标上表现性能十分优异,当k值继续增大时,Coverage 值可以接近最优解1.0,代表MLF-KNN 算法对于测试样本的预测所有相关性标记的平均查找深度小,分类性能有所提高.由表2和表3的对比实验结果图可以看出,本文所提出的算法MLFKNN 在数据集yeast 当中表现优异.反映在具体评价指标上,MLF-KNN 算法在One-error,Ranking Loss 和Average Precision 指标上表现不是最优,虽然Ranking Loss 指标上的表现低于LIFT 算法,但是相比ML-KNN算法而言该评价指标有所提高.在数据集image 中,本算法同样在评价指标Haming Loss 和Coverage 上表现最优.实验结果表明对ML-KNN 算法引入标记特定特征和标记相关性进行改进可以进一步提高算法分类性能,尤其在Coverage 上表现更为明显,同时也证明了从标记特定特征对算法进行改进创新这一思路的有效性.

4 结论与展望

ML-KNN 算法在模型训练过程中没有考虑到标记之间的相关性,同时在预测不同标记时基于同一特征空间,忽略了每个标记所特定的标记特征.LIFT 算法从利用每个标记所独有的特征出发,为多标记学习研究指明了一个新的方向.基于此,我们对ML-KNN 算法进行改进,在构造标记特征空间的同时对其进行增强,引入与其它标记之间的相关性,提高了算法分类性能.在之后的工作中,可以进一步对构建标记特征空间的方法进行创新,另外本算法并未对标记不平衡的问题进行考虑,当正负标记样本数量差异过大时会制约算法的分类性能,所以下一步工作可以将当前多标记学习领域对正负标记不平衡问题的研究[18]引入到本算法当中.