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