·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 卷