第2期 杨成东，等：综合属性选择和删除的属性约简方法 185. 6)compute the attribute frequency of a Ym(D）=Yoi-a(D), 7)end for 那么这样的属性a在14)~19)的循环中被删除了， 8)select a with the largest attribute frequency,then 即a年red. red =red Uas; 因此，假设不成立，red是独立的.所以，red是 9)set the elements of M including a:with 0. 约简 10)ifM=0, 例2继续使用例1，利用算法2，可以得到约 11)retumn red; 简red={b,c.因此，与基于辨识矩阵属性约简方法 12 else 相比，该方法能够有效地获得约简。 13)tur to 5); 14)end if 4实验与分析 15)for each a∈red, 用6个UCI标准数据集来验证本文提出的方法 16)if yrod-a(D)=Yc(D), 的实用性和有效性，如表2所示.表3对经典方法选 17)red red-a; 择的属性序列和本文提出的方法选择的属性序列进 18)end if 行了比较.利用经典方法得到的6个数据集中， 19)end for Heart、Lymph、Soybean有3个不是约简.而本文方法 20)return red 得到的都是约简，有效地解决了经典方法得不到约 算法2比算法1多了一个循环0(1U11C1),由 简的问题. 于这2个循环是并列的，那么总的时间复杂度为 表2UCI标准数据集 0(1U11C12)+0(1U11C1)=0(1U11C2),因此算 Table 2 UCI standard datasets 法2与算法1具有相同的时间复杂度，本文提出的 数据集 简称 对象个数属性个数 算法的时间复杂度不会增加. Car Evaluation Car 172 7 下面证明算法2选择的属性子集是约简，既保 Spect Heart Heart 267 23 持了信息，又有效地消除了冗余信息. Tic-Tac-Toe Tic 958 10 定理2给定决策系统S=(U,CUD,V,),经 过算法2后，得到red,那么red是约简. Lymphography Lymphography 148 19 证明类似于定理1的证明，可以得到 Soybean Large) Soybean 683 36 Yrd(D)=Yc(D). Z00 Z00 101 17 另一方面，采用反证法证明red是独立的.假设red 不是独立的，那么存在a∈red,满足 表3与经典方法的比较 Table 3 Comparison of UCI standard datasets and the classical approaches 原始 经典方法 本文提出的方法 数据集 属性个数 选择序列 选择个数 选择序列 选择个数 Car 7 {2,1,4,6,5,3 6 12,1,4,6,5,3 Heart 23 f16,22,21,20,19,1,13, 15 {16,22,21,20,19,1,13,3,5,9,14,12 12 3,8,5,9,10,14,4,12 Lymph 10 {18,14,13,12,1,15,2,10 8 {18,14,13,12,15,2,10 {6,5,7,9,16,4,10,1,22 Sovbean 19 16 {6,5,7,9,16,4,10,1,22,29,15,8} 12 29,15,28,13,21,14,8 Tic 36 {5,2,46,8,1,3,7} {5,2,4,6,8,1,3,7 8 Z00 17 16,13,4,8,3} 6 16,13,4,8,3} 6 平均属性个数18.7 9.8 8.5