智能系统：不完备信息系统中测试代价敏感的可变精度分类粗糙集

第9卷第2期 智能系统学报 Vol.9 No.2 2014年4月 CAAI Transactions on Intelligent Systems Apr.2014 D0I:10.3969/j.issn.1673-4785.201307010 网络出版t地址：http:/www.cmki.net/kcms/doi/CNKI:23-1538/TP.20131105.1201.004.html 不完备信息系统中测试代价敏感的 可变精度分类粗糙集 鞠恒荣1，马兴斌，杨习贝12，祁云嵩，杨静宇2 (1.江苏科技大学计算机科学与工程学院，江苏镇江212003：2.南京理工大学计算机科学与技术学院，江苏南京 210094) 摘要：在不完备信息系统中，可变精度分类关系是限制容差关系的改进形式，但其并未考虑数据集中属性的测试 代价。为解决这一问题，提出了基于测试代价敏感的可变精度分类粗糙集模型。进一步地，通过分析传统启发式 算法没有考虑测试代价以及回溯算法的时间消耗等因素，提出一种新的属性重要度测量，并在此基础上设计了一 种新的启发式算法。通过实验对比分析，说明了新提出算法的有效性。 关键词：属性约简：不完备信息系统：测试代价敏感：变精度分类粗糙集 中图分类号：TP18文献标志码：A文章编号：1673-4785(2014)02-0219-05 中文引用格式：鞠恒荣，马兴斌，杨习贝，等.不完备信息系统中测试代价敏感的可变精度分类粗糙集[J].智能系统学报，2014,9 (2):219-223. 英文引用格式：JU Hengrong,MA Xingbin,YANG Xibei,etal.Test-cost-sensitive based variable precision classification rough set in incomplete information system[J].CAAI Transactions on Intelligent Systems,2014,9(2):219-223. Test-cost-sensitive based variable precision classification rough set in incomplete information system JU Hengrong',MA Xingbin',YANG Xibei2,QI Yunsong',YANG Jingyu2 (1.School of Computer Science and Engineering,Jiangsu University of Science and Technology,Zhenjiang 212003.China;2.School of Computer Science and Technology,Nanjing University of Science and Technology,Nanjing 210094,China) Abstract:In an incomplete information system,the precision-variable classification relation is an improvement of the limited tolerance relation.However,the test costs of the data concentration attributes are not taken into account. To solve this problem,a test-cost-sensitive-based precision-variable precision classification rough set is proposed. Furthermore,the traditional heuristic algorithm does not take the importance of the test costs of the attributes into account,and backtracking algorithm is very time-consuming.Therefore,not only was a new importance of the at- tribute proposed,but a new heuristic algorithm was also presented for obtaining reduction with minor test costs.The experimental results show the effectiveness of the new algorithm by comparing it with the other algorithms. Keywords:attribute reduction;incomplete information system:test cost sensitive;variable precision classification rough set 作为一种处理不精确、不确定性问题的数学工 出后便受到了广泛关注2。然而由于数据测量的误 具，粗糙集理论(rough set)由波兰学者Pawlak提 差、数据获取的限制等原因，导致了所面临的信息系 统往往是不完备的。为处理这类问题，王国胤)提出 收稿日期：2013-07-05.网络出版日期：2013-11-05. 了限制容差关系。进一步，杨习贝[提出了一种新的 基金项目：国家自然科学基金资助项目(61100116,61203024)；江苏省 自然科学基金资助项目(BK2011492,BK2012700):江苏省 基于可变精度分类的拓展粗糙集模型，对限制容差 高校自然科学基金资助项目(11KJB520004,13KB520003): 高维信息智能感知与系统教育部重点实验室（南京理工大 关系进行了改进。然而，在实际工程应用中，数据的 学)基金资助项目(30920130122005)：江苏省普通高校研究 获取是需要付出一些成本或代价的，称其为测试代 生科研创新计划项目资助项目(CXLX13707). 通信作者：杨习贝.E-mail:yangxibei@hotmail.com 价。针对该问题，Mi等[率先将测试代价引入到

