LeCo

Overview

LeCo (Lattice Constructor) is the third main module of the Coron platform. The goal of LeCo is to construct Hasse diagrams of formal concept lattices. LeCo can be used to construct either complete or iceberg lattices.

LeCo works the following way: as input, it takes the frequent closed itemsets (FCIs) that are generated by Coron-base. FCIs are the intent parts in the concepts of a Hasse diagram. LeCo can, in addition: (1) find extents (if you need them), (2) find order (construct the Hasse diagram), and (3) visualize the Hasse diagram.

Command-line usage

./core03_leco.sh  [switches]  <database>  <min_supp>  -alg:<alg>  -method:<method>

There are 4 compulsory parameters:

  1. database file (in .basenum, .bool, or .rcf format)
  2. minimum support
  3. name of the algorithm to be used
  4. method to be used to find the order among the concepts

The following algorithm/method combinations can be used:

Close:
   1) Naive 1                                  -method:naive1
   2) Naive 2                                  -method:naive2
Charm (v4) [triangular matrix; hash for FCIs]:
   1) Naive 1                                  -method:naive1
   2) Naive 2                                  -method:naive2
   3) Border                                   -method:border
   4) Border 2                                 -method:border2
Zart (v2) [triangular matrix]:
   1) Naive 1                                  -method:naive1
   2) Naive 2                                  -method:naive2
   3) Snow                                     -method:snow
Eclat-Z [save to file; process file; output: like Zart]:
   1) Naive 1                                  -method:naive1
   2) Naive 2                                  -method:naive2
   3) Snow                                     -method:snow
Touch (v1) [Charm + Talky-G + association]:
   1) Naive 1                                  -method:naive1
   2) Naive 2                                  -method:naive2
   3) Snow                                     -method:snow
dTouch [dCharm + dTalky-G + association]:
   1) Naive 1                                  -method:naive1
   2) Naive 2                                  -method:naive2
   3) Snow                                     -method:snow
Norris algorithm (FCA community):
   1) Naive 1                                  -method:naive1
   2) Naive 2                                  -method:naive2
Next Closure algorithm (FCA community):
   1) Naive 1                                  -method:naive1
   2) Naive 2                                  -method:naive2
CbO algorithm (FCA community):
   1) Naive 1                                  -method:naive1
   2) Naive 2                                  -method:naive2

Most efficient solution

Our most efficient implementation for the moment is the dTouch / Snow pair.

Implemented Methods

Naive1 (-method:naive1) and Naive2 (-method:naive2)

Two very simple methods for finding the order. They are slow but they are useful for comparing results when implementing a new method.

Border (-method:border)

This method was introduced in [1].

Border2 (-method:border2)

Border2, introduced in [2], is an improvement of the Border method. Note that in [2] we renamed Border2 to iPred.

Snow (-method:snow)

Snow, introduced in [3], is our most efficient method for finding the order among concepts.

A short example

If you need a full-fledged lattice:

./core03_leco.sh sample/laszlo.rcf 1 -names -order -alg:dtouch -method:snow -dot -ext -dot:ext -null -uc
cd graphviz/
./compile_gif_leco.sh
./view_leco.sh

That is:

  • specify the input database
  • min_supp=1, which means that you will have a complete lattice
  • attribute names are used instead of attribute numbers
  • we want to find the order among the concepts
  • we use the most efficient solution, the Snow-dTouch pair
  • we want to visualize the Hasse diagram with GraphViz
  • we also want to see the extents of the concepts (this is optional)
  • we also want to see the extensions in the GraphViz output
  • we do not want to see the lattice on the standard output
  • we want to see the attribute names in uppercase (which is more readable in my opinion)
  • the lattice is produced as a .dot file in the graphviz/ directory
  • compile the .dot file and visualize it

Troubleshooting: you will have to install these packages:

sudo apt-get install graphviz
sudo apt-get install gqview

The produced lattice (click for full size):

20091111_01.gif Explanation.
Consider the node in the top left hand corner just below the Top:
  • the intent of the concept is BE
  • the extent of the concept is 1345
  • the closed itemset BE has two generators: B and E
  • the support of the equivalence class of BE is 4

Further examples

Example 1 (stdout)

You can get a textual description of the lattice, i.e. no .dot file is produced, everything is sent to the standard output.

./core03_leco.sh sample/laszlo.rcf 1 -names -order -alg:dtouch -method:snow -ext

Example 2 (XML)

You can get an XML description of the lattice by using the switch -xml.

./core03_leco.sh sample/laszlo.rcf 1 -names -order -alg:dtouch -method:snow -ext -xml

Example 3 (PHP)

You can get a PHP description of the lattice by using the switch -php. Tip: from your PHP script you can call LeCo, redirect the output to a file, and then include that file in your PHP program.

./core03_leco.sh sample/laszlo.rcf 1 -names -order -alg:dtouch -method:snow -ext -php -of:/tmp/lattice.php

Example 4 (intents only)

To construct the Hasse diagram, we do not actually need the extents. It is enough to work with the intents only:

./core03_leco.sh sample/laszlo.rcf 1 -names -order -alg:dtouch -method:snow

To visualize the lattice, add some options:

./core03_leco.sh sample/laszlo.rcf 1 -names -order -alg:dtouch -method:snow -dot -null -uc

Meaning: -null: optional, suppress the output to the standard output; -uc: optional, show the attribute names in uppercase.

The produced lattice (click for full size):
20091111_02.gif

Example 5 (iceberg lattices)

To produce iceberg lattices, increase the value of the min_supp:

./core03_leco.sh sample/laszlo.rcf 3 -names -order -alg:charm -method:border2 -dot -null -uc

Here we used a different alg. and a different method. As a result, we have no generators associated to the concepts this time.

The produced iceberg lattice (click for full size):
20091111_03.gif

Notice that LeCo always adds a bottom concept. It has a technical reason. This way the lattice can be traversed not only from the Top but from the Bottom too. Since the support of the Bottom in this examle is less than the specified min_supp value, this Bottom should not be part of the iceberg lattice.


Bibliography
1. A Fast Algorithm for Building the Hasse Diagram of a Galois Lattice. P. Valtchev, R. Missaoui, and P. Lebrun. In Proc. of Colloque LaCIM 2000, pages 293-306, Montreal, Canada, 2000.
2. Yet a Faster Algorithm for Building the Hasse Diagram of a Galois Lattice. Baixeries, J., Szathmary, L., Valtchev, P. and Godin, R. In Proc. of the 7th Intl. Conf. on Formal Concept Analysis (ICFCA '09), pages 162-177, Darmstadt, Germany, May 2009. [ PDF, BibTeX ]
3. Constructing Iceberg Lattices from Frequent Closures Using Generators. Szathmary, L., Valtchev, P., Napoli, A. and Godin, R. In Proc. of the 11th Intl. Conf. on Discovery Science (DS '08), pages 136-147, Budapest, Hungary, Oct 2008. [ PDF, BibTeX ]
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License