On efficient methods of computing attribute-value blocks in incomplete decision systems

doi:10.1016/j.knosys.2016.09.025

	On efficient methods of computing attribute-value blocks in incomplete decision systems
	Meng, Zuqiang 1,2; Gan, Qiuling 1,2; Shi, Zhongzhi 3
	2016-12-01
发表期刊	KNOWLEDGE-BASED SYSTEMS
ISSN	0950-7051
卷号	113 页码:171-185
摘要	In rough set models, almost all computations, such as attribute reduction, rule reduction, etc., are based on attribute-value blocks. Computing attribute-value blocks is most frequently used and time-consuming basic operation for these computations. However, special studies were relatively little reported on the construction of efficient methods of computing attribute-value blocks for incomplete decision systems. In this paper, we considered two representative interpretations of missing values: "do not care" conditions and "lost values", and divided incomplete decision systems into two categories: ones containing only "do not care" conditions and the other ones containing both "do not care" conditions and "lost values", which lead to two kinds of rough set models, tolerance relation-based rough set models (TRRSMs) and characteristic relation-based rough set models (CRRSMs), respectively. Then, two algorithms, division algorithm and index algorithm, for computing attribute-value blocks were proposed, with the division algorithm for TRRSMs and the index algorithm for both CRRSMs and TRRSMs. The two proposed algorithms are far more efficient than usual algorithms when dealing with "do not care" conditions; the division algorithm is a little more efficient than the index algorithm when missing value degrees are small, but it can not deal with "lost values", whereas the index algorithm is evidently more efficient than the division algorithm when missing value degrees are relatively large, and it is relatively insensitive to missing value degrees. Experimental results also show that the proposed algorithms are effective and efficient. Thus, the two proposed methods constitute an effective solution to the problem of efficiently computing attribute-value blocks for incomplete decision systems. (C) 2016 Elsevier B.V. All rights reserved.
关键词	Attribute-value block Efficiency Incomplete decision system Rough set theory Missing value Attribute reduction
DOI	10.1016/j.knosys.2016.09.025
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61363027] ; Guangxi Natural Science Foundation, China[2015GXNSFAA139292] ; National Basic Research Programme of China[2013CB329502]
WOS研究方向	Computer Science
WOS类目	Computer Science, Artificial Intelligence
WOS记录号	WOS:000387519500015
出版者	ELSEVIER SCIENCE BV
引用统计	被引频次：3[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/7961
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Meng, Zuqiang
作者单位	1.Guangxi Univ, Coll Comp Elect & Informat, Nanning 530004, Peoples R China 2.Guangxi Univ, Guangxi Coll & Univ Key Lab Multimedia Commun & I, Nanning 530004, Peoples R China 3.Chinese Acad Sci, Key Lab Intelligent Informat Proc, Inst Comp Technol, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Meng, Zuqiang,Gan, Qiuling,Shi, Zhongzhi. On efficient methods of computing attribute-value blocks in incomplete decision systems[J]. KNOWLEDGE-BASED SYSTEMS,2016,113:171-185.
APA	Meng, Zuqiang,Gan, Qiuling,&Shi, Zhongzhi.(2016).On efficient methods of computing attribute-value blocks in incomplete decision systems.KNOWLEDGE-BASED SYSTEMS,113,171-185.
MLA	Meng, Zuqiang,et al."On efficient methods of computing attribute-value blocks in incomplete decision systems".KNOWLEDGE-BASED SYSTEMS 113(2016):171-185.