第6期 张晓鹤，等：粒协调决策形式背景的属性约简与规则融合 ·1139· 即更易获取决策规则。越来越多的学者开始深入 定义49设V,1≤m是非空有限集.记 研究决策形式背景的属性约简与规则提取问题。 P={E=(E1,E2,…,Em):E≤Vl≤m)S 2009年，Wu研究了保持概念格的粒结构不 P(E1)XP(E2)×…X(Em) 变的属性约简与规则提取，并给出具体算法。 称P为集合向量空间。对于P中的两个集合向 Li等7)提出了一种新的决策形式背景知识约简 量E=(E,…,Em),S=(S,…,Sm,如果l≤m,均有 框架，给出约简算法，且在决策形式背景研究了 E≤S,则记E≤S,且(P,≤)为偏序集。 保持决策规则不变的属性约简。Li等研究了 定义511设(P,≤)为偏序集，称D:P→ 基于同余关系的不协调决策形式背景的属性约 [0,1]为集值向量包含度，满足下列条件： 简。Li等川提出了基于最大规则的决策形式背 1)0≤DS/E)≤1： 景中的新型属性约简。Chen2l1提出了一种大数 2)E≤S时，D(S/E)=1: 据模型下的快速属性约简模型，并结合实例分析 3)E≤S≤G时，D(E/G)≤D(E/S)e 其算法复杂度。Yang基于蕴涵映射对实数集 2基于等价关系的粒协调决策形式 决策形式背景中的属性约简和规则提取问题进行 背景的属性约简 研究。Q1从多角度讨论了两类三支概念格与 传统概念格之间的联系，并给出了在经典概念格 以往对决策形式背景进行讨论时通常会分别 基础上构造三支概念格的算法。Zhang等Io利 构造条件概念格与决策概念格，利用两者的序关 用概念格提出了一种基于案例的层次化分类器。 系来定义形式背景的协调性。本节利用等价关系 Zhang等叼研究了模糊决策格值信息系统上的近 对对象集进行划分，从而得到对应的决策类，可以 似约简与规则提取。张89叙述了信息系统上的 在保持对象的决策不变的前提下删除冗余属性。 知识发现与知识约简，提出了协调近似表示空间 设F=(U,A,I,D,G)为一个决策形式背景，A 上的规则融合方法。 为条件属性集，D为决策属性集，并且AnD=O, 目前在概念格领域已取得诸多成果，但仍存 IsU×A。定义Ro={(x,y∈U×U:dx)=dy)d∈ 在众多问题有待解决。比如基于等价关系的粒协 D》,则由上述等价关系可产生U上的一个划分： U/Rp ([xlp xEU=(D..D2.....D,] 调决策形式背景的属性约简问题，利用确定性规 其中 则获取全部规则的具体途径，本文将进一步讨论 [xlD=yEU:(x,y)E Rp] 这些问题。 如果x∈U,均满足x4S[xD,则称决策形式 1预备知识 背景F是粒协调的。 定义6设F=(U,A,1,D,G)为粒协调决策形 定义1设三元组F=(U,A,)是形式背景 式背景，对BSA,如果Yx∈U,都有xSxD,则 U={x1,,…,xn,A={a1,2,…,amh,I二UXA。如果 称B是F的一个粒协调集。进一步，如果不存在 (x,ad)∈L,则称x具有属性a。用P(U)表示U的幂集， CcB,使得Hx∈U都有xCC[xo,则B是F的粒 P(A)表示A的幂集。YX∈P(U,B∈P(A),定义： 约简。 X={a∈A:x∈X,(x,a)∈ (1) B°={x∈U:YaeB,(x,aeI (2) 注：1)对粒协调决策形式背景F来说，必存 在粒约简。如用{B:i≤)表示F所有的粒约简， 定义2对于形式背景F=(U,A,),若二元 组(X,B)EP(U)×P(A)满足X=B且B=X,则 则B=∩B:为F的核心，B中的元素称为核心元 (X,B)称为形式概念或概念。其中X是概念(X,B) 素或绝对必要属性。 的外延，B是概念(X,B)的内涵。 2)对于x,y∈Dj,Yd∈D有d(x)=dy),显然 定义361对于形式背景F=(U,A,),C≤ 决策类中所有对象决策值相同，记为d(D)。称T,= A,可以得到形式背景Fc=(U,C,Ic),Fc称为F的 {d(D,d(D,),…,d(D》为决策类D,的决策值。 子背景，其中Ic=In(U×C)。 设F=(U,A,L,D,G是一个粒协调决策形式 则对XsU,定义映射C:P(U→P(C:XC= 背景.BSA.记 RB={(x,x)∈U×U:xoSx,Va∈B}(4) {a∈C:YxeX,(x,a)e。特别地，当X={x},C={a 时有 则容易证明： {a,(x,a)∈I (3) 1)x={x,∈U:(x,x)∈Rg 0.(x.a)I 2)x二D台RBC RD,即B是粒协调集等价即更易获取决策规则。越来越多的学者开始深入 研究决策形式背景的属性约简与规则提取问题。 2009 年，Wu[6] 研究了保持概念格的粒结构不 变的属性约简与规则提取，并给出具体算法。 Li 等 [7-9] 提出了一种新的决策形式背景知识约简 框架，给出约简算法，且在决策形式背景研究了 保持决策规则不变的属性约简。Li 等 [10] 研究了 基于同余关系的不协调决策形式背景的属性约 简。Li 等 [11] 提出了基于最大规则的决策形式背 景中的新型属性约简。Chen[12-13] 提出了一种大数 据模型下的快速属性约简模型，并结合实例分析 其算法复杂度。Yang[14] 基于蕴涵映射对实数集 决策形式背景中的属性约简和规则提取问题进行 研究。Qi[15] 从多角度讨论了两类三支概念格与 传统概念格之间的联系, 并给出了在经典概念格 基础上构造三支概念格的算法。 Zhang 等 [16] 利 用概念格提出了一种基于案例的层次化分类器。 Zhang 等 [17] 研究了模糊决策格值信息系统上的近 似约简与规则提取。张[18-19] 叙述了信息系统上的 知识发现与知识约简, 提出了协调近似表示空间 上的规则融合方法。 目前在概念格领域已取得诸多成果，但仍存 在众多问题有待解决。比如基于等价关系的粒协 调决策形式背景的属性约简问题，利用确定性规 则获取全部规则的具体途径，本文将进一步讨论 这些问题。 1 预备知识 F = (U, A,I) U = {x1, x2,··· , xn} A = {a1,a2,··· ,am} I ⊆ U × A (x,a) ∈ I x a P(U) U P(A) A ∀X ∈ P(U) B ∈ P(A) 定义 1 [6] 设三元组 是形式背景， ， ， 。如果 ，则称 具有属性 。用 表示 的幂集， 表示 的幂集。 ， ，定义： X ∗ = {a ∈ A : ∀x ∈ X,(x,a) ∈ I} (1) B ◁ = {x ∈ U : ∀a ∈ B,(x,a) ∈ I} (2) F = (U, A,I) (X,B) ∈ P(U)× P(A) X ∗ = B B ◁ = X (X,B) X (X,B) B (X,B) 定义 2 [6] 对于形式背景 ，若二元 组 满足 且 ，则 称为形式概念或概念。其中 是概念 的外延， 是概念 的内涵。 F = (U, A,I) C ⊆ A FC = (U,C,IC) F IC=I∩(U ×C) 定义 3 [ 6 ] 对于形式背景 ， ，可以得到形式背景 ，FC 称为 的 子背景，其中 。 X ⊆ U ∗C : P(U) → P(C) : X ∗C = {a ∈ C : ∀x ∈ X,(x,a) ∈ I} X = {x} C = {a} 则对 ，定义映射 。特别地，当 ， 时有 x ∗{a} = { {a}, (x,a) ∈ I Ø, (x,a) < I (3) 定义 4 Vl(l ⩽ m) [19] 设 是非空有限集，记 P= {E= (E1,E2,···,Em) : El ⩽ Vl(l ⩽ m)} ⊆ P(E1)× P(E2)× ··· ×(Em) P P E= (E1,···,Em) S= (S1,···,Sm) ∀l ⩽ m El ⩽ Sl E ⩽ S (P, ⩽ ) 称 为集合向量空间。对于 中的两个集合向 量 ， ，如果 ，均有 ，则记 ，且 为偏序集。 (P, ⩽ ) D : P 定义 5 2 → [ 1 9 ] 设 为偏序集，称 [0,1] 为集值向量包含度，满足下列条件： 1) 0 ⩽ D(S/E) ⩽ 1 ； 2) E ⩽ S 时， D(S/E) = 1 ； 3) E ⩽ S ⩽ G 时， D(E/G) ⩽ D(E/S)。 2 基于等价关系的粒协调决策形式 背景的属性约简 以往对决策形式背景进行讨论时通常会分别 构造条件概念格与决策概念格，利用两者的序关 系来定义形式背景的协调性。本节利用等价关系 对对象集进行划分，从而得到对应的决策类，可以 在保持对象的决策不变的前提下删除冗余属性。 F = (U, A,I, D,G) A D A∩ D = Ø I ⊆ U × A RD = {(x, y) ∈ U ×U : dl(x) = dl(y)(∀dl ∈ D)} U 设 为一个决策形式背景， 为条件属性集， 为决策属性集，并且 ， 。定义 ，则由上述等价关系可产生 上的一个划分： U/RD = {[x]D : x ∈ U}= {D1,D2,··· , Dr} 其中 [x]D= {y ∈ U : (x, y) ∈ RD} ∀x ∈ U x ∗A◁ ⊆ [x]D F 如果 ，均满足 ，则称决策形式 背景 是粒协调的。 F = (U, A,I, D,G) B ⊆ A ∀x ∈ U x ∗B◁ ⊆ [x]D B F C ⊂ B ∀x ∈ U x ∗C◁ ⊆ [x]D B F 定义 6 设 为粒协调决策形 式背景，对 ，如果 ，都有 ，则 称 是 的一个粒协调集。进一步，如果不存在 ，使得 都有 ，则 是 的粒 约简。 F {Bi : i ⩽ l} F B = ∩l i=1 Bi F B 注：1) 对粒协调决策形式背景 来说，必存 在粒约简。如用 表示 所有的粒约简， 则 为 的核心， 中的元素称为核心元 素或绝对必要属性。 x y ∈ Dj ∀dl ∈ D dl(x) = dl(y) dl(Dj) Tj = {d1(Dj),d2(Dj),··· ,d|D|(Dj)} Dj 2) 对于 ， ， 有 ，显然 决策类中所有对象决策值相同，记为 。称 为决策类 的决策值。 F = (U, A,I, D,G) B ⊆ A 设 是一个粒协调决策形式 背景， ，记 RB = {(xi , xj) ∈ U ×U : x ∗{a} i ⊆ x ∗{a} j ,∀a ∈ B} (4) 则容易证明： x ∗B◁ i = {xj ∈ U : (xi 1) , xj) ∈ RB} ； x ∗B◁ 2) i ⊆ [xi]D ⇔ RB ⊆ RD，即 B 是粒协调集等价 第 6 期 张晓鹤，等：粒协调决策形式背景的属性约简与规则融合 ·1139·