nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Similarity-based Rough Sets and Its Applications in Data Mining

verfasst von : Dávid Nagy

Erschienen in: Transactions on Rough Sets XXII

Verlag: Springer Berlin Heidelberg

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Pawlakian spaces rely on an equivalence relation which represent indiscernibility. As a generalization of these spaces, some approximation spaces have appeared that are not based on an equivalence relation but on a tolerance relation that represents similarity. These spaces preserve the property of the Pawlakian space that the union of the base sets gives out the universe. However, they give up the requirement that the base sets are pairwise disjoint. The base sets are generated in a way where for each object, the objects that are similar to the given object, are taken. This means that the similarity to a given object is considered. In the worst case, it can happen that the number of base sets equals those of objects in the universe. This significantly increases the computational resource need of the set approximation process and limits the efficient use of them in large databases. To overcome this problem, a possible solution is presented in this dissertation. The space is called similarity-based rough sets where the system of base sets is generated by the correlation clustering. Therefore, the real similarity is taken into consideration not the similarity to a distinguished object. The space generated this way, on the one hand, represents the interpreted similarity properly and on the other hand, reduces the number of base sets to a manageable size. This work deals with the properties and applicability of this space, presenting all the advantages that can be gained from the correlation clustering.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A Study of Algebras and Logics of Rough Sets Based on Classical and Generalized Approximation Spaces

Nur mit Berechtigung zugänglich

The work described in this chapter was based on [5‐7, 21, 35‐38].

The formal definition of these answers can also be seen in the first chapter but for better readability, they are also listed here again focusing on covering approximation spaces based on a tolerance relation.

The work described in this section was based on [38].

The work described in this section was based on [37].

The work described in this section was based on [5‐7, 35].

The work described in this section was based on [5].

The work described in this section was based on [6, 7, 21, 35].

The work described in this section was based on [21].

The work described in this section was based on [6, 7].

The work described in this section was based on [35].

The work described in this chapter was based on [6, 35].

The work described in this section was based on [35].

The work described in this section was based on [6].

Aigner, M.: Enumeration via ballot numbers. Discrete Math. 308(12), 2544–2563 (2008). https://doi.org/10.1016/j.disc.2007.06.012, http://www.sciencedirect.com/science/article/pii/S0012365X07004542

Altman, A., Tennenholtz, M.: Ranking systems: the PageRank axioms. In: Proceedings of the 6th ACM Conference on Electronic Commerce, pp. 1–8. ACM (2005)

Aszalós, L., Bakó, M.: Advanced search methods (in Hungarian) (2012). http://morse.inf.unideb.hu/~aszalos/diak/fka

Aszalós, L., Hajdu, L., Pethő, A.: On a correlational clustering of integers. Indagationes Mathematicae 27(1), 173–191 (2016)MathSciNetCrossRef

Aszalós, L., Nagy, D.: Visualization of tolerance relations. In: Gábor, Kusper; Roland, K. (ed.) Proceedings of the 10th International Conference on Applied Informatics, pp. 15–22 (2018)

Aszalós, L., Nagy, D.: Iterative set approximations based on tolerance relation. In: Mihálydeák, T., et al. (eds.) Rough Sets, pp. 78–90. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-22815-6_7CrossRefMATH

Aszalós, L., Nagy, D.: Selecting representatives. In: Ganzha, M., Maciaszek, L., Paprzycki, M. (eds.) Communication Papers of the 2019 Federated Conference on Computer Science and Information Systems. Annals of Computer Science and Information Systems, vol. 20, pp. 13–19. PTI (2019). https://doi.org/10.15439/2019F95

Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1–3), 89–113 (2004)MathSciNetCrossRef

Becker, H.: A survey of correlation clustering. Advanced Topics in Computational Learning Theory, pp. 1–10 (2005)

10.

Bello, R., Falcon, R.: Rough Sets in Machine Learning: A Review, pp. 87–118. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-54966-8_5

11.

Brownlee, J.: Clever Algorithms: Nature-Inspired Programming Recipes. 1st edn. Lulu.com (2011)

12.

