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