AOC poset Builder

  • Home
  • Online from local file
  • Online from direct input
  • Offline with Java tool

AOC-poset algorithms

The AOC-poset (or pruned concept hierarchy, or Galois Sub-hierarchy) is the sub-order of the concept lattice restricted to Attribute-Concepts (highest concept introducing an attribute) and Object-Concepts (lowest concept introducing an object).

There are currently 4 published algorithms for building the AOC-poset:
  • Ares (incremental)
  • Ceres
  • Pluton
  • Hermes

Results

Below are the results of the comparisons between the algorithms implemented in Java:

Datasets


Tools

Terminology

Inheritance Knowledge space. Godin and Mili 1993. Robert Godin, Hafedh Mili, Building and maintaining analysis-level class hierarchies using Galois Lattices, Proceeding of OOPSLA '93, ACM SIGPLAN Notices, Volume 28 Issue 10, Oct. 1, 1993, pp. 394 - 410

Pruned concept hierarchy. Godin et al 1998.  Robert Godin, Hafedh Mili, Guy W. Mineau, Rokia Missaoui, Amina Arfi, Thuy-Tien Chau. Design of Class Hierarchies Based on Concept (Galois) Lattices. TAPOS 4(2): 117-134 (1998)

Galois Sub-hierarchy. Dicky et al 1995. Hervé Dicky, Christophe Dony, Marianne Huchard, and Thérèse Libourel. ARES, Adding a class and REStructuring Inheritance Hierarchies. in Proc. of Bases de Données avancées (BDA’95), pages 25–42, 1995.

AOC-poset. Osswald and Petersen, 2001/2003. Rainer Osswald, Wiebke Petersen. Logical Approach to Data-Driven Classification. In Proc. of KI 2003: Advances in Artificial Intelligence, 26th Annual German Conference on AI. Lecture Notes in Computer Science 2821, pp 267-281, Springer.

References

Ares. Hervé Dicky, Christophe Dony, Marianne Huchard, and Thérèse Libourel. ARES, Adding a class and REStructuring Inheritance Hierarchies. in Proc. of Bases de Données avancées (BDA’95), pages 25–42, 1995. paper

Ceres. Hervé Leblanc, Sous-hiérarchies de Galois : un modèle pour la construction et l'évolution des hiérarchies d'objets. Thèse de doctorat de l'Université Montpellier 2. 2000. thesis (french)  The algorithm is also outlined in a previous comparative study. draft.

Pluton. Anne Berry, Marianne Huchard, Ross M. McConnell, Alain Sigayret, and Jeremy Spinrad. Efficiently Computing a Linear Extension of the Sub-hierarchy of a Concept Lattice. In Int. Conf. on Formal Concept Analysis (ICFCA 2005), volume 3403 of Lecture Notes in Computer Science, pages 208–222. Springer, 2005. draft

Hermes. Anne Berry, Marianne Huchard, Amedeo Napoli, Alain Sigayret Hermes: an efficient algorithm for building Galois sub-hierarchies in Proc. of Concept Lattices and Their Applications (CLA 2012). pp. 21-32. Université de Malaga. paper

Local file

After selecting the file and the file format, press Create Matrix button

Direct input

After filling the table, press Create Matrix button

Java tool

This software implements 4 algorithms intended to build a AOC-poset (or Galois sub-hierarchy).

In order to use our algorithms, download AOCPosetBuilder.jar. Then run it from the command line.

Manual

Syntax

Print Help

java -jar AOCPosetBuilder.jar --help

Simple Syntax -- use default options:

java -jar AOCPosetBuilder.jar -a ALGO -i INPUT [-o OUTPUT] [-d DOTFILE]

Complete Syntax -- use other options:

java -jar AOCPosetBuilder.jar -a ALGO -i INPUT [-o OUTPUT] [-d DOTFILE] [-f DISPLAY-FORMAT] [-g] [-h] [-m IMPL] [-n INPUT-FORMAT] [-s] [-v] [-z]

Use graphical interface

java -jar AOCPosetBuilder.jar

Options

Algorithms

-a,--algo ALGO
name of algorithm to be used. Available algorithms are:
  • Ares (incremental)
  • Ceres
  • Pluton
  • Hermes
-m,--implementation IMPL
select implementation of the collections used by algorithms. Available implementations are :
  • BITSET (default) using java.util.BitSet
  • HASHSET using java.util.HashSet
  • TROVEHASHSET using gnu.trove.set.hash.TIntHashSet.

Inputs

-i,--input INPUT
input filename of binary context.
-n,--inputformat INPUT-FORMAT
format of the input file. Supported formats are:
  • CSV the classical comma-separated values format.
  • IBM each line is a suit of space separated number, the first one is the number of following number in this line, each following number are the identifier of the attributes associated to the object (Caution: the identifier numbers started at 1 and not 0).
  • SLF a human-readable format for binary context. The main feature of this format is to allow user assigning names to objects and attributes.
  • GALICIA_XML the XML format for binary context in Galicia.
  • ADJACENCY_MATRIX a list of space separated numbers. Each line contains a couple: object_number attribute_number.

Outputs

-o,--output OUTPUT
output filename of Galois Sub-Hierarchy represented in a XML structure.
-s,--simplified
simplified intent and extent in Galois Sub-Hierarchy xml representation.
-d,--dotfile DOTFILE
optional .dot filename for GraphViz.
-f,--format DISPLAY-FORMAT
display format of the concepts for GraphViz. Available formats are:
  • SIMPLIFIED (default) only new object and/or attributes are displayed.
  • FULL all intent and extent are displayed.
  • MINIMAL only concept ID are displayed.
-z,--size
option for GraphViz. Display size of intent and extent.

Miscellanous

-g,--gui
use graphical user interface. Note: the system look and feel is used except with Mac OS.
-h,--help
print the help content.
-v,--verbose
print a report of the algorithm execution. Info. about algorithm and implementation, size and density of the input matrix, execution time and the size of the sub-hierarchy

Usage example

Files example.csv, example.ibm, example.adj example.xml and example.slf represent the same matrix below:
0 1 1 0 1 1
1 0 0 1 1 1
1 0 0 1 0 0
1 0 0 1 0 1
0 0 1 1 1 1
1 0 0 1 1 1
this command:
java -jar AOCPosetBuilder.jar -i example.slf -a HERMES -o example_gsh.xml -d example.dot -f SIMPLIFIED -z
will produce a xml representation of the galois subhierarchy on file example_gsh.xml and a GraphViz file example.dot
Image produced with GraphViz