A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets

doi:10.1016/j.ins.2009.04.002

	A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets
	Meng, Zuqiang 1,2; Shi, Zhongzhi 1
	2009-07-20
发表期刊	INFORMATION SCIENCES
ISSN	0020-0255
卷号	179 期号:16 页码:2774-2793
摘要	Efficient attribute reduction in large, incomplete decision systems is a challenging problem: existing approaches have time complexities no less than O(vertical bar C vertical bar(2)vertical bar U vertical bar(2)). This paper derives some important properties of incomplete information systems, then constructs a positive region-based algorithm to solve the attribute reduction problem with a time complexity no more than O(vertical bar C vertical bar(2)vertical bar U vertical bar log vertical bar U vertical bar). Furthermore, our approach does not change the size of the original incomplete system. Numerical experiments show that the proposed approach is indeed efficient, and therefore of practical value to many real-world problems. The proposed algorithm can be applied to both consistent and inconsistent incomplete decision systems. (c) 2009 Elsevier Inc. All rights reserved.
关键词	Attribute reduction Tolerance relation Positive region Incomplete decision system Rough set theory
DOI	10.1016/j.ins.2009.04.002
收录类别	SCI
语种	英语
资助项目	National Science Foundation of China[90604017] ; 863 National High-Tech Program[2007AA01Z132] ; National Basic Research Priorities Programme[2007CB311004]
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems
WOS记录号	WOS:000267562500006
出版者	ELSEVIER SCIENCE INC
引用统计	被引频次：116[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/11457
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Meng, Zuqiang
作者单位	1.Chinese Acad Sci, Key Lab Intelligent Informat Proc, Inst Comp Technol, Beijing 100190, Peoples R China 2.Guangxi Univ, Coll Comp Elect & Informat, Nanning 530004, Peoples R China
推荐引用方式 GB/T 7714	Meng, Zuqiang,Shi, Zhongzhi. A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets[J]. INFORMATION SCIENCES,2009,179(16):2774-2793.
APA	Meng, Zuqiang,&Shi, Zhongzhi.(2009).A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets.INFORMATION SCIENCES,179(16),2774-2793.
MLA	Meng, Zuqiang,et al."A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets".INFORMATION SCIENCES 179.16(2009):2774-2793.