A new general and e cient architecture for working with pattern structures, an extension of FCA for dealing with \complex" descriptions, is introduced and implemented in a subsystem of Formal Concept Analysis Research Toolbox (FCART). The architecture is universal in terms of possible dataset structures and formats, techniques of pattern structure manipulation.
FCART1 is a specialized software for data analysis by means of Formal
Concept Analysis (FCA) and related methods aiming at processing an arbitrary
dataset [
The paper is organized as follows. Section 1 de nes FCA and PSs. The next section describes the overall PS processing within FCART, divided into logical submodules of the approach. Finally, the paper is concluded before program interfaces of di erent modules are given.
Formal concept analysis (FCA) [
De nition 1. A PS is a triple (G; (D; u); ), where G is a set of objects, (D; u) is a complete meet-semilattice of descriptions and : G ! D maps an object to the description.
The lattice operation in the semilattice (u) corresponds to the similarity between two descriptions d1 and d2, i.e. the description which is common between d1 and d2. Standard FCA can be presented in terms of PSs in the following way. The set of objects G remains, while the semilattice of descriptions is (}(M ); \), where }(M ) is a powerset of M , and, thus, a description is a set of attributes. The similarity operation corresponds to the set intersection, i.e. the similarity is the set of common attributes. If x = fa; b; cg and y = fa; c; dg then xuy = x\y = fa; cg. The mapping : G ! }(M ) is given by, (g) = fm 2 M j (g; m) 2 Ig.
The Galois connection for a PS (G; (D; u); ) between the set of objects and the semilattice of descriptions is de ned as follows:
A := l (g);
g2A d := fg 2 G j d v (g)g; for A
G for d 2 D; where the partial order (or the subsumption order) on D is de ned w.r.t. the similarity operation u: c v d , c u d = c, and c is subsumed by d. De nition 2. A pattern concept of a PS (G; (D; u); ) is a pair (A; d) where A G and d 2 D such that A = d and d = A, A is called a concept extent and d is called a concept intent.
As in the standard case of FCA, a pattern concept corresponds to the maximal set of objects A whose description subsumes the description d, while there is no e 2 D, subsuming d, i.e. d v e, describing every object in A. The set of all concepts can be partially ordered w.r.t. partial order on the extents (dually, the intents by v), within a concept lattice.
Example 1. PSs are successfully used for interval data [
Example 2. Given a dataset with objects described by elements of poset P , e.g. sequences (w.r.t sequence-subsequence relation) or graphs (w.r.t. subgraph isomorphism relation), a corresponding PS can be de ned in the following way. The semilattice (D; u) based on poset P is a subset of the powerset of P , D }(P ), such that if d 2 D contains an element p 2 P then all its \subelements" x should be included into d, 8p 2 d; @x p : x 2= d, and the semilattice operation is the set intersection for two sets of elements. Given two patterns d1; d2 2 D, the set intersection operation ensures that if an element p belongs to d1 u d2 then any subsequence of p belongs to d1 u d2 and, thus, (d1 u d2) 2 D.
However, the set of all possible \subelements" for a given pattern can be rather large. Thus, it is more e cient and representable to keep a pattern d 2 D as a set of all maximal elements d~, d~ = fp 2 d j @x 2 d : x pg . Note that representing a pattern by the set of all maximal elements allows for an e cient implementation of the intersection \u" of two patterns.
m1 m2 m3 g1 [1; 3] [3; 5] [2; 4] g2 [5; 7] [4; 6] [2; 5] g3 [1; 9] [2; 7] [6; 6]
(fg1; g2; g3g ; h[1; 9]; [2; 7]; [2; 6]i) (fg1; g2g ; h[1; 7]; [3; 6]; [2; 5]i) (fg1g ; h[1; 3]; [3; 5]; [2; 4]i) (fg2g ; h[5; 7]; [4; 6]; [2; 5]i)
(fg3g ; h[1; 9]; [2; 7]; [6; 6]i) (;; )
PSs can be hard to process due to the usually large number of concepts in the
concept lattice and the complexity of the similarity operation (think for instance
of the graph isomorphism problem). Moreover, a pattern lattice can contain a
lot of irrelevant patterns for an expert. Projections of PSs \simplify" to some
degree the computation and allow one to work with a reduced description. In fact,
projections can be considered as constraints (or lters) on patterns respecting
certain mathematical properties, ensuring that the concepts in the projected
lattice have correspondence to the original ones [
A projection : D ! D is an operator, which is monotone (x v y ) (x) v
(y)), contractive ( (x) v x) and idempotent ( ( (x)) = (x)). A projection
preserves the semilattice operation u as follows. Under a projection , a PS
(G; (D; u); ) becomes the projected PS ((G; (D; u); )) = (G; (D; u); ).
The concepts of a projected pattern structure have a \similar" concept in the
initial pattern structure [
As a PS is an abstract mathematical object, any software aiming at the PS realization should either prepare several di erent PSs, such as PSs based on intervals or graphs, or give to a user an opportunity to add arbitrary PSs to the software. Our goal is to process any PSs and in this case one should decide how an arbitrary semilattice can be introduced by a user. It is not possible in some cases to enumerate all elements of a semilattice. For example, the semilattice of Function CloseByOne(Ext, Int)
Data: (G; (D; u); ), extent Ext and intent Int of a concept.
Result: All canonical ancestor concepts of the concept (Ext; Int). foreach S G, S Ext do
N ewInt d (g) ;
g2S N ewExt fg 2 G j N ewInt v (g)g; if IsCanonicExtension(Ext, N ewExt) then
SaveConcept((N ewExt; N ewInt));
CloseByOne(NewExt,NewInt ); CloseByOne(;, >);
Algorithm 1: The modi ed version of CbO for PS processing. /* u - intersection */ /* v - subsumption */ /* Find all concepts... */ graphs is in nite and even if one would like to select a nite subset of it, the subset should be signi cantly large in order to be useful in real-life applications. Another option is the constructive way for de ning a semilattice, i.e. one should be able to keep any element of the given semilattice, to compute the semilattice operation between two elements of the semilattice and to check equality of two elements. Although the subsumption relation on a semilattice can be checked as c v d , c u d = c, in many cases it can be more e cient to check the subsumption relation directly. Later we discuss how semilattices are processed more carefully.
But how can we build a concept lattice from a given PS? Many
state-of-theart algorithms can be slightly modi ed in such a way that avoid enumeration of
attributes, i.e. performing only the set intersection operation and checking the
subset relation without naming the attributes. This modi cation allows to
further substitute the set intersection by the corresponding semilattice operations
and to compute the concept lattice from a PS. Algorithm 1 shows the listing of
the modi ed CbO [
The following parts, called plugins, are introduced in FCART: { A constructive semilattice description; { Extent and Intent storages, managing extents and intents of a lattice; { A concept lattice builder working with any available semilattices.
Now we can build a concept lattice from any PSs, but we still do not know how to process the di erent element nature of a semilattice, i.g. how to load or save it. These problems are discussed in the following subsection as well as the processing of projections of PSs. 2.1
For the purposes of keeping and exchanging of patterns format JSON is chosen
because it allows to serialize nearly any kind of data, is standardized 1, has low
1 http://www.json.org/
f
g
f
g
\Count": 3,
\Inds":[
(a) Indices array. (b) Real numbers array.
f[ ]g ]g, f \NodesCount" : 2 g, f \Nodes" : [ f \Int" : 0, \Ext" : 0 g, f \Int" : 1, \Ext" : 1 g ]g, f \ArcsCount" : 1 g, f \Arcs" : [ f \S" : 0, \D" : 1 g, (c) Concept Lattice. parsing overhead, and is more compact than XML. We introduce the following general datatypes: primitives (numbers, strings), sets, ordered sets, rooted trees and general structures, i.e. graphs. But what kind of data we need to process? First a dataset from an external source should be converted to JSON and put into an internal collection. This imported dataset corresponds to a -function for a PS. Since the target semilattice can be a projection, the descriptions in this semilattice can be di erent from the descriptions in the imported dataset. For example, an object description can be a graph, while the projection can be a chain which can be kept in more e cient and tractable structure than a general graph. Thus we have two datatypes, one is used for a -function and the second is for a semilattice object. To allow for a plugin work with only the descriptions this plugin can work, the plugin speci es the external and internal datatypes by unique ID of that datatype. Figure 2 exempli es indexes array, which can be used to keep sets, and numbers array, which can be used as the initial description of interval PS.
The next entity for exchanging between FCART and a plugin is a concept lattice. In our case it is a set of concepts with several edges. The concepts extents and intents are referred by special indexes, which come from extent and intent storages. The simple lattice is exempli ed in Figure 2c.
Finally, a plugin can have its own running settings, which are given in an arbitrary JSON. For example, this properties allows us to realize a class of projections rather than a given projection, i.g. the projections of a graph to all its subgraphs of no more then k vertices, where k is a parameter of the plugin. A semilattice (D; u) is given in the constructive way by a plugin called \Pattern Manager". The main operations which should be performed by this plugin are listed in Table 2. The rst two properties are description types the plugin can load from a dataset or process as patterns. Patterns here refers to an internal data format of patterns known only by this pattern manager. Loading patterns from a given JSONs, patterns can be intersected or compared. This allows to give a semilattice in the constructive way without enumerating all possible elements of a lattice. Any patterns can be saved in a JSON of a `GetPatternType()' type. And, nally, there are three functions which can creates patterns. To remove a pattern and clear the memory of this pattern, function `FreePattern' is introduced. 2.3
Although Pattern Manager can create a lot of patterns by the intersection or the loading operations, it is not responsible for memory it creates. Plugin `Intent Storage' is a special layer which separates the raw representation of a pattern (an output of a Pattern Manager) and the IDs of intents, which are used in a lattice builder. Moreover, all patterns should pass through an Intent Storage and thus it controls memory for patterns. Intent Storage is responsible for the indexes it creates and, thus, it can be (de)serialized in a uni ed way in order to preserve the intents between sessions. Finally, as Intent Storage translates some of its call to Pattern Manager, we should initialize Intent Storage by the required Pattern Manager. The functions of Intent Storage are the same as for Pattern Manager but it should be initialized with a Pattern Manager and can be (de)serialized.
Plugin `Extent Storage' is an analog of Intent Storage but for the extents. We know exactly what an extent is, and, thus, the additional layer `Extent Manager' is not necessary. To work with extents in the bottom to top strategy we usually do not require any intersection operations and just add objects to this set. The interface functions of Extent Storage plugin are shown in Table 3. 2.4
Finally, to build a pattern concept lattice, a special plugin \Lattice Builder" is
introduced. Lattice Builder takes as an arguments Extent and Intent storages
and the path where the result lattice in the describing above format should
be saved. It has three functions: `Initialize()' taking Extent and Intent Storage
plugins; `AddObject(ObjID, IntentID)' taking a unique ID of an object which
should be added to the context with the corresponding description given by its
ID; and nally `Build()' building or postprocessing a lattice and writing it to
the required le. We should remember that there are two types of algorithms for
building a concept lattice: incremental such as AddIntent [
To allow the e cient implementation of any plugins, they are kept in a dynamic link library with a special API, which is called \Plugin System API". This library should contain at least three functions listed in Table 4. Function 'GetDescription' return a JSON array 2, with description of every plugin that can be found 2 JSON is selected for plugin data representation by the previously mentioned reasons. in the plugin system. The description contains unique ID of a plugin, type of the plugin, i.e. Patten Manager, Extent or Intent storage, or LatticeBuilder. According to the type of the plugin it contains the map from a plugin functions to the functions realized in the library.
Every plugin in a system should implement the functions listed in Table 5. Which allows to use them in a generalized way. The plugin can describe its parameters, for example the size of graph in a projection, and then load them and save them in a described JSON format. Finally, as some plugins can be initialized by other plugins, a plugin can request another plugin in its description. The initializing plugin is given to the requester as an ID and FCART has API for requesting an address of a plugin be the plugin ID and the function name.
Pattern structures is a very general and powerful technique for knowledge extraction form complex object descriptions with perspectives for working with Big Data. We implemented PSs within an original framework in an e cient and universal way. Current prototype is presented in FCART software and justi es the approach. The project is improving taking into account benchmark and pro ling results and requirements of researches.
Acknowledgements: this research received funding from the Basic Research Program at the National Research University Higher School of Economics (Russia) and from the BioIntelligence project (France). Function Description ID=GetObjectType() Returns the JSON type of an object ID=GetPatternType() Returns the JSON type of the patterns it works with Pttrn=Preprocess(JSON) Loads JSON description of an object and converts it to the internal pattern type P ttrn = a u b Computes semilattice operation between patterns a and b. fT rue; F alseg=a v b Checks if pattern a is subsumed by pattern b. fT rue; F alseg=(a == b) Checks if one pattern is equal to another pattern. Pttrn=LoadPattern() Convert the internal pattern to/from the JSON with type JSON=SavePattern(a) GetPatternType().
FreePattern(a) Free memory allocated for pattern a
Function Description Init() Initialization of a library Done() Deinitialization of a library JSON=GetDescription() Returns the description of all the plugins that the given plugin system support