Formal Concept Analysis Research Toolbox (FCART) is an integrated environment for knowledge and data engineers with a set of research tools based on Formal Concept Analysis (FCA). In the paper we consider main FCA workflow and some applications in the field of the text pattern matching.
Formal Concept Analysis (FCA) [
In previous articles [
In this paper we will focus on basic FCA tasks and some interesting applications in the field of the text pattern matching.
The underlying methodology of the FCART allows one to obtain new knowledge
from data in an iterative ontology-driven process. The software is based on modern
methods and algorithms of data analysis, technologies for processing big data
collections, data visualization, reporting, and interactive processing techniques. The
FCART evolves in the direction of a distributed system based on REST web-services
[
The current local version of FCART consists of the following components. ─ Core component includes: • the multiple-document user interface of research environment with session manager and extensions manager, • snapshot profiles editor (SHPE), • snapshot query editor (SHQE), • query rules database (RDB), • session database (SDB), • core of report builder. ─ Intermediate Data Storage (IDS) for preprocessed data collections in JSON format. ─ Internal solvers and visualizers. ─ Additional plugins, scripts and report templates.
We use Microsoft and Embarcadero programming environments and different programming languages (C++, C#, Delphi, Python and other). The native executable (the core of the system) is compatible with Microsoft Windows 2000 and later and has not any additional dependences. The important feature of FCART is scripting. Thus, generating and transforming artifacts, drawing, and building reports can be done by scripts. For scripting we use Delphi Web Script and Python languages.
From an analyst point of view, the basic FCA workflow in FCART has four stages (see Fig. 1). On each stage, a user has the ability to import/export every artifact or add it to a report. 1. The filling Intermediate Data Storage (IDS) of FCART from various external SQL, XML or JSON-like data sources (querying external source described by an External Data Query Description – EDQD). EDQD can be produced by some External Data Browser. 2. The loading a data snapshot from the IDS into an analytic session (a snapshot is described by a Snapshot Profile). A data snapshot is a data table with annotated structured and text attributes loaded in the system by accessing IDS. 3. The transforming a snapshot to a binary context (a transformation is described by a
Scaling Query). 4. The building and visualizing formal concept lattice and the other artifacts based on the binary context in a scope of analytic session.
External Data Source
External Data Set
External Data Query Description Snapshot Profile & Graph Generators Snaphot Scaling
Query
IDS Web-service
Http Request Parser
IDS Import/Export Tools Communication Subsystem
Indexing Subsystem
MongoDB Analytic Artifacts
Pattern Structure
Clusters SOMs
JSON Collection Binary Context
Concept Lattice
FCART Import/Export
Tools
Session DB
Data Snapshot (Multivalued Context)
Some of FCA entities appear to be fundamental to the information representation. In the methodology, we use the term “analytic artifact” to denote the definition of an abstract interface, describing the entity of the analytic process. The basic artifact for FCA-based methods is that of the “formal context”, i.e., object-attribute representation of a subject domain. The most important artifacts also include the “concept lattice” and the “formal concept”.
Artifacts’ instances can be linked by “origination” relationship. For example, we can generate a concept lattice from the given formal context. In this case, the formal concept will be an "origin artifact" or simply “origin” for the lattice. Another example is the pair of a lattice and an “association rules set”: the lattice is the origin of the rules set. Any artifact’s instance is immutable. It means that any instance cannot be changed after creation, but can be copied and visualized in various ways.
If we have the predefined set of artifacts, in the most cases we can use the term “artifact” instead of “artifacts’ instance” without ambiguity. The collection of all artifacts in current analytic cycle forms so-called “analytical session”.
An “Initial artifact” is an artifact without origin in a current session. For example, after loading a formal context from a file on a disk we obtain an initial artifact. Such an artifact becomes one of the roots in a current session. 3.2
An analyst works with analytic artifacts using solvers, visualizers and reports.
Solvers. All types of artifacts are generated by solvers. Each solver requires one or many artifacts’ instances of preassigned types as an input and produces one artifact’s instance of preassigned type as an output. The parameters profile of a solver allows to save/load parameters and automatically create dialogs for a user input. Each parameter has Id, title, data type, hint, group and default value.
Having the predefined types of artifacts and links (assigned by solvers) between immutable artifacts’ instances we can check the integrity of data of particular analytical session. Without explicit user action a session cannot lose any artifact instances and links, and guarantees the integrity of a session.
A solver without input artifacts is called “Generator”. Generator can use a script or a plugin for automatic building artifact from scratch.
Visualizers. Artifact visualizer is a special solver that generates the user-oriented visual representation of input artifact (or several artifacts) instance. From a technical point of view, visualizer produces an interactive or non-interactive window with some elements of user interface. Of course, one artifact can have different kinds of visual appearance.
Each artifact type has default visualizer, which is invoked by clicking on an artifact in the session window. The parameters profile of visualizer defines common visual properties and drawing parameters (for example, coordinates of concepts in a concept lattice). In interactive visualizer, a user has the set of tools for changing the drawing parameters “on the fly”. Usually, visualizer is the last in a chain of solvers. However, we can get a visual representation of each artifact in the current session. For example, formal concept lattice visualizer (lattice browser) draws a diagram of the lattice and allows a user to manipulate the diagram, but this browser itself does not generate new artifacts. We need to distinguish the generation of new artifact and drawing of an existing artifact for various cases: working in the batch mode, increasing efficiency of long chains of solvers, benchmarking, etc. Of course, a complex visualizer can help invoking next solvers by simplifying select of some input artifacts as parts of the visualized artifact.
Reports. Report is a final representation of the research results. Every scientific environment should provide a rich text editor of a report with additional functionality to avoid mistakes while converting and moving multiple artifacts with metadata into an external editor. The main feature of the FCART report builder is the automatic insertion of the fully decorated artifact representation in the resulting report. An artifact can support several representations in form of a text as of a vector or a bitmap image as well. 3.3
What is sources of the artifacts? An initial artifact can be generated by: 1. The executing a script or a plugin (with type “Generator of …”) without an input artifact. 2. The loading an artifact from a session or an external file 3. The querying to the IDS or some External Data Source. 4. The opening one of the interactive editor.
The result of a generator or a query becomes immutable. It is also obvious that artifact is mutable while editing by an interactive editor. A user can send a copy of an artifact to an interactive editor, if FCART has the registered editor for such an artifact’s type. Fig. 4 shows the user interface of the standard formal context editor. After execution of the “Build lattice…” command the immutable formal context is added to the session and becomes the origin of the formal concept lattice.
The Formal Concept Analysis approach is used for transform a Deterministic Finite
Automata (DFA) into a Failure Deterministic Finite Automata (FDFA). FDFA is
proposed and defined by Kourie D.G., Watson B.W. and others in 2012 [
Madoda N., Kourie’s master student, had used the local version of FCART in
2014 for efficient generation of the state/out-transition concepts and interactive
analysis of the state/out-transition (formal concept) lattice [
Optionally a user can check the context and analyse the lattice that also saved in XML format.
The next step should be the development of a new web-solver for distributed
version of FCART [
In this paper we have described the FCART software and its application in research of failure deterministic finite automata. The demo-version of used local version 0.9.4 of the FCART can be downloaded from http://cs.hse.ru/en/ai/issa/proj_fcart.
We will try to advance some functionality in the distributed version of FCART.
This work was carried out by the authors within the project “Data mining based on applied ontologies and lattices of closed descriptions” supported by the Basic Research Program of the National Research University Higher School of Economics.