一种新的多标记特征提取方法

张居杰，方 敏，郭 锦

(1. 西安电子科技大学 计算机学院，陕西 西安 710071; 2. 西北工业大学 计算机学院，陕西 西安 710072; 3. 西安工业大学 电子信息工程学院，陕西 西安 710021)



一种新的多标记特征提取方法

张居杰1，方 敏1，郭 锦2,3

(1. 西安电子科技大学 计算机学院，陕西 西安 710071; 2. 西北工业大学 计算机学院，陕西 西安 710072; 3. 西安工业大学 电子信息工程学院，陕西 西安 710021)

针对已有多标记特征提取方法并未充分利用特征信息的问题，提出了基于希尔伯特-施密特独立标准和主成分分析的多标记特征提取方法．该方法通过使标记与降维后特征之间希尔伯特-施密特范数达到最大，以充分利用标记知识;同时利用主成分分析，以尽量减少特征提取过程中的协方差信息损失．通过在Yahoo数据集上的实验表明，该算法的性能优于主成分分析和当前3种主要的多标记特征提取方法，验证了该算法的有效性．

多标记分类;特征提取;希尔伯特-施密特独立标准;主成分分析

由于多标记分类问题在图像标注、文本分类、基因功能分析和音乐理解等方面的应用中广泛出现，多标记学习目前已成为机器学习领域中的一个研究热点[1-3]． 传统的分类问题(二分类或者多分类)中一个示例通常只与一个标记相关，而多标记学习问题中每一个示例可与多个标记相关联．多标记分类问题与传统的二分类或者多分类的主要区别是，多标记分类问题中可利用标记之间的关系提高分类性能[1]．而与传统分类问题类似，多标记学习问题也面临着高维特征带来的挑战．目前，多标记问题的特征降维已经成为多标记学习研究中的一个热点．

特征降维主要有两方面的作用：首先，高维特征容易导致过拟合，即在训练集上能得到较好的分类效果，而在测试数据集上却无法得到理想的分类效果．通过降低特征维度，能够解决过拟合问题，从而提高后续训练模型的预测能力；其次，利用高维特征进行运算消耗的时间更多、存储量更大，无法进行高效的训练和测试．因此，为能够进行更快速的训练和测试，需要降低特征维度．特征降维方法可以分为两类: 特征提取和特征选择．与特征选择相比，利用某种变换方法，特征提取能够得到更有用的低维特征．目前，已有很多传统的特征提取方法，如主成分分析(Principal Component Analysis，PCA)[4]、线性判别分析(Linear Discriminant Analysis，LDA)[5]等．但是，对多标记学习问题中的特征提取方法的研究才刚刚开始．

文献[6]将无监督的潜在语义索引(Latent Semantic Indexing，LSI)[7]与标记信息结合，提出了多标记潜在语义索引(Multi-label Latent Semantic Indexing，MLSI)．其利用加权的方式将特征信息和标记信息构建目标函数．该方法考虑了同时利用特征信息和标记信息，但降维的效果对权重因子很敏感，很难找到一个恰当的权重因子．文献[8]在最小二乘法的基础上设计了一种多标记特征提取方法，然而由于其主要目标是分类，并不是为特征降维而设计，这种方法很容易产生过拟合问题．文献[9]中的方法直接将LDA方法应用于多标记特征降维问题上，并没有有效利用标记关系．而标记关系在多标记分类中起着很重要的作用[10-13]．文献[14]提出了多标记线性判别分析(Multi-label Linear Discriminant Analysis，MLDA)方法，在LDA的基础上利用了多个标记之间的关系，但其性能受制于标记的数目．文献[15]基于希尔伯特-施密特独立标准(Hilbert-Schmidt Independence Criterion，HSIC)[16]提出了基于最大化依赖的多标记维度约简方法(Multi-label Dimensionality reDuction via Maximum dependence，MDDM)．MDDM通过使得标记核矩阵和特征提取后对应的示例核矩阵之间的希尔伯特-施密特范数(Hilbert-Schmidt norm)最大，以最大化两者之间的依赖关系，得到有效的线性投影矩阵．然而，该矩阵并没有充分获取特征信息，也没有考虑特征之间的内在联系．

上述几种多标记特征提取方法并没有充分利用特征和标记中的信息．为此，笔者提出了基于希尔伯特-施密特独立标准(Hilbert-Schmidt Independence Criterion，HSIC)和主成分分析的多标记特征提取方法．一方面，按照MDDM的思想，基于HSIC，使得降维后的特征与标记之间的依赖关系最大化; 另一方面，基于PCA，利用特征之间的联系，尽可能地减少降维过程中的协方差信息损失．在Yahoo数据集的11个子数据集上对所提出的算法进行了验证．

1 基于HSIC和PCA的多标记特征提取算法

Gretton等提出来的HSIC，通过计算两组变量协方差算子的希尔伯特-施密特范式，来衡量两组变量之间的独立性[16]．基于数据集D，HSIC的经验估计可表示为

HSIC已经成功应用于特征选择[17]、有监督特征提取[18]和无监督特征提取[19]等．MDDM将其应用于多标记特征提取．对于示例核矩阵K采用了线性核，忽略掉常数项 (N-1)-2，得到的目标函数为

