A partition-based approach towards constructing Galois (concept) lattices

Valtchev, Petko; Missaoui, Rokia et Lebrun, Pierre (2002). « A partition-based approach towards constructing Galois (concept) lattices ». Discrete Mathematics, 256(3), pp. 801-829.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (453kB)

Résumé

Galois lattices and formal concept analysis of binary relations have proved useful in the resolution of many problems of theoretical or practical interest. Recent studies of practical applications in data mining and software engineering have put the emphasis on the need for both efficient and flexible algorithms to construct the lattice. Our paper presents a novel approach for lattice construction based on the apposition of binary relation fragments. We extend the existing theory to a complete characterization of the global Galois (concept) lattice as a substructure of the direct product of the lattices related to fragments. The structural properties underlie a procedure for extracting the global lattice from the direct product, which is the basis for a full-scale lattice construction algorithm implementing a divide-and-conquer strategy. The paper provides a complexity analysis of the algorithm together with some results about its practical performance and describes a class of binary relations for which the algorithm outperforms the most efficient lattice-constructing methods.

Type:	Article de revue scientifique
Mots-clés ou Sujets:	Galois lattice; Formal concept analysis; Lattice-constructing algorithms; Data fragments; Context apposition; Lattice products
Unité d'appartenance:	Faculté des sciences > Département d'informatique
Déposé par:	Petko Valtchev
Date de dépôt:	27 avr. 2016 13:37
Dernière modification:	19 mai 2016 18:12
Adresse URL :	http://archipel.uqam.ca/id/eprint/8331

Modifier les métadonnées (propriétaire du document)

Statistiques