一种适应于非完备标签数据和标签关联性的多标签分类方法

2016-12-01张丽娜戴灵鹏匡泰

电信科学 2016年8期

关键词：遗失关联性分类器

张丽娜，戴灵鹏，匡泰

（1.浙江安防职业技术学院信息工程系，浙江温州 325016；2.温州大学生命与环境科学学院，浙江温州 325035）

一种适应于非完备标签数据和标签关联性的多标签分类方法

张丽娜1，2，戴灵鹏2，匡泰1

（1.浙江安防职业技术学院信息工程系，浙江温州 325016；2.温州大学生命与环境科学学院，浙江温州 325035）

多标签分类已在很多领域得到了实际应用，所用标签大多具有很强的关联性，甚至存在非完备标签或部分标签遗失。然而，现有的多标签分类算法难以同时处理这两种情况。基于此，提出一种新的概率模型处理方法，实现同时对具有标签关联性和遗失标签情况进行多标签分类。该方法可以自动获知和掌握多标签的关联性。此外，通过整合遗失的标签信息，该方法能够提供一个自适应策略来处理遗失的标签。在完备标签和非完备标签的数据上进行实验，结果表明，与现有的多标签分类算法相比，提出的方法得到了较好的分类预测评价值。

非完备标签；标签关联性；多标签分类；概率模型

1 引言

在传统的标签数据分类问题中，一个样点通常只分配一个标签。但在实际应用中，大部分都涉及多标签分类，即一个样点可分配多个标签，如文本分类、图像标注以及基因方程的分析［1］等。正是由于该类问题的不断出现，也吸引了越来越多的学者进行多标签分类问题的研究。

经过多年的研究和发展，目前已出现了大量的多标签分类方法，最为经典且应用最广泛的是问题转换类方法［2，3］。在此类方法中，较常用的一种方法是二值相关（binary relevance，BR）［4］算法。该方法建立在标签之间相互独立假设的基础上，当标签存在很大的关联性时，该方法的效果不佳。针对BR方法的局限性，一种解决方案是假定标签的关联性是一种先验信息或很容易被估计，如Read等人［5］提出了一种链式分类器（classifier chain，CC）算法，该方法以一定的次序将一系列BR分类器串联起来，后一个分类器的结果总是依赖于前一个分类器，这样便考虑了标签的关联性。然而，其弊端是如果前一个分类器存在误差，这种关联也会将误差进行传递积累。孙霞等人［6］提出了一种基于Haddoop框架的传播算法，该方法能适应大规模数据，但误差同样会在迭代算法中传播。在Hariharan等人［7］提出的最大边界多标签分类器（max-margin multi-label classifier，M3L）中，标签的关联性被从训练集中计算出的成对标签关联所代替，取得了不错的效果，但该方法在样本数量较少时会出现一些误差。此外，一些方法通过标签转换进行去标签关联，即对去关联的标签进行分离学习，如Hsu等人［8］提出的利用随机矩阵进行标签转换、在标签矩阵中采用奇异值分解法的主标签空间转换（principal label space transformation，PLST）［9］、在标签矩阵和输入样本矩阵中均采用奇异值分解法的条件主标签空间转换（conditional principal label space transformation，CPLST）［10］以及在最小二乘回归基础上利用SVD技术的多标签分类算法［11］，经过这些方法转换后的标签都可以单独进行处理。再有，一些学者在方法的精度等方面也做了一些研究，如李远航等人［12］、许美香等人［13］通过主动学习的方法提高分类器的精度和效率；徐晓丹等人［14］通过对数据进行预处理来提高分类器的精度。

在多标签分类算法中，另一个重要的问题是标签遗失。针对此问题，一些学者也提出了相应的解决方案。其中一种解决方法是丢弃所有没有标签的样本，但会损失大量的标签信息。另一种方法是估算遗失的标签，尤其是正标签，如群索引多标签排序（multi-label ranking with group lasso，MLRGL）［15］算法，它将分类问题转化为双边排序问题进行解决；快速图像标记［16］（fast image tagging，FastTag）法，它假设标签一致性被破坏，该方法能对可能遗失的正标签进行恢复，但不能有效地处理标签关联性问题，且只能对正标签进行恢复。Yu等人［17］根据经验误差最小化，提出了一种对遗失标签的分析方法，该方法也没有准确考虑标签的关联性，限制了它的应用。

