Research Paper:
Refined β̂-QuickReduct: An Improved β̂-QuickReduct Algorithm with Verification of Original Results
Yasuo Kudo* and Hajime Okawa**
*Muroran Institute of Technology
27-1 Mizumoto, Muroran, Hokkaido 050-8585, Japan
**National Institute of Technology, Tomakomai College
443 Nishikioka, Tomakomai, Hokkaido 059-1275, Japan
In this study, the heuristic β̂-QuickReduct algorithm in the variable precision rough set model for calculating a β̂-reduct candidate is refined. The Refined β̂-QuickReduct algorithm involves checking the redundancy of attributes in the β̂-reduct candidate obtained using the original β̂-QuickReduct and rejecting all redundant attributes. The advantage of this refinement is that the Refined β̂-QuickReduct always produces a valid β̂-reduct, a property that is theoretically guaranteed. Experimental results suggest that the Refined β̂-QuickReduct is significantly faster than the method of Nakahama et al. in calculating a valid β̂-reduct. Consequently, two issues are overcome in the calculation of a valid β̂-reduct: (i) the limitation of the original β̂-QuickReduct that renders the output β̂-reduct invalid because of the redundancy of attributes in the β̂-reduct candidate and (ii) the high computational cost in calculating a valid β̂-reduct by Nakahama et al.’s method.
Extraction of a true hat-beta reduct
- [1] Z. Pawlak, “Rough sets,” Int. J. of Information and Computer Science, Vol.11, No.5, pp. 341-356, 1982. https://doi.org/10.1007/BF01001956
- [2] Z. Pawlak, “Rough Sets: Theoretical Aspects of Reasoning about Data,” Kluwer Academic Publishers, 1991. https://doi.org/10.1007/978-94-011-3534-4
- [3] W. Ziarko, “Variable precision rough set model,” J. of Computer and System Sciences, Vol.46, No.1, pp. 39-59, 1993. https://doi.org/10.1016/0022-0000(93)90048-2
- [4] J. D. Katzberg and W. Ziarko, “Variable Precision Extension of Rough Sets,” Fundamenta Informaticae, Vol.27, Nos.2-3, pp. 155-168, 1996. https://doi.org/10.3233/FI-1996-272304
- [5] M. Beynon, “Reducts within the variable precision rough sets model: A further investigation,” European J. of Operational Research, Vol.134, No.3, pp. 592-605, 2001. https://doi.org/10.1016/S0377-2217(00)00280-0
- [6] M. J. Beynon and M. J. Peel, “Variable precision rough set theory and data discretization: An application to corporate failure prediction,” Omega, Vol.29, No.6, pp. 561-576, 2001. https://doi.org/10.1016/S0305-0483(01)00045-7
- [7] C. T. Su and J. H. Hsu, “Precision parameter in the variable precision rough sets model: An application,” Omega, Vol.34, No.2, pp. 149-157, 2006. https://doi.org/10.1016/j.omega.2004.08.005
- [8] M. Inuiguchi, “Structure-Based Attribute Reduction in Variable Precision Rough Set Models,” J. Adv. Comput. Intell. Intell. Inform., Vol.10, No.5, pp. 657-665, 2006. https://doi.org/10.20965/jaciii.2006.p0657
- [9] X. Zhao, M. Ha, and A. Zhang, “Variable Precision Rough Set Model in Incomplete Ordered Decision System,” Proc. of 2008 3rd Int. Conf. Innovative Computing, Information and Control (ICICIC), Article No.498, 2008. https://doi.org/10.1109/ICICIC.2008.672
- [10] Y. Kudo and T. Murai, “A Heuristic Algorithm for Generating Decision Rules in Variable Precision Rough Set Models,” Proc. of SCIS & ISIS 2010, pp. 1568-1573, 2010. https://doi.org/10.14864/softscis.2010.0.1568.0
- [11] X. D. Song, J. W. Mu, R. F. Feng, and Z. Z. Qiu, “Variable Precision Rough Set Optimization Algorithm for Constructing Decision Tree,” Advanced Materials Research, Vols.181-182, pp. 43-48, 2011. https://doi.org/10.4028/www.scientific.net/AMR.181-182.43
- [12] Y. Weiguo, L. Mingyu, and L. Zhi, “Variable precision rough set based decision tree classifier,” J. of Intelligent & Fuzzy Systems, Vol.23, Nos.2-3, pp. 61-70, 2012. https://doi.org/10.3233/IFS-2012-0496
- [13] Y. Liu, Y. Lin, and H.-h. Zhao, “Variable precision intuitionistic fuzzy rough set model and applications based on conflict distance,” Expert Systems, Vol.32, No.2, pp. 220-227, 2015. https://doi.org/10.1111/exsy.12083
- [14] F. M. Perez, J. V. B. Martienz, A. F. Oliva, and M. A. Ortega, “Application of the Variable Precision Rough Sets Model to Estimate the Outlier Probability of Each Element,” Complexity, Vol.2018, No.1, Article No.4867607, 2018. https://doi.org/10.1155/2018/4867607
- [15] A. Apriani, I. T. R. Yanto, S. Fathurrohmah, S. Haryatmi, and D. Danardono, “Variable precision rough set model for attribute selection on environment impact dataset,” Int. J. of Advances in Intelligent Informatics, Vol.4, No.1, pp. 70-75, 2018. https://doi.org/10.26555/ijain.v4i1.109
- [16] B. Yu, Y. Hu, and J. Dai, “A bi-variable precision rough set model and its application to attribute reduction,” Information Sciences, Vol. 645, Article No.119368, 2023. https://doi.org/10.1016/j.ins.2023.119368
- [17] Z. T. Gong, B. Z. Sun, Y. B. Shao, D. G. Chen, and Q. He, “Variable precision rough set model based on general relation,” Proc. of 2024 Int. Conf. Machine Learning and Cybernetics, Vol.4, pp. 2490-2494, 2024. https://doi.org/10.1109/ICMLC.2004.1382222
- [18] Y. Nakahama, H. Okawa, Y. Kudo, and T. Murai, “An Improvement of β-reduct and Its Computation in Variable Precision Rough Set Model,” J. of the Japan Society for Fuzzy Theory and Intelligent Informatics, Vol.37, No.1, pp. 596-606, 2025 (in Japanese). https://doi.org/10.3156/jsoft.37.1_596
- [19] Y. Kudo and H. Okawa, “β̂-QuickReduct: A Heuristic Algorithm for Computing a β̂-Reduct Candidate in Variable Precision Rough Set Model,” Proc. of 41th Fuzzy System Symp. (FSS2025), 2025 (in Japanese). https://doi.org/10.14864/fss.41.0_563
- [20] A. Chouchoulas and Q. Shen, “Rough Set-Aided Keyword Reduction for Text Categorization,” Applied Artificial Intelligence, Vol.15, No.9, pp. 843-873, 2001. https://doi.org/10.1080/088395101753210773
- [21] A. Skowron and C. Rauser, “The discernibility matrix and functions in information systems,” R. Słowiński (Ed.), “Intelligent Decision Support. Theory and Decision Library,” pp. 331-362, Springer, 1992. https://doi.org/10.1007/978-94-015-7975-9_21
- [22] UCI Machine Learning Repository. http://archive.ics.uci.edu/ [Accessed October 1, 2019]
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.