第 ９ 卷第 ２ 期 智 能 系 统 学 报 Ｖｏｌ．９ №．２ ２０１４ 年 ４ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ａｐｒ． ２０１４ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１３０７０１０ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｏｉ ／ ＣＮＫＩ：２３⁃１５３８ ／ ＴＰ．２０１３１１０５．１２０１．００４．ｈｔｍｌ 不完备信息系统中测试代价敏感的 可变精度分类粗糙集 鞠恒荣１ ，马兴斌１ ，杨习贝１，２ ，祁云嵩１ ，杨静宇２ （１．江苏科技大学 计算机科学与工程学院，江苏 镇江 ２１２００３； ２． 南京理工大学 计算机科学与技术学院，江苏 南京 ２１００９４） 摘 要：在不完备信息系统中， 可变精度分类关系是限制容差关系的改进形式， 但其并未考虑数据集中属性的测试 代价。 为解决这一问题， 提出了基于测试代价敏感的可变精度分类粗糙集模型。 进一步地， 通过分析传统启发式 算法没有考虑测试代价以及回溯算法的时间消耗等因素， 提出一种新的属性重要度测量， 并在此基础上设计了一 种新的启发式算法。 通过实验对比分析，说明了新提出算法的有效性。 关键词：属性约简；不完备信息系统；测试代价敏感；变精度分类粗糙集 中图分类号： ＴＰ１８ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１４）０２⁃０２１９⁃０５ 中文引用格式：鞠恒荣，马兴斌，杨习贝，等． 不完备信息系统中测试代价敏感的可变精度分类粗糙集［ Ｊ］． 智能系统学报， ２０１４， ９ （２）： ２１９⁃２２３． 英文引用格式：ＪＵ Ｈｅｎｇｒｏｎｇ，ＭＡ Ｘｉｎｇｂｉｎ， ＹＡＮＧ Ｘｉｂｅｉ， ｅｔ ａｌ． Ｔｅｓｔ⁃ｃｏｓｔ⁃ｓｅｎｓｉｔｉｖｅ ｂａｓｅｄ ｖａｒｉａｂｌｅ ｐｒｅｃｉｓｉｏｎ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｒｏｕｇｈ ｓｅｔ ｉｎ ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１４， ９（２）： ２１９⁃２２３． Ｔｅｓｔ⁃ｃｏｓｔ⁃ｓｅｎｓｉｔｉｖｅ ｂａｓｅｄ ｖａｒｉａｂｌｅ ｐｒｅｃｉｓｉｏｎ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｒｏｕｇｈ ｓｅｔ ｉｎ ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ ＪＵ Ｈｅｎｇｒｏｎｇ １ ， ＭＡ Ｘｉｎｇｂｉｎ １ ， ＹＡＮＧ Ｘｉｂｅｉ １，２ ， ＱＩ Ｙｕｎｓｏｎｇ １ ， ＹＡＮＧ Ｊｉｎｇｙｕ ２ （１． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， Ｊｉａｎｇｓｕ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｚｈｅｎｊｉａｎｇ ２１２００３， Ｃｈｉｎａ； ２． Ｓｃｈｏｏｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｎａｎｊｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， Ｎａｎｊｉｎｇ ２１００９４， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ａｎ ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ， ｔｈｅ ｐｒｅｃｉｓｉｏｎ⁃ｖａｒｉａｂｌｅ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｒｅｌａｔｉｏｎ ｉｓ ａｎ ｉｍｐｒｏｖｅｍｅｎｔ ｏｆ ｔｈｅ ｌｉｍｉｔｅｄ ｔｏｌｅｒａｎｃｅ ｒｅｌａｔｉｏｎ． Ｈｏｗｅｖｅｒ， ｔｈｅ ｔｅｓｔ ｃｏｓｔｓ ｏｆ ｔｈｅ ｄａｔａ ｃｏｎｃｅｎｔｒａｔｉｏｎ ａｔｔｒｉｂｕｔｅｓ ａｒｅ ｎｏｔ ｔａｋｅｎ ｉｎｔｏ ａｃｃｏｕｎｔ． Ｔｏ ｓｏｌｖｅ ｔｈｉｓ ｐｒｏｂｌｅｍ， ａ ｔｅｓｔ⁃ｃｏｓｔ⁃ｓｅｎｓｉｔｉｖｅ⁃ｂａｓｅｄ ｐｒｅｃｉｓｉｏｎ⁃ｖａｒｉａｂｌｅ ｐｒｅｃｉｓｉｏｎ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｒｏｕｇｈ ｓｅｔ ｉｓ ｐｒｏｐｏｓｅｄ． Ｆｕｒｔｈｅｒｍｏｒｅ， ｔｈｅ ｔｒａｄｉｔｉｏｎａｌ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ｄｏｅｓ ｎｏｔ ｔａｋｅ ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｏｆ ｔｈｅ ｔｅｓｔ ｃｏｓｔｓ ｏｆ ｔｈｅ ａｔｔｒｉｂｕｔｅｓ ｉｎｔｏ ａｃｃｏｕｎｔ， ａｎｄ ｂａｃｋｔｒａｃｋｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｓ ｖｅｒｙ ｔｉｍｅ⁃ｃｏｎｓｕｍｉｎｇ． Ｔｈｅｒｅｆｏｒｅ， ｎｏｔ ｏｎｌｙ ｗａｓ ａ ｎｅｗ ｉｍｐｏｒｔａｎｃｅ ｏｆ ｔｈｅ ａｔ⁃ ｔｒｉｂｕｔｅ ｐｒｏｐｏｓｅｄ， ｂｕｔ ａ ｎｅｗ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ｗａｓ ａｌｓｏ ｐｒｅｓｅｎｔｅｄ ｆｏｒ ｏｂｔａｉｎｉｎｇ ｒｅｄｕｃｔｉｏｎ ｗｉｔｈ ｍｉｎｏｒ ｔｅｓｔ ｃｏｓｔｓ． Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｓｈｏｗ ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｂｙ ｃｏｍｐａｒｉｎｇ ｉｔ ｗｉｔｈ ｔｈｅ ｏｔｈｅｒ ａｌｇｏｒｉｔｈｍｓ． Ｋｅｙｗｏｒｄｓ：ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ； ｉｎｃｏｍｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍ； ｔｅｓｔ ｃｏｓｔ ｓｅｎｓｉｔｉｖｅ； ｖａｒｉａｂｌｅ ｐｒｅｃｉｓｉｏｎ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｒｏｕｇｈ ｓｅｔ 收稿日期：２０１３⁃０７⁃０５． 网络出版日期：２０１３⁃１１⁃０５． 基金项目：国家自然科学基金资助项目（６１１００１１６， ６１２０３０２４）； 江苏省 自然科学基金资助项目（ＢＫ２０１１４９２， ＢＫ２０１２７００）；江苏省 高校自然科学基金资助项目（１１ＫＪＢ５２０００４， １３ＫＪＢ５２０００３）； 高维信息智能感知与系统教育部重点实验室（南京理工大 学）基金资助项目（３０９２０１３０１２２００５）；江苏省普通高校研究 生科研创新计划项目资助项目（ＣＸＬＸ１３＿７０７）． 通信作者：杨习贝． Ｅ⁃ｍａｉｌ：ｙａｎｇｘｉｂｅｉ＠ ｈｏｔｍａｉｌ．ｃｏｍ． 作为一种处理不精确、不确定性问题的数学工 具， 粗糙集理论［１］ （ｒｏｕｇｈ ｓｅｔ）由波兰学者 Ｐａｗｌａｋ 提 出后便受到了广泛关注［２⁃４］ 。 然而由于数据测量的误 差、数据获取的限制等原因， 导致了所面临的信息系 统往往是不完备的。 为处理这类问题， 王国胤［５］提出 了限制容差关系。 进一步，杨习贝［６］提出了一种新的 基于可变精度分类的拓展粗糙集模型， 对限制容差 关系进行了改进。 然而， 在实际工程应用中， 数据的 获取是需要付出一些成本或代价的， 称其为测试代 价。 针对该问题， Ｍｉｎ 等［７⁃１１］率先将测试代价引入到

