第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] 提出基于全局 线性约束的多标签半监督方法，无需构建 Lapla￾cian 图和特征分解操作，计算量少，速度快，但其 忽略了真实数据嵌入在高维空间的底层流形结 构。受启于上述研究工作，本文提出基于 l1 图的 半监督多标签特征选择方法 SMFSL (semi-super￾vised 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·