其中，P∈Rd×t，是线性变换矩阵，t

PCA通过对样本协方差矩阵进行分析，挖掘特征之间的相关性，寻找一组能最大程度保留协方差中的信息的主成分．PCA要优化的目标是:

其中，·F表示矩阵的Frobenius范式．

目前，PCA已经得到了广泛的应用[4]．

现有的多标记特征提取方法并不能充分利用特征信息，为此，文中提出的方法希望既能够有效利用标记信息，又能够充分利用特征信息．一方面，为利用标记信息，新算法基于HSIC，采用了与MDDM相同的目标函数式(2)，即希望 X P 与标记Y之间的依赖性达到最大;另一方面，为尽可能减少降维过程中特征信息的损失，采用PCA的目标函数式(3)．将两者结合成一个目标函数，即

式(4)既能够最大化降维后的特征X P与标记Y之间的依赖性，又能够使特征信息的损失达到最小．

为求解式(4)，令

算法的流程中，maxitr表示最大迭代次数，ε为误差．在第步中给定Pm，可将其代入式(5)获得λm+1(P)．第～步，固定λm(P)，求解Pm．式(5)可写作 tr(PTXTH L H X P)-．则可通过优化下式求解Pm，即

根据式(6)，为获得Pm，可对XT(H L H+λm(P) H) X进行SVD分解，XT(H L H+ λm(P) H) X= U Σ UT，其中，U UT= UTU= Id，Σ为一对角矩阵，Σ= diag{σ1，σ2，…，σd}且 σ1≥ σ2≥ …≥ σd．则Pm由U的前t列构成．

该算法收敛性的证明方法可见文献[20]．实验过程中发现，该算法收敛很快，其与MDDM的主要区别是，该算法既能够充分利用标记知识，又能充分保留特征的协方差信息．此外，由式(6)可发现，下面形式的目标函数可认为是上述算法求解过程中的一个步骤:

即式(7)的解只是式(4)解的一个中间解．而且式(7)中λ对特征提取效果很重要，往往需要反复地调参才能找到一个合适的值，而式(4)并不需要这样的调参过程．

2 算法验证

为验证文中提出算法的有效性，将文中算法与MLSI、MLDA、MDDM以及PCA进行了比较，降维后的

表1 实验中数据集的相关信息

图1 各算法在Yahoo子数据集上随降维维度变化的性能对比

分类模型采用LIBSVM工具包里的默认支持向量机(Support Vector Machine，SVM)[21]．按照文献[14]中设置MLSI的权重因子为0.5．MDDM和文中所提出算法中的标记核矩阵采用线性核函数进行计算．实验采用的数据集为Yahoo数据集的11个子数据集[15]，表1给出了它们的相关信息．所有数据集均有 5 000 个样本，其中 2 000 个用作训练，3 000 个用作测试[15]．表1中，d表示特征维度，C表示标签数目．

实验中设置t值是以2为间隔，从2逐渐增加到60．测试基于几种降维算法的SVM模型的预测性能，性能评估采用汉明距离(Hamming loss)[1]．图1给出了各算法在Yahoo的11个子数据集上随t变化时的实验结果．

从图1中可以看出，虽然PCA并没有利用标记信息，但其可有效利用特征中的协方差信息，取得了适中的性能，这也表明了有效利用特征协方差信息的重要性．MLDA的性能最差，这是由于其性能受标记数目的影响，当 t≪L 时，其能取得尚可的性能;但是随着t趋近甚至大于L时，其性能甚至可能变差．MLSI的性能有时比PCA的性能好，有时比PCA的性能差，这是因为MLSI严重依赖权重因子，而且简单地将特征信息和标记信息进行简单的相加，其并不是利用标记知识的好方式．

与前述3种算法相比，MDDM和文中提出的算法的性能在11个Yahoo子数据集上都能取得更好的性能，这是由于HSIC能够充分挖掘标记和特征之间的关联关系; 而相比MDDM，新算法能获得相当或者更优的效果，这是由于在充分利用标记知识的同时，保留了特征内部的协方差信息，更加充分地利用了特征．

3 结 束 语

为有效提高多标记特征提取方法的性能，充分利用特征和标记中的信息，文中提出的算法一方面利用HSIC能充分挖掘两组变量关系的能力，使提取的特征与标记之间的依赖性达到最大; 另一方面PCA能利用不相关的特征进行数据重建的能力，使提取过程中特征的协方差矩阵中的信息损失最小．将两者结合进一个目标函数中，并给出了一种有效的优化方法获得最优投影矩阵．实验结果表明，与现有的多标记特征提取方法相比，文中提出的特征提取方法能取得更优的性能．

[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]TSOUMAKAS G, KATAKIS I. Multi-label Classification: an Overview [J]. International Journal of Data Warehousing and Mining, 2007, 3(3): 1-13.

[3]ZHANG J J, FANG M, LI X. Multi-label Learning with Discriminative Features for Each Label [J]. Neurocomputing, 2015, 154: 305-316.

