·474· 智能系统学报 第13卷 2)根据每个对象对应的相容类，计算每个对象 性质3设区间值决策系统DS=(U,CUD,V,f), 相对于每一个决策类的概率分布(x)。 H=h1Vh2V.Vhm和K=k1 VkV...Vkn分别是分布 3)根据每个对象的概率分布，计算所对应的最 约简和最大分布约简结果，则在阈值α下，对于K中 大分布y(x)。 任意一个蕴含项k,H中存在一个蕴含项h,满足 4)根据每个对象的可信度不同构造最大分布 h2kjo 约简可辨识矩阵DMax。 S)由可辨识矩阵DMa计算最大分布约简可 3实验验证与分析 辨识函数f(C)ax。 本节对提出的最大分布约简算法进行实验验 6)利用分配率和吸收率将U转化为h(C)x, 证，实验包括两部分：1)比较最大分布约简方法和 hg(C)中每一个蕴含项为一个最大分布保持的约简。 算法2是通过可辨识矩阵求得区间值决策表的 其他约简方法的约简结果，验证了性质3的正确 所有最大分布保持约简，因此算法在最坏情况下的 性：2)比较了最大分布保持、分布保持和正域保持 时间复杂度为OC),C为条件属性的个数，IU为 3种约简算法的约简效率。采用UCI标准测试集进 对象的个数。 行实验。实验环境为PC机，操作系统为Windows 例4如表1所示的区间值决策系统，令 7旗舰版64位；内存为6.0 GB DDR3,CPU为Intel α=0.6，根据例2可知相似布尔矩阵以及相容类。 i5-3470。 计算决策属性D对U划分： 实验选取8组标准UCI数据集，对缺失数据通 U/D (D1.D2)=(x1.xs,x61.(x2,xx 过将对应属性下占多数属性值进行替换，对名词性 计算每个对象对应的概率分布： 数据采用{0,1}替换，对连续型数据采用等频分割 g6(x1)={1,0,26(2)={0,1, 的方法，所有数据预处理均在WEKA3.6进行，数据 e6()={2/3,1/31,e6(x)=(0,1, 集信息如表2所示，IUI表示对象数，AT表示条件属 e(xs)={(2/3,1/3,e(x6)=2/3,1/31。 性数，D表示决策属性将对象分类个数。 计算每个对象对应的最大分布： 表2UCI数据集信息 y2(x)={Dh,Y2()={D2l, Table 2 UCI data sets information Y2(3)={D,y2(xa)=(D2l, 数据集 10 JATI D ye5(xs)=(Dil,ye(x6)=(Do 计算最大分布约简可辨识矩阵： BLOGGER 100 4 ⊙ Fertility 100 a1,a2,a3,a4 0 0 a3,a4 0 Teaching Assistant DMPM(6.6)= 151 a1,a2,a3 0 as 0 Evaluation 0 a3,a40a30 ⊙ a3,a40 00 QualitativeBankruptcy 250 计算最大分布约简可辨识函数： User Knowledge 258 f86(C)Max(a1,2,,a4)=a3 Modeling 因此，最大分布保持约简结果为{a} Liverdisorders 345 例5如表1所示的区间值决策系统，令α分别 Auto MPG 398 为0.4,0.5,0.6,0.7，则分布保持约简结果为 h9(C)(a1,a2,a3,a4)=a1Va4 Mammographic Mass 961 h9(C)(a1,a2,a3,a4)=(a1Aa3)V(a2Aa3) 由于表格有限，表3~10中数据集名称均为相 h8(C)(a1,a2,a3,a4)=(a1Aa3)V(a2Aa3) h(C)(a,az,asa)=(aAas)v(aAas) 应数据集名称的缩写。 最大分布保持约简结果为 由于采用的UCI数据集都是单值数据，因此需 hp(C)Max(an,an,a.)=ava 将单值数据转换为区间值数据，单值数据转换为区 h (C)Ma(an,a,a.)=as 间值数据的方法在文献[19]中已经描述，先将该方 h0(C)Mx(a1,a2,a3,a4)= 法改进，引进阈值入，该值可调节振幅，即区间值的 h97(C)Mx(a1,a2,a3,a4)=a3 长度。µ α C (xi) 2) 根据每个对象对应的相容类，计算每个对象 相对于每一个决策类的概率分布 。 γ α C (xi) 3) 根据每个对象的概率分布，计算所对应的最 大分布 。 DMα DMax 4) 根据每个对象的可信度不同构造最大分布 约简可辨识矩阵 。 DMα DMax f α D (C)Max 5) 由可辨识矩阵 计算最大分布约简可 辨识函数 。 U h α D (C)Max h α D (C)Max 6) 利用分配率和吸收率将 转化为 ， 中每一个蕴含项为一个最大分布保持的约简。 O(|C| |U| 2 ) |C| |U| 算法 2 是通过可辨识矩阵求得区间值决策表的 所有最大分布保持约简，因此算法在最坏情况下的 时间复杂度为 ， 为条件属性的个数， 为 对象的个数。 α = 0.6 例 4 如表 1 所示的区间值决策系统，令 ，根据例 2 可知相似布尔矩阵以及相容类。 计算决策属性 D 对 U 划分： U/D = {D1 ,D2} = { {x1 , x5 , x6},{x2 , x3 , x4} } 。 计算每个对象对应的概率分布： µ 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}。 计算每个对象对应的最大分布： γ 0.6 C (x1) = {D1} γ 0.6 C ， (x2) = {D2}， γ 0.6 C (x3) = {D1} γ 0.6 C ， (x4) = {D2}， γ 0.6 C (x5) = {D1} γ 0.6 C ， (x6) = {D1}。 计算最大分布约简可辨识矩阵： DM0.6 DMax(6,6) =   Ø a1,a2,a3,a4 Ø Ø a3 ,a4 Ø a1 ,a2 ,a3 Ø a3 Ø Ø a3,a4 Ø a3 Ø Ø a3,a4 Ø a3 Ø Ø   计算最大分布约简可辨识函数： f 0.6 D (C)Max(¯a1,a¯ 2,a¯ 3,a¯ 4) = a3 因此，最大分布保持约简结果为{a3}。 α 0.4,0.5,0.6,0.7 例 5 如表 1 所示的区间值决策系统，令 分别 为 ，则分布保持约简结果为 h 0.4 D (C)(¯a1,a¯ 2,a¯ 3,a¯ 4) = a1 ∨a4 h 0.5 D (C)(¯a1,a¯ 2,a¯ 3,a¯ 4) = (a1 ∧a3)∨(a2 ∧a3) h 0.6 D (C)(¯a1,a¯ 2,a¯ 3,a¯ 4) = (a1 ∧a3)∨(a2 ∧a3) h 0.7 D (C)(¯a1,a¯ 2,a¯ 3,a¯ 4) = (a1 ∧a3)∨(a2 ∧a3) 最大分布保持约简结果为 h 0.4 D (C)Max(¯a1,a¯ 2,a¯ 3,a¯ 4) = a1 ∨a4 h 0.5 D (C)Max(¯a1,a¯ 2,a¯ 3,a¯ 4) = a3 h 0.6 D (C)Max(¯a1,a¯ 2,a¯ 3,a¯ 4) = a3 h 0.7 D (C)Max(¯a1,a¯ 2,a¯ 3,a¯ 4) = a3 DS = (U,C ∪ D,V, f) H = h1 ∨h2 ∨ ··· ∨hm K = k1 ∨k2 ∨ ··· ∨kn α K kj H hi hi ⊇ kj 性质 3 设区间值决策系统 ， 和 分别是分布 约简和最大分布约简结果，则在阈值 下，对于 中 任意一个蕴含项 ， 中存在一个蕴含项 满足 。 3 实验验证与分析 本节对提出的最大分布约简算法进行实验验 证，实验包括两部分：1) 比较最大分布约简方法和 其他约简方法的约简结果，验证了性质 3 的正确 性；2) 比较了最大分布保持、分布保持和正域保持 3 种约简算法的约简效率。采用 UCI 标准测试集进 行实验。实验环境为 PC 机，操作系统为 Windows 7 旗舰版 64 位；内存为 6.0 GB DDR3，CPU 为 Intel i5-3470。 |U| |D| 实验选取 8 组标准 UCI 数据集，对缺失数据通 过将对应属性下占多数属性值进行替换，对名词性 数据采用{0,1}替换，对连续型数据采用等频分割[19] 的方法，所有数据预处理均在 WEKA3.6 进行，数据 集信息如表 2 所示， 表示对象数，|AT|表示条件属 性数， 表示决策属性将对象分类个数。 表 2 UCI 数据集信息 Table 2 UCI data sets information 数据集 |U| |AT| |D| BLOGGER 100 4 2 Fertility 100 9 2 Teaching Assistant Evaluation 151 4 3 QualitativeBankruptcy 250 6 2 User Knowledge Modeling 258 4 4 Liverdisorders 345 6 2 Auto MPG 398 6 3 Mammographic Mass 961 4 2 由于表格有限，表 3～10 中数据集名称均为相 应数据集名称的缩写。 λ 由于采用的 UCI 数据集都是单值数据，因此需 将单值数据转换为区间值数据，单值数据转换为区 间值数据的方法在文献[19]中已经描述，先将该方 法改进，引进阈值 ，该值可调节振幅，即区间值的 长度。 ·474· 智 能 系 统 学 报 第 13 卷