·220 智能系统学报 第9卷 粗糙集的约简问题中，终究未能将测试代价引入到不 策系统，其中AcAr,x,y∈U,Va∈A,定义特征 完备信息系统环境下粗糙集本身的近似模型上。 函数如下所示： 1基本概念 1:P.(x）≠0 8.(x)= 0:P(x)=0 形式化地，信息系统可表示为四元组1、=〈U, 1:P.(x)nP.(y)≠0 A,V,月，其中U={x1,x2,…,xm}为研究对象的 o.(x,y)= 0:P(x)nP.(y)=☑ 有限集合，称为论域；A7={a1,a2,…,an}为描述 式中：P.(x)={aeA:f(x,a)已知}。 对象的全部属性所组成的集合；V=U。'为属性 定义5设TCSIIDS为测试代价敏感不完备决 集合A,的值域，其中Vn为属性a的值域；f:U×A7 策系统，其中AA,由A决定的可变精度分类关 V为信息函数，表示对每一个x∈U,a∈Ar,f(x, 系记为”且 a)∈V,。特别地，当信息系统中属性集A=A,UD且 Va=(x,y)EU:Va EP (x)np(y) A,∩D=⑦（其中A,为条件属性集合，D为决策属性 集合)时，信息系统也被称为决策系统。 ∑e(a)x.x) f(x,a)=f(y,a) ≥aUI 定义1)设S为不完备信息系统，ACA, 三e06 由A决定的可变精度分类关系记为：，且 其中：a∈[0,1]。 a={(x,y)∈U:a∈P4(x)∩P(y), 定义6设TCSIIDS为测试代价敏感不完备决策 P(x)∩Py) f (x,a)=f(y,a)- -≥aUIu 系统，ACA,对于VXcU,X基于可变精度分类关系 I P(x)I ·的下、上近似集分别记为4g`(X)和M(X) (1) 式中：P(x)={a∈A:f(x,a)已知}，a∈[0,1]， 4g.e`(X)={x∈U:Ve∴(x)cX} IXI表示集合X的基数，Iu为恒等关系且Iu= A(X)={x∈U:.(x)∩X≠0列 {(x,x):x∈U}。 式中：e(x)={y∈U:(x,y)ee}表示在测 定义26)设S为不完备信息系统，A二A7, 试代价敏感不完备决策系统中对象x的可变精度容 对于任意的XU,X基于可变精度分类关系：的 差类。 下、上近似集合分别记为A(X)和A(X): 3属性约简 A(X)={x∈U:(x)cX} 属性约简是粗糙理论的主要研究内容之一。然 A(X)={x∈U:(x)∩X☑} 而，寻找决策表的最小约简已被证明是一个NP-hard 式中：(x)={y∈U:(x,y)∈}表示对象x的 问题，在处理大规模数据时计算时间代价很大，针对 可变精度容差类。 这一问题，许多学者提出了许多高效的约简算法，启 2测试代价与可变精度分类粗糙集 发式搜索方法就是其中的一个典型代表。 定义7设TCSIIDS为测试代价敏感不完备决 不完备信息系统环境下的粗糙集模型未考虑数 据的代价问题，Mi等]将测试代价引入到信息系 策系统，a∈[0,1]，U/IND(D)={X1,,Xn}表示 根据决策属性得到的所有决策类的合集，那么U/ 统中，具体的描述见定义3。 定义3[劉一个测试代价敏感的不完备决策系 ND(D)的近似质量可定义为 统TCSIIDS为一个五元组(U,AUD,V,f,c·〉， y(A,a,D)=1U{Ag(X):1≤j≤m}I/1UI U,A,UD,V和f的含义与第1节所示相同， 定理1令TCSIDS为测试代价敏感不完备决 c°：Ar={a1,a2,…,an}→R*U{0}为测试代价函 策系统，AcAT,若00,a:eAro (A,a,D)=y(AT,a,D)且HBCA,y(B,,D)≠ 定义4令TCSIDS为测试代价敏感不完备决 y(A,&,D)

粗糙集的约简问题中，终究未能将测试代价引入到不 完备信息系统环境下粗糙集本身的近似模型上。 １ 基本概念 形式化地， 信息系统可表示为四元组 ＩＳ ＝ 〈Ｕ， ＡＴ， Ｖ， ｆ〉， 其中 Ｕ＝｛ｘ１ ， ｘ２ ， … ， ｘｍ ｝为研究对象的 有限集合， 称为论域； ＡＴ ＝ ｛ａ１ ， ａ２ ， … ， ａｎ ｝为描述 对象的全部属性所组成的集合； Ｖ ＝ ∪ ａ Î ＡＴ Ｖａ为属性 集合 ＡＴ 的值域， 其中 Ｖａ为属性 ａ 的值域； ｆ ： Ｕ ´ＡＴ ®Ｖ 为信息函数， 表示对每一个 ｘ ÎＵ， ａ ÎＡＴ， ｆ（ｘ， ａ）ÎＶａ 。 特别地， 当信息系统中属性集 Ａ ＝ ＡＴ∪Ｄ 且 ＡＴ∩Ｄ＝Æ（其中 ＡＴ 为条件属性集合， Ｄ 为决策属性 集合）时， 信息系统也被称为决策系统。 定义 １ ［６］ 设 Ｓ 为不完备信息系统， "Ａ ÍＡＴ ， 由 Ａ 决定的可变精度分类关系记为 Ｖ α Ａ ，且 Ｖ α Ａ ＝ ｛（ｘ， ｙ） ÎＵ ２ ： "ａ ÎＰＡ（ｘ） ∩ ＰＡ（ｙ）， ｆ （ｘ， ａ） ＝ ｆ （ｙ， ａ） Ù ｜ ＰＡ（ｘ） ∩ＰＡ（ｙ） ｜ ｜ ＰＡ（ｘ） ｜ ≥α｝ ∪ＩＵ （１） 式中：ＰＡ（ｘ） ＝ ｛ａ ÎＡ： ｆ （ｘ， ａ）已知｝， α Î［０， １］， ｜ Ｘ ｜ 表示集合 Ｘ 的基数， ＩＵ 为恒等关系且 ＩＵ ＝ ｛（ｘ， ｘ）： ｘ ÎＵ｝。 定义 ２ ［６］ 设 Ｓ 为不完备信息系统，"Ａ ÍＡＴ ， 对于任意的 Ｘ ÍＵ， Ｘ 基于可变精度分类关系 Ｖ α Ａ 的 下、上近似集合分别记为Ａ－ α Ｖ（Ｘ）和Ａ － α Ｖ（Ｘ）： Ａ－ α Ｖ（Ｘ） ＝ ｛ｘ ÎＵ ： Ｖ α Ａ（ｘ） ÍＸ｝ Ａ － α Ｖ（Ｘ） ＝ ｛ｘ ÎＵ ：Ｖ α Ａ（ｘ） ∩ Ｘ ¹Æ｝ 式中：Ｖ α Ａ（ｘ） ＝ ｛ｙ ÎＵ ： （ ｘ， ｙ）ÎＶ α Ａ ｝表示对象 ｘ 的 可变精度容差类。 ２ 测试代价与可变精度分类粗糙集 不完备信息系统环境下的粗糙集模型未考虑数 据的代价问题， Ｍｉｎ 等［８］将测试代价引入到信息系 统中， 具体的描述见定义 ３。 定义 ３ ［８］ 一个测试代价敏感的不完备决策系 统 ＴＣＳＩＩＤＳ 为一个五元组〈Ｕ， ＡＴ∪Ｄ， Ｖ， ｆ， ｃ ∗ 〉， Ｕ， ＡＴ ∪ Ｄ， Ｖ 和 ｆ 的 含 义 与 第 １ 节 所 示 相 同， ｃ ∗ ： ＡＴ ＝ ｛ａ１ ， ａ２ ，…，ａｎ ｝®Ｒ ＋ ∪｛０｝ 为测试代价函 数（Ｒ ＋表示正整数集）， 即 ｃ ∗ （ ＡＴ ） ＝ ∑ ｜ ＡＴ ｜ ｉ ＝ １ ｃ ∗ （｛ ａｉ ｝）， 其中 ｃ ∗ （｛ ａｉ｝）表示单个属性 ａｉ的测试代价。 本文 假设 所 有 属 性 的 测 试 代 价 均 为 正 整 数， 即 ｃ ∗ （｛ａｉ｝）>０， ａｉÎＡＴ 。 定义 ４ 令 ＴＣＳＩＩＤＳ 为测试代价敏感不完备决 策系统， 其中 Ａ ÍＡＴ ， "ｘ， ｙ ÎＵ， "ａ ÎＡ， 定义特征 函数如下所示： δ ａ（ｘ） ＝ １：Ｐａ（ｘ） ≠ Æ {０：Ｐａ（ｘ） ＝ Æ φａ（ｘ，ｙ） ＝ １：Ｐａ（ｘ） ∩ Ｐａ（ｙ） ≠ Æ {０：Ｐａ（ｘ） ∩ Ｐａ（ｙ） ＝ Æ 式中： Ｐａ（ｘ） ＝ ｛ａ ÎＡ： ｆ （ｘ， ａ）已知｝。 定义 ５ 设 ＴＣＳＩＩＤＳ 为测试代价敏感不完备决 策系统， 其中 Ａ ÍＡＴ ， 由 Ａ 决定的可变精度分类关 系记为 Ｖ α，ｃ∗ Ａ 且 Ｖ α，ｃ∗ Ａ ＝ ｛（ｘ，ｙ） ÎＵ ２ ： "ａ ÎＰａ（ｘ） ∩ Ｐａ（ｙ） ｆ （ｘ， ａ）＝ ｆ （ｙ， ａ） Ù ∑ａ∈Ａ （ｃ ∗ （ａ） × φａ（ｘ，ｙ）） ∑ａ∈Ａ （ｃ ∗ （ａ） × δａ（ｘ）） ≥α｝ ∪ＩＵ 其中：α Î［０， １ ]。 定义 ６ 设 ＴＣＳＩＩＤＳ 为测试代价敏感不完备决策 系统， Ａ ÍＡＴ， 对于"Ｘ ÍＵ， Ｘ 基于可变精度分类关系 Ｖ α，ｃ∗ Ａ 的下、上近似集分别记为Ａ－ α，ｃ∗ Ｖ （Ｘ）和Ａ － α，ｃ∗ Ｖ （Ｘ） Ａ－ α，ｃ∗ Ｖ （Ｘ）＝ ｛ｘ ÎＵ： Ｖ α，ｃ∗ Ａ （ｘ）ÍＸ｝ Ａ － α，ｃ∗ Ｖ （Ｘ）＝ ｛ｘ ÎＵ： Ｖ α，ｃ∗ Ａ （ｘ）∩Ｘ ¹Æ｝ { 式中：Ｖ α，ｃ∗ Ａ （ｘ） ＝ ｛ｙ ÎＵ： （ｘ， ｙ） ÎＶ α，ｃ∗ Ａ ｝表示在测 试代价敏感不完备决策系统中对象 ｘ 的可变精度容 差类。 ３ 属性约简 属性约简是粗糙理论的主要研究内容之一。 然 而， 寻找决策表的最小约简已被证明是一个 ＮＰ⁃ｈａｒｄ 问题， 在处理大规模数据时计算时间代价很大， 针对 这一问题， 许多学者提出了许多高效的约简算法， 启 发式搜索方法就是其中的一个典型代表。 定义 ７ 设 ＴＣＳＩＩＤＳ 为测试代价敏感不完备决 策系统， α Î［０， １］， Ｕ／ ＩＮＤ（Ｄ）＝ ｛Ｘ１ ，¼，Ｘｎ ｝表示 根据决策属性得到的所有决策类的合集， 那么 Ｕ／ ＩＮＤ（Ｄ）的近似质量可定义为 γ（Ａ， α， Ｄ） ＝ ｜ ∪ ｛Ａ － α，ｃ∗ Ｖ （Ｘｊ）：１ ≤ ｊ ≤ ｍ｝ ｜ ／ ｜ Ｕ ｜ 定理 １ 令 ＴＣＳＩＩＤＳ 为测试代价敏感不完备决 策系统， "Ａ ÍＡＴ， 若 ０ <α１<α２<１， 则有 γ（Ａ， α１ ， Ｄ） ≤ γ（Ａ， α２ ， Ｄ） 证明 根据定义 ６， 定理 １ 易证。 定义 ８ 令 ＴＣＳＩＩＤＳ 为测试代价敏感不完备决 策系统， α Î［０， １］， Ａ ÍＡＴ 为一个约简当且仅当 γ （Ａ， α， Ｄ） ＝ γ（ＡＴ， α， Ｄ）且"Ｂ ÌＡ， γ（Ｂ， α， Ｄ）¹ γ（Ａ， α， Ｄ）。 ·２２０· 智 能 系 统 学 报 第 ９ 卷

