·380. 智能系统学报 第12卷 4)根据广义分布差别矩阵构造广义分布差别 Y98.(1)={<0,1>} 函数，并通过吸收率进行简化。 Y08,(u2)={<1,1> 5)在DF(Ma))基础上通过结合律获取所有 Y9.(u3)=⑦ 的广义分布保持约简。 Ya.(u4)=⑦ 其中，a和B满足(a=0∧B∈[0,1])或(a∈ 3)构造广义分布差别矩阵 [0,1]ΛB=1)。 [a,B]=[0,0.3]时对应的广义分布差别矩阵 由于上述算法是通过差别矩阵获取决策表的 如表2所示，[a,β]=[0.8,1]时对应的广义分布差 所有的广义分布保持约简，故算法在最坏情况下的 别矩阵如表3所示。 时间复杂度为O(|AT2),最坏情况下的空间复 表2广义分布差别矩阵1 杂度为O(|ATIU2),其中1U1为样本空间中的对 Table 2 Generalized distribution discernibility matrix 1 象数目，|AT为条件属性数，下面通过例1简要说 M[o.0.3] 明GDPRA的执行过程。 AT {a2} a2,a3}}a2,a3 例1如表1所示，论域为U={山1，山2，山3，u4}, {a2} AT {a3 {a3} AT={a1,a2,a3,a4}为条件属性集，D={d为决策属 u3 {a2,a3} {a3} AT AT 性，分别求[a,B]=[0,0.3]以及[a,B]=[0.8,1]时 的所有广义分布保持约简。 {a2,a3} {a3} AT AT 表1决策表 表3广义分布差别矩阵2 Table 1 Decision table Table 3 Generalized distribution discernibility matrix 2 a a Mlas.1] 41 2 AT 1 1 0 0 {a2} {a2,a3}{a2,a3} la2l AT {a3} {a3} 1 0 0 1 u3 {a2,a} 1a31 AT AT u3 1 0 2 {a2,a3}1a3} AT AT 1 0 4)获取差别函数并进行简化 1)获取每个对象的置信度分布 DF(Mo.aJ)=(a2)A(a3） U/AT={E1,E2,E3} DF(Ma8.)=(a2)A(a3) U/D={D1,D2,D3 5)通过结合律获取所有的广义分布保持约简 E,={u1} 由计算得，[a,B]=[0,0.3]时和[a,B]=[0.8, E2={u2} 1]时的所有广义分布保持约简均为{a2,a3}。 E3={u3,u4} D1=u1} 4一些特殊情形下的讨论 D2={u2,u4} 值得注意的是，给定决策表DT=(U,ATUD,V, D3={u3} ),当α和B取某些特殊值时，广义分布保持约简可 (41)=(1,0,0) 以退化为目前已存在的一些约简，本节将根据α和 u(42)=(0,1,0) B不同的特殊取值情况展开讨论，并给出相应的结 r(3)=(0,0.5,0.5) 论。其中，将MN、Mpos以及Ms分别记为广义决 r(44)=(0,0.5,0.5) 策可辨识矩阵、正域可辨识矩阵以及分布可辨识矩 2)获取每个对象的[α，B]决策-置信度序偶集 阵，同时，将M、M以及M分别记为对象山， 当a=0,B=0.3时 和”：对应在广义决策可辨识矩阵、正域可辨识矩阵 Y9a(41)={<1,0>,<2,0>} 以及分布可辨识矩阵的可辨识属性集，其中论域为 Y9aJ(2)={<0,0>,<2,0>} U={u1,山2，…，4n},i,je{1,2,…,n}。 Y00J(u3)={<0,0>} 1)a=B=0时 Y0aJ(u4)={<0,0> 当α和B取值均为0时，广义分布保持约简实 当x=0.8,B=1时 质是保证对于置信度为0的规则在约简前后的置信４） 根据广义分布差别矩阵构造广义分布差别 函数，并通过吸收率进行简化。 ５） 在 ＤＦ（Ｍ ［α，β］ ）基础上通过结合律获取所有 的广义分布保持约简。 其中，α 和 β 满足（α ＝ ０∧β∈［０，１］） 或（α∈ ［０，１］∧β ＝ １）。 由于上述算法是通过差别矩阵获取决策表的 所有的广义分布保持约简，故算法在最坏情况下的 时间复杂度为 Ｏ（ ＡＴ ｜ Ｕ｜ ２ ），最坏情况下的空间复 杂度为 Ｏ（ ＡＴ Ｕ ２ ），其中｜Ｕ ｜ 为样本空间中的对 象数目， ＡＴ 为条件属性数，下面通过例 １ 简要说 明 ＧＤＰＲＡ 的执行过程。 例 １ 如表 １ 所示，论域为 Ｕ ＝ ｛ｕ１ ，ｕ２ ，ｕ３ ，ｕ４ ｝， ＡＴ＝ ｛ａ１ ，ａ２ ，ａ３ ，ａ４ ｝为条件属性集，Ｄ＝ ｛ｄ｝为决策属 性，分别求［α，β］ ＝ ［０，０．３］以及［α，β］ ＝ ［０．８，１］时 的所有广义分布保持约简。 表 １ 决策表 Ｔａｂｌｅ １ Ｄｅｃｉｓｉｏｎ ｔａｂｌｅ Ｕ ａ１ ａ２ ａ３ ａ４ ｄ ｕ１ １ １ ０ １ ０ ｕ２ １ ０ ０ １ １ ｕ３ １ ０ １ １ ２ ｕ４ １ ０ １ １ １ １）获取每个对象的置信度分布 Ｕ／ ＡＴ ＝ ｛Ｅ１ ，Ｅ２ ，Ｅ３ ｝ Ｕ／ Ｄ＝ ｛Ｄ１ ，Ｄ２ ，Ｄ３ ｝ Ｅ１ ＝ ｛ｕ１ ｝ Ｅ２ ＝ ｛ｕ２ ｝ Ｅ３ ＝ ｛ｕ３ ，ｕ４ ｝ Ｄ１ ＝ ｛ｕ１ ｝ Ｄ２ ＝ ｛ｕ２ ，ｕ４ ｝ Ｄ３ ＝ ｛ｕ３ ｝ μＡＴ（ｕ１ ）＝ （１，０，０） μＡＴ（ｕ２ ）＝ （０，１，０） μＡＴ（ｕ３ ）＝ （０，０．５，０．５） μＡＴ（ｕ４ ）＝ （０，０．５，０．５） ２）获取每个对象的［α，β］决策－置信度序偶集 当 α＝ ０，β ＝ ０．３ 时 Υ ［０，０．３］ ＡＴ （ｕ１ ）＝ ｛＜１，０＞，＜２，０＞｝ Υ ［０，０．３］ ＡＴ （ｕ２ ）＝ ｛＜０，０＞，＜２，０＞｝ Υ ［０，０．３］ ＡＴ （ｕ３ ）＝ ｛＜０，０＞｝ Υ ［０，０．３］ ＡＴ （ｕ４ ）＝ ｛＜０，０＞｝ 当 α＝ ０．８，β ＝ １ 时 Υ ［０．８，１］ ＡＴ （ｕ１ ）＝ ｛＜０，１＞｝ Υ ［０．８，１］ ＡＴ （ｕ２ ）＝ ｛＜１，１＞｝ Υ ［０．８，１］ ＡＴ （ｕ３ ）＝ ⌀ Υ ［０．８，１］ ＡＴ （ｕ４ ）＝ ⌀ ３）构造广义分布差别矩阵 ［α，β］ ＝ ［０，０．３］ 时对应的广义分布差别矩阵 如表 ２ 所示，［α，β］ ＝ ［０．８，１］时对应的广义分布差 别矩阵如表 ３ 所示。 表 ２ 广义分布差别矩阵 １ Ｔａｂｌｅ ２ Ｇｅｎｅｒａｌｉｚｅｄ ｄｉｓｔｒｉｂｕｔｉｏｎ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ １ Ｍ ［０，０．３］ ｕ１ ｕ２ ｕ３ ｕ４ ｕ１ ＡＴ ｛ａ２ ｝ ｛ａ２ ，ａ３ ｝ ｛ａ２ ，ａ３ ｝ ｕ２ ｛ａ２ ｝ ＡＴ ｛ａ３ ｝ ｛ａ３ ｝ ｕ３ ｛ａ２ ，ａ３ ｝ ｛ａ３ ｝ ＡＴ ＡＴ ｕ４ ｛ａ２ ，ａ３ ｝ ｛ａ３ ｝ ＡＴ ＡＴ 表 ３ 广义分布差别矩阵 ２ Ｔａｂｌｅ ３ Ｇｅｎｅｒａｌｉｚｅｄ ｄｉｓｔｒｉｂｕｔｉｏｎ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ ２ Ｍ ［０．８，１］ ｕ１ ｕ２ ｕ３ ｕ４ ｕ１ ＡＴ ｛ａ２ ｝ ｛ａ２ ，ａ３ ｝ ｛ａ２ ，ａ３ ｝ ｕ２ ｛ａ２ ｝ ＡＴ ｛ａ３ ｝ ｛ａ３ ｝ ｕ３ ｛ａ２ ，ａ３ ｝ ｛ａ３ ｝ ＡＴ ＡＴ ｕ４ ｛ａ２ ，ａ３ ｝ ｛ａ３ ｝ ＡＴ ＡＴ ４）获取差别函数并进行简化 ＤＦ（Ｍ ［０，０．３］ ） ＝ （ａ２ ） ∧ （ａ３ ） ＤＦ（Ｍ ［０．８，１］ ） ＝ （ａ２ ） ∧ （ａ３ ） ５）通过结合律获取所有的广义分布保持约简 由计算得，［α，β］ ＝ ［０，０．３］时和［α，β］ ＝ ［０．８， １］时的所有广义分布保持约简均为｛ａ２ ，ａ３ ｝。 ４ 一些特殊情形下的讨论 值得注意的是，给定决策表 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ， ｆ），当 α 和 β 取某些特殊值时，广义分布保持约简可 以退化为目前已存在的一些约简，本节将根据 α 和 β 不同的特殊取值情况展开讨论，并给出相应的结 论。 其中，将 ＭＧＥＮ、ＭＰＯＳ以及 ＭＤＩＳ分别记为广义决 策可辨识矩阵、正域可辨识矩阵以及分布可辨识矩 阵，同时，将 Ｍ ＧＥＮ ｉｊ 、Ｍ ＰＯＳ ｉｊ 以及 Ｍ ＤＩＳ ｉｊ 分别记为对象 ｕｉ 和 ｕｊ 对应在广义决策可辨识矩阵、正域可辨识矩阵 以及分布可辨识矩阵的可辨识属性集，其中论域为 Ｕ＝ ｛ｕ１ ，ｕ２ ，…，ｕｎ ｝，ｉ，ｊ∈｛１，２，…，ｎ｝。 １）α＝ β ＝ ０ 时 当 α 和 β 取值均为 ０ 时，广义分布保持约简实 质是保证对于置信度为 ０ 的规则在约简前后的置信 ·３８０· 智 能 系 统 学 报 第 １２ 卷