Caballero, Y., Bello, R., Alvarez, D., Gareia, M.M., Pizano, Y.: Improving the K-NN method: rough set in edit training set. In: Debenham, J. (ed.) Professional Practice in Artificial Intelligence, pp. 21–30. Springer, Boston (2006)CrossRef

13.

Ciucci, D., Mihálydeák, T., Csajbók, Z.E.: On Definability and Approximations in Partial Approximation Spaces, pp. 15–26. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-11740-9_2

14.

Csajbók, Z., Mihálydeák, T.: From vagueness to rough sets in partial approximation spaces. In: JRS2014 (submitted, 2014)

15.

Csajbók, Z., Mihálydeák, T.: A general set theoretic approximation framework. In: Greco, S., Bouchon-Meunier, B., Coletti, G., Fedrizzi, M., Matarazzo, B., Yager, R. (eds.) Advances on Computational Intelligence, Communications in Computer and Information Science, vol. 297, pp. 604–612. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31709-5_61

16.

Csajbók, Z., Mihálydeák, T.: Partial approximative set theory: a generalization of the rough set theory. Int. J. Comput. Inf. Syst. Ind. Manag. Appl. 4, 437–444 (2012)

17.

Delic, D., Lenz, H.J., Neiling, M.: Improving the quality of association rule mining by means of rough sets. In: Grzegorzewski, P., Hryniewicz, O., Gil, M.Á. (eds.) Soft Methods in Probability, Statistics and Data Analysis, pp. 281–288. Physica-Verlag HD, Heidelberg (2002)CrossRef

18.

Dubois, D., Prade, H.: Twofold fuzzy sets and rough sets–some issues in knowledge representation. Fuzzy Sets Syst. 23(1), 3–18 (1987). https://doi.org/10.1016/0165-0114(87)90096-0, http://www.sciencedirect.com/science/article/pii/0165011487900960. fuzzy Information Processing in Artificial Intelligence and Operations Research

19.

Dubois, D., Prade, H.: Rough fuzzy sets and fuzzy rough sets*. Int. J. Gener. Syst. 17(2–3), 191–209 (1990). https://doi.org/10.1080/03081079008935107

20.

Düntsch, I., Gediga, G.: Approximation Operators in Qualitative Data Analysis, pp. 214–230. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-24615-2_10

21.

Dávid, N., László Aszalós, T.M.: Finding the representative in a cluster using correlation clustering. Pollack Periodica 14(1), 15–24 (2019). https://doi.org/10.1556/606.2019.14.1.2

22.

Erdös, P., Rényi, A.: On random graphs I. Publ. Math. Debrecen 6, 290 (1959)MathSciNetMATH

23.

Erdős, P., Rényi, A.: On the evolution of random graphs. In: Publication of the Mathematical Institute of the Hungarian Academy of Sciences, pp. 17–61 (1960)

24.

Filiberto, Y., Caballero, Y., Larrua, R., Bello, R.: A method to build similarity relations into extended rough set theory. In: 2010 10th International Conference on Intelligent Systems Design and Applications, pp. 1314–1319, November 2010. https://doi.org/10.1109/ISDA.2010.5687091

25.

Gogoi, P., Bhattacharyya, D.K., Kalita, J.K.: A rough set-based effective rule generation method for classification with an application in intrusion detection. Int. J. Secur. Netw. 8(2), 61–71 (2013). https://doi.org/10.1504/IJSN.2013.055939

26.

Greco, S., Matarazzo, B., Słowiński, R.: Parameterized rough set model using rough membership and bayesian confirmation measures. Int. J. Approx. Reason. 49(2), 285–300 (2008). https://doi.org/10.1016/j.ijar.2007.05.018, http://www.sciencedirect.com/science/article/pii/S0888613X0700151X. special Section on Probabilistic Rough Sets and Special Section on PGM’06

27.

Grzymala-Busse, J.W.: LERS-A System for Learning from Examples Based on Rough Sets, pp. 3–18. Springer, Dordrecht (1992). https://doi.org/10.1007/978-94-015-7975-9_1

28.

Guan, J.W., Bell, D.A., Liu, D.Y.: The rough set approach to association rule mining. In: Third IEEE International Conference on Data Mining, pp. 529–532, November 2003. https://doi.org/10.1109/ICDM.2003.1250969

