Different Types of Search Algorithms for Rough Sets

Keywords: rough set theory, set approximation, data mining


Based on the available information in many cases it can happen that two objects cannot be distinguished. If a set of data is given and in this set
two objects have the same attribute values, then these two objects are called indiscernible. This indiscernibility has an effect on the membership relation,
because in some cases it makes our judgment uncertain about a given object. The uncertainty appears because if something about an object is needed to be
stated, then all the objects that are indiscernible from the given object must be taken into consideration. The indiscernibility relation is an equivalence
relation which represents background knowledge embedded in an information system. In a Pawlakian system this relation is used in set approximation.
Correlation clustering is a clustering technique which generates a partition. In the authors’ previous research the possible usage of the correlation clustering
in rough set theory was investigated. In this paper the authors show how different types of search algorithms affect the set approximation.


Aigner, Martin. Enumeration via ballot numbers. Discrete Mathematics, 308(12):2544 - 2563, 2008. DOI: 10.1016/j.disc.2007.06.012.

Aszalós, László and Mária, Bakó. Advanced Search Methods. Educatio Társadalmi Szolgáltató Nonprofit Kft., 2012. in Hungarian.

Bansal, Nikhil, Blum, Avrim, and Chawla, Shuchi. Correlation clustering. Machine Learning, 56(1-3):89--113, 2004.

Becker, Hila. A survey of correlation clustering. Advanced Topics in Computational Learning Theory, pages 1--10, 2005.

Brownlee, Jason. Clever Algorithms: Nature-Inspired Programming Recipes. Lulu.com, 1st edition, 2011.

Erdős, P. and Rényi, A. On random graphs I. Publicationes Mathematicae Debrecen, 6:290, 1959.

Erdős, P. and Rényi, A. On the evolution of random graphs. In Publication of the Mathematical Institute of the Hungarian Academy of Sciences, pages 17--61, 1960.

Mani, A. Choice inclusive general rough semantics. Information Sciences, 181(6):1097--1115, 2011.

Mihálydeák, Tamás. Logic on similarity based rough sets. In Nguyen, Hung~Son, Ha, Quang-Thuy, Li, Tianrui, and Przybyla-Kasperek, Malgorzata, editors, Rough Sets, pages 270--283, Cham, 2018. Springer International Publishing.

Nagy, Dávid, Mihálydeák, Tamás, and Aszalós, László. 10.1007/978-3-319-60840-2_7, Similarity Based Rough Sets, pages 94--107.

Springer International Publishing, Cham, 2017.

Nagy, Dávid, Mihálydeák, Tamás, and Aszalós, László. Similarity based rough sets with annotation. In Nguyen, Hung~Son, Ha, Quang-Thuy, Li, Tianrui, and Przybyla-Kasperek, Malgorzata, editors, Rough Sets, pages 88--100, Cham, 2018. Springer International Publishing.

Pawlak, Zdzislaw. Rough sets. International Journal of Parallel Programming, 11(5):341--356, 1982.

Pawlak, Zdzislaw et al. Rough sets: Theoretical aspects of reasoning about data. Systern Theory, Knowledge Engineering and Problem Solving, Kluwer Academic Publishers, Dordrecht, 199l, 9, 1991.

Pawlak, Zdzislaw and Skowron, Andrzej. Rudiments of rough sets. Information sciences, 177(1):3--27, 2007.

Skowron, Andrzej and Stepaniuk, Jaroslaw. Tolerance approximation spaces. Fundamenta Informaticae, 27(2):245--253, 1996.

Yao, Yiyu and Yao, Bingxue. Covering based rough set approximations. Information Sciences, 200:91 - 107, 2012. DOI: 10.1016/j.ins.2012.02.065.

Zimek, Arthur. Correlation clustering. ACM SIGKDD Explorations Newsletter, 11(1):53--54, 2009.

How to Cite
Nagy, D., Mihalydeak, T., & Aszalos, L. (2019). Different Types of Search Algorithms for Rough Sets. Acta Cybernetica, 24(1), 105-120. https://doi.org/10.14232/actacyb.24.1.2019.8
Special Issue of the 11th Conference of PhD Students in Computer Science