Lattice Algorithms | References | Links
 
Formal Concept Analysis  

Formal Concept Analysis is a theory of data analysis, it's also called concept lattice. It was introduced by Rudolf Wille in 1982. Its theoretical foundation rest on the mathematical lattice theory.

Concept lattice studies how objects can be hierarchically grouped together according to their common attributes. One set of objects possesses some attributes, we can classify objects and attributes (i.e. generate concepts) according to the relation between objects set and attribute set. Furthermore we can add knowledge rules in concept lattice. This method is proved to be efficiently used for association rules, classification and clustering. Many other works can be found in Web mining for semantic Web, email, information retrieval and Web log etc. Concept lattice is a natural framework for data mining, its many characteristics are very suitable for data mining. Concept lattice has successfully been applied to many fields, such as medicine and psychology, musicology, linguistic databases, library and information science, software re-engineering, civil engineering, ecology, and others. A strong feature of Formal Concept Analysis is its capability of producing graphical visualizations of the inherent structures among data.

 
 
Lattice Algorithms  

Several algorithms were proposed to generate concepts or concept lattices on a data, for example: algorithms of

  • Chein(1969)
  • Norris(1978)
  • Ganter(1984)
  • Bordat(1986)
  • Zabezhailo et al.(1987)
  • Kuznetsov(1993)
  • Dowling(1993)
  • Godin et al.(1995)
  • Carpineto and Romano(1996)
  • Lindig(1999)
  • Nourine(1999) etc.
 
   
References  
[1] G Birkhoff: Lattice Theory. 3rd edition, American Mathematical Society, Providence, RI 1967.
[2] Wille, R.: Restructuring Lattice Theory. In Rival, I., ed.: Symposium on Ordered Sets, University of Calgary, Boston (1982) 445-470
[3] Ganter, B., Wille, R.: Formal Concept Analysis. Mathematical Foundations. Springer (1999).
[4] Chein, M.: Algorithme de recherche des sous-matrice premières d'une matrice. Bulletin Math. de la Soc. Sci. de la R.S. de Roumanie 61 (1969) Tome 13.
[5] Norris, E.: An algorithm for computing the maximal rectangles in a binary relation. Revue Roumaine Math. Pures et Appl. XXIII (1978) 243-250
[6] Ganter, B.: Two basic algorithms in concept analysis. Technical Report 831, Technische Hochschule, Darmstadt, Germany (1984) preprint.
[7] Bordat, J.: Calcul pratique du treillis de galois d'une correspondance. Mathématiques, Informatiques et Sciences Humaines 24 (1986) 31-47
[8] Godin, R., Mineau, G., Missaoui, R., Mili, H.: Méthodes de classification conceptuelle basées sur les treillis de Galois et applications. Revue d'intelligence articielle 9 (1995) 105-137
[9] B. Ganter, K. Rindfrey, and M. Skorsky. Software for formal concept analysis. In Classification as a tool of research, Elsevier Science, 1986.
[10] C. Carpineto and G. Romano. Information retrieval through hybrid navigation of lattice representations. International Journal of Human-Computer Studies 45, pp 553-578. 1996.
[11] Nourine, L., Raynaud, O.: A fast algorithm for building lattices. Information Processing Letters 71 (1999) 199-204
[12] R. Godin and R. Missaoui. An Incremental Concept Formation Approach for Learning from Databases. Theoretical Computer Science, Special Issue on Formal Methods in Databases and Software Engineering, 133, 387-419. 1994.
[13] DG. Kourie, GD. Oosthuizen. Lattices in machine learning: complexity issues. Acta Informatica 35, 269-292. 1998.
[14] GD. Oosthuizen. Lattice-based Knowledge Discovery. In Proceedings of AAAI-91 Knowledge Discovery in Databases Workshop, Anaheim pp221-235, 1991.
[15] E. Mephu Nguifo, M. Liquiere, and V. Duquenne. Journal of Experimental and Theoretical Artificial Intelligence (JE-TAI) Special Issue on Concept Lattice-based theory, methods and tools for Knowledge Discovery in Databases. Taylor and Francis, 2002.
[16] Kuznetsov, S., Obiedkov, S.: Comparing performance of algorithms for generating concept lattices. JETAI Special Issue on Concept Lattice for KDD 14 (2002) 189-216
 
   
Links  
 
   
 

Copyright © 2003 Huaiguo Fu