第2期 鞠恒荣，等：不完备信息系统中测试代价敏感的可变精度分类粗糙集 .221. 令TCSIIDS为测试代价敏感决策系统，ae[0, 2)red←-g 1],VACAT,aeA,a,的重要度为 3)Ha:eA7,计算属性a:的重要度TCSLSigin(a:, LSigin (ai,A,D)=y(A,a,D)-y(A-a;,a,D) ArD); 可以看出，LSign(a,B,D)反映了a,从当前条 4)TCSLSigin (a;,Ar,D)=max TCSISigin (a:, 件属性集A中删除后近似质量的变化，相应地也可 Ar,D):a:eA,},则red←-a,计算y(red,a,D): 定义 5)若y(ed,a,D)y(Az,a,D),则重复以下循 ISig(a;,A,D)=y(A U a;,a,D)-y(A,a,D) 环，否则转6)； 式中：a,∈A,-A,LSig(a:,A,D)用以度量向属性集A ①Va,eA,-red,计算TCSLSig(a:,red,D); 增加属性α，后近似质量的变化。根据上述属性的重要 ②若TCSLSig,(a:,B,D)=max{TCSLSigou(a:, 度可以设计启发式属性约简算法。Min等在文献[11] B,D):a,∈A,-red},则red←-a:; 中设计了传统的启发式算法（记为算法1）。其算法复 6)a:∈red,若y(red-a:,a,D)=y(Ar,a,D), 14 杂度为0(1A,IU1+∑1U1(1A,1-i+1)。 red red-a:,tmp =c'(red); 7)c'(red)=minc'(red),tmp Min等从获取约简的测试代价最小出发设计出 8)若0大于给定阈值，则0=0-6（此处8为步 新的约简算法，即回溯算法（记为算法2）。其算法 长，6>0)且重复2)~7)，否则转9)： 复杂度为0(2r-1)。详细算法见文献[11]。 9)输出red及c·(red)。 3.1考虑属性测试代价的启发式算法 3.2实验分析 由上文可知回溯算法的时间复杂度为O(24- 本节将通过实验，对比算法1、算法2和算法 1)。考虑到现实生活中存在着大量高维属性的数据， 3。表1列出了实验中使用的4组测试数据的基本 这样一种机制将会大大制约属性约简的时间。为解 信息，所有数据集均下载于UCI数据集。由于UCI 决这一问题，本文依然从启发式算法的角度出发，将 数据集中的大部分数据不含有测试代价，所以在本 属性的测试代价考虑到属性重要度定义中。为此，给 组实验中为每个数据集的属性随机增加了取值在 出如下的属性融合重要度定义。 [10,100]之间的测试代价。 TCSLSigin(a:,Ar,D)= 表1实验数据基本信息 0.1×LSigi(a,A7,D)+0.9×(c·(a:))° Table 1 Data sets descriptions TCSLSig (a:,Ar,D)= Decision 0.1 xLSig.(a,A7,D)+0.9×(c(a))° Data ID Data sets Samples Attributes Classes 式中：0≤0。可以看出，TCSLSig..(a:,A7,D)是LSig 1 Bridges 108 12 1 2 Credit Approval 263 3 (a:,A,D)与(c(a:)”之和。当9=0时，无论属性 3 Heart-Disease 303 14 的测试代价取何值，都有TCSLSigin(a:,Ar,D)=0.1× 4 Hepatitis 155 19 2 LSig(a:,A,D)+1,这说明TCSLSig.(a:,A7,D)的大 由于基于测试代价敏感的可变精度分类粗糙集 小与属性测试代价的大小无关，仅与LSig.(a:,Ar, 模型的下、上近似集由阈值α控制，因此，在实验 D)的值有关。随着0值的不断减小，(c(a:))°的值 中选取了10组不同的α值分别对比3个算法的测 也不断减小（本文随机产生测试代价在[10,100]）， 试代价，在算法3的第8步中，给定阈值设为-5， 此时(c(a:)°在TCSLSig.(a:,A7,D)中所占的比重 步长δ为0.5，即重复求得10次约简，取其中的最 也越来越小，表明属性测试代价在属性的重要度中 小测试代价作为输出。具体的实验结果见图1。 的影响作用越来越小。根据新的属性融合重要度， ×109 7 不难设计出综合考虑了测试代价的启发式算法，具 算法1 6 算法2 体算法流程见算法1。 ★ 24 算法3 算法1基于测试代价敏感不完备决策系统 TCSIIDS综合考虑测试代价的启发式算法 输入：测试代价敏感不完备决策系统TCSIIDS,a; 0 0.10.20.30.40.50.60.70.80.91.0 输出：约简red及约简的测试代价c·(red)。 1)计算y(4,a,D):令=0，c(d)=c(4): (a)Bridges

令 ＴＣＳＩＩＤＳ 为测试代价敏感决策系统， α Î［０， １］， "Ａ ÍＡＴ， "ａｉÎＡ， ａｉ的重要度为 ＬＳｉｇｉｎ（ａｉ， Ａ， Ｄ） ＝ γ（Ａ， α， Ｄ） -γ（Ａ -ａｉ， α， Ｄ） 可以看出， ＬＳｉｇｉｎ（ａｉ， Ｂ， Ｄ）反映了 ａｉ从当前条 件属性集 Ａ 中删除后近似质量的变化， 相应地也可 定义 ＬＳｉｇｏｕｔ（ａｉ， Ａ， Ｄ） ＝ γ（Ａ ∪ ａｉ， α， Ｄ） -γ（Ａ， α， Ｄ） 式中：ａｉÎＡＴ -Ａ， ＬＳｉｇｏｕｔ（ａｉ，Ａ， Ｄ）用以度量向属性集 Ａ 增加属性 ａｉ后近似质量的变化。 根据上述属性的重要 度可以设计启发式属性约简算法。 Ｍｉｎ 等在文献［１１］ 中设计了传统的启发式算法（记为算法 １）。 其算法复 杂度为 Ｏ（ ｜ＡＴ ｜ ｜Ｕ｜ ＋∑ ｜ ＡＴ ｜ ｉ ＝ １ ｜Ｕ｜（ ｜ＡＴ ｜ -ｉ＋１））。 Ｍｉｎ 等从获取约简的测试代价最小出发设计出 新的约简算法， 即回溯算法（记为算法 ２）。 其算法 复杂度为 Ｏ（２ ｜ ＡＴ ｜ -１）。 详细算法见文献［１１］。 ３．１ 考虑属性测试代价的启发式算法 由上文可知回溯算法的时间复杂度为 Ｏ（２ ｜ ＡＴ ｜ - １）。 考虑到现实生活中存在着大量高维属性的数据， 这样一种机制将会大大制约属性约简的时间。 为解 决这一问题， 本文依然从启发式算法的角度出发， 将 属性的测试代价考虑到属性重要度定义中。 为此， 给 出如下的属性融合重要度定义。 ＴＣＳＬＳｉｇｉｎ（ａｉ， ＡＴ ， Ｄ） ＝ ０．１ ´ＬＳｉｇｉｎ（ａｉ， ＡＴ ， Ｄ） ＋ ０．９ ´（ｃ ∗ （ａｉ）） θ ＴＣＳＬＳｉｇｏｕｔ（ａｉ， ＡＴ ， Ｄ） ＝ ０．１ ´ＬＳｉｇｏｕｔ（ａｉ， ＡＴ ， Ｄ） ＋ ０．９ ´（ｃ ∗ （ａｉ）） θ 式中：θ≤ ０。 可以看出， ＴＣＳＬＳｉｇｉｎ（ａｉ，ＡＴ，Ｄ）是 ＬＳｉｇｉｎ （ａｉ， ＡＴ， Ｄ）与（ｃ ∗ （ａｉ）） θ 之和。 当 θ＝ ０ 时， 无论属性 的测试代价取何值， 都有 ＴＣＳＬＳｉｇｉｎ（ａｉ，ＡＴ，Ｄ）＝ ０．１ ´ ＬＳｉｇｉｎ （ａｉ，ＡＴ，Ｄ）＋１， 这说明 ＴＣＳＬＳｉｇｉｎ（ａｉ，ＡＴ，Ｄ）的大 小与属性测试代价的大小无关， 仅与 ＬＳｉｇｉｎ （ａｉ，ＡＴ， Ｄ）的值有关。 随着 θ 值的不断减小， （ｃ ∗ （ａｉ）） θ 的值 也不断减小（本文随机产生测试代价在［１０， １００］）， 此时（ｃ ∗ （ａｉ）） θ 在 ＴＣＳＬＳｉｇｉｎ（ａｉ，ＡＴ，Ｄ）中所占的比重 也越来越小， 表明属性测试代价在属性的重要度中 的影响作用越来越小。 根据新的属性融合重要度， 不难设计出综合考虑了测试代价的启发式算法， 具 体算法流程见算法 １。 算法 １ 基于测试代价敏感不完备决策系统 ＴＣＳＩＩＤＳ 综合考虑测试代价的启发式算法 输入：测试代价敏感不完备决策系统 ＴＣＳＩＩＤＳ， α； 输出：约简 ｒｅｄ 及约简的测试代价 ｃ ∗ （ｒｅｄ）。 １）计算 γ（ＡＴ， α， Ｄ）； 令θ＝０， ｃ ∗ （ｒｅｄ）＝ ｃ ∗ （ＡＴ）； ２） ｒｅｄ ¬Æ； ３）"ａｉÎＡＴ ， 计算属性 ａｉ的重要度 ＴＣＳＬＳｉｇｉｎ（ａｉ， ＡＴ ，Ｄ）； ４）若 ＴＣＳＬＳｉｇｉｎ（ａｊ，ＡＴ，Ｄ） ＝ ｍａｘ｛ＴＣＳＬＳｉｇｉｎ（ａｉ， ＡＴ，Ｄ）： ａｉÎＡＴ｝， 则 ｒｅｄ ¬ａｊ，计算 γ（ｒｅｄ，α，Ｄ）； ５）若 γ（ｒｅｄ，α，Ｄ）¹γ（ＡＴ ，α，Ｄ）， 则重复以下循 环， 否则转 ６）； ①"ａｉÎＡＴ -ｒｅｄ，计算 ＴＣＳＬＳｉｇｏｕｔ（ａｉ，ｒｅｄ，Ｄ）； ②若 ＴＣＳＬＳｉｇｏｕｔ（ａｉ，Ｂ，Ｄ） ＝ ｍａｘ｛ＴＣＳＬＳｉｇｏｕｔ（ ａｉ， Ｂ，Ｄ）： ａｉÎＡＴ -ｒｅｄ｝，则 ｒｅｄ ¬ａｉ； ６）"ａｉÎｒｅｄ， 若 γ（ｒｅｄ -ａｉ，α，Ｄ）＝ γ（ＡＴ ，α，Ｄ）， 则 ｒｅｄ ＝ ｒｅｄ -ａｉ， ｔｍｐ ＝ ｃ ∗ （ｒｅｄ）； ７）ｃ ∗ （ｒｅｄ）＝ ｍｉｎ｛ｃ ∗ （ｒｅｄ）， ｔｍｐ｝； ８）若 θ 大于给定阈值， 则 θ ＝ θ -δ（此处 δ 为步 长，δ＞０）且重复 ２） ～７），否则转 ９）； ９）输出 ｒｅｄ 及 ｃ ∗ （ｒｅｄ）。 ３．２ 实验分析 本节将通过实验， 对比算法 １、算法 ２ 和算法 ３。 表 １ 列出了实验中使用的 ４ 组测试数据的基本 信息， 所有数据集均下载于 ＵＣＩ 数据集。 由于 ＵＣＩ 数据集中的大部分数据不含有测试代价， 所以在本 组实验中为每个数据集的属性随机增加了取值在 ［１０， １００］之间的测试代价。 表 １ 实验数据基本信息 Ｔａｂｌｅ １ Ｄａｔａ ｓｅｔｓ ｄｅｓｃｒｉｐｔｉｏｎｓ Ｄａｔａ ＩＤ Ｄａｔａ ｓｅｔｓ Ｓａｍｐｌｅｓ Ａｔｔｒｉｂｕｔｅｓ Ｄｅｃｉｓｉｏｎ Ｃｌａｓｓｅｓ １ Ｂｒｉｄｇｅｓ １０８ １２ ７ ２ Ｃｒｅｄｉｔ Ａｐｐｒｏｖａｌ ２６３ １５ ３ ３ Ｈｅａｒｔ⁃Ｄｉｓｅａｓｅ ３０３ １４ ５ ４ Ｈｅｐａｔｉｔｉｓ １５５ １９ ２ 由于基于测试代价敏感的可变精度分类粗糙集 模型的下、上近似集由阈值 α 控制， 因此， 在实验 中选取了 １０ 组不同的 α 值分别对比 ３ 个算法的测 试代价， 在算法 ３ 的第 ８ 步中， 给定阈值设为－５， 步长 δ 为 ０．５， 即重复求得 １０ 次约简， 取其中的最 小测试代价作为输出。 具体的实验结果见图 １。 （ａ）Ｂｒｉｄｇｅｓ 第 ２ 期 鞠恒荣，等：不完备信息系统中测试代价敏感的可变精度分类粗糙集 ·２２１·

.222. 智能系统学报 第9卷 ×10 的启发式算法用以获取测试代价次优的约简。实验 10r 算法1 表明，总体而言，改进的启发式算法是寻找约简测 ·一算法2 ★一 6 算法3 试代价次优的合适方法。 参考文献： 0 [1]PAWLAK Z.Rough sets-theoretical aspects of reasoning a- 0.10.20.30.40.50.60.70.80.91.0 bout data[M].Dordrecht:Kluwer Academic,1991 (b)Credit approval [2]HU Q H,CHE X J,ZHANG L,et al.Rank entropy based ×10 decision trees for monotonic classification[J].IEEE Trans- 算法1 actions on Knowledge and Data Engineering,2012,24 6 算法2 (11):2052-2064. ★一 算法3 4 [3]HU Q H,PAN WW,ZHANG L,et al.Feature selection for monotonic classification[.IEEE Transactions on Fuzzy Systems.2012,20(1):69-81. 0.10.20.30.40.50.60.70.80.91.0 [4]LUO G Z,YANG X B.Limited dominance-based rough set 以 model and knowledge reductions in incomplete decision sys- (c)Heart-disease tem[].Journal of Information Science and Engineering, 110 2010,26(6):2199-2211. 10 算法1 [5]王国胤.Rough集理论在不完备信息系统中的扩充[J]. 算法2 计算机研究与发展，2002,39(10)：1238-1243。 42 6 算法3 WANG Guoyin.Extension of rough set under incomplete in- formation systems[J].Journal of Computer Research and Development,.2002,39(10):1238-1243. 0 0.10.20.30.40.50.60.70.80.91.0 [6]杨习贝，杨静宇，於东军，等.不完备信息系统中的可 变精度分类粗糙集模型[J].系统工程理论与实践， (d)Hepatitis 2008,28(5):116-121 图13种约简算法所求得的测试代价对比 YANG Xibei,YANG Jingyu,YU Dongjun,et al.Rough set Fig.1 Comparisons among test costs obtained by three model based on variable parameter classification in incom- algorithms plete information systems[J].System Engineering-Theory 由图1的实验结果，可以得到：1)传统的启发 and Practice,2008,28(5):116-121. 式算法所获取的约简的测试代价最大，回溯算法所 [7]MIN F,HE H P,QIAN Y H,et al.Test-cost-sensitive at- 约简的测试代价最小，而综合考虑测试代价的改进 tribute reduction J].Information Sciences,2011,181 的启发式算法得到约简的测试代价则是基于两者之 (22):4928-4942. 间。2)从图1的4个子图可以发现，3种算法的测 [8]MIN F,LIU Q H.A hierarchical model for test-cost-sensi- 试代价随α值的不断增加呈现先增加达到一定峰 tive decision systems[J].Information Sciences,2009,179 值后再下降的大致趋势，从实验的角度可看出α值 (14):2442-2452. 在这3个算法中发挥着调节正域的作用。 [9]MIN F,ZHU W.Test-cost-sensitive attribute reduction based on neighborhood rough set[C]//2011 IEEE Interna- 4结束语 tional Conference on Granular Computing.Kaohsiung,Chi- na,2011:802-806. 本文将测试代价引入不完备信息系统中，提出 [10]MIN F,ZHU W.Attribute reduction of data with error ran- 了基于测试代价敏感的可变精度分类粗糙集模型。 ges and test costs [J].Information Sciences,2012,211: 进一步地，通过分析传统启发式约简算法未考虑测 48-67. 试代价以及回溯约简算法为获取最优测试需要消耗 [11]MIN F,HE H P,QIAN Y H,et al.Test-cost-sensitive at- 大量时间的不足，本文对传统属性重要度测量进行 tribute reduction[J].Information Sciences,2011,181: 了改进，并根据新的属性重要度测量设计了一种新 4928.4942

