Email this article Symbolic Representation for Rough Set Attribute Reduction Using Ordered Binary Decision Diagrams
Abstract
The theory of rough set is the current research focus for knowledge discovery, attribute reduction is one of crucial problem in rough set theory. Most existing attribute reduction algorithms are based on algebra and information representations, discernibility matrix is a common knowledge representation for attribute reduction. As problem solving under different knowledge representations corresponding to different difficulties, by changing the method of knowledge representation, a novel knowledge representation to represent the discernibility matrix using ordered binary decision diagrams (OBDD) is proposed in this paper, the procedures to translate the discernibility matrix model to the conversion OBDD model is presented, experiment is carried to compare the storage space of discernibility matrix with that of OBDD, results show that OBDD model has better storage performance and improve the attribute reduction for those information systems with more objects and attributes, it provide the foundation for seeking new efficient algorithm of attribute reduction.
Index Terms—rough set, attribute reduction, discernibility matrix, ordered binary decision diagrams
Keywords
References
[1] Pawlak Z. “Rough sets.” International Journal of Information and Computer Science, vol.11, no.5, pp.341-356, 1982.
doi:10.1007/BF01001956
[2] Skowron A, “Rauszer. The discernibility matrices and functions in information systems,” in: R. Slowinski (Ed.), Intelligent Decision Support–handbook of Applications and Advances of the Rough Sets Theory. Dordrecht: Kluwer Academic Publishers, pp.331-362, 1992.
[3] Pawlak Z. “Rough set approach to multi-attribute decision analysis.” European Journal of Operational Research, vol.72, no.3, pp.443-459, 1994.
doi:10.1016/0377-2217(94)90415-4
[4] Pawlak Z, Skowron A. “Rudiments of rough set.” Information Sciences, vol.177, no.1, pp. 3-27, 2007.
doi:10.1016/j.ins.2006.06.003
[5] A Muir, I Düntsch, G Gediga. “Rough set data representation using binary decision diagrams.” Computational Sciences, vol.98, no.1, pp.197-211, 2004.
[6] Wong S K M, Ziarko W. “On Optimal Decision Rules in Decision Tables.” Bulletin of Polish Academy of Sciences, vol.33, pp. 693-696, 1985.
[7] Chen Yuming, Miao Duoqian. “Searching Algorithm for Attribute Reduction based on Power Graph.” Chinese Journal of Computers, vol.32, no.8, pp.1486-1492, 2009.
[8] Tianlong Gu, Zhoubo Xu, Zhifei Yang. “Symbolic OBDD representations for mechanical assembly sequences.” Computer-Aided Design, vol.40, pp.411-421, 2008.
doi:10.1016/j.cad.2007.12.001
[9] YiYu Yao, Yan Zhao, and Jue Wang, “On Reduct Construction Algorithms,” Proceedings of the First International Conference on Rough Sets and Knowledge Technologies, Chongqing, China, pp.297-304, 2006.
[10] Yiyu Yao, Yan Zhao. “Discernibility matrixsimplification for constructing attribute ruducts.” Information Sciences, vol.179, no.7, pp. 867-882, 2009.
doi:10.1016/j.ins.2008.11.020
[11] K.Thangavel, A. “Pethalakshmi. Dimensionality reduction based on rough set theory: A review.” Applied Soft Computing, no.9, pp. 1-12, 2009.
doi:10.1016/j.asoc.2008.05.006
[12] Hu X H, Cercone N. “Learning in relational databases: A rough set approach.” Computational Intelligence, vol.11, no.2, pp.323-337, 1995.
doi:10.1111/j.1467-8640.1995.tb00035.x
[13] Ye Dongyi, Chen Zhaojiong. “A new discernibility matrix and the computation of a core.” Acta Electronica Sinica, vol.30no.7, pp.1086-1088, 2002.
[14] Wang Guoyin. “Calculation methods for core attributes of decision table.” Chinese Journal of Computer, vol.26, no. 5, pp. 611-615, 2003.
[15] Liu Qing. Rough sets and Rough Reasoning. Beijing: Science Press, 2001
[16] Gu Tianlong, Xu Zhoubo. Ordered binary decision diagram and it s application. Beijing: Science Press, pp.22-57, 2009.
Full Text: PDF