Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
International Journal of Machine Learning and Cybernetics
Published in: International Journal of Machine Learning and Cybernetics 9/2022

04-04-2022 | Original Article

Computing formal concepts in parallel via a workload rebalance approach

Authors: Ligeng Zou, Xiaozhi Chen, Tingting He, Jianhua Dai

Published in: International Journal of Machine Learning and Cybernetics | Issue 9/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The scalability issue has always been a bottleneck for formal concept analysis (FCA) since the number of formal concepts is possibly exponential in the formal context. Motivated by the need to handle large formal contexts efficiently, we propose a parallel algorithm for computing formal concepts, the aim of which is to make Close-by-One (CbO) and its variants highly parallelized and easy to apply. Current approaches to parallelization of CbO-type algorithms such as PCbO (Parallel CbO) compute concepts in the top L recursion levels in serial and then turn to parallel computation after that. To avoid massive serial computations and the hassle of choosing the hyperparameter L in real applications, our proposed algorithm enters parallelization at once after the computation of the top concept and its direct successors, and then uses a parallel reshuffle approach to rebalance the workload distribution among worker threads without communication with the main thread. We describe the algorithm and present an experimental evaluation of its performance and comparison with PCbO on various datasets. Empirical analyses demonstrate that our algorithm is superior when applied to various types of formal contexts.
previous article A review on machine learning techniques for the assessment of image grading in breast mammogram
next article CIRAN: extracting crowd interaction with residual attention network for pedestrian trajectory prediction

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
Show more products
Literature
1.
Andrews S (2011) In-close2, a high performance formal concept miner. In: Andrews S, Polovina S, Hill R, Akhgar B (eds) Conceptual structures for discovering knowledge. Springer, pp 50–62CrossRef
2.
Andrews S (2015) A ‘Best-of-Breed’ approach for designing a fast algorithm for computing fixpoints of Galois Connections. Inf Sci 295:633–649MathSciNetCrossRef
3.
Andrews S (2017) Making Use of Empty Intersections to Improve the Performance of CbO-Type Algorithms. In: Proceedings of the 14th international conference on formal concept analysis. Springer, pp 56–71
4.
Andrews S (2018) A new method for inheriting canonicity test failures in Close-by-One type algorithms. In: Proceedings of the 14th international conference on concept lattices and their applications. Springer, pp 255–266
5.
Andrews S, Orphanides C (2010) FcaBedrock, a Formal Context Creator. In: Croitoru M, Ferré S, Lukose D (eds) Conceptual structures: from information to intelligence. Springer, New York, pp 181–184CrossRef
6.
Belohlavek R, Outrata J, Trnecka M (2019) Factorizing Boolean matrices using formal concepts and iterative usage of essential entries. Inf Sci 489:37–49MathSciNetCrossRef
7.
Dong H, Ma Y, Gong X (2008) A new parallel algorithm for construction of concept lattice. J Front Comput Sci Technol 2(6):651–657
8.
9.
Ganter B (2010) Two basic algorithms in concept analysis. In: Kwuida L, Sertkaya B (eds) Formal concept analysis. Springer, New York, pp 312–340CrossRef
10.
Ganter B, Wille R (1999) Formal concept analysis: mathematical foundations. Springer, New YorkCrossRef
11.
Godin R, Missaoui R, Alaoui H (1995) Incremental concept formation algorithms based on Galois lattices. Comput Intell 11:246–267CrossRef
12.
13.
Janostik R, Konecny J, Krajca P (2020) Interface between logical analysis of data and formal concept analysis. Eur J Oper Res 284:792–800MathSciNetCrossRef
14.
Li J, Mei C, Xu W, Qian Y (2015) Concept learning via granular computing: a cognitive viewpoint. Inf Sci 298:447–467MathSciNetCrossRef
15.
Kengue JFD, Valtchev P, Djamegni CT (2005) A parallel algorithm for lattice construction. In: Proceedings of the International conference on formal concept analysis. Springer, pp 249–264
16.
Kodagoda N, Andrews S, Pulasinghe K (2017) A parallel version of the in-close algorithm. In: Proceedings of 6th national conference on technology and management, vol 7872818, pp 1–5
17.
Kodagoda N, Pulasinghe K (2016) Comparision between features of CbO based algorithms for generating formal concepts. Int J Concept Struct Smart Appl 4:1–34
18.
Konecny J, Krajca P (2021) Systematic categorization and evaluation of CbO-based algorithms in FCA. Inf Sci 575:265–288MathSciNetCrossRef
19.
Krajca P, Outrata J, Vychodil V (2010) Parallel algorithm for computing fixpoints of Galois connections. Ann Math Artif Intell 59:257–272MathSciNetCrossRef
20.
Krajca P, Outrata J, Vychodil V (2010) Advances in algorithms based on CbO. In: Proceedings of the 7th international conference on concept lattices and their applications, pp 325–337
21.
Krajca P, Vychodil V (2009) Distributed algorithm for computing formal concepts using map-reduce framework. In: Adams NM, Robardet C, Siebes A, Boulicaut J-F (eds) Advances in intelligent data analysis VIII. Springer, New York, pp 333–344CrossRef
22.
Kuznetsov SO (1989) Interpretation on graphs and complexity characteristics of a search for specific patterns. Nauchno-Tekhnicheskaya Informatsiya, seriya 2 Informatsionnye protsessy i sistemy 23(1):23–27
23.
Kuznetsov SO (1993) A fast algorithm for computing all intersections of objects in a finite semi-lattice. Nauchno-Tekhnicheskaya Informatsiya, seriya 2 Informatsionnye protsessy i sistemy 27(1):17–20
24.
25.
Kuznetsov SO (1999) Learning of simple conceptual graphs from positive and negative examples. In: Żytkow JM, Rauch J (eds) Principles of data mining and knowledge discovery. Springer, Berlin, pp 384–391CrossRef
26.
27.
Kuznetsov SO, Obiedkov SA (2002) Comparing performance of algorithms for generating concept lattices. J Exp Theor Artif Intell 14:189–216CrossRef
28.
Kwon SE, Kim YT, Suh H, Lee H (2021) Identifying the mobile application repertoire based on weighted formal concept analysis. Expert Syst Appl 173:114678CrossRef
29.
Li J, Aswani Kumar C, Mei C, Wang X (2017) Comparison of reduction in formal decision contexts. Int J Approx Reason 80:100–122MathSciNetCrossRef
30.
Li X, Shao M-W, Zhao X-M (2017) Constructing lattice based on irreducible concepts. Int J Mach Learn Cyber 8:109–122CrossRef
31.
Ma J-M, Cai M-J, Zou C-J (2017) Concept acquisition approach of object-oriented concept lattices. Int J Mach Learn Cyber 8:123–134CrossRef
32.
33.
34.
Outrata J, Vychodil V (2012) Fast algorithm for computing fixpoints of Galois connections induced by object-attribute relational data. Inf Sci 185:114–127MathSciNetCrossRef
35.
Poelmans J, Kuznetsov SO, Ignatov DI, Dedene G (2013) Formal concept analysis in knowledge processing: a survey on models and techniques. Expert Syst Appl 40:6601–6623CrossRef
36.
Qian T, Wei L, Qi J (2017) Decomposition methods of formal contexts to construct concept lattices. Int J Mach Learn Cyber 8:95–108CrossRef
37.
Qin K, Lin H, Jiang Y (2020) Local attribute reductions of formal contexts. Int J Mach Learn Cyber 11:81–93CrossRef
38.
Shi Y, Mi Y, Li J, Liu W (2019) Concurrent concept-cognitive learning model for classification. Inf Sci 496:65–81CrossRef
39.
Strok F, Neznanov A (2010) Comparing and analyzing the computational complexity of FCA algorithms. In: Proceedings of the 2010 annual research conference of the South African institute of computer scientists and information technologists on. ACM Press, pp 417–420
40.
Van der Merwe D, Obiedkov S, Kourie D (2004) AddIntent: a new incremental algorithm for constructing concept lattices. In: Lecture notes in artificial intelligence, pp 205–206
41.
Wille R (1982) Restructuring lattice theory: an approach based on hierarchies of concepts. In: Rival I (ed) Ordered sets. Springer, New York, pp 445–470CrossRef
42.
Xu B, de Fréin R, Robson E, Foghlú Ó (2012) Distributed formal concept analysis algorithms based on an iterative MapReduce framework. In: Domenach F, Ignatov DI, Poelmans J (eds) Formal concept analysis. Springer, New York, pp 292–308CrossRef
43.
Zhang T, Bai D, Li H (2017) Parallel concept computing based on bottom-up decomposition of attribute topology. J Softw 28:3129–3145MathSciNetMATH
44.
45.
46.
Zou L, Zhang Z, Long J (2015) A fast incremental algorithm for constructing concept lattices. Expert Syst Appl 42:4474–4481CrossRef
Metadata
Title
Computing formal concepts in parallel via a workload rebalance approach
Authors
Ligeng Zou
Xiaozhi Chen
Tingting He
Jianhua Dai
Publication date
04-04-2022
Publisher
Springer Berlin Heidelberg
Published in
International Journal of Machine Learning and Cybernetics / Issue 9/2022
Print ISSN: 1868-8071
Electronic ISSN: 1868-808X
DOI
https://doi.org/10.1007/s13042-022-01547-1

Other articles of this Issue 9/2022

International Journal of Machine Learning and Cybernetics 9/2022 Go to the issue

Original Article

Exploring correlation of relationship reasoning for scene graph generation

Original Article

A heuristically self-organised Linguistic Attribute Deep Learning for edge intelligence

Original Article

A shadowed set-based three-way clustering ensemble approach

Original Article

Video person re-identification using key frame screening with index and feature reorganization based on inter-frame relation

Original Article

Clustering mixed type data: a space structure-based approach

Original Article

A review on machine learning techniques for the assessment of image grading in breast mammogram