针对目前大部分方法分别在处理标签关联和标签遗失问题中存在的缺陷以及难以对这两个问题同时进行处理的情况，提出一个新的概率模型，该模型能同时处理标签关联和标签遗失问题，它不需准确地找出标签转换，只需将概率模型重新表述成原始的标签空间，在原始标签空间中自动获知和掌握标签的关联性。此外，通过对遗失的标签信息进行整合，以提供一种自适应的方法来处理遗失标签。最后，在具有完备标签和遗失标签数据上进行试验，结果表明，该方法所获得的效果优于现有经典方法。

2 提出的方法

第2节主要介绍同时处理非完备标签数据和标签关联性的多标签分类方法。首先进行最基本的步骤，即标签转换，在此基础上，提出一个新的概率模型，对标签关联和遗失标签同时进行处理，并给出优化子问题的推导过程。

2.1 标签转换

在多标签分类问题中，对于一个给定的训练集{（x，y）}，其中，x∈Rd是输入，y∈{0，1}m是对应的输出，其中，m 是样点数，d是样点维度。标签转换［9，10］是指将每一个 y转换成=Py，其中是转换矩阵，经转换之后的标签是不相关的，即可以单独对待。首先，采用一个线性模型作为初始模型（加权为，偏差为），即被假定为：是噪声方差。注意：用于标签转换的高斯噪声一般是实值（尽管原始值是二值）。式（1）可改写为如下形式：其中，

2.2 标签关联处理

第2.1节主要介绍了标签转换的基本方法，接下来将建立一个模型，利用该模型对标签关联性进行处理。

2.2.1 模型建立及分析

首先，建立一个概率模型。通过使用式（2）和式（4）以及和转换标签时编码原始标签的误差以得到，在对式（4）中z进行凑整之前的多标签预测遵从下列正态分布：

其中，λ1，λ2＞0 是两个自由参数，用来增加-1的稀疏度和收缩性，-1指精度矩阵，表示标签i和标签j之间部分相关［18］。增加-1的稀疏度意味着大部分的标签是条件不相关的。这里，p（）是根据-1表述，而不是。为了模拟从z到二值预测y的凑整误差，通过下面的正态分布来近似：

其中，λ0＞0。

其中，β1，β2＞0。图 1 是代表整个模型的一个图解表示，可清楚呈现其建立过程。具体地，首先通过自由参数λ1和λ2根据式（6）来获得的信息；同时，通过参数 β1和 β2根据式（11）来获得的信息，进而得到的分布。根据式（5），通过已知的训练集x、偏差b以及得到的W和来得到z，进而根据式（7）通过给定的参数λ0来获得y。提出的模型相较传统方法模型的优势在于：现有的部分方法未考虑标签间的关联性，或考虑了相关性，但由于串联分类器存在误差或样本数量较少等原因，其关联会将误差传递积累，进而导致更多的误差。而提出的模型不需要准确地找出标签转换，只需将概率模型重新表述成原始的标签空间，在原始标签空间中自动获知和掌握标签的关联性，目标是获得能够实现同时对具有标签关联性和遗失标签情况进行多标签分类求解模型（具体求解处理见第2.2.2节和第2.3节）。

图1 提出模型的一个图解表示

2.2.2 模型推导求解

对建立的模型进行推导求解。对于给定的N个样点，令研究表明，凑整会导致编码误差为对应的标签矩阵。其中，上标（i）表示第i个样点。当

下面，使用交替最大化方法［23］对式（11）进行求解，交替获得后验信息最大值，即在式（13）中每次固定其他变量而求一个变量的最大值。这里，每一个子问题是凸性的，且容易求解，具体如下。

（1）固定其他变量，求解Z

最优化子问题是：

