|
|
基于区间值决策系统的正域快速求解算法
|
Abstract:
区间值决策系统在不确定性数据处理领域具有重要应用价值，而正域的高效计算是提升系统整体性能的关键。由于相容类的计算是正域求解的必要步骤，但是传统相容类计算方法在处理大规模数据时面临较高的计算复杂度，导致属性约简的效率显著下降。针对这一问题，本文提出了一种利用哈希思想的快速计算方法。该方法通过哈希函数对每个对象进行快速分区，缩小相容类的查找范围，减少冗余计算，从而显著提升了相容类的计算效率，以至于能够优化属性约简的整体性能。通过在8个UCI数据集上的实验验证，本文所提方法在计算速度上较传统方法具有明显优势，为区间值决策系统的高效属性约简算法提供了新思路。
Interval-valued decision systems play a crucial role in uncertain data processing, where the efficient computation of the positive domain is essential for enhancing overall system performance. Since the computation of compatible classes is a necessary step in solving the positive domain, traditional methods for computing compatible classes face high computational complexity when handling large-scale data, leading to a significant decline in attribute reduction efficiency. To address this issue, this paper proposes a fast computation method based on hashing techniques. By utilizing hash functions to rapidly partition each object, the proposed method narrows the search scope for compatible classes, reduces redundant computations, and significantly improves the efficiency of compatible class computation, thereby optimizing the overall performance of attribute reduction. Experimental validation on eight UCI datasets demonstrates that the proposed method achieves a significant speed advantage over traditional approaches, providing new insights for developing efficient attribute reduction algorithms in interval-valued decision systems.
| [1] | Pawlak, Z. (1982) Rough Sets. International Journal of Computer & Information Sciences, 11, 341-356. https://doi.org/10.1007/bf01001956 |
| [2] | Dai, J., Wang, W., Xu, Q. and Tian, H. (2012) Uncertainty Measurement for Interval-Valued Decision Systems Based on Extended Conditional Entropy. Knowledge-Based Systems, 27, 443-450. https://doi.org/10.1016/j.knosys.2011.10.013 |
| [3] | Chen, B., Zhang, X. and Yuan, Z. (2024) Two-Dimensional Improved Attribute Reductions Based on Distance Granulation and Condition Entropy in Incomplete Interval-Valued Decision Systems. Information Sciences, 657, Article 119910. https://doi.org/10.1016/j.ins.2023.119910 |
| [4] | 张楠, 苗夺谦, 岳晓冬. 区间值信息系统的知识约简[J]. 计算机研究与发展, 2010, 47(8): 1362-1371. |
| [5] | Yao, Y. and Zhao, Y. (2008) Attribute Reduction in Decision-Theoretic Rough Set Models. Information Sciences, 178, 3356-3373. https://doi.org/10.1016/j.ins.2008.05.010 |
| [6] | Wang, C., Huang, Y., Ding, W. and Cao, Z. (2021) Attribute Reduction with Fuzzy Rough Self-Information Measures. Information Sciences, 549, 68-86. https://doi.org/10.1016/j.ins.2020.11.021 |
| [7] | Li, Z., Zhang, Q., Liu, S., Peng, Y. and Li, L. (2024) Information Fusion and Attribute Reduction for Multi-Source Incomplete Mixed Data via Conditional Information Entropy and D-S Evidence Theory. Applied Soft Computing, 151, Article 111149. https://doi.org/10.1016/j.asoc.2023.111149 |
| [8] | 苗夺谦, 胡桂荣. 知识约简的一种启发式算法[J]. 计算机研究与发展, 1999, 36(6): 42-45. |
| [9] | Yao, Y. and Zhao, Y. (2009) Discernibility Matrix Simplification for Constructing Attribute Reducts. Information Sciences, 179, 867-882. https://doi.org/10.1016/j.ins.2008.11.020 |
| [10] | Qian, W., Wan, L. and Shu, W. (2024) Semi-Supervised Feature Selection Based on Discernibility Matrix and Mutual Information. Applied Intelligence, 54, 7278-7295. https://doi.org/10.1007/s10489-024-05481-3 |
| [11] | 杨明. 一种基于改进差别矩阵的核增量式更新算法[J]. 计算机学报, 2006, 29(3): 407-413. |
| [12] | Sowkuntla, P. and Sai Prasad, P.S.V.S. (2025) Parallel Attribute Reduction in High-Dimensional Data: An Efficient Mapreduce Strategy with Fuzzy Discernibility Matrix. Applied Soft Computing, 172, Article 112870. https://doi.org/10.1016/j.asoc.2025.112870 |
| [13] | 徐伟华. 序信息系统与粗糙集[M]. 北京: 科学出版社, 2013. |
| [14] | Yong, L., Wenliang, H., Yunliang, J. and Zhiyong, Z. (2014) Quick Attribute Reduct Algorithm for Neighborhood Rough Set Model. Information Sciences, 271, 65-81. https://doi.org/10.1016/j.ins.2014.02.093 |