（ｂ）Ｃｒｅｄｉｔ ａｐｐｒｏｖａｌ （ｃ）Ｈｅａｒｔ⁃ｄｉｓｅａｓｅ （ｄ）Ｈｅｐａｔｉｔｉｓ 图 １ ３ 种约简算法所求得的测试代价对比 Ｆｉｇ．１ Ｃｏｍｐａｒｉｓｏｎｓ ａｍｏｎｇ ｔｅｓｔ ｃｏｓｔｓ ｏｂｔａｉｎｅｄ ｂｙ ｔｈｒｅｅ ａｌｇｏｒｉｔｈｍｓ 由图 １ 的实验结果， 可以得到： １）传统的启发 式算法所获取的约简的测试代价最大， 回溯算法所 约简的测试代价最小， 而综合考虑测试代价的改进 的启发式算法得到约简的测试代价则是基于两者之 间。 ２）从图 １ 的 ４ 个子图可以发现， ３ 种算法的测 试代价随 α 值的不断增加呈现先增加达到一定峰 值后再下降的大致趋势， 从实验的角度可看出 α 值 在这 ３ 个算法中发挥着调节正域的作用。 ４ 结束语 本文将测试代价引入不完备信息系统中， 提出 了基于测试代价敏感的可变精度分类粗糙集模型。 进一步地， 通过分析传统启发式约简算法未考虑测 试代价以及回溯约简算法为获取最优测试需要消耗 大量时间的不足， 本文对传统属性重要度测量进行 了改进， 并根据新的属性重要度测量设计了一种新 的启发式算法用以获取测试代价次优的约简。 实验 表明， 总体而言， 改进的启发式算法是寻找约简测 试代价次优的合适方法。 参考文献： ［１］ＰＡＷＬＡＫ Ｚ． Ｒｏｕｇｈ ｓｅｔｓ－ｔｈｅｏｒｅｔｉｃａｌ ａｓｐｅｃｔｓ ｏｆ ｒｅａｓｏｎｉｎｇ ａ⁃ ｂｏｕｔ ｄａｔａ［Ｍ］． Ｄｏｒｄｒｅｃｈｔ： Ｋｌｕｗｅｒ Ａｃａｄｅｍｉｃ， １９９１． ［２］ＨＵ Ｑ Ｈ， ＣＨＥ Ｘ Ｊ， ＺＨＡＮＧ Ｌ， ｅｔ ａｌ． Ｒａｎｋ ｅｎｔｒｏｐｙ ｂａｓｅｄ ｄｅｃｉｓｉｏｎ ｔｒｅｅｓ ｆｏｒ ｍｏｎｏｔｏｎｉｃ ｃｌａｓｓｉｆｉｃａｔｉｏｎ［ Ｊ］． ＩＥＥＥ Ｔｒａｎｓ⁃ ａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ， ２０１２， ２４ （１１）： ２０５２⁃２０６４． ［３］ＨＵ Ｑ Ｈ， ＰＡＮ Ｗ Ｗ， ＺＨＡＮＧ Ｌ， ｅｔ ａｌ． Ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｆｏｒ ｍｏｎｏｔｏｎｉｃ ｃｌａｓｓｉｆｉｃａｔｉｏｎ［Ｊ］． ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｆｕｚｚｙ Ｓｙｓｔｅｍｓ， ２０１２， ２０（１）： ６９⁃８１． ［４］ＬＵＯ Ｇ Ｚ， ＹＡＮＧ Ｘ Ｂ． Ｌｉｍｉｔｅｄ ｄｏｍｉｎａｎｃｅ⁃ｂａｓｅｄ ｒｏｕｇｈ ｓｅｔ ｍｏｄｅｌ ａｎｄ ｋｎｏｗｌｅｄｇｅ ｒｅｄｕｃｔｉｏｎｓ ｉｎ ｉｎｃｏｍｐｌｅｔｅ ｄｅｃｉｓｉｏｎ ｓｙｓ⁃ ｔｅｍ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅ ａｎｄ Ｅｎｇｉｎｅｅｒｉｎｇ， ２０１０， ２６（６）： ２１９９⁃２２１１． ［５］王国胤． Ｒｏｕｇｈ 集理论在不完备信息系统中的扩充［ Ｊ］． 计算机研究与发展， ２００２， ３９（１０）： １２３８⁃１２４３． ＷＡＮＧ Ｇｕｏｙｉｎ． Ｅｘｔｅｎｓｉｏｎ ｏｆ ｒｏｕｇｈ ｓｅｔ ｕｎｄｅｒ ｉｎｃｏｍｐｌｅｔｅ ｉｎ⁃ ｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍｐｕｔｅｒ Ｒｅｓｅａｒｃｈ ａｎｄ Ｄｅｖｅｌｏｐｍｅｎｔ， ２００２， ３９（１０）： １２３８⁃１２４３． ［６］杨习贝， 杨静宇， 於东军， 等． 不完备信息系统中的可 变精度分类粗糙集模型［ Ｊ］． 系统工程理论与实践， ２００８， ２８（５）：１１６⁃１２１． ＹＡＮＧ Ｘｉｂｅｉ， ＹＡＮＧ Ｊｉｎｇｙｕ， ＹＵ Ｄｏｎｇｊｕｎ， ｅｔ ａｌ． Ｒｏｕｇｈ ｓｅｔ ｍｏｄｅｌ ｂａｓｅｄ ｏｎ ｖａｒｉａｂｌｅ ｐａｒａｍｅｔｅｒ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｉｎ ｉｎｃｏｍ⁃ ｐｌｅｔｅ ｉｎｆｏｒｍａｔｉｏｎ ｓｙｓｔｅｍｓ ［ Ｊ］． Ｓｙｓｔｅｍ Ｅｎｇｉｎｅｅｒｉｎｇ － Ｔｈｅｏｒｙ ａｎｄ Ｐｒａｃｔｉｃｅ， ２００８， ２８（５）： １１６⁃１２１． ［７］ＭＩＮ Ｆ， ＨＥ Ｈ Ｐ， ＱＩＡＮ Ｙ Ｈ， ｅｔ ａｌ． Ｔｅｓｔ⁃ｃｏｓｔ⁃ｓｅｎｓｉｔｉｖｅ ａｔ⁃ ｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ［ Ｊ ］． Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ， ２０１１， １８１ （２２）： ４９２８⁃４９４２． ［８］ＭＩＮ Ｆ， ＬＩＵ Ｑ Ｈ． Ａ ｈｉｅｒａｒｃｈｉｃａｌ ｍｏｄｅｌ ｆｏｒ ｔｅｓｔ⁃ｃｏｓｔ⁃ｓｅｎｓｉ⁃ ｔｉｖｅ ｄｅｃｉｓｉｏｎ ｓｙｓｔｅｍｓ［ Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ， ２００９， １７９ （１４）： ２４４２⁃２４５２． ［９ ］ ＭＩＮ Ｆ， ＺＨＵ Ｗ． Ｔｅｓｔ⁃ｃｏｓｔ⁃ｓｅｎｓｉｔｉｖｅ ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｂａｓｅｄ ｏｎ ｎｅｉｇｈｂｏｒｈｏｏｄ ｒｏｕｇｈ ｓｅｔ［Ｃ］ ／ ／ ２０１１ ＩＥＥＥ Ｉｎｔｅｒｎａ⁃ ｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｇｒａｎｕｌａｒ Ｃｏｍｐｕｔｉｎｇ． Ｋａｏｈｓｉｕｎｇ， Ｃｈｉ⁃ ｎａ， ２０１１： ８０２⁃８０６． ［１０］ＭＩＮ Ｆ， ＺＨＵ Ｗ． Ａｔｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ｏｆ ｄａｔａ ｗｉｔｈ ｅｒｒｏｒ ｒａｎ⁃ ｇｅｓ ａｎｄ ｔｅｓｔ ｃｏｓｔｓ ［ Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ， ２０１２， ２１１： ４８⁃６７． ［１１］ＭＩＮ Ｆ， ＨＥ Ｈ Ｐ， ＱＩＡＮ Ｙ Ｈ， ｅｔ ａｌ． Ｔｅｓｔ⁃ｃｏｓｔ⁃ｓｅｎｓｉｔｉｖｅ ａｔ⁃ ｔｒｉｂｕｔｅ ｒｅｄｕｃｔｉｏｎ ［ Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ， ２０１１， １８１： ４９２８⁃４９４２． ·２２２· 智 能 系 统 学 报 第 ９ 卷

