Journal of South China University of Technology (Natural Science Edition) ›› 2013, Vol. 41 ›› Issue (1): 83-88.doi: 10.3969/j.issn.1000-565X.2013.01.013

• Computer Science & Technology • Previous Articles     Next Articles

Attribute Reduction Algorithm for Incomplete Decision Table Based onAttribute Discernibility

Ji Xia1,2 Li Long-shu1,2 Qi Ping1   

  1. 1. Key Laboratory of Intelligent Computing and Signal Processing of the Ministry of Education, Anhui University, Hefei 230039,Anhui, China; 2. School of Computer Science and Technology, Anhui University, Hefei 230601, Anhui, China
  • Received:2012-01-20 Revised:2012-08-02 Online:2013-01-25 Published:2012-12-03
  • Contact: 纪霞(1982-),女,博士,讲师,主要从事不精确信息处理、粗糙集理论及其应用研究. E-mail:jixia1983@163.com
  • About author:纪霞(1982-),女,博士,讲师,主要从事不精确信息处理、粗糙集理论及其应用研究.
  • Supported by:

    安徽省自然科学基金资助项目(090412054);安徽省高等学校省级自然科学基金资助项目(KJ2011Z020);安徽大学博士科研启动基金资助项目(33190081)

PDF

844

Abstract:

Proposed in this paper is a novel attribute reduction algorithm based on the attribute discernibility to re-duce the high computational complexity of the existing attribute reduction algorithms for incomplete decision tables.In the investigation, the external manifestation of condition attribute significance relative to the decision attribute inincomplete decision tables is analyzed, the attribute discernibility is defined, and the calculating method of dynamicupdate of attribute discernibility with the change of reduction subset is proposed. During the attribute reduction, thealgorithm continuously deletes the objects belonging to the positive domain or the consistent blocks having no effecton the positive domain calculation. Thus, the data scale and the time consumption decreases, and the attribute re-duction quickens. Theoretical analyses and simulation experiments demonstrate that the proposed attribute reductionalgorithm for incomplete decision tables is effective and is superior to the existing algorithms in terms of time com-plexity.

Key words: incomplete decision table, attribute reduction, consistent block, attribute discernibility