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:
On randomly generated binary relations (uniform
distribution)
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.
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