Fast Mining of Iceberg Lattices: A Modular Approach Using Generators
Identifieur interne : 002121 ( Main/Merge ); précédent : 002120; suivant : 002122Fast Mining of Iceberg Lattices: A Modular Approach Using Generators
Auteurs : Laszlo Szathmary [Canada] ; Petko Valtchev [Canada] ; Amedeo Napoli [France] ; Robert Godin [Canada] ; Alix Boc [Canada] ; Vladimir Makarenkov [Canada]Source :
English descriptors
Abstract
Beside its central place in FCA, the task of constructing the concept lattice, i.e., concepts plus Hasse diagram, has attracted some interest within the data mining (DM) field, primarily to support the mining of association rule bases. Yet most FCA algorithms do not pass the scalability test fundamental in DM. We are interested in the iceberg part of the lattice, alias the frequent closed itemsets (FCIs) plus precedence, augmented with the respective generators (FGs) as these provide the starting point for nearly all known bases. Here, we investigate a modular approach that follows a workflow of individual tasks that diverges from what is currently practiced. A straightforward instantiation thereof, Snow-Touch, is presented that combines past contributions of ours, Touch for FCIs/FGs and Snow for precedence. A performance comparison of Snow-Touch to its closest competitor, Charm-L, indicates that in the specific case of dense data, the modularity overhead is offset by the speed gain of the new task order. To demonstrate our method's usefulness, we report first results of a genome data analysis application.
Url:
Links toward previous steps (curation, corpus...)
- to stream Hal, to step Corpus: 002237
- to stream Hal, to step Curation: 002237
- to stream Hal, to step Checkpoint: 001B33
Links to Exploration step
Hal:hal-00640898Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Fast Mining of Iceberg Lattices: A Modular Approach Using Generators</title><author><name sortKey="Szathmary, Laszlo" sort="Szathmary, Laszlo" uniqKey="Szathmary L" first="Laszlo" last="Szathmary">Laszlo Szathmary</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-38354" status="VALID"><orgName>Département d'informatique [Canada]</orgName><orgName type="acronym">UQAM</orgName><desc><address><country key="CA"></country></address></desc><listRelation><relation active="#struct-360045" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-360045" type="direct"><org type="institution" xml:id="struct-360045" status="VALID"><orgName>Université du Québec à Montréal </orgName><orgName type="acronym">UQAM</orgName><desc><address><addrLine>Université du Québec à MontréalCase postale 8888, succursale Centre-villeMontréal (Québec) H3C 3P8 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.uqam.ca/en/about/presentation_en.htm</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Valtchev, Petko" sort="Valtchev, Petko" uniqKey="Valtchev P" first="Petko" last="Valtchev">Petko Valtchev</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-38354" status="VALID"><orgName>Département d'informatique [Canada]</orgName><orgName type="acronym">UQAM</orgName><desc><address><country key="CA"></country></address></desc><listRelation><relation active="#struct-360045" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-360045" type="direct"><org type="institution" xml:id="struct-360045" status="VALID"><orgName>Université du Québec à Montréal </orgName><orgName type="acronym">UQAM</orgName><desc><address><addrLine>Université du Québec à MontréalCase postale 8888, succursale Centre-villeMontréal (Québec) H3C 3P8 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.uqam.ca/en/about/presentation_en.htm</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Napoli, Amedeo" sort="Napoli, Amedeo" uniqKey="Napoli A" first="Amedeo" last="Napoli">Amedeo Napoli</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2358" status="OLD"><idno type="RNSR">200818291B</idno><orgName>Knowledge representation, reasonning</orgName><orgName type="acronym">ORPAILLEUR</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/orpailleur</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Godin, Robert" sort="Godin, Robert" uniqKey="Godin R" first="Robert" last="Godin">Robert Godin</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-38354" status="VALID"><orgName>Département d'informatique [Canada]</orgName><orgName type="acronym">UQAM</orgName><desc><address><country key="CA"></country></address></desc><listRelation><relation active="#struct-360045" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-360045" type="direct"><org type="institution" xml:id="struct-360045" status="VALID"><orgName>Université du Québec à Montréal </orgName><orgName type="acronym">UQAM</orgName><desc><address><addrLine>Université du Québec à MontréalCase postale 8888, succursale Centre-villeMontréal (Québec) H3C 3P8 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.uqam.ca/en/about/presentation_en.htm</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Boc, Alix" sort="Boc, Alix" uniqKey="Boc A" first="Alix" last="Boc">Alix Boc</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-38354" status="VALID"><orgName>Département d'informatique [Canada]</orgName><orgName type="acronym">UQAM</orgName><desc><address><country key="CA"></country></address></desc><listRelation><relation active="#struct-360045" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-360045" type="direct"><org type="institution" xml:id="struct-360045" status="VALID"><orgName>Université du Québec à Montréal </orgName><orgName type="acronym">UQAM</orgName><desc><address><addrLine>Université du Québec à MontréalCase postale 8888, succursale Centre-villeMontréal (Québec) H3C 3P8 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.uqam.ca/en/about/presentation_en.htm</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Makarenkov, Vladimir" sort="Makarenkov, Vladimir" uniqKey="Makarenkov V" first="Vladimir" last="Makarenkov">Vladimir Makarenkov</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-38354" status="VALID"><orgName>Département d'informatique [Canada]</orgName><orgName type="acronym">UQAM</orgName><desc><address><country key="CA"></country></address></desc><listRelation><relation active="#struct-360045" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-360045" type="direct"><org type="institution" xml:id="struct-360045" status="VALID"><orgName>Université du Québec à Montréal </orgName><orgName type="acronym">UQAM</orgName><desc><address><addrLine>Université du Québec à MontréalCase postale 8888, succursale Centre-villeMontréal (Québec) H3C 3P8 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.uqam.ca/en/about/presentation_en.htm</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">HAL</idno><idno type="RBID">Hal:hal-00640898</idno><idno type="halId">hal-00640898</idno><idno type="halUri">https://hal.inria.fr/hal-00640898</idno><idno type="url">https://hal.inria.fr/hal-00640898</idno><date when="2011-10">2011-10</date><idno type="wicri:Area/Hal/Corpus">002237</idno><idno type="wicri:Area/Hal/Curation">002237</idno><idno type="wicri:Area/Hal/Checkpoint">001B33</idno><idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">001B33</idno><idno type="wicri:Area/Main/Merge">002121</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Fast Mining of Iceberg Lattices: A Modular Approach Using Generators</title><author><name sortKey="Szathmary, Laszlo" sort="Szathmary, Laszlo" uniqKey="Szathmary L" first="Laszlo" last="Szathmary">Laszlo Szathmary</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-38354" status="VALID"><orgName>Département d'informatique [Canada]</orgName><orgName type="acronym">UQAM</orgName><desc><address><country key="CA"></country></address></desc><listRelation><relation active="#struct-360045" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-360045" type="direct"><org type="institution" xml:id="struct-360045" status="VALID"><orgName>Université du Québec à Montréal </orgName><orgName type="acronym">UQAM</orgName><desc><address><addrLine>Université du Québec à MontréalCase postale 8888, succursale Centre-villeMontréal (Québec) H3C 3P8 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.uqam.ca/en/about/presentation_en.htm</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Valtchev, Petko" sort="Valtchev, Petko" uniqKey="Valtchev P" first="Petko" last="Valtchev">Petko Valtchev</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-38354" status="VALID"><orgName>Département d'informatique [Canada]</orgName><orgName type="acronym">UQAM</orgName><desc><address><country key="CA"></country></address></desc><listRelation><relation active="#struct-360045" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-360045" type="direct"><org type="institution" xml:id="struct-360045" status="VALID"><orgName>Université du Québec à Montréal </orgName><orgName type="acronym">UQAM</orgName><desc><address><addrLine>Université du Québec à MontréalCase postale 8888, succursale Centre-villeMontréal (Québec) H3C 3P8 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.uqam.ca/en/about/presentation_en.htm</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Napoli, Amedeo" sort="Napoli, Amedeo" uniqKey="Napoli A" first="Amedeo" last="Napoli">Amedeo Napoli</name><affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-2358" status="OLD"><idno type="RNSR">200818291B</idno><orgName>Knowledge representation, reasonning</orgName><orgName type="acronym">ORPAILLEUR</orgName><desc><address><country key="FR"></country></address><ref type="url">http://www.inria.fr/equipes/orpailleur</ref></desc><listRelation><relation active="#struct-160" type="direct"></relation><relation name="UMR7503" active="#struct-441569" type="indirect"></relation><relation active="#struct-300009" type="indirect"></relation><relation active="#struct-300291" type="indirect"></relation><relation active="#struct-300292" type="indirect"></relation><relation active="#struct-300293" type="indirect"></relation><relation active="#struct-2496" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-160" type="direct"><org type="laboratory" xml:id="struct-160" status="OLD"><orgName>Laboratoire Lorrain de Recherche en Informatique et ses Applications</orgName><orgName type="acronym">LORIA</orgName><desc><address><addrLine>Campus Scientifique BP 239 54506 Vandoeuvre-lès-Nancy Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.loria.fr</ref></desc><listRelation><relation name="UMR7503" active="#struct-441569" type="direct"></relation><relation active="#struct-300009" type="direct"></relation><relation active="#struct-300291" type="direct"></relation><relation active="#struct-300292" type="direct"></relation><relation active="#struct-300293" type="direct"></relation></listRelation></org></tutelle><tutelle name="UMR7503" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID"><idno type="IdRef">02636817X</idno><idno type="ISNI">0000000122597504</idno><orgName>Centre National de la Recherche Scientifique</orgName><orgName type="acronym">CNRS</orgName><date type="start">1939-10-19</date><desc><address><country key="FR"></country></address><ref type="url">http://www.cnrs.fr/</ref></desc></org></tutelle><tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName><orgName type="acronym">Inria</orgName><desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/en/</ref></desc></org></tutelle><tutelle active="#struct-300291" type="indirect"><org type="institution" xml:id="struct-300291" status="OLD"><orgName>Université Henri Poincaré - Nancy 1</orgName><orgName type="acronym">UHP</orgName><date type="end">2011-12-31</date><desc><address><addrLine>24-30 rue Lionnois, BP 60120, 54 003 NANCY cedex, France</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300292" type="indirect"><org type="institution" xml:id="struct-300292" status="OLD"><orgName>Université Nancy 2</orgName><date type="end">2011-12-31</date><desc><address><addrLine>91 avenue de la Libération, BP 454, 54001 Nancy cedex</addrLine><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-300293" type="indirect"><org type="institution" xml:id="struct-300293" status="OLD"><orgName>Institut National Polytechnique de Lorraine</orgName><orgName type="acronym">INPL</orgName><date type="end">2011-12-31</date><desc><address><country key="FR"></country></address></desc></org></tutelle><tutelle active="#struct-2496" type="direct"><org type="laboratory" xml:id="struct-2496" status="OLD"><orgName>INRIA Lorraine</orgName><desc><address><addrLine>615 rue du Jardin Botanique 54600 Villers-lès-Nancy</addrLine><country key="FR"></country></address><ref type="url">http://www.inria.fr/centre-de-recherche-inria/nancy-grand-est</ref></desc><listRelation><relation active="#struct-300009" type="direct"></relation></listRelation></org></tutelle></tutelles></hal:affiliation><country>France</country><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Université Nancy 2</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName><placeName><settlement type="city">Nancy</settlement><region type="region" nuts="2">Grand Est</region><region type="old region" nuts="2">Lorraine (région)</region></placeName><orgName type="university">Institut national polytechnique de Lorraine</orgName><orgName type="institution" wicri:auto="newGroup">Université de Lorraine</orgName></affiliation></author><author><name sortKey="Godin, Robert" sort="Godin, Robert" uniqKey="Godin R" first="Robert" last="Godin">Robert Godin</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-38354" status="VALID"><orgName>Département d'informatique [Canada]</orgName><orgName type="acronym">UQAM</orgName><desc><address><country key="CA"></country></address></desc><listRelation><relation active="#struct-360045" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-360045" type="direct"><org type="institution" xml:id="struct-360045" status="VALID"><orgName>Université du Québec à Montréal </orgName><orgName type="acronym">UQAM</orgName><desc><address><addrLine>Université du Québec à MontréalCase postale 8888, succursale Centre-villeMontréal (Québec) H3C 3P8 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.uqam.ca/en/about/presentation_en.htm</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Boc, Alix" sort="Boc, Alix" uniqKey="Boc A" first="Alix" last="Boc">Alix Boc</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-38354" status="VALID"><orgName>Département d'informatique [Canada]</orgName><orgName type="acronym">UQAM</orgName><desc><address><country key="CA"></country></address></desc><listRelation><relation active="#struct-360045" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-360045" type="direct"><org type="institution" xml:id="struct-360045" status="VALID"><orgName>Université du Québec à Montréal </orgName><orgName type="acronym">UQAM</orgName><desc><address><addrLine>Université du Québec à MontréalCase postale 8888, succursale Centre-villeMontréal (Québec) H3C 3P8 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.uqam.ca/en/about/presentation_en.htm</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author><author><name sortKey="Makarenkov, Vladimir" sort="Makarenkov, Vladimir" uniqKey="Makarenkov V" first="Vladimir" last="Makarenkov">Vladimir Makarenkov</name><affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-38354" status="VALID"><orgName>Département d'informatique [Canada]</orgName><orgName type="acronym">UQAM</orgName><desc><address><country key="CA"></country></address></desc><listRelation><relation active="#struct-360045" type="direct"></relation></listRelation><tutelles><tutelle active="#struct-360045" type="direct"><org type="institution" xml:id="struct-360045" status="VALID"><orgName>Université du Québec à Montréal </orgName><orgName type="acronym">UQAM</orgName><desc><address><addrLine>Université du Québec à MontréalCase postale 8888, succursale Centre-villeMontréal (Québec) H3C 3P8 Canada</addrLine><country key="CA"></country></address><ref type="url">http://www.uqam.ca/en/about/presentation_en.htm</ref></desc></org></tutelle></tutelles></hal:affiliation><country>Canada</country></affiliation></author></analytic></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="mix" xml:lang="en"><term>data mining</term><term>formal concept analysis</term><term>frequent itemsets</term><term>frequent pattern mining</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Beside its central place in FCA, the task of constructing the concept lattice, i.e., concepts plus Hasse diagram, has attracted some interest within the data mining (DM) field, primarily to support the mining of association rule bases. Yet most FCA algorithms do not pass the scalability test fundamental in DM. We are interested in the iceberg part of the lattice, alias the frequent closed itemsets (FCIs) plus precedence, augmented with the respective generators (FGs) as these provide the starting point for nearly all known bases. Here, we investigate a modular approach that follows a workflow of individual tasks that diverges from what is currently practiced. A straightforward instantiation thereof, Snow-Touch, is presented that combines past contributions of ours, Touch for FCIs/FGs and Snow for precedence. A performance comparison of Snow-Touch to its closest competitor, Charm-L, indicates that in the specific case of dense data, the modularity overhead is offset by the speed gain of the new task order. To demonstrate our method's usefulness, we report first results of a genome data analysis application.</div></front></TEI></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002121 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Merge/biblio.hfd -nk 002121 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Merge
|type= RBID
|clé= Hal:hal-00640898
|texte= Fast Mining of Iceberg Lattices: A Modular Approach Using Generators
}}
| This area was generated with Dilib version V0.6.33. |  |