Computing iceberg concept lattices with Titanic

Gerd Stumme; Rafik Taouil; Yves Bastide; Nicolas Pasquier; Lotfi Lakhal

hal-00578830, version 1

Computing iceberg concept lattices with Titanic

Gerd Stumme ^1, 2, Rafik Taouil ³, Yves Bastide ⁴, Nicolas Pasquier () ⁵, Lotfi Lakhal ⁶

Data and Knowledge Engineering 42, 2 (2002) 189-222

Résumé : We introduce the notion of iceberg concept lattices and show their use in knowledge discovery in databases. Iceberg lattices are a conceptual clustering method, which is well suited for analyzing very large databases. They also serve as a condensed representation of frequent itemsets, as starting point for computing bases of association rules, and as a visualization method for association rules. Iceberg concept lattices are based on the theory of Formal Concept Analysis, a mathematical theory with applications in data analysis, information retrieval, and knowledge discovery. We present a new algorithm called TITANIC for computing (iceberg) concept lattices. It is based on data mining techniques with a level-wise approach. In fact, TITANIC can be used for a more general problem: Computing arbitrary closure systems when the closure operator comes along with a so-called weight function. The use of weight functions for computing closure systems has not been discussed in the literature up to now. Applications providing such a weight function include association rule mining, functional dependencies in databases, conceptual clustering, and ontology engineering. The algorithm is experimentally evaluated and compared with Ganter's Next-Closure algorithm. The evaluation shows an important gain in eﬃciency, especially for weakly correlated data.

1 : Institute AIFB, Universität Karlsruhe
AIFB, Universit¨at Karlsruhe
2 : University of Karlsruhe (TH)
University of Karlsruhe – Universität of Karlsruhe
3 : ORPAILLEUR (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
4 : Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS)
CNRS : UMR6158 – Université d'Auvergne - Clermont-Ferrand I – Université Blaise Pascal - Clermont-Ferrand II – Institut Français de Mécanique Avancée
5 : Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S)
Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
6 : Laboratoire d'Informatique de Marseille (LIM)
CNRS : FR2246 – Université de la Méditerranée - Aix-Marseille II

hal-00578830, version 1
http://hal.archives-ouvertes.fr/hal-00578830
oai:hal.archives-ouvertes.fr:hal-00578830
Contributeur : Nicolas Pasquier <>
Soumis le : Mardi 22 Mars 2011, 14:15:37
Dernière modification le : Vendredi 14 Septembre 2012, 10:41:59

Voir la fiche détaillée

Documents associés

PDF :

DOI : 10.1016/S0169-023X(02)00057-5

Exporter

Bibtex EndNote TEI RefWorks