显然，每一个 z（i）都可以单独求解。令 z（i）的导数为 0，可以得到：

（2）固定其他变量，求解W和b

最优化子问题为：

令W的导数为0，可以得到一个封闭形式的解：，对于 b，令其导数为 0，可以得到：

根据式（6）的先验信息，最优化子问题为：

2.3 遗失标签处理

基于提出的模型，对遗失标签情况进行处理。如前所说，标签向量也许会有一些遗失记录。假设样点x（i）具有li个观测标签以及 ui=m-li个遗失标签，可将 y（i）和 z（i）分别记为和，其中，。同样，对每一个i，通过将第li行／列与首次观测的标签进行对应，可将-1记为其中，

不同于直接估算遗失标签值的方法［15］，这里所获得的信息直接来源于观测标签，类似于式（13），可以得到：

则仍然满足正态分布［24］：是W的子矩阵，W的列对应于li观测标签。注意：每一个在整个矩阵中相对于是独立的。因此，尽管有遗失标签存在，推理过程仍然可以利用标签关联信息。

如第2.2.2节所示，本节也将使用交替最大化法来求解式（21）中的后验信息最大值。对于的最大化子问题与之前相同，因此其校正不变。

最优化子问题为：

（2）固定其他变量，求解W和b

最优化子问题为：

不同于式（16），这里无法对该凸问题得到封闭解，而需要通过降低梯度对W进行最优化，即对b可得到一个封闭解：

最优化子问题为：

通过软阈值迭代算法［25］进行求解，将式（28）分解为两部分：

梯度降；

其中，τ=λ2η，η 是梯度降的补偿。

3 实验效果与分析

在第 3节中，对 Guillaumin等人［26］采用的 4个图像标注的数据集（表1）进行试验。对每一个图像都提取1 000个SIFT特征。

表1 数据集

将提出的处理非完备数据和标签关联的多标签分类方法（multi-label classification with incomplete labeled data and label relevance，ILDLR）与下列经典方法进行对比分析：

· 二值相关（BR）算法［4］；

· 条件的主标签空间转换（CPLST）法［10］；

· 具有群索引的多标签排序（MLRGL）法［15］；

· 快速图像标记（FastTag）法［16］。

由于在CPLST方法中的转换标签是实际值，因此，使用脊回归作为其初始模型。所有方法的参数调整都基于一个已验证的集合，该集合通过对实验数据采样25%获得。下面两个参数被广泛的用于多标签分类的效果评价［26］：

其中，macro_F1和micro_F1值越大，效果越好。

3.1 在完备标签数据上的实验

在4组完备数据集上进行实验，并与其他几种方法进行对比。基于10折交叉验证方法，对数据进行分类及F1值评价，结果见表2，其中，“±”表示10次验证计算的 F1评价值的浮动范围。可以看到，在完备标签的情况下，提出的ILDLR方法对所有的数据处理效果都比其他方法要好。对于 MLRGL方法，在 COREL5K、ESPGAME和IAPRTCL12 3个数据集上的处理效果与其他几种方法的效果差距较大。

3.2 在非完备标签数据上的实验

通过以下方式生成遗失标签。之前提及有m个标签，对每一个训练样本集，选择其中的一半作为观测值，其余的为遗失值。由于每个样点都普遍具有极少的正标签，且标签进行随机拆分有可能导致仅仅观测到负标签，因此，对每一个样点，保证有k=1，2，3个观测到的正标签（如果一个样本的正标签数少于k个，那么它所有的正标签将被挑选出来）。将ILDLR、MLRGL、FastTag和BR 4种方法进行比较，这4种方法都能处理遗失标签。

表3呈现的是10折交叉验证的结果，可以看到，ILDLR的效果要优于其他方法（除了在MIRFLICKR数据集中当k=2时）。当遗失标签的数量远大于k的最大值时，效果并不会随着k的增大而变好。并且当k=1时，通过ILDLR获得的F1与表2中具有完备标签所获得的值很接近。对于数据COREL5K，ILDLR在标签遗失的情况下反而效果更好，其原因是：对于完备标签，需要学习m×n的标签矩阵Z。而当标签遗失时，只需要学习观测标签矩阵Z对应的子矩阵。这样，尽管式（22）依赖于分布的结果，且可能会引进一些误差，但减少了自由参数的个数。因此，提出的ILDLR方法在标签遗失的情况下也会得到很好的处理效果。

