第3期 尹继亮，等：不协调区间值决策系统的最大分布约简 ·473· 假设S(x=Sx),有(，x)ET,即Y(x)=Yx), AcC,则A是最大分布协调集当且仅当任意x,x∈U, 又因为yx)=y(x)和y(x)=y(x)成立，那么 当yx)≠y(c)时，有DM(i)nA≠O。 (x)=Y(x),这与y()≠y(x)矛盾，从而任意 证明“一”：设A是最大分布协调集，对于任意的 x,x∈U,当/()=y(x)时，有(x)≠S(x)。 x,x,∈U,假设存在DMOMA(i,)使DMa(，位jnA≠O, “=”:对任意，x∈U,当S(x)=S(x）,有 则存在S(x)和S(x),有y(x)≠Y(x),由定理1得 y(x)=y(x),对于任意的D∈y(,有D∈Y() S)≠S(x),从而存在ak∈A,满足a<a,因此存 由于S)=US(xS(x)eJ(S(x},于是对任意 在a4∈MPM(，低)，即DMM(,i)nA≠O。 的k≤q,有 “=”:假设存在x,x∈U,满足y(x)≠y(x,且 D(D/SA(xi))= DMa位，)nA≠O,则对任意a∈A,有DMPMa(低，j, ∑{D.nS(x:S(x)eJ((x)川 a崎>a,因此(：，x)∈T。假设x、x对应的a-相容类 IS(G川 分别为S(x)和S(x,则有S(x)=S(x)由定理 ∑D.S2 IS( Z11S(x训 IS(c川 S(x)∈J(S(x)》 1得A不是最大分布协调集。定理得证。 定义16设区间值决策系统DS=(U,CUD,V,fD, 9 IS( IS(x) S(x;)EJ(S(x)) C={a1,a2,…,aGl,DMx(位，)表示最大分布可辨识矩 DnS=DD1Sx》 阵中第行j列的元素，基于α-相容类的最大分布可 IS(x) 辨识函数为与a1,a2,…,an相对应C个布尔变量āg 故D。∈y(,从而yx)=y()o 的布尔函数：fg(C)Max(a,a2,…,ac)=A(VDMPMa(i,): 另一方面，任意的D∈yx),若D(),则 DM%ax(位，)≠O,为基于a-相容类的最大分布约简可 任意的S(x)∈JSx),由yx)=y(x）可得 辨识函数，简称最大分布可辨识函数。VDM(位，) m(x)>D(D./S(x》。取D∈y(x),则 表示满足aeDM%Max(i,)的全体布尔变量a的析取式。 DDL/S(x)》= 利用分配率和吸收率将f(C)ax转化为（ā， Σ9 1S(x川 :S(x)eJ(S(x》 a2,…,ag)=(A0)V…V(g),a≤C,k=(a1,a2,…,ag)= S() (A8)V…V(0),0≤C,k=1,2,…,l,0中每一个属性 ∑me)x S(x) SG) :S(x）∈J(S(x)> 元素只出现一次。 定理4设区间值决策系统DS=(U,CUD, ∑DD.1Sx》 S(x训 ISx) :S(x)∈J(S()》 Vf),h(C)au是可辨识函数(C)Mar的形式转化，若 IDnS(xl、IS(x训 A是最大分布约简，当且仅当A是h(C)人x的一个蕴 IS(x IS4(x) Sc(xj)EJ(S(x)) 含项。 D.nS(c训 D(Dj/S(x)) 证明“=”：假设0是h(C)ax的一个蕴含项，则 S(x訓 存在DM(位，)n0≠O,通过定理2得知0是其中一 与D。∈y(x)矛盾，因此D。∈y(x),于是有yx)S 个最大分布约简。 (x)。 “←”：根据定义16可得hg(C)Max(a1,a2,…,an)= 因此，证明了对任意x∈U,yx)=y(x),即集 (A0)V…V(0),0二C,k=1,2,…,1若在0中去掉一个元 合A是最大分布协调集。定理得证。 素形成0，则存在S(x)和S(x)满足y(x)≠y(x, 定义15设区间值决策系统DS=(U,CUD,V,f), 使得DMx(,)n0≠O,故g不是最大分布约简， U={,2,…,x山，则对任意i≥L,j≤W 从而0是其中一个最大分布约简。定理得证。 DMoMx(i,j)= {alak∈CAa崎<a以，yx)≠yx) 基于差别矩阵的分布约简算法(maximum dis- 0,y(x)=y(x) tribution reduction algorithm based on discernibility DMa(位，)为基于a-相容类的最大分布约简可 matrix,.MDRADM)描述如算法2。 辨识矩阵DMM第行j列的元素，DMa简称为最 算法2 MDRADM 大分布可辨识矩阵，其中i,j=1,2,…,U八，0表示空集。 输入区间值决策系统DS,阈值a。 基于-相容类的最大分布可辨识矩阵是一个 输出区间值决策系统的所有最大分布保持约 相对于主对角线对称的矩阵，在进行运算时只需考 简结果。 虑其上三角或下三角部分即可。 1)计算区间值决策系统DS在阈值α下的相容 定理3设区间值决策系统DS=(U,CUD,Vf), 类集合S:(U)。S α A (xi) = S α A (xj) (xi , xj) ∈ T α A γ α A (xi) = γ α A (xj) γ α A (xi) = γ α C (xi) γ α A (xj) = γ α C (xj) γ α C (xi) = γ α C (xj) γ α C (xi) , γ α C (xj) xi , xj ∈ U γ α C (xi) = γ α C (xj) S α A (xi) , S α A (xj) 假设 ，有 ，即 ， 又因为 和 成立，那么 ，这与 矛盾，从而任意 ，当 时，有 。 ⇐ xi , xj ∈ U S α A (xi) = S α A (xj) γ α C (xi) = γ α C (xj) Dj0 ∈ γ α C (xi) Dj0 ∈ γ α C (xj) S α A (xi) = ∪{S α C (xj)|S α C (xj) ∈J(S α A (xi))} k ⩽ q “ ” ：对任意 ， 当 ， 有 ，对于任意的 ，有 。 由于 ，于是对任意 的 ，有 D(Dk/S α A (xi))= ∑ {|Dk ∩S α C (xj)| : S α C (xj) ∈ J(S α A (xi))} |S α A (xi)| = ∑{ |Dk ∩S α C (xj)| |S α C (xj)| × |S α C (xj)| |S α A (xi)| : S α C (xj) ∈ J(S α A (xi))} ⩽ ∑{ |Dj0 ∩S α C (xj)| |S α C (xi)| × |S α C (xj)| |S α A (xi)| : S α C (xj) ∈ J(S α A (xi))} = |Dj0 ∩S α A (xi)| |S α A (xi)| =D(Dj0 /S α A (xi)) Dj0 ∈ γ α C (xi) γ α A (xi) = γ α C 故 ，从而 (xi)。 Dj0 ∈ γ α A (xi) Dj0 ,γ α C (xi) S α C (xj) ∈ J(S α A (xi)) γ α C (xi) = γ α C (xj) m α C (xj) > D(Dj0 /S α C (xj)) Dk0 ∈ γ α C (xj) 另一方面，任意的 ，若 ，则 任意的 ， 由 可 得 。取 ，则 D(Dk0 /S α A (xi))= ∑{ |Dk0 ∩S α C (xj)| |S α C (xj)| × |S α C (xj)| S α A (xi) : S α C (xj) ∈ J(S α A (xi))} = ∑{ m α C (xj)× |S α C (xj)| |S α A (xi)| : S α C (xj) ∈ J(S α A (xi))} > ∑{ D(Dj0 /S α C (xj))× |S α AT(xj)| |S α A (xi)| : S α C (xj) ∈ J(S α A (xi))} = ∑{ |Dj0 ∩S α C (xj)| |S α C (xj)| × |S α C (xj)| |S α A (xi)| : S α C (xj) ∈ J(S α A (xi))} = |Dj0 ∩S α A (xi)| |S α A (xi)| = D(Dj0 /S α A (xi)) Dj0 ∈ γ α A (xi) Dj0 ∈ γ α C (xi) γ α A (xi) ⊆ γ α C (xi) 与 矛盾，因此 ，于是有 。 xi ∈ U γ α A (xi) = γ α C 因此，证明了对任意 ， (xi) ，即集 合 A 是最大分布协调集。定理得证。 DS = (U,C ∪ D,V, f) U = {x1, x2,··· , x|U|} i ⩾ 1, j ⩽ |U| 定义 15 设区间值决策系统 ， ，则对任意 ： DMα DMax(i, j) = { {ak |ak ∈ C ∧α k i j < α}, γα A (xi) , γ α A (xj) Ø, γα A (xi) = γ α A (xj) DMα DMax(i, j) DMα DMax i j DMα DMax i, j = 1,2,··· ,|U| 为基于 α-相容类的最大分布约简可 辨识矩阵 第 行 列的元素， 简称为最 大分布可辨识矩阵，其中 ，Ø表示空集。 基于 α-相容类的最大分布可辨识矩阵是一个 相对于主对角线对称的矩阵，在进行运算时只需考 虑其上三角或下三角部分即可。 定理 3 设区间值决策系统 DS = (U,C ∪ D,V, f)， A ⊆ C xi , xj ∈ U γ α C (xi) , γ α C (xj) DMα DMax(i, j)∩ A , Ø ，则 A 是最大分布协调集当且仅当任意 ， 当 时，有 。 ⇒ A xi , xj ∈ DMα DMax(i, j) DMα DMax(i, j)∩A , Ø S α C (xi) S α C (xj) γ α C (xi) , γ α C (xj) S α A (xi) , S α A (xj) ak ∈ A α k i j < α ak ∈ DMα DMax(i, j) DMα DMax(i, j)∩ A , Ø 证明 “ ”：设 是最大分布协调集，对于任意的 U，假设存在 使 ， 则存在 和 ，有 ，由定理 1 得 ，从而存在 ，满足 ，因此存 在 ，即 。 ⇐ γ α C (xi) ,γ α C (xj) DMα DMax(i, j)∩ A , Ø ak <DMα DMax(i, j) α k i j > α (xi , xj) ∈ T α A xi、xj α S α A (xi) S α A (xj) S α A (xi) = S α A (xj) A “ ”：假设存在 xi，xj∈U，满足 ，且 ，则对任意ak∈A，有 ， ，因此 。假设 对应的 -相容类 分别为 和 ，则有 ，由定理 1 得 不是最大分布协调集。定理得证。 DS = (U,C ∪ D,V, f) C = { a1,a2,··· ,a|C| } DMα DMax(i, j) i j a1,a2,··· ,am |C| a¯|C| f α D (C)Max(¯a1,a¯ 2,··· ,a¯|C|) =∧{∨DMα DMax(i, j) : 定义 16 设区间值决策系统 ， ， 表示最大分布可辨识矩 阵中第 行 列的元素，基于 α-相容类的最大分布可 辨识函数为与 相对应 个布尔变量 的布尔函数： DMα DMax(i, j) , Ø} α ∨DMα DMax(i, j) a ∈ DMα DMax(i, j) a¯ ，为基于 -相容类的最大分布约简可 辨识函数，简称最大分布可辨识函数。 表示满足 的全体布尔变量 的析取式。 f α D (C)Max (¯a1, a¯ 2,··· ,a¯|C|) = (∧θ1)∨ ··· ∨(θl) θk ⊆ C, k = (¯a1,a¯ 2,··· ,a¯|C|) = (∧θ1)∨ ··· ∨(θl), θk ⊆ C, k = 1,2,··· ,l θk 利用分配率和吸收率将 转化为 ， ， 中每一个属性 元素只出现一次。 DS = (U,C ∪ D, V, f) h α D (C)Max f α D (C)Max A h α D (C)Max 定 理 4 设区间值决策系统 ， 是可辨识函数 的形式转化，若 是最大分布约简，当且仅当 A 是 的一个蕴 含项。 ⇒ θ h α D (C)Max DMα DMax(i, j)∩θ , Ø θ 证明 “ ”：假设 是 的一个蕴含项，则 存在 ，通过定理 2 得知 是其中一 个最大分布约简。 ⇐ h α D (C)Max(¯a1,a¯ 2,··· ,a¯m) = (∧θ1)∨ ··· ∨(θl), θk ⊆ C, k = 1,2,··· ,l S α C (xi) S α C (xj) γ α C (xi) , γ α C (xj) DMα DMax(i, j)∩θ ′ , Ø “ ”：根据定义 16 可得 ，若在θ中去掉一个元 素形成 θ′，则存在 和 满足 ， 使得 ，故 θ′ 不是最大分布约简， 从而 θ 是其中一个最大分布约简。定理得证。 基于差别矩阵的分布约简算法 (maximum dis￾tribution reduction algorithm based on discernibility matrix，MDRADM) 描述如算法 2。 算法 2 MDRADM 输入 区间值决策系统 DS，阈值α。 输出 区间值决策系统的所有最大分布保持约 简结果。 α S α C (U) 1) 计算区间值决策系统 DS 在阈值 下的相容 类集合 。 第 3 期 尹继亮，等：不协调区间值决策系统的最大分布约简 ·473·