|
|
区间值决策系统下的最小属性约简
|
Abstract:
在给定的属性约简目标函数下，决策表中往往存在多个约简。最后的决策规则集直接依赖于所获得的约简。决策规则集的简洁性、可理解性、通用性和精确性因约简的不同而不同，因此期望得到一些最优结果，即长度最短的最小约简。这样可以尽可能多地去除冗余属性，有效地管理决策表的存储空间，并且决策规则集的性能将变得优异。不幸的是，寻找最小约简已被证明是一个NP-难问题(Wong和Ziarko 1985)。当给定决策表时，启发式算法并不总是能得到最小约简。因此本文在区间值决策系统下提出了基于差别矩阵的0-1规划最短约简算法。
With a given attribute reduction objective function, there are often multiple reductions in the deci-sion table. The final decision rule set is directly dependent on the obtained reductions. The con-ciseness, comprehensibility, generality and accuracy of the decision rule set vary from one reduc-tion to another, so it is expected to obtain some optimal result, i.e., the smallest reduction with the shortest length. This will remove as many redundant attributes as possible, manage the storage space of the decision table efficiently, and the performance of the decision rule set will become superior. Unfortunately, finding the minimum reduction has been shown to be an NP-hard problem (Wong and Ziarko, 1985). Heuristic algorithms do not always yield the minimum reduction when given a decision table. Therefore, in this paper, we propose a difference matrix-based shortest reduction algorithm for 0-1 programming under interval-valued decision system.
| [1] | Pawlak, Z. (1982) Rough Sets. International Journal of Computer and Information Sciences, 11, 341-356.
https://doi.org/10.1007/BF01001956 |
| [2] | Chen, Q., Huang, M., Wang, H. and Xu, G. (2022) A Feature Discreti-zation Method Based on Fuzzy Rough Sets for High-Resolution Remote Sensing Big Data under Linear Spectral Model. IEEE Transactions on Fuzzy Systems, 30, 1328-1342. https://doi.org/10.1109/TFUZZ.2021.3058020 |
| [3] | Dai, J.H., Hu, H., Zheng, G.J., et al. (2016) Attribute Reduction in Interval-Valued Information Systems Based on Infor-mation Entropies. Frontiers of Information Technology & Electronic Engineering, 17, 919-928.
https://doi.org/10.1631/FITEE.1500447 |
| [4] | Sun, L., Yin, T., Ding, W., Qian, Y. and Xu, J. (2022) Feature Selec-tion with Missing Labels Using Multilabel Fuzzy Neighborhood Rough Sets and Maximum Relevance Minimum Re-dundancy. IEEE Transactions on Fuzzy Systems, 30, 1197-1211. https://doi.org/10.1109/TFUZZ.2021.3053844 |
| [5] | Bao, H., Wu, W.Z., Zheng, J.W., et al. (2021) Entropy Based Optimal Scale Combination Selection for Generalized Multi-Scale Information Tables. International Journal of Machine Learning and Cybernetics, 12, 1427-1437.
https://doi.org/10.1007/s13042-020-01243-y |
| [6] | 叶东毅. Jelonek属性约简算法的一个改进[J]. 电子学报, 2000, 28(12): 81-82.
http://dx.chinadoi.cn/10.3321/j.issn:0372-2112.2000.12.023 |
| [7] | 苗夺谦, 胡桂荣. 知识约简的一种启发式算法[J]. 计算机研究与发展, 1999, 36(6): 42-45. |
| [8] | Yao, Y.Y. and Zhang, X.Y. (2017) Class-Specific Attribute Reducts in Rough Set Theory. Information Sciences, 418-419, 601-618. https://doi.org/10.1016/j.ins.2017.08.038 |
| [9] | Shu, W.H. and Qian, W.B. (2015) An Incremental Approach to Attribute Reduction from Dynamic Incomplete Decision Sys-tems in Rough Set Theory. Data & Knowledge Engineering, 100, 116-132.
https://doi.org/10.1016/j.datak.2015.06.009 |
| [10] | Yao, Y. and Zhao, Y. (2008) Discernibility Matrix Simplification for Constructing Attribute Reducts. Information Sciences, 179, 867-882. https://doi.org/10.1016/j.ins.2008.11.020 |
| [11] | Skowron, A. and Rauszer, C. (1992) The Discernibility Matrices and Functions in Information Systems. In: S？owiński, R., Ed., Intelligent Decision Support. Theory and Decision Li-brary, Vol. 11, Springer, Dordrecht, 331-362.
https://doi.org/10.1007/978-94-015-7975-9_21 |
| [12] | Huang, Z.H., Li, J.J., Dai, W.Z. and Lin, R.D. (2019) Gener-alized Multi-Scale Decision Tables with Multi-Scale Decision Attributes. International Journal of Approximate Reason-ing, 115, 194-208.
https://doi.org/10.1016/j.ijar.2019.09.010 |
| [13] | 钱文彬. 基于信息熵的二进制差别矩阵属性约简算法[J]. 计算机工程与应用, 2010, 46(6): 120-123.
http://cea.ceaj.org/CN/10.3778/j.issn.1002-8331.2010.06.034 |
| [14] | 张楠, 许鑫, 童向荣, 等. 不协调区间值决策系统的知识约简[J]. 小型微型计算机系统, 2017, 38(7): 1585-1589. |
| [15] | 刘鹏惠, 陈子春, 秦克云. 区间值信息系统的决策属性约简[J]. 计算机工程与应用, 2009, 45(28): 148-150+229.
http://dx.chinadoi.cn/10.3778/j.issn.1002-8331.2009.28.044 |
| [16] | 尹继亮, 张楠, 赵立威, 等. 区间值决策系统的局部属性约简[J]. 计算机科学, 2018, 45(7): 178-185.
http://dx.chinadoi.cn/10.11896/j.issn.1002-137X.2018.07.031 |
| [17] | Leung, Y., Wu, W.Z. and Mi, J.S. (2008) A Rough Set Approach for the Discovery of Classification Rules in Interval-Valued Information Systems. SSRN Electronic Jour-nal. https://doi.org/10.1016/j.ijar.2007.05.001 |
| [18] | Borowik, G. and Luba, T. (2012) Attribute Reduction Based on the Complementation of Boolean Functions. 1st Australian Conference on the Applications of Systems Engineering ACASE’12, Sydney, 6-8 February 2012. |
| [19] | 詹婉荣, 于海. 基于0-1规划的最小属性约简算法[J]. 洛阳师范学院学报, 2021, 40(2): 1-4.
http://dx.chinadoi.cn/10.3969/j.issn.1009-4970.2021.02.001 |
| [20] | Zhang, X., Mei, C., Chen, D., et al. (2014) Mul-ti-Confidence Rule Acquisition and Confidence-Preserved Attribute Reduction in Interval-Valued Decision Systems. In-ternational Journal of Approximate Reasoning, 55, 1787-1804.
https://doi.org/10.1016/j.ijar.2014.05.007 |
