·66· 智能系统学报 第2卷 个对象x的属性值，即x∈U,a∈A,有f(x,ad∈ 识矩阵的定义得到.根据性质)，计算最小化决策 Va. 规则可辨识矩阵时，只需计算矩阵的下三角矩阵即 对于任意B∈A,记：ind(B)={(x,以：f(x,a)= 可 f(y,ad,廿au∈A},则ind(B)是U上的等价关系， 实例1考虑如表1的决策表，条件属性集C= 称为由B决定的不可区分关系，它们产生的U上的 a,b,c,决策属性集D=/d,U={#1,#2,#3, 划分为：U/ind(B)=[x]s:x∈U},其中：[x]a= #4,#5 fy:(x,以Gnd(B)}是x关于B的等价类P. 表1决策表 定义2设决策表系统S=<U,A,V,f>,AS Table 1 Decision table 是S上的一个基本算法，AS中有相同后件中的所 C a b c 有基本规则的集合被表示为AS·,并且用AP表示 #1 1 0 2 1 属于AS·的决策规则的所有前件的集合.如果= #2 2 0 3 1 sVAP一V(AP-),则在AS中的基本规则 #3 1 1 中→是可约去的，其中VAP表示AP中所有公式 #4 3 的析取，否则这条规则在AS中是不能被约去的： #5 0 0 如果AS中所有决策规则都是不能被约去的，则规 则集合AS被称为独立的：如果AS6中所有决策规 在表1中求得决策类1（相同后件(d,1)的所 则集都是独立的，并且=s VA P&-P,则称决策 有基本决策规则的集合为AS={(c,2)→(d,1), 规则集AS的子集AS。是AS0的一个约简，AS (a,2b,0)→(d,1),(b,2)→(d,1),(c,1)→(d 称做AS的一个最小化决策规则集.显然，AS可 )},其对应的最小化决策规则可辨识矩阵[C]为 以有多个最小化决策规则集P引 G1=C2=G3=C2=G23=C3=:G1=f(a,2)(b, 0};G1=f(c,2)∧c,1),c,2)∧b,2),(a,2)(b 2最小化决策规则集的计算方法 0)b,2),a,2)(b,0∧(c,1)};C2=f(a,2)(b, 定义3设决策表系统S=<U,A,V,f>,AS 0∧b,2),a,2(b,0∧(c,1)}. 是S上的一个基本算法，AS中有相同后件中的所 命题2设决策表系统S=<U,A,V,∫>， 有基本规则的集合为AS=中，9→中，…中一 AS0=中，攻→中，…，→剪为具有相同后件中 g,AP表示属于ASΦ的决策规则的所有前件的集 的所有基本规则的集合，[C]为决策规则集AS0的 合AP0={中，，…，虫}.记[中]表示满足所有后件中 最小化决策规则可辨识矩阵，AS为决策规则集 的对象集合，[A]表示满足所有前件的对象集 AS0的子集，AP6表示属于AS·的决策规则的所有 合，I=4],对任意的，∈(，当i为时， 前件的集合，则，出，=内对任意的G地都 C={6:6∈AP0且x,x∈[6]，或6=A∧4且x:∈ 存在Y∈C,使得YSAP. [4]、x∈4]，A、$∈AP}:当i=j时，C=中称 证明假设存在C≠中，不存在Y∈C,使得 Cg为x:,x的最小化决策规则集；[C]为决策规则 Y∈AP%,则x:∈（且x,∈6品，I6]或方∈(]且 集AS0=中→中，→中，…，虫→的最小化决策规 后品可，这与出1=子盾.所以，对任意 则集可辨识矩阵. 的Cg≠Φ，都存在Y∈C,使得YSAP6. 定义4设决策表系统S=<U,A,V,∫>， AS0={中→中，$→中，，虫→州为具有相同后件中 反证：假设存在，∈（且x,怎[可，对任意 的所有基本规则的集合，[C]为AS·的最小化决策 的x∈[，记C为x,x的最小化决策规则集，则 规则可辨识矩阵，则称M=个(Va::a∈C}为 不存在Y∈C,使得YSAP6,这与已知条件矛盾，所 可辨识公式. 以1可2I.又品，I∈.即，I1= 命题1[C]为决策规则集AS·=(4→中， $一中，中→的最小化决策规则可辨识矩阵，则 命题3设决策表系统S=<U,A,V,f>, [C1具有如下性质： AS={中→中，一→中，…虫→g为具有相同后件中 1)[Cg是对称矩阵：2[C1主对角线上的元素 的所有基本规则的集合，[Cg]为决策规则集AS的 为空 最小化决策规则可辨识矩阵，其对应的可辨识公式 性质1)2)可以直接根据最小化决策规则可辨 M的极小析取范式为M,则M包含AS的全体 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net个对象 x 的属性值 ,即 x ∈U , a ∈A ,有 f ( x , a) ∈ V a . 对于任意 B ΑA ,记:ind (B) = { ( x , y) : f ( x , ak ) = f ( y , ak ) , ΠaA ∈A} ,则 ind ( B) 是 U 上的等价关系 , 称为由 B 决定的不可区分关系 ,它们产生的 U 上的 划分为 :U/ ind ( B) = { [ x ]B : x ∈U} , 其中 : [ x ]B = { y :( x , y) ∈ind ( B) }是 x 关于 B 的等价类[2 - 3 ] . 定义 2 设决策表系统 S = < U , A ,V , f > , A S 是 S 上的一个基本算法 , A S 中有相同后件φ的所 有基本规则的集合被表示为 A Sφ ,并且用 A Pφ 表示 属于 A Sφ 的决策规则的所有前件的集合. 如果| = s ∨A Pφ ∴∨( A Pφ - { <}) , 则在 A S 中的基本规则 <→φ是可约去的 ,其中 ∨A Pφ 表示 A Pφ 中所有公式 的析取 ,否则这条规则在 A Sφ 中是不能被约去的; 如果 A Sφ 中所有决策规则都是不能被约去的 ,则规 则集合 A Sφ 被称为独立的;如果 A S′φ 中所有决策规 则集都是独立的 ,并且| = s ∨A Pφ ∴A P′φ ,则称决策 规则集 A Sφ 的子集 A S′φ 是 A Sφ 的一个约简 , A S′φ 称做 A Sφ 的一个最小化决策规则集. 显然 , A Sφ 可 以有多个最小化决策规则集[2 - 3 ] . 2 最小化决策规则集的计算方法 定义 3 设决策表系统 S = < U , A ,V , f > , A S 是 S 上的一个基本算法 , A S 中有相同后件φ的所 有基本规则的集合为 A Sφ = { <1 →φ, <2 →φ, …, <n → φ} , A Pφ 表示属于 A Sφ 的决策规则的所有前件的集 合 A Pφ = { <1 , <2 , …, <n } . 记[φ]表示满足所有后件φ 的对象集合 , [ <k ]表示满足所有前件的 <k 对象集 合 ,[ <] = ∪ n k = 1 [ <k ] ,对任意的 xi , x j ∈[ <] ,当 i ≠j 时 , Cij = {δ:δ∈A P< 且 x i , x j ∈[δ] ,或δ= <k ∧<l且 x i ∈ [ <k ]、x j ∈[ <l ] , <k 、<l ∈A Pφ} ;当 i = j 时 , Cij =Φ. 称 Cij为 x i , x j 的最小化决策规则集; [ Cij ]为决策规则 集 A Sφ = { <1 →φ, <2 →φ, …, <n →φ}的最小化决策规 则集可辨识矩阵. 定义 4 设决策表系统 S = < U , A , V , f > , A Sφ = { <1 →φ, <2 →φ, …, <n →φ} 为具有相同后件φ 的所有基本规则的集合 ,[ Cij ]为 A Sφ 的最小化决策 规则可辨识矩阵 ,则称 M = ∧i , j ( ∨{ ak ∶ak ∈Cij } 为 可辨识公式. 命题 1 [ Cij ]为决策规则集 A Sφ = { <1 →φ, <2 →φ, …, <n →φ}的最小化决策规则可辨识矩阵 ,则 [ Cij ]具有如下性质 : 1) [ Cij ]是对称矩阵;2) [ Cij ]主对角线上的元素 为空. 性质 1) 、2) 可以直接根据最小化决策规则可辨 识矩阵的定义得到. 根据性质 1) ,计算最小化决策 规则可辨识矩阵时 ,只需计算矩阵的下三角矩阵即 可. 实例 1 考虑如表 1 的决策表 ,条件属性集 C = { a , b, c} ,决策属性集 D = { d} , U = { # 1 , # 2 , # 3 , # 4 , # 5} . 表 1 决策表 Table 1 Decision table U a b c d # 1 1 0 2 1 # 2 2 0 3 1 # 3 1 2 1 1 # 4 2 1 3 0 # 5 1 0 3 0 在表 1 中求得决策类 1 (相同后件 ( d , 1) ) 的所 有基本决策规则的集合为 A Sφ = { ( c , 2) →( d , 1) , ( a ,2) ( b, 0) →( d , 1) , ( b, 2) →( d , 1) , ( c , 1) →( d , 1) } ,其对应的最小化决策规则可辨识矩阵[ Cij ]为 C11 = C12 = C13 = C22 = C23 = C33 =Φ; C21 = { ( a ,2) ( b, 0) } ; C31 = { ( c ,2) ∧( c , 1) , ( c , 2) ∧( b, 2) , ( a , 2) ( b, 0) ∧( b,2) , ( a , 2) ( b, 0) ∧( c , 1) } ; C32 = { ( a , 2) ( b, 0) ∧( b,2) , ( a ,2) ( b,0) ∧( c ,1) } . 命题 2 设决策表系统 S = < U , A , V , f > , A Sφ = { <1 →φ, <2 →φ, …, <n →φ} 为具有相同后件φ 的所有基本规则的集合 ,[ Cij ]为决策规则集 A Sφ 的 最小化决策规则可辨识矩阵 , A S′φ 为决策规则集 A Sφ 的子集 , A P′φ 表示属于 A S′φ 的决策规则的所有 前件的集合 ,则δ ∪∈A Pφ′ [δ] = [ <] Ζ对任意的 Cij ≠Φ,都 存在γ∈Cij使得γΑA P′. 证明 假设存在 Cij ≠Φ, 不存在γ∈Cij 使得 γΑA P′φ ,则 xi ∈[ <]且 xi /∈δ ∪∈A Pφ′ [δ]或 x j ∈[ <]且 x j /∈δ ∪∈A Pφ′ [δ] ,这与δ ∪∈A Pφ′ [δ] = [ <]矛盾. 所以 ,对任意 的 Cij ≠Φ,都存在γ∈Cij使得γΑA P′φ. 反证 :假设存在 xi ∈[ <]且 xi /∈δ ∪∈A Pφ′ [δ] ,对任意 的 x j ∈[ <] ,记 Cij为 x i , x j 的最小化决策规则集 ,则 不存在γ∈Cij 使得γΑ A P′φ ,这与已知条件矛盾 ,所 以 , δ ∪∈A Pφ′ [δ] Β [ <]. 又δ ∪∈A Pφ′ [δ] Α [ <] , 即δ ∪∈A Pφ′ [δ] = [ <]. 命题 3 设决策表系统 S = < U , A , V , f > , A Sφ = { <1 →φ, <2 →φ, …, <n →φ} 为具有相同后件φ 的所有基本规则的集合 ,[ Cij ]为决策规则集 A Sφ 的 最小化决策规则可辨识矩阵 ,其对应的可辨识公式 M 的极小析取范式为 M1 ,则 M1 包含 A Sφ 的全体 · 66 · 智 能 系 统 学 报 第 2 卷