29.

Hu, Q., Yu, D., Liu, J., Wu, C.: Neighborhood rough set based heterogeneous feature subset selection. Inf. Sci. 178(18), 3577–3594 (2008). https://doi.org/10.1016/j.ins.2008.05.024, http://www.sciencedirect.com/science/article/pii/S0020025508001643

30.

Janusz, A.: Algorithms for similarity relation learning from high dimensional data. Trans. Rough Sets 17, 174–292 (2014)CrossRef

31.

Lenarcik, A., Piasta, Z.: Discretization of Condition Attributes Space, pp. 373–389. Springer, Dordrecht (1992). https://doi.org/10.1007/978-94-015-7975-9_23

32.

Mani, A.: Choice inclusive general rough semantics. Inf. Sci. 181(6), 1097–1115 (2011)MathSciNetCrossRef

33.

Mihálydeák, T.: Logic on similarity based rough sets. In: Nguyen, H.S., Ha, Q.T., Li, T., Przybyła-Kasperek, M. (eds.) Rough Sets, pp. 270–283. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99368-3_21CrossRef

34.

Mises, R.V., Pollaczek-Geiringer, H.: Praktische verfahren der gleichungsauflösung. ZAMM - Journal of Applied Mathematics and Mechanics / Zeitschrift für Angewandte Mathematik und Mechanik 9(2), 152–164 (1929). https://doi.org/10.1002/zamm.19290090206, https://onlinelibrary.wiley.com/doi/abs/10.1002/zamm.19290090206

35.

Nagy, D., Aszalós, L.: Approximation based on representatives. In: Mihálydeák, T., et al. (eds.) Rough Sets, pp. 91–101. Springer, Cham (2019). https://doi.org/10.1007/978-3-642-31900-6_48CrossRefMATH

36.

Nagy, D., Mihálydeák, T., Aszalós, L.: Similarity Based Rough Sets, pp. 94–107. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-60840-2_7

37.

Nagy, D., Mihálydeák, T., Aszalós, L.: Similarity based rough sets with annotation. In: Nguyen, H.S., Ha, Q.T., Li, T., Przybyła-Kasperek, M. (eds.) Rough Sets, pp. 88–100. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-99368-3_7CrossRefMATH

38.

Nagy, D., Mihalydeak, T., Aszalos, L.: Different types of search algorithms for rough sets. Acta Cybern. 24(1), 105–120 (2019). https://doi.org/10.14232/actacyb.24.1.2019.8, http://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3999

39.

Néda, Z., Sumi, R., Ercsey-Ravasz, M., Varga, M., Molnár, B., Cseh, G.: Correlation clustering on networks. J. Phys. A: Math. Theor. 42(34), 345003 (2009). https://doi.org/10.1088/1751-8113/42/34/345003, http://www.journalogy.net/Publication/18892707/correlation-clustering-on-networks

40.

Néda, Z., Sumi, R., Ercsey-Ravasz, M., Varga, M., Molnár, B., Cseh, G.: Correlation clustering on networks. J. Phys. A: Math. Theor. 42(34), 345003 (2009)MathSciNetCrossRef

41.

Nguyen, H.S.: Discretization problem for rough sets methods. In: Polkowski, L., Skowron, A. (eds.) Rough Sets Curr. Trends Comput., pp. 545–552. Springer, Heidelberg (1998). https://doi.org/10.1007/3-540-69115-4_75CrossRef

42.

Pawlak, Z.: Rough sets. Int. J. Parallel Prog. 11(5), 341–356 (1982)MATH

43.

Pawlak, Z., Skowron, A.: Rudiments of rough sets. Inf. Sci. 177(1), 3–27 (2007)MathSciNetCrossRef

44.

Pawlak, Z., Wong, S., Ziarko, W.: Rough sets: probabilistic versus deterministic approach. Int. J. Man-Mach. Stud. 29(1), 81–95 (1988). https://doi.org/10.1016/S0020-7373(88)80032-4

45.

