第11卷第4期 智能系统学报 Vol.11 No.4 2016年8月 CAAI Transactions on Intelligent Systems Aug.2016 D0I:10.11992/is.201606005 网络出版地址：http://www.cnki.net/kcms/detail,/23.1538.TP.20160808.0830.008.html 面向成组对象集的增量式属性约简算法 钱进2，朱亚炎1 (1.江苏理工学院计算机工程学院，江苏常州213015：2.南京信息工程大学江苏省大数据分析技术重点实验室，江 苏南京210044) 摘要：现实世界中数据集都是动态变化的，非增量式属性约简方法从头重新计算原始数据集，而且未考虑先前约 简结果中的信息，将耗费大量的时间和空间。为此，讨论了动态数据环境下约简的不变性，提出了一种面向成组对 象集的增量式属性约简算法，利用先前约简中信息来快速获取强传承性的约简，从而提高增量式学习算法效率。最 后，将该算法与非增量式约简方法和面向单个对象的增量式约简方法在UC数据集和人工数据集上进行了相关比 较。实验结果表明，面向成组对象的增量式属性约简算法能够快速处理动态数据，具有较好的约简传承性。 关键词：粗糙集：属性约简：成组对象集：约简传承性：增量式学习 中图分类号：TP181文献标志码：A文章编号：1673-4785(2016)04-0496-07 中文引用格式：钱进，朱亚炎.面向成组对象集的增量式属性约简算法[J].智能系统学报，2016,11(4)：496-502. 英文引用格式：QIAN Jin,ZHU Yayan.An incremental attribute reduction algorithm for group objects[J】.CAAI Transactions on Intelligent Systems,2016,11(4):496-502. An incremental attribute reduction algorithm for group objects QIAN Jin'2,ZHU Yayan' (1.School of Computer Engineering,Jiangsu University of Technology,Changzhou 213015,China;2.Jiangsu Key Laboratory of Big Data Analysis Technology /B-DAT,Nanjing University of Information Science Technology,Nanjing 210044,China) Abstract:Real-world datasets change in size dynamically.Non-incremental attribute reduction methods usually need to re-compute source data when obtaining a new reduction without considering the information in the existing reduc- tion,which consumes a great deal of computational time and storage space.Therefore,in this paper,some reduc- tion invariance properties for dynamic datasets are discussed.An incremental attribute reduction algorithm for group objects using the previous reduction is proposed to quickly update a reduction with high inheritance rate and thus improve the efficiency of incremental learning.Finally,the incremental approach proposed is compared with an ex- isting incremental attribute reduction algorithm for a single object,the non-incremental attribute reduction algo- rithms on the UCI,and synthetic datasets.Experimental results show that this incremental attribute reduction algo- rithm for group objects can deal with dynamic data rapidly,as it has better inheritance of reduction. Keywords:rough set theory;attribute Reduction;group objects;inheritance rate of Reduct;incremental learning 属性约简是Rough集理论中的核心问题之一，也是知识获取的关键步骤。目前，许多学者已提出 收稿日期：2014-06-02.网络出版日期：2014-08-08. 了一些有效的属性约简算法[1-)，如基于正区域的 基金项目：江苏省自然科学基金项目(BK20141152);教育部人文社会属性约简算法、基于差别矩阵的属性约简算法、基于 科学研究青年基金项目(15YCZH129):江苏省青蓝工程项 目：江苏省大数据分析技术重点实验室开放基金项目 信息嫡的属性约简算法等，但这些算法都是针对静 (KXK1402):江苏理工学院校级大学生创新项目 态的决策表，不适合处理动态的信息系统。现实世 (KYX15017). 通信作者：钱进.E-mail:qjqjlqyf(@163.com. 界是不断变化的，数据会源源不断地添加到原始决第 １１ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．４ ２０１６ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０６００５ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０８０８．０８３０．００８．ｈｔｍｌ 面向成组对象集的增量式属性约简算法 钱进１，２ ，朱亚炎１ （１．江苏理工学院 计算机工程学院，江苏 常州 ２１３０１５； ２． 南京信息工程大学 江苏省大数据分析技术重点实验室，江 苏 南京 ２１００４４） 摘 要：现实世界中数据集都是动态变化的，非增量式属性约简方法从头重新计算原始数据集，而且未考虑先前约 简结果中的信息，将耗费大量的时间和空间。 为此，讨论了动态数据环境下约简的不变性，提出了一种面向成组对 象集的增量式属性约简算法，利用先前约简中信息来快速获取强传承性的约简，从而提高增量式学习算法效率。 最 后，将该算法与非增量式约简方法和面向单个对象的增量式约简方法在 ＵＣＩ 数据集和人工数据集上进行了相关比 较。 实验结果表明，面向成组对象的增量式属性约简算法能够快速处理动态数据，具有较好的约简传承性。 关键词：粗糙集；属性约简；成组对象集；约简传承性；增量式学习 中图分类号： ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１６）０４－０４９６－０７ 中文引用格式：钱进，朱亚炎． 面向成组对象集的增量式属性约简算法［Ｊ］． 智能系统学报， ２０１６， １１（４）： ４９６－５０２． 英文引用格式：ＱＩＡＮ Ｊｉｎ， ＺＨＵ Ｙａｙａｎ． Ａｎ ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｇｒｏｕｐ ｏｂｊｅｃｔｓ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６， １１（４）： ４９６－５０２． Ａｎ ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｇｒｏｕｐ ｏｂｊｅｃｔｓ ＱＩＡＮ Ｊｉｎ １，２ ， ＺＨＵ Ｙａｙａｎ １ （１． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｊｉａｎｇｓｕ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｃｈａｎｇｚｈｏｕ ２１３０１５， Ｃｈｉｎａ； ２． Ｊｉａｎｇｓｕ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｂｉｇ Ｄａｔａ Ａｎａｌｙｓｉｓ Ｔｅｃｈｎｏｌｏｇｙ ／ Ｂ⁃ＤＡＴ， Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ＆ Ｔｅｃｈｎｏｌｏｇｙ， Ｎａｎｊｉｎｇ ２１００４４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｒｅａｌ⁃ｗｏｒｌｄ ｄａｔａｓｅｔｓ ｃｈａｎｇｅ ｉｎ ｓｉｚｅ ｄｙｎａｍｉｃａｌｌｙ． Ｎｏｎ⁃ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｍｅｔｈｏｄｓ ｕｓｕａｌｌｙ ｎｅｅｄ ｔｏ ｒｅ⁃ｃｏｍｐｕｔｅ ｓｏｕｒｃｅ ｄａｔａ ｗｈｅｎ ｏｂｔａｉｎｉｎｇ ａ ｎｅｗ ｒｅｄｕｃｔｉｏｎ ｗｉｔｈｏｕｔ ｃｏｎｓｉｄｅｒｉｎｇ ｔｈｅ ｉｎｆｏｒｍａｔｉｏｎ ｉｎ ｔｈｅ ｅｘｉｓｔｉｎｇ ｒｅｄｕｃ⁃ ｔｉｏｎ， ｗｈｉｃｈ ｃｏｎｓｕｍｅｓ ａ ｇｒｅａｔ ｄｅａｌ ｏｆ ｃｏｍｐｕｔａｔｉｏｎａｌ ｔｉｍｅ ａｎｄ ｓｔｏｒａｇｅ ｓｐａｃｅ． Ｔｈｅｒｅｆｏｒｅ， ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｓｏｍｅ ｒｅｄｕｃ⁃ ｔｉｏｎ ｉｎｖａｒｉａｎｃｅ ｐｒｏｐｅｒｔｉｅｓ ｆｏｒ ｄｙｎａｍｉｃ ｄａｔａｓｅｔｓ ａｒｅ ｄｉｓｃｕｓｓｅｄ． Ａｎ ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｇｒｏｕｐ ｏｂｊｅｃｔｓ ｕｓｉｎｇ ｔｈｅ ｐｒｅｖｉｏｕｓ ｒｅｄｕｃｔｉｏｎ ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｑｕｉｃｋｌｙ ｕｐｄａｔｅ ａ ｒｅｄｕｃｔｉｏｎ ｗｉｔｈ ｈｉｇｈ ｉｎｈｅｒｉｔａｎｃｅ ｒａｔｅ ａｎｄ ｔｈｕｓ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｉｎｃｒｅｍｅｎｔａｌ ｌｅａｒｎｉｎｇ． Ｆｉｎａｌｌｙ， ｔｈｅ ｉｎｃｒｅｍｅｎｔａｌ ａｐｐｒｏａｃｈ ｐｒｏｐｏｓｅｄ ｉｓ ｃｏｍｐａｒｅｄ ｗｉｔｈ ａｎ ｅｘ⁃ ｉｓｔｉｎｇ ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａ ｓｉｎｇｌｅ ｏｂｊｅｃｔ， ｔｈｅ ｎｏｎ⁃ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏ⁃ ｒｉｔｈｍｓ ｏｎ ｔｈｅ ＵＣＩ， ａｎｄ ｓｙｎｔｈｅｔｉｃ ｄａｔａｓｅｔｓ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｉｓ ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏ⁃ ｒｉｔｈｍ ｆｏｒ ｇｒｏｕｐ ｏｂｊｅｃｔｓ ｃａｎ ｄｅａｌ ｗｉｔｈ ｄｙｎａｍｉｃ ｄａｔａ ｒａｐｉｄｌｙ， ａｓ ｉｔ ｈａｓ ｂｅｔｔｅｒ ｉｎｈｅｒｉｔａｎｃｅ ｏｆ ｒｅｄｕｃｔｉｏｎ． Ｋｅｙｗｏｒｄｓ： ｒｏｕｇｈ ｓｅｔ ｔｈｅｏｒｙ； ａｔｔｒｉｂｕｔｅ Ｒｅｄｕｃｔｉｏｎ； ｇｒｏｕｐ ｏｂｊｅｃｔｓ； ｉｎｈｅｒｉｔａｎｃｅ ｒａｔｅ ｏｆ Ｒｅｄｕｃｔ； ｉｎｃｒｅｍｅｎｔａｌ ｌｅａｒｎｉｎｇ 收稿日期：２０１４－０６－０２． 网络出版日期：２０１４－０８－０８． 基金项目：江苏省自然科学基金项目（ＢＫ２０１４１１５２）；教育部人文社会 科学研究青年基金项目（ １５ＹＪＣＺＨ１２９）；江苏省青蓝工程项 目；江苏 省 大 数 据 分 析 技 术 重 点 实 验 室 开 放 基 金 项 目 （ＫＸＫ１４０２ ）； 江 苏 理 工 学 院 校 级 大 学 生 创 新 项 目 （ＫＹＸ１５０１７）． 通信作者：钱进． Ｅ⁃ｍａｉｌ：ｑｊｑｊｌｑｙｆ＠ １６３．ｃｏｍ． 属性约简是 Ｒｏｕｇｈ 集理论中的核心问题之一， 也是知识获取的关键步骤。 目前，许多学者已提出 了一些有效的属性约简算法［１－４］ ，如基于正区域的 属性约简算法、基于差别矩阵的属性约简算法、基于 信息熵的属性约简算法等，但这些算法都是针对静 态的决策表，不适合处理动态的信息系统。 现实世 界是不断变化的，数据会源源不断地添加到原始决