基于共现分析的分类器链标签序列优化方法

赖德迪,罗智徽,马应龙

(华北电力大学控制与计算机工程学院,北京 102206)

0 引 言

分类算法是机器学习中非常重要的研究课题。通过分类算法可以使得机器对所分析的研究对象自动划分种类,从而达到识别对象、认识对象特征的目的。在实际问题中,一个对象所属的类别往往不是单一的,而可能是同时属于多个类别的[1-2]。例如,在一些针对复杂化、信息化的大型装备的故障检测任务中[3],一组设备的状态监测数据异常极有可能是因为制动器、齿轮箱、扭矩传感器、驱动电机中的一个或多个部件故障引起的,因此该异常事件可以同时对应一个或多个故障类别。这种为每个对象准确预测其所有可能类别的分类方法称为多标签分类[4]。而传统的分类方法只是为每一个对象准确预测一个类别标记。

多标签分类的难点主要表现在以下方面。首先,每个对象需要预测的标签数量通常是不确定的,有的对象可能只有一个分类标签,而有的对象的标签数量却可能很多[5]。虽然一些多标签分类算法当前已经被应用于图像多目标检测识别等领域,但现有的多标签分类方法在总体分类准确率等方面还有待提高,特别是在标签数量很多的情况下进行准确的多标签预测是一个具有挑战性的问题。其次,高准确率的多标签分类需要深入挖掘标签之间的潜在关联或依赖关系。因为在进行多标签分类时,大多数的标签之间通常存在着正向或负向的相关性。例如在多标签图像目标识别的任务中[6],如果一张图像中包含了战斗机、轰炸机、预警机等多个不同类型的目标对象,一旦识别出图像中的这些目标对象,则该图像会被同时标记为“战斗机”“轰炸机”“预警机”等类型标签。因此,如何分析和挖掘多个标签之间的潜在关联或依赖关系是多标签分类的另一大难点。

现有的多标签分类方法大致基于两种策略,分别是算法适应策略[7]和问题转换策略[8]。算法适应策略将多标签分类问题转换成聚类[9]等其他形式的问题进行处理。例如基于K最近邻思想的多标签分类方法[10],其对于每个测试样本,在训练集中找到其K个近邻,然后基于邻居样本的统计信息,采用最大后验概率决定测试样本的标签集合。另一种基于标签排序校准的多标签分类方法[11]则依据测试样本在每个标签分类器上得到的值为1(或0)进行加分(或减分)。最后按照分值大小进行排序,取分值靠前的多个标签作为当前测试样本的标签集合。但由于该类算法需要对每两个标签之间训练一个分类器,使得算法时间复杂度较高,在标签数目较多的任务上难以展开。近来也有学者在信息论的基础上对于多标签分类算法模型进行改进[12-13],该类改进算法借助于嵌入特征选择的方法对样本特征进行筛选。通过去除样本中冗余的特征,保留有效特征的方式,来减少无关特征对分类结果的影响,从而达到优化的效果。然而去除特征或多或少会减少了原样本的实例信息,并影响分类器训练的收敛速度和最终的分类性能。

问题转换策略则主要将多标签分类问题拆解成一个多分类问题或多个二分类问题,从而简化多标签分类任务。其代表性的方法,如标签幂集算法[14-15],其将原问题转换为选择标签集合中一个子集,并以此来作为测试样本的标签预测集。其充分考虑了给定标签集合可能的组合情况,但由于标签集合所包含的子集数量往往十分庞大,因此该算法在标签数目较多的情况下,时间复杂度极高。上述算法无疑都显示了多标签分类的潜力,部分算法也已经被应用于文本分类[16-18]、媒体内容标签[19]、在线处理[20]、蛋白质和基因组预测[21-23]等应用领域。然而,基于算法自适应的多标签分类方法往往需要建立更复杂的学习模型来进行模型训练和实例标签的特征表示,并且往往具有较高的复杂度,而上述算法都难以在这样的任务中有较好的表现。