第2期 鞠恒荣，等：不完备信息系统中测试代价敏感的可变精度分类粗糙集 .223, 作者简介： 杨习贝，男，1980年生，副教授， 鞠恒荣，男，1989年生，硕士研究 博士（后），江苏省青蓝工程优秀青年 生，主要研究方向为粗糙集，主持江苏 骨干教师。主要研究方向为粗糙集、粒 省普通高校研究生科研创新计划项目 计算、知识工程、人工智能等。近年来， 一项。 发表学术论文60余篇，出版英文学术 专著一部。现主持国家自然科学基金、 江苏省自然科学基金等多项科研项目。 马兴斌，男，1992年生，硕士研究 生，主要研究方向为粗糙集。 第11届全球智能控制与自动化大会(WCICA2014) The 11th World Congress on Intelligent Control and Automation(WCICA2014) The 11th World Congress on Intelligent Control and Automation (WCICA 2014)will be held in Shenyang,China, from June 27 to 30,2014.WCICA 2014 is technically sponsored by IEEE Robotics and Automation Society,IEEE Control Systems Society,National Natural Science Foundation of China,the Chinese Association of Automation,and the Chinese Association of Artificial Intelligence. WCICA 2014 features plenary keynotes and plenary panel discussion sessions by the world leading researchers as well as awards to honor outstanding papers presented at this Congress.The awards include Best Paper on Theory,Best Paper on Applications,Best Student Paper,Best Poster Paper,Best Paper on Biomedical Biosystem Related Areas,SUPCON Best Paper on Industrial Automation,and AIAG Best Paper on Supply Chain Related Topics. Moreover,we are in the process to arrange post-conference publication of a selected group of accepted papers at WCI- CA 2014 in more than ten leading international journals and top Chinese journals as special issues,among them are IEEE/ ASME Transactions on Mechatronics,IEEE Transactions on Robotics,IEEE Transactions on Control Systems Technology, IEEE Transactions on Industrial Electronics,IEEE Transactions on Systems,Man,and Cybernetics,Part B,and Acta Automation Sinica. It is our great pleasure to invite you to submit your original research papers to the Congress.WCICA 2014 also wel- comes proposals for organizing Focused Theme Sessions on the conference topics,Tutorials and Workshops on emerging topics.You are invited to submit focused theme session proposals to Prof.Simon X.Yang (syang@uoguelph.ca)before Dec.1,2013.Please refer to the Congress website for details. Website:http://2014.wcica.info/index.shtml. Tel:02483681047-8013. E-mail:wcica2014@gmail.com

