第2期 高琪，等：基于模糊不一致对的多标记属性约简 ·375· 低维特征空间的过程。 设B是一个属性子集，相对于决策属性D,样 常见的特征提取方法包括线性判别分析 本x和y在B下的满意度(satisfiability)定义为 (LDA)I、特征抽取方法MDDM)和多标记潜在 minfug(x,y))max(1-ug.(x,y)), 语义搜索(MLSI)。特征提取方法虽然能够提高 SATRD(M'(x,y))= N(uR,(x,y)=1: 多标记分类器的分类性能，但该方法形成的新特 0,N(ugp(x,y))=0 征空间失去了原特征的语义。不同于特征提取的 总满意度(total satisfiability)定义为 方法，特征选择方法是根据一定的评价准则，从 原始的特征空间中选择一个（组）最优特征子集 sTMB。kE SAT(M'(x,y)) 的过程。常见的评价准则有依赖性度量、信息 SATD(M'(x.y)) 度量、距离度量以等。例如，Spolaor等基 性质113引 给定一个决策表<U,A,D>, 于二元关系方法和标签幂集法，提出了基于多标 BCA是一个条件属性子集。若B满足以下条件： 记的特征选择方法(RF-BR、RF-LP、IG-BR、IG- 1)SAT(B)=SAT(A)=1: LP):Li等利用最大化信息增益来度量特征和标 2)YB'C B,SAT(B)<SAT(B). 记的相关性，提出基于信息增益的多标记特征选 则B是决策表<U,A,D>的一个模糊粗糙 择算法IGML)等。 约简。 在模糊粗糙集模型中，使用模糊相似关系代 为表述方便，在下文中，对a∈A,记 替经典粗糙集模型中的等价关系，进而衡量两个 sima(x,y)=ug(x.y) 对象之间的不可区分性。在模糊粗糙集理论中， disa(x,y）=N(uR(x,y) 模糊区分矩阵概念被提出B,Chen等提出了 定义21给定一个决策表<U,A,D>,模糊 ~种基于区分矩阵中的最小元素集的属性约简方 区分矩阵中每一项对应于样本对(xy),则该样本 法，提高了属性约简的计算效率。Dai等6提出 对对应的最大模糊区分属性定义为 种基于模糊粗糙集合的最大区分对的属性约简 [aldis(x,y)=max dis(y),aA) 算法。 MDAAD(x,y)= 4e(x,y)=0 在多标记学习中，每个样本可能同时隶属于 Φ， 4R(c,y)=1 多个标记，标记之间也可能存在着某种关系，因 对于Va∈A,其对应的最大模糊区分对定义为 而本文针对多标记学习问题，利用KL散度度量 MDP.D(Uの={x,y)la E MDAD(x,y),(x,y)∈U×U) 标记间的关系，并定义标记权重。考虑权重情 由于MDA D(x,y)的对称性，则上式可定 况，定义模糊不一致对，提出一种基于模糊不一 义为 致对的多标记属性约简方法(MLAR-FL),并通过 MDP。D(U)={(,xla∈MDAAD(x,x, 实验验证了本文算法的有效性。 Yx,x∈U,i<j 性质261给定一个决策表<U,A,D>,若 1基本概念 B为一个属性子集，则有 MDP D(U)=U MDP D(U) 给定一个决策表<U,A,D>,其中U={x1, VaER x2,“,xm}为非空有限样本集合，称其为论域， 性质31%给定一个决策表<U,A,D>,若属 A={a,a2,…,ap}为非空有限的条件属性集，D为 性子集B满足： 一个决策属性。设B为一个条件属性子集，R。为 1)MDP D(U)=MDP D(U月 由属性a所决定的U上的模糊二元关系，Ro为由 2)VB'C B,MDP D(U)C MDP D(U). 决策属性D决定的U上的二元关系，4(xy为由 则B为决策表的一个约简。 R。导出的U上的某个二元关系，称为样本x,y在 2多标记属性约简方法 属性a下的模糊不可区分度。N(u(xy)Fl-R(xy) 表示样本xy在属性下的模糊可区分度。 给定一个多标记决策表S=<U,A,L>,其中 定义11给定一个决策表<U,A,D>,决定 U={x,x2,,xn}为样本集，A={a,a,,a}为条 一个模糊区分矩阵M,其中的项定义为 件属性集，L={l,12,,1}为标记集。若样本x拥 M'(x,y）={aMa.ela∈A,Yx,y∈U 有标记1，则(x)=1,否则x=0。 值得注意的是，上述区分矩阵每个项中的元 定义3 181 KL散度(Kullback-Leibler diver- 是一个带有模糊可区分度值的条件属性集。 gence)。设p和q是概率空间2下的两个概率分布。低维特征空间的过程。 常见的特征提取方法包括线性判别分 析 (LDA)[3] 、特征抽取方法 (MDDM)[4] 和多标记潜在 语义搜索 (MLSI)[5]。特征提取方法虽然能够提高 多标记分类器的分类性能，但该方法形成的新特 征空间失去了原特征的语义。不同于特征提取的 方法，特征选择方法是根据一定的评价准则，从 原始的特征空间中选择一个 (组) 最优特征子集 的过程。常见的评价准则有依赖性度量[6] 、信息 度量[7-8] 、距离度量[9-12] 等。例如，Spolaôr 等 [12] 基 于二元关系方法和标签幂集法，提出了基于多标 记的特征选择方法 (RF-BR、RF-LP、IG-BR、IG￾LP)；Li 等 [8] 利用最大化信息增益来度量特征和标 记的相关性，提出基于信息增益的多标记特征选 择算法 (IGML) 等。 在模糊粗糙集模型中，使用模糊相似关系代 替经典粗糙集模型中的等价关系，进而衡量两个 对象之间的不可区分性。在模糊粗糙集理论中， 模糊区分矩阵概念被提出[13-14] ，Chen 等 [15] 提出了 一种基于区分矩阵中的最小元素集的属性约简方 法，提高了属性约简的计算效率。Dai 等 [16] 提出 一种基于模糊粗糙集合的最大区分对的属性约简 算法。 在多标记学习中，每个样本可能同时隶属于 多个标记，标记之间也可能存在着某种关系，因 而本文针对多标记学习问题，利用 KL 散度度量 标记间的关系，并定义标记权重。考虑权重情 况，定义模糊不一致对，提出一种基于模糊不一 致对的多标记属性约简方法 (MLAR-FL),并通过 实验验证了本文算法的有效性。 1 基本概念 给定一个决策表<U， A， D>，其中 U={x 1， x 2， ···， x n }为非空有限样本集合，称其为论域， A={a1，a2，···，ap}为非空有限的条件属性集，D 为 一个决策属性。设 B 为一个条件属性子集，Ra 为 由属性 a 所决定的 U 上的模糊二元关系，RD 为由 决策属性 D 决定的 U 上的二元关系，uRa(x,y) 为由 Ra 导出的 U 上的某个二元关系，称为样本 x,y 在 属性 a 下的模糊不可区分度。N(uRa(x,y))=1−uRa(x,y) 表示样本 x,y 在属性下的模糊可区分度。 定义 1 [13] 给定一个决策表<U，A，D>，决定 一个模糊区分矩阵 M′，其中的项定义为 M′ (x, y) = {aN(uRa (x,y))|a ∈ A,∀x, y ∈ U} 值得注意的是，上述区分矩阵每个项中的元 是一个带有模糊可区分度值的条件属性集。 设 B 是一个属性子集，相对于决策属性 D，样 本 x 和 y 在 B 下的满意度 (satisfiability) 定义为[17] SATB,D(M′ (x, y)) =    min a∈B {uRa (x, y)} = max a∈B {1−uRa (x, y)}, N(uRD (x, y)) = 1; 0, N(uRD (x, y)) = 0 总满意度 (total satisfiability) 定义为 SAT(B) = ∑ x,y∈U,x,y SATB,D(M′ (x, y)) ∑ x,y∈U,x,y SATA,D(M′ (x, y)) ⊂ 性 质 1 [ 1 3 ] 给定一个决策表 <U， A， D> ， B A 是一个条件属性子集。若 B 满足以下条件： 1) SAT(B) = SAT(A) = 1; ∀B ′ ⊂ B,SAT(B ′ 2) ) < SAT(B)。 则 B 是决策表<U，A， D>的一个模糊粗糙 约简。 为表述方便，在下文中，对 a∈A，记 sima(x, y) = uRa (x, y) disa(x, y) = N(uRa (x, y)) 定义 2 [15] 给定一个决策表<U，A，D>，模糊 区分矩阵中每一项对应于样本对 (x,y)，则该样本 对对应的最大模糊区分属性定义为 MDAAD(x, y) =    {a|disA(x, y) = max a∈A disa(x, y),a ∈ A} uRD (x, y) = 0 Φ, uRD (x, y) = 1 对于∀a∈A,其对应的最大模糊区分对定义为 MDPaD(U) = {(x, y)|a ∈ MDAAD(x, y),(x, y) ∈ U ×U} 由于 MDAA D(x,y) 的对称性，则上式可定 义为 MDP′ aD(U) = {(xi , xj)|a ∈ MDAAD(xi , xj), ∀xi , xj ∈ U,i < j} 性质 2 [ 1 6 ] 给定一个决策表<U，A，D>，若 B 为一个属性子集，则有 MDP′ BD(U) = ∪ ∀a∈B MDP′ aD(U) 性质 3 [16] 给定一个决策表<U，A，D>，若属 性子集 B 满足： MDP′ BD(U) = MDP′ 1) AD(U); ∀B ′ ⊂ B,MDP′ B′D(U) ⊂ MDP′ 2) BD(U)。 则 B 为决策表的一个约简。 2 多标记属性约简方法 给定一个多标记决策表 S=<U，A，L>，其中 U={x1，x2，···，xn}为样本集，A={a1，a2，···，ad}为条 件属性集，L={l1，l2，···，lq}为标记集。若样本 x 拥 有标记 li，则 li (x)=1，否则 li (x)=0。 Ω 定义 3 [18] KL 散度 (Kullback-Leibler diver￾gence)。设 p 和 q 是概率空间 下的两个概率分布。 第 2 期 高琪，等：基于模糊不一致对的多标记属性约简 ·375·