第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. 界是不断变化的，数据会源源不断地添加到原始决
第 １１ 卷第 ４ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．４ ２０１６ 年 ８ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｕｇ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０６００５ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１６０８０８．０８３０．００８．ｈｔｍｌ 面向成组对象集的增量式属性约简算法 钱进１，２ ，朱亚炎１ （１．江苏理工学院 计算机工程学院，江苏 常州 ２１３０１５； ２． 南京信息工程大学 江苏省大数据分析技术重点实验室，江 苏 南京 ２１００４４） 摘 要：现实世界中数据集都是动态变化的，非增量式属性约简方法从头重新计算原始数据集，而且未考虑先前约 简结果中的信息，将耗费大量的时间和空间。 为此，讨论了动态数据环境下约简的不变性，提出了一种面向成组对 象集的增量式属性约简算法，利用先前约简中信息来快速获取强传承性的约简，从而提高增量式学习算法效率。 最 后，将该算法与非增量式约简方法和面向单个对象的增量式约简方法在 ＵＣＩ 数据集和人工数据集上进行了相关比 较。 实验结果表明，面向成组对象的增量式属性约简算法能够快速处理动态数据，具有较好的约简传承性。 关键词：粗糙集；属性约简；成组对象集；约简传承性；增量式学习 中图分类号： ＴＰ１８１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１６）０４－０４９６－０７ 中文引用格式：钱进，朱亚炎． 面向成组对象集的增量式属性约简算法［Ｊ］． 智能系统学报， ２０１６， １１（４）： ４９６－５０２． 英文引用格式：ＱＩＡＮ Ｊｉｎ， ＺＨＵ Ｙａｙａｎ． Ａｎ ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｇｒｏｕｐ ｏｂｊｅｃｔｓ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６， １１（４）： ４９６－５０２． Ａｎ ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｇｒｏｕｐ ｏｂｊｅｃｔｓ ＱＩＡＮ Ｊｉｎ １，２ ， ＺＨＵ Ｙａｙａｎ １ （１． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｊｉａｎｇｓｕ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｃｈａｎｇｚｈｏｕ ２１３０１５， Ｃｈｉｎａ； ２． Ｊｉａｎｇｓｕ Ｋｅｙ Ｌａｂｏｒａｔｏｒｙ ｏｆ Ｂｉｇ Ｄａｔａ Ａｎａｌｙｓｉｓ Ｔｅｃｈｎｏｌｏｇｙ ／ Ｂ⁃ＤＡＴ， Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ＆ Ｔｅｃｈｎｏｌｏｇｙ， Ｎａｎｊｉｎｇ ２１００４４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｒｅａｌ⁃ｗｏｒｌｄ ｄａｔａｓｅｔｓ ｃｈａｎｇｅ ｉｎ ｓｉｚｅ ｄｙｎａｍｉｃａｌｌｙ． Ｎｏｎ⁃ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｍｅｔｈｏｄｓ ｕｓｕａｌｌｙ ｎｅｅｄ ｔｏ ｒｅ⁃ｃｏｍｐｕｔｅ ｓｏｕｒｃｅ ｄａｔａ ｗｈｅｎ ｏｂｔａｉｎｉｎｇ ａ ｎｅｗ ｒｅｄｕｃｔｉｏｎ ｗｉｔｈｏｕｔ ｃｏｎｓｉｄｅｒｉｎｇ ｔｈｅ ｉｎｆｏｒｍａｔｉｏｎ ｉｎ ｔｈｅ ｅｘｉｓｔｉｎｇ ｒｅｄｕｃ⁃ ｔｉｏｎ， ｗｈｉｃｈ ｃｏｎｓｕｍｅｓ ａ ｇｒｅａｔ ｄｅａｌ ｏｆ ｃｏｍｐｕｔａｔｉｏｎａｌ ｔｉｍｅ ａｎｄ ｓｔｏｒａｇｅ ｓｐａｃｅ． Ｔｈｅｒｅｆｏｒｅ， ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｓｏｍｅ ｒｅｄｕｃ⁃ ｔｉｏｎ ｉｎｖａｒｉａｎｃｅ ｐｒｏｐｅｒｔｉｅｓ ｆｏｒ ｄｙｎａｍｉｃ ｄａｔａｓｅｔｓ ａｒｅ ｄｉｓｃｕｓｓｅｄ． Ａｎ ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｇｒｏｕｐ ｏｂｊｅｃｔｓ ｕｓｉｎｇ ｔｈｅ ｐｒｅｖｉｏｕｓ ｒｅｄｕｃｔｉｏｎ ｉｓ ｐｒｏｐｏｓｅｄ ｔｏ ｑｕｉｃｋｌｙ ｕｐｄａｔｅ ａ ｒｅｄｕｃｔｉｏｎ ｗｉｔｈ ｈｉｇｈ ｉｎｈｅｒｉｔａｎｃｅ ｒａｔｅ ａｎｄ ｔｈｕｓ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｉｎｃｒｅｍｅｎｔａｌ ｌｅａｒｎｉｎｇ． Ｆｉｎａｌｌｙ， ｔｈｅ ｉｎｃｒｅｍｅｎｔａｌ ａｐｐｒｏａｃｈ ｐｒｏｐｏｓｅｄ ｉｓ ｃｏｍｐａｒｅｄ ｗｉｔｈ ａｎ ｅｘ⁃ ｉｓｔｉｎｇ ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａ ｓｉｎｇｌｅ ｏｂｊｅｃｔ， ｔｈｅ ｎｏｎ⁃ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏ⁃ ｒｉｔｈｍｓ ｏｎ ｔｈｅ ＵＣＩ， ａｎｄ ｓｙｎｔｈｅｔｉｃ ｄａｔａｓｅｔｓ． Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈａｔ ｔｈｉｓ ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏ⁃ ｒｉｔｈｍ ｆｏｒ ｇｒｏｕｐ ｏｂｊｅｃｔｓ ｃａｎ ｄｅａｌ ｗｉｔｈ ｄｙｎａｍｉｃ ｄａｔａ ｒａｐｉｄｌｙ， ａｓ ｉｔ ｈａｓ ｂｅｔｔｅｒ ｉｎｈｅｒｉｔａｎｃｅ ｏｆ ｒｅｄｕｃｔｉｏｎ． Ｋｅｙｗｏｒｄｓ： ｒｏｕｇｈ ｓｅｔ ｔｈｅｏｒｙ； ａｔｔｒｉｂｕｔｅ Ｒｅｄｕｃｔｉｏｎ； ｇｒｏｕｐ ｏｂｊｅｃｔｓ； ｉｎｈｅｒｉｔａｎｃｅ ｒａｔｅ ｏｆ Ｒｅｄｕｃｔ； ｉｎｃｒｅｍｅｎｔａｌ ｌｅａｒｎｉｎｇ 收稿日期：２０１４－０６－０２． 网络出版日期：２０１４－０８－０８． 基金项目：江苏省自然科学基金项目（ＢＫ２０１４１１５２）；教育部人文社会 科学研究青年基金项目（ １５ＹＪＣＺＨ１２９）；江苏省青蓝工程项 目；江苏 省 大 数 据 分 析 技 术 重 点 实 验 室 开 放 基 金 项 目 （ＫＸＫ１４０２ ）； 江 苏 理 工 学 院 校 级 大 学 生 创 新 项 目 （ＫＹＸ１５０１７）． 通信作者：钱进． Ｅ⁃ｍａｉｌ：ｑｊｑｊｌｑｙｆ＠ １６３．ｃｏｍ． 属性约简是 Ｒｏｕｇｈ 集理论中的核心问题之一， 也是知识获取的关键步骤。 目前，许多学者已提出 了一些有效的属性约简算法［１－４］ ，如基于正区域的 属性约简算法、基于差别矩阵的属性约简算法、基于 信息熵的属性约简算法等，但这些算法都是针对静 态的决策表，不适合处理动态的信息系统。 现实世 界是不断变化的，数据会源源不断地添加到原始决
第4期 钱进，等：面向成组对象集的增量式属性约简算法 .497. 策表中，一般不希望将原有的决策表和新产生的增 IND(R)表示，简记为U/R。U/R中的任何元素 量数据整合成一个新的决策表进行属性约简，因为 [x]R={ylHa∈R,f(x,a)=f(y,a)}称为等价 这样会对原有数据不断地进行重复的计算。因此， 类。不失一般性，假设决策表$仅有一个决策属性 如何利用原决策表中所含的信息并结合增量数据来 D={d},其决策属性值映射为1,2，…，k,由D导 进行属性约简成为粗糙集理论新的挑战。 出的U上划分记为U/D={D,D2,…,D},其 数据的动态变化主要有3种情况：1)属性集保 中，D={x∈Ulf(x,D)=i},i=1,2,…,k。 持不变而对象不断增加5$】：2)对象集保持不变而 定义2在决策表S=〈U,CUD,V)中，对 属性集不断增加：3)对象集和属性集同时增 于每个决策类D:∈U/D和不可区分关系ACC,D: 加。本文着重研究第1种情况的增量式属性约 的下近似集与上近似集分别可以由A的基本集定义 简问题，尤其研究适合大规模数据集的约简问题。 如下： 文献[5]提出了基于正区域的属性约简增量式更新 apra(D:)=UxUI [x]D 算法，提高了属性约简算法效率；文献[6]提出了基 apr(D:)=U{x∈U1[x]A∩D:≠☑} 于差别矩阵的属性约简增量式更新算法；文献[7] 定义3在决策表S=〈U,C,D,V)中， 提出了不使用可辨识矩阵的增量式核更新算法以及 HACC,正区域POS,(D)和边界域BND,(D)定 属性约简算法；文献[8]针对现有增量式属性约简 义为 算法中存在的约简传承性差以及不完备现象，提出 PoS,(D)=apr(D.) 了基于标记可辨识矩阵的增量式属性约简算法。然 而，这些算法不适宜解决每次增加批量对象的问题。 BND(D)=U (apr(D:)apr(D))= 文献[11]提出了面向成组对象集的3种增量式信 U-POS (D) 息嫡属性约简算法：文献[12]充分利用先前约简中 定义4 在决策表S中，一个属性集Red C 信息和计数排序算法快速更新批量对象的约简，降 是C的D-约简，如果 低计算复杂度；文献[13-14]探讨了混合属性约简 1)POSRed(D)=POSc(D); 算法以及利用MapReduce进行面向大规模数据集 2)Ha∈Red,POSRed-lai(D)≠POSR(D)。 的属性约简方法。 定义5在决策表S中，ACC,Hc∈A,在正 为提高增量式学习算法效率5]和约简传承性， 区域下属性c重要性定义为 本文构建了面向成组对象的增量式属性约简算法， Sigi(c,A,D)=Y(D)-YA-ic(D) 利用原始决策表的一个候选约简来快速地更新新增 I POS (D)I 式中：ya(D)= 决策表的约简，这样既提高了约简的传承性，又有效 U川 地利用了原有知识，提高了增量式学习算法效率。 定义6在决策表S中，A二C,Hc∈C-A, 在正区域下属性c重要性定义为 1粗糙集概念 Sig"(c,A,D)=YAul(D)-Y(D) 下面简要介绍本文主要用到的一些Rough集的 定义7设Red为决策表S的候选属性约简， 基本概念1,9，，1-14 NewRed为新增样本之后的新约简，则单次增量式 定义1四元组S=〈U,CUD,V,f是一个决 约简的传承率(inheritance rate,IR)定义为 策表，其中U={x1,x2,…,xn}表示对象的非空有限 IRed∩NewRed I IR = min(I Red I,I NewRed I) 集合，称为论域：C表示条件属性的非空有限集，D 假设进行了地次增量式约简，则平均传承率 表示决策属性的非空有限集，C∩D=☑；V=U acCUD (inheritance rate average,IRA)定义为 V。,V。是属性a的值域；f:U×(CUD)→V是一个 IR 信息函数，它为每个对象赋予一个信息值，即Ha∈ IRA= CUD,x∈U,有fx,a)∈'。；每一个属性子集 在约简过程中，传承率越高则约简集的变化越 R二CUD决定了一个二元不可区分关系 小，对原始规则集的影响将越小。如果传承率为1， IND(R): 说明新增的对象不影响原始的规则集：如果传承率 IND(R)= 为0，则新的约简集与原来的约简集完全不同，这时 {(x,y）∈U×U|a∈Rf(x,a)=fy,a)} 需全部更新所有规则。 关系IND(R)构成了U的一个划分，用U/
策表中，一般不希望将原有的决策表和新产生的增 量数据整合成一个新的决策表进行属性约简，因为 这样会对原有数据不断地进行重复的计算。 因此， 如何利用原决策表中所含的信息并结合增量数据来 进行属性约简成为粗糙集理论新的挑战。 数据的动态变化主要有 ３ 种情况：１）属性集保 持不变而对象不断增加［５－８ ］ ；２）对象集保持不变而 属性集不断增加［９］ ； ３） 对象集和属性集同时增 加［１０］ 。 本文着重研究第 １ 种情况的增量式属性约 简问题，尤其研究适合大规模数据集的约简问题。 文献［５］提出了基于正区域的属性约简增量式更新 算法，提高了属性约简算法效率；文献［６］提出了基 于差别矩阵的属性约简增量式更新算法；文献［７］ 提出了不使用可辨识矩阵的增量式核更新算法以及 属性约简算法；文献［８］针对现有增量式属性约简 算法中存在的约简传承性差以及不完备现象，提出 了基于标记可辨识矩阵的增量式属性约简算法。 然 而，这些算法不适宜解决每次增加批量对象的问题。 文献［１１］提出了面向成组对象集的 ３ 种增量式信 息熵属性约简算法；文献［１２］充分利用先前约简中 信息和计数排序算法快速更新批量对象的约简，降 低计算复杂度；文献［１３－１４］探讨了混合属性约简 算法以及利用 ＭａｐＲｅｄｕｃｅ 进行面向大规模数据集 的属性约简方法。 为提高增量式学习算法效率［１５］ 和约简传承性， 本文构建了面向成组对象的增量式属性约简算法， 利用原始决策表的一个候选约简来快速地更新新增 决策表的约简，这样既提高了约简的传承性，又有效 地利用了原有知识，提高了增量式学习算法效率。 １ 粗糙集概念 下面简要介绍本文主要用到的一些 Ｒｏｕｇｈ 集的 基本概念［１，９，１１，１３－１４］ 。 定义 １ 四元组 Ｓ ＝ Ｕ，Ｃ ∪ Ｄ，Ｖ，ｆ 是一个决 策表，其中 Ｕ ＝ ｛ｘ１ ，ｘ２ ，…，ｘｎ ｝表示对象的非空有限 集合，称为论域； Ｃ 表示条件属性的非空有限集， Ｄ 表示决策属性的非空有限集， Ｃ ∩ Ｄ ＝ ⌀ ； Ｖ ＝ ∪ａ∈Ｃ∪Ｄ Ｖａ ， Ｖａ 是属性 ａ 的值域； ｆ：Ｕ × （Ｃ ∪ Ｄ） → Ｖ 是一个 信息函数，它为每个对象赋予一个信息值，即 ∀ａ ∈ Ｃ ∪ Ｄ ， ｘ ∈ Ｕ ，有 ｆ（ｘ， ａ） ∈ Ｖａ ；每一个属性子集 Ｒ ⊆ Ｃ ∪ Ｄ 决 定 了 一 个 二 元 不 可 区 分 关 系 ＩＮＤ（Ｒ） ： ＩＮＤ（Ｒ） ＝ ｛（ｘ，ｙ） ∈ Ｕ × Ｕ ｜ ∀ａ ∈ Ｒ，ｆ（ｘ，ａ） ＝ ｆ（ｙ，ａ）｝ 关系 ＩＮＤ（ Ｒ ） 构成了 Ｕ 的一个划分， 用 Ｕ ／ ＩＮＤ（ Ｒ ） 表示， 简记为 Ｕ／ Ｒ 。 Ｕ／ Ｒ 中的任何元素 ［ｘ］ Ｒ ＝ ｛ ｙ ｜ ∀ａ ∈ Ｒ ， ｆ（ｘ，ａ） ＝ ｆ（ｙ，ａ） ｝称为等价 类。 不失一般性， 假设决策表 Ｓ 仅有一个决策属性 Ｄ ＝ ｛ｄ｝， 其决策属性值映射为 １， ２，…， ｋ ，由 Ｄ 导 出的 Ｕ 上划分记为 Ｕ／ Ｄ ＝ ｛ Ｄ１ ， Ｄ２ ， …，Ｄｋ ｝，其 中， Ｄｉ ＝ ｛ ｘ ∈ Ｕ ｜ ｆ（ｘ，Ｄ） ＝ ｉ ｝， ｉ ＝ １， ２， …， ｋ。 定义 ２ 在决策表 Ｓ ＝ Ｕ，Ｃ ∪ Ｄ，Ｖ，ｆ 中，对 于每个决策类 Ｄｉ ∈ Ｕ／ Ｄ 和不可区分关系 Ａ ⊆ Ｃ， Ｄｉ 的下近似集与上近似集分别可以由 Ａ 的基本集定义 如下： ａｐｒＡ（Ｄｉ） ＝∪ ｛ｘ ∈ Ｕ ｜ ［ｘ］ Ａ ⊆ Ｄｉ｝ ａｐｒＡ（Ｄｉ） ＝∪ ｛ｘ ∈ Ｕ ｜ ［ｘ］ Ａ ∩ Ｄｉ ≠ ⌀｝ 定 义 ３ 在 决 策 表 Ｓ ＝ Ｕ，Ｃ，Ｄ，Ｖ，ｆ 中， ∀Ａ ⊆Ｃ， 正区域 ＰＯＳＡ（Ｄ） 和边界域 ＢＮＤＡ（Ｄ） 定 义为 ＰＯＳＡ（Ｄ） ＝ ∪１≤ｉ≤ｋ ａｐｒＡ（Ｄｉ） ＢＮＤＡ（Ｄ） ＝ ∪１≤ｉ≤ｋ （ａｐｒＡ（Ｄｉ） － ａｐｒＡ（Ｄｉ）） ＝ Ｕ － ＰＯＳＡ（Ｄ） 定义 ４ 在决策表 Ｓ 中，一个属性集 Ｒｅｄ ⊆ Ｃ 是 Ｃ 的 Ｄ⁃ 约简， 如果 １） ＰＯＳＲｅｄ（Ｄ） ＝ ＰＯＳＣ（Ｄ） ； ２） ∀ａ ∈ Ｒｅｄ ， ＰＯＳＲｅｄ－｛ａ｝（Ｄ） ≠ ＰＯＳＲｅｄ（Ｄ） 。 定义 ５ 在决策表 Ｓ 中， Ａ⊆Ｃ ， ∀ｃ∈Ａ ，在正 区域下属性 ｃ 重要性定义为 Ｓｉｇ ｉｎｎｅｒ （ｃ，Ａ，Ｄ） ＝ γＡ（Ｄ） – γＡ－｛ｃ｝（Ｄ） 式中： γＡ（Ｄ） ＝ ｜ ＰＯＳＡ（Ｄ） ｜ Ｕ 。 定义 ６ 在决策表 Ｓ 中， Ａ ⊆ Ｃ ， ∀ｃ ∈ Ｃ － Ａ ， 在正区域下属性 ｃ 重要性定义为 Ｓｉｇ ｏｕｔｅｒ （ｃ，Ａ，Ｄ） ＝ γＡ∪｛ｃ｝（Ｄ） – γＡ（Ｄ） 定义 ７ 设Ｒｅｄ为决策表 Ｓ 的候选属性约简， ＮｅｗＲｅｄ 为新增样本之后的新约简，则单次增量式 约简的传承率（ｉｎｈｅｒｉｔａｎｃｅ ｒａｔｅ， ＩＲ）定义为 ＩＲ ＝ ｜ Ｒｅｄ ∩ ＮｅｗＲｅｄ ｜ ｍｉｎ（｜ Ｒｅｄ ｜ ， ｜ ＮｅｗＲｅｄ ｜ ） 假设进行了 ｗ 次增量式约简，则平均传承率 （ｉｎｈｅｒｉｔａｎｃｅ ｒａｔｅ ａｖｅｒａｇｅ，ＩＲＡ）定义为 ＩＲＡ ＝ ∑ ｗ ｉ ＝ １ ＩＲｉ ｗ 在约简过程中，传承率越高则约简集的变化越 小，对原始规则集的影响将越小。 如果传承率为 １， 说明新增的对象不影响原始的规则集；如果传承率 为 ０，则新的约简集与原来的约简集完全不同，这时 需全部更新所有规则。 第 ４ 期 钱进，等：面向成组对象集的增量式属性约简算法 ·４９７·
.498 智能系统学报 第11卷 2面向成组对象集的增量式属性约简 新决策表S”的约简。 算法 证明若Red为决策表S的约简，则POS= POS8。又3X,∈BND&[y∈X:],则POSg= 给定决策表S=〈U,CUD,V,,一个约简 P0S%和P0S名=P0S,从而P0SE=P0S,故 Red CC。新对象y加入到决策表S中，U=UU Red为决策表S'的约简。 {y},将此时的新决策表标记为S”。一种最简单的 定理2给定决策表S和新增对象y,Red是决 属性约简增量式更新算法是直接计算S”的约简。 策表S的约简，若3X:∈P0S8[y∈X:]且Hz∈ 显然，这种方法的属性约简效率比较低下，因为需要 X,[Ha∈Red[fz,a)=fy,a)]→f(z,d)=fy, 重复计算原始决策表S中的等价类。为此，如何在 d)],则Red是新决策表S'的约简。 已有的约简Red的基础上快速更新约简则成为本文 证明若Red为决策表S的约简，则POS= 主要研究内容。为此，如何在已有的约简Red的基 POS&。又3X:∈POS[y∈X:]且Hz∈X:[H 础上快速更新约简则成为本文主要研究内容。为方 a ERed[f(z,a)=f(y,a)=f(z,d)=f(y,d)], 便讨论，假设U/Red={X,X2,…,Xm},U/C= 则P0S=POS&U{y}和P0S=P0SU{yl, {X'1,X'2,…,X,{,用POS表示决策表S由约简 从而P0S%=POS%,故Red为决策表S”的约简。 Red导出的正区域，用BNDg表示决策表S由约简 定理3给定决策表S和新增对象y,Red是决 Red导出的边界域，即U-POS。 策表S的约简，yU/C∧y∈U/Red,若3zeX 当新对象y加入到S中，主要分为两类情况： [f(z,Red)=f(y,Red)]Af(z,d)≠fy,d),则 1)y无法用Red区分，当且仅当3x∈U使得 Red不是决策表S'的约简。 Ya E Red [f(x,a)=f(y,a)] 证明若Red为决策表S的约简，则POS= 2)y可以用Red区分，当且仅当Hx∈U使得 P0S。又y生U/C,则P0SE=P0S形U{y}。 3a∈Red[f(x,a)≠f(y,a)]。 [y]a∈U/Red,若3z∈X[f(x,Red)=f八y, 对于第2种情况，显然P0S=P0SU{y, Red)]Af(x,d)≠f(y,d),显然POS≠ 则Rd是新决策表S'的约简。对于第1种情况，还 POSU{y},故Red不是决策表S'的约简。 不能完全判断出正区域的变化，需要对上述情况进 下面给出面向单个对象的增量式属性约简算 一步细分，分为以下4种情况。 法，如算法1所示。 ①若3X:eBND[y∈X:],则POSg= 算法1面向单个对象的增量式属性约简算法 P0S8; 输入一个决策表，S;一个新增对象，y;一个 ②若3X,∈P0S[y∈X:],分为2种情况： 约简，Redu; a)Vxe X:f(x,d)=f(y,d)],POSRe POSRed 输出一个新的约简，Redyulsto U{y},而P0Sg=P0S8U{y},即P0Sg= 1)A =Redo P0s;b)3x∈X,[f(x,d)≠fy,d)],则 2)计算U/A={A1,A2,…,A,},U/C={X1,X2, P0S8=P0S8-X:,而P0S=P0S-X:,则 “,X,},计算POS和POS/y属于旧的正区域 P0SE=P0S。总之，P0S=P0SE。 3)如果y∈P0S,则转到9)：/y属于旧的边 界域 ③若[y]cU/CA[y]a∈U/Red,若 4)如果y∈BND,则转到9)；/y属于新的正 3 EPOSR使得Hz∈[x]d[f(z,d)=f八y, 区域对象 d)],则P0S=P0SU{y},而P0S8= 5)如果y主U/A,则转到9)；否则A'。=AU POS Uy POS POS {y}; ④当[y]cEU/CA[y]a∈U/Red,若 6)判断A'。一致性，若A'。中对象的决策一致， 3x∈POS使得3z∈[x]a[f(x,d)≠fy, 则转到9)：/y与其他对象在A属性集上产生冲突 d)],则P0Sg=P0S-[x]m,而POs8= 7)While (I POS POS) POS"c U{y,即P0S≠P0sE。 For each attribute c C-A 根据上述分析，可以得出以下定理。 计算sig0r(c,A,D); 定理1给定决策表S和新增对象y,Red是决 sigu(a,A,D)=max(sigu(c,A,D)); 策表S的约简，若3X:∈BND[y∈X:],则Red是 A=A Ua:
２ 面向成组对象集的增量式属性约简 算法 给定决策表 Ｓ ＝ Ｕ，Ｃ ∪ Ｄ，Ｖ，ｆ， 一个约简 Ｒｅｄ ⊆Ｃ 。 新对象 ｙ 加入到决策表 Ｓ 中， Ｕ′ ＝ Ｕ ∪ ｛ｙ｝ ，将此时的新决策表标记为 Ｓ′ 。 一种最简单的 属性约简增量式更新算法是直接计算 Ｓ′ 的约简。 显然，这种方法的属性约简效率比较低下，因为需要 重复计算原始决策表 Ｓ 中的等价类。 为此，如何在 已有的约简Ｒｅｄ的基础上快速更新约简则成为本文 主要研究内容。 为此，如何在已有的约简Ｒｅｄ的基 础上快速更新约简则成为本文主要研究内容。 为方 便讨论，假设 Ｕ／ Ｒｅｄ ＝ ｛ Ｘ１ ， Ｘ２ ，…， Ｘｍ ｝， Ｕ／ Ｃ ＝ ｛ Ｘ′１ ，Ｘ′２ ，…，Ｘ′ｔ ｝，用 ＰＯＳ Ｕ Ｒｅｄ 表示决策表 Ｓ 由约简 Ｒｅｄ导出的正区域，用 ＢＮＤ Ｕ Ｒｅｄ 表示决策表 Ｓ 由约简 Ｒｅｄ导出的边界域，即 Ｕ⁃ ＰＯＳ Ｕ Ｒｅｄ 。 当新对象 ｙ 加入到 Ｓ 中，主要分为两类情况： １） ｙ 无法用Ｒｅｄ区分，当且仅当 ∃ｘ ∈ Ｕ 使得 ∀ａ ∈ Ｒｅｄ ［ ｆ（ｘ，ａ） ＝ ｆ（ｙ，ａ） ］； ２） ｙ 可以用Ｒｅｄ区分，当且仅当 ∀ｘ ∈ Ｕ 使得 ∃ａ ∈ Ｒｅｄ ［ ｆ（ｘ，ａ） ≠ ｆ（ｙ，ａ） ］。 对于第 ２ 种情况，显然 ＰＯＳ Ｕ′ Ｒｅｄ ＝ ＰＯＳ Ｕ Ｒｅｄ ∪ ｛ｙ｝， 则Ｒｅｄ是新决策表 Ｓ′ 的约简。 对于第 １ 种情况，还 不能完全判断出正区域的变化，需要对上述情况进 一步细分，分为以下 ４ 种情况。 ①若 ∃Ｘｉ ∈ ＢＮＤ Ｕ Ｃ ［ ｙ ∈ Ｘｉ ］， 则 ＰＯＳ Ｕ′ Ｒｅｄ ＝ ＰＯＳ Ｕ′ Ｃ ； ②若 ∃Ｘｉ ∈ ＰＯＳ Ｕ Ｃ ［ ｙ ∈ Ｘｉ ］，分为 ２ 种情况： ａ） ∀ｘ∈Ｘｉ ［ ｆ（ｘ，ｄ） ＝ ｆ（ｙ，ｄ） ］，则 ＰＯＳ Ｕ′ Ｒｅｄ ＝ ＰＯＳ Ｕ Ｒｅｄ ∪ ｛ ｙ ｝， 而 ＰＯＳ Ｕ′ Ｃ ＝ ＰＯＳ Ｕ Ｃ ∪ ｛ ｙ ｝， 即 ＰＯＳ Ｕ′ Ｒｅｄ ＝ ＰＯＳ Ｕ′ Ｃ ； ｂ ） ∃ｘ ∈ Ｘｉ ［ ｆ（ｘ，ｄ） ≠ ｆ（ｙ，ｄ） ］， 则 ＰＯＳ Ｕ′ Ｃ ＝ ＰＯＳ Ｕ Ｃ － Ｘｉ ，而 ＰＯＳ Ｕ′ Ｒｅｄ ＝ ＰＯＳ Ｕ Ｒｅｄ － Ｘｉ ，则 ＰＯＳ Ｕ′ Ｃ ＝ ＰＯＳ Ｕ′ Ｒｅｄ 。 总之， ＰＯＳ Ｕ′ Ｒｅｄ ＝ ＰＯＳ Ｕ′ Ｃ 。 ③ 若 ［ｙ］ Ｃ ∉ Ｕ／ Ｃ ∧ ［ｙ］ Ｒｅｄ ∈ Ｕ／ Ｒｅｄ ， 若 ∃ｘ ∈ＰＯＳ Ｕ Ｒｅｄ 使 得 ∀ｚ ∈ ［ｘ］ Ｒｅｄ ［ ｆ（ｚ，ｄ） ＝ ｆ（ｙ， ｄ） ］， 则 ＰＯＳ Ｕ′ Ｒｅｄ ＝ ＰＯＳ Ｕ Ｒｅｄ ∪ ｛ｙ｝ ， 而 ＰＯＳ Ｕ′ Ｃ ＝ ＰＯＳ Ｕ Ｃ ∪｛ｙ｝ ，则 ＰＯＳ Ｕ′ Ｒｅｄ ＝ ＰＯＳ Ｕ′ Ｃ ； ④ 当 ［ｙ］ Ｃ ∉ Ｕ／ Ｃ ∧ ［ｙ］ Ｒｅｄ ∈ Ｕ／ Ｒｅｄ ， 若 ∃ｘ ∈ＰＯＳ Ｕ Ｒｅｄ 使 得 ∃ｚ ∈ ［ｘ］ Ｒｅｄ ［ｆ（ｘ，ｄ） ≠ ｆ（ｙ， ｄ）］， 则 ＰＯＳ Ｕ′ Ｒｅｄ ＝ ＰＯＳ Ｕ Ｒｅｄ － ［ｘ］ Ｒｅｄ ， 而 ＰＯＳ Ｕ′ Ｃ ＝ ＰＯＳ Ｕ Ｃ ∪ ｛ｙ｝ ，即 ＰＯＳ Ｕ′ Ｒｅｄ ≠ ＰＯＳ Ｕ′ Ｃ 。 根据上述分析，可以得出以下定理。 定理 １ 给定决策表 Ｓ 和新增对象 ｙ，Ｒｅｄ是决 策表 Ｓ 的约简，若 ∃Ｘｉ ∈ ＢＮＤ Ｕ Ｃ ［ ｙ ∈ Ｘｉ ］，则Ｒｅｄ是 新决策表 Ｓ′ 的约简。 证明 若Ｒｅｄ为决策表 Ｓ 的约简，则 ＰＯＳ Ｕ Ｒｅｄ ＝ ＰＯＳ Ｕ Ｃ 。 又 ∃Ｘｉ ∈ ＢＮＤ Ｕ Ｃ ［ ｙ ∈ Ｘｉ ］，则 ＰＯＳ Ｕ′ Ｃ ＝ ＰＯＳ Ｕ Ｃ 和 ＰＯＳ Ｕ′ Ｒｅｄ ＝ ＰＯＳ Ｕ Ｒｅｄ ，从而 ＰＯＳ Ｕ′ Ｃ ＝ ＰＯＳ Ｕ′ Ｒｅｄ ，故 Ｒｅｄ为决策表 Ｓ′ 的约简。 定理 ２ 给定决策表 Ｓ 和新增对象 ｙ，Ｒｅｄ是决 策表 Ｓ 的约简，若 ∃Ｘｉ ∈ ＰＯＳ Ｕ Ｃ ［ ｙ ∈ Ｘｉ ］且 ∀ｚ ∈ Ｘｉ ［ ∀ａ ∈ Ｒｅｄ ［ｆ（ｚ，ａ） ＝ ｆ（ｙ，ａ）］ ⇒ ｆ（ｚ，ｄ） ＝ ｆ（ｙ， ｄ） ］，则Ｒｅｄ是新决策表 Ｓ′ 的约简。 证明 若Ｒｅｄ为决策表 Ｓ 的约简，则 ＰＯＳ Ｕ Ｒｅｄ ＝ ＰＯＳ Ｕ Ｃ 。 又 ∃Ｘｉ ∈ ＰＯＳ Ｕ Ｒｅｄ ［ ｙ ∈ Ｘｉ ］且 ∀ｚ ∈ Ｘｉ ［ ∀ ａ ∈Ｒｅｄ［ｆ（ｚ， ａ） ＝ ｆ（ｙ， ａ）⇒ｆ（ｚ， ｄ） ＝ ｆ（ｙ， ｄ）］， 则 ＰＯＳ Ｕ′ Ｃ ＝ ＰＯＳ Ｕ Ｃ ∪ ｛ｙ｝和 ＰＯＳ Ｕ′ Ｒｅｄ ＝ ＰＯＳ Ｕ Ｒｅｄ ∪ ｛ｙ｝， 从而 ＰＯＳ Ｕ′ Ｒｅｄ ＝ ＰＯＳ Ｕ′ Ｃ ，故Ｒｅｄ为决策表 Ｓ′ 的约简。 定理 ３ 给定决策表 Ｓ 和新增对象 ｙ，Ｒｅｄ是决 策表 Ｓ 的约简， ｙ ∉ Ｕ／ Ｃ ∧ ｙ ∈ Ｕ／ Ｒｅｄ ，若 ∃ｚ ∈ Ｘｉ ［ ｆ（ｚ，Ｒｅｄ） ＝ ｆ（ｙ，Ｒｅｄ） ］ ∧ ｆ（ｚ，ｄ） ≠ ｆ（ｙ，ｄ） ，则 Ｒｅｄ不是决策表 Ｓ′ 的约简。 证明 若Ｒｅｄ为决策表 Ｓ 的约简，则 ＰＯＳ Ｕ Ｒｅｄ ＝ ＰＯＳ Ｕ Ｃ 。 又 ｙ ∉ Ｕ／ Ｃ ，则 ＰＯＳ Ｕ′ Ｃ ＝ ＰＯＳ Ｕ Ｃ ∪ ｛ ｙ ｝ 。 ［ｙ］ Ｒｅｄ ∈ Ｕ／ Ｒｅｄ ，若 ∃ｚ ∈ Ｘｉ ［ ｆ（ｘ，Ｒｅｄ） ＝ ｆ（ｙ， Ｒｅｄ） ］ ∧ ｆ（ｘ，ｄ） ≠ ｆ（ｙ，ｄ） ， 显 然 ＰＯＳ Ｕ′ Ｒｅｄ ≠ ＰＯＳ Ｕ Ｒｅｄ ∪｛ ｙ ｝ ，故Ｒｅｄ不是决策表 Ｓ′ 的约简。 下面给出面向单个对象的增量式属性约简算 法，如算法 １ 所示。 算法 １ 面向单个对象的增量式属性约简算法 输入 一个决策表， Ｓ ；一个新增对象， ｙ ；一个 约简， ＲｅｄＵ； 输出 一个新的约简， ＲｅｄＵ∪｛ｙ｝ 。 １） Ａ ＝ ＲｅｄＵ ； ２）计算Ｕ／ Ａ ＝｛ Ａ１， Ａ２，…， Ａｒ ｝，Ｕ／ Ｃ ＝ ｛ Ｘ１，Ｘ２， …， Ｘｔ ｝，计算 ＰＯＳ Ｕ Ｃ 和 ＰＯＳ Ｕ Ａ ／ ／ ｙ 属于旧的正区域 ３）如果 ｙ ∈ ＰＯＳ Ｕ Ｃ ，则转到 ９）； ／ ／ ｙ 属于旧的边 界域 ４）如果 ｙ ∈ ＢＮＤ Ｕ Ｃ ，则转到 ９）； ／ ／ ｙ 属于新的正 区域对象 ５）如果 ｙ ∉ Ｕ／ Ａ ， 则转到 ９）； 否则 Ａ′ｈ ＝ Ａｈ ∪ ｛ｙ｝ ； ６）判断 Ａ′ｈ 一致性，若 Ａ′ｈ 中对象的决策一致， 则转到 ９）； ／ ／ ｙ 与其他对象在 Ａ 属性集上产生冲突 ７）Ｗｈｉｌｅ （ ｜ ＰＯＳ Ａ′ｈ Ａ ｜ ≠ ｜ ＰＯＳ Ａ′ｈ Ｃ ｜ ） ｛ Ｆｏｒ ｅａｃｈ ａｔｔｒｉｂｕｔｅ ｃ ∈ Ｃ － Ａ 计算 ｓｉｇ ｏｕｔｅｒ Ｕ′ （ｃ，Ａ，Ｄ） ； ｓｉｇ ｏｕｔｅｒ Ｕ′ （ａ，Ａ，Ｄ） ＝ ｍａｘ（ ｓｉｇ ｏｕｔｅｒ Ｕ′ （ｃ，Ａ，Ｄ） ）； Ａ ＝ Ａ ∪ ｛ａ｝； ·４９８· 智 能 系 统 学 报 第 １１ 卷
第4期 钱进，等：面向成组对象集的增量式属性约简算法 ·499· 8)For each attribute c eA X分，…，X4}和(UUUa)/C={X,X'2,…, {计算sig(c,A,D); X,X1,…,X,X验1，…，X哈{街 如果sig(c,A,D)=0,则A=A-c; 4)如果h=0和h'=0,转5： 9)Reduvis=A,输出Redwvist。 5)计算P0S和P0S, 复杂度分析算法的时间复杂度主要集中在 如果P0S△=P0S,转到10)：否则转到6)。 2)、7)和8)。利用文献[13]中计数排序算法和简 /新增对象集中约简不能区分的矛盾对象 化决策表处理方式，2)的时间复杂度为 6)U'=U-POSA; 0(1C11U1),7)的时间复杂度为O(1C11U1), 7)for i=1 to h 8)的最坏时间复杂度为0(1C12(1U/C1+1)),故 {如果A',不一致，则U=U'dUA':; 整个算法时间复杂度为max(O(ICI川U1), /累加同一等价类中约简不能区分的矛盾对象 0(1C1(1U/C1+1))),空间复杂度为 8)计算POS和POS8ad; 0(1U1)。 9)While I POS I POS 1) 若每次只增加一个对象，使用算法1来计算约 For each attribute c C-A 简，其计算效率较差。为此，本文主要考虑当每次增 计算sig(c,A,D); 加一批对象时如何进行属性约简。给定一个决策表 sigue (a,A,D)=max(sigu(c,A,D)); S,ASC,U/A={A1,A2,…,A,}。假设UA是新 /若这样的属性有多个，则任选一个； 增的对象集，U/A={A,A分，…，A},那么 A=A Ua (UUU)/A={A'1,A'2,…,A'A,A+1,…,A,, 10)For each attribute c EA A1,…,A},其中A':=AUA(i=1,2,…, {计算sig把a(c,A,D); h)。当成批增加对象时，我们主要考虑UUUA中 如果siga(c,A,D)=0,则A=A-{c:} A不能区分的对象集，进一步说就是考虑A'中对象 lI)Reduuv△=A,输出RedyvuA。 集以及A1,…,A中C能够区分而A不能区分的 复杂度分析算法的时间复杂度主要集中在 对象集。下面给出面向成组对象集的增量式属性约 2)、3)、9)和10)。利用文献[13]中计数排序算法 简算法，如算法2所示。 和简化决策表处理方式，2)的时间复杂度为 算法2面向成组对象集的增量式属性约简算 O(1A1IUUU°I),3)的时间复杂度为 法(GIAR) O(1C1IUUU小I),9)的时间复杂度为 输入一个决策表，S;一个候选约简，Rdu; 0(IC1川U'I),10)的最坏时间复杂度为 新增对象集，U: O(1C121[UUU]/C1),故整个算法时间复杂 输出一个新的约简，Redovu△。 度为max(0(1C11U'mdI),O(1C121[UU l)A=Redu,Uhd=☑； U]/C1)),空间复杂度为0(1UUUI)。 2)计算U/A={A1,A2,…,A,},UA/A= 例1表1给出一个决策表S和新增对象集 A,A始，…，A9}和(UUU)/A={A'1,A'2,…, 0A,决策表S包含3个约简{c2}、{c2c3}和 A,A1,…,A,A分，…，A: {cc4},分别计算约简的变化情况，如表2所示。 3)U/C={X1,X2,…,X},U/C={X, 表2原始决策表S和新增对象集U Table 2 Original decision table S and new added object set UA U C2 C3 d UA C3 Ca d 1 0 10 2 210 0 1 X2 0 0 1 2 Y2 1 0 1 0 4 3 1 1 1 1 3 0 1 0 1 2 尤4 1 0 1 0 0 2 1 1 1 5 0 2 2 2 0 1 1 2 X6 1 2 0 0 2 0 1 1
８） Ｆｏｒ ｅａｃｈ ａｔｔｒｉｂｕｔｅ ｃ ∈ Ａ ｛ 计算 ｓｉｇ ｉｎｎｅｒ Ｕ′ （ｃ，Ａ，Ｄ） ； 如果 ｓｉｇ ｉｎｎｅｒ Ｕ′ （ｃ，Ａ，Ｄ） ＝ ０，则 Ａ ＝ Ａ － ｃ； ９） ＲｅｄＵ∪｛ｙ｝ ＝ Ａ， 输出 ＲｅｄＵ∪｛ｙ｝ 。 复杂度分析 算法的时间复杂度主要集中在 ２）、７）和 ８）。 利用文献［１３］中计数排序算法和简 化 决 策 表 处 理 方 式， ２ ） 的 时 间 复 杂 度 为 Ｏ（｜ Ｃ ｜ ｜ Ｕ ｜ ）， ７）的时间复杂度为 Ｏ（｜ Ｃ ｜ ｜ Ｕ ｜ ） ， ８）的最坏时间复杂度为 Ｏ（｜ Ｃ ｜ ２ （｜ Ｕ／ Ｃ ｜ ＋ １）） ，故 整个算法时间复杂度为 ｍａｘ （ Ｏ（ ｜ Ｃ ｜ ｜ Ｕ ｜ ） ， Ｏ（｜ Ｃ ｜ ２ （ ｜ Ｕ／ Ｃ ｜ ＋ １）） ）， 空 间 复 杂 度 为 Ｏ（｜ Ｕ ｜ ）。 若每次只增加一个对象，使用算法 １ 来计算约 简，其计算效率较差。 为此，本文主要考虑当每次增 加一批对象时如何进行属性约简。 给定一个决策表 Ｓ ， Ａ ⊆ Ｃ ， Ｕ／ Ａ ＝ ｛ Ａ１ ， Ａ２ ，…， Ａｒ ｝。 假设 Ｕ △ 是新 增的对 象 集， Ｕ △ ／ Ａ ＝ ｛ Ａ △ １ ， Ａ △ ２ ， …， Ａ △ ｒ′ ｝， 那 么 （Ｕ ∪Ｕ △ ） ／ Ａ ＝ ｛ Ａ′１ ， Ａ′２ ，…， Ａ′ｈ ， Ａｈ＋１ ，…， Ａｒ ， Ａ △ ｈ＋１ ， …， Ａ △ ｒ′ ｝，其中 Ａ′ｉ ＝ Ａｉ ∪ Ａ △ ｉ （ｉ ＝ １，２，…， ｈ）。 当成批增加对象时，我们主要考虑 Ｕ ∪ Ｕ △ 中 Ａ 不能区分的对象集，进一步说就是考虑 Ａ′ｉ 中对象 集以及 Ａ △ ｈ＋１ ，…， Ａ △ ｒ′ 中 Ｃ 能够区分而 Ａ 不能区分的 对象集。 下面给出面向成组对象集的增量式属性约 简算法，如算法 ２ 所示。 算法 ２ 面向成组对象集的增量式属性约简算 法（ＧＩＡＲ） 输入 一个决策表， Ｓ ；一个候选约简， ＲｅｄＵ ； 新增对象集， Ｕ △ ； 输出 一个新的约简， ＲｅｄＵ∪Ｕ△ 。 １） Ａ ＝ ＲｅｄＵ ， Ｕ′ｂｎｄ ＝ ⌀ ； ２）计算 Ｕ／ Ａ ＝ ｛ Ａ１ ， Ａ２ ，…， Ａｒ ｝， Ｕ △ ／ Ａ ＝ ｛ Ａ △ １ ， Ａ △ ２ ，…， Ａ △ ｒ′ ｝和 （Ｕ ∪ Ｕ △ ） ／ Ａ ＝ ｛ Ａ′１ ， Ａ′２ ，…， Ａ′ｈ ， Ａｈ＋１ ，…， Ａｒ ， Ａ △ ｈ＋１ ，…， Ａ △ ｒ′ ｝； ３） Ｕ／ Ｃ ＝ ｛ Ｘ１ ， Ｘ２ ，…， Ｘｔ ｝， Ｕ △ ／ Ｃ ＝ ｛ Ｘ △ １ ， Ｘ △ ２ ，…， Ｘ △ ｔ′ ｝ 和 （Ｕ ∪ Ｕ △ ） ／ Ｃ ＝ ｛ Ｘ′１ ， Ｘ′２ ， …， Ｘ′ｈ′， Ｘｈ′＋１ ，…， Ｘｒ ， Ｘ △ ｈ′＋１ ，…， Ｘ △ ｔ′ ｝； ４）如果 ｈ ＝ ０ 和 ｈ′ ＝ ０，转 ５； ５）计算 ＰＯＳ Ｕ△ Ａ 和 ＰＯＳ Ｕ△ Ｃ ， 如果 ＰＯＳ Ｕ△ Ａ ＝ ＰＯＳ Ｕ△ Ｃ ， 转到 １０）；否则转到 ６）。 ／ ／ 新增对象集中约简不能区分的矛盾对象 ６） Ｕ′ｂｎｄ ＝ Ｕ Δ － ＰＯＳ Ｕ△ Ａ ； ７）ｆｏｒ ｉ ＝ １ ｔｏ ｈ ｛如果 Ａ′ｉ 不一致，则 Ｕ′ｂｎｄ ＝ Ｕ′ｂｎｄ ∪ Ａ′ｉ ；｝ ／ ／ 累加同一等价类中约简不能区分的矛盾对象 ８）计算 ＰＯＳ Ｕ′ｂｎｄ Ａ 和 ＰＯＳ Ｕ′ｂｎｄ Ｃ ； ９）Ｗｈｉｌｅ （ ｜ ＰＯＳ Ｕ′ｂｎｄ Ａ ｜ ≠ ｜ ＰＯＳ Ｕ′ｂｎｄ Ｃ ｜ ） ｛Ｆｏｒ ｅａｃｈ ａｔｔｒｉｂｕｔｅ ｃ ∈ Ｃ － Ａ 计算 ｓｉｇ ｏｕｔｅｒ Ｕ′ｂｎｄ （ｃ，Ａ，Ｄ） ； ｓｉｇ ｏｕｔｅｒ Ｕ′ｂｎｄ （ａ，Ａ，Ｄ） ＝ ｍａｘ（ ｓｉｇ ｏｕｔｅｒ Ｕ′ｂｎｄ （ｃ，Ａ，Ｄ） ）； ／ ／ 若这样的属性有多个，则任选一个； Ａ ＝ Ａ ∪ ｛ａ｝；｝ １０）Ｆｏｒ ｅａｃｈ ａｔｔｒｉｂｕｔｅ ｃ ∈ Ａ ｛ 计算 ｓｉｇ ｉｎｎｅｒ Ｕ∪ＵΔ（ｃ，Ａ，Ｄ） ； 如果 ｓｉｇ ｉｎｎｅｒ Ｕ∪ＵΔ（ｃ，Ａ，Ｄ） ＝ ０，则 Ａ ＝ Ａ –｛ｃ｝； ｝ １１） ＲｅｄＵ∪Ｕ△ ＝ Ａ， 输出 ＲｅｄＵ∪Ｕ△ 。 复杂度分析 算法的时间复杂度主要集中在 ２）、３）、９）和 １０）。 利用文献［１３］ 中计数排序算法 和简 化 决 策 表 处 理 方 式， ２ ） 的 时 间 复 杂 度 为 Ｏ（｜ Ａ ｜ ｜ Ｕ ∪ Ｕ Δ ｜ ） ， ３ ） 的 时 间 复 杂 度 为 Ｏ（｜ Ｃ ｜ ｜ Ｕ ∪ Ｕ Δ ｜ ） ， ９ ） 的 时 间 复 杂 度 为 Ｏ（｜ Ｃ ｜ ｜ Ｕ′ｂｎｄ ｜ ） ， １０ ） 的 最 坏 时 间 复 杂 度 为 Ｏ（｜ Ｃ ｜ ２ ｜ ［Ｕ ∪ Ｕ Δ ］ ／ Ｃ ｜ ） ，故整个算法时间复杂 度为 ｍａｘ （ Ｏ（ ｜ Ｃ ｜ ｜ Ｕ′ｂｎｄ ｜ ） ， Ｏ（ ｜ Ｃ ｜ ２ ｜ ［Ｕ ∪ Ｕ Δ ］ ／ Ｃ ｜ ） ），空间复杂度为 Ｏ（｜ Ｕ ∪ Ｕ Δ ｜ ） 。 例 １ 表 １ 给出一个决策表 Ｓ 和新增对象集 Ｕ △ ，决 策 表 Ｓ 包 含 ３ 个 约 简 ｛ ｃ２ ｃ１ ｝、 ｛ ｃ２ ｃ３ ｝ 和 ｛ ｃ３ ｃ４ ｝，分别计算约简的变化情况，如表 ２ 所示。 表 ２ 原始决策表 Ｓ 和新增对象集 Ｕ △ Ｔａｂｌｅ ２ Ｏｒｉｇｉｎａｌ ｄｅｃｉｓｉｏｎ ｔａｂｌｅ Ｓ ａｎｄ ｎｅｗ ａｄｄｅｄ ｏｂｊｅｃｔ ｓｅｔ Ｕ △ Ｕ ｃ１ ｃ２ ｃ３ ｃ４ ｄ Ｕ △ ｃ１ ｃ２ ｃ３ ｃ４ ｄ ｘ１ １ ０ １ ０ ２ ｙ１ ２ １ ０ ０ １ ｘ２ ０ １ ０ １ ２ ｙ２ １ ０ １ ０ ４ ｘ３ １ １ １ １ ３ ｙ３ ０ １ ０ １ ２ ｘ４ １ ０ １ ０ １ ｙ４ ０ ２ １ １ １ ｘ５ ０ ２ ２ １ ２ ｙ５ ０ １ １ １ ２ ｘ６ １ ２ ０ ０ ２ ｙ６ ０ １ １ ２ １ 第 ４ 期 钱进，等：面向成组对象集的增量式属性约简算法 ·４９９·
.500. 智能系统学报 第11卷 表2约简变化与约简传承性比较 Table 2 Comparison of Reduct change and Reduct inheritance rate NewObject Case Red Red IR Red, Red IR Rede Red IR 21001 1) cact C2C1 1c2c3 C2C1 0.5 c3ca C3CAC1 1 10104 ① C2C1 C2C1 1 C2C3 C2C3 1 C3C4 C3C4 1 01012 ② C2Ci C2Ct 1 C2C3 C2C3 1 C3ca C3C4 1 02111 ② czc1 c2c 1 C2C3 C2C3 1 C3c4 c3caC1 1 01112 ③ C2C1 CaCt 1 C2C3 C2C1 0.5 C3C4 C3C4CI 1 01121 ④ C2C1 c2CiC3 1 C2C3 C2C3C1 1 C3C4 csea 1 合计 平均传承率 平均传承率 0.83 平均传承率 1 3实验验证 据集进行实验。每个数据集仅有1个决策属性。人 工数据集Datasetl每个属性值为1~5；而人工数据 为了评价所提出的增量式约简算法效率和约简 集Dataset2.每个属性值为1~9。表3描述了6个数 传承性，使用Windows7操作系统，2.4GHz处理器 据集特性。原始数据集的50%作为基本数据集，剩 和16GB内存的计算机和Visual C#2012实现了相 下50%数据集的20%、40%、60%、80%和100%作为 关实验。由于所提出的约简算法和经典的约简算法 5个增量数据集，非增量式属性约简算法(NIAR)、 仅能够处理离散型属性，先采用Rosetta软件(ht- 面向单个属性的增量式属性约简算法(SIAR)和面 tp:/www.lcb.uu.se/tools/rosetta)填充缺省值，并将 向成组数据集的属性增量式约简算法(GIAR)实验 数值型属性连续值离散化：然后，分别在4个来自 结果如图1所示。 UCI Repository机器学习公共数据集和2个人工数 105 10 103 102 10 一一 -----0 10 0- NIAR 10 -B-SIRA 一NIAR 10 GIAR 寺耀 10 10 8 100合8 10 爱 10 0…0⑨…0 1 10 2 3 5 3 4 2 3 4 增量数据集 增量数据集 增量数据巢 (a)Chess (b)mushroom (c)nursery 10 10 10 10 …0…00 104 10 -NIAR …o…GAR 10 。&S …0…0…0 。縱 10 10 … 3 4 5 2 3 3 3 3 4 5 增量数据集 增量数据集 增量数据集 (d)Connect (e)Dataset I (f)Dataset 2 图1增量式约简算法和非增量式约简算法运行时间比较 Fig.I Comparison of incremental and non-incremental Reduction algorithms on running time 由于面向单个属性的增量式约简算法(SLAR) 时间更长，而GLAR算法的运行时间明显少于NIAR 对大规模数据集运行时间太长，图1(e)-(f)未标 算法，特别对于较大数据集，算法的效果越明显。实 出。从图1可以看出，SIAR算法比GAR算法运行 验结果表明，所提出的面向成组对象集的增量式约
表 ２ 约简变化与约简传承性比较 Ｔａｂｌｅ ２ Ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｒｅｄｕｃｔ ｃｈａｎｇｅ ａｎｄ Ｒｅｄｕｃｔ ｉｎｈｅｒｉｔａｎｃｅ ｒａｔｅ ＮｅｗＯｂｊｅｃｔ Ｃａｓｅ ＲｅｄＵ ＲｅｄＵ′ ＩＲ ＲｅｄＵ ＲｅｄＵ′ ＩＲ ＲｅｄＵ ＲｅｄＵ′ ＩＲ ２１００１ １） ｃ２ ｃ１ ｃ２ ｃ１ １ ｃ２ ｃ３ ｃ２ ｃ１ ０．５ ｃ３ ｃ４ ｃ３ ｃ４ ｃ１ １ １０１０４ ① ｃ２ ｃ１ ｃ２ ｃ１ １ ｃ２ ｃ３ ｃ２ ｃ３ １ ｃ３ ｃ４ ｃ３ ｃ４ １ ０１０１２ ② ｃ２ ｃ１ ｃ２ ｃ１ １ ｃ２ ｃ３ ｃ２ ｃ３ １ ｃ３ ｃ４ ｃ３ ｃ４ １ ０２１１１ ② ｃ２ ｃ１ ｃ２ ｃ１ １ ｃ２ ｃ３ ｃ２ ｃ３ １ ｃ３ ｃ４ ｃ３ ｃ４ ｃ１ １ ０１１１２ ③ ｃ２ ｃ１ ｃ２ ｃ１ １ ｃ２ ｃ３ ｃ２ ｃ１ ０．５ ｃ３ ｃ４ ｃ３ ｃ４ ｃ１ １ ０１１２１ ④ ｃ２ ｃ１ ｃ２ ｃ１ ｃ３ １ ｃ２ ｃ３ ｃ２ ｃ３ ｃ１ １ ｃ３ ｃ４ ｃ３ ｃ４ １ 合计 平均传承率 １ 平均传承率 ０．８３ 平均传承率 １ ３ 实验验证 为了评价所提出的增量式约简算法效率和约简 传承性，使用 Ｗｉｎｄｏｗｓ ７ 操作系统，２．４ ＧＨｚ 处理器 和 １６ ＧＢ 内存的计算机和 Ｖｉｓｕａｌ Ｃ＃２０１２ 实现了相 关实验。 由于所提出的约简算法和经典的约简算法 仅能够处理离散型属性，先采用 Ｒｏｓｅｔｔａ 软件（ ｈｔ⁃ ｔｐ： ／ ／ ｗｗｗ．ｌｃｂ．ｕｕ．ｓｅ ／ ｔｏｏｌｓ／ ｒｏｓｅｔｔａ） 填充缺省值，并将 数值型属性连续值离散化；然后，分别在 ４ 个来自 ＵＣＩ Ｒｅｐｏｓｉｔｏｒｙ 机器学习公共数据集和 ２ 个人工数 据集进行实验。 每个数据集仅有 １ 个决策属性。 人 工数据集 Ｄａｔａｓｅｔ１ 每个属性值为 １ ～ ５；而人工数据 集 Ｄａｔａｓｅｔ２ 每个属性值为 １ ～ ９。 表 ３ 描述了 ６ 个数 据集特性。 原始数据集的 ５０％作为基本数据集，剩 下 ５０％数据集的 ２０％、４０％、６０％、８０％和 １００％作为 ５ 个增量数据集，非增量式属性约简算法（ＮＩＡＲ）、 面向单个属性的增量式属性约简算法（ ＳＩＡＲ） 和面 向成组数据集的属性增量式约简算法（ＧＩＡＲ）实验 结果如图 １ 所示。 图 １ 增量式约简算法和非增量式约简算法运行时间比较 Ｆｉｇ．１ Ｃｏｍｐａｒｉｓｏｎ ｏｆ ｉｎｃｒｅｍｅｎｔａｌ ａｎｄ ｎｏｎ－ｉｎｃｒｅｍｅｎｔａｌ Ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｏｎ ｒｕｎｎｉｎｇ ｔｉｍｅ 由于面向单个属性的增量式约简算法（ ＳＩＡＲ） 对大规模数据集运行时间太长，图 １（ ｅ） －（ ｆ） 未标 出。 从图 １ 可以看出，ＳＩＡＲ 算法比 ＧＩＡＲ 算法运行 时间更长，而 ＧＩＡＲ 算法的运行时间明显少于 ＮＩＡＲ 算法，特别对于较大数据集，算法的效果越明显。 实 验结果表明，所提出的面向成组对象集的增量式约 ·５００· 智 能 系 统 学 报 第 １１ 卷
第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-
简算法是可行的。 表 ３ ６ 个数据集特性 Ｔａｂｌｅ ３ Ａ ｄｅｓｃｒｉｐｔｉｏｎ ｏｆ ｓｉｘ ｄａｔａ ｓｅｔｓ 序号 数据集 对象数 属性个数 类别数 １ Ｃｈｅｓｓ ３ １９６ ３６ ２ ２ ｍｕｓｈｒｏｏｍ ８ １２４ ２２ ２ ３ ｎｕｒｓｅｒｙ １２ ９６０ ９ ５ ４ Ｃｏｎｎｅｃｔ ６７ ５５７ ４２ ３ ５ Ｄａｔａｓｅｔ１ ２００ ０００ ３０ ５ ６ Ｄａｔａｓｅｔ２ ５００ ０００ ３０ ９ 下面比较约简长度与约简的传承性。 图 ２ 给出了 ６ 个数据集在不同增长比例下的约简长度。 在 ４ 个数 据集上，约简不变，则只需要生成新增数据集的规则， 原始规则集不必重新生成，而在另外两个数据集上，约 简长度稍微增长，这主要因为新增对象与原始数据集 引起冲突，需要另外的属性集来细分原始对象，这时除 了生成新规则集外，还需要修改部分原始规则。 图 ２ 约简长度比较 Ｆｉｇ．２ Ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｒｅｄｕｃｔ ｌｅｎｇｔｈ 表 ４ 给出了约简的传承性。 从表 ４ 可以看出， 利用先前约简中信息所得到的新约简结果变化不 大，约简传承性较好。 表 ４ 约简传承性比较 Ｔａｂｌｅ ４ Ｃｏｍｐａｒｉｓｏｎ ｏｆ Ｒｅｄｕｃｔ ｉｎｈｅｒｉｔａｎｃｅ ｒａｔｅ ％ 数据集 ２０％ ４０％ ６０％ ８０％ １００％ Ｃｈｅｓｓ １００ １００ ９５．４５ ９５．４５ ９５．４５ ｍｕｓｈｒｏｏｍ １００ １００ １００ １００ １００ ｎｕｒｓｅｒｙ １００ １００ １００ １００ １００ Ｃｏｎｎｅｃｔ １００ １００ １００ １００ １００ Ｄａｔａｓｅｔ１ １００ １００ １００ １００ １００ Ｄａｔａｓｅｔ２ １００ １００ ９０．９ ９０．９ １００ ４ 结论 在数据挖掘中， 属性约简仅仅是数据预处理中 一个过程，挖掘规则才是最终的输出。 因此，充分利 用先前约简中信息不仅能够快速得到约简，而且更 容易地利用已有知识进行规则更新。 本文所提出的 面向成组对象集的增量式约简方法就是充分利用先 前约简中信息来快速更新约简，不仅具有较高的约 简传承率，而且可以快速进行增量式学习，具有良好 的实用性。 作者下一步将利用 Ｍａｐ Ｒｅｄｕｃｅ 进一步 研究大规模数据集增量式属性约简方法。 参考文献： ［１］ＰＡＷＬＡＫ Ｚ． Ｒｏｕｇｈ ｓｅｔｓ［ Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｃｏｍ⁃ ｐｕｔｅｒ ＆ ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， １９８２， １１（５）： ３４１－３５６． ［２］ ＳＫＯＷＲＯＮ Ａ， ＲＡＵＳＺＥＲ Ｃ． Ｔｈｅ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｃｅｓ ａｎｄ ｆｕｎｃｔｉｏｎｓ ｉｎ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ［Ｍ］ ／ ／ ＳＬＯＷＩＮＳＫＩ Ｒ． Ｉｎｔｅｌｌｉｇｅｎｔ Ｄｅｃｉｓｉｏｎ Ｓｕｐｐｏｒｔ， Ｈａｎｄｂｏｏｋ ｏｆ Ａｐｐｌｉｃａｔｉｏｎｓ ａｎｄ Ａｄｖａｎｃｅｓ ｏｆ ｔｈｅ Ｒｏｕｇｈ Ｓｅｔｓ Ｔｈｅｏｒｙ． Ｎｅｔｈｅｒｌａｎｄｓ： Ｓｐｒｉｎｇｅｒ， １９９２： ３１１－３６２． ［３］苗夺谦， 胡桂荣． 知识约简的一种启发式算法［ Ｊ］． 计算 机研究与发展， １９９９， ３６（６）： ６８１－６８４． ＭＩＡＯ Ｄｕｏｑｉａｎ， ＨＵ Ｇｕｉｒｏｎｇ． Ａ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｒｅ⁃ ｄｕｃｔｉｏｎ ｏｆ ｋｎｏｗｌｅｄｇｅ ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ｒｅｓｅａｒｃｈ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ， １９９９， ３６（６）： ６８１－６８４． ［４］王国胤， 于洪， 杨大春． 基于条件信息熵的决策表约简 ［Ｊ］． 计算机学报， ２００２， ２５（７）： ７５９－７６６． ＷＡＮＧ Ｇｕｏｙｉｎ， ＹＵ Ｈｏｎｇ， ＹＡＮＧ Ｄａｃｈｕｎ． Ｄｅｃｉｓｉｏｎ ｔａｂｌｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｃｏｎｄｉｔｉｏｎａｌ ｉｎｆｏｒｍａｔｉｏｎ ｅｎｔｒｏｐｙ ［Ｊ］． Ｃｈｉ⁃ ｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２００２， ２５（７）： ７５９－７６６． ［５］ＨＵ Ｆｅｎｇ， ＷＡＮＧ Ｇｕｏｙｉｎ， ＨＵＡＮＧ Ｈａｉ， ｅｔ ａｌ． Ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｅｌｅｍｅｎｔａｒｙ ｓｅｔｓ［Ｍ］ ／ ／ ＳＬＥＺＡＫ Ｄ， ＷＡＮＧ Ｇｕｏｙｉｎ， ＳＺＣＺＵＫＡ Ｍ， ｅｔ ａｌ． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １０ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｒｏｕｇｈ Ｓｅｔｓ， Ｆｕｚｚｙ Ｓｅｔｓ， Ｄａｔａ Ｍｉｎｉｎｇ， ａｎｄ Ｇｒａｎｕｌａｒ Ｃｏｍｐｕｔｉｎｇ． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ， ２００５： １８５－１９３． ［６］杨明． 一种基于改进差别矩阵的属性约简增量式更新算 法［Ｊ］． 计算机学报， ２００７， ３０（５）： ８１５－８２２． ＹＡＮＧ Ｍｉｎｇ． Ａｎ ｉｎｃｒｅｍｅｎｔａｌ ｕｐｄａｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｉｍｐｒｏｖｅｄ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ［ Ｊ］． Ｃｈｉ⁃ ｎｅｓｅ ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒｓ， ２００７， ３０（５） ８１５－８２２． ［７］冯少荣， 张东站． 一种高效的增量式属性约简算法［ Ｊ］． 控制与决策， ２０１１， ２６（４）： ４９５－５００． ＦＥＮＧ Ｓｈａｏｒｏｎｇ， ＺＨＡＮＧ Ｄｏｎｇｚｈａｎ． Ｅｆｆｅｃｔｉｖｅ ｉｎｃｒｅｍｅｎｔａｌ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ［ Ｊ］． Ｃｏｎｔｒｏｌ ａｎｄ ｄｅｃｉｓｉｏｎ， ２０１１， ２６（４）： ４９５－５００． ［８］尹林子， 阳春华， 王晓丽， 等． 基于标记可辨识矩阵的 增量式属性约简算法［ Ｊ］． 自动化学报， ２０１４， ４０（ ３）： ３９７－４０４． ＹＩＮ Ｌｉｎｚｉ， ＹＡＮＧ Ｃｈｕｎｈｕａ， ＷＡＮＧ Ｘｉａｏｌｉ， ｅｔ ａｌ． Ａｎ ｉｎ⁃ 第 ４ 期 钱进，等：面向成组对象集的增量式属性约简算法 ·５０１·
.502. 智能系统学报 第11卷 cremental algorithm for attribute reduction based on labeled [14]QIAN Jin,MIAO Duoqian,ZHANG Zehua,et al.Parallel discernibility matrix[J].Acta automatica sinica,2014,40 attribute reduction algorithms using MapReduce [J].Infor- (3):397-404. mation sciences,2014,279:671-690. [9]SHU Wenhao,SHEN Hong.Updating attribute reduction in [15]康向平，苗夺谦。一种基于概念格的集值信息系统中的 incomplete decision systems with the variation of attribute 知识获取方法[J].智能系统学报，2016,11(3)：287- set[J].International journal of approximate reasoning, 293. 2014,55(3):867-884. KANG Xiangping,MIAO Duoqian.A knowledge acquisi- [10]CHEN Hongmei,LI Tianrui,LUO Chuan,et al.A Deci- tion method based on concept latticein set-valued informa- sion-theoretic rough set approach for dynamic data mining tion systems[J].CAAI transactions on intelligent systems, []IEEE transactions on fuzzy systems,2015,23(6): 2016.11(3):287-293. 1958-1970. 作者简介： [11]LIANG Jiye,WANG Feng,DANG Chuangyin,et al.A 钱进，男，1975年生，副教授，博士， group incremental approach to feature selection applying 主要研究方向为粗糙集、粒计算、云计 rough set technique[J].IEEE transactions on knowledge 算、大数据等。发表学术论文40余篇， and data engineering,2014,26(2):294-308. 其中被SCI,EI检索20余篇。 [12]QIAN Jin,YE Feiyue,LV Ping.An incremental attribute reduction algorithm in decision table[C]//Proceedings of the 7th International Conference on Fuzzy Systems and 朱亚炎，男，1994年生，主要研究方 Knowledge Discovery FSKD).Yantai,China:IEEE, 向为粗糙集、云计算等。 2010,4:1848-1852. [13]QIAN Jin,MIAO Duoqian,ZHANG Zehua,et al.Hybrid approaches to attribute reduction based on indiscernibility and discernibility relations[].International journal of ap- proximate reasoning,2011,52(2):212-230. 2017EEE机电一体化与自动化国际会议 2017 IEEE International Conference on Mechatronics and Automation The 2017 IEEE International Conference on Mechatronics and Automation ICMA 2017)will take place in Takamat- su,Kagawa,Japan from August 6 to August 9,2017.Takamatsu is a small city located at Sikoku which is the smallest is- land in 4 main islands of Japan.Shikoku contains a lot of temples including Zentsu-ji,where one of the most famous Bud- dhists,Kukai,was born.As the host city of ICMA 2017,Takamatsu not only provides the attendees with a great venue for this event,but also an unparalled experience in the Japanese history through several historical architectures.You are cor- dially invited to join us at IEEE ICMA 2017 in Takamatsu.The objective of ICMA 2017 is to provide a forum for research- ers,educators,engineers,and government officials involved in the general areas of mechatronics,robotics,automation and sensors to disseminate their latest research results and exchange views on the future research directions of these fields. website:http://2017.ieee-icma.org/
ｃｒｅｍｅｎｔａｌ ａｌｇｏｒｉｔｈｍ ｆｏｒ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｌａｂｅｌｅｄ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｍａｔｒｉｘ［Ｊ］． Ａｃｔａ ａｕｔｏｍａｔｉｃａ ｓｉｎｉｃａ， ２０１４， ４０ （３）： ３９７－４０４． ［９］ＳＨＵ Ｗｅｎｈａｏ， ＳＨＥＮ Ｈｏｎｇ． Ｕｐｄａｔｉｎｇ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｉｎ ｉｎｃｏｍｐｌｅｔｅ ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍｓ ｗｉｔｈ ｔｈｅ ｖａｒｉａｔｉｏｎ ｏｆ ａｔｔｒｉｂｕｔｅ ｓｅｔ ［ Ｊ ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ａｐｐｒｏｘｉｍａｔｅ ｒｅａｓｏｎｉｎｇ， ２０１４， ５５（３）： ８６７－８８４． ［１０］ＣＨＥＮ Ｈｏｎｇｍｅｉ， ＬＩ Ｔｉａｎｒｕｉ， ＬＵＯ Ｃｈｕａｎ， ｅｔ ａｌ． Ａ Ｄｅｃｉ⁃ ｓｉｏｎ⁃ｔｈｅｏｒｅｔｉｃ ｒｏｕｇｈ ｓｅｔ ａｐｐｒｏａｃｈ ｆｏｒ ｄｙｎａｍｉｃ ｄａｔａ ｍｉｎｉｎｇ ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｆｕｚｚｙ ｓｙｓｔｅｍｓ， ２０１５， ２３（ ６）： １９５８－１９７０． ［１１］ ＬＩＡＮＧ Ｊｉｙｅ， ＷＡＮＧ Ｆｅｎｇ， ＤＡＮＧ Ｃｈｕａｎｇｙｉｎ， ｅｔ ａｌ． Ａ ｇｒｏｕｐ ｉｎｃｒｅｍｅｎｔａｌ ａｐｐｒｏａｃｈ ｔｏ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ａｐｐｌｙｉｎｇ ｒｏｕｇｈ ｓｅｔ ｔｅｃｈｎｉｑｕｅ ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｋｎｏｗｌｅｄｇｅ ａｎｄ ｄａｔａ ｅｎｇｉｎｅｅｒｉｎｇ， ２０１４， ２６（２）： ２９４－３０８． ［１２］ＱＩＡＮ Ｊｉｎ， ＹＥ Ｆｅｉｙｕｅ， ＬＶ Ｐｉｎｇ． Ａｎ ｉｎｃｒｅｍｅｎｔａｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｉｎ ｄｅｃｉｓｉｏｎ ｔａｂｌｅ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ７ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｆｕｚｚｙ Ｓｙｓｔｅｍｓ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ （ ＦＳＫＤ）． Ｙａｎｔａｉ， Ｃｈｉｎａ： ＩＥＥＥ， ２０１０， ４： １８４８－１８５２． ［１３］ＱＩＡＮ Ｊｉｎ， ＭＩＡＯ Ｄｕｏｑｉａｎ， ＺＨＡＮＧ Ｚｅｈｕａ， ｅｔ ａｌ． Ｈｙｂｒｉｄ ａｐｐｒｏａｃｈｅｓ ｔｏ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｉｎｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ａｎｄ ｄｉｓｃｅｒｎｉｂｉｌｉｔｙ ｒｅｌａｔｉｏｎｓ［Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ａｐ⁃ ｐｒｏｘｉｍａｔｅ ｒｅａｓｏｎｉｎｇ， ２０１１， ５２（２）： ２１２－２３０． ［１４］ＱＩＡＮ Ｊｉｎ， ＭＩＡＯ Ｄｕｏｑｉａｎ， ＺＨＡＮＧ Ｚｅｈｕａ， ｅｔ ａｌ． Ｐａｒａｌｌｅｌ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｕｓｉｎｇ ＭａｐＲｅｄｕｃｅ ［Ｊ］． Ｉｎｆｏｒ⁃ ｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２０１４， ２７９： ６７１－６９０． ［１５］康向平， 苗夺谦． 一种基于概念格的集值信息系统中的 知识获取方法［Ｊ］． 智能系统学报， ２０１６， １１（３）： ２８７－ ２９３． ＫＡＮＧ Ｘｉａｎｇｐｉｎｇ， ＭＩＡＯ Ｄｕｏｑｉａｎ． Ａ ｋｎｏｗｌｅｄｇｅ ａｃｑｕｉｓｉ⁃ ｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｃｏｎｃｅｐｔ ｌａｔｔｉｃｅｉｎ ｓｅｔ－ｖａｌｕｅｄ ｉｎｆｏｒｍａ⁃ ｔｉｏｎ ｓｙｓｔｅｍｓ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２０１６， １１（３）： ２８７－２９３． 作者简介： 钱进，男，１９７５ 年生，副教授，博士， 主要研究方向为粗糙集、粒计算、云计 算、大数据等。 发表学术论文 ４０ 余篇， 其中被 ＳＣＩ、ＥＩ 检索 ２０ 余篇。 朱亚炎，男，１９９４ 年生，主要研究方 向为粗糙集、云计算等。 ２０１７ ＩＥＥＥ 机电一体化与自动化国际会议 ２０１７ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍｅｃｈａｔｒｏｎｉｃｓ ａｎｄ Ａｕｔｏｍａｔｉｏｎ Ｔｈｅ ２０１７ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍｅｃｈａｔｒｏｎｉｃｓ ａｎｄ Ａｕｔｏｍａｔｉｏｎ （ＩＣＭＡ ２０１７） ｗｉｌｌ ｔａｋｅ ｐｌａｃｅ ｉｎ Ｔａｋａｍａｔ⁃ ｓｕ， Ｋａｇａｗａ， Ｊａｐａｎ ｆｒｏｍ Ａｕｇｕｓｔ ６ ｔｏ Ａｕｇｕｓｔ ９， ２０１７． Ｔａｋａｍａｔｓｕ ｉｓ ａ ｓｍａｌｌ ｃｉｔｙ ｌｏｃａｔｅｄ ａｔ Ｓｉｋｏｋｕ ｗｈｉｃｈ ｉｓ ｔｈｅ ｓｍａｌｌｅｓｔ ｉｓ⁃ ｌａｎｄ ｉｎ ４ ｍａｉｎ ｉｓｌａｎｄｓ ｏｆ Ｊａｐａｎ． Ｓｈｉｋｏｋｕ ｃｏｎｔａｉｎｓ ａ ｌｏｔ ｏｆ ｔｅｍｐｌｅｓ ｉｎｃｌｕｄｉｎｇ Ｚｅｎｔｓｕ⁃ｊｉ， ｗｈｅｒｅ ｏｎｅ ｏｆ ｔｈｅ ｍｏｓｔ ｆａｍｏｕｓ Ｂｕｄ⁃ ｄｈｉｓｔｓ， Ｋｕｋａｉ， ｗａｓ ｂｏｒｎ． Ａｓ ｔｈｅ ｈｏｓｔ ｃｉｔｙ ｏｆ ＩＣＭＡ ２０１７， Ｔａｋａｍａｔｓｕ ｎｏｔ ｏｎｌｙ ｐｒｏｖｉｄｅｓ ｔｈｅ ａｔｔｅｎｄｅｅｓ ｗｉｔｈ ａ ｇｒｅａｔ ｖｅｎｕｅ ｆｏｒ ｔｈｉｓ ｅｖｅｎｔ， ｂｕｔ ａｌｓｏ ａｎ ｕｎｐａｒａｌｌｅｄ ｅｘｐｅｒｉｅｎｃｅ ｉｎ ｔｈｅ Ｊａｐａｎｅｓｅ ｈｉｓｔｏｒｙ ｔｈｒｏｕｇｈ ｓｅｖｅｒａｌ ｈｉｓｔｏｒｉｃａｌ ａｒｃｈｉｔｅｃｔｕｒｅｓ． Ｙｏｕ ａｒｅ ｃｏｒ⁃ ｄｉａｌｌｙ ｉｎｖｉｔｅｄ ｔｏ ｊｏｉｎ ｕｓ ａｔ ＩＥＥＥ ＩＣＭＡ ２０１７ ｉｎ Ｔａｋａｍａｔｓｕ． Ｔｈｅ ｏｂｊｅｃｔｉｖｅ ｏｆ ＩＣＭＡ ２０１７ ｉｓ ｔｏ ｐｒｏｖｉｄｅ ａ ｆｏｒｕｍ ｆｏｒ ｒｅｓｅａｒｃｈ⁃ ｅｒｓ， ｅｄｕｃａｔｏｒｓ， ｅｎｇｉｎｅｅｒｓ， ａｎｄ ｇｏｖｅｒｎｍｅｎｔ ｏｆｆｉｃｉａｌｓ ｉｎｖｏｌｖｅｄ ｉｎ ｔｈｅ ｇｅｎｅｒａｌ ａｒｅａｓ ｏｆ ｍｅｃｈａｔｒｏｎｉｃｓ， ｒｏｂｏｔｉｃｓ， ａｕｔｏｍａｔｉｏｎ ａｎｄ ｓｅｎｓｏｒｓ ｔｏ ｄｉｓｓｅｍｉｎａｔｅ ｔｈｅｉｒ ｌａｔｅｓｔ ｒｅｓｅａｒｃｈ ｒｅｓｕｌｔｓ ａｎｄ ｅｘｃｈａｎｇｅ ｖｉｅｗｓ ｏｎ ｔｈｅ ｆｕｔｕｒｅ ｒｅｓｅａｒｃｈ ｄｉｒｅｃｔｉｏｎｓ ｏｆ ｔｈｅｓｅ ｆｉｅｌｄｓ． ｗｅｂｓｉｔｅ：ｈｔｔｐ： ／ ／ ２０１７．ｉｅｅｅ⁃ｉｃｍａ．ｏｒｇ ／ ·５０２· 智 能 系 统 学 报 第 １１ 卷