Skip to main content

2016 | OriginalPaper | Buchkapitel

Correlation Clustering by Contraction, a More Effective Method

verfasst von : László Aszalós, Tamás Mihálydeák

Erschienen in: Recent Advances in Computational Optimization

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

In this article we propose two effective methods to produce a near optimal solution for the problem of correlation clustering. We study their properties at different circumstances, and show that the inner structure generated by a tolerance relation has effect on the accuracy of the methods. Finally, we show that there is no royal road to the sequence of clusterings.

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!

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!

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!

Literatur
2.
Zurück zum Zitat Aszalós, L., Mihálydeák, T.: Rough clustering generated by correlation clustering. Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, pp. 315–324. Springer, Berlin (2013). doi:10.1109/TKDE.2007.1061 CrossRef Aszalós, L., Mihálydeák, T.: Rough clustering generated by correlation clustering. Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, pp. 315–324. Springer, Berlin (2013). doi:10.​1109/​TKDE.​2007.​1061 CrossRef
3.
Zurück zum Zitat Aszalós, L., Mihálydeák, T.: Rough classification based on correlation clustering. Rough Sets and Knowledge Technology, pp. 399–410. Springer, Berlin (2014). doi:10.1007/978-3-319-11740-9_37 Aszalós, L., Mihálydeák, T.: Rough classification based on correlation clustering. Rough Sets and Knowledge Technology, pp. 399–410. Springer, Berlin (2014). doi:10.​1007/​978-3-319-11740-9_​37
4.
Zurück zum Zitat Aszalós, L., Mihálydeák, T.: Correlation clustering by contraction. In: Ganzha, M., Maciaszek, L.A., Paprzycki, M. (eds.) Federated Conference on Computer Science and Information Systems, FedCSIS 2015, Lódz, Poland, 13–16 September 2015, pp. 425–434. IEEE (2015). doi:10.15439/2015F137 Aszalós, L., Mihálydeák, T.: Correlation clustering by contraction. In: Ganzha, M., Maciaszek, L.A., Paprzycki, M. (eds.) Federated Conference on Computer Science and Information Systems, FedCSIS 2015, Lódz, Poland, 13–16 September 2015, pp. 425–434. IEEE (2015). doi:10.​15439/​2015F137
5.
Zurück zum Zitat Aszalós, L., Mihálydeák, T.: Rough classification in incomplete databases by correlation clustering. In: Alonso, J.M., Bustince, H., Reformat, M. (eds.) Conference of the International Fuzzy Systems Association and the European Society for Fuzzy Logic and Technology (IFSA-EUSFLAT-15), Gijón, Spain, 30 June 2015. Atlantis Press (2015) Aszalós, L., Mihálydeák, T.: Rough classification in incomplete databases by correlation clustering. In: Alonso, J.M., Bustince, H., Reformat, M. (eds.) Conference of the International Fuzzy Systems Association and the European Society for Fuzzy Logic and Technology (IFSA-EUSFLAT-15), Gijón, Spain, 30 June 2015. Atlantis Press (2015)
6.
Zurück zum Zitat Aszalós, L., Kormos, J., Nagy, D.: Conjectures on phase transition at correlation clustering of random graphs. Ann. Univ. Sci. Bp. Sect. Comput. 42, 37–54 (2014)MathSciNetMATH Aszalós, L., Kormos, J., Nagy, D.: Conjectures on phase transition at correlation clustering of random graphs. Ann. Univ. Sci. Bp. Sect. Comput. 42, 37–54 (2014)MathSciNetMATH
8.
9.
Zurück zum Zitat Chen, Z., Yang, S., Li, L., Xie, Z.: A clustering approximation mechanism based on data spatial correlation in wireless sensor networks. Wireless Telecommunications Symposium (WTS), pp. 1–7. IEEE (2010). doi:10.1109/WTS.2010.5479626 Chen, Z., Yang, S., Li, L., Xie, Z.: A clustering approximation mechanism based on data spatial correlation in wireless sensor networks. Wireless Telecommunications Symposium (WTS), pp. 1–7. IEEE (2010). doi:10.​1109/​WTS.​2010.​5479626
10.
Zurück zum Zitat Dorigo, M., Gambardella, L.M.: Ant colonies for the travelling salesman problem. BioSystems 43(2), 73–81 (1997)CrossRef Dorigo, M., Gambardella, L.M.: Ant colonies for the travelling salesman problem. BioSystems 43(2), 73–81 (1997)CrossRef
11.
Zurück zum Zitat DuBois, T., Golbeck, J., Kleint, J., Srinivasan, A.: Improving recommendation accuracy by clustering social networks with trust. Recomm. Syst. Soc. Web 532, 1–8 (2009). doi:10.1145/2661829.2662085 DuBois, T., Golbeck, J., Kleint, J., Srinivasan, A.: Improving recommendation accuracy by clustering social networks with trust. Recomm. Syst. Soc. Web 532, 1–8 (2009). doi:10.​1145/​2661829.​2662085
12.
Zurück zum Zitat Geem, Z.W.: Optimal cost design of water distribution networks using harmony search. Eng. Optim. 38(03), 259–277 (2006)CrossRef Geem, Z.W.: Optimal cost design of water distribution networks using harmony search. Eng. Optim. 38(03), 259–277 (2006)CrossRef
13.
Zurück zum Zitat Kim, S., Nowozin, S., Kohli, P., Yoo, C.D.: Higher-order correlation clustering for image segmentation. In: Advances in Neural Information Processing Systems, pp. 1530–1538 (2011) Kim, S., Nowozin, S., Kohli, P., Yoo, C.D.: Higher-order correlation clustering for image segmentation. In: Advances in Neural Information Processing Systems, pp. 1530–1538 (2011)
15.
Zurück zum Zitat 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) 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)
16.
Zurück zum Zitat Yang, B., Cheung, W.K., Liu, J.: Community mining from signed social networks. IEEE Trans. Knowl. Data Eng. 19(10), 1333–1348 (2007)CrossRef Yang, B., Cheung, W.K., Liu, J.: Community mining from signed social networks. IEEE Trans. Knowl. Data Eng. 19(10), 1333–1348 (2007)CrossRef
Metadaten
Titel
Correlation Clustering by Contraction, a More Effective Method
verfasst von
László Aszalós
Tamás Mihálydeák
Copyright-Jahr
2016
DOI
https://doi.org/10.1007/978-3-319-40132-4_6