Minimal generators, an affordable approach by means of massive computation
Pages 1350 - 1367
Abstract
Closed sets and minimal generators are fundamental elements to build a complete knowledge representation in formal concept analysis. The enumeration of all the closed sets and their minimal generators from a set of rules or implications constitutes a complex problem, drawing an exponential cost. Even for small datasets, such representation can demand an exhaustive management of the information stored as attribute implications. In this work, we tackle this problem by merging two strategies. On the one hand, we design a pruning, strongly based on logic properties, to drastically reduce the search space of the method. On the other hand, we consider a parallelization of the problem leading to a massive computation by means of a map-reduce like paradigm. In this study we have characterized the type of search space reductions suitable for parallelization. Also, we have analyzed different situations to provide an orientation of the resources (number of cores) needed for both the parallel architecture and the size of the problem in the splitting stage to take advantage in the map stage.
References
[1]
Armstrong WW (1974) Dependency structures of data base relationships. In: IFIP Congress, pp 580---583
[2]
Benito-Picazo F, Cordero P, Enciso M, Mora A (2017) Reducing the search space by closure and simplification paradigms. J Supercomput 73(1):75---87
[3]
Buchi JR, Siefkes D (1990) Finite automata, their algebras and grammars. Springer, New York Inc, Secaucus
[4]
Codd EF (1970) A relational model of data for large shared data banks. Commun ACM 13(6):377---387
[5]
Cohen E, Datar M, Fujiwara S, Gionis A, Indyk P, Motwani R, Ullman JD, Yang C (2001) Finding interesting associations without support pruning. IEEE Trans Knowl Data Eng 13(1):64---78
[6]
Cordero P, Enciso M, Mora A, Ojeda-Aciego M (2012) Computing minimal generators from implications: a logic-guided approach. In Szathmary L, Priss U (eds) Proceedings of the Ninth International Conference on Concept Lattices and Their Applications, Fuengirola (Málaga), Spain, October 11---14, 2012, volume 972 of CEUR Workshop Proceedings, pp 187---198. CEUR-WS.org
[7]
Cordero P, Mora A, Enciso M, de Guzmán IP (2002) SLFD logic: elimination of data redundancy in knowledge representation. Lect Notes Comput Sci 2527:141---150
[8]
de Moraes NRM, Dias SM, Freitas HC, Zárate LE (2016) Parallelization of the next closure algorithm for generating the minimum set of implication rules. Artif Intell Res 5(2):40---54
[9]
Doignon J, Falmagne J (1998) Knowledge spaces. Springer, Berlin
[10]
Dong GZ, Jiang CY, Pei J, Li JY, Wong L (2005) Mining succinct systems of minimal generators of formal concepts. Proc Database Syst Adv Appl 3453:175---187
[11]
Ganter B, Wille R (1999) Formal concept analysis: mathematical foundations. Springer, Berlin
[12]
Guigues JL, Duquenne V (1986) Famille minimale d'implications informatives résultant d'un tableau de données binaires. Math Sci Hum 24(95):5---18
[13]
Harper FM, Konstan JA (2015) The movielens datasets: history and context. ACM Trans Interact Intell Syst 5(4):19:1---19:19
[14]
Hu X, Wei X, Wang D, Li P (2007) A parallel algorithm to construct concept lattice. In Lei J (ed) Proceedings of the Fourth International Conference on Fuzzy Systems and Knowledge Discovery, FSKD 2007, 24---27 August 2007, Haikou, Hainan, China, vol 2, pp 119---123. IEEE Computer Society
[15]
Kuznetsov SO, Obiedkov SA (2002) Comparing performance of algorithms for generating concept lattices. J Exp Theor Artif Intell 14(2---3):189---216
[16]
Maier D (1983) The theory of relational databases. Computer Science Press, Rockville
[17]
Missaoui R, Nourine L, Renaud Y (2010) An inference system for exhaustive generation of mixed and purely negative implications from purely positive ones. In: CEUR Workshop Proceedings, vol 672, pp 271---282
[18]
Missaoui R, Nourine L, Renaud Y (2012) Computing implications with negation from a formal context. Fundam Inf 115(4):357---375
[19]
Mora A, Enciso M, Cordero P, Fortes I (2012) Closure via functional dependence simplification. Int J Comput Math 89(4):510---526
[20]
Nishio N, Mutoh A, Inuzuka N (2012) On computing minimal generators in multi-relational data mining with respect to 0-subsumption. In: CEUR Workshop Proceedings, vol 975, pp 50---55
[21]
Poelmans J, Ignatov DI, Kuznetsov SO, Dedene G (2013) Formal concept analysis in knowledge processing: a survey on applications. Expert Syst Appl 40(16):6538---6560
[22]
Qu K, Zhai Y, Liang J, Chen M (2007) Study of decision implications based on formal concept analysis. Int J Gen Syst 36(2):147---156
[23]
Rodríguez-Lorenzo E, Cordero P, Enciso M, Mora Á (2017) Canonical dichotomous direct bases. Inf Sci 376:39---53
Index Terms
- Minimal generators, an affordable approach by means of massive computation
Index terms have been assigned to the content through auto-classification.
Recommendations
Mining succinct systems of minimal generators of formal concepts
DASFAA'05: Proceedings of the 10th international conference on Database Systems for Advanced ApplicationsFormal concept analysis has become an active field of study for data analysis and knowledge discovery. A formal concept C is determined by its extent (the set of objects that fall under C) and its intent (the set of properties or attributes covered by C)...
Mining disjunctive minimal generators with TitanicOR
Disjunctive minimal generators were proposed by Zhao, Zaki, and Ramakrishnan (2006). They defined disjunctive closed itemsets and disjunctive minimal generators through the disjunctive support function. We prove that the disjunctive support function is ...
Computation of minimal generators of ideals of fat points
ISSAC '01: Proceedings of the 2001 international symposium on Symbolic and algebraic computationWe present an implementation of an algorithm for computing minimal homogeneous generators and Hilbert functions of ideals of fat points. First we construct a set of generators by an interpolating method which is based on the Hermite interpolation and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Copyright © 2019 Springer Science+Business Media, LLC, part of Springer Nature.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 01 March 2019
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Jan 2025