第14卷第5期 智能系统学报 Vol.14 No.5 2019年9月 CAAI Transactions on Intelligent Systems Sep.2019 D0:10.11992/tis.201807027 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190525.1801.002.html 代价敏感数据的多标记特征选择算法 黄琴2，钱文彬2，王映龙，吴兵龙 (1.江西农业大学计算机与信息工程学院，江西南昌330045,2.江西农业大学软件学院，江西南昌330045) 摘要：在多标记学习中，特征选择是提升多标记学习分类性能的有效手段。针对多标记特征选择算法计算复 杂度较大且未考虑到现实应用中数据的获取往往需要花费代价，本文提出了一种面向代价敏感数据的多标记 特征选择算法。该算法利用信息嫡分析特征与标记之间的相关性，重新定义了一种基于测试代价的特征重要 度准则，并根据服从正态分布的特征重要度和特征代价的标准差，给出一种合理的阈值选择方法，同时通过阈 值剔除冗余和不相关特征，得到低总代价的特征子集。通过在多标记数据的实验对比和分析，表明该方法的有 效性和可行性。 关键词：特征选择；属性约简；代价敏感：粗糙集：粒计算；多标记学习；信息嫡：正态分布 中图分类号：TP391 文献标志码：A 文章编号：1673-4785(2019)05-0929-10 中文引用格式：黄琴，钱文彬，王映龙，等.代价敏感数据的多标记特征选择算法.智能系统学报，2019,14(5)：929-938， 英文引用格式：HUANG Qin,QIAN Wenbin,.VANG Yinglong,et aL.Multi-.label feature selection algorithm for cost-sensitive data[J.CAAI transactions on intelligent systems,2019,14(5):929-938. Multi-label feature selection algorithm for cost-sensitive data HUANG Qin2,QIAN Wenbin,WANG Yinglong',WU Binglong? (1.School of Computer and Information Engineering.Jiangxi Agricultural University,Nanchang 330045,China;2.School of Soft- ware,Jiangxi Agricultural University,Nanchang 330045,China) Abstract:In multi-label learning,feature selection is an effective means to improve multi-label learning classification performance.Aiming at the problem that the existing multi-label feature selection methods have high computation com- plexity and do not consider the cost of data acquisition in real-world applications,this paper proposes a multi-label fea- ture selection algorithm for cost-sensitive data.The algorithm first analyzes the relevance between the feature and label based on information entropy,and redefines a criterion for feature significance by employing feature test cost,it then gives a reasonable threshold selection method on the basis of the standard deviation of feature significance and feature cost that obey normal distribution.At the same time,the algorithm derives the feature subsets with low total cost by re- moving redundant and irrelevant features according to a threshold.Finally,the effectiveness and feasibility of the pro- posed algorithm are verified by the comparison and analysis of the experimental results on a multi-labeled dataset. Keywords:feature selection;attribute reduction;cost-sensitive;rough sets;granular computing;multi-label learning;in- formation entropy;normal distribution 随着物联网及信息技术的发展，数据资源呈 能满足现实应用的需求，因此多标记学习的重要 海量特征。在数据量不断增大的同时，数据标注 性逐渐突显。在多标记学习中，每个样本在一个 结构的复杂度也在增加，传统的单标记学习已不 特征向量下，可能同时隶属于多个类别标记。近 年来，多标记学习问题已成为机器学习、数据挖 收稿日期：2018-07-26.网络出版日期：2019-05-27. 基金项目：国家自然科学基金项目(61502213.61662023)：江西 掘和模式识别等领域的研究热点之一。 省自然科学基金项日(20161BAB212047):江西省教 育厅科技项目(GJ180200). 波兰数学家Pawlak教授于1982年提出的粗 通信作者：钱文彬.E-mail:qianwenbinl027@l26.com 糙集理论是一种用于处理不精确、不完全和不相
DOI: 10.11992/tis.201807027 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190525.1801.002.html 代价敏感数据的多标记特征选择算法 黄琴1,2，钱文彬1,2，王映龙1 ，吴兵龙2 （1. 江西农业大学 计算机与信息工程学院，江西 南昌 330045; 2. 江西农业大学 软件学院，江西 南昌 330045） 摘 要：在多标记学习中，特征选择是提升多标记学习分类性能的有效手段。针对多标记特征选择算法计算复 杂度较大且未考虑到现实应用中数据的获取往往需要花费代价，本文提出了一种面向代价敏感数据的多标记 特征选择算法。该算法利用信息熵分析特征与标记之间的相关性，重新定义了一种基于测试代价的特征重要 度准则，并根据服从正态分布的特征重要度和特征代价的标准差，给出一种合理的阈值选择方法，同时通过阈 值剔除冗余和不相关特征，得到低总代价的特征子集。通过在多标记数据的实验对比和分析，表明该方法的有 效性和可行性。 关键词：特征选择；属性约简；代价敏感；粗糙集；粒计算；多标记学习；信息熵；正态分布 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2019)05−0929−10 中文引用格式：黄琴, 钱文彬, 王映龙, 等. 代价敏感数据的多标记特征选择算法 [J]. 智能系统学报, 2019, 14(5): 929–938. 英文引用格式：HUANG Qin, QIAN Wenbin, WANG Yinglong, et al. Multi-label feature selection algorithm for cost-sensitive data[J]. CAAI transactions on intelligent systems, 2019, 14(5): 929–938. Multi-label feature selection algorithm for cost-sensitive data HUANG Qin1,2 ，QIAN Wenbin1,2 ，WANG Yinglong1 ，WU Binglong2 (1. School of Computer and Information Engineering, Jiangxi Agricultural University, Nanchang 330045, China; 2. School of Software, Jiangxi Agricultural University, Nanchang 330045, China) Abstract: In multi-label learning, feature selection is an effective means to improve multi-label learning classification performance. Aiming at the problem that the existing multi-label feature selection methods have high computation complexity and do not consider the cost of data acquisition in real-world applications, this paper proposes a multi-label feature selection algorithm for cost-sensitive data. The algorithm first analyzes the relevance between the feature and label based on information entropy, and redefines a criterion for feature significance by employing feature test cost; it then gives a reasonable threshold selection method on the basis of the standard deviation of feature significance and feature cost that obey normal distribution. At the same time, the algorithm derives the feature subsets with low total cost by removing redundant and irrelevant features according to a threshold. Finally, the effectiveness and feasibility of the proposed algorithm are verified by the comparison and analysis of the experimental results on a multi-labeled dataset. Keywords: feature selection; attribute reduction; cost-sensitive; rough sets; granular computing; multi-label learning; information entropy; normal distribution 随着物联网及信息技术的发展，数据资源呈 海量特征。在数据量不断增大的同时，数据标注 结构的复杂度也在增加，传统的单标记学习已不 能满足现实应用的需求，因此多标记学习的重要 性逐渐突显。在多标记学习中，每个样本在一个 特征向量下，可能同时隶属于多个类别标记。近 年来，多标记学习问题已成为机器学习、数据挖 掘和模式识别等领域的研究热点之一[1-4]。 波兰数学家 Pawlak 教授于 1982 年提出的粗 糙集理论是一种用于处理不精确、不完全和不相 收稿日期：2018−07−26. 网络出版日期：2019−05−27. 基金项目：国家自然科学基金项目 (61502213，61662023)；江西 省自然科学基金项目 (20161BAB212047)；江西省教 育厅科技项目 (GJJ180200). 通信作者：钱文彬. E-mail: qianwenbin1027@126.com. 第 14 卷第 5 期 智 能 系 统 学 报 Vol.14 No.5 2019 年 9 月 CAAI Transactions on Intelligent Systems Sep. 2019
·930· 智能系统学报 第14卷 容知识的数学工具，近年来，该理论在机器学习 集，设计时间复杂度较低的特征选择算法，但其 和数据挖掘领域得到了广泛的应用6：”。属性约 没有给出和分析的信息熵阈值对特征子集的影 简，又称特征选择，是粗糙集理论的核心内容之 响。张振海等利用信息增益下的阈值选择设 一，其目的是在保持分类能力不变的条件下，删 计了一种多标记特征选择算法(MLFSIE)。综上 除不相关或冗余特征。与单标记学习一样，多标 所述，这些多标记特征选择算法并未考虑到特征 记学习也面临着“维数灾难”的挑战。高维数据不 的代价敏感问题。 仅影响算法的执行效率，也降低了分类器的分类 在许多实际应用领域中，获取和采集数据是 性能，而特征降维技术是解决维数灾难的有效方 需要花费代价的，因此从代价敏感的视角研究多 法。目前，针对单标记数据特征降维技术的研究 标记学习具有重要的意义。针对当前多标记特征 较为广泛，而针对多标记数据特征降维技术的研 选择算法的计算复杂度较大且未考虑特征代价的 究相对较少。因此，基于多标记学习特征选择的 研究具有重要的理论和应用意义。另外，在现实 问题，提出了一种面向代价敏感数据的多标记特 应用领域中，数据特征的获取往往需要花费一定 征选择算法。首先，该方法计算出特征与标记集 的代价，为此从代价敏感的视角研究多标记特征 合之间的信息增益，在此基础上重新定义了特征 选择问题显得尤为重要。 重要度的计算方法，并根据服从正态分布的特征 重要度与特征代价的标准差之间的差值，提出了 1相关工作 一种合理的阈值选择方法，从而实现对冗余或不 近年来，在多标记特征提取方面已经取得一 相关特征的剔除，同时能得到总代价较低的特征 些有意义的研究成果。如Sun等提出的多标记 子集。为了验证算法的有效性，利用Mulan平台 降维方法(LDA),其直接将单标记特征降维的方 上的真实多标记数据集进行实验比较和分析，通 法应用于多标记特征降维中，忽略了标记之间的 过实验结果进一步验证算法的有效性和可行性。 相关性。Zhang等采用核矩阵进行映射降维， 2基本知识 设计了一种最大化依赖度的多标记特征降维方 法(MDDM)。Yu等o提出了一种有监督的多标 2.1多标记学习 记潜在语义索引降维方法(MLSI)。多标记特征 在粒计算理论中，多标记数据可表示成一个 提取能够实现特征降维的效果，但由于其忽略了 多标记决策表MDT=(U,AUD,Vf),其中：U为样 标记之间的关联以及损失了原始特征的物理含 本集{x,2,·,x山，也称为论域；A为条件特征集 义，这对多标记学习问题的研究造成了较大的困难。 {a,a2,…,am:D为多标记决策特征{l1,2,…,lk,且 多标记特征选择通过设计特征度量准则从原 AnD=O;V为全特征集的值域，其中V=UVa, 始特征中别除冗余或不相关特征，得到一组相对 aeAUD,V.表示特征a的值域；f是U×(AUD)→V 最优的特征子集，从而可有效降低特征空间的维 的信息函数。 数，提升算法的分类性能。特征选择的结果能够 保持原始特征的物理含义，使得多标记学习的研 定义1给定多标记决策表MDT=(U,AU 究更容易理解。目前许多研究人员针对多标记特 D,Vf),对于Ya∈A,特征a的等价关系R。为 征选择开展研究，段洁等山重新定义了多标记邻 R=((xixj)EUxU,f(xi.a)=f(xj.a) 域粗糙集的下近似和依赖度的计算方法，在此基 定义2给定多标记决策表MDT=(U,AU 础上，设计了一种基于邻域粗糙集的特征选择算 D,Vf),对于l,∈D,标记l,的等价关系R,为 法(ARMLNRS)。王晨曦等从每个标记对样本 R.={,x)eU×U,fx,l)=fx,l)》 不同分组的角度出发，提出了基于信息粒化的多 2.2信息熵 标记特征选择算法(MFIG)。Lin等11在乐观、中 基于条件信息熵下的特征选择是研究者从信 立和悲观这3种不同的视角下，通过3种基于邻 息观视角对高维数据进行特征选择，该方法可有 域互信息准则进行特征选择。刘景华等通过 效地度量信息的不确定性程度。 引人局部子空间模型，构建了一种基于局部子空 定义3给定多标记决策表MDT=(U,AUD, 间的多标记特征选择算法(MFSLS)。上述算法的 V,f),对于任意特征子集B二A,根据特征子集B 计算复杂度相对较大。后来Lee等通过特征信 的等价关系Rs可得U/B=X,X2,…,Xg,则特征 息熵之差最大化和正向搜索的方法选择特征子 子集B的信息嫡为
容知识的数学工具[5] ，近年来，该理论在机器学习 和数据挖掘领域得到了广泛的应用[6-7]。属性约 简，又称特征选择，是粗糙集理论的核心内容之 一，其目的是在保持分类能力不变的条件下，删 除不相关或冗余特征。与单标记学习一样，多标 记学习也面临着“维数灾难”的挑战。高维数据不 仅影响算法的执行效率，也降低了分类器的分类 性能，而特征降维技术是解决维数灾难的有效方 法。目前，针对单标记数据特征降维技术的研究 较为广泛，而针对多标记数据特征降维技术的研 究相对较少。因此，基于多标记学习特征选择的 研究具有重要的理论和应用意义。另外，在现实 应用领域中，数据特征的获取往往需要花费一定 的代价，为此从代价敏感的视角研究多标记特征 选择问题显得尤为重要。 1 相关工作 近年来，在多标记特征提取方面已经取得一 些有意义的研究成果。如 Sun 等 [8] 提出的多标记 降维方法 (LDA)，其直接将单标记特征降维的方 法应用于多标记特征降维中，忽略了标记之间的 相关性。Zhang 等 [9] 采用核矩阵进行映射降维， 设计了一种最大化依赖度的多标记特征降维方 法 (MDDM)。Yu 等 [10] 提出了一种有监督的多标 记潜在语义索引降维方法 (MLSI)。多标记特征 提取能够实现特征降维的效果，但由于其忽略了 标记之间的关联以及损失了原始特征的物理含 义，这对多标记学习问题的研究造成了较大的困难。 多标记特征选择通过设计特征度量准则从原 始特征中剔除冗余或不相关特征，得到一组相对 最优的特征子集，从而可有效降低特征空间的维 数，提升算法的分类性能。特征选择的结果能够 保持原始特征的物理含义，使得多标记学习的研 究更容易理解。目前许多研究人员针对多标记特 征选择开展研究，段洁等[11] 重新定义了多标记邻 域粗糙集的下近似和依赖度的计算方法，在此基 础上，设计了一种基于邻域粗糙集的特征选择算 法 (ARMLNRS)。王晨曦等[12] 从每个标记对样本 不同分组的角度出发，提出了基于信息粒化的多 标记特征选择算法 (MFIG)。Lin 等 [13] 在乐观、中 立和悲观这 3 种不同的视角下，通过 3 种基于邻 域互信息准则进行特征选择。刘景华等[14] 通过 引入局部子空间模型，构建了一种基于局部子空 间的多标记特征选择算法 (MFSLS)。上述算法的 计算复杂度相对较大。后来 Lee 等 [15] 通过特征信 息熵之差最大化和正向搜索的方法选择特征子 集，设计时间复杂度较低的特征选择算法，但其 没有给出和分析的信息熵阈值对特征子集的影 响。张振海等[16] 利用信息增益下的阈值选择设 计了一种多标记特征选择算法 (MLFSIE)。综上 所述，这些多标记特征选择算法并未考虑到特征 的代价敏感问题。 在许多实际应用领域中，获取和采集数据是 需要花费代价的，因此从代价敏感的视角研究多 标记学习具有重要的意义。针对当前多标记特征 选择算法的计算复杂度较大且未考虑特征代价的 问题，提出了一种面向代价敏感数据的多标记特 征选择算法。首先，该方法计算出特征与标记集 合之间的信息增益，在此基础上重新定义了特征 重要度的计算方法，并根据服从正态分布的特征 重要度与特征代价的标准差之间的差值，提出了 一种合理的阈值选择方法，从而实现对冗余或不 相关特征的剔除，同时能得到总代价较低的特征 子集。为了验证算法的有效性，利用 Mulan 平台 上的真实多标记数据集进行实验比较和分析，通 过实验结果进一步验证算法的有效性和可行性。 2 基本知识 2.1 多标记学习 MDT = (U,A∪ D,V, f) U {x1, x2,··· , xn} A {a1,a2,··· ,am} D {l1,l2,··· ,lk} A∩ D = Ø V V = ∪Va a ∈ A∪ D Va a f U ×(A∪ D) → V 在粒计算理论中，多标记数据可表示成一个 多标记决策表 ，其中： 为样 本集 ，也称为论域； 为条件特征集 ； 为多标记决策特征 ，且 ； 为全特征集的值域，其中 ， ， 表示特征 的值域； 是 的信息函数。 MDT = (U,A∪ D,V, f) ∀a ∈ A a Ra 定 义 1 给定多标记决策表 ，对于 ，特征 的等价关系 为 Ra = {(xi , xj) ∈ U ×U, f(xi ,a) = f(xj ,a)} MDT = (U,A∪ D,V, f) ∀lt ∈ D lt Rlt 定 义 2 给定多标记决策表 ，对于 ，标记 的等价关系 为 Rlt = {(xi , xj) ∈ U ×U, f(xi ,lt) = f(xj ,lt)} 2.2 信息熵 基于条件信息熵下的特征选择是研究者从信 息观视角对高维数据进行特征选择，该方法可有 效地度量信息的不确定性程度。 MDT = (U,A∪ D, V, f) B ⊆ A B RB U/B = {X1,X2,··· ,Xq} B 定义 3 给定多标记决策表 ，对于任意特征子集 ，根据特征子集 的等价关系 可得 ，则特征 子集 的信息熵为 ·930· 智 能 系 统 学 报 第 14 卷
第5期 黄琴，等：代价敏感数据的多标记特征选择算法 ·931· H(B)=-∑pX))logp(X) NIG(Lla) 当信息嫡H(B)的值越大，说明特征子集B的 不确定性越大。 >[NIG(La)-u 定义4给定多标记决策表MDT=(U,AUD VfD,对于任意标记子集LD,根据标记子集L 在计算测试代价下的标记集合下特征重要度 的等价关系R可得U/L=Y,Y2,…,Y,则在特征 之前，需先将特征代价进行归一化处理： 子集B下标记子集L的条件熵为 Cost(a;)-min(Cost(a;)) Cost(a)= max(Cost(a;))-min(Cost(a;)) H(4B)=- 式中：max(Cost(a)表示特征的测试代价最大值； min(Cost(a)表示特征的测试代价最小值。 由定义4可知，当H(LB)=0时，说明标记子 定义7给定基于测试代价的多标记决策表 集L完全依赖于特征子集B,当H(LB)=H(L)时， CMDT=(U,AUD,Vf,c),其阈值6定义为 表明标记子集L独立于特征子集B。 定义5给定多标记决策表MDT=(U,AUD 1CSIG(Dla-Cost.o m Vf),对于任意特征子集BSA,则标记子集L在 特征子集B上的信息增益为 式中：Cost.σ表示所有特征的测试代价标准差，其 IG(LB)=H(L)-H(LB) 公式为 信息增益IG(B)值用于衡量特征子集B与 标记子集L的相关程度，IG(LB)值越大，说明其 Cost.o= m台 Cost(a)-Cost] 特征子集B与标记子集L的相关程度越大。 为了使得各个特征与标记之间的信息增益值 Cost.u= 在同一量纲下比较，需先对信息增益的值进行归 Cost(a) 式中：Costμ表示所有特征的测试代价均值。 一化处理： IG(LB) 3.2基于特征代价的信息熵模型可行性分析 NIG(LIB)= H(B)+H(L)） 性质1若特征a与标记1，相互独立，则特征 a与标记l,之间的信息增益取最小值；若标记4， 3代价敏感下的多标记学习 完全依赖于特征a,则特征a与标记l,的信息增 3.1基于特征代价的信息熵模型 益取最大值。 在机器学习和数据挖掘领域，代价敏感学习 证明由信息论理论结合定义4和定义5可 是十大最具有挑战性问题之一。因此，将特征 推导出，H(LB)≥0，且IG(LB)≤H(L)。当H(LB)=0 代价引入到多标记特征选择具有重要的意义。 时，IG(LB)=H(L),信息增益的值最大；当H(LB)= 定义6给定基于测试代价的多标记决策表 H(L)时，IG(B)=0,此时信息增益的值最小，同时 可知，信息增益IG(心B)值具有非负性。 CMDT=(U,AUD,Vf,c),其中c:A→R*UO!为测 试代价函数，对于任意特征Ya,aSA,标记集合 对于任意特征aEA,l,∈D,由定义5可知， D在特征a:上的特征重要度为 IGl,a)=Hl)-H(,a,由定义3和定义4可推导出， CSIG(Dla)=NIGS(Dla)'-Cost(a;)" IGUapX topx)p(Y lospYI 由定义5可得，标记集合D在特征a上的信 X),且届上述推导可知，当Ha)=H)时， 息增益为 IGl,a=0,信息增益的值最小，此时logp(X)= NIGS(Da)=∑NIGl,a) 人 之pYX)loY).表明标记L独立于特征a。 为了获取合理的阈值，使得信息增益的值服 同理，当Hlla)=0时，此时IG(a)=Hl),信息增 从正态分布： 益IGa)最大，即logp(X)-∑pYX)logp(YJX) NIGS(Dla)= NIGS(Dlla )-p 式中：μ表示特征与标记集合的信息增益均值；σ 最大，当p(YX)ogp(Y,X)=0时，表明标记1完 表示特征与标记集合的信息增益标准差，其公式 全依赖于特征a。 分别为 性质2标记集合D在特征a:上的特征重要
H(B) = − ∑q i=1 p(Xi)log p(Xi) 当信息熵 H(B) 的值越大，说明特征子集 B 的 不确定性越大。 MDT = (U,A∪ D, V, f) L ⊆ D L RL U/L = {Y1,Y2,··· ,Yp} B L 定义 4 给定多标记决策表 ，对于任意标记子集 ，根据标记子集 的等价关系 可得 ，则在特征 子集 下标记子集 的条件熵为 H(L|B) = − ∑q i=1 p(Xi) ∑p j=1 p(Yj |Xi)log p(Yj |Xi) H(L|B)=0 H(L|B)=H(L) 由定义 4 可知，当 时，说明标记子 集 L 完全依赖于特征子集 B，当 时， 表明标记子集 L 独立于特征子集 B。 MDT = (U,A∪ D, V, f) B ⊆ A L B 定义 5 给定多标记决策表 ，对于任意特征子集 ，则标记子集 在 特征子集 上的信息增益为 IG(L|B) = H(L)− H(L|B) IG(L|B) IG(L|B) 信息增益 值用于衡量特征子集 B 与 标记子集 L 的相关程度， 值越大，说明其 特征子集 B 与标记子集 L 的相关程度越大。 为了使得各个特征与标记之间的信息增益值 在同一量纲下比较，需先对信息增益的值进行归 一化处理： NIG(L|B) = IG(L|B) H(B)+ H(L) 3 代价敏感下的多标记学习 3.1 基于特征代价的信息熵模型 在机器学习和数据挖掘领域，代价敏感学习 是十大最具有挑战性问题之一[17]。因此，将特征 代价引入到多标记特征选择具有重要的意义。 CMDT = (U,A∪ D,V, f, c) c : A → R + ∪ {0} ∀ai ,aj ⊆ A D ai 定义 6 给定基于测试代价的多标记决策表 ，其中 为测 试代价函数，对于任意特征 ，标记集合 在特征 上的特征重要度为 CSIG(D|ai) = NIGS(D|ai) ∗ −Cost(ai) ∗ 由定义 5 可得，标记集合 D 在特征 ai 上的信 息增益为 NIGS(D|ai) = ∑k t=1 NIG(lt |ai) 为了获取合理的阈值，使得信息增益的值服 从正态分布： NIGS(D|ai) ∗ = NIGS(D||ai)−µ σ 式中： µ 表示特征与标记集合的信息增益均值；σ 表示特征与标记集合的信息增益标准差，其公式 分别为 µ= 1 k ∑k t=1 NIG(lt |ai) σ = vt 1 k ∑k t=1 [ NIG(lt |ai)−µ ]2 在计算测试代价下的标记集合下特征重要度 之前，需先将特征代价进行归一化处理： Cost(ai) ∗ = Cost(ai)−min(Cost(aj)) max(Cost(aj))−min(Cost(aj)) max(Cost(aj)) min(Cost(aj)) 式中： 表示特征的测试代价最大值； 表示特征的测试代价最小值。 CMDT = (U,A∪ D,V, f, c) δ 定义 7 给定基于测试代价的多标记决策表 ，其阈值 定义为 δ= 1 m ∑m i=1 |CSIG(D|ai)|−Cost.σ 式中： Cost.σ 表示所有特征的测试代价标准差，其 公式为 Cost.σ = vt 1 m ∑m i=1 [ Cost(ai)−Cost.µ]2 Cost.µ= 1 m ∑m i=1 Cost(ai) 式中： Cost.µ 表示所有特征的测试代价均值。 3.2 基于特征代价的信息熵模型可行性分析 a lt a lt lt a a lt 性质 1 若特征 与标记 相互独立，则特征 与标记 之间的信息增益取最小值；若标记 完全依赖于特征 ，则特征 与标记 的信息增 益取最大值。 H(L|B) ⩾ 0 IG(L|B) ⩽ H(L) H(L|B)=0 IG(L|B)=H(L) H(L|B)= H(L) IG(L|B)=0 IG(L|B) 证明 由信息论理论结合定义 4 和定义 5 可 推导出， ，且 。当 时， ，信息增益的值最大；当 时， ，此时信息增益的值最小，同时 可知，信息增益 值具有非负性。 a ∈ A lt ∈ D IG(lt |a) = H(lt)− H(lt |a) IG(lt |a) = ∑q i=1 p(Xi)log p(Xi)− ∑q i=1 p(Xi) ∑p j=1 p(Yj |Xi)log p(Yj | Xi) H(lt |a)=H(lt) IG(lt |a) = 0 log p(Xi) = ∑p j=1 p(Yj |Xi)log p(Yj |Xi) lt a H(lt |a) = 0 IG(lt |a)=H(lt) IG(lt |a) log p(Xi)− ∑p j=1 p(Yj |Xi) log p(Yj |Xi) ∑p j=1 p(Yj |Xi)| log p(YjXi)=0 lt a 对于任意特征 ， ，由定义 5 可知， ，由定义 3 和定义 4 可推导出， ，且由上述推导可知，当 时 ， ，信息增益的值最小，此时 ，表明标记 独立于特征 。 同理，当 时，此时 ，信息增 益 最大，即 最大，当 时，表明标记 完 全依赖于特征 。 性质 2 标记集合 D 在特征 ai 上的特征重要 第 5 期 黄琴，等：代价敏感数据的多标记特征选择算法 ·931·
·932· 智能系统学报 第14卷 度具有单调性，即标记D在特征a,上的信息增益 于每个标记的信息增益IG(U,la): 随单个标记在特征a:上的信息增益的增大而增 4)对于Ya∈A,执行操作： 大，且标记与特征之间的相关程度越大。 ①计算标记集合下每个特征的重要度 证明由性质1可得，若单个标记与特征a CSIG(Dla); 的相关性越大，则信息增益值越大，即IG,la)越 ②计算阈值6； 大。由定义6可知，NIGS(Dla)=∑NIG(lai),因此 5)对于Ha∈A,执行操作： 若CsIG(Dla)>6,则Red←RedU{al NIGL,a)越大，则NIGS(Da)的值越大，而特征代 6)输出特征子集Red,算法结束。 价的值Cost(a,)是固定的，此时可得CSIG(Dla)= 4.2时间复杂度分析 NIGS(Dla)'-Cost(a)'越大，即标记D在特征a:上 代价敏感数据的多标记特征选择算法中：步 的信息增益随单个标记在特征a上的信息增益 骤1)初始化一个变量存放特征选择后的特征子 的增大而增大。由性质1可知，标记与特征之间 集，其时间复杂度为O(1)；步骤2)中①需利用基 信息增益越大，则其相关程度也越大。由此可 数排序劉计算等价类，则整个条件特征集每个特 得，标记集合D在特征a:上的信息增益具有单调性。 征的信息嫡的时间复杂度为O4AIUD,步骤2)中 性质3阈值6具有单调性，即阈值随标记 ②计算每个特征的条件信息嫡的时间复杂度为 集合D在特征a:上的信息增益值的增大而增大。 O(U/AIUIIDD,可知步骤2)的时间复杂度最坏为 证明由性质2和定义7可知，特征代价的 O(AIIUIIDD;步骤3)分别计算每个标记与每个特 标准差Cost.o的值是固定的，CSIG(Da,)的值越 征之间的信息增益，其时间复杂度为O4 IUIDD: 大，则上CSIG(Dla--Costo越大，即阀值6的值 步骤4)中①计算标记集合下每个特征重要度，其 m 越大。 时间复杂度为O(4IUID,步骤4)中②计算阈值 的时间复杂度为O4IUD,因此步骤4)的时间复 4多标记特征选择算法 杂度最坏为O(AIlUIDD::步骤5)根据阈值进行特 征选择其时间复杂度为O4。因此本文算法的 4.1算法描述 时间复杂度为O4IUD)。 根据上述分析可知，在多标记学习算法中，一 为了分析本文算法在计算复杂度上的优越 个特征不仅与某一标记具有相关性，也可能同时 性，将本文算法分别与CSMLPA9算法和MLDM 与多个标记具有相关性，因此需要计算单个特征 算法进行比较。CSMLPA算法是基于文献2O]的正 与标记集合之间的相关性。在此基础上，从代价 区域模型设计的，并且考虑了测试代价的多标记 敏感学习的视角，提出了一种基于测试代价的特 特征选择算法，算法采用的是向前启发式搜索策 征重要度；然后根据服从正态分布的特征重要度 略，其计算复杂度主要消耗在计算加入单个特征到 以及特征代价的标准差设计出一种合理的阈值选 特征子集后的正域大小，时间复杂度为O(APIUIIDD。 择方法；最后，通过计算的阈值删除冗余或不相 MLDM算法是基于文献[21]的差别矩阵方法改 关的特征。 进的多标记特征选择算法，该算法主要耗时在对 本文提出的代价敏感数据的多标记特征选择 实例进行两两比较，其时间复杂度为O(LAIIUPIDD。 算法(CSMLFSIE)具体步骤如下： 本文算法与CSMLPA算法和MLDM算法相比，时 算法代价敏感数据的多标记特征选择算 间复杂度由非线性OCAFIUIID)和O(AIIUPIDD降 法(CSMLFSIE) 低至线性O(AIlUIIDD。由此可知，本文算法在计 输入多标记决策表<U,AUD,Vf>; 算复杂度上具有显著的优越性。 输出特征子集Red。 1)初始化Red←-o; 5实验结果与分析 2)对于Ha∈A,l,∈D,执行操作： 为了验证本文的CSMLFSIE算法的性能，从 ①计算在特征集A下每个特征的信息增益 Mulan数据集中选取了Emotions、Birds和Yeast H(a); 这3个真实数据集进行实验测试和分析。实验将 ②每个特征相对于每个标记的条件信息熵 算法CSMLFSIE与MLFSIE、CSMLPA、MLPA和 H(a); MLDM进行对比分析，其中，MLFSIE是一类基 3)对于Ya∈A,Yl,∈D分别计算每个特征相对 于信息熵的多标记特征选择算法，CSMLPA算法
ai ai 度具有单调性，即标记 D 在特征 上的信息增益 随单个标记在特征 上的信息增益的增大而增 大，且标记与特征之间的相关程度越大。 ai IG(lt |a) NIGS(D|a)= ∑k t=1 NIG(lt |ai) NIG(lt |ai) NIGS(D|a) Cost(ai) ∗ CSIG(D|ai) = NIGS(D|ai) ∗−Cost(ai) ∗ D ai ai D ai 证明 由性质 1 可得，若单个标记与特征 的相关性越大，则信息增益值越大，即 越 大。由定义 6 可知， ，因此 越大，则 的值越大，而特征代 价的值 是固定的，此时可得 越大，即标记 在特征 上 的信息增益随单个标记在特征 上的信息增益 的增大而增大。由性质 1 可知，标记与特征之间 信息增益越大，则其相关程度也越大。由此可 得，标记集合 在特征 上的信息增益具有单调性。 δ D ai 性质 3 阈值 具有单调性，即阈值随标记 集合 在特征 上的信息增益值的增大而增大。 Cost.σ CSIG(D|ai) 1 m ∑m i=1 |CSIG(D|ai)|−Cost.σ δ 证明 由性质 2 和定义 7 可知，特征代价的 标准差 的值是固定的， 的值越 大，则 越大，即阈值 的值 越大。 4 多标记特征选择算法 4.1 算法描述 根据上述分析可知，在多标记学习算法中，一 个特征不仅与某一标记具有相关性，也可能同时 与多个标记具有相关性，因此需要计算单个特征 与标记集合之间的相关性。在此基础上，从代价 敏感学习的视角，提出了一种基于测试代价的特 征重要度；然后根据服从正态分布的特征重要度 以及特征代价的标准差设计出一种合理的阈值选 择方法；最后，通过计算的阈值删除冗余或不相 关的特征。 本文提出的代价敏感数据的多标记特征选择 算法 (CSMLFSIE) 具体步骤如下： 算法 代价敏感数据的多标记特征选择算 法 (CSMLFSIE) 输入 多标记决策表 < U,A∪ D,V, f > ； 输出 特征子集 Red。 1) 初始化 Red ← ∅ ； ∀a ∈ A ∀l 2) 对于 ， t ∈ D ，执行操作： H(a) ①计算在特征集 A 下每个特征的信息增益 ； H(lt |a) ②每个特征相对于每个标记的条件信息熵 ； ∀a ∈ A ∀l 3) 对于 ， t ∈ D 分别计算每个特征相对 IG(lt 于每个标记的信息增益 |a) ； 4) 对于 ∀a ∈ A ，执行操作: CSIG(D|a) ①计算标记集合下每个特征的重要度 ； ②计算阈值 δ ； 5) 对于 ∀a ∈ A ，执行操作： 若 CSIG(D|a) > δ ，则 Red ← Red∪{a} 6) 输出特征子集 Red，算法结束。 4.2 时间复杂度分析 O(1) O(|A||U|) O(|U/A||U||D|) O(|A||U||D|) O(|A||U||D|) O(|A||U||D|) O(|A||U|) O(|A||U||D|) O(|A|) O(|A||U||D|) 代价敏感数据的多标记特征选择算法中：步 骤 1) 初始化一个变量存放特征选择后的特征子 集，其时间复杂度为 ；步骤 2) 中①需利用基 数排序[18] 计算等价类, 则整个条件特征集每个特 征的信息熵的时间复杂度为 ，步骤 2) 中 ②计算每个特征的条件信息熵的时间复杂度为 ，可知步骤 2) 的时间复杂度最坏为 ；步骤 3) 分别计算每个标记与每个特 征之间的信息增益，其时间复杂度为 ； 步骤 4) 中①计算标记集合下每个特征重要度，其 时间复杂度为 ，步骤 4) 中②计算阈值 的时间复杂度为 ，因此步骤 4) 的时间复 杂度最坏为 ；步骤 5) 根据阈值进行特 征选择其时间复杂度为 。因此本文算法的 时间复杂度为 。 O(|A| 2 |U||D|) O(|A||U| 2 |D|) O(|A| 2 |U||D|) O(|A||U| 2 |D|) O(|A||U||D|) 为了分析本文算法在计算复杂度上的优越 性，将本文算法分别与 CSMLPA[19] 算法和 MLDM 算法进行比较。CSMLPA 算法是基于文献 [20] 的正 区域模型设计的，并且考虑了测试代价的多标记 特征选择算法，算法采用的是向前启发式搜索策 略，其计算复杂度主要消耗在计算加入单个特征到 特征子集后的正域大小，时间复杂度为 。 MLDM 算法是基于文献 [21] 的差别矩阵方法改 进的多标记特征选择算法，该算法主要耗时在对 实例进行两两比较，其时间复杂度为 。 本文算法与 CSMLPA 算法和 MLDM算法相比，时 间复杂度由非线性 和 降 低至线性 。由此可知，本文算法在计 算复杂度上具有显著的优越性。 5 实验结果与分析 为了验证本文的 CSMLFSIE 算法的性能，从 Mulan 数据集中选取了 Emotions、Birds 和 Yeast 这 3 个真实数据集进行实验测试和分析。实验将 算法 CSMLFSIE 与 MLFSIE、CSMLPA、MLPA 和 MLDM 进行对比分析，其中，MLFSIE[16] 是一类基 于信息熵的多标记特征选择算法，CSMLPA 算法 ·932· 智 能 系 统 学 报 第 14 卷
第5期 黄琴，等：代价敏感数据的多标记特征选择算法 ·933 是基于文献[20]的正区域模型设计的考虑了测试 PC= Costg(D) 代价的多标记特征选择算法，MLPA是一种利用 Costa(D) 文献[20]中的正区域模型改进的多标记特征选择 2)平均分类精度(AP)是指在标记预测序列 算法，MLDM算法是基于文献[21]的差别矩阵方 中，排在相关标记之前的标记仍是相关标记的 法改进的多标记特征选择算法。最后通过IBLR- 比率： ML多标记分类器验证上述算法特征选择结果的 AP=1en)roM 分类性能。 m台四名 r() 实验过程中首先采用以上5种特征选择算法 3)汉明损失(L)是指预测出的标记与实际 分别对3个数据集进行特征降维，然后使用分类 标记的平均差异值： 算法对降维后的数据集采用10倍交叉验证法验 HL= YAZI 证算法的有效性。本实验的测试环境：CPU为 m台 M Inter(R)Core(TM)i5-4590s(3.0 GHz),8.0 GB, 其中4为Y、Z两个集合之间的对称差。 算法编程语言为Python和Java,使用的开发工具 4)覆盖率(Coverage)是指所有对象实际包含 分别是记事本和Eclipse4.7。 的所有标记所需最大的排序距离： 5.1数据集 1 Coverage=- 〉maxr(2)-1 实验中选取的3个真实数据集的相关信息如 e 表1所示，表中Yeast2四数据集描述的是酵母菌的 5)1错误率(OE)是指预测出的标记排序最靠 基因功能分类，Emotions2]数据集是来自于某音 前的标记不在实际对象中的比率： 乐学院的音频剪辑，Birds2数据集通过鸟叫声的 OE= 记录来区分鸟的种类。其中，Yeast数据集涉及的 了，6 (arg minr.》 m 是生物信息领域，而Emotions和Birds数据集涉 若argminr,()生Y:条件满足时，则6(arg minr.(☑尸 及的是音频信息领域。表1中对数据集中的实例 1,否则为0。 个数、特征数、标记数、标记基数和总代价进行了 6)排序损失(RL)是指预测出的标记中实际 描述，其中，标记基数用于统计训练集中实例的 不包含的标记比实际包含的标记排序高的比率： 平均标记个数，总代价是指利用正态分布函数为 数据集中的所有特征生成的代价总和。 RL 1 1 表1多标记数据集 m台阿× Table 1 Multi-label datasets I{0a,b):r(aa)>n(b)(亿a,s)∈Y×Y 平均分类精度越大说明分类性能越好，代价 数据集 实例数特征数标记数 标记基数 总代价 约简率、汉明损失、覆盖率、1错误率、排序损失 Yeast 2417 103 14 4.24 10033 越小说明分类性能越好。 Emotions 593 72 6 1.87 8013 5.3实验结果及比较 Birds 645 260 19 1.01 26390 5.3.1离散参数k的选择 由于本文所选择的3个多标记数据集的特征 5.2评价指标 值都包含连续型数据，但CSMLFSIE算法处理的 文中选用了代价约简率以及平均分类精度 是离散型特征变量，因此对于多标记数据集的处 (average precision,.AP)、汉明损失(Hamming loss, 理需要对特征值进行离散化处理。在实验过程中 HL)、覆盖率(Coverage)、1错误率(one error,OE)、 发现，k的步长取值为5时，降维后的特征子集的 排序损失(ranking loss,RL)这5种多标记评价性 分类性能差别较为明显。因此，本文将k以步长 能指标来评价算法性能。给定一组多标记对象集 5从5增加到50进行实验分析与比较。下面以 合(，Y),i=1,2,…,m,m表示对象大小，Y表示多 Emotions数据集为例，讨论离散化参数k的选择 标记分类器预测测试对象具有的标记集合，Y: 对多标记分类性能的影响，图1~5给出了Emo- 表示多标记分类器预测测试对象x具有的标记 tions数据集的5项评价指标随着离散化参数k的 集合，YSL,L={:j=1,2,…,9h,L表示所有标记 值增加的变化曲线。CSMLFSIE曲线、MLF- 集合，Z表示测试对象x实际的标记集合，了表 SIE曲线、CSMLPA曲线、MLPA曲线和 示Y:的补集，r()为标记A的排序。 MLDM曲线分别为这几种多标记特征选择算法 1)代价约简率是考虑特征代价的特征子集B 的性能。 的代价占全特征集A总代价的比率： 由图1~5可知，CSMLFSIE和MLFSIE算法
是基于文献 [20] 的正区域模型设计的考虑了测试 代价的多标记特征选择算法，MLPA 是一种利用 文献 [20] 中的正区域模型改进的多标记特征选择 算法，MLDM 算法是基于文献 [21] 的差别矩阵方 法改进的多标记特征选择算法。最后通过 IBLRML 多标记分类器验证上述算法特征选择结果的 分类性能。 实验过程中首先采用以上 5 种特征选择算法 分别对 3 个数据集进行特征降维，然后使用分类 算法对降维后的数据集采用 10 倍交叉验证法验 证算法的有效性。本实验的测试环境：CPU 为 Inter(R) Core(TM) i5-4590s (3.0 GHz)，内存 8.0 GB， 算法编程语言为 Python 和 Java，使用的开发工具 分别是记事本和 Eclipse 4.7。 5.1 数据集 实验中选取的 3 个真实数据集的相关信息如 表 1 所示，表中 Yeast[22] 数据集描述的是酵母菌的 基因功能分类，Emotions[23] 数据集是来自于某音 乐学院的音频剪辑，Birds[24] 数据集通过鸟叫声的 记录来区分鸟的种类。其中，Yeast 数据集涉及的 是生物信息领域，而 Emotions 和 Birds 数据集涉 及的是音频信息领域。表 1 中对数据集中的实例 个数、特征数、标记数、标记基数和总代价进行了 描述，其中，标记基数用于统计训练集中实例的 平均标记个数，总代价是指利用正态分布函数为 数据集中的所有特征生成的代价总和。 表 1 多标记数据集 Table 1 Multi-label datasets 数据集 实例数 特征数 标记数 标记基数 总代价 Yeast 2 417 103 14 4.24 10 033 Emotions 593 72 6 1.87 8 013 Birds 645 260 19 1.01 26 390 5.2 评价指标 (xi ,Yi) i = 1,2,··· ,m m Yi xi Yi xi Yi ⊆ L L= { λj : j = 1,2,··· ,q } L Zi xi Yi Yi ri(λ) λ 文中选用了代价约简率以及平均分类精度 (average precision，AP)、汉明损失 (Hamming loss， HL)、覆盖率 (Coverage)、1 错误率 (one error，OE)、 排序损失 (ranking loss，RL) 这 5 种多标记评价性 能指标来评价算法性能。给定一组多标记对象集 合 ， ， 表示对象大小， 表示多 标记分类器预测测试对象 具有的标记集合， 表示多标记分类器预测测试对象 具有的标记 集合， ， ， 表示所有标记 集合， 表示测试对象 实际的标记集合， 表 示 的补集， 为标记 的排序。 B A 1) 代价约简率是考虑特征代价的特征子集 的代价占全特征集 总代价的比率： PC = CostB(D) CostA (D) 2) 平均分类精度 (AP) 是指在标记预测序列 中，排在相关标记之前的标记仍是相关标记的 比率： AP= 1 m ∑m i=1 1 |Yi | ∑ λ∈Yi |{λ′ ∈ Yi : ri(λ′) ⩽ ri(λ)}| ri(λ) 3) 汉明损失 (HL) 是指预测出的标记与实际 标记的平均差异值： HL = 1 m ∑m i=1 |Yi∆Zi | M 其中 ∆ 为 Yi、Zi 两个集合之间的对称差。 4) 覆盖率 (Coverage) 是指所有对象实际包含 的所有标记所需最大的排序距离： Coverage= 1 m ∑m i=1 max λ∈Yi ri(λ)−1 5) 1 错误率 (OE) 是指预测出的标记排序最靠 前的标记不在实际对象中的比率： OE= 1 m ∑m i=1 δ(argmin λ∈Yi ri(λ)) arg λ∈Yi minri(λ) < Yi δ(argmin λ∈Yi 若 条件满足时，则 ri(λ))= 1，否则为 0。 6) 排序损失 (RL) 是指预测出的标记中实际 不包含的标记比实际包含的标记排序高的比率： RL = 1 m ∑m i=1 1 ∥Yi∥ Yi × |{(λa, λb) : ri(λa) > ri(λb) (λa, λb) ∈ Yi ×Yi}| 平均分类精度越大说明分类性能越好，代价 约简率、汉明损失、覆盖率、1 错误率、排序损失 越小说明分类性能越好。 5.3 实验结果及比较 5.3.1 离散参数 k 的选择 k k k k 由于本文所选择的 3 个多标记数据集的特征 值都包含连续型数据，但 CSMLFSIE 算法处理的 是离散型特征变量，因此对于多标记数据集的处 理需要对特征值进行离散化处理。在实验过程中 发现， 的步长取值为 5 时，降维后的特征子集的 分类性能差别较为明显。因此，本文将 以步长 5 从 5 增加到 50 进行实验分析与比较。下面以 Emotions 数据集为例，讨论离散化参数 的选择 对多标记分类性能的影响，图 1～5 给出了 Emotions 数据集的 5 项评价指标随着离散化参数 的 值增加的变化曲线。CSMLFSIE 曲线、 MLFS I E 曲线、 CSMLP A 曲线、 MLP A 曲 线 和 MLDM 曲线分别为这几种多标记特征选择算法 的性能。 由图 1～5 可知，CSMLFSIE 和 MLFSIE 算法 第 5 期 黄琴，等：代价敏感数据的多标记特征选择算法 ·933·