分类器链(classifier chains,CC)模型[24]作为一种最典型的基于问题转换策略的多标签分类算法,因其简单易用而得到广泛地应用和发展[25-26]。CC模型基于二元相关性(binary relevance,BR)[27]原理,对每个标签都训练一个二元分类器,所有样本在每个分类器上都进行二元分类,并通过链式增长的方式训练出多标签分类模型。然而在CC模型中,二元CC序列是随机生成的[28-30],没有充分考虑二元分类器对应标签之间存在的隐含依赖关系,而这无疑会导致分类错误传播,并直接影响多标签分类性能。因此采取合理的策略优化标签的排序就显得尤其重要[31]。近年来研究人员已提出很多CC算法优化策略。文献[32]提出了一种多树增宽CC方法,该算法通过建模标签与属性之间合理的条件依赖关系来近似底层依赖关系,但该方法计算复杂度极高,其预测计算代价随标签数量呈指数级增长。文献[33]提出了基于神经网络的CC模型算法,虽能明显提升多标签分类的性能,但随着实例和标签的增加,用于神经网络模型训练的计算复杂度将会急剧增加,因此类似方法不适用于一些需要快速地进行分类预测的应用环境,如边缘计算环境等。

本文针对原始CC标签序列随机生成导致多标签分类性能不高的问题,分别提出贪心CC(greedy CC,GCC)方法和基于n-gram的CC(n-gram based CC,NCC)方法对标签序列中的标签序列进行优化,以提升模型的多标签分类性能。另外,通过与当前流行的基于CC模型的多标签分类模型进行实验对比,以验证本文所提方法的有效性和高效性。

1 基本原理

1.1 多标签分类

令X⊆Rk为k维实例输入特征空间,Y={l1,l2,…,lq}标签的集合。由n个数据组成的训练样本集D,表示为D={(xi,yi)}(i=1,2,…,n)。每个实例(xi,yi)∈D。xi=(xi,1,xi,2,…,xi,k)∈X是一个k维特征向量,xi,j代表特征向量xi的第j个元素。本文用yi=(yi,1,yi,2,…,yi,q)∈{0,1}q表示一个q维的标签向量,其中yi,j=1表示标号lj与xi相关,而yi,j=0则表示与xi无关。设Yi⊆Y是与xi相关的标记组成的集合,则有Yi={lj|yi,j=1,1≤j≤q}。

多标签分类的任务是找到一个能将yi最优地分配给每个实例xi的分类器f:X→{0,1}q。在BR[27]的背景下,一个多标签分类器f是由q个二值分类器f1,f2,…,fq组成。每个二值分类器fj:X→{0,1}都可以从派生训练集Dj={(xi,yi,j)}(j=1,2,…,n)中根据其与lj的相关性训练得出。其中Dj是通过将每个实例(xi,yi)∈D转化为对应于标签lj的二进制实例(xi,yi,j)而得到的。对于标签未知的实例x′,通过查询每个分类器fj,可以预测其关联的标签集Y′={lj|fj(x′)=1,1≤j≤q}。

1.2 CC模型

CC是一种著名的基于BR模型的多标签分类方法,克服了BR模型在训练数据中忽略标签间相关关系的局限性,从而获得了较好的预测性能。该模型通过将前面分类器的结果添加到当前分类器来实现分类器的串行连接。具体来说,CC模型首先随机生成一个标签的序列,记为Y={l1,l2,…,lq},然后CC模型按照CC的序列训练一组二元分类器f1,f2,…,fq。

在训练阶段,每个二元分类器fj:X→{0,1}都是基于当前标签lj同前j-1个标签l1,l2,…,lj-1的关联性,从特定的派生训练数据集Dj={(xi,yi,1,…,yi,j-1,yi,j)}(i=1,2,…,n)中训练得到的。该训练数据集Dj中的每一个实例都是由原始数据集D中的相对应的实例(xi,yi)派生得到的。

在测试阶段,该方法以贪心方式来预测未知的实例x*的值fj(x*)。通过查询每个分类器fj(1≤j≤q),来预测实例x*的关联标签集Y*,其中Y*={lj|fj(x*)=1,1≤j≤q}。

