【人工智能基础】代价敏感数据的多标记特征选择算法

第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 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 随着物联网及信息技术的发展，数据资源呈 海量特征。在数据量不断增大的同时，数据标注 结构的复杂度也在增加，传统的单标记学习已不 能满足现实应用的需求，因此多标记学习的重要 性逐渐突显。在多标记学习中，每个样本在一个 特征向量下，可能同时隶属于多个类别标记。近 年来，多标记学习问题已成为机器学习、数据挖 掘和模式识别等领域的研究热点之一[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。由此可知，本文算法在计 输入多标记决策表; 算复杂度上具有显著的优越性。 输出特征子集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) 输入 多标记决策表 ； 输出 特征子集 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] 的差别矩阵方 法改进的多标记特征选择算法。最后通过 IBLR￾ML 多标记分类器验证上述算法特征选择结果的 分类性能。 实验过程中首先采用以上 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(λ) 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 给出了 Emo￾tions 数据集的 5 项评价指标随着离散化参数 的 值增加的变化曲线。CSMLFSIE 曲线、 MLF￾S I E 曲线、 CSMLP A 曲线、 MLP A 曲 线 和 MLDM 曲线分别为这几种多标记特征选择算法 的性能。 由图 1～5 可知，CSMLFSIE 和 MLFSIE 算法 第 5 期 黄琴，等：代价敏感数据的多标记特征选择算法 ·933·

·934· 智能系统学报 第14卷 的5项分类性能随离散化参数增加变化较为平 --CSMLFSIE--MLFSIE -CSMLPA --MLPA --MLDM 缓，CSMLPA、MLPA和MLDM算法的5项分类 2.4r 性能随离散化参数增加变化较为显著，其中，变 2.2 化较显著的是MLPA算法，5项分类性能随离散 2.0 化参数k取值的增加变化趋势较明显。针对 CSMLPA算法，当k的取值在[5,10]这个区间 时，HL、OE、Coverage和RL的值随离散化参数k .6 5101520253035404550 的取值增加而增大，同时，AP的值随离散化参数 离散化参数k k的取值增加而减小，5项多标记性能指标的值变 图3覆盖率随着离散化参数增加的变化曲线 化较为明显。当k的取值在[40,50]区间时，HL、 Fig.3 Variation of coverage with increase in the discretiz- ation parameter OE、Coverage、RL和AP这5项多标记分类性能 指标的值变化较小。针对MLDM算法，当离散化 -CSMLFSIE--MLFSIE -CSMLPA -MLPA -MLDM 参数值从5变化至20时，HL、OE、Coverage和 0.28 0.26 RL的值呈上升趋势，AP的值呈下降趋势，降维后 0.24 的特征子集的分类性能变化较显著。当离散化参 数取值从25变化至35时，HL、OE、Coverage、 0.18 L和AP的5项性能指标的值变化较为平缓，由 0.16 此可知，降维后的特征子集的分类性能在这个区 0.14 5 101520253035404550 间的稳定性较强。另外，通过实验结果可知，当 离散化参数k 离散化参数k的值为25时，CSMLFSIE和MLF- 图4排序损失随着离散化参数增加的变化曲线 SIE算法所取得的特征子集的分类性能最优； Fig.4 Variation of ranking loss with increase in the dis- cretization parameter CSMLPA和MLDM算法在离散化参数k为5时， 其降维后的特征子集分类性能最优：当k=35时， --CSMLFSIE-4-MLFSIE -*CSMLPA --MLPA --MLDM MLPA算法得到的特征子集的分类性能最优。 0.85 -CSMLFSIE--MLFSIE -CSMLPA 0.80-- --MLPA --MLDM 0.30 0.75 0.70 0.25 0.65 5 101520253035404550 离散化参数k 0.15 图5平均精度随着离散化参数增加的变化曲线 5 101520253035404550 Fig.5 Variation of average precision with increase in the 离散化参数k discretization parameter 图1汉明损失随着离散化参数增加的变化曲线 综上所述，与其他4种算法相比，随离散化参 Fig.1 Variation of Hamming loss with increase in the dis cretization parameter 数增加，CSMLFSIE算法的5项分类性能变化最 为平缓，即离散化参数的变化对CSMLFSIE算法 -CSMLFSIE--MLFSIE -CSMLPA --MLPA --MLDM 影响最小，因此CSMLFSIE算法的稳定性和健壮 0.45 性更优。 0.40 5.3.2实验对比 年0.35 实验过程中将训练数据集和测试数据集相结 0.30 合，采用10倍交叉验证法来验证算法的有效性， 0.25 0.20 实验结果采用评价指标的平均值和标准差表示。 5101520253035404550 离散化参数k 另外，由于Mulan数据集自身并不含测试代价，因 此本文采用正态分布函数为每个特征生成测试代 图21错误率随着离散化参数增加的变化曲线 Fig.2 Variation of one error rate with increase in the dis- 价，其中，正态分布函数的取值以100为期望，以 cretization parameter 30为标准差

