FORMAL CONCEPT ANALYSIS


A formal context is a triple (G,M,I) consisting of a set of formal objects G, a set of formal attributes M, and a binary relation I inclus G x M (expressing for each object which attributes it has) (Wille R., 1982, 1997a, 1997a, 2001 and Ganter B., Wille R., (1997, 1999).). Generally, the relation is an equivalence, but it may also be a similarity (see Slowinski and Vanderpooten 2000).

A formal concept of (G,M,I) is a pair (A,B) of sets satisfying :
       A inclus G, B inclus M, A'= B, A = B'
where A' et B' are the operators :
       A' := {m inclus M | (g,m) inclus I for all g inclus A} (A' is the set of attributes which are possessed by all the objects of A)
       B' := {g inclus G | (g,m) inclus I for all m inclus B}  (B' is the set of objects which possess all the attributes of B)
The set A is called the extent of the formal concept (A, B), and the set B is called its intent.

Concepts are ordered by:
       (A1,B1) LE (A2,B2) :   implique A1 inclus A2   ( implique B2 inclus B1 )
The set B (G,M,I) of all concepts of (G,M,I) with this order is a complete lattice, called the concept lattice of (G,M,I).

NB: Multi-valued-contexts must be transformed into one-valued contexts by using nominal scaling or plain scaling (each value of a multi-valued attribute becomes nominally a one-valued attribute).

     FCA example

List of available software: click here

Concept Approximation by a similarity index (see Saquer and Deogun)

A method giving the formal concept which is the closest approximation to a set of objects A, a set of attributes B or a pair {A,B} is implemented in Semana. It is based on a similarity index proposed by Saquer and Deogun.
Another method based on Rough Set Theory has been proposed by the same authors (see RST).

Alpha Galois Lattices
(see Pernelle et al.)
A method to reduce the size of the lattice when the number of nodes is very large. The method is based on a preliminary partition of the full BD in "types" (basic concepts)

Association Rules
A list of the Association Rules (A => B) (cf. Agrawal and Srikant 1994) may be obtained with their support up to a given threshold.
A is a set of attributes called premise, B is a set of attributes called conclusion. Example:
      {D,F} => {H}    (12/12)     100
means that, when an object has features D and F, it has also feature H in 100% of the 12 occurrences in the formal context. Such a rule, observed without exception within the formal context, is called Duquenne-Guigues implication.

References

AGRAWAL R., R. SRIKANT (1994). Fast algorithms for mining association rules. Proc. 20th VLDB Conference, Santiago, Chile.
AGRAWAL R., R. SRIKANT (1995).Mining generalized association rules. Proc. 21th VLDB Conference, Zurich, Swizerland.
GANTER B., WILLE R. (1997). Applied Lattice Theory: Formal Concept Analysis. In General Lattice Theory, G. Grätzer editor, Birkhäuser
GANTER B., WILLE R. (1999). Formal concept analysis: Mathematical foundations, Springer: Berlin, 1999.
PERNELLE N., M.-C.ROUSSET , H. SOLDANO H., V. VENTOS (2002). ZOOM: a nested Galois lattices-based system for conceptual clustering. J. of Experimental and Theoretical Artificial Intelligence, 1 (14), 157-187.
PERNELLE N., V. VENTOS, H. SOLDANO (2003). ZooM: Alpha Galois lattices for conceptual clustering MASPEGHI 2003, 2nd International Workshop on MAnaging SPEcialization/ Generalization HIerarchies, Montréal, Québec, Canada.
PREDIGER S. (1997). Symbolic objects in Formal Concept Analysis. In Proceedings of the second International Symposium on Knowledge, Retrieval, Use and Storage for efficiency. Vancouver (G. Mineau, A. Fall eds.)
PREDIGER S. (1997). Logical scaling in Formal Concept Analysis. In Conceptual structures: fulfilling Peirce's dream (D. Lukose et al. eds.) Proceedings of the 5th Internat. Conf. on conceptual structures (ICCS'97). Lecture notes in Artificial Intelligence n°1257, Springer-Verlag: Berlin, p. 332-341.
PREDIGER S., WILLE R. (1999). The lattice of concept graphs of a relationally scaled context. Cyre (eds.): Conceptual Structures: Standards and Practices.
PRISS U. (2004). Linguistic Applications of Formal Concept Analysis. in Proceedings of the First International Conference on Formal Concept Analysis (ICFCA 2003)
SAQUER J., J. S. DEOGUN (1999). Formal Rough Concept Analysis, Proc. of 7th International Workshop, RSFDGrC'99, Yamaguchi, New Directions in Rough Sets, Data Mining, and Granular-soft Computing, Lecture Notes in Computer Science. Ed. Zhong, N., Skowron, A., and Ohsuga, S. Springer-Verlag, 1999.
SAQUER J., J. S. DEOGUN (2000), Concept approximations for formal concept analysis, The 8th International Conference on Conceptual Structures (ICCS'2000) (Darmstadt, Germany), vol. II Working with Conceptual Structures.
SAQUER J., J. S. DEOGUN (2001). Concept Approximations Based on Rough Sets and Similarity Measures.International Journal of Applied Mathematics and Computer Science
SLOWINSKI R., D. VANDERPOOTEN (2000). A generalized definition of Rough Approximations. IEEE Transactions on knowledge and data engineering, 12, n°2, p. 331-336.
WILLE, R. (1982) "Restructuring lattice theory: an approach based on hierarchies of concepts". In Rival, I., editor, Ordered sets, volume 83 of NATO Advanced Studies Institute, Reidel, Dordrecht, pages 445–470.Wille, R. (1982). Restructuring lattice theory: an Approach based on Hierarchies of Concepts. In I. Rival (Ed.), Ordered sets. Reidel, Dordrecht-Boston, 445-470.
WILLE R. (1992). "Concept Lattices and Conceptual Knowledge Systems". Computers & Mathematics with Applications, 23, 493-515.
WILLE R. (1997a). Introduction to Formal Concept Analysis. In G. Negrini (Ed.), Modelli e modellizzazione. Models and modelling. Consiglio Nazionale delle Ricerche, Instituto di Studi sulli Ricerca e Documentazione Scientifica, Roma, 39-51.
WILLE R. (1997b). Conceptual graphs and Formal Concept Analysis. in D.Lukose, H. Delugach, M. Keeler, L. Searle, & J. F. Sowa (Eds.), Conceptual Structures: Fulfilling Peirce’s Dream. Proc. ICCS’97. LNAI 1257. Berlin:Springer, 290-303.
WILLE R. (2001). Why Can Concept Lattices Support Knowledge Discovery in Databases? ICCS'01 International Workshop on Concept Lattices-based KDD, 7-20.
WOLFF K. E. (1993). A first course in Formal Concept Analysis. How to understand line diagrams. Advances in Statistical Software, 4, 429-438.


Apache/1.3.29 Server at celta.paris-sorbonne.fr Port 80