Logo PTI Logo FedCSIS

Proceedings of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS)

Annals of Computer Science and Information Systems, Volume 43

Estimating the entropy of covering-based rough set approximation operators

, , ,

DOI: http://dx.doi.org/10.15439/2025F0110

Citation: Proceedings of the 20th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 43, pages 195–205 ()

Full text

Abstract. Rough set theory provides a robust framework for dealing with inconsistent data by utilizing equivalence relations to group indiscernible instances. A significant extension of this framework is the concept of covering-based rough sets, where equivalence relations are replaced with coverings. The effectiveness of covering-based rough sets in practical applications largely depends on the choice of an appropriate covering. To guide this selection, various metrics have been proposed to evaluate the quality of coverings, including entropy. While entropy serves as a valuable measure, its exact computation is often prohibitively expensive. In this paper, we propose an efficient method for estimating the entropy of covering-based rough set approximation operators, making the metric more feasible for practical use. We assess the accuracy of these estimates through experiments on both synthetic coverings and coverings for real-world datasets, the latter constructed using the Mapper algorithm, from the field of topological data analysis.

References

  1. Z. Pawlak, “Rough sets,” International Journal of Computer and Information Sciences, vol. 11, no. 5, pp. 341–356, 1982. https://dx.doi.org/10.1007/BF01001956
  2. Y. Yao, “On generalizing rough set theory,” in Lecture Notes in Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg, 2007, pp. 44–51.
  3. Z. Shi and Z. Gong, “The further investigation of covering-based rough sets: Uncertainty characterization, similarity measure and generalized models,” Information Sciences, vol. 180, no. 19, pp. 3745–3763, 2010. https://dx.doi.org/10.1016/j.ins.2010.06.020
  4. T. Yang and Q. Li, “Reduction about approximation spaces of covering generalized rough sets,” International Journal of Approximate Reasoning, vol. 51, no. 3, pp. 335–345, 2010. https://dx.doi.org/10.1016/j.ijar.2009.11.001
  5. I. Couso and D. Dubois, “Rough sets, coverings and incomplete information,” Fundam. Inform., vol. 108, pp. 223–247, 01 2011. https://dx.doi.org/10.3233/FI-2011-421
  6. J. Järvinen and S. Radeleczki, “Rough sets determined by tolerances,” International Journal of Approximate Reasoning, vol. 55, no. 6, pp. 1419–1438, 2014. https://dx.doi.org/10.1016/j.ijar.2013.12.005
  7. D. Chen, X. Zhang, and W. Li, “On measurements of covering rough sets based on granules and evidence theory,” Information Sciences, vol. 317, pp. 329–348, 2015. https://dx.doi.org/10.1016/j.ins.2015.04.051
  8. L. D’eer and C. Cornelis, “Notes on covering-based rough sets from topological point of view: Relationships with general framework of dual approximation operators,” International Journal of Approxi- mate Reasoning, vol. 88, pp. 295–305, 2017. https://dx.doi.org/10.1016/j.ijar.2017.06.006
  9. M. Restrepo, C. Cornelis, and J. Gómez, “Partial order relation for approximation operators in covering based rough sets,” Information Sciences, vol. 284, pp. 44–59, 2014. https://dx.doi.org/10.1016/j.ins.2014.06.032
  10. M. Restrepo, C. Cornelis, and J. Gómez, “Duality, conjugacy and adjointness of approximation operators in covering-based rough sets,” International Journal of Approximate Reasoning, vol. 55, no. 1, Part 4, pp. 469–485, 2014. https://dx.doi.org/10.1016/j.ijar.2013.08.002 Rough Sets and Logic.
  11. C. Wang, M. Shao, B. Sun, and Q. Hu, “An improved attribute reduction scheme with covering based rough sets,” Applied Soft Computing, vol. 26, pp. 235–243, 2015. https://dx.doi.org/10.1016/j.asoc.2014.10.006
  12. L. Fachao, R. Yexing, and J. Chenxia, “Attribute reduction method of covering rough set based on dependence degree,” International Journal of Computational Intelligence Systems, vol. 14, pp. 1419–1425, 2021. https://dx.doi.org/10.2991/ijcis.d.210419.002
  13. Y. Yang, D. Chen, X. Zhang, and Z. Ji, “Covering rough set-based incremental feature selection for mixed decision system,” Soft Comput., vol. 26, no. 6, pp. 2651–2669, 2022. https://dx.doi.org/10.1007/s00500-021-06687-0
  14. P. Zhu and Q. Wen, “Entropy and co-entropy of a covering approximation space,” International Journal of Approximate Reasoning, vol. 53, no. 4, pp. 528–540, 2012. https://dx.doi.org/10.1016/j.ijar.2011.12.004
  15. Z. Li, S. Wei, and S. Liu, “Outlier detection using conditional information entropy and rough set theory,” Journal of Intelligent & Fuzzy Systems, vol. 46, no. 1, pp. 1899–1918, 2024. https://dx.doi.org/10.3233/JIFS-236009
  16. L. Zhou and F. Jiang, “A rough set approach to feature selection based on relative decision entropy,” in Rough Sets and Knowledge Technology. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011. https://dx.doi.org/10.1007/978-3-642-24425-4 17 pp. 110–119.
  17. M. Restrepo and C. Cornelis, “Mapper-based rough sets,” in Rough Sets: International Joint Conference, IJCRS 2024, Halifax, NS, Canada, May 17–20, 2024, Proceedings, Part I. Berlin, Heidelberg: Springer-Verlag, 2024. https://dx.doi.org/10.1007/978-3-031-65665-1_1 p. 3–17.
  18. A. D. Smith, P. Dłotko, and V. M. Zavala, “Topological data analysis: Concepts, computation, and applications in chemical engineering,” Computers Chemical Engineering, vol. 146, 2021. doi: https://doi.org/10.1016/j.compchemeng.2020.107202
  19. V. Q. Vu, B. Yu, and R. E. Kass, “Coverage-adjusted entropy estimation,” Statistics in Medicine, vol. 26, no. 21, pp. 4039–4060, 2007. https://dx.doi.org/10.1002/sim.2942
  20. J. G. Bazan, H. S. Nguyen, S. H. Nguyen, P. Synak, and J. Wróblewski, Rough Set Algorithms in Classification Problem. Heidelberg: Physica-Verlag HD, 2000, pp. 49–88.
  21. W. Ziarko and N. Shan, “Discovering attribute relation ships, dependencies and rules by using rough sets,” in Proceedings of the Twenty-Eighth Annual Hawaii International Conference on System Sciences, vol. 3, 1995. https://dx.doi.org/10.1109/HICSS.1995.375608 pp. 293–299 vol.3.
  22. H. Alqaheri, A. E. Hassanien, and A. Abraham, “Dis covering stock price prediction rules using rough sets,” Neural Network World, vol. 18, 01 2008.
  23. M. S. Raza and U. Qamar, Understanding and using rough set based feature selection: Concepts, tech niques and applications, 2nd ed. Singapore, Singapore: Springer, Sep. 2019.
  24. K. Thangavel and A. Pethalakshmi, “Dimensionality re duction based on rough set theory: A review,” Applied Soft Computing, vol. 9, no. 1, pp. 1–12, 2009. https://dx.doi.org/10.1016/j.asoc.2008.05.006
  25. A. K. Das, S. Sengupta, and S. Bhattacharyya, “A group incremental feature selection for classification using rough set theory based genetic algorithm,” Applied Soft Computing, vol. 65, pp. 400–411, 2018. https://dx.doi.org/10.1016/j.asoc.2018.01.040
  26. W. De Maeyer, C. Cornelis, and M. Restrepo, “The granular structure of covering-based rough sets generated by mapper,” in Proceedings of 16th European Symposium on Computational Intelligence and Mathematics (ESCIM 2025), in press.
  27. B. S. Everitt, S. Landau, M. Leese, and D. Stahl, Cluster Analysis, 5th ed., ser. Wiley Series in Probability and Statistics. Hoboken, NJ: Wiley-Blackwell, 2011.
  28. C. Shannon, “A mathematical theory of communication,” The Bell System Technical Journal, vol. 27, no. 3, pp. 379–423, 1948. https://dx.doi.org/10.1002/j.1538-7305.1948.tb01338.x
  29. L. Paninski, “Estimation of entropy and mutual infor mation,” Neural Computation, vol. 15, pp. 1191–1253, 2003. https://dx.doi.org/10.1162/089976603321780272
  30. A. Chao and T.-J. Shen, “Nonparametric estimation of shannon’s diversity index when there are unseen species in sample. environ ecol stat 10: 429-443,” Environmental and Ecological Statistics, vol. 10, pp. 429–443, 2003. https://dx.doi.org/10.1023/A:1026096204727
  31. D. G. Horvitz and D. J. Thompson, “A generalization of sampling without replacement from a finite universe,” Journal of the American Statistical Association, vol. 47, no. 260, pp. 663–685, 1952. https://dx.doi.org/10.2307/2280784
  32. M. Skorski, “Improved estimation of collision entropy in high and low-entropy regimes and applications to anomaly detection,” IACR Cryptol. ePrint Arch., vol. 2016, p. 1035, 2016.
  33. M. Kelly, R. Longjohn, and K. Nottingham, the UCI Machine Learning Repository. [Online]. Available: https://archive.ics.uci.edu