%% hal-00578830, version 1
%% http://hal.archives-ouvertes.fr/hal-00578830
@article{stumme:hal-00578830,
    hal_id = {hal-00578830},
    url = {http://hal.archives-ouvertes.fr/hal-00578830},
    title = {{Computing iceberg concept lattices with Titanic}},
    author = {Stumme, Gerd and Taouil, Rafik and Bastide, Yves and Pasquier, Nicolas and Lakhal, Lotfi},
    abstract = {{We introduce the notion of iceberg concept lattices and show their use in knowledge discovery in databases. Iceberg lattices are a conceptual clustering method, which is well suited for analyzing very large databases. They also serve as a condensed representation of frequent itemsets, as starting point for computing bases of association rules, and as a visualization method for association rules. Iceberg concept lattices are based on the theory of Formal Concept Analysis, a mathematical theory with applications in data analysis, information retrieval, and knowledge discovery. We present a new algorithm called TITANIC for computing (iceberg) concept lattices. It is based on data mining techniques with a level-wise approach. In fact, TITANIC can be used for a more general problem: Computing arbitrary closure systems when the closure operator comes along with a so-called weight function. The use of weight functions for computing closure systems has not been discussed in the literature up to now. Applications providing such a weight function include association rule mining, functional dependencies in databases, conceptual clustering, and ontology engineering. The algorithm is experimentally evaluated and compared with Ganter's Next-Closure algorithm. The evaluation shows an important gain in efficiency, especially for weakly correlated data.}},
    keywords = {Data mining ; Galois closure ; Concept lattice ; Association rules ; Algorithms},
    language = {Anglais},
    affiliation = {Institute AIFB, Universit{\"a}t Karlsruhe , University of Karlsruhe - TH , ORPAILLEUR - INRIA Lorraine - LORIA , Laboratoire d'Informatique, de Mod{\'e}lisation et d'optimisation des Syst{\`e}mes - LIMOS , Laboratoire d'Informatique, Signaux, et Syst{\`e}mes de Sophia-Antipolis - I3S , Laboratoire d'Informatique de Marseille - LIM},
    pages = {189-222},
    journal = {Data and Knowledge Engineering},
    volume = {42},
    number = {2 },
    audience = {internationale },
    doi = {10.1016/S0169-023X(02)00057-5 },
    year = {2002},
    month = Aug,
    pdf = {http://hal.archives-ouvertes.fr/hal-00578830/PDF/Stumme\_et\_al.\_-\_2002.pdf},
}

%F hal-00578830, version 1
%0 Journal Article
%U http://hal.archives-ouvertes.fr/hal-00578830
%2 INFO:INFO_DS
%T Computing iceberg concept lattices with Titanic
%A Stumme, Gerd
%A Taouil, Rafik
%A Bastide, Yves
%A Pasquier, Nicolas
%A Lakhal, Lotfi
%+ Institute AIFB, Universität Karlsruhe , University of Karlsruhe - TH , ORPAILLEUR - INRIA Lorraine - LORIA , Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes - LIMOS , Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis - I3S , Laboratoire d'Informatique de Marseille - LIM
%X We introduce the notion of iceberg concept lattices and show their use in knowledge discovery in databases. Iceberg lattices are a conceptual clustering method, which is well suited for analyzing very large databases. They also serve as a condensed representation of frequent itemsets, as starting point for computing bases of association rules, and as a visualization method for association rules. Iceberg concept lattices are based on the theory of Formal Concept Analysis, a mathematical theory with applications in data analysis, information retrieval, and knowledge discovery. We present a new algorithm called TITANIC for computing (iceberg) concept lattices. It is based on data mining techniques with a level-wise approach. In fact, TITANIC can be used for a more general problem: Computing arbitrary closure systems when the closure operator comes along with a so-called weight function. The use of weight functions for computing closure systems has not been discussed in the literature up to now. Applications providing such a weight function include association rule mining, functional dependencies in databases, conceptual clustering, and ontology engineering. The algorithm is experimentally evaluated and compared with Ganter's Next-Closure algorithm. The evaluation shows an important gain in eﬃciency, especially for weakly correlated data.
%G Anglais
%R 10.1016/S0169-023X(02)00057-5
%J Data and Knowledge Engineering
%2 internationale
%8 2002-08-01
%V 42
%N 2
%P 189-222
%K Data mining ; Galois closure ; Concept lattice ; Association rules ; Algorithms

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="hal-00578830"><analytic>
<author><persName><forename>Gerd</forename><surname>Stumme</surname></persName>
<affiliation>
<orgName type="team">Institute AIFB, Universität Karlsruhe</orgName>
<country>DE</country>
<orgName type="institution">AIFB, Universit¨at Karlsruhe</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">TH</orgName>
<orgName type="team">University of Karlsruhe</orgName>
<country>DE</country>
<orgName type="institution">University of Karlsruhe</orgName>
<orgName type="institution">Universität of Karlsruhe</orgName>
</affiliation>
</author>
<author><persName><forename>Rafik</forename><surname>Taouil</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">ORPAILLEUR</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Yves</forename><surname>Bastide</surname></persName>
<affiliation>
<orgName type="laboratory">LIMOS</orgName>
<orgName type="team">Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR6158</orgName>
<orgName type="institution">Université d'Auvergne - Clermont-Ferrand I</orgName>
<orgName type="institution">Université Blaise Pascal - Clermont-Ferrand II</orgName>
<orgName type="institution">Institut Français de Mécanique Avancée</orgName>
</affiliation>
</author>
<author><persName><forename>Nicolas</forename><surname>Pasquier</surname></persName>
<affiliation>
<orgName type="laboratory">I3S</orgName>
<orgName type="team">Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis</orgName>
<country>FR</country>
<orgName type="institution">Université Nice Sophia Antipolis [UNS]</orgName>
<orgName type="institution">CNRS : UMR7271</orgName>
</affiliation>
</author>
<author><persName><forename>Lotfi</forename><surname>Lakhal</surname></persName>
<affiliation>
<orgName type="laboratory">LIM</orgName>
<orgName type="team">Laboratoire d'Informatique de Marseille</orgName>
<country>FR</country>
<orgName type="institution">CNRS : FR2246</orgName>
<orgName type="institution">Université de la Méditerranée - Aix-Marseille II</orgName>
</affiliation>
</author>
<title type="main" level="a">Computing iceberg concept lattices with Titanic</title></analytic><monogr><title level="j" type="main">Data and Knowledge Engineering</title><imprint><biblScope type="publicationDate">2002-08-01</biblScope><biblScope type="vol">42</biblScope><biblScope type="issue">2</biblScope><biblScope type="pp">189-222</biblScope></imprint></monogr><idno type="doi">10.1016/S0169-023X(02)00057-5</idno><idno type="HALid">http://hal.archives-ouvertes.fr/hal-00578830</idno><idno type="HALFile">http://hal.archives-ouvertes.fr/hal-00578830/PDF/Stumme_et_al._-_2002.pdf</idno></biblStruct>
</listBibl>
</listBibl>