Pawlak, Z., et al.: Rough sets: theoretical aspects of reasoning about data. In: System Theory, Knowledge Engineering and Problem Solving, Kluwer Academic Publishers, Dordrecht, 1991, September 1991

46.

Pawlak, Z., Skowron, A.: Rough sets: some extensions. Inf. Sci. 177(1), 28–40 (2007). https://doi.org/10.1016/j.ins.2006.06.006, http://www.sciencedirect.com/science/article/pii/S0020025506001496, zdzisław Pawlak life and work (1926–2006)

47.

Polkowski, L., Skowron, A., Zytkow, J.: Rough foundations for rough sets soft computing: rough sets, fuzzy logic, neural networks, uncertainty management, knowledge discovery, pp. 55–58, May 2020

48.

do Prado, H.A., Engel, P.M., Filho, H.C.: Rough clustering: an alternative to find meaningful clusters by using the reducts from a dataset. In: Alpigini, J.J., Peters, J.F., Skowron, A., Zhong, N. (eds.) RSCTC 2002. LNCS (LNAI), vol. 2475, pp. 234–238. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45813-1_30CrossRefMATH

49.

Skowron, A., Stepaniuk, J.: Tolerance approximation spaces. Fundamenta Informaticae 27(2), 245–253 (1996)MathSciNetCrossRef

50.

Ślęzak, D., Ziarko, W.: The investigation of the bayesian rough set model. Int. J. Approx. Reason. 40(1), 81–91 (2005). https://doi.org/10.1016/j.ijar.2004.11.004, http://www.sciencedirect.com/science/article/pii/S0888613X04001410. data Mining and Granular Computing

51.

Słowiński, R., Vanderpooten, D.: A generalized definition of rough approximations based on similarity. IEEE Trans. Knowl. Data Eng. 12(2), 331–336 (2000)CrossRef

52.

Słowiński, R., Vanderpooten, D.: Similarity relation as a basis for rough approximations. Adv. Mach. Intell. Soft-Comput. 4, 17–33 (1997)

53.

Swiniarski, R.W., Skowron, A.: Rough set methods in feature selection and recognition. Pattern Recogn. Lett. 24(6), 833–849 (2003). https://doi.org/10.1016/S0167-8655(02)00196-4, http://www.sciencedirect.com/science/article/pii/S0167865502001964

54.

Yang, Y., Chen, D., Dong, Z.: Novel algorithms of attribute reduction with variable precision rough set model. Neurocomputing 139, 336–344 (2014). https://doi.org/10.1016/j.neucom.2014.02.023

55.

Yao, Y.Y.: Combination of Rough and Fuzzy Sets Based on \(\alpha \)-Level Sets, pp. 301–321. Springer, Boston (1997). https://doi.org/10.1007/978-1-4613-1461-5_15

56.

Yao, Y.: Decision-theoretic rough set models. In: Yao, J., Lingras, P., Wu, W.Z., Szczuka, M., Cercone, N.J., Ślęzak, D. (eds.) Rough Sets and Knowledge Technology, pp. 1–12. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72458-2_1CrossRef

57.

Yao, Y., Greco, S., Słowiński, R.: Probabilistic Rough Sets, pp. 387–411. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-43505-2_24

58.

Yao, Y., Yao, B.: Covering based rough set approximations. Information Sciences 200, 91–107 (2012). https://doi.org/10.1016/j.ins.2012.02.065, http://www.sciencedirect.com/science/article/pii/S0020025512001934

59.

Zakowski, W.: Approximations in the space (u,\(\pi \)). Demonstratio Math. 16(3), 761–770 (1983). https://doi.org/10.1515/dema-1983-0319MathSciNetCrossRefMATH

60.

Zimek, A.: Correlation clustering. ACM SIGKDD Explor. Newslett. 11(1), 53–54 (2009)CrossRef

Titel: Similarity-based Rough Sets and Its Applications in Data Mining
verfasst von: Dávid Nagy
Verlag: Springer Berlin Heidelberg
Buch: Transactions on Rough Sets XXII
Print ISBN: 978-3-662-62797-6

Electronic ISBN: 978-3-662-62798-3

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-662-62798-3_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner