A Quick Algorithm for Attribute Reduction Based on Divide and Conquer Method

Abstract:

Knowledge reduction is one of the most important contributions of rough set theory. High efficient algorithm is necessary for attribute reduction. In this paper, combining given attribute order and quick sort method, a heuristic algorithm for attribute reduction is developed. In this method, the objects in universe are divided into many small parts on the attributes by divide and conquer method, and different granules in different granular levels are obtained. The small ones can be processed quickly, so a fast heuristic algorithm for attribute reduction is proposed. Simulation experiment results illustrate the high efficiency of the improved knowledge reduction algorithm.

• Periodical: Advanced Materials Research (Volume 267)
• Pages: 92-97
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.267.92
• Online since: June 2011
• Authors: Feng Hu, Xi Chen, Xiao Yan Wang, Chuan Jiang Luo
• Keywords: Attribute Reduction, Conquer, Divide, Equivalence Relation, Rough Set (RS)

References

[1] Z. Pawlak: Rough Sets. International Journal of Computer and Information Sciences Vol. 11 (1982), pp.341-356.

[2] Z. Pawlak and A. Skowron: Rudiments of Rough Sets. Information Sciences Vol. 177 (2007), pp.2-27.

DOI: 10.1016/j.ins.2006.06.003

[3] Z. Pawlak and A. Skowron: Rough Sets and Boolean Reasoning. Information Sciences. Vol. 177 (2007), pp.41-73.

DOI: 10.1016/j.ins.2006.06.007

[4] G. Y. Wang: Rough Set Theory and Knowledge Acquisition (Xi' an Jiaotong University Press, China 2001). (in Chinese).

[5] A. Skowron, and C. Rauszer: The Discernibility Functions Matrics and Functions in Information Systems, in: Intelligent Decision Support-Hand-book of Applications and Advances of the Rough Sets Theory, edited by R. Slowinski, Dordrecht, Kluwer Academic Publisher (1992).

DOI: 10.1007/978-94-015-7975-9_21

[6] Y.Y. Yao and Y. Zhao: Discernibility Matrix Simplification For Constructing Attribute Reducts. Information Sciences Vol. 179 (2009), pp.867-882.

DOI: 10.1016/j.ins.2008.11.020

[7] H. Ge, L.S. Li, and C.J. Yang: New Discernibility Matrix And Reduction Method. Control and Decision. Vol. 25 (2010), pp.1891-1895 (in Chinese).

[8] S.Q. Han and J. Wang: Reduct and Attribute Order. Journal of Computer Science and Technology. Vol. 19 (2004), pp.429-449.

[9] G. Y. Wang, H. Yu, and D. C. Yang: Decision Table Reduction Based on Conditional Information Entropy. Chinese Journal of Computers. Vol. 25 (2002), pp.759-766 (in Chinese).

[10] X. X Yu, G.H. Cui and H.M. Zhou: Fundamentals of Computer Algorithms (Huazhong University Press, Wuhan, China 2005). (in Chinese).

[11] F. Hu, and G.Y. Wang: Analysis of The Complexity of Quick Sort for Two Dimension Table. Chinese Journal of Computers. Vol. 30 (2007), pp.693-698 (in Chinese).