k k k k k k k k = 35 的 5 项分类性能随离散化参数增加变化较为平 缓，CSMLPA、MLPA 和 MLDM 算法的 5 项分类 性能随离散化参数增加变化较为显著，其中，变 化较显著的是 MLPA 算法，5 项分类性能随离散 化参数 取值的增加变化趋势较明显。针对 CSMLPA 算法，当 的取值在 [5，10] 这个区间 时，HL、OE、Coverage 和 RL 的值随离散化参数 的取值增加而增大，同时，AP 的值随离散化参数 的取值增加而减小，5 项多标记性能指标的值变 化较为明显。当 的取值在 [40，50] 区间时，HL、 OE、Coverage、RL 和 AP 这 5 项多标记分类性能 指标的值变化较小。针对 MLDM 算法，当离散化 参数值从 5 变化至 20 时，HL、OE、Coverage 和 RL 的值呈上升趋势，AP 的值呈下降趋势，降维后 的特征子集的分类性能变化较显著。当离散化参 数取值从 25 变化至 35 时 ，HL、OE、Coverage、 RL 和 AP 的 5 项性能指标的值变化较为平缓，由 此可知，降维后的特征子集的分类性能在这个区 间的稳定性较强。另外，通过实验结果可知，当 离散化参数 的值为 25 时，CSMLFSIE 和 MLF￾SIE 算法所取得的特征子集的分类性能最优； CSMLPA 和 MLDM 算法在离散化参数 为 5 时， 其降维后的特征子集分类性能最优；当 时， MLPA 算法得到的特征子集的分类性能最优。 5 0.15 0.20 0.25 0.30 10 15 20 25 30 35 40 45 50 离散化参数k 汉明损失 MLPA MLFSIE MLDM CSMLFSIE CSMLPA 图 1 汉明损失随着离散化参数增加的变化曲线 Fig. 1 Variation of Hamming loss with increase in the dis￾cretization parameter 5 0.20 0.25 0.30 0.35 0.45 0.40 10 15 20 25 30 35 40 45 50 离散化参数k 1错误率 MLPA MLFSIE MLDM CSMLFSIE CSMLPA 图 2 1 错误率随着离散化参数增加的变化曲线 Fig. 2 Variation of one error rate with increase in the dis￾cretization parameter 5 1.6 1.8 2.0 2.2 2.4 10 15 20 25 30 35 40 45 50 离散化参数k 覆盖率 MLPA MLFSIE MLDM CSMLFSIE CSMLPA 图 3 覆盖率随着离散化参数增加的变化曲线 Fig. 3 Variation of coverage with increase in the discretiz￾ation parameter 5 0.14 0.16 0.18 0.20 0.24 0.22 0.28 0.26 10 15 20 25 30 35 40 45 50 离散化参数k 排序损失 MLPA MLFSIE MLDM CSMLFSIE CSMLPA 图 4 排序损失随着离散化参数增加的变化曲线 Fig. 4 Variation of ranking loss with increase in the dis￾cretization parameter 5 0.65 0.75 0.70 0.85 0.80 10 15 20 25 30 35 40 45 50 离散化参数k 平均精度 MLPA MLFSIE MLDM CSMLFSIE CSMLPA 图 5 平均精度随着离散化参数增加的变化曲线 Fig. 5 Variation of average precision with increase in the discretization parameter 综上所述，与其他 4 种算法相比，随离散化参 数增加，CSMLFSIE 算法的 5 项分类性能变化最 为平缓，即离散化参数的变化对 CSMLFSIE 算法 影响最小，因此 CSMLFSIE 算法的稳定性和健壮 性更优。 5.3.2 实验对比 实验过程中将训练数据集和测试数据集相结 合，采用 10 倍交叉验证法来验证算法的有效性， 实验结果采用评价指标的平均值和标准差表示。 另外，由于 Mulan 数据集自身并不含测试代价，因 此本文采用正态分布函数为每个特征生成测试代 价，其中，正态分布函数的取值以 100 为期望，以 30 为标准差。 ·934· 智 能 系 统 学 报 第 14 卷

