.382. 智能系统学报 第12卷 例2表1所示决策表，论域U={u1,山2，u3, 一个广义分布保持约简，进一步，若给定置信度区 u4},AT={a1,a2,a3,a,}为条件属性集，D={d}为决 间[a',B],且满足[a',B]≤[a,B],则3A'≤A,使 策属性。由 得A'是置信度区间[α'，B]下的一个广义分布保持 U/AT={E1,E2,E3} 约简，且满足A'二A。其中，a和B满足(a=0∧B∈ E1={u1} [0,1])或(a∈[0,1]ΛB=1)。 E2={u2} 证明由已知条件得，[a',B]C[a,B],Hu∈ E2={山3，u4} U,有Ya剧(u)=Ya](u)。则u∈U,必然有 U/D={D1,D2,D3} Ye(u)=Yg(u),故A是决策表在置信度区 D1={u1} 间[α'，B]下的一个广义分布协调集。假设A是决 D2={42,u4} 策表在置信度区间[α'，B]下的一个广义分布约简， D3={u3} 则有A'CA:反之，必然3A'CA,使得Y0F](u)= POST(D)=u1,u2 Ya](u),故3A'CA,使得A'≤A成立，证毕。 8Ar(u1)={0} 5实验分析 8Ar(u2)={1} 8Ar(u3)={1,2 本节采用4个UCI数据集进行实验，数据集信 8Ar(u4)={1,2 息如表5所示，其中，|U川表示数据集的样本数， um(u1)=(1,0,0) |AT表示数据集的特征数，|D表示分类数。对于 uA(2)=(0,1,0) 数据集的预处理，处理策略如下：缺失特征值通过 r(u3)=(0,0.5,0.5) 用该缺失特征值所对应特征下的多数特征值进行 r(u4）=(0,0.5,0.5) 填充，连续型特征进行等频离散化，名词性特征值 求得正域保持约简为a2,a3},广义决策保持约 用整数进行替换，所有数据集的预处理均在Weka 简为{a2,a3},分布保持约简为{a2,a3}。 3.6下进行。实验环境如下：Windows7旗舰版32位 因此，当a=B=1时，可得：Y(1)={(0,1)}, 操作系统，intel Pentium G640C处理器，主频 Y(42）={(1,1)},Y(4）=⑦， 2.8GHz,内存6.0GB,所有算法均采用MATLAB Y(u)=0。 R2010h编写实现。 据此构造广义分布差别矩阵，如表4所示。 表5UCI数据集信息 表4广义分布差别矩阵 Table 5 Information of UCI data sets Table 4 Generalized distribution discernibility matrix 数据集 IUI ATI DI Mu. 42 Haberman's Survival 306 3 2 AT {a2} {a2,a3 {a2,a3 Blood Transfusion Service Center 748 2 {a2} AT {a3} {a3} Stone Flakes 79 3 us {a2,a3} {a3} AT AT Airfoil Self-Noise 1503 5 16 4 {a2,a3} {a} AT AT 注：BTSC为数据集Blood Transfusion Service Center的 由广义分布差别矩阵可得所有的广义分布保 缩写 持约简为{a2,a3},与正域约简一致。同理，a=B=0 实验分为两部分。第1部分验证置信度区间分 时的广义分布保持约简为a2,a3},与广义决策约简 别为[1.0,1.0]、[0.0,0.0]以及[0.0,1.0]时，广义分 一致；a=0,B=1时的广义分布保持约简为{a2, 布保持约简可分别退化为正域保持约简、广义决策 a3},与分布约简一致。 保持约简以及分布约简，同时，也可验证广义分布 由定理4~6可得如下结论。 保持约简算法的正确性：第2部分验证在较小的置 推论1设DT=(U,ATUD,V,f),置信度区间 信度区间下求得的广义分布保持约简是在较大的 为[a,B],VACAT,且A是置信度区间[a,B]下的 置信度区间下求得的广义分布保持约简的子集。例 ２ 表 １ 所示决策表，论域 Ｕ ＝ ｛ ｕ１ ，ｕ２ ，ｕ３ ， ｕ４ ｝，ＡＴ ＝ ｛ａ１ ，ａ２ ，ａ３ ，ａ４ ｝为条件属性集，Ｄ＝ ｛ｄ｝为决 策属性。 由 Ｕ／ ＡＴ ＝ ｛Ｅ１ ，Ｅ２ ，Ｅ３ ｝ Ｅ１ ＝ ｛ｕ１ ｝ Ｅ２ ＝ ｛ｕ２ ｝ Ｅ２ ＝ ｛ｕ３ ，ｕ４ ｝ Ｕ／ Ｄ＝ ｛Ｄ１ ，Ｄ２ ，Ｄ３ ｝ Ｄ１ ＝ ｛ｕ１ ｝ Ｄ２ ＝ ｛ｕ２ ，ｕ４ ｝ Ｄ３ ＝ ｛ｕ３ ｝ ＰＯＳＡＴ（Ｄ）＝ ｛ｕ１ ，ｕ２ ｝ δＡＴ（ｕ１ ）＝ ｛０｝ δＡＴ（ｕ２ ）＝ ｛１｝ δＡＴ（ｕ３ ）＝ ｛１，２｝ δＡＴ（ｕ４ ）＝ ｛１，２｝ μＡＴ（ｕ１ ）＝ （１，０，０） μＡＴ（ｕ２ ）＝ （０，１，０） μＡＴ（ｕ３ ）＝ （０，０．５，０．５） μＡＴ（ｕ４ ）＝ （０，０．５，０．５） 求得正域保持约简为｛ａ２ ，ａ３ ｝，广义决策保持约 简为｛ａ２ ，ａ３ ｝，分布保持约简为｛ａ２ ，ａ３ ｝。 因此，当 α＝β ＝ １ 时，可得：Υ ［１，１］ ＡＴ （ｕ１ ）＝ ｛〈０，１〉｝， Υ ［１，１］ ＡＴ （ ｕ２ ） ＝ ｛〈 １， １ 〉｝， Υ ［１，１］ ＡＴ （ ｕ３ ） ＝ ⌀， Υ ［１，１］ ＡＴ （ｕ４ ）＝ ⌀。 据此构造广义分布差别矩阵，如表 ４ 所示。 表 ４ 广义分布差别矩阵 Ｔａｂｌｅ ４ Ｇｅｎｅｒａｌｉｚｅｄ ｄｉｓｔｒｉｂｕｔｉｏｎ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ Ｍ ［１，１］ ｕ１ ｕ２ ｕ３ ｕ４ ｕ１ ＡＴ ｛ａ２ ｝ ｛ａ２ ，ａ３ ｝ ｛ａ２ ，ａ３ ｝ ｕ２ ｛ａ２ ｝ ＡＴ ｛ａ３ ｝ ｛ａ３ ｝ ｕ３ ｛ａ２ ，ａ３ ｝ ｛ａ３ ｝ ＡＴ ＡＴ ｕ４ ｛ａ２ ，ａ３ ｝ ｛ａ３ ｝ ＡＴ ＡＴ 由广义分布差别矩阵可得所有的广义分布保 持约简为｛ａ２ ，ａ３ ｝，与正域约简一致。 同理，α ＝ β ＝ ０ 时的广义分布保持约简为｛ａ２ ，ａ３ ｝，与广义决策约简 一致；α ＝ ０， β ＝ １ 时的广义分布保持约简为｛ ａ２ ， ａ３ ｝，与分布约简一致。 由定理 ４～６ 可得如下结论。 推论 １ 设 ＤＴ ＝ （Ｕ，ＡＴ∪Ｄ，Ｖ，ｆ ），置信度区间 为［α，β］，∀Ａ⊆ＡＴ，且 Ａ 是置信度区间［α，β］下的 一个广义分布保持约简，进一步，若给定置信度区 间［α′，β′］，且满足［α′，β′］⊆［α，β］，则∃Ａ′⊆Ａ，使 得 Ａ′是置信度区间［α′，β′］下的一个广义分布保持 约简，且满足 Ａ′⊆Ａ。 其中，α 和 β 满足（α ＝ ０∧β∈ ［０，１］）或（α∈［０，１］∧β ＝ １）。 证明 由已知条件得，［α′，β′］⊆［α，β］，∀ｕ∈ Ｕ，有 Υ ［α，β］ Ａ （ ｕ） ＝ Υ ［α，β］ ＡＴ （ ｕ）。 则 ∀ｕ ∈ Ｕ， 必然有 Υ ［α′，β′］ Ａ （ｕ）＝ Υ ［α′，β′］ ＡＴ （ ｕ），故 Ａ 是决策表在置信度区 间［α′，β′］下的一个广义分布协调集。 假设 Ａ 是决 策表在置信度区间［α′，β′］下的一个广义分布约简， 则有 Ａ′⊆Ａ；反之，必然∃Ａ′⊂Ａ，使得 Υ ［α′，β′］ Ａ′ （ ｕ） ＝ Υ ［α′，β′］ Ａ （ｕ），故∃Ａ′⊆Ａ，使得 Ａ′⊆Ａ 成立，证毕。 ５ 实验分析 本节采用 ４ 个 ＵＣＩ 数据集进行实验，数据集信 息如表 ５ 所示，其中， Ｕ 表示数据集的样本数， ＡＴ 表示数据集的特征数， Ｄ 表示分类数。 对于 数据集的预处理，处理策略如下：缺失特征值通过 用该缺失特征值所对应特征下的多数特征值进行 填充，连续型特征进行等频离散化，名词性特征值 用整数进行替换，所有数据集的预处理均在 Ｗｅｋａ ３．６下进行。 实验环境如下：Ｗｉｎｄｏｗｓ ７ 旗舰版 ３２ 位 操 作 系 统， Ｉｎｔｅｌ Ｐｅｎｔｉｕｍ Ｇ６４０Ｃ 处 理 器， 主 频 ２．８ ＧＨｚ，内 存 ６．０ ＧＢ， 所 有 算 法 均 采 用 ＭＡＴＬＡＢ Ｒ２０１０ｂ 编写实现。 表 ５ ＵＣＩ 数据集信息 Ｔａｂｌｅ ５ Ｉｎｆｏｒｍａｔｉｏｎ ｏｆ ＵＣＩ ｄａｔａ ｓｅｔｓ 数据集 Ｕ ＡＴ Ｄ Ｈａｂｅｒｍａｎ’ｓ Ｓｕｒｖｉｖａｌ ３０６ ３ ２ Ｂｌｏｏｄ Ｔｒａｎｓｆｕｓｉｏｎ Ｓｅｒｖｉｃｅ Ｃｅｎｔｅｒ ７４８ ４ ２ Ｓｔｏｎｅ Ｆｌａｋｅｓ ７９ ７ ３ Ａｉｒｆｏｉｌ Ｓｅｌｆ⁃Ｎｏｉｓｅ １５０３ ５ １６ 注：ＢＴＳＣ 为数据集 Ｂｌｏｏｄ Ｔｒａｎｓｆｕｓｉｏｎ Ｓｅｒｖｉｃｅ Ｃｅｎｔｅｒ 的 缩写 实验分为两部分。 第 １ 部分验证置信度区间分 别为［１．０，１．０］、［０．０，０．０］以及［０．０，１．０］时，广义分 布保持约简可分别退化为正域保持约简、广义决策 保持约简以及分布约简，同时，也可验证广义分布 保持约简算法的正确性；第 ２ 部分验证在较小的置 信度区间下求得的广义分布保持约简是在较大的 置信度区间下求得的广义分布保持约简的子集。 ·３８２· 智 能 系 统 学 报 第 １２ 卷