作者简介： 鞠恒荣， 男， １９８９ 年生，硕士研究 生，主要研究方向为粗糙集， 主持江苏 省普通高校研究生科研创新计划项目 一项。 马兴斌， 男， １９９２ 年生， 硕士研究 生， 主要研究方向为粗糙集。 杨习贝， 男， １９８０ 年生， 副教授， 博士（后）， 江苏省青蓝工程优秀青年 骨干教师。 主要研究方向为粗糙集、粒 计算、知识工程、人工智能等。 近年来， 发表学术论文 ６０ 余篇， 出版英文学术 专著一部。 现主持国家自然科学基金、 江苏省自然科学基金等多项科研项目。 第 １１ 届全球智能控制与自动化大会（ＷＣＩＣＡ２０１４） Ｔｈｅ １１ｔｈ Ｗｏｒｌｄ Ｃｏｎｇｒｅｓｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｎｔｒｏｌ ａｎｄ Ａｕｔｏｍａｔｉｏｎ（ＷＣＩＣＡ２０１４） Ｔｈｅ １１ｔｈ Ｗｏｒｌｄ Ｃｏｎｇｒｅｓｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｃｏｎｔｒｏｌ ａｎｄ Ａｕｔｏｍａｔｉｏｎ （ＷＣＩＣＡ ２０１４） ｗｉｌｌ ｂｅ ｈｅｌｄ ｉｎ Ｓｈｅｎｙａｎｇ， Ｃｈｉｎａ， ｆｒｏｍ Ｊｕｎｅ ２７ ｔｏ ３０， ２０１４． ＷＣＩＣＡ ２０１４ ｉｓ ｔｅｃｈｎｉｃａｌｌｙ ｓｐｏｎｓｏｒｅｄ ｂｙ ＩＥＥＥ Ｒｏｂｏｔｉｃｓ ａｎｄ Ａｕｔｏｍａｔｉｏｎ Ｓｏｃｉｅｔｙ， ＩＥＥＥ Ｃｏｎｔｒｏｌ Ｓｙｓｔｅｍｓ Ｓｏｃｉｅｔｙ， Ｎａｔｉｏｎａｌ Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｆｏｕｎｄａｔｉｏｎ ｏｆ Ｃｈｉｎａ， ｔｈｅ Ｃｈｉｎｅｓｅ Ａｓｓｏｃｉａｔｉｏｎ ｏｆ Ａｕｔｏｍａｔｉｏｎ， ａｎｄ ｔｈｅ Ｃｈｉｎｅｓｅ Ａｓｓｏｃｉａｔｉｏｎ ｏｆ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ． ＷＣＩＣＡ ２０１４ ｆｅａｔｕｒｅｓ ｐｌｅｎａｒｙ ｋｅｙｎｏｔｅｓ ａｎｄ ｐｌｅｎａｒｙ ｐａｎｅｌ ｄｉｓｃｕｓｓｉｏｎ ｓｅｓｓｉｏｎｓ ｂｙ ｔｈｅ ｗｏｒｌｄ ｌｅａｄｉｎｇ ｒｅｓｅａｒｃｈｅｒｓ ａｓ ｗｅｌｌ ａｓ ａｗａｒｄｓ ｔｏ ｈｏｎｏｒ ｏｕｔｓｔａｎｄｉｎｇ ｐａｐｅｒｓ ｐｒｅｓｅｎｔｅｄ ａｔ ｔｈｉｓ Ｃｏｎｇｒｅｓｓ． Ｔｈｅ ａｗａｒｄｓ ｉｎｃｌｕｄｅ Ｂｅｓｔ Ｐａｐｅｒ ｏｎ Ｔｈｅｏｒｙ， Ｂｅｓｔ Ｐａｐｅｒ ｏｎ Ａｐｐｌｉｃａｔｉｏｎｓ， Ｂｅｓｔ Ｓｔｕｄｅｎｔ Ｐａｐｅｒ， Ｂｅｓｔ Ｐｏｓｔｅｒ Ｐａｐｅｒ， Ｂｅｓｔ Ｐａｐｅｒ ｏｎ Ｂｉｏｍｅｄｉｃａｌ ＆ Ｂｉｏｓｙｓｔｅｍ Ｒｅｌａｔｅｄ Ａｒｅａｓ， ＳＵＰＣＯＮ Ｂｅｓｔ Ｐａｐｅｒ ｏｎ Ｉｎｄｕｓｔｒｉａｌ Ａｕｔｏｍａｔｉｏｎ， ａｎｄ ＡＩＡＧ Ｂｅｓｔ Ｐａｐｅｒ ｏｎ Ｓｕｐｐｌｙ Ｃｈａｉｎ Ｒｅｌａｔｅｄ Ｔｏｐｉｃｓ． Ｍｏｒｅｏｖｅｒ， ｗｅ ａｒｅ ｉｎ ｔｈｅ ｐｒｏｃｅｓｓ ｔｏ ａｒｒａｎｇｅ ｐｏｓｔ⁃ｃｏｎｆｅｒｅｎｃｅ ｐｕｂｌｉｃａｔｉｏｎ ｏｆ ａ ｓｅｌｅｃｔｅｄ ｇｒｏｕｐ ｏｆ ａｃｃｅｐｔｅｄ ｐａｐｅｒｓ ａｔ ＷＣＩ⁃ ＣＡ ２０１４ ｉｎ ｍｏｒｅ ｔｈａｎ ｔｅｎ ｌｅａｄｉｎｇ ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌｓ ａｎｄ ｔｏｐ Ｃｈｉｎｅｓｅ ｊｏｕｒｎａｌｓ ａｓ ｓｐｅｃｉａｌ ｉｓｓｕｅｓ， ａｍｏｎｇ ｔｈｅｍ ａｒｅ ＩＥＥＥ／ ＡＳＭＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｍｅｃｈａｔｒｏｎｉｃｓ， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｒｏｂｏｔｉｃｓ， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｎｔｒｏｌ Ｓｙｓｔｅｍｓ Ｔｅｃｈｎｏｌｏｇｙ， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｄｕｓｔｒｉａｌ Ｅｌｅｃｔｒｏｎｉｃｓ， ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｙｓｔｅｍｓ， Ｍａｎ， ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ， Ｐａｒｔ Ｂ， ａｎｄ Ａｃｔａ Ａｕｔｏｍａｔｉｏｎ Ｓｉｎｉｃａ． Ｉｔ ｉｓ ｏｕｒ ｇｒｅａｔ ｐｌｅａｓｕｒｅ ｔｏ ｉｎｖｉｔｅ ｙｏｕ ｔｏ ｓｕｂｍｉｔ ｙｏｕｒ ｏｒｉｇｉｎａｌ ｒｅｓｅａｒｃｈ ｐａｐｅｒｓ ｔｏ ｔｈｅ Ｃｏｎｇｒｅｓｓ． ＷＣＩＣＡ ２０１４ ａｌｓｏ ｗｅｌ⁃ ｃｏｍｅｓ ｐｒｏｐｏｓａｌｓ ｆｏｒ ｏｒｇａｎｉｚｉｎｇ Ｆｏｃｕｓｅｄ Ｔｈｅｍｅ Ｓｅｓｓｉｏｎｓ ｏｎ ｔｈｅ ｃｏｎｆｅｒｅｎｃｅ ｔｏｐｉｃｓ， Ｔｕｔｏｒｉａｌｓ ａｎｄ Ｗｏｒｋｓｈｏｐｓ ｏｎ ｅｍｅｒｇｉｎｇ ｔｏｐｉｃｓ． Ｙｏｕ ａｒｅ ｉｎｖｉｔｅｄ ｔｏ ｓｕｂｍｉｔ ｆｏｃｕｓｅｄ ｔｈｅｍｅ ｓｅｓｓｉｏｎ ｐｒｏｐｏｓａｌｓ ｔｏ Ｐｒｏｆ． Ｓｉｍｏｎ Ｘ． Ｙａｎｇ （ ｓｙａｎｇ＠ ｕｏｇｕｅｌｐｈ．ｃａ） ｂｅｆｏｒｅ Ｄｅｃ． １， ２０１３． Ｐｌｅａｓｅ ｒｅｆｅｒ ｔｏ ｔｈｅ Ｃｏｎｇｒｅｓｓ ｗｅｂｓｉｔｅ ｆｏｒ ｄｅｔａｉｌｓ． Ｗｅｂｓｉｔｅ： ｈｔｔｐ： ／ ／ ２０１４．ｗｃｉｃａ．ｉｎｆｏ ／ ｉｎｄｅｘ．ｓｈｔｍｌ． Ｔｅｌ： ０２４８３６８１０４７⁃８０１３． Ｅ⁃ｍａｉｌ： ｗｃｉｃａ２０１４＠ ｇｍａｉｌ．ｃｏｍ． 第 ２ 期 鞠恒荣，等：不完备信息系统中测试代价敏感的可变精度分类粗糙集 ·２２３·