第5期 黄琴，等：代价敏感数据的多标记特征选择算法 ·935· 表2~4中表示在正态分布函数下，用5种多 中给出的数据是AP取最优值时，所对应的PC、 标记特征选择算法分别对Yeast、Emotions和Birds HL、OE、Coverage、RL和k的值。另外，各项评价 这3个数据集进行特征降维，并用IBLR-ML 指标的最优值用黑体标注，」表示该项指标值越小 分类算法验证降维后的特征子集的分类性能，同 算法的分类性能越好，↑表示该项指标的值越大算 时，与原始数据集的分类性能进行对比。表2~4 法的分类性能越好。 表2 Yeast数据集的实验结果比较 Table 2 The comparisons of Yeast datasets 性能指标 原始数据集 CSMLFSIE算法MLFSIE算法 CSMLPA算法 MLPA算法 MLDM算法 PC(1/% 100 2.34 3.26 16.34 15.81 15.02 HL ( 0.1934±0.01180.193240.0121 0.1926±0.01150.2082±0.0092 0.2109±0.0102 0.2094±0.0086 OE() 0.2263±0.0316 0.2197±0.03380.2271±0.02750.2379±0.03440.2453±0.0306 0.2441±0.0356 Coverage() 6.1927±0.1747 6.1567±0.2028 6.1662±0.1822 6.4811±0.1564 6.5972±0.2097 6.5726±0.1803 RL() 0.1635±0.0117 0.1619±0.0122 0.1624±0.01170.1808±0.01340.1882±0.0148 0.1847±0.0147 AP(1) 0.7687±0.0200 0.7724±0.02150.7711±0.01940.7470±0.0221 0.7368±0.0212 0.7398±0.0229 45 45 J 表3 Emotions数据集的实验结果比较 Table 3 The comparisons of Emotions datasets 性能指标 原始数据集 CSMLFSIE算法 MLFSIE算法 CSMLPA算法 MLPA算法 MLDM算法 PC(/% 100 6.47 18.96 21.83 6.47 17.08 HL() 0.1883±0.02390.1864±0.0237 0.1853±0.01990.2024±0.02000.2218±0.02580.2249±0.0214 OE() 0.2581±0.0656 0.2582±0.0732 0.2514±0.05610.2784±0.0560 0.31530.0487 0.3020±0.0660 Coverage() 1.7087±0.1303 1.6905±0.1540 1.7292±0.14201.8031±0.1282 1.8908±0.1508 1.8674±0.1321 RL() 0.1496±0.0280 0.1488±0.0315 0.1519±0.02650.1683±0.02150.1914±0.0243 0.1826±0.0267 AP(1) 0.8126±0.0349 0.8135±0.0404 0.812740.03240.7950±0.0283 0.773440.0310 0.7803±0.0336 k 25 25 5 35 表4 Birds数据集的实验结果比较 Table 4 The comparisons of Birds datasets 性能指标 原始数据集 CSMLFSIE算法MLFSIE算法 CSMLPA算法 MLPA算法 MLDM算法 PC(1/% 100 11.65 46.54 21.83 2.77 2.95 HL() 0.0501±0.0065 0.051240.0075 0.0502±0.00770.0520±0.00750.0533±0.0084 0.0557±0.0087 OE() 0.7189±0.0446 0.7034±0.0437 0.70200.02880.7252±0.0349 0.7406±0.0301 0.7375±0.0403 Coverage(1)2.6227±0.5371 2.4450±0.5553 2.4856±0.56592.6571±0.5322 2.4642±0.4007 2.6112±0.5422 RL() 0.0915±0.0218 0.0841±0.0202 0.0848±0.0217 0.0920±0.0203 0.0883±0.0146 0.0930±0.0194 AP(↑) 0.5914±0.0458 0.6171±0.0577 0.6137±0.0502 0.5905±0.0564 0.5746±0.0426 0.5734±0.0472 45 35 5 30 25 由表2~4中的5种多标记分类性能评价指 行特征降维后，特征子集的分类性能优于原始数 标的结果可以看出，CSMLFSIE算法总体优于其 据集，其中，最为突出的是在PC这项指标上。另 他4种算法，较为明显的有Coverage、HL和AP 外，由表2~4可知，各个算法分类性能最优时， 这3项性能指标。同时，通过CSMLFSIE算法进 所对应的离散化参数k的取值也存在差异。由表2

表 2～4 中表示在正态分布函数下，用 5 种多 标记特征选择算法分别对 Yeast、Emotions 和 Birds 这 3 个数据集进行特征降维，并用 IBLR-ML 分类算法验证降维后的特征子集的分类性能，同 时，与原始数据集的分类性能进行对比。表 2～4 中给出的数据是 AP 取最优值时，所对应的 PC、 HL、OE、Coverage、RL 和 k 的值。另外，各项评价 指标的最优值用黑体标注，↓表示该项指标值越小 算法的分类性能越好，↑表示该项指标的值越大算 法的分类性能越好。 表 2 Yeast 数据集的实验结果比较 Table 2 The comparisons of Yeast datasets 性能指标 原始数据集 CSMLFSIE算法 MLFSIE算法 CSMLPA算法 MLPA算法 MLDM算法 PC(↓)/% 100 2.34 3.26 16.34 15.81 15.02 HL (↓) 0.193 4±0.011 8 0.193 2±0.012 1 0.192 6±0.011 5 0.208 2±0.009 2 0.210 9±0.010 2 0.209 4±0.008 6 OE (↓) 0.226 3±0.031 6 0.219 7±0.033 8 0.227 1±0.027 5 0.237 9±0.034 4 0.245 3±0.030 6 0.244 1±0.035 6 Coverage(↓) 6.192 7±0.174 7 6.156 7±0.202 8 6.166 2±0.182 2 6.481 1±0.156 4 6.597 2±0.209 7 6.572 6±0.180 3 RL (↓) 0.163 5±0.011 7 0.161 9±0.012 2 0.162 4±0.011 7 0.180 8±0.013 4 0.188 2±0.014 8 0.184 7±0.014 7 AP (↑) 0.768 7±0.020 0 0.772 4±0.021 5 0.771 1±0.019 4 0.747 0±0.022 1 0.736 8±0.021 2 0.739 8±0.022 9 k — 45 45 5 5 5 表 3 Emotions 数据集的实验结果比较 Table 3 The comparisons of Emotions datasets 性能指标 原始数据集 CSMLFSIE算法 MLFSIE算法 CSMLPA算法 MLPA算法 MLDM算法 PC(↓)/% 100 6.47 18.96 21.83 6.47 17.08 HL (↓) 0.188 3±0.023 9 0.186 4±0.023 7 0.185 3±0.019 9 0.202 4±0.020 0 0.221 8±0.025 8 0.224 9±0.021 4 OE (↓) 0.258 1±0.065 6 0.258 2±0.073 2 0.251 4±0.056 1 0.278 4±0.056 0 0.315 3±0.048 7 0.302 0±0.066 0 Coverage(↓) 1.708 7±0.130 3 1.690 5±0.154 0 1.729 2±0.142 0 1.803 1±0.128 2 1.890 8±0.150 8 1.867 4±0.132 1 RL (↓) 0.149 6±0.028 0 0.148 8±0.031 5 0.151 9±0.026 5 0.168 3±0.021 5 0.191 4±0.024 3 0.182 6±0.026 7 AP (↑) 0.812 6±0.034 9 0.813 5±0.040 4 0.812 7±0.032 4 0.795 0±0.028 3 0.773 4±0.031 0 0.780 3±0.033 6 k — 25 25 5 35 5 表 4 Birds 数据集的实验结果比较 Table 4 The comparisons of Birds datasets 性能指标 原始数据集 CSMLFSIE算法 MLFSIE算法 CSMLPA算法 MLPA算法 MLDM算法 PC(↓)/% 100 11.65 46.54 21.83 2.77 2.95 HL (↓) 0.050 1±0.006 5 0.051 2±0.007 5 0.050 2±0.007 7 0.052 0±0.007 5 0.053 3±0.008 4 0.055 7±0.008 7 OE (↓) 0.718 9±0.044 6 0.703 4±0.043 7 0.702 0±0.028 8 0.725 2±0.034 9 0.740 6±0.030 1 0.737 5±0.040 3 Coverage(↓) 2.622 7±0.537 1 2.445 0±0.555 3 2.485 6±0.565 9 2.657 1±0.532 2 2.464 2±0.400 7 2.611 2±0.542 2 RL (↓) 0.091 5±0.021 8 0.084 1±0.020 2 0.084 8±0.021 7 0.092 0±0.020 3 0.088 3±0.014 6 0.093 0±0.019 4 AP (↑) 0.591 4±0.045 8 0.617 1±0.057 7 0.613 7±0.050 2 0.590 5±0.056 4 0.574 6±0.042 6 0.573 4±0.047 2 k — 45 35 5 30 25 由表 2～4 中的 5 种多标记分类性能评价指 标的结果可以看出，CSMLFSIE 算法总体优于其 他 4 种算法，较为明显的有 Coverage、HL 和 AP 这 3 项性能指标。同时，通过 CSMLFSIE 算法进 行特征降维后，特征子集的分类性能优于原始数 据集，其中，最为突出的是在 PC 这项指标上。另 外，由表 2～4 可知，各个算法分类性能最优时， 所对应的离散化参数 k 的取值也存在差异。由表 2 第 5 期 黄琴，等：代价敏感数据的多标记特征选择算法 ·935·

·936· 智能系统学报 第14卷 中的Yeast数据集可知，由本文CSMLFSIE算法 较优。 降维后的特征子集的分类性能较优，其降维后的 另外，由表2~4可知，针对CSMLPA算法， 特征子集PC的值与MLFSIE、CSMLPA、 3个数据集的离散化参数k取值为5时，其降维后 MLPA和MLDM算法相比，分别减少了0.92%、 特征子集的分类性能最优；针对CSMLFSIE算法 14%、13.47%和12.68%；同时，AP分别提高了 进行离散化处理时，参数值为45时，Yeast数据集 0.13%、2.54%、2.54%和3.26%.且0E、C0ver- 和Bids数据集降维后的特征子集的分类效果较 age和RL值相对较优。另一方面，CSMLFSIE算 佳，而对于Emotions数据集来说，离散化参数取 法降维之后的特征子集与原始数据集相比，P℃的 25较优；针对MLFSIE算法和MLPA算法，在 值为2.34%，比原始数据集减少了97.66%，且其 3个数据集降维后的特征子集的分类性能最优 他5项分类性能评价指标的值更优，其中，AP的 时，所对应的离散化参数的取值也不同；针对 值提高了0.37%，HL、OE、Coverage、RL值分别降 MLDM算法，对于Yeast数据集和Emotions数据 低了0.02%、0.66%、3.6%和0.16%。 集，离散化参数取5时，降维后的特征子集的分类 针对Emotions数据集，由本文CSMLFSIE算 性能较优，在Birds数据集中，离散化参数取值为 法选择的特征子集的分类性能总体较优，根据 25较好。由此可知，各个算法的分类性能与离散 表3中各项性能指标的结果可知，除HL和OE性 化参数k的取值相关，降维后的特征子集影响着 能指标之外，其他3项多标记分类性能指标的值 分类器的分类性能。 最优，且总测试代价PC的值最小。CSMLFSIE算 综上所述，原始数据集中存在大量冗余和不 法与MLPA算法相比，PC的值同为6.47%，但 相关特征，且这些特征直接影响了分类器的分类 AP的值却提高了6.26%，同时，HL、OE、Cover- 性能，综合各项性能评价指标可知，CSMLFSIE算 age和RL的值都显著降低。由此可知，CSMLF- 法总体优于其他4种算法，达到了较好的特征降 SIE算法要优于MLPA算法。CSMLFSIE算法与 维的效果。 MLFSIE算法相比，PC的值减少了12.49%，另外， 6结束语 Coverage、RL和AP这3项性能指标相对更优，因 此CSMLFSIE算法总体优于MLFSIE算法。此 传统的基于多标记的特征选择算法往往忽略 外，CSMLFSIE算法与CSMLPA和MLDM算法相 了每个特征获取和采集所需花费的代价问题，为 比，PC的值分别减少了15.36%和10.61%，其 此，本文提出了一种代价敏感数据的多标记特征 HL、OE、Coverage、RL和AP这5项性能指标的 选择算法，该算法利用信息熵分析特征与标记之 值更优。 间的相关性，利用均匀分布函数和正态分布函数 从表4中的Birds数据集可以看出，CSMLF- 为特征生成测试代价，从代价敏感的研究视角· SIE算法选择后的特征子集的分类性能与Raw 构建一种新特征重要度准则。然后，根据服从正 Data相比，除HL这项性能指标之外，其他4项性 态分布的特征重要度和特征代价的标准差设置阈 能指标的值都更优，P℃的值也减少了88.65%，因 值，通过阈值别除冗余和不相关特征。通过对 此CSMLFSIE算法选择后的特征子集的分类性能 3个真实数据集实验结果的分析与比较，验证了 总体优于Raw Data。CSMLFSIE算法与MLF- 本文算法的有效性和高效性。但是，该算法并未 SIE算法相比，Coverage、RL和AP的值较优， 充分考虑标记之间的相关性以及误分类代价的问 PC的值减少了35.89%。CSMLFSIE算法与 题，这也是我们下一步的研究工作。 CSMLPA算法相比，PC的值减少了10.18%，AP 参考文献： 的值由59.05%提高至61.71%，HL、OE、Coverage 和RL的值分别降低了0.08%、2.18%、21.21%和 [1]ZHANG Minling,ZHOU Zhihua.A review on multi-label learning algorithms[J].IEEE transactions on knowledge 0.79%。CSMLFSIE算法与MLPA算法和MLDM and data engineering,2014,26(8):1819-1837. 算法相比，AP的值分别提高了4.25%、4.37%， [2]TSOUMAKAS G,KATAKIS I,VLAHAVAS I.Random- HL、OE、Coverage和RL的值有所下降，但PC的 Labelsets for multilabel classification[J].IEEE transac- 值分别增加了8.88%、8.7%。由此可知，由 tions on knowledge and data engineering,2011,23(7): CSMLFSIE算法选择的特征子集的分类性能总体 1079-1089

中的 Yeast 数据集可知，由本文 CSMLFSIE 算法 降维后的特征子集的分类性能较优，其降维后的 特征子 集 P C 的 值 与 MLFSIE 、 CSMLPA 、 MLPA 和 MLDM 算法相比，分别减少了 0.92%、 14%、13.47% 和 12.68%；同时，AP 分别提高了 0.13%、2.54%、2.54% 和 3.26%，且 OE、Cover￾age 和 RL 值相对较优。另一方面，CSMLFSIE 算 法降维之后的特征子集与原始数据集相比，PC 的 值为 2.34%，比原始数据集减少了 97.66%，且其 他 5 项分类性能评价指标的值更优，其中，AP 的 值提高了 0.37%，HL、OE、Coverage、RL 值分别降 低了 0.02%、0.66%、3.6% 和 0.16%。 针对 Emotions 数据集，由本文 CSMLFSIE 算 法选择的特征子集的分类性能总体较优，根据 表 3 中各项性能指标的结果可知，除 HL 和 OE 性 能指标之外，其他 3 项多标记分类性能指标的值 最优，且总测试代价 PC 的值最小。CSMLFSIE 算 法与 MLPA 算法相比，PC 的值同为 6.47%，但 AP 的值却提高了 6.26%，同时，HL、OE、Cover￾age 和 RL 的值都显著降低。由此可知，CSMLF￾SIE 算法要优于 MLPA 算法。CSMLFSIE 算法与 MLFSIE 算法相比，PC 的值减少了 12.49%，另外， Coverage、RL 和 AP 这 3 项性能指标相对更优，因 此 CSMLFSIE 算法总体优于 MLFSIE 算法。此 外，CSMLFSIE 算法与 CSMLPA 和 MLDM 算法相 比 ，PC 的值分别减少了 15.36% 和 10.61%，其 HL、OE、Coverage、RL 和 AP 这 5 项性能指标的 值更优。 从表 4 中的 Birds 数据集可以看出，CSMLF￾SIE 算法选择后的特征子集的分类性能与 Raw Data 相比，除 HL 这项性能指标之外，其他 4 项性 能指标的值都更优，PC 的值也减少了 88.65%，因 此 CSMLFSIE 算法选择后的特征子集的分类性能 总体优于 Raw Data。CSMLFSIE 算法与 MLF￾SIE 算法相比，Coverage、RL 和 AP 的值较优， PC 的值减少了 35.89%。CSMLFSIE 算法与 CSMLPA 算法相比，PC 的值减少了 10.18%，AP 的值由 59.05% 提高至 61.71%，HL、OE、Coverage 和 RL 的值分别降低了 0.08%、2.18%、21.21% 和 0.79%。CSMLFSIE 算法与 MLPA 算法和 MLDM 算法相比，AP 的值分别提高了 4.25%、4.37%， HL、OE、Coverage 和 RL 的值有所下降，但 PC 的 值分别增加 了 8.88% 、 8.7%。由此可知， 由 CSMLFSIE 算法选择的特征子集的分类性能总体 较优。 另外，由表 2～4 可知，针对 CSMLPA 算法， 3 个数据集的离散化参数 k 取值为 5 时，其降维后 特征子集的分类性能最优；针对 CSMLFSIE 算法 进行离散化处理时，参数值为 45 时，Yeast 数据集 和 Birds 数据集降维后的特征子集的分类效果较 佳，而对于 Emotions 数据集来说，离散化参数取 25 较优；针对 MLFSIE 算法和 MLPA 算法，在 3 个数据集降维后的特征子集的分类性能最优 时，所对应的离散化参数的取值也不同；针对 MLDM 算法，对于 Yeast 数据集和 Emotions 数据 集，离散化参数取 5 时，降维后的特征子集的分类 性能较优，在 Birds 数据集中，离散化参数取值为 25 较好。由此可知，各个算法的分类性能与离散 化参数 k 的取值相关，降维后的特征子集影响着 分类器的分类性能。 综上所述，原始数据集中存在大量冗余和不 相关特征，且这些特征直接影响了分类器的分类 性能，综合各项性能评价指标可知，CSMLFSIE 算 法总体优于其他 4 种算法，达到了较好的特征降 维的效果。 6 结束语 传统的基于多标记的特征选择算法往往忽略 了每个特征获取和采集所需花费的代价问题，为 此，本文提出了一种代价敏感数据的多标记特征 选择算法，该算法利用信息熵分析特征与标记之 间的相关性，利用均匀分布函数和正态分布函数 为特征生成测试代价，从代价敏感的研究视角， 构建一种新特征重要度准则。然后，根据服从正 态分布的特征重要度和特征代价的标准差设置阈 值，通过阈值剔除冗余和不相关特征。通过对 3 个真实数据集实验结果的分析与比较，验证了 本文算法的有效性和高效性。但是，该算法并未 充分考虑标记之间的相关性以及误分类代价的问 题，这也是我们下一步的研究工作。 参考文献： ZHANG Minling, ZHOU Zhihua. A review on multi-label learning algorithms[J]. IEEE transactions on knowledge and data engineering, 2014, 26(8): 1819–1837. [1] TSOUMAKAS G, KATAKIS I, VLAHAVAS I. Random - Labelsets for multilabel classification[J]. IEEE transac￾tions on knowledge and data engineering, 2011, 23(7): 1079–1089. [2] ·936· 智 能 系 统 学 报 第 14 卷

第5期 黄琴，等：代价敏感数据的多标记特征选择算法 ·937· [3]郑伟，王朝坤，刘璋，等.一种基于随机游走模型的多标 特征选择算法).模式识别与人工智能，2016,29(3)： 签分类算法.计算机学报，2010,33(8)：1418-1426. 240-251. ZHENG Wei,WANG Chaokun,LIU Zhang,et al.A multi- LIU Jinghua,LIN Menglei,WANG Chenxi,et al.Multi- label classification algorithm based on random walk mod- label feature selection algorithm based on local el[J].Chinese journal of computers,2010,33(8): subspace[J].Pattern recognition and artificial intelligence. 1418-1426. 2016,29(3:240-251. [4]李宇峰，黄圣君，周志华.一种基于正则化的半监督多标 [15]LEE J,LIM H,KIM D W.Approximating mutual inform- 记学习方法[J】.计算机研究与发展，2012,49(6)： ation for multi-label feature selection[J].Electronics let- 1272-1278 ters,2012,48(15):929-930. LI Yufeng,HUANG Shengjun,ZHOU Zhihua.Regular- [16]张振海，李士宁，李志刚，等.一类基于信息嫡的多标签 ized semi-supervised multi-label learning[J].Journal of 特征选择算法「J1.计算机研究与发展，2013,50(6)： computer research and development,2012,49(6): 1177-1184. 1272-1278 ZHANG Zhenhai,LI Shining,LI Zhigang,et al.Multi-la- [5]PAWLAK Z.Rough sets[J].International journal of com- bel feature selection algorithm based on information en- puter and information sciences,1982,11(5):341-356. tropy[J].Journal of computer research and development, [6]PAWLAK Z,SO-Winski R.Rough set approach to multi- 2013,50(6):1177-1184 attribute decision analysis[J].European journal of opera- [17]YANG Qiang,WU Xindong.10 challenging problems in tional research,1994,72(3):443-459. data mining research[J].International journal of informa- [7]刘清.Rough集及Rough推理[M.北京：科学出版社， tion technology decision making,2006,5(4):597-604. 2001 [18]徐章艳，刘作鹏，杨炳儒，等.一个复杂度为 [8]SUN Liang,JI Shuiwang,YE Jieping.Multi-label dimen- max(O(CIUD,O(CU1C)的快速属性约简算法).计 sionality reduction[M].Florida:CRC Press,2013:20-22. 算机学报，2006,29(3)：391-399 [9]ZHANG Yin,ZHOU Zhihua.Multi-label dimensionality XU Zhangyan,LIU Zuopeng,YANG Bingru,et al.A reduction via dependence maximization[C]//Proceedings of quick attribute reduction algorithm with complexity of the 23rd National Conference on Artificial Intelligence. max((IC]U),O(IC]JU/CD)[J].Chinese journal of com- Chicago,Illinois,2008:1503-1505. puters,.2006,29(3:391-399. [10]YU Kai,YU Shipeng,TRESP V.Multi-label informed [19]WU Binglong,QIAN Wenbin,HUANG Qin,et al.Cost- latent semantic indexing[C]//Proceedings of the 28th An- Sensitive multi-label feature selection algorithm based on nual International ACM SIGIR Conference on Research positive approximation[C]//Fuzzy Systems and Data Min- and Development in Information Retrieval.Salvador, ing IV-Proceedings of FSDM 2018.Bangkok,Thailand, Brazil,.2005:258-265. 2018:381-386. [11]段洁，胡清华，张灵均，等.基于邻域粗糙集的多标记分 [20]QIAN Yuhua,LIANG Jiye,PEDRYCZ W,et al.Positive 类特征选择算法.计算机研究与发展，2015,52(1)： approximation:an accelerator for attribute reduction in 56-65. rough set theory[J].Artificial intelligence,2010, DUAN Jie,HU Qinghua,ZHANG Lingjun,et al.Feature 1749/10):597-618 selection for multi-label classification based on neighbor- [21]WEI Wei,WU Xiaoying,LIANG Jiye,et al.Discernibil- hood rough sets[J].Journal of computer research and de- ity matrix based incremental attribute reduction for dy- velopment,.2015,52(1):56-65. namic data[J].Knowledge-based systems,2018,140: [12]王晨曦，林耀进，唐莉，等.基于信息粒化的多标记特征 142-157. 选择算法[J].模式识别与人工智能，2018,31(2)： [22]ELISSEEFF A,WESTON J.A kernel method for multi- 123-131. labelled classification[Cl//Proceedings of the 14th Inter- WANG Chenxi,LIN Yaojin,TANG Li,et al.Multi-label national Conference on Neural Information Processing feature selection based on information granulation[J].Pat- Systems:Natural and Synthetic.Vancouver,Canada. tern recognition and artificial intelligence,2018,31(2): 2001:681-687 123-131」 [23]TROHIDIS K,TSOUMAKAS G,KALLIRIS G,et al. [13]LIN Yaojin,HU Qinghua,LIU Jinghua,et al.Multi-label Multi-label classification of music into emotions[Cl//Pro- feature selection based on neighborhood mutual informa- ceedings of the 9th International Society for Music In- tion[J].Applied soft computing,2016,38:244-256. formation Retrieval Conference.Philadelphia,PA,2008: [14]刘景华，林梦雷，王晨曦，等.基于局部子空间的多标记 325-330

郑伟, 王朝坤, 刘璋, 等. 一种基于随机游走模型的多标 签分类算法 [J]. 计算机学报, 2010, 33(8): 1418–1426. ZHENG Wei, WANG Chaokun, LIU Zhang, et al. A multi￾label classification algorithm based on random walk mod￾el[J]. Chinese journal of computers, 2010, 33(8): 1418–1426. [3] 李宇峰, 黄圣君, 周志华. 一种基于正则化的半监督多标 记学习方法 [J]. 计算机研究与发展, 2012, 49(6): 1272–1278. LI Yufeng, HUANG Shengjun, ZHOU Zhihua. Regular￾ized semi- supervised multi-label learning[J]. Journal of computer research and development, 2012, 49(6): 1272–1278. [4] PAWLAK Z. Rough sets[J]. International journal of com￾puter and information sciences, 1982, 11(5): 341–356. [5] PAWLAK Z, SO-Winski R. Rough set approach to multi￾attribute decision analysis[J]. European journal of opera￾tional research, 1994, 72(3): 443–459. [6] 刘清. Rough 集及 Rough 推理 [M]. 北京: 科学出版社, 2001. [7] SUN Liang, JI Shuiwang, YE Jieping. Multi-label dimen￾sionality reduction[M]. Florida: CRC Press, 2013: 20–22. [8] ZHANG Yin, ZHOU Zhihua. Multi-label dimensionality reduction via dependence maximization[C]//Proceedings of the 23rd National Conference on Artificial Intelligence. Chicago, Illinois, 2008: 1503−1505. [9] YU Kai, YU Shipeng, TRESP V. Multi-label informed latent semantic indexing[C]//Proceedings of the 28th An￾nual International ACM SIGIR Conference on Research and Development in Information Retrieval. Salvador, Brazil, 2005: 258−265. [10] 段洁, 胡清华, 张灵均, 等. 基于邻域粗糙集的多标记分 类特征选择算法 [J]. 计算机研究与发展, 2015, 52(1): 56–65. DUAN Jie, HU Qinghua, ZHANG Lingjun, et al. Feature selection for multi-label classification based on neighbor￾hood rough sets[J]. Journal of computer research and de￾velopment, 2015, 52(1): 56–65. [11] 王晨曦, 林耀进, 唐莉, 等. 基于信息粒化的多标记特征 选择算法 [J]. 模式识别与人工智能, 2018, 31(2): 123–131. WANG Chenxi, LIN Yaojin, TANG Li, et al. Multi-label feature selection based on information granulation[J]. Pat￾tern recognition and artificial intelligence, 2018, 31(2): 123–131. [12] LIN Yaojin, HU Qinghua, LIU Jinghua, et al. Multi-label feature selection based on neighborhood mutual informa￾tion[J]. Applied soft computing, 2016, 38: 244–256. [13] [14] 刘景华, 林梦雷, 王晨曦, 等. 基于局部子空间的多标记 特征选择算法 [J]. 模式识别与人工智能, 2016, 29(3): 240–251. LIU Jinghua, LIN Menglei, WANG Chenxi, et al. Multi￾label feature selection algorithm based on local subspace[J]. Pattern recognition and artificial intelligence, 2016, 29(3): 240–251. LEE J, LIM H, KIM D W. Approximating mutual inform￾ation for multi-label feature selection[J]. Electronics let￾ters, 2012, 48(15): 929–930. [15] 张振海, 李士宁, 李志刚, 等. 一类基于信息熵的多标签 特征选择算法 [J]. 计算机研究与发展, 2013, 50(6): 1177–1184. ZHANG Zhenhai, LI Shining, LI Zhigang, et al. Multi-la￾bel feature selection algorithm based on information en￾tropy[J]. Journal of computer research and development, 2013, 50(6): 1177–1184. [16] YANG Qiang, WU Xindong. 10 challenging problems in data mining research[J]. International journal of informa￾tion technology & decision making, 2006, 5(4): 597–604. [17] 徐章艳 , 刘作鹏 , 杨炳儒 , 等 . 一个复杂度 为 max(O(|C||U|),O(|C| 2 |U/C|)) 的快速属性约简算法 [J]. 计 算机学报, 2006, 29(3): 391–399. XU Zhangyan, LIU Zuopeng, YANG Bingru, et al. A quick attribute reduction algorithm with complexity of max(O(|C||U|),O(|C| 2 |U/C|))[J]. Chinese journal of com￾puters, 2006, 29(3): 391–399. [18] WU Binglong, QIAN Wenbin, HUANG Qin, et al. Cost￾Sensitive multi-label feature selection algorithm based on positive approximation[C]//Fuzzy Systems and Data Min￾ing IV-Proceedings of FSDM 2018. Bangkok, Thailand, 2018: 381−386. [19] QIAN Yuhua, LIANG Jiye, PEDRYCZ W, et al. Positive approximation: an accelerator for attribute reduction in rough set theory[J]. Artificial intelligence, 2010, 174(9/10): 597–618. [20] WEI Wei, WU Xiaoying, LIANG Jiye, et al. Discernibil￾ity matrix based incremental attribute reduction for dy￾namic data[J]. Knowledge-based systems, 2018, 140: 142–157. [21] ELISSEEFF A, WESTON J. A kernel method for multi￾labelled classification[C]//Proceedings of the 14th Inter￾national Conference on Neural Information Processing Systems: Natural and Synthetic. Vancouver, Canada, 2001: 681−687. [22] TROHIDIS K, TSOUMAKAS G, KALLIRIS G, et al. Multi-label classification of music into emotions[C]//Pro￾ceedings of the 9th International Society for Music In￾formation Retrieval Conference. Philadelphia, PA, 2008: 325−330. [23] 第 5 期 黄琴，等：代价敏感数据的多标记特征选择算法 ·937·

·938· 智能系统学报 第14卷 [24]BRIGGS F,HUANG Yonghong,RAICH R,et al.The 9th 钱文彬，男，1984年生，副教授 annual MLSP competition:new methods for acoustic 博土，主要研究方向为粒计算、知识发 现与机器学习。主持完成国家青年科 classification of multiple simultaneous bird species in a 学基金项目和江西省青年科学基金项 noisy environment[C]//Proceedings of 2013 IEEE Interna- 目各1项。发表学术论文20余篇。 tional Workshop on Machine Learning for Signal Pro- cessing.Southampton,UK,2013:22-25. 作者简介： 王映龙，男，1970年生，教授，博 黄琴，女，1993年生，硕士研究 士，主要研究方向为知识发现与数据 生，主要研究方向为粒计算与机器学 挖掘。参与国家自然科学基金项目 习。取得计算机软件著作权2项，发 2项，先后主持江西省自然科学基金 表学术论文3篇。 项目3项。发表学术论文20余篇。 CCAI2019中国人工智能大会 中国人工智能大会由中国人工智能学会创办于2015年，每年举办一届。该会是我国最早发起举办的人 工智能大会，目前已经成为我国人工智能领域规格最高、规模最大、影响力最强的会议之一。 2019年中国人工智能大会(CCAI2019)由中国人工智能学会、青岛市政府共同主办，胶州市政府、马上 科普承办，旨在搭建人工智能前沿技术探索桥梁、打造高端交流平台和引领科技创新发展。 CCAI2019将延续过去四届的强大阵容，设置1个主论坛、1个大会论坛和6个分论坛。该大会将邀请 全球人工智能领域顶尖科学家和企业家，围绕当前热点话题、核心技术以及国家和社会关注的热点问题进 行重点探讨，并着重关注如何认识我国当前人工智能发展态势。 会议官网：http://ccai.cn/#o5 会议日期：2019年9月21一22日 会议地点：中国青岛胶州方圆体育中心

BRIGGS F, HUANG Yonghong, RAICH R, et al. The 9th annual MLSP competition: new methods for acoustic classification of multiple simultaneous bird species in a noisy environment[C]//Proceedings of 2013 IEEE Interna￾tional Workshop on Machine Learning for Signal Pro￾cessing. Southampton, UK, 2013: 22−25. [24] 作者简介： 黄琴，女，1993 年生，硕士研究 生，主要研究方向为粒计算与机器学 习。取得计算机软件著作权 2 项，发 表学术论文 3 篇。 钱文彬，男，1984 年生，副教授， 博士，主要研究方向为粒计算、知识发 现与机器学习。主持完成国家青年科 学基金项目和江西省青年科学基金项 目各 1 项。发表学术论文 20 余篇。 王映龙，男，1970 年生，教授，博 士，主要研究方向为知识发现与数据 挖掘。参与国家自然科学基金项目 2 项，先后主持江西省自然科学基金 项目 3 项。发表学术论文 20 余篇。 CCAI2019 中国人工智能大会 中国人工智能大会由中国人工智能学会创办于 2015 年，每年举办一届。该会是我国最早发起举办的人 工智能大会，目前已经成为我国人工智能领域规格最高、规模最大、影响力最强的会议之一。 2019 年中国人工智能大会（CCAI 2019）由中国人工智能学会、青岛市政府共同主办，胶州市政府、马上 科普承办，旨在搭建人工智能前沿技术探索桥梁、打造高端交流平台和引领科技创新发展。 CCAI 2019 将延续过去四届的强大阵容，设置 1 个主论坛、1 个大会论坛和 6 个分论坛。该大会将邀请 全球人工智能领域顶尖科学家和企业家，围绕当前热点话题、核心技术以及国家和社会关注的热点问题进 行重点探讨，并着重关注如何认识我国当前人工智能发展态势。 会议官网：http://ccai.cn/#05 会议日期：2019 年 9 月 21—22 日 会议地点：中国青岛胶州方圆体育中心 ·938· 智 能 系 统 学 报 第 14 卷