Paper:

# Heuristic Algorithm for Attribute Reduction Based on Classification Ability by Condition Attributes

## Yasuo Kudo^{*} and Tetsuya Murai^{**}

^{*}Graduate School of Engineering, Muroran Institute of Technology, 27-1 Mizumoto, Muroran 050-8585, Japan

^{**}Graduate School of Information Science and Technology, Hokkaido University, Kita 14, Nishi 9, Kita-Ku, Sapporo 060-0814, Japan

The heuristic algorithm we propose to compute a relative reduct candidate is based on evaluating classification ability of condition attributes. Considering the discernibility and equivalence of objects for condition attributes in relative reducts, we introduce evaluation criteria for condition attributes and relative reducts. The computational complexity of the proposed algorithm is *O*(|*U*|^{2}|*C*|^{2}). Experimental results indicate that our algorithm often generates a relative reduct producing a good evaluation result.

- [1] Z. Pawlak, “Rough Sets,” Int. J. of Computer and Information Science, Vol.11, pp. 341-356, 1982.
- [2] Z. Pawlak, “Rough Sets: Theoretical Aspects of Reasoning about Data,” Kluwer Academic Publishers, 1991.
- [3] A. Skowron and C.M. Rauszer, “The discernibility matrix and functions in information systems,” R. Słowiński (ed.), Intelligent Decision Support: Handbook of Application and Advance of the Rough Set Theory, Kluwer Academic Publishers, pp. 331-362, 1992.
- [4] A. Chouchoulas and Q. Shen, “Rough Set-Aided Keyword Reduction for Text Categorization,” Applied Artificial Intelligence, Vol.15, No.9, pp. 843-873, 2001.
- [5] H. Ge and C. Yang, “An Efficient Attribute Reduction Algorithm Based on Concentrated Ordered Discernibility Set,” Proc. of 2008 Int. Conf. on Computer Science and Software Engineering, IEEE, pp. 332-335, 2008.
- [6] J. W. Guan and D. A. Bell, “Rough computational methods for information systems,” Artificial Intelligence, Vol.105, pp. 77-103, 1998.
- [7] A. H. Hedar, J.Wang, and M. Fukushima, “Tabu search for attribute reduction in rough set theory,” Soft Couping, Vol.12, No.9, pp. 909-918, Springer, 2008.
- [8] F. Hu, G. Wang, and L. Feng, “Fast Knowledge Reduction Algorithms Based on Quick Sort,” Rough Sets and Knowledge Technology, LNAI 5009, pp. 72-79, Springer, 2008.
- [9] K. Hu, L. Diao, Y. Lu, and C. Shi, “A Heuristic Optiaml Reduct Algorithm,” Proc. of IDEAL2000, LNSC 1983, pp. 139-144, Springer, 2000.
- [10] M. Kryszkiewicz and P. Lasek, “FUN: Fast Discovery of Minimal Sets of Attributes Functionally Determining a Decision Attribute,” Trans. on Rough Sets IX, LNCS 5390, pp. 76-95, Springer, 2008.
- [11] Y. Kudo and T. Murai, “A Heuristic Algorithm for Selective Calculation of a Better Relative Reduct in Rough Set Theory,” K. Nakamatsu et al. (eds.), New Advances in Intelligent Decision Technologies, SCI199, pp. 555-564, Springer, 2009.
- [12] Z. Pawlak and R. Słowiński, “Rough Set Approach to Multi-Attribute Decision Analysis,” European J. of Operation Research, Vol.74, pp. 443-459, 1994.
- [13] S. Tan, H. Xu, and J. Gu, “Efficient Algorithms for Attributes Reduction Problem,” Int. J. of Innovative Computing, Information and Control, Vol.1, No.4, pp. 767-777, 2005.
- [14] J. Xu and L. Sun, “New Reduction Algorithm Based on Decision Power of Decision Table,” Rough Sets and Knowledge Technology, LNAI 5009, pp. 180-188, Springer, 2008.
- [15] Z. Xu, C. Zhang, S. Zhang, W. Song, and B. Yang, “Efficient Attribute Reduction Based on Discernibility Matrix,” Rough Sets and Knowledge Technology, LNAI 4481, pp. 13-21, Springer, 2007.
- [16] Y. Y. Yao, Y. Zhao, J.Wang, and S. Han, “AModel of User-Oriented Reduct Construction for Machine Learning,” Trans. on Rough Sets VIII, LNCS 5084, pp. 332-351, Springer, 2008.
- [17] J. Zhang, J. Wang, D. Li, H. He, and J. Sun, “A New Heuristic Reduct Algorithm Based on Rough Sets Theory,” Proc. of WAIM2003, LNCS 2762, pp. 247-253, Springer, 2003.
- [18] F. Zhu, Y. Zhang, and L. Zhao, “An Efficient Attribute Reduction in Decision Information Systems,” Proc. of 2008 Int. Conf. on Computer Science and Software Engineering, IEEE, pp. 466-469, 2008.
- [19] http://archive.ics.uci.edu/ml/index.html
- [20] Y. Kudo and T.Murai, “A Heuristic Algorithm for Attribute Reduction Based on Discernibility and Equivalence by Attributes,” Proc. of the 6th Int. Conf. on Modeling Decisions for Artificial Intelligence, LNAI 5861, pp. 351-359, Springer, 2009.
- [21] N. Mori, H. Tanaka, and K. Inoue, “Rough Sets and Kansei – Knowledge Acquisition and Reasoning from Kansei Data –,” Kaibundo, 2004. (in Japanese)
- [22] L. Polkowski, “Rough Sets: Mathematical Foundations,” Advances in Soft Computing, Physica-Verlag, 2002.
- [23] D. Yamaguchi, “Attribute dependency functions considering data efficiency,” Int. J. of Approximate Reasoning, Vol.51, pp. 89-98, 2009.
- [24] Z. Pawlak, “On Rough Dependency of Attributes in Information Systems,” Bulletin of the Polish Academy of Sciences, Technical Sciences, Vol.33, pp. 481-485, 1985.