A Parallel Computation Method for Heuristic Attribute Reduction Using Reduced Decision Tables
Yasuo Kudo* and Tetsuya Murai**
*College of Information and Systems, 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
In this paper, we propose a parallel computation framework for a heuristic attribute reduction method. Attribute reduction is a key technique to use rough set theory as a tool in data mining. The authors have previously proposed a heuristic attribute reduction method to compute as many relative reducts as possible from a given dataset with numerous attributes. We parallelize our method by using open multiprocessing. We also evaluate the performance of a parallelized attribute reduction method by experiments.
-  Z. Pawlak, “Rough Sets,” Int. J. of Computer and Information Science, Vol.11, pp. 341-356, 1982.
-  Z. Pawlak, “Rough Sets: Theoretical Aspects of Reasoning about Data,” Kluwer Academic Publisher, 1991.
-  A. Chouchoulas and A. Shen, “Rough set-aided keyword reduction for text categorization,” Applied Artificial Intelligence, Vol.15, No.9, pp. 843-873, 2001.
-  K. Hu, L. Diao, Y. Lu, and C. Shi, “A heuristic optimal reduct algorithm,” Proc. of IDEAL2000, LNSC, Vol.1983, pp. 139-144, Springer, 2000.
-  M. Kryszkiewicz and P. Lasek, “FUN: Fast discovery of minimal sets of attributes functionally determining a decision attribute,” Trans. on Rough Sets IX, LNCS, Vol.5390, pp. 76-95, Springer, 2008.
-  Y. Kudo and T. Murai, “Heuristic algorithm for attribute reduction based on classification ability by condition attributes,” J. of Advanced Computational Intelligence and Intelligent Informatics, Vol.15, No.1, pp. 102-109, 2011.
-  J. Zhang, J.Wang, D. Li, H. He, and J. Sun, “A new heuristic reduct algorithm based on rough sets theory,” Proc. ofWAIM2003, LNCS, Vol.2762, pp. 247-253, Springer, 2003.
-  Y. Kudo and T. Murai, “An attribute reduction algorithm by switching exhaustive and heuristic computation of relative reducts,” Proc. of IEEE GrC2010, pp. 265-270, IEEE, 2010.
-  Y. Kudo and T.Murai, “A Parallel Computation Method of Attribute Reduction,” Proc. of ISCIIA 2012, 2012.
-  L. Polkowski, “Rough Sets: Mathematical Foundations,” Advances in Soft Computing, Physica-Verlag, 2002.
-  A. Skowron and C.M. Rauszer, “The discernibility matrix and functionsin 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.
-  OpenMP
-  OpenMP from Wikipedia
-  UCI Machine Learning Repository