表2 具有完备标签数据的结果

4 结束语

对多标签分类提出了一个概率模型，然后受标签转换方法的启发，此模型在原始标签空间而不是在转换标签空间进行表述，这可以灵活地处理标签相关和遗失标签情况，并且推导过程简单。在完备的数据和具有非完备的遗失标签数据上的实验都表明，提出的方法比现有的其他经典方法效果更好。

［1］ZHANG M L，ZHOU Z H.A review on multi-label learning algorithms ［J］.IEEE Transactions on Knowledge and Data Engineering，2014，26（8）：1819-1837.

［2］MADJAROV G，KOCEV D，GJORGJEVIKJ D，et al.An extensive experimental comparison of methods for multi-label learning［J］.Pattern Recognition，2012，45（9）：3084-3104.

［3］王霄，周李威，陈耿，等.一种基于标签相关性的多标签分类算法［J］.计算机应用研究，2014，31（9）：2609-2614.WANG X，ZHOU L W，CHEN G，et al.Correlation label-based multi-label classification algorithm.［J］.Application Research of Computers，2014，31（9）：2609-2614.

［4］TSOUMAKAS G， KATAKIS I， VLAHAVAS I.Mining multi-label data［M］.New York：Springer，2010：667-685.

表3 10折交叉验证结果

［5］READ J，PFAHRINGER B，HOLMES G，et al.Classifier chains for multi-labelclassification ［C］／／European Conference on Machine Learning，June 14-18，2009，Montreal，Canada.New Jersey：IEEE Press，2009：254-269.

［6］孙霞，张敏超，冯筠，等.Hadoop框架下的多标签传播算法［J］.西安交通大学学报，2015，49（5）：134-139.SUN X，ZHANG M C，FENG J，et al.A label propagation algorithm for multi-label classification ［J］.Journal of Xi’an Jiaotong University，2015，49（5）：134-139.

［7］HARIHARAN B，ZELNIK M L，VISHWANATHAN S，et al.Large scale max-margin multi-label classification with priors［C］／／27th International Conference on Machine Learning，June 21-24，2010，Haifa，Isreal.New Jersey：IEEE Press，2010：423-430.

［8］HSU D，KAKADE S，LANGFORD J，et al.Multi-label prediction via compressed sensing［J］.Computer Science，2009：772-780.

［9］ TAI F，LIN H.Multi-label classification with principal label space transformation ［J］.Neural Computation，2012，24 （9）：2508-2542.

［10］CHEN Y N，LIN H T.Feature-aware label space dimension reduction for multi-label classification ［J］.Advances in Neural Information Processing Systems ，2012（2）：1538-1546.

［11］马宗杰，刘华文.基于奇异值分解-偏最小二乘回归的多标签分类算法［J］.计算机应用，2014，34（7）：2058-2061.MA Z J，LIU H W.Multi-label classification based on singular value decomposition-partial least squares regression［J］.Journal of Computer Applications，2014，34（7）：2058-2061.

［12］李远航，刘波，唐侨.面对多标签图数据的主动学习［J］.计算机科学，2014，41（11）：260-264.LIYH，LIUB，TANGQ.Activelearningformulti-label classification on graphs［J］.Computer Science，2014，41（11）：260-264.

［13］许美香，孙福明，李豪杰.主动学习的多标签图像分类在线分类［J］.中国图像图形学报，2015，20（2）：237-244.XU M X，SUN F M，LI H J.Online multi-label image classification with active learning ［J］.Journal of Image and Graphics，2015，20（2）：237-244.

［14］徐晓丹，姚明海，刘华文，等.基于kNN的多标签分类预处理方法［J］.计算机科学，2015，42（5）：106-108.XU X D，YAO M H，LIU H W，et al.Pre-processing method of multi-label classification based on kNN［J］.Computer Science，2015，42（5）：106-108.

［15］BUCK S，JIN R，JAIN A.Multi-label learning with incomplete class assignments ［C］／／IEEE Conference on Computer Vision and Pattern Recognition，June 20-25，2011，Providence，RI，USA.New Jersey：IEEE Press，2012：2801-2808.

［16］CHEN M，ZHENG A，WEINBERGER K Q.Fast image tagging［C］／／30th International Conference on Machine Learning，June 16-21，2013，Atlanta，GA，USA.New Jersey：IEEE Press，2013：1274-1282.

［17］YU H F，JAIN P，DHILLON I S.Large-scale multi-label learning with missing labels［C］／／31st International Conference on Machine Learning，June 21-26，2014，Beijing，China.New Jersey：IEEE Press，2014：593-601.

［18］PETTERSON J，CAETANO T.Submodular multi-label learning［J］.Advances in Neural Information Processing Systems，2011：1512-1520.

［19］GUPTA A，NAGAR D.Matrix variate distributions ［M］.Boca Raton：Chapmanamp;Hall／CRC Press，2000.

［20］RAI P，KUMAR A，III H D.Simultaneously leveraging output and task structures for multiple-output regression［C］／／Advances in Neural Information Processing Systems，December 3-8，2012，South Lake Tahoe，USA.New Jersey：IEEE Press，2012：3194-3202.

［21］ROTHMAN A J，LEVINA E，ZHU J.Sparse multivariate regression with covariance estimation［J］.Journal of Computational and Graphical Statistics，2010，19（4）：947-962.

［22］ZHANG Y，YEUNG D Y.A convex formulation for learning task relationships in multi-task learning ［C］／／26th Conference on Uncertainty in Artificial Intelligence，July 8-11，2010，Los Angeles，USA.New Jersey：IEEE Press，2010：733-742.

［23］BERTSEKAS D P.Nonlinear programming ［M］.Nashua：Athena Scientific，1999.

［24］BISHOP C M.Pattern recognition and machine learning［M］.New York：Springer-Verlag，2006：125-153.

［25］BECK A，TEBOULLE M.A fast iterative shrinkage-thresholding algorithm for linear inverse problem［J］.SIAM Journal on Imaging Sciences，2009，2（1）：183-202.

［26］GUILLAUMIN M，MENSINK T，VERBEEK J，et al.Tagprop：discriminative metric learning in nearest neighbor models for image auto-annotation ［C］／／International Conference on Computer Vision，September 29-October 2，2009，Kyoto，Japan.New Jersey：IEEE Press，2009：309-316.

A multi-label classification method for disposing incomplete labeled data and label relevance

ZHANG Lina1，2，DAI Lingpeng2，KUANG Tai1
1.Department of Information Engineering，Zhejiang College of Security Technology，Wenzhou 325016，China 2.College of Life and Environmental Science，Wenzhou University，Wenzhou 325035，China

Multi-label classification methods have been applied in many real-world fields，in which the labels may have strong relevance and some of them even are incomplete or missing.However，existing multi-label classification algorithms are unable to handle both issues simultaneously.A new probabilistic model that can automatically learn and exploit multi-label relevance was proposed on label relevance and missing label classification simultaneously.By integrating out the missing information，it also provides a disciplined approach to handle missing labels.Experiments on a number of real world data sets with both complete and incomplete labels demonstrated that the proposed method can achieve higher classification and prediction evaluation scores than the existing multi-label classification algorithms.

incomplete label，label relevance，multi-label classification，probabilistic model

s： Education Science Department Foundation of Zhejiang Province（No.2016SCG188），The Natural Science Foundation of Zhejiang Province of China （No.LY14C03007）

TP311

10.11959／j.issn.1000-0801.2016197

2016-05-04；

2016-07-10

张丽娜，zln_zcst@163.com

浙江省教育科学规划基金资助项目（No.2016SCG188）；浙江省自然科学基金资助项目（No.LY14C03007）