CC算法由于初始随机生成的标签链的顺序无法有效避免错误传播的风险,故对CC的顺序仍然非常敏感。因此,为CC选择一个最优的序列以保证多标签分类的高精度成为一个关键问题。

2 CC优化方法框架

2.1 CC优化方法流程

本文提出的CC优化方法总体上可分为4个主要阶段。第1阶段,根据训练样本集合D={(xi,yi)}(i=1,2,…,n)来构建共现率矩阵M。第2阶段,根据共现率矩阵M来确定标签序列的首部(优化标签序列中的前两个标签)。在第3阶段,本文提出两种方法生成完整的标签优化序列方法,即GCC)和NCC。这两种方法依据不同的标签关联发掘方式,得到不同的标签优化序列。在第4阶段,通过前面阶段获得的优化标签序列进行基于CC模型的多标签分类。本文CC优化方法的总体框架如图1所示。

图1 CC优化方法总体框架Fig.1 Overall framework of CC optimization method

2.2 共现率矩阵创建

共现分析是通过计算两个元素一起出现的频率[34-35]来定量度量两个元素之间潜在关系的关联度的一种方法,目前已应用于单词嵌入[36]等技术中。共现率矩阵M的创建过程大致如下:

令D={(xi,yi)}(i=1,2,…,n)代表数据集,q代表标签的数目。令Yi⊆Y代表与xi相关的标签集合,则对yi=(yi,1,yi,2,…,yi,q)有Yi={lj|yi,j=1,1≤j≤q}。同时采用Si={(xj,yj)|(xj,yj)∈D,yj,i=1}来表示与标签相关的实例。相应地用(Si={(xj,yj)|(xj,yj)∈D,yj,i=0}表示与li无关的实例集。因此,Si∩Sj={(xk,yk)|(xk,yk)∈D,yk,i=1,yk,j=1}。

在本文中,共现率矩阵是一个q×q大小的矩阵,对于共现率矩阵M中的i行j列(i≠j)的元素共现率Mij定义如下：

(1)

式中：|S|为集合S中元素的总数；n为训练集D中样本的总数。同时注意到,共现率矩阵必然是对称矩阵,因此只需要计算矩阵的一半元素即可。基于式(1),共现率矩阵的一个例子如表1所示,其涉及q=5个标签,是一个5×5矩阵。另外,共现率矩阵中只需要计算不同标签之间的共现率,而无需计算相同标签之间共现率。

表1 共现率矩阵的例子Table 1 Example of co-occurrence rate matrix

计算共现率矩阵中元素Mi,j在最坏情况下的计算复杂度为O(n)。由于计算同一标签的共现性毫无意义,因此构建共现率矩阵的总复杂度应为O(n(q-1)2)。根据样例的标签集合建立对应的共现矩阵,可以将标签之间的潜在关联关系用于后续的标签序列优化。

2.3 标签序列首部的选定

在分析共现率矩阵M的基础上,通过遍历M中的每一行,找到值最大的单元格来确定前两个标签的在CC上的最优选择。基于此,本文通过对每对标签(li,lj)对应的Mi,j进行两两比较,并选择Mi值最大的两个标签作为首部标签,从而确定最优的首部选择,如下所示:

(2)

式中:H表示共现率矩阵中具有最大共现率Mi,j的所有数对(i,j)的集合,每个数对(i,j)对应的标签对为(li,lj)。

确定首部标签在链中的顺序至关重要,其基本标准是将共现率较高的标签排序到尽可能早的位置,这样可以有效地利用前面分类器的结果进行基于当前分类器的分类。本文通过两个步骤确定优化标签序列的前两个元素。

步骤 1若H只包含一个标签对,设H={(i,j)},则需要判断标签对(li,lj)是否满足:

(3)

式(3)用于计算除(li,lj)以外分别与li和lj共现率最大的标签对(li,ls)和(lj,lt)。若式(3)成立,那么li和lj分别是标签序列的第1个和第2个标签,否则反之。

步骤 2若H包含两个及以上标签对,不失一般性地假设H={(i,j),(s,t)}包含两个标签对(3个以上的标签对可以通过任意两个标签对之间的两两比较最终确定两个标签对),则需要分别计算这两对标签和其他标签之间的最大共现率是否满足：

(4)

来确定,最终选取序列首部,即优化序列的前两个标签。若式(4)成立,则确定将使用(li,lj)标签对作为标签首部,否则使用(ls,lt)标签对作为标签首部。一旦确定了一个标签对,则可进一步通过步骤1判断该标签对中哪个标签是标签序列的第1个和第2个。

由于序列首部(优化序列的前两个标签)已经选定了,因此只需不断选取后续的标签序列即可。本文分别提出GCC算法和NCC算法来确定优化标签序列中的其他标签。

3 GCC方法

本文提出GCC方法,其具体流程如算法1所示。GCC算法需要遍历共现率矩阵M所有元素。在算法1中,第1～4行是将(s,t)按前两个标签的正确顺序排列,并进行一些初始化。在第5～10行,通过贪心策略来最大化标签序列尾部L[c]的共现率ML[c],r,从而选取标签序列的后继标签。

通过执行算法1,将对所有的标签从原始的标签集合Y中重新排序,使之符合其编号。链中标签的最优顺序为lL[0]→lL[1]→ … →lL[q-1],GCC算法的复杂度包括共现率矩阵的构造,算法复杂度在最坏情况下仅为O(nq),其中n和q为样本总数和标签总数。

4 NCC方法

本文提出的NCC方法借助于n-gram的语言模型实现。n-gram是一种用于词序列的概率生成的模型[37-38],考虑了句子中词的前后联系,从条件概率的角度给出一个句子的生成概率[39]。假定当前需要生成的词序列共有m个词w1,w2,…,wm,且假设当前词仅与其前面n-1个词有关(n

P(w1,w2,…,wm)=
P(w1)P(w2|w1)…P(wm|wm-n+1,…,wm -1)

(5)

式中:n的取值不同对于整个序列的影响程度是不一样的。选取过大的n会使得时间复杂度急剧变高,从而使得原本任务变得很困难。考虑到n-gram在词序列的特征提取上面有比较好的表现,本文采用n-gram算法思想,将标签序列看成是若干个词组合而成的序列,来对标签序列进行优化。

设L={l1,l2,…,lq}是一个由q个标签组成的CC序列,进一步基于式(5),采用n-gram模型并根据

P(L)=P(l1,l2,…,lq)=
P(l1)P(l2|l1)…P(lq|lq-1,lq-2,lq-3)

(6)

将L标签序列发生的概率转换为条件概率的乘积。

为了实现以序列增长的方式产生CC优化序列,标签li出现在li-1和li-2后面的条件概率为P(li|li-1,li-2),定义如下：

(7)

式中：Si-2、Si-1和Si分别表示与标签li-2、li-1和li相关的实例集,每个Si={(xj,yj)|(xj,yj)∈D,yj,j=1}。如果能使得所生成的标签序列的概率最大化,实际上就选择出了一条优化的分类器标签序列。因此,NCC策略生成多标签序列的任务可以转换为:设Li={l1,l2,…,li}表示完整序列L中前i个标签组成的子序列,在以迭代方式添加后续标签到当前序列的过程中,需要确保标签添加后的新序列的概率P(Li)值最大。也就是说,假设已经确定顺序的前i-1个标签的序列P(Li-1)值最大。当后面添加可能的标签li的时候,依然要选择使得概率P(Li)=P(Li-1)P(li|li-1,li-2)值最大的那个标签。

(8)

从Y′的序列中选择某一个标签li添加到序列Li-1的末尾作为其第i个标签。这样不断地选择剩余标签,最终可以生成包含所有标签的优化的CC的标签序列。

NCC方法的具体流程如算法2所示。因为标签首部已经确定,所以只需要确定标签序列中的剩余标签顺序。在算法2中,第1～4行是按照前两个标签的顺序放置(s,t),并进行一些初始化。在第5～18行,通过使后续标签的条件概率最大来选择完整的优化标签序列。在第8～15行中,选择概率最大的P(lc|lc-2,lc-1)的标签作为之前已经确定的标签序列的后续标签。算法2在最坏情况下的计算复杂度为O(|D|×|Y|2)。在现实世界中,标签的数量|Y|远远小于实例的数量|D|。因此,算法2对于训练的实例的数目几乎具有线性一致性。

算法2 NCC算法输入 数据集D={(xi,yi)},i=1,2,…,n,序列首部(s,t)∈H输出 CC序列L[q]1.L[0]←s;2.L[1]←t;3.Y←YlL[0],lL[1]};4.c←2; ∥一种记录标签数目的索引5.whileY≠⌀do ∥选择条件概率最大的标签6. B←{(xk,yk)(D|yk,L[c-1]=1,yk,L[c-2]=1};7. max←0;8. foreachlj∈Ydo9. U←{(xk,yk)(P|yk,j=1};10. p←|U|/(|B|+1)11. ifp>maxthen12. max←p;13. L[c]←j;14. endif15. endfor16. Y←Y{lL[c]};17. c←c+1;18.endwhile19.returnL[];End

5 实验分析评估

实验主要目的是评估本文提出的GCC和NCC两种方法的效能。

5.1 实验评估基线算法

与 CC模型相关的用于多标签分类的典型算法包括BR算法[27]、初始CC[24]以及用于多标记学习的局部顺序CC(locally ordinal CC,LOCC)算法[40]、标签幂集的改进算法(pairwise random k-labelsets,pwRakel)[15]。本文将这些算法作为基线算法用于多标签分类性能比较。

5.2 数据集与实验设置

本文从MULAN网站和MEKA网站收集了yeast,enron,emotions[41],Slashdot-F,CAL500等5个数据集用于实验评估。其领域涵盖文本、图片、生物等不同类型数据。数据集的信息细节如表2所示。

表2 数据集描述Table 2 Description of datasets

所有实验评估均采用python语言实现,借助sklearn库进行相应的实验。在对于基分类器的选择上,本文采用支持向量机作为基分类器,核函数选择高斯核函数,惩罚参数C=100,所有算法的基分类器采用相同参数,以避免在基分类器上存在差异从而影响序列优化本身所带来的效果。

5.3 评价指标

在评价指标上,传统分类任务中所使用的分类准确率计算并不能很好地反映多标签分类算法的性能,因此本文选择采用在文献[42]中提到的针对多标签分类的准确率Accuracy和F1测量作为性能评价指标。

(1)准确率指标(Accuracy)

抽取2016年1月—2017年1月该院临床检验520例患者作为研究对象,男性患者280例,女性患者240例,年龄18~76岁,平均年龄(50.4±1.8)岁,所有患者共进行临床检验862次,其中,血液分析檢验262次,生化检验150次,尿沉渣检验300次,大便检验150次。

(9)

式中:|D|为样本个数；Yi为样本xi的真实标签集合；Pi为样本xi的预测结果集合；Yi∩Pi表示样本xi预测正确的标签个数；Yi∪Pi表示样本xi总计出现的标签次数。

(2)F-score测量指标(F1)

(10)

(11)

(12)

(13)

(6)归一化平均时间(Time*)

(14)

(7)归一化准确率(Accuracy*)

(15)

5.4 算法比较与评估分析

5.4.1 NCC算法的n值实验与验证

NCC算法采用基于n-gram语言模型的策略进行多标签分类,而n值的选择对于NCC算法分类性能有重要影响。如果n值选择过小,分类准确率可能会受到影响。但如果n值选择过大则会急剧地增加NCC算法的计算复杂度。

本文为经验验证参数n对于NCC算法的影响大小,在部分指标数值相近的数据集上选取了不同的n值进行实验,计算并比较了不同n值下的NCC算法的准确率和F1测量值。试验结果如图2和图3所示。

图2 n值在不同数据集上的Accuracy比较Fig.2 Accuracy comparison over different datasets with respect to n value

图3 n值在不同数据集上的F1比较Fig.3 F1 comparison over different datasets with respect to n value

从图2中可以看到,对于Accuracy指标,在emotions,yeast,Slashdot-F等数据集下,当n<4时,NCC算法分类准确率表现不稳定；当n≥4时,随着n值的增大,NCC算法分类效能基本稳定了。从图3中针对不同的数据集分析对应的F1指标值,也可以得出类似的结论。

因此，综合不同的数据集以及不同情况下参数n的表现考虑,在默认情况下本文选择n=4最好,这样既可以保证NCC算法分类性能处于基本稳定的状态,同时也可以使得n-gram概率计算的复杂度不会过高。从另一方面来看,该实验也从侧面验证了本文采用n-gram模型来挖掘标签之间潜在关联关系的有效性与正确性。

5.4.2 算法指标性能对比分析

在实验结果的验证方面,本文采用五折交叉验证的方式，分类的指标结果如表3～表5所示,其中加粗标示的为对应指标最优的结果,用下划线标示的为对应指标次优的结果。

表3 不同算法关于Accuracy的性能比较Table 3 Accuracy comparison of different algorithms

表4 不同算法关于F1的性能比较Table 4 F1 measure comparison of different algorithms

表5 不同算法和比较Table comparison of different algorithms

如表3所示,在Accuracy指标上可以观察到NCC算法几乎优于其他所有算法。同时其在yeast、Slashdot-F和emotions等3个数据集上表现优越,在yeast数据集上比原CC算法高出2个百分点,而在Slashdot-F数据集上则比原CC算法高了3个百分点。在个别数据集如enron和CAL500上,PwRakel和GCC算法性能则相对较优。

从表4可以观察到,从F1指标进行衡量,GCC算法和NCC算法的性能在所有数据集上都优于其余算法,同时在不同数据集上分别占据了算法效果最优和次优的位置。

本文提出的NCC和GCC两种算法都取得明显性能提升的原因,归根结底是在于其在生成优化序列时,都考虑了不同长度的潜在标签关联关系对整个序列造成的影响。GCC算法每次考虑前一个标签同后一个标签存在的最大共现关联关系,从而保证了优化的标签序列能体现最大的共现率。NCC算法则更进一步考虑到了前n-1个标签同当前尾部标签序列的关系,并采用n-gram来发掘标签前后间的依赖关系。因此,这两种算法都取得了较好的效果。

5.4.3 算法指标综合效能对比分析

本文评估不同算法在不同数据集上执行时间损耗。利用式(13)求出平均时间,各种算法执行时间损耗如图4所示,其中Time_avg为算法在所有数据集上的平均执行时间。

图4 不同算法的时间损耗比较Fig.4 Comparison of time loss for different algorithms

采用归一化式(14)和式(15),对图4的时间损耗和表3的准确率求取归一化的平均值,利用所有算法的归一化准确率和时间损耗绘制出图5,进一步比较各种算法的综合效能。从图5可以观察到,CC算法的耗时最短,但效果并不理想。同时，不难发现LOCC算法相比原算法时间损耗并不大,但是算法性能提升较少。同样地,PwRakel算法时间损耗较大,准确率的提升却不明显。

图5 不同算法的综合效能比较Fig.5 Comprehensive effectiveness comparison of different algorithms

反观GCC和NCC算法,两者的时间损耗与原CC算法相比虽略有提升,但小于LOCC和PwRakel等算法。但与此同时,NCC算法和GCC算法效果却提升显著。这足以体现GCC和NCC算法具有优良的综合效能。而这归功于本文在CC算法基础上,既考虑了标签间潜在的关联关系,又采用了时间复杂度相对低的策略来进行算法的优化。

6 总 结

本文对于CC算法在标签序列的生成上采用随机生成的缺点,创新性地在共现分析的基础上,采取贪心策略和n-gram策略来对标签序列进行优化。两种方法都一定程度上考虑了不同长度标签的潜在关联关系,因此都给原CC算法带来了稳定的提升。

在实验部分,本文首先经验验证了n的不同取值对NCC算法分类效果的影响,并选取最合适的n的取值参与后续的实验,最后,在经过实验并综合考虑了Accuracy和F1指标、平均指标、综合分类性能等各种指标情况下,本文发现NCC和GCC算法能比大多数前沿的多标签分类算法取得更好的效果。证实了通过共现分析来优化标签序列,进而改进整体CC分类性能的策略是行之有效的。