·1140· 智能系统学报 第14卷 于RB C RDo G 定义7 设F=(U,A,L,D,G)是一个粒协调决策 输出B(粒约简集) 形式背景.x,v∈U,x与y的辨识属性集定义如下： 1)for1sisUⅥand1sss4 D,y={aeA:rgya.d≠d) 其他 (5) 2)if (xia,)EI.x;d =a, 10, 3)else x;"tal 且D={D(x,y)Ix,y∈U)为F的辨识矩阵。 4)initialize Da(xi.x)= 由定义7可知，以下性质显然成立： 5)for 1sssl and 1s/D do 1)Da(x,x)=0: 6)if x"la x"la and di(x)+di(x)then 2)Da(xy)∩D0y,x)=0。 7) Da(,x)←Da(x,x）Vas 定理1设F=(U,A,L,D,G)是一个粒协调决 8)end if 策形式背景，BSA。则B是F的粒协调集，当且 9)end for 仅当Da(x,y)≠O时有B∩D(x,y)≠0。 10)initialize B=O 证明（一→）当D(x,y)≠0时，由定义7可知， Yd∈D均满足d()≠d),即(x,y)生Ro。而B是 11)for1sisU八，1 sU do F的粒协调集，则有RSRD。因此(x,y)生R,故 12)B=BA Da(xi,x) 必存在b∈B使得x4y。所以b∈D(x,y)。因 13)end for 而B∩Da(x,y)≠0。 14)compute B=V=() (=)若D(x,y)≠O,则Yd∈D,d(x)≠dy),即 15)return B (x,)Ro。故B∩D(x,y)≠O,一定存在b∈B,使 例1表1给出了一个决策形式背景，其中对 得b∈D(x,y,则有x生y,从而(x,y)生RB。当 象集U={x1,,,x4,x,x6小，D={d山为决策属性 (x,y)生RD时(x,y)生RB,故R&C RD。综上，B是F 集。A={a1,a2,a3,a4,a5,a6,a,as}为条件属性集。 的粒协调集。 表1决策形式背景F=(U,A,I,D,G) 定理2设F=(U,A,L,D,G)是一个粒协调决 Table 1 A formal decision context:F=(U,A,I,D,G) 策形式背景，a∈A,则a是F的核心属性，等价于 U a a2 asasasas a as d 存在x,yeU使得Du(x,y)={alo 1 证明(=)如果条件属性a∈A是F的核心 属性，则A-{al不可能是F的粒约简，即RA-o￠Ro。 1 故存在x,y∈U,使得(c,y)生Rn时有(x,y)∈RA-ao 3 1 1 此时d(x)≠dy)。又易证xa4y,由定义7可知 X4 1 1 1 3 aeD(x,y),即3x,yeU使得D(x,y)={a(事实上， Xs 1 如xa≤ya,则由(x,y∈RA-可知(c,y)eRAo 又F是一个粒协调决策形式背景，所以R4SRo, 1 1 1 1 2 即VdeD均满足d(x)=doy),这与d(x)≠d)矛 古 1 3 盾，所以xa4ya)o (∈)如果D(xy)={a,定义7可知d(x)≠dy) 计算可知： xa生ya并且任取b∈A-a,必有xo二yo。因此 x=x,2,3}=[x]D,x={2,3}[x2lD=[x]D (x,y)ERn且(x,y)∈RA-a。故可得RA-a生Rn,即 x={x3}二[x3]b=[xJD,x={x4}{x4,x}=[x4D A-{a不是F的粒约简，a是F的核心属性。 xs (xs,X6)E [xs,x6)=[xs]D 定义8设F=(U,A,I,D,GO是一个粒协调决 x=(x6)C [x6lD [xs]D,x=(x[xi]D [xa]D 策形式背景，xvEU、D(x,y≠O。记 M=入(Dax,)=A(Va:aeDa(x,y》 可知F为粒协调的，其辨识矩阵如表2所 (6) 示。由布尔方法可获取F的所有粒约简，具体过 基于文献[18]可知，如果B={a。:t≤qu}中没 程如下： 有重复元素，则 M=A(VDa(x,y)) M=VR(a) (7) =a AasAas Aas A(a3 Vas) 称为F的极小析取范式。B(k≤p)是F的所有 =(a1Aa4Aa6 Ads Aa3)V(a1∧a4Aa6Aag∧as) 粒约简的集合，具体算法如下： 故该形式背景存在两个粒约简，即B,={a1, 算法1粒协调决策形式背景的属性约简算法 a3,a46,ag}与B2={a1,a4,a5,a6,ag,F的核心属性为 输入粒协调决策形式背景F=(U,A,L,D, a1,a4,a6与ag0于 RB ⊆ RD。 F = (U, A,I, D,G) x, y ∈ U x y 定义 7 设 是一个粒协调决策 形式背景， ， 与 的辨识属性集定义如下： Dd(x, y)= { {a ∈ A : x ∗{a} ⊈ y ∗{a} }, dl(x) , dl(y) Ø, 其他 (5) D ∗ 且 = {Dd(x, y) | x, y ∈ U} 为 F 的辨识矩阵。 由定义 7 可知，以下性质显然成立： 1) Dd(x, x) = Ø ； Dd(x, y) ∩ 2) Dd(y, x) = Ø。 F = (U, A,I, D,G) B ⊆ A B F Dd(x, y) , Ø B ∩ Dd(x, y) , Ø 定理 1 设 是一个粒协调决 策形式背景， 。则 是 的粒协调集，当且 仅当 时有 。 (⇒) Dd(x, y) , Ø ∀dl ∈ D dl(x) , dl(y) (x, y) < RD B F RB ⊆ RD (x, y) < RB b ∈ B x ∗{b} ⊈ y ∗{b} b ∈ Dd(x, y) B ∩ Dd(x, y) , Ø 证明 当 时，由定义 7 可知， 均满足 ，即 。而 是 的粒协调集，则有 。因此 ，故 必存在 使得 。所以 。因 而 。 (⇐) Dd(x, y) , Ø ∀dl ∈ D dl(x) , dl(y) (x, y) < RD B ∩ Dd(x, y) , Ø b ∈ B, b ∈ Dd(x, y) x ∗{b} ⊈ y ∗{b} (x, y) < RB (x, y) < RD (x, y) < RB RB ⊆ RD B F 若 ，则 ， ，即 。故 ，一定存在 使 得 ，则有 ，从而 。当 时 ，故 。综上， 是 的粒协调集。 F = (U, A,I, D,G) a ∈ A a F x y ∈ U Dd(x, y) = {a} 定理 2 设 是一个粒协调决 策形式背景， ，则 是 的核心属性，等价于 存在 ， 使得 。 (⇒) a ∈ A F A− {a} F RA−{a} ⊈RD x y ∈ U (x, y) < RD (x, y) ∈ RA−{a} dl(x) , dl(y) x ∗{a} ⊈ y ∗{a} a ∈ Dd(x, y) ∃x, y ∈ U Dd(x, y) = {a} x ∗{a} ⊆ y ∗{a} (x, y) ∈ RA−{a} (x, y) ∈ RA F RA ⊆ RD ∀dl ∈ D dl(x) = dl(y) dl(x) , dl(y) x ∗{a} ⊈ y ∗{a} 证明 如果条件属性 是 的核心 属性，则 不可能是 的粒约简，即 。 故存在 ， ，使得 时有 。 此时 。又易证 ，由定义 7 可知 ，即 使得 (事实上， 如 ，则由 可 知 。 又 是一个粒协调决策形式背景，所以 ， 即 均满足 ，这与 矛 盾，所以 )。 (⇐) Dd(x, y) = {a} dl(x) , dl(y) x ∗{a} ⊈ y ∗{a} b ∈ A−a, x ∗{b} ⊆ y ∗{b} (x, y) < RD (x, y) ∈ RA−{a} RA−{a} ⊈ RD A− {a} F a F 如果 ，定义 7 可知 并且任取 必有 。因此 且 。故可得 ， 即 不是 的粒约简， 是 的核心属性。 F = (U, A,I, D,G) x, y ∈ U Dd(x, y) , Ø 定义 8 设 是一个粒协调决 策形式背景， ， 。记 M=∧(∨Dd(x, y)) = ∧(∨{al : al ∈ Dd(x, y)}) (6) B q k = {ait 基于文献 [18] 可知，如果 : t ⩽ qk} 中没 有重复元素，则 M = ∨ p k=1 (∧ qk t=1 ait ) (7) 称为 F 的极小析取范式。 Bk(k ⩽ p) 是 F 的所有 粒约简的集合，具体算法如下： 算法 1 粒协调决策形式背景的属性约简算法 输入 粒协调决策形式背景 F=(U，A，I，D， G) 输出 B (粒约简集) 1) for 1≤i≤|U| and 1≤s≤|A| (xi ,as) ∈ I, xi ∗{as} 2) if = as xi ∗{as} 3) else = Ø Dd ( xi , xj ) 4) initialize = Ø 5) for 1≤s≤|A| and 1≤l≤|D| do xi ∗{as} ⊈ xj ∗{as} and dl(xi) , dl ( xj ) 6) if then Dd ( xi , xj ) ← Dd ( xi , xj ) 7) ∨as 8) end if 9) end for 10) initialize B = Ø 11) for 1≤i≤|U|, 1≤j≤|U| do B = B∧ Dd ( xi , xj ) 12) 13) end for B = ∨ p m=1 ( ∧ si q=1 aq ) 14) compute 15) return B U = {x1, x2, x3, x4, x5, x6, x7} D = {d} A = {a1,a2,a3,a4,a5,a6,a7,a8} 例 1 表 1 给出了一个决策形式背景，其中对 象集 ， 为决策属性 集。 为条件属性集。 表 1 决策形式背景 F = (U, A,I, D,G) Table 1 A formal decision context: F = (U, A,I, D,G) U a1 a2 a3 a4 a5 a6 a7 a8 d x1 1 − − − − 1 − − 1 x2 1 − − − − 1 1 − 1 x3 1 1 − − − 1 1 − 1 x4 − 1 − − 1 1 1 1 3 x5 1 − 1 − 1 − − − 2 x6 1 1 1 − 1 − − − 2 x7 − 1 1 1 − − − − 3 计算可知： x ∗◁ 1 = {x1, x2, x3} = [x1]D, x ∗◁ 2 = {x2, x3} ⊆ [x2]D = [x1]D x ∗◁ 3 = {x3} ⊆ [x3]D = [x1]D, x ∗◁ 4 = {x4} ⊆ {x4 , x7} = [x4]D x ∗◁ 5 = {x5 , x6} ⊆ {x5 , x6} = [x5]D x ∗◁ 6 = {x6} ⊆ [x6]D = [x5]D, x ∗◁ 7 = {x7} ⊆ [x7]D = [x4]D F F 可知 为粒协调的，其辨识矩阵如表 2 所 示。由布尔方法可获取 的所有粒约简，具体过 程如下： M = ∧(∨Dd(x, y)) =a1 ∧a4 ∧a6 ∧a8 ∧(a3 ∨a5) =(a1 ∧a4 ∧a6 ∧a8 ∧a3)∨(a1 ∧a4 ∧a6 ∧a8 ∧a5) a3,a4,a6,a8} B2 = {a1,a4,a5,a6,a8} F a1,a4,a6 a8 故该形式背景存在两个粒约简，即 B1= {a1 , 与 ， 的核心属性为 与 。 ·1140· 智 能 系 统 学 报 第 14 卷