In a recent paper, we presented a new pattern discovery algoriNtehxmt,PriorityConcept, in order to take into account complex and heterogeneous data using Formal Concept Analysis. We implemented this algorithm and developed apython 3 library whose acronymGALACTIC means Galois LatticesC,oncept Theory,Implicational systems andClosures. It is opened to the community using a BSD-3 license and its architecture allows the writing of plugins to take into account new datatypes. In this article we will present the architecture of our software solution, we will explain how to add new plugins to the core of our system by giving the UML diagram of each kind of plugins and we will give some examples of plugins developed within our team.
extend the approach of pattern structu1r]easn[d logical concept analysis2[]. It’s a development
platform for a generic implementation of NthexetPriorityConcept[
predicates; • A core which implements theNextPriorityConcept algorithm and a lot of tools for visualizing lattices and reduced contexts in python notebooks; • A set ofcharacteristic plugins defining new types of data; • A set ofdescription plugins defining new types of descriptions and their associated • A set ofstrategy plugins defining new types of strategies for a given characteristic;
Strategy Data reader
Next Priority Concept • A set ofmeasure plugins useful for the filter meta-strategies; • A set ofdata reader plugins allowingGALACTIC to read any type of data file; • A set ofapplications using the core library and the diferent plugins; • A set oflocalization plugins for translating the diferent applications.
Each plugin must register with the core library by declaring an entry point in the configuration ifle of the setuptools1 (setup.py) named py_galactic_extension. The declared function informs the library that a new extension is available.
The construction of the lattice is carried out as showFing.i1n: the data are read from a file; characteristics are extracted; a description is produced for each concept; strategies generate selectors for the exploration of potential new concepts NanedxtPhreiorityConcept algorithm selects the predecessors and maintains the lattice structure.
A data reader plugin is responsible for reading a file according to its extension and producing the list of individuals of the population. It must implement two class methods: • read(cls, data_file: TextIO): Iterable[Any] that reads a file and produces an iterable of objects. • extensions(cls): Iterator[str] that produces the list of file extensions supported by this plugin. 1https://pypi.org/project/setuptools/
Each concept is composed of a subset of objects together with a set of predicates describing them, each predicate being specific to one type of characteristics. Such generic use of predicates makes it possible to consider heterogeneous data as input, i.e. numeric, discrete or more complex data.
A characteristic plugin (Fcifg. 3 in appendix) is responsible of extracting a value from a python object. It must implement t_h_ecall__ magic method which will be applied to each individual of the population. This method should return the characteristic of the individual. It is also reasonable to implement the other magic meth_o_desq__, __hash__, __str__.
The algorithm introduces the notiondeoscfription as an application to provide predicates describing a set of objects according to their characteristics, that corresponds to a concept (, ()) . At each iteration, predicates describing the ob jecotfsthe current concept are computed ”on the fly” by a specific treatment for each type of characteristics, depending on whether it is numeric, discrete or more complex, and the final descri ptiisotnhe union of these predicates. In order to obtain a lattice, the description must()ve⊑ri(f y ′) for ′ ⊆ . NextPriorityConcept computes the concept lattice of the context composed of individuals in rows and predicates issued from the description in colum3]n.s[
A description plugin (cFfig. 4 in appendix) is used to describe a collection of individuals using a set of predicates. It usually defines a new predicate class and a new description class. The description class is responsible of calculating a set of descriptors representing the convex hull of a collection of individuals. These descriptors must be predicates that describe half-spaces on the set of individuals. The convex hull is represented by the intersection of the set of descriptors.
The algorithm also introduces the notionstroaftegy to provide selectors generating the predecessors of a concep(t, ()) . The selectors propose a way to refine or cut the description () . The purpose of a strategy plugin is then to produce a set of selectors restricting the set of individuals in order to obtain new potential concepts containing fewer individuals. The NextPriorityConcept algorithm selects among the set of selectors produced by the strategies that generates new efective concepts (i.e. with a reduction of individuals). The lattice property is maintained using propagation of cross and residuals constraints and a level by level generation of concepts using a priority queu3e].[
A basic strategy plugin proposes selectors to NtehxetPriorityConcept algorithm. These selectors act as cut into the set of individuals. A basic strategy must be initialized with a description and must implement tsheelectors method (cfFig. 5 in appendix).
The core of theGALACTIC library defines two meta-strategies that act as filters for other strategies: • LimitFilter which selects predecessors whose measure is above/below a threshold; • SelectionFilter which selects the best/worst predecessors relatively to a measure.
They are initialized with a set of strategies and with a measure. A measure is a class for measuring a predicate on a concept. It must implement__tchaell__ magic method with a concept and a predicate as parametersF(cigf. 6 in appendix).
We implemented some basic description and strategies plugins to manage boolean, categorical, numerical characteristic, but also more complex characteristics such as temporal seq4u].ences[
When characteristics are of the same tyNpex,tPriorityConcept ofers the possibility to process them separately or together. An immediate way to process with several characteristics together would be to merge the predicates obtained in individual cases, both for the descriptions and for the strategies. But it is possible to obtain more relevant predicates by using a specific process.
For boolean characteristics for example, the classical FCA approach describes a set of objects thanks to the set of attribu t=es{ ∶ ∈
and possesses } and the strategy would consider as selectors the set of all the attributes that are n.oTtheisne two sets described by predicates of the form ”possesses attribu”tweould respectively corresponds t()o and () .
It is possible to consider other descriptio ns boyf the introduction of negative attributes, for example, the disjunction of clauses or its minimalization.
⋁ ⋀ { ∈ if possesses otherwise (1)
We defined plugins allowing to manage several boolean variables and their negations in the
same description using the well-known Qui-nMecCluskey’s dual algorithm (or the method of
prime implicants) that computes the minimization of a set of disjunctive clauses with a time
complexity in(3 log ) [
The basic strategy associated to that description consists in simply adding a boolean variable or its negation to a concept to generate its potential predecessors.
As already proposed in pattern structure the6o],riyt[ is possible to describe a set of poi ntsof ℝ using the usual convex hull represented by a polytope, the descript()ionis then composed of predicates describing the borders of the convex hull. For points in two and three dimensions, output-sensitive algorithms are known to compute the convex hull in( timloge ) , where is the number of points.
We defined a description calculating the convex hull, and two strategies for cutting the -dimensional space by projecting the data on the main axis of inertia: • we can define two predicates, ≥ − and ≤ + where is a parameter of this strategy , is the mean and is the standard deviation; • we can define a set of similar predicates by using the quantiles of the numerical data. The number of quantiles is a parameter of the strategy.
The measure plugins are mainly used in thLeimitFilter and SelectionFilter metastrategies. They must give a numerical value evaluating a predicate in relation to a concept. In the core, we developed the confidence, support and cardinality measures and we defined a plugin for evaluating the entropy relatively to a categorical characteristic, i.e. a class attribute.
For a given concept(, ) , a predicate that select only some individuals fro mand a categorical characterisΩti,cthe entropy (, , Ω) is defined by:
( ′, Ω) = (, , Ω) = ({ ∈ |()}, Ω) + (1 − ) ({ ∈ |¬()}, Ω) ( ′, Ω) = ∑ ( ′, Ω)( ( ′, Ω)) ∈ Ω |{ ∈ ′|Ω() = }|
| ′|
where is a [
In this article, we described the software architecture ofGoAuLrACTIC platform that implements the NextPriorityConcept algorithm to generate formal concepts for heterogeneous and complex data.
We explained the diferent types of plugins (reader, characteristic, description, strategy, measure) and we specified the methods to implement new ones. Then we presented some interesting plugins that we had developed, that can be used either to mine data or to develop new plugins. We are currenly working for plugins on time series.
Inspired from pattern structures, the generated lattices are often smaller with more relevant concepts thanks to the notion of strategy, and a user driven approach to discover patterns is possible, in an interactive way for instance. TGhAeLACTIC engine is data agnostic since it only handles predicates generated by strategies and descriptions for each type of characteristics.
We are currently working on adding a graphical interface and the possibility of changing strategies on demand. This will ease the use of tGhAeLACTIC platform for non-IT users. Future work will also be devoted to the extraction of minimal generators and logical rules from the concepts. descriptions: Iterator[Description] mybasicplugin
produces galactic.descriptions galactic.strategies descriptions: Iterator[Description]
MetaStrategy strategies: Tuple[Strategy]
Filter measure: Measure
contains Measure
LimitFilter
SelectionFilter mymeasureplugin
MyMeasure
A measure can be called on a concept for a specific predicate.