第14卷第4期 智能系统学报 Vol.14 No.4 2019年7月 CAAI Transactions on Intelligent Systems Jul.2019 D0:10.11992/tis.201809017 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190409.0946.016html 鲁棒的半监督多标签特征选择方法 严菲，王晓栋 (厦门理工学院计算机与信息工程学院，福建厦门361024) 摘要：针对现有的半监督多标签特征选择方法利用-范数建立谱图易受到噪声影响的问题，文中提出一种鲁 棒的半监督多标签特征选择方法，利用全局线性回归函数建立多标签特征选择模型，结合1图获取局部描述信 息提高模型准确度，引入2！约束提升特征之间可区分度和回归分析的稳定性，避免噪声干扰。在4种开源数 据集上借助多种性能评价标准验证所提出方法，结果表明：本文方法能有效提高分类模型的准确性和对外界噪 声的抗干扰性。 关键词：特征选择；半监督学习；多标签学习：1范式图；线性回归：2！范数；鲁棒；分类；聚类 中图分类号：TP391.4文献标志码：A文章编号：1673-4785(2019)04-0812-08 中文引用格式：严菲，王晓栋.鲁棒的半监督多标签特征选择方法.智能系统学报，2019,14(4)：812-819. 英文引用格式：YAN Fei,,VANG Xiaodong.A robust,semi-supervised,and multi-label feature selection method J.CAAI transac- tions on intelligent systems,2019,14(4):812-819. A robust,semi-supervised,and multi-label feature selection method YAN Fei,WANG Xiaodong (College of Computer and Information Engineering,Xiamen University of Technology,Xiamen 361024,China) Abstract:The existing semi-supervised multi-label feature selection method constructs a spectral image based on the /2- norm,which is sensitive to noise.To handle this problem,a robust semi-supervised multi-label feature selection method is presented in this study.A global linear regression function is utilized to construct the multi-label feature selection model,and the /-norm graph is combined to obtain the local discriminant information.Subsequently,the /2-norm con- straint is added to improve the distinguishability between these features and the stability of regression analysis to avoid noise interference.Four open source datasets are selected to verify the proposed method based on various evaluation cri- teria.The results demonstrate the efficiency of our method with respect to the classification accuracy and robustness Keywords:feature selection;semi-supervised learning;multi-label learning,h-norm graph;linear regression;/2-norm; robust;classification,clustering 在机器学习中，特征选择从原始数据集中提大量已知标签时，该类方法能取得较好的识别效 取最具代表性子集，降低数据维度以提高后续分 果。但在实际应用中获取大量已知标签较困难， 类、聚类处理精度，是当前研究的热点。按已标 且当已知标签数量不足时该类方法性能迅速下 记数据样本数量划分，特征选择方法可分为监 降。无监督特征选择方法B通过对无标签数据 督、无监督和半监督学习。监督特征选择2在已 的训练以发现其隐藏的结构性知识，但由于缺乏 知数据集和类别标签上训练学习模型。在已获取 可区分性的标签信息导致学习性下降。近年来， 收稿日期：2018-09-13.网络出版日期：2019-04-10. 半监督特征选择将少量已知标签数据与未标记数 基金项目：国家自然科学基金项目(61871464)：福建省自然科 学基金面上项目(2017J01511):福建省中青年教师科 据结合建立学习模型，受到学者的广泛研究。D0- 研项目(JATI70417):厦门理工学院科研攀登计划项 目(XPDKQ18012). quire等提出以数据方差为评价准则筛选出重 通信作者：严菲.E-mail:fyan@xmut.edu.cn. 要特征，但其忽略了特征间的相关性，易陷入局
DOI: 10.11992/tis. 201809017 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190409.0946.016.html 鲁棒的半监督多标签特征选择方法 严菲，王晓栋 （厦门理工学院 计算机与信息工程学院，福建 厦门 361024） 摘 要：针对现有的半监督多标签特征选择方法利用 l2 -范数建立谱图易受到噪声影响的问题，文中提出一种鲁 棒的半监督多标签特征选择方法，利用全局线性回归函数建立多标签特征选择模型，结合 l1 图获取局部描述信 息提高模型准确度，引入 l2,1 约束提升特征之间可区分度和回归分析的稳定性，避免噪声干扰。在 4 种开源数 据集上借助多种性能评价标准验证所提出方法，结果表明：本文方法能有效提高分类模型的准确性和对外界噪 声的抗干扰性。 关键词：特征选择；半监督学习；多标签学习；l1 范式图；线性回归；l2,1 范数；鲁棒；分类；聚类 中图分类号：TP391.4 文献标志码：A 文章编号：1673−4785(2019)04−0812−08 中文引用格式：严菲, 王晓栋. 鲁棒的半监督多标签特征选择方法 [J]. 智能系统学报, 2019, 14(4): 812–819. 英文引用格式：YAN Fei, WANG Xiaodong. A robust, semi-supervised, and multi-label feature selection method[J]. CAAI transactions on intelligent systems, 2019, 14(4): 812–819. A robust, semi-supervised, and multi-label feature selection method YAN Fei，WANG Xiaodong (College of Computer and Information Engineering, Xiamen University of Technology, Xiamen 361024, China) Abstract: The existing semi-supervised multi-label feature selection method constructs a spectral image based on the l2 - norm, which is sensitive to noise. To handle this problem, a robust semi-supervised multi-label feature selection method is presented in this study. A global linear regression function is utilized to construct the multi-label feature selection model, and the l1 -norm graph is combined to obtain the local discriminant information. Subsequently, the l2,1-norm constraint is added to improve the distinguishability between these features and the stability of regression analysis to avoid noise interference. Four open source datasets are selected to verify the proposed method based on various evaluation criteria. The results demonstrate the efficiency of our method with respect to the classification accuracy and robustness. Keywords: feature selection; semi-supervised learning; multi-label learning; l1 -norm graph; linear regression; l2,1-norm; robust; classification; clustering 在机器学习中，特征选择从原始数据集中提 取最具代表性子集，降低数据维度以提高后续分 类、聚类处理精度，是当前研究的热点。按已标 记数据样本数量划分，特征选择方法可分为监 督、无监督和半监督学习。监督特征选择[1-2] 在已 知数据集和类别标签上训练学习模型。在已获取 大量已知标签时，该类方法能取得较好的识别效 果。但在实际应用中获取大量已知标签较困难， 且当已知标签数量不足时该类方法性能迅速下 降。无监督特征选择方法[3-4] 通过对无标签数据 的训练以发现其隐藏的结构性知识，但由于缺乏 可区分性的标签信息导致学习性下降。近年来， 半监督特征选择将少量已知标签数据与未标记数 据结合建立学习模型，受到学者的广泛研究。Doquire 等 [5] 提出以数据方差为评价准则筛选出重 要特征，但其忽略了特征间的相关性，易陷入局 收稿日期：2018−09−13. 网络出版日期：2019−04−10. 基金项目：国家自然科学基金项目 (61871464)；福建省自然科 学基金面上项目 (2017J01511)；福建省中青年教师科 研项目 (JAT170417)；厦门理工学院科研攀登计划项 目 (XPDKQ18012). 通信作者：严菲. E-mail: fyan@xmut.edu.cn. 第 14 卷第 4 期 智 能 系 统 学 报 Vol.14 No.4 2019 年 7 月 CAAI Transactions on Intelligent Systems Jul. 2019
第4期 严菲，等：鲁棒的半监督多标签特征选择方法 ·813· 部最优。为解决此问题，研究者提出基于谱图理 xi-xi 论的半监督方法，依据某准则建立Laplacian矩阵 x为x的近邻 (1) 提取数据底层流形结构进行特征选择，如Lu等阿 0.其他 提出以迹比准则为评价机制，Ma等忉引入流形正 式中：σ为宽度参数，控制函数的径向作用范围。 则化的稀疏特征选择方法等。 基于式(1)构造加权图，谱聚类算法将聚类问 在现实应用中，存在某个数据样本同时隶属 题转化为图划分问题，但其最优解为NP问题。 于一个或多个不同的类别，如网页分类、自然场 传统解决方法以借助松弛方法得到连续的类别标 景分类等。以图像标注为例，一幅自然图像可包 签，进而转换为率切(ratio cut)问题： 含多种场景，如树、陆地、沙漠，即一个图像样本 min Tr(2"LO) (2) Q'0=1 可属于多种类别。最简单的解决方法将多标签簇 式中：Q=[q12…qJeR"为聚类指标矩阵，c为 问题分解为多个独立单标签分类问题，但其忽略 类别标签数，qk∈R为Q矩阵第k列；L为谱图 了多标签间的相关性。为此，Ji等1利用多标签 Laplacian矩阵，其定义为L=D-A,D为对角矩阵， 的共享子空间建立学习框架，文献[9]使用互信 其每个i对角元素D:=∑A。为获取最终的类别 息和交互信息的理论方法寻找最优子集，这些方 标签，必须进一步借助聚类算法将连续值矩阵 法均属于监督类方法。但现实应用中大量训练样 本中已标记数据极少。如何利用未标记数据及其 进行离散化，如采用K-means算法等。Nie等 提出基于I1范数图模型来获取更清晰的流形结 之间的关系信息提高泛化性能，给多标签特征选 构，上述式(2)转换为 择方法带来了巨大的挑战。针对此问题，研究者 提出半监督多标签特征学习。Alalga等0提出利 i∑Alq:-qb (3) 用Laplacian得分判断多标签类间关系，但其利用 l2-范数建立Laplacian矩阵易受离群点的影响，从 2 基于1，图的半监督多标签特征选 而导致学习稳定性差。Chang等提出基于全局 择方法 线性约束的多标签半监督方法，无需构建Lapla- cian图和特征分解操作，计算量少，速度快，但其 2.1 问题定义 忽略了真实数据嵌入在高维空间的底层流形结 给定数据集X=[x1x2…Xx41…xn]ER 构。受启于上述研究工作，本文提出基于1图的 x,∈R为第i组数据，d为维度，I为已标记样本数 半监督多标签特征选择方法SMFSL(semi-super- (亿《n)。设Y=y1y2…y'∈R为已标记数据集 vised multi-label feature selection method based on L- 的标签矩阵，，∈{0,1}为数据x,的类别标签。 norm graph),利用全局线性回归函数方法和l2,:组 若x,被标识为j类，则Y=1,否则Y=O。为获取 稀疏约束建立多标签特征选择模型，引用1，图模 未标签数据的类别标签信息，定义预测标签矩阵 型以提高特征选择准确度。 P=U方[长]eR心其中初始化为 Fm∈Raxc则为未标签数据的标签矩阵，且初始 1范数图模型 化F=O,O为所有元素为0的矩阵。定义W=[w, 在机器学习中，基于图的学习方法通过构建 w2· weR为特征选择分类器，半监督多标 近邻图，利用样本间反映流形分布而建立问题模 签特征选择学习模型定义为 型，得到广泛的研究应用。其中，基于谱图理论 的谱聚类学习方法)，在多种应用场景下取得较 w∑1os(W,fD+y2(W (4) 好的效果。 在式(4)中，2)为正则化项（可以选择不同 谱聚类根据数据样本间的相似关系建立 的正则化模型，如1范数、2：范数等)，参数y为正 Laplacian矩阵，利用特征值和特征向量获取样本 则化参数，loss()为损失函数。从模型的简单性、 间的内在联系。给定n组数据集X={x1,x2,, 高效性角度进行考虑，本文选择最小二乘法作为 xn}eR",其中x,∈R为第i组数据，d为维度。 损失函数，式(4)可表示为 定义G=(V,A)为无向权重图，其中V为向量集， wK'w+b'-F+2(刚 (5) 相似矩阵A=[A1A2·AnER"“,A=A≥0。基于 式中：beR为偏置量；1eR”为元素值全是1的 高斯核函数σ相似矩阵A定义为 列向量
部最优。为解决此问题，研究者提出基于谱图理 论的半监督方法，依据某准则建立 Laplacian 矩阵 提取数据底层流形结构进行特征选择，如 Liu 等 [6] 提出以迹比准则为评价机制，Ma 等 [7] 引入流形正 则化的稀疏特征选择方法等。 在现实应用中，存在某个数据样本同时隶属 于一个或多个不同的类别，如网页分类、自然场 景分类等。以图像标注为例，一幅自然图像可包 含多种场景，如树、陆地、沙漠，即一个图像样本 可属于多种类别。最简单的解决方法将多标签簇 问题分解为多个独立单标签分类问题，但其忽略 了多标签间的相关性。为此，Ji 等 [8] 利用多标签 的共享子空间建立学习框架，文献 [9] 使用互信 息和交互信息的理论方法寻找最优子集，这些方 法均属于监督类方法。但现实应用中大量训练样 本中已标记数据极少。如何利用未标记数据及其 之间的关系信息提高泛化性能，给多标签特征选 择方法带来了巨大的挑战。针对此问题，研究者 提出半监督多标签特征学习。Alalga 等 [10] 提出利 用 Laplacian 得分判断多标签类间关系，但其利用 l2 -范数建立 Laplacian 矩阵易受离群点的影响，从 而导致学习稳定性差。Chang 等 [11] 提出基于全局 线性约束的多标签半监督方法，无需构建 Laplacian 图和特征分解操作，计算量少，速度快，但其 忽略了真实数据嵌入在高维空间的底层流形结 构。受启于上述研究工作，本文提出基于 l1 图的 半监督多标签特征选择方法 SMFSL (semi-supervised multi-label feature selection method based on L1 - norm graph)，利用全局线性回归函数方法和 l2,1 组 稀疏约束建立多标签特征选择模型，引用 l1 图模 型以提高特征选择准确度。 1 范数图模型 在机器学习中，基于图的学习方法通过构建 近邻图，利用样本间反映流形分布而建立问题模 型，得到广泛的研究应用。其中，基于谱图理论 的谱聚类学习方法[12] ，在多种应用场景下取得较 好的效果。 谱聚类根据数据样本间的相似关系建 立 Laplacian 矩阵，利用特征值和特征向量获取样本 间的内在联系。给定 n 组数据集 X={x1，x2，···， xn}∈R d×n ，其中 xi∈R d 为第 i 组数据，d 为维度。 定义 G=(V，A) 为无向权重图，其中 V 为向量集， 相似矩阵 A=[A1 A2 ··· An ]∈R n×n ，Aji=Aij≥0。基于 高斯核函数 σ 相似矩阵 A 定义为 Ai j = exp − xi − xj 2 σ2 , xi为xj的近邻 0, 其他 (1) 式中：σ 为宽度参数，控制函数的径向作用范围。 基于式 (1) 构造加权图，谱聚类算法将聚类问 题转化为图划分问题，但其最优解为 NP 问题。 传统解决方法以借助松弛方法得到连续的类别标 签，进而转换为率切 (ratio cut) 问题： min QTQ=I Tr( Q T LQ) (2) Dii = ∑n j=1 Ai j 式中：Q=[q1 q2 ··· qn ] T∈R n×c 为聚类指标矩阵，c 为 类别标签数，qk∈R c 为 Q 矩阵第 k 列；L 为谱图 Laplacian 矩阵，其定义为 L=D-A，D 为对角矩阵， 其每个 i 对角元素 。为获取最终的类别 标签，必须进一步借助聚类算法将连续值矩阵 Q 进行离散化，如采用 K-means 算法等。Nie 等 [13] 提出基于 l1 范数图模型来获取更清晰的流形结 构，上述式 (2) 转换为 min QTQ=I ∑n i, j=1 Ai j qi − qj 2 (3) 2 基于 l1 图的半监督多标签特征选 择方法 2.1 问题定义 l ≪ n F = [ f1 f2 · · fn ]T = [ Fl Fu ] ∈ R n×c 给定数据集 X=[x1 x2 ··· xl xl+1··· xn ]∈R d×n ， xi∈R d 为第 i 组数据，d 为维度，l 为已标记样本数 ( )。设 Yl=[y1 y2 ··· yl ] T∈R l×c 为已标记数据集 的标签矩阵， yi∈{0,1}c 为数据 xi 的类别标签。 若 xi 被标识为 j 类，则 Yij=1，否则 Yij=0。为获取 未标签数据的类别标签信息，定义预测标签矩阵 ，其中 Fl 初始化为 Yl， Fu∈R (n-l)×c 则为未标签数据的标签矩阵，且初始 化 Fu=Ο，Ο 为所有元素为 0 的矩阵。定义 W=[w1 w2 ··· wd ] T∈R d×c 为特征选择分类器，半监督多标 签特征选择学习模型定义为 min W,F,Fl=Yl ∑n i=1 loss(W, fi)+γΩ(W) (4) 在式 (4) 中， Ω(·) 为正则化项 (可以选择不同 的正则化模型，如 l1 范数、l2,1 范数等)，参数 γ 为正 则化参数，loss(·) 为损失函数。从模型的简单性、 高效性角度进行考虑，本文选择最小二乘法作为 损失函数，式 (4) 可表示为 min W,F,b,Fl=Yl X TW +1b T − F 2 F +γΩ(W) (5) 式中：b∈R c 为偏置量；1∈R n 为元素值全是 1 的 列向量。 第 4 期 严菲，等：鲁棒的半监督多标签特征选择方法 ·813·
·814· 智能系统学报 第14卷 从式（⑤）可以看出，利用线性回归函数逐渐逼 保持W,S,F不变，将式(8)对b求导，令求 近可找出全局最优，但却忽略了其局部数据之间 导结果为0，得到： 相关性。为提高特征选择准确度，文献[7)]提出 1 (9) 建立相似矩阵以获取局部流形结构，建立的学习 b-Tsi(F'S-Wxs) 模型如下： 将式(9)代入式(8)，为简化公式，令H= 盟之4-成+ 其中H为中心化矩陈.IeR为 I- i.l (6) 单位矩阵。式(8)将转换为： alXW+Ib-F+y2(W) (FLF+a((HXW-HF)'S 式中a为平衡参数。 (10) HXW-HF))+yllWll 半监督学习应用中，已标签的数据集往往只 将式(10)对W求导，并令求导结果为0，得到 占据小部分，无标签数据集非常庞大，而离群点 aXHSHXTW+yDwW=aXHSHF (11) 一般存在无标签数据集中。Nie等I)研究证明， 式中Dm为对角矩阵，可表示为 采用(，范数有效减少噪音的影响，从而获取更清 1 晰的谱聚类结构，因此本文提出将1范数引入半 2lw1l2+6 监督学习模型中。同时为减少外界噪声点的干 Dw= (12) 扰，本文提出采用12：范数来约束最小二乘损 2llwallk +6 失函数。给定任意矩阵M∈Raxc,其定义为 由于矩阵Dm与W相关，无法直接求解上 M=公区G,结合式队式回转换为 式。为解决此问题，将W随机初始化以获取矩阵 D,转换式(11)，推导出： ∑A-fl+aKw+B-FLt W=a(aXHSHXT+yDw)XHSHF (13) y2(W) 为求解F,将式(10)进行变换，得到： 为有效地去除原数据集的冗余特征，本文对 ipu(FTLF)+ot(FHSHF)+yt(WD.W)+ (14) 特征选择矩阵W引入正则化模型12！范数，最后 atr(WTXHSHXW)-2atr(FTHSHXW) 提出的目标函数定义如下： 转换式(14)，得到： iutallxw++wlk ipt(FLF)+at(FHSHF) tr(WT(aXHSHXT+yD.)W)- (15) (7) 2atr(FHSHXW) 2.2学习模型求解 将W的求导结果式(13)代入式(15)，得到： 为获取最终选择特征子集，将对多标签特征 mintr(FTLF)+atr(FTHSHF)-a2tr 选择的目标函数进行模型求解。由于目标函数 (FHSHX(aXHSHXT+yDw)'XHSHF) (16) 式(7)引入的12，：范数具有非光滑特征，无法直接 定义M为： 进行求解，因此本文提出一种迭代优化方法来解决。 M=L+aHSH- (17) 首先，将目标函数（⑦）进行转换。定义对角矩 (aXHSHXT+yDw)）XHSH 阵S,其元素S:=2xw+D-F业+6。其中，为 将式(16)按分块矩阵形式转换为： 防止S:除数为0，δ的值为接近于0的正常量。 mintr F TI MM F lF.MaM]F. 式(7)转换后形式如下： 将上式对F求导，并令求导结果为0，得到： wsy(FLF+a(XTW+1bT-F) (8) F=-M MF S(XTW+1bT-F))+rllWlk 基于以上推导过程求解学习模型，本文方法 式中：i为对角矩阵且定义为i=D-A;矩阵A元 具体描述如下： A 素定文为A,:D为对角矩阵，元素值为 算法1 SMFSL 输入数据集X∈Rm,类别标签Y,∈Rc,相 D:=∑，Aj。给定任意矩阵B∈R"”,对矩阵B迹 似矩阵A,参数a,y: 函数定义m(B)=宫B,B,为矩阵B的第1个对角 输出特征选择矩阵W,预测标签矩阵F。 元素。 I)=O,随机初始化WR,bR,F'Rmxc
从式 (5) 可以看出，利用线性回归函数逐渐逼 近可找出全局最优，但却忽略了其局部数据之间 相关性。为提高特征选择准确度，文献 [7] 提出 建立相似矩阵以获取局部流形结构，建立的学习 模型如下： min W,F,b,Fl=Yl ∑n i, j=1 Ai j fi − fj 2 2 + α X TW +1b T − F 2 F +γΩ(W) (6) 式中 α 为平衡参数。 M2,1 = ∑d i=1 vt∑c j=1 M2 i j 半监督学习应用中，已标签的数据集往往只 占据小部分，无标签数据集非常庞大，而离群点 一般存在无标签数据集中。Nie 等 [13] 研究证明， 采用 l1 范数有效减少噪音的影响，从而获取更清 晰的谱聚类结构，因此本文提出将 l1 范数引入半 监督学习模型中。同时为减少外界噪声点的干 扰，本文提出采用 l2,1 范数[3] 来约束最小二乘损 失函数。给定任意矩 阵 M∈R d × c ，其定义为 。结合式 (3)，式 (6) 转换为 min W,F,b,Fl=Yl ∑n i, j=1 Ai j fi − fj 2 +α X TW +1b T − F 2,1 + γΩ(W) 为有效地去除原数据集的冗余特征，本文对 特征选择矩阵 W 引入正则化模型 l2,1 范数，最后 提出的目标函数定义如下： min W,F,b,Fl=Yl ∑n i, j=1 Ai j fi − fj 2 +α X TW +1b T − F 2,1 +r∥W∥2,1 (7) 2.2 学习模型求解 为获取最终选择特征子集，将对多标签特征 选择的目标函数进行模型求解。由于目标函数 式 (7) 引入的 l2,1 范数具有非光滑特征，无法直接 进行求解，因此本文提出一种迭代优化方法来解决。 Sii = 1 2∥XTW +1b T − F∥2 +δ 首先，将目标函数 (7) 进行转换。定义对角矩 阵 S，其元素 。其中，为 防止 Sii 除数为 0，δ 的值为接近于 0 的正常量。 式 (7) 转换后形式如下： min W,S,F,b,Fl=Yl tr( F T L˜F +α ( X TW +1b T − F )T S ( X TW +1b T − F ))+r∥W∥2,1 (8) L˜ L˜ = D˜ − A˜ A˜ A˜ i j = Ai j 2 fi − fj 2 D˜ D˜ ii = ∑ j A˜ i j tr(B) = ∑n i=1 Bii 式中： 为对角矩阵且定义为 ；矩阵 元 素定义为 ； 为对角矩阵，元素值为 。给定任意矩阵 B∈R n×n ，对矩阵 B 迹 函数定义 ，Bii 为矩阵 B 的第 i 个对角 元素。 保持 W，S，F 不变，将式 (8) 对 b 求导，令求 导结果为 0，得到： b= 1 1 T S1 ( F TS−WTXS) (9) H= ( I− 1 1 T S1 11T S ) 将 式 ( 9 ) 代 入 式 (8) ，为简化公式，令 ，其中 H 为中心化矩阵，I∈R n×n 为 单位矩阵。式 (8) 将转换为： min W,S,F tr(F T L˜F +α( ( HXTW − HF)T S HXTW − HF))+γ∥W∥2,1 (10) 将式 (10) 对 W 求导，并令求导结果为 0，得到 αXHSHXTW +γDWW = αXHSHF (11) 式中 DW 为对角矩阵，可表示为 DW = 1 2∥w1∥2 +δ . . . 1 2∥wd∥2 +δ (12) 由于矩阵 D W 与 W 相关，无法直接求解上 式。为解决此问题，将 W 随机初始化以获取矩阵 DW，转换式 (11)，推导出： W = α ( αXHSHXT +γDW )−1 XHSHF (13) 为求解 F，将式 (10) 进行变换，得到： min W,F tr(F T L˜F)+αtr( F THSHF) +γtr( WT DwW ) + αtr( WTXHSHXTW ) −2αtr( F THSHXTW ) (14) 转换式 (14)，得到： min W,F tr(F T L˜F)+αtr( F THSHF) + tr( WT ( αXHSHXT +γDw ) W ) − 2αtr( F THSHXTW ) (15) 将 W 的求导结果式 (13) 代入式 (15)，得到： min F tr(F T L˜F)+αtr( F THSHF) −α 2 tr ( F THSHXT ( αXHSHXT +γDW )−1 XHSHF) (16) 定义 M 为： M = L˜ +αHSH− ( αXHSHXT +γDW )−1 XHSH (17) 将式 (16) 按分块矩阵形式转换为： min Fu tr [ Fl Fu ]T [ Mll Mul Mlu Muu ] [ Fl Fu ] 将上式对 Fu 求导，并令求导结果为 0，得到： Fu = −M−1 uu MulFl 基于以上推导过程求解学习模型，本文方法 具体描述如下： 算法 1 SMFSL X ∈ R d×n Yl ∈ R l×c α, γ 输入 数据集 ，类别标签 ，相 似矩阵 A，参数 ； 输出 特征选择矩阵 W，预测标签矩阵 F。 1) t=0，随机初始化 W t ϵR d×c ，b t ϵR c ，F t ϵR n×c ·814· 智 能 系 统 学 报 第 14 卷
第4期 严菲，等：鲁棒的半监督多标签特征选择方法 ·815 2)repeat 将(4= Aij -L代入式(19，得到： )计算1=0-4，其中产D为对 角矩阵，其元素值为D=∑A ar-rE+mL+sw,r.到 2-f2 4)计算对象矩阵S,其第i个元素 了A-f +yWl2,+g(W,F,(b,S） 1 台2f-f孔 Γ2Xw+1(b)T-F2+6 (21) 列计第以H=:P列 结合引理1的式(18)，有以下公式： 6)根据式(12)计算对角矩阵D 7)根据式(17)计算M+1=i+aHSH-a2 HS'HXT 立ar (aXHSHXT+yD)XHSH 8)计算F=-(M)MF,并且更新F+1= r-置 (22) 结合式(20)和(21)，得到 9)更新 -cw.m.os) W a(aXHS'HXT+yD)XHS'HF 2A-%+iw+smFs列 10)更新 (23) ()sI-(w)xs) 接下来，固定F为F1、b为b、S为S来求 11)=41 解W,根据算法1可得出： 12)until收敛 w=argmin 在得到特征选择矩阵W后，按照w (24) (i=1,2,…,d)的值，对输入数据的特征进行降序排 ylwlk+g(W.F,(b).S) 列，其中最前面的p个特征即为所选择的特征。 同样，参考文献[14]中的方法，可得出： 2.3收敛性分析 本小节将对上一小节提出的SMFSL算法收 -Lsw.s) 敛性进行证明。 引理1对于任意非零的向量p,q∈R°，有以 交a-l+wFm到 (25) 下不等式成立： 接下来，固定F为F1、W为W1求解b、 风-荒s- (18) S,同样，参考文献[14中的方法，可得出： 根据以上引理，本文提出以下定理： 豆ar-rl-tx0.mw5s)s 定理1算法SMFSL在每次迭代过程中最小 化目标函数。 4"-"l+wL:+m一. 证明为方便起见，首先定义g(W,F,b「，S)= (26) atr(XW4lb-F)SXW4lbT-F)。目标函数可写为： 最后，结合式(22)、(23)和(24)，可得出： 册2A,-成+w+ewF.a9 ob1.) 假设在第1次迭代后获得了W,F,b'和S。在 下一次迭代中，固定W为W、b为b、S为S来求 2aG-l+wj.cr.r.w到 解F,参考文献[14]中的方法可得出： (27) 从式(25)中可证明出算法1是收敛的。 -ormws)< 3实验分析 是④，-f+w+s,Rs 3.1对比方法及实验数据 (20) 为验证本文方法的有效性，对相关方法进行
2) repeat L˜ = D˜ − A˜ A˜ i j = Ai j 2 fi − fj 2 D˜ D˜ ii = ∑ j A˜ i j 3) 计算 ，其中 ， 为对 角矩阵，其元素值为 S t Sii t = 1 2 XTWt +1(b t ) T − Ft 2 +δ 4) 计算对象矩阵 ，其第 i 个元素 H = ( I− 1 1 T S t1 11T S t ) 5) 计算 H， D t 6) 根据式 w (12) 计算对角矩阵 Mt+1 = L˜ +αHStH −α 2HStHXT ( αXHStHXT +γD t w )−1 XHStH 7) 根据式 (17) 计算 F t+1 u =− ( Mt+1 uu )−1Mt+1 ul Fl F t+1 = [ Fl F t+1 u ] 8) 计算 ，并且更新 9) 更新 Wt+1 = α ( αXHStHXT +γD t w )−1 XHStHFt+1 10) 更新 b t+1 = 1 1 T S t1 (( F t+1 )T S t 1− ( Wt+1 )T XSt 1 ) 11) t=t+1 12) until 收敛 w t i 2 (i = 1,2,··· ,d) 在得到特征选择矩 阵 W 后，按照 的值，对输入数据的特征进行降序排 列，其中最前面的 p 个特征即为所选择的特征。 2.3 收敛性分析 本小节将对上一小节提出的 SMFSL 算法收 敛性进行证明。 引理 1 对于任意非零的向量 p,q∈R c ，有以 下不等式成立： ∥p∥2 − ∥p∥ 2 2 2∥q∥2 ⩽ ∥q∥2 − ∥q∥ 2 2 2∥q∥2 (18) 根据以上引理，本文提出以下定理： 定理 1 算法 SMFSL 在每次迭代过程中最小 化目标函数。 证明 为方便起见，首先定义 g(W,F,b T ,S)= αtr((X TW+1b T -F) T S(X TW+1b T -F)) 。目标函数可写为： min W,F,b ∑n i, j=1 A˜ i j fi − fj 2 2 +γ∥W∥2,1 +g ( W,F, b T ,S ) (19) 假设在第 t 次迭代后获得了 W，F,b T 和 S。在 下一次迭代中，固定 W 为 W t 、b 为 b t 、S 为 S t 来求 解 F t+1，参考文献 [14] 中的方法可得出： ∑n i, j=1 (A˜ t )i j f t+1 i − f t+1 j 2 2 +γ∥Wt ∥2,1+g ( Wt ,F t+1 ,(b t ) T ,S t ) ⩽ ∑n i, j=1 (A˜ t )i j f t i − f t j 2 2 +γ∥Wt ∥2,1 +g ( Wt ,F t ,(b t ) T ,S t ) (20) (A˜t )i j = Ai j 2 f t i − f t j 2 将 代入式 (19)，得到： ∑n i, j=1 Ai j f t+1 i − f t+1 j 2 2 2 f t i − f t j 2 +γ Wt 2,1 +g ( Wt ,F t+1 ,(b t ) T ,S t ) ⩽ ∑n i, j=1 Ai j f t i − f t j 2 2 2 f t i − f t j 2 +γ Wt 2,1 +g ( Wt ,F t ,(b t ) T ,S t ) (21) 结合引理 1 的式 (18)，有以下公式： ∑n i, j=1 Ai j f t+1 i − f t+1 j 2 − f t+1 i − f t+1 j 2 2 2 f t i − f t j 2 ⩽ ∑n i, j=1 Ai j f t i − f t j 2 − f t i − f t j 2 2 2 f t i − f t j 2 (22) 结合式 (20) 和 (21)，得到 ∑n i, j=1 Ai j f t+1 i − f t+1 j 2 +γ∥Wt ∥2,1 +g ( Wt ,F t+1 ,(b t ) T ,S t ) ⩽ ∑n i, j=1 Ai j f t i − f t j 2 +γ∥Wt ∥2,1 +g ( Wt ,F t ,(b t ) T ,S t ) (23) 接下来，固定 F 为 F t+1 、b 为 b t 、S 为 S t 来求 解 W t+1，根据算法 1 可得出： Wt+1 = argmin W ∑n i, j=1 (A˜ t )i j f t+1 i − f t+1 j 2 2 + γ∥Wt ∥2,1 +g ( Wt ,F t+1 ,(b t ) T ,S t ) (24) 同样，参考文献 [14] 中的方法，可得出： ∑n i, j=1 Ai j f t+1 i − f t+1 j 2 +γ Wt+1 2,1 +g ( Wt+1 ,F t+1 ,(b t ) T ,S t ) ⩽ ∑n i, j=1 Ai j f t+1 i − f t+1 j 2 +γ Wt 2,1 +g ( Wt ,F t+1 ,(b t ) T ,S t ) (25) 接下来，固定 F 为 F t+1 、W 为 W t+1 求解 b t+1 、 S t+1，同样，参考文献 [14] 中的方法，可得出： ∑n i, j=1 Ai j f t+1 i −f t+1 j 2 +γ Wt+1 2,1 +g ( Wt+1 ,F t+1 ,(b t+1 ) T ,S t+1 ) ⩽ ∑n i, j=1 Ai j f t+1 i − f t+1 j 2 +γ Wt 2,1 +g ( Wt ,F t+1 ,(b t ) T ,S t ) (26) 最后，结合式 (22)、(23) 和 (24)，可得出： ∑n i, j=1 Ai j f t+1 i − f t+1 j 2 +γ Wt+1 2,1 +g ( Wt+1 ,F t+1 ,(b t+1 ) T ,S t+1 ) ⩽ ∑n i, j=1 Ai j f t i − f t j 2 +γ Wt 2,1 +g ( Wt ,F t ,(b t ) T ,S t ) (27) 从式 (25) 中可证明出算法 1 是收敛的。 3 实验分析 3.1 对比方法及实验数据 为验证本文方法的有效性，对相关方法进行 第 4 期 严菲，等：鲁棒的半监督多标签特征选择方法 ·815·
·816- 智能系统学 报 第14卷 描述。 标签分类器，其中MLKNN的优化参数参照文献[18。 AIl-feature:其数据未采用特征选择，本次实 表1实验数据集 验以该分类结果作为基准线。 Table 1 Experimental datasets TRCFS(trace ratio criterion for feature selec- 样本特征类别 数据集 数数数 特征数 tion):采用谱图的半监督学习方法，其通过引入 MIML 20001355 {20,40,60,80.100,120} 具有抗噪声的率切准则提高特征选择的效率。 YEAST 2417 103 14 20.40.60.80.100) CSFS(convex semi-supervised multi-label fea- Education 5000 550 33 {100.200,300.400.500} ture selection)a:该将线性回归模型引入特征选择 Entertainment500064021{100,200,300,400,500,600} 模型中，是一种快速的半监督特征选择方法。 3.2 性能对比分析 FSNM(feature selection via joint /2,i-norms min- 本次实验选择Hamming loss(HL,汉明损失)、 imization):监督学习方法，其在损失函数和正则 One-Error(OE,单错误)作为评价指标9用来评价 化方面采用1，范数模型进行特征选择。 方法的分类性能。其中，Hamming loss和One Er-- 本次实验将所提出方法应用到各种场景，包 ror值越低代表性能越好。图1、2列出了以AIl- 括自然场景分类、网页分类和基因功能分类。同 feature方法的分类结果为基准线，TRCFS、CSFS 时本文将各方法应用到多种开源数据库，包括 FSNM以及本文提出的SMFSL方法在各种数据 MML、YEAST、Education和Entertainment, 集的性能对比分析。其中图1分别为HL评价标 数据集的相关属性描述如表1所示。 准的性能提升百分比，以及图2分别为OE评价 本文对于每一种方法所有涉及到的参数（如 标准的性能提升百分比。从图中可以看出： 果有的话)的范围设定为{10、102、10°、102、10)。 1)大部分特征选择方法要优于未采用特征选 择的AIl-feature,.由此可证明特征选择有助于提高 对于每种数据集，随机选择n个样本作为训练集， 多标记学习性能。但在YEAST、Education和En- 其中分别选择10%、20%和40%的数据为已标记 tertainment数据集中，TRCFS学习性能整体略低 数据集，其余为未标记数据。实验独立重复5次， 于All-feature,但该方法经过特征选择后维度会有 最后取其平均值。本次实验选择MLKNN作为多 所降低，从而能有效地节省后续分类时间。 TRCFS TRCFS 4 0 SMFSL MIM Educ MIML YEAST Education Entertainm MIML YEAST Education Ente Entertainm (a)已标记数据集为10% (b)已标记数据集为20% (c)已标记数据集为40% 图1各种方法在各数据集上的汉明损失 Fig.I Hamming loss comparison of various methods on various datasets TRCFS TRCFS IRCFS CSFS CSES SNM SMESL SMFSL 2 YEAS Edue Entertainment MIML YEAST Education MIML Entertain YEAST Education (a)已标记数据集为10% (b)已标记数据集为20% (c)已标记数据集为40% 图2 各种方法在各数据集上的单错误 Fig.2 One-Error comparison of various methods on various datasets
描述。 All-feature：其数据未采用特征选择，本次实 验以该分类结果作为基准线。 TRCFS(trace ratio criterion for feature selection)[6] ：采用谱图的半监督学习方法，其通过引入 具有抗噪声的率切准则提高特征选择的效率。 CSFS(convex semi-supervised multi-label feature selection)[12] ：该将线性回归模型引入特征选择 模型中，是一种快速的半监督特征选择方法。 FSNM(feature selection via joint l2,1-norms minimization)[1] ：监督学习方法，其在损失函数和正则 化方面采用 l2,1 范数模型进行特征选择。 本次实验将所提出方法应用到各种场景，包 括自然场景分类、网页分类和基因功能分类。同 时本文将各方法应用到多种开源数据库，包括 MIML[15] 、YEAST[16] 、Education[17] 和 Entertainment [17] ， 数据集的相关属性描述如表 1 所示。 本文对于每一种方法所有涉及到的参数 (如 果有的话) 的范围设定为{10−4 、10−2 、100 、102 、104 }。 对于每种数据集，随机选择 n 个样本作为训练集， 其中分别选择 10%、20% 和 40% 的数据为已标记 数据集，其余为未标记数据。实验独立重复 5 次， 最后取其平均值。本次实验选择 MLKNN 作为多 标签分类器，其中 MLKNN 的优化参数参照文献 [18]。 表 1 实验数据集 Table 1 Experimental datasets 数据集 样本 数 特征 数 类别 数 特征数 MIML 2 000 135 5 {20，40，60，80，100，120} YEAST 2 417 103 14 {20，40，60，80，100} Education 5 000 550 33 {100，200，300，400，500} Entertainment 5 000 640 21 {100，200，300，400，500，600} 3.2 性能对比分析 本次实验选择 Hamming loss(HL，汉明损失)、 One-Error(OE，单错误) 作为评价指标[19] 用来评价 方法的分类性能。其中，Hamming loss 和 One Error 值越低代表性能越好。图 1、2 列出了以 Allfeature 方法的分类结果为基准线，TRCFS、CSFS、 FSNM 以及本文提出的 SMFSL 方法在各种数据 集的性能对比分析。其中图 1 分别为 HL 评价标 准的性能提升百分比，以及图 2 分别为 OE 评价 标准的性能提升百分比。从图中可以看出： 1) 大部分特征选择方法要优于未采用特征选 择的 All-feature，由此可证明特征选择有助于提高 多标记学习性能。但在 YEAST、Education 和 Entertainment 数据集中，TRCFS 学习性能整体略低 于 All-feature，但该方法经过特征选择后维度会有 所降低，从而能有效地节省后续分类时间。 5 4 3 2 1 0 −1 MIML YEAST (a) 已标记数据集为 10% 汉明损失性能提升率/% Education Entertainment 4 3 2 1 0 −3 −2 −1 MIML YEAST (b) 已标记数据集为 20% 汉明损失性能提升率/% Education Entertainment 5 4 3 2 1 0 −4 −3 −2 −1 MIML YEAST (c) 已标记数据集为 40% 汉明损失性能提升率/% Education Entertainment TRCFS CSFS FSNM SMFSL TRCFS CSFS FSNM SMFSL TRCFS CSFS FSNM SMFSL 图 1 各种方法在各数据集上的汉明损失 Fig. 1 Hamming loss comparison of various methods on various datasets 8 6 4 2 0 −2 MIML YEAST (a) 已标记数据集为 10% 汉明损失性能提升率/% Education Entertainment 8 6 4 2 0 −4 −2 MIML YEAST (b) 已标记数据集为 20% 汉明损失性能提升率/% Education Entertainment 8 6 4 2 0 −6 −4 −2 MIML YEAST (c) 已标记数据集为 40% 汉明损失性能提升率/% Education Entertainment TRCFS CSFS FSNM SMFSL TRCFS CSFS FSNM SMFSL TRCFS CSFS FSNM SMFSL 图 2 各种方法在各数据集上的单错误 Fig. 2 One-Error comparison of various methods on various datasets ·816· 智 能 系 统 学 报 第 14 卷