[4]JOLLIFFE J T. Principal Component Analysis [M]. Berlin: Springer, 2001: 1-9.

[5]HASTIE T, TIBSHIRANI R, FRIEDMAN J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction [M]. 2nd Edition. New York: Springer, 2009: 106-113.

[6]YU K, YU S, TRESP V. Multi-label Informed Latent Semantic Indexing [C]//Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. New York: ACM, 2005: 258-265.

[7]DEERWESTER S C, DUMAIS S T, FUMAS G W, et al. Indexing by Latent Semantic Analysis [J]. Journal of the American Society for Information Science, 1990, 41(6): 391-407.

[8]JI S, TANG L, YU S, et al. A Shared-subspace Learning Framework for Multi-label Classification [J]. ACM Transactions on Knowledge Discovery from Data, 2010, 4(2): 1-29.

[9]PARK C H, LEE M. On Applying Linear Discriminant Analysis for Multi-label Problems [J]. Pattern Recognition Letters, 2008, 29(7): 878-887.

[10]YU Y, PEDRYCZ W, MIAO D. Multi-label Classification by Exploiting Label Correlations [J]. Expert Systems with Applications, 2014, 41(6): 2989-3004.

[11]XU J. Multi-label Core Vector Machine with a Zero Label [J]. Pattern Recognition, 2014, 47(7): 2542-2557.

[12]LI P, LI H, WU M. Multi-label Ensemble Based on Variable Pairwise Constraint Projection [J]. Information Sciences, 2013, 222: 269-281.

[13]ENRIQUE SUCAR L,BIELZA C, MORALES E F, et al. Multi-label Classification with Bayesian Network-based Chain Classifiers [J]. Pattern Recognition Letters, 2014, 41(1): 14-22.

[14]WANG H, DING C, HUANG H. Multi-label Linear Discriminant Analysis [C]//Lecture Notes in Computer Science: 6316 LNCS, PART 6. Berlin: Springer Verlag, 2010: 126-139.

[15]GRETTON A, BOUSQUET O, SMOLA A, et al. Measuring Statistical Dependence with Hilbert-Schmidt Norms [C]//Lecture Notes in Artificial Intelligence: 3734 LNAI. Berlin: Springer Verlag, 2005: 63-77.

[16]ZHANG Y, ZHOU Z H. Multi-label Dimensionality Reduction via Dependence Maximization [C]//Proceedings of the National Conference on Artificial Intelligence: 3. Menlo Park: AAAI, 2008: 1503-1505.

[17]SONG L, SMOLA A, GRETTON A, et al. Feature Selection via Dependence Maximization [J]. Journal of Machine Learning Research, 2012, 13: 1393-1434.

[18]CHANG B, KRUGER U, KUSTRA R, et al. Canonical Correlation Analysis Based on Hilbert-Schmidt Independence Criterion and Centered Kernel Target Alignment [C]//30th International Conference on Machine Learning: 2. Princeton: IMLS, 2013: 975-983.

[19]WANG M, SHA F, JORDAN M I. Unsupervised Kernel Dimension Reduction [C]//Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Red Hook: Curran Associates Incorporated, 2010: 2379-2387.

[20]WANG H, YAN S, XU D, et al. Trace Ratio vs. Ratio Trace for Dimensionality Reduction [C]//Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Piscataway: IEEE, 2007: 108-115.

[21]CHANG C C, LIN C J. LIBSVM: a Library for Supporting Vector Machines [J]. ACM Transactions on Intelligent Systems and Technology, 2011, 2(3): 1-27.

(编辑：齐淑娟)

New method for multi-label feature extraction

ZHANGJujie1，FANGMin1，GUOJin2,3

(1. School of Computer Science and Technology, Xidian Univ., Xi’an 710071, China; 2. School of Computer Science and Engineering, Northwestern Polytechnical Univ., Xi’an 710072, China; 3. College of Electronical and Information Engineering, Xi’an Technological Univ., Xi’an 710021, China)

Existing multi-label feature extraction methods are limited by not fully exploiting feature information. To tackle this problem， this paper proposes a new method for multi-label feature extraction. First, it maximizes the Hilbert-Schmidt independence criterion (HSIC) between labels and the features after reducing dimensionality to exploit label information, while it minimizes the information loss using principal component analysis (PCA). Experiments across Yahoo demonstrate the effectiveness and superiority of the proposed method to PCA and 3 state-of-art multi-label feature extraction methods.

multi-label classification; feature extraction; Hilbert-Schmidt independence criterion; principal component analysis

2015-09-07

时间：2016-04-01

国家自然科学基金资助项目(61472305, 61070143)；陕西省科学研究发展计划资助项目(2015GY027)；航空科学基金资助项目(20151981009)

张居杰(1987-)，男，西安电子科技大学博士研究生，E-mail：jujiezhang@stu.xidian.edu.cn．

方 敏(1965-)，女，教授，E-mail：mfang@mail.xidian.edu.cn．

http://www.cnki.net/kcms/detail/61.1076.tn.20160401.1622.022.html

10.3969/j.issn.1001-2400.2016.06.011

TP391.4

A

1001-2400(2016)06-0062-06