第4期 钱进，等：面向成组对象集的增量式属性约简算法 ·501· 简算法是可行的。 一个过程，挖掘规则才是最终的输出。因此，充分利 表36个数据集特性 用先前约简中信息不仅能够快速得到约简，而且更 Table 3 A description of six data sets 容易地利用已有知识进行规则更新。本文所提出的 序号 数据集 对象数 属性个数类别数 面向成组对象集的增量式约简方法就是充分利用先 1 Chess 3196 36 2 前约简中信息来快速更新约简，不仅具有较高的约 2 mushroom 8124 22 2 简传承率，而且可以快速进行增量式学习，具有良好 3 nursery 12960 9 5 的实用性。作者下一步将利用Map Reduce进一步 4 Connect 67557 42 研究大规模数据集增量式属性约简方法。 5 Datasetl 200000 30 参考文献： 6 Dataset2 500000 30 9 [1]PAWLAK Z.Rough sets[J].International journal of com- 下面比较约简长度与约简的传承性。图2给出了 puter information sciences,1982.11(5):341-356. 6个数据集在不同增长比例下的约简长度。在4个数 [2]SKOWRON A,RAUSZER C.The discernibility matrices 据集上，约简不变，则只需要生成新增数据集的规则， and functions in information systems[M]//SLOWINSKI R. 原始规则集不必重新生成，而在另外两个数据集上，约 Intelligent Decision Support,Handbook of Applications and 简长度稍微增长，这主要因为新增对象与原始数据集 Advances of the Rough Sets Theory.Netherlands:Springer, 引起冲突，需要另外的属性集来细分原始对象，这时除 1992:311-362 了生成新规则集外，还需要修改部分原始规则。 [3]苗夺谦，胡桂荣.知识约简的一种启发式算法[J].计算 机研究与发展，1999.36(6)：681-684. MIAO Duoqian,HU Guirong.A heuristic algorithm for re- 35 20% 30 40% duction of knowledge []Journal of computer research and 60% 25 80% development,.1999.36(6):681-684. 100% [4]王国胤，于洪，杨大春.基于条件信息熵的决策表约简 15 [J].计算机学报，2002,25(7)：759-766. 10 5 WANG Guoyin,YU Hong,YANG Dachun.Decision table 2 reduction based on conditional information entropy[].Chi- 3 4 数据集 nese journal of computers,2002,25(7):759-766. [5]HU Feng,WANG Guoyin,HUANG Hai,et al.Incremental 图2约简长度比较 attribute reduction based on elementary sets[M]//SLEZAK Fig.2 Comparison of Reduct length D,WANG Guoyin,SZCZUKA M,et al.Proceedings of the 表4给出了约简的传承性。从表4可以看出， 10th International Conference on Rough Sets,Fuzzy Sets, 利用先前约简中信息所得到的新约简结果变化不 Data Mining,and Granular Computing.Berlin Heidelberg: 大，约简传承性较好。 Springer,2005:185-193. 表4约简传承性比较 [6]杨明.一种基于改进差别矩阵的属性约简增量式更新算 Table 4 Comparison of Reduct inheritance rate 号 法[J刀.计算机学报，2007,30(5)：815-822. YANG Ming.An incremental updating algorithm for attribute 数据集 20% 40% 60% 80% 100% reduction based on improved discernibility matrix[.Chi- Chess 100 100 95.45 95.45 95.45 nese journal of computers,2007,30(5)815-822. mushroom 100 100 100 100 100 [7]冯少荣，张东站.一种高效的增量式属性约简算法[J], nursery 100 100 100 100 100 控制与决策，2011,26(4)：495-500. Connect 100 100 100 100 100 FENG Shaorong,ZHANG Dongzhan.Effective incremental Datasetl 100 100 100 100 100 algorithm for attribute reduction[J].Control and decision, Dataset2 100 100 90.9 90.9 100 2011.26(4):495-500. [8]尹林子，阳春华，王晓丽，等.基于标记可辨识矩阵的 4 结论 增量式属性约简算法[J].自动化学报，2014,40(3)： 397-404. 在数据挖掘中，属性约简仅仅是数据预处理中 YIN Linzi,YANG Chunhua,WANG Xiaoli,et al.An in-简算法是可行的。 表 ３ ６ 个数据集特性 Ｔａｂｌｅ ３ Ａ ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｓｉｘ ｄａｔａ ｓｅｔｓ 序号 数据集 对象数 属性个数 类别数 １ Ｃｈｅｓｓ ３ １９６ ３６ ２ ２ ｍｕｓｈｒｏｏｍ ８ １２４ ２２ ２ ３ ｎｕｒｓｅｒｙ １２ ９６０ ９ ５ ４ Ｃｏｎｎｅｃｔ ６７ ５５７ ４２ ３ ５ Ｄａｔａｓｅｔ１ ２００ ０００ ３０ ５ ６ Ｄａｔａｓｅｔ２ ５００ ０００ ３０ ９ 下面比较约简长度与约简的传承性。 图 ２ 给出了 ６ 个数据集在不同增长比例下的约简长度。 在 ４ 个数 据集上，约简不变，则只需要生成新增数据集的规则， 原始规则集不必重新生成，而在另外两个数据集上，约 简长度稍微增长，这主要因为新增对象与原始数据集 引起冲突，需要另外的属性集来细分原始对象，这时除 了生成新规则集外，还需要修改部分原始规则。 图 ２ 约简长度比较 Ｆｉｇ．２ Ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｒｅｄｕｃｔ ｌｅｎｇｔｈ 表 ４ 给出了约简的传承性。 从表 ４ 可以看出， 利用先前约简中信息所得到的新约简结果变化不 大，约简传承性较好。 表 ４ 约简传承性比较 Ｔａｂｌｅ ４ Ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｒｅｄｕｃｔ ｉｎｈｅｒｉｔａｎｃｅ ｒａｔｅ ％ 数据集 ２０％ ４０％ ６０％ ８０％ １００％ Ｃｈｅｓｓ １００ １００ ９５．４５ ９５．４５ ９５．４５ ｍｕｓｈｒｏｏｍ １００ １００ １００ １００ １００ ｎｕｒｓｅｒｙ １００ １００ １００ １００ １００ Ｃｏｎｎｅｃｔ １００ １００ １００ １００ １００ Ｄａｔａｓｅｔ１ １００ １００ １００ １００ １００ Ｄａｔａｓｅｔ２ １００ １００ ９０．９ ９０．９ １００ ４ 结论 在数据挖掘中， 属性约简仅仅是数据预处理中 一个过程，挖掘规则才是最终的输出。 因此，充分利 用先前约简中信息不仅能够快速得到约简，而且更 容易地利用已有知识进行规则更新。 本文所提出的 面向成组对象集的增量式约简方法就是充分利用先 前约简中信息来快速更新约简，不仅具有较高的约 简传承率，而且可以快速进行增量式学习，具有良好 的实用性。 作者下一步将利用 Ｍａｐ Ｒｅｄｕｃｅ 进一步 研究大规模数据集增量式属性约简方法。 参考文献： ［１］ＰＡＷＬＡＫ Ｚ． Ｒｏｕｇｈ ｓｅｔｓ［ Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｃｏｍ⁃ ｐｕｔｅｒ ＆ ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， １９８２， １１（５）： ３４１－３５６． ［２］ ＳＫＯＷＲＯＮ Ａ， ＲＡＵＳＺＥＲ Ｃ． Ｔｈｅ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｃｅｓ ａｎｄ ｆｕｎｃｔｉｏｎｓ ｉｎ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ［Ｍ］ ／ ／ ＳＬＯＷＩＮＳＫＩ Ｒ． Ｉｎｔｅｌｌｉｇｅｎｔ Ｄｅｃｉｓｉｏｎ Ｓｕｐｐｏｒｔ， Ｈａｎｄｂｏｏｋ ｏｆ Ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ Ａｄｖａｎｃｅｓ ｏｆ ｔｈｅ Ｒｏｕｇｈ Ｓｅｔｓ Ｔｈｅｏｒｙ． Ｎｅｔｈｅｒｌａｎｄｓ： Ｓｐｒｉｎｇｅｒ， １９９２： ３１１－３６２． ［３］苗夺谦， 胡桂荣． 知识约简的一种启发式算法［ Ｊ］． 计算 机研究与发展， １９９９， ３６（６）： ６８１－６８４． ＭＩＡＯ Ｄｕｏｑｉａｎ， ＨＵ Ｇｕｉｒｏｎｇ． Ａ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｒｅ⁃ ｄｕｃｔｉｏｎ ｏｆ ｋｎｏｗｌｅｄｇｅ ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ｒｅｓｅａｒｃｈ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ， １９９９， ３６（６）： ６８１－６８４． ［４］王国胤， 于洪， 杨大春． 基于条件信息熵的决策表约简 ［Ｊ］． 计算机学报， ２００２， ２５（７）： ７５９－７６６． ＷＡＮＧ Ｇｕｏｙｉｎ， ＹＵ Ｈｏｎｇ， ＹＡＮＧ Ｄａｃｈｕｎ． Ｄｅｃｉｓｉｏｎ ｔａｂｌｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｃｏｎｄｉｔｉｏｎａｌ ｉｎｆｏｒｍａｔｉｏｎ ｅｎｔｒｏｐｙ ［Ｊ］． Ｃｈｉ⁃ ｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２００２， ２５（７）： ７５９－７６６． ［５］ＨＵ Ｆｅｎｇ， ＷＡＮＧ Ｇｕｏｙｉｎ， ＨＵＡＮＧ Ｈａｉ， ｅｔ ａｌ． Ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｅｌｅｍｅｎｔａｒｙ ｓｅｔｓ［Ｍ］ ／ ／ ＳＬＥＺＡＫ Ｄ， ＷＡＮＧ Ｇｕｏｙｉｎ， ＳＺＣＺＵＫＡ Ｍ， ｅｔ ａｌ． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １０ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｏｕｇｈ Ｓｅｔｓ， Ｆｕｚｚｙ Ｓｅｔｓ， Ｄａｔａ Ｍｉｎｉｎｇ， ａｎｄ Ｇｒａｎｕｌａｒ Ｃｏｍｐｕｔｉｎｇ． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ， ２００５： １８５－１９３． ［６］杨明． 一种基于改进差别矩阵的属性约简增量式更新算 法［Ｊ］． 计算机学报， ２００７， ３０（５）： ８１５－８２２． ＹＡＮＧ Ｍｉｎｇ． Ａｎ ｉｎｃｒｅｍｅｎｔａｌ ｕｐｄａｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ［ Ｊ］． Ｃｈｉ⁃ ｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２００７， ３０（５） ８１５－８２２． ［７］冯少荣， 张东站． 一种高效的增量式属性约简算法［ Ｊ］． 控制与决策， ２０１１， ２６（４）： ４９５－５００． ＦＥＮＧ Ｓｈａｏｒｏｎｇ， ＺＨＡＮＧ Ｄｏｎｇｚｈａｎ． Ｅｆｆｅｃｔｉｖｅ ｉｎｃｒｅｍｅｎｔａｌ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ［ Ｊ］． Ｃｏｎｔｒｏｌ ａｎｄ ｄｅｃｉｓｉｏｎ， ２０１１， ２６（４）： ４９５－５００． ［８］尹林子， 阳春华， 王晓丽， 等． 基于标记可辨识矩阵的 增量式属性约简算法［ Ｊ］． 自动化学报， ２０１４， ４０（ ３）： ３９７－４０４． ＹＩＮ Ｌｉｎｚｉ， ＹＡＮＧ Ｃｈｕｎｈｕａ， ＷＡＮＧ Ｘｉａｏｌｉ， ｅｔ ａｌ． Ａｎ ｉｎ⁃ 第 ４ 期 钱进，等：面向成组对象集的增量式属性约简算法 ·５０１·