¡¡Chinese Journal of Computers   Full Text
  TitleQuick Reduction Algorithm Based on Attribute Order
  AuthorsHU Feng WANG Guoª²Yin
  Address(Institute of Computer Science and Technology, Chongqing University of Posts and Telecommunications, Chongqing 400065)
(School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031)
  Year2007
  IssueNo.8(1429¡ª1435)
  Abstract &
  Background 		Abstract The idea of divide and conquer is adopted in attribute reduction of rough set theory. A quick algorithm for attribute reduction of ordered attributes is proposed based on the divide and conquer method. A unique attribute reduction can be obtained with this algorithm. It is suitable for dealing with huge data reduction. If all data of a decision table could be loaded in memory one time, the average time complexity of this algorithm will be O(£üU£ü¡Á£üC£ü¡Á(£üC£ü+log£üU£ü)) and its space complexity will be O(£üU£ü+£üC£ü). Simulation experimental results show its efficiency.

keywords rough set; divide and conquer; attribute reduction; attribute order

background This paper is partially supported by the National Natural Science Foundation of China under Grants No.60373111 and No. 60573068, Program for New Century Excellent Talents in University (NCET), Natural Science Foundation of Chongqing under grant Noª±2005BA2003, Science & Technology Research Program of Chongqing Education Commission under grant Noª±KJ060517.
In the research of rough set theory, many researchers have proposed many algorithms for attribute reduction. However, it is difficult for the existed attribute reduction algorithms to process huge data sets. There are two reasons. One is the time complexity, and the other is the space complexity. Especially in processing huge data set, the space complexity of an algorithm will affect greatly its efficiency. In this paper, a quick algorithm for attribute reduction of ordered attributes is proposed based on the divide and conquer method. Its average time complexity is O(£üU£ü¡Á£üC£ü¡Á(£üC£ü+log£üU£ü)) and space complexity is O(£üU£ü+£üC£ü). The algorithm is suitable for huge data processing. It may be helpful to put rough set theory into industry applications.