·472· 智能系统学报 第13卷 1.2区间值决策系统的分布约简 根据例2可知相似布尔矩阵以及相容类集合。 文献[16提出不协调区间决策系统的分布约简。 计算每个对象对应的概率分布： 定义10设区间值决策系统DS=(U,CUD, e(x)=1,0,2(x2)=0,1, Vf月，A≤U,U/D={D,D2,…,Duo,则xeU对应 2(x3)={2/3,1/3,e6(x4)=(0,1, 的概率分布定义为 2(xs)=2/3,1/3},(x6)=(2/3,1/3}。 (c)=(D(D/S(x),D(D2/Sc),…, 计算分布保持约简可辨识矩阵： DD,/S(x),·,D(Du/Sc》 0 式中DD,/Sg》= DinS SM,js1U1D。 a1,a2,a3,a4 0 定义11设区间值决策系统DS=(U,CUD, DMg(6,6)= a1,a2 a3,a40 a1,a2,a3 0 as 0 Vf月，U={x,2,…,ml,则对任商≤i,j≤U: a1,a2 a3,a4 a3 0 a1,42 a3,a40 a30 0 DMp(i,j)= {alas∈CAa<a,(x)≠(x) 0,(x)=(x) 计算分布约简可辨识函数： 式中：DMi,)为基于a-相容类的分布约简可辨识 (C)(a,az,as,a)=as(az va) 矩阵DMg第i行j列的元素，DMg简称为分布可辨识 转化后的分布约简可辨识函数为 矩阵，其中i,j=1,2.…,U八，0表示空集。 h (C)(a,az,aa)=(a Aa3)v (aza3) 定义12设区间值决策系统DS=(U,CUD,Vf), 因此分布保持约简为{a1,a}和(a2,a3。 C={a1,a2,…,ag},DM%(i,)表示可辨识矩阵中第 2区间值决策系统的最大分布约简 i行j列的元素，基于α-相容类的分布可辨识函数定 义为与a1,a2,…,ag相对应的C个布尔变量a,a2,…, 本节在区间值决策系统中引入最大规则置信度 ag的布尔函数为 的概念，提出了不协调区间值决策系统的最大分布 f(C)(a,a,.,a)=A(VDMD(i,D):DMD(i,i)#O 约简算法。 此函数简称分布可辨识函数。这里的vDM位，)表 定义13设区间值决策系统DS=(U,CUD,Vf, 示满足aE DMp((,)的全体布尔变量ā的析取式。 A≤C,UID={D,D2,…,Duol,则x∈U对应的最大 利用分配率和吸收率将fg(C)转化为h(C) 概率分布定义为 (a1,a2,…,am)=(A)V…V(A0),0≤C,k=1,2,…,l,0 mA(x:)=D(Dj/S(x))=max D(Di/S(x)) 中每一个属性元素只出现一次。 定理1设区间值决策系统DS=(U,CUD,Vf, x∈U对应的最大分布为 yx)={DlD(D,/S(x)》=D(D/Sg(x)》 (C)是分布可辨识函数f(C)的形式转化，若A二C 是分布约简，当且仅当A是(C)的一个蕴含项。 若对任意的x,∈U,有y(x)=y(x),称A是 基于可辨识矩阵的分布约简算法(distribution DS中基于α-相容关系的最大分布协调集，简称最大 分布协调集。若A是最大分布协调集，且A的任意 reduction algorithm based on discernibility matrix, DRADM)描述如下。 真子集都不是最大分布协调集，那么称A是DS中 算法1 DRADM 基于α-相容关系的最大分布相对约简，简称最大分 输入区间值决策系统DS,阈值a。 布约简。 输出区间值决策系统的所有分布保持约简结果。 定义14设区间值决策系统DS=(U,CUD,V,f), I)计算区间值决策系统DS的在阈值α下的相容 ASC,x∈U,若属性子集A满足： 类集合S(U): 1)y(x）=y(x: 2)根据每个对象对应的相容类，计算每个对象 2)任意BcA,满足y(x)≠Y(x 相对于每一个决策类的概率分布(x): 那么称属性子集A为区间值决策系统基于相容关 3)根据每个对象的可信度不同构造分布约简 系的最大分布约简。DS的所有约简集合记为a- 可辨识矩阵DM: Reduct,.所有约简的交集称为DS的核，记为a-Core。 4)由可辨识矩阵DM计算分布约简可辨识函 定理2设区间值决策系统DS=(U,CUD,V,f), 数f8(C): ASC,则A是最大分布协调集当且仅当任意x,x∈U, 5)利用分配率和吸收率将(C)转化为(C), 当y(x)=yx,有S()S(x (C)中每一个蕴含项为一个分布保持的约简。 证明记J(S(x》=(S(x,S(x,)≤S(x》。 例3如表1所示的区间值决策系统，令α=0.6， “一”：设A是最大分布协调集，对任意x,x∈U,1.2 区间值决策系统的分布约简 文献[16]提出不协调区间决策系统的分布约简。 DS = (U,C ∪ D, V, f) A ⊆ U U/D = {D1,D2,··· ,D|U/D|} 定义 1 0 设区间值决策系统 ， ， ，则 xi∈U 对应 的概率分布定义为 µ α A (xi) = (D(D1/S α A (xi)),D(D2/S α A (xi)),··· , D(Dj/S α A (xi),··· ,D(D|U|/S α A (xi))) D(Dj/S α A (xi)) = |Dj ∩S α A (xi)| |S α A (xi)| 式中 ， j ⩽ |U/D|。 DS = (U,C ∪ D, V, f) U = {x1, x2,··· , x|U|} 1 ⩽ i, j ⩽ |U| 定义 1 1 设区间值决策系统 ， ，则对任意 ： DMα D (i, j) = { {ak |ak ∈ C ∧α k i j < α}, µα A (xi) , µ α A (xj) Ø, µα A (xi) = µ α A (xj) DMα D (i, j) α DMα D i j DMα D i, j = 1,2,··· ,|U| 式中： 为基于 -相容类的分布约简可辨识 矩阵 第 行 列的元素， 简称为分布可辨识 矩阵，其中 ，Ø表示空集。 DS = (U,C ∪ D,V, f) C = {a1,a2,··· ,a|C|} DMα D (i, j) α a1,a2,··· ,a|C| |C| a¯ 1,a¯ 2,··· , a¯|C| 定义 12 设区间值决策系统 ， ， 表示可辨识矩阵中第 i 行 j 列的元素，基于 -相容类的分布可辨识函数定 义为与 相对应的 个布尔变量 的布尔函数为 f α D (C)(¯a1,a¯ 2,··· ,a¯|C|) = ∧{∨DMα D (i, j) : DMα D (i, j) , Ø} ∨DMα D (i, j) a ∈ DMα D (i, j) a¯ 此函数简称分布可辨识函数。这里的 表 示满足 的全体布尔变量 的析取式。 f α D (C) h α D (C) (¯a1,a¯ 2,··· ,a¯m) = (∧θ1)∨ ··· ∨(∧θl), θk ⊆ C, k = 1,2,··· ,l θk 利用分配率和吸收率将 转化为 ， 中每一个属性元素只出现一次。 DS = (U,C ∪ D,V, f) h α D (C) f α D (C) A ⊆ C h α D (C) 定理 1 设区间值决策系统 ， 是分布可辨识函数 的形式转化，若 是分布约简，当且仅当 A 是 的一个蕴含项。 基于可辨识矩阵的分布约简算法 (distribution reduction algorithm based on discernibility matrix， DRADM) 描述如下。 算法 1 DRADM 输入 区间值决策系统 DS ，阈值 α。 输出 区间值决策系统的所有分布保持约简结果。 DS α S α C (U) 1) 计算区间值决策系统 的在阈值 下的相容 类集合 ； µ α C (xi) 2) 根据每个对象对应的相容类，计算每个对象 相对于每一个决策类的概率分布 ； DMα D 3) 根据每个对象的可信度不同构造分布约简 可辨识矩阵 ； DMα D f α D (C) 4) 由可辨识矩阵 计算分布约简可辨识函 数 ； f α D (C) h α D (C) h α D (C) 5) 利用分配率和吸收率将 转化为 ， 中每一个蕴含项为一个分布保持的约简。 例 3 如表 1 所示的区间值决策系统，令α = 0.6， 根据例 2 可知相似布尔矩阵以及相容类集合。 计算每个对象对应的概率分布： µ 0.6 C (x1) = {1,0} µ 0.6 C (x2) = {0,1} µ 0.6 C (x3) = {2/3,1/3} µ 0.6 C (x4) = {0,1} µ 0.6 C (x5) = {2/3,1/3} µ 0.6 C (x6) = {2/3,1/3} ， ， ， ， ， 。 计算分布保持约简可辨识矩阵： DM0.6 D (6,6) =   Ø a1,a2,a3,a4 Ø a1 ,a2 a3 ,a4 Ø a1 ,a2 ,a3 Ø a3 Ø a1,a2 a3,a4 Ø a3 Ø a1,a2 a3,a4 Ø a3 Ø Ø   计算分布约简可辨识函数： f 0.6 D (C)(¯a1,a¯ 2,a¯ 3,a¯ 4) = a3 ∧(a2 ∨a1) 转化后的分布约简可辨识函数为 h 0.6 D (C)(¯a1,a¯ 2,a¯ 3,a¯ 4) = (a1 ∧a3)∨(a2 ∧a3) 因此分布保持约简为 {a1,a3} 和 {a2,a3}。 2 区间值决策系统的最大分布约简 本节在区间值决策系统中引入最大规则置信度 的概念，提出了不协调区间值决策系统的最大分布 约简算法。 DS = (U,C ∪ D,V, f) A ⊆ C U/D = {D1,D2,··· ,D|U/D|} xi ∈ U 定义 13 设区间值决策系统 ， ， ，则 对应的最大 概率分布定义为 m α A (xi) = D(Dj0 /S α A (xi)) = max j⩽q D(Dj/S α A (xi)) xi ∈ U 对应的最大分布为 γ α A (xi) = {Dj |D(Dj/S α A (xi)) = D(Dj0 /S α A (xi)} γ α A (xi) = γ α C (xi) α α 若对任意的 x i∈U，有 ，称 A 是 DS 中基于 -相容关系的最大分布协调集，简称最大 分布协调集。若 A 是最大分布协调集，且 A 的任意 真子集都不是最大分布协调集，那么称 A 是 DS 中 基于 -相容关系的最大分布相对约简，简称最大分 布约简。 DS = (U,C ∪ D,V, f) A ⊆ C xi ∈ U 定义 14 设区间值决策系统 ， ， ，若属性子集 A 满足： γ α A (xi) = γ α C 1) (xi) ； B ⊂ A γ α B (xi) , γ α C 2) 任意 ，满足 (xi) ； α Reduct α Core 那么称属性子集 A 为区间值决策系统基于相容关 系的最大分布约简。DS 的所有约简集合记为 - ，所有约简的交集称为 DS 的核，记为 - 。 DS = (U,C ∪ D,V, f) A ⊆ C xi , xj ∈ U γ α C (xi) = γ α C (xj) S α A (xi) ,S α A (xj) 定理 2 设区间值决策系统 ， ，则 A 是最大分布协调集当且仅当任意 ， 当 ，有 。 J(S α A (xi)) = {S α C (xj)|S α C (xj) ⊆ S α A (xi)} ⇒ 证 明 记 。 “ ”：设 A 是最大分布协调集，对任意 xi，xj∈U， ·472· 智 能 系 统 学 报 第 13 卷