We describe FCART software system, a universal integrated environment for knowledge and data engineers with a set of research tools based on Formal Concept Analysis. The system is intended for knowledge discovery from big dynamic data collections, including text collections. FCART allows the user to load structured and unstructured data (texts and various metainformation) from heterogeneous data sources, build data snapshots, compose queries, generate and visualize concept lattices, clusters, attribute dependencies, and other useful analytical artifacts. Full preprocessing scenario is considered.
We introduce a new software system for information retrieval and knowledge
discovery from various data sources (textual data, structured databases, etc.). Formal
Concept Analysis Research Toolbox (FCART) was designed especially for the analysis of
unstructured (textual) data. The core of the system supports knowledge discovery
techniques, including those based on Formal Concept Analysis [
FCART is based on DOD-DMS (The Dynamic Ontology-driven Data Mining System) software platform. In case studies we applied DOD-DMS for analyzing data in the fields of medical informatics and trends detection. The core of the system complements a traditional knowledge extraction process with methods of clustering, multimodal clustering, Formal Concept Analysis, Hidden Markov chains, pattern structures and others.
Currently, there are several well-known open source FCA-based tools, such as
ConExp [
For example, Coron has some tools for filtering objects and attributes, merging and transforming contexts (http://coron.wikidot.com/pre:filterdb), but Coron does not provide flexible tools for importing external data. 2
The DOD-DMS is a universal and extensible software platform intended for building
data mining and knowledge discovery tools for various application fields. The
creation of this platform was inspired by the CORDIET methodology (abbreviation of
Concept Relation Discovery and Innovation Enabling Technology) [
Now we introduce version 0.8 of DOD-DMS as a local Windows application and version 0.4 as a distributed Web-based application. Those versions use local XMLstorage for accumulating snapshots and integrated research environment with snapshot profiles editor, query builder, ontology editor, and some set of solvers (artifact builders) and visualizers (artifact browsers). The main solvers for this time can produce clusters, biclusters, concept lattice, sublattices, association rules, and implications, calculate stability indexes, similarity measures for contexts and concepts, etc. The set of solvers, visualizers, and scripts specifies a subject field of DOD-DMS edition.
We use Microsoft and Embarcadero programing environments and different
programing languages (C++, C#, Delphi, Python and others). For scripting we use Delphi
Web Script [
There are several ways to obtain a binary context, the basic FCA artifact: ─ Load from ready data files of supported formats like CXT or CSV, ─ Generate by plugin or script, ─ Query from data snapshots.
Loading contexts from ready data files is supported by most FCA-tools. The most interesting way to obtain a context is querying from snapshots. Let us look to all steps needed to convert external data into some set of objects with binary attributes. 4.2
Local storage of FCART can be filled from various data sources. System supports SQL, XML and JSON sources, so it can load data from most databases and Webservices.
Data snapshot (or snapshot) is a data table with structured and text attributes, loaded in the local storage by accessing external data sources. Snapshot is described by a set of metadata: snapshot profile, local path, link to external data source, time stamp, author, and comment. FCART provides one with a snapshot profile editor (SHPE). Profile consists of definitions of fields. Each element of a snapshot is a record: array of values of fields. Each field is defined by the following main properties: ─ Id (identifier of field) ─ Path (path in initial XML or JSON – may be empty) ─ Name (user-friendly name of field) ─ Group (for visual grouping of fields) ─ Comment ─ Data type (Boolean / Integer / Float / Text / Binary / DateTime) ─ Is Unstructured? (field can be interpreted as unstructured text) ─ Is Multivalued? (for sets / arrays) ─ Type of multivalued presentation (delimited content / same path / path in form of “name + number”)
Consider the following example of XML file: <?xml version="1.0" encoding="utf-8"?> <Data>
// ... <Genre>Lounge</Genre> <Genre>Easy listening</Genre>
// ... </Data>
In this example field “Genre” is multivalued and have multivalued presentation type “same path” (Path = “<Data>/<Genre>”). But in other source we can have type “name + number” (Path = “<Data>/<Genre%d>”): <Data>
// ... <Genre01>Lounge</Genre01> <Genre02>Easy listening</Genre02>
// ... </Data>
Unstructured field definition additionally contains the following properties: ─ Language (main language of text) ─ SW (list of stop words) ─ Stemmer (not required now because we use snowball stemmer from Lucene).
It is very useful for dealing with dynamic data collections, including texts in natural language, and helps to query full-text data more effectively. There is a sample of unstructured and multivalued field description in JSON format: { "Id": "02", "Path": "object\/author", "Caption": "Artwork Creators", "Group": "Common", "Comment": "The sequence of authors", "DataType": "Text", "Unstruct": { "Is": true, "Language": "English", "StopWords": [ ], "Stemmer": "Snowball" }, "MV": { "Is": true, "MVType": "Vector", "MVRepresentation": "NameNumber", "MVFormat": "author%d" } }
Fig. 1 shows a variant of snapshot profile editor (SHPE) for XML filtering. The left pane “XML Structure” displays a sample of an XML-document from a dataset. A user can select any element from the document, add it to profile as a new field and set properties of the field.
The system has query language for transforming snapshots into binary formal context. This language describes so-called rules. Main rule types are the following: ─ Simple rule generates one attribute from atomic fields of a snapshot. This rule type has syntax very similar to SQL WHERE clause ─ Scaling rule generates several attributes from atomic fields based on nominal or ordinal scale ─ Text mining rule generates one attribute from unstructured text fields. ─ Multivalued rule generates one or many attributes from multivalued field (arrays and sets) ─ Compound rule merges rules of all types into a single rule. This rule uses standard logical operations and brackets to combine elements.
We have also implemented additional rule types: Temporal rules are used for manipulating date and time intervals and Filters are used for removing objects with their intents from contexts.
In most cases, it is not necessary to write a query from scratch. One can select some entities in rules DB (RDB) and automatically generate a query. It is possible because the RDB is aware of dependencies between rules. Each rule type has XML presentation, so every query (or full RDB) can be imported and exported as an XMLfile.
The following XML file is a sample of the scaling rule: <scale name="Age" ScaleType="Order" DataType="Integer" Ends="Open" id="t34"> <Offset1>8</Offset1> <Offset2>16</Offset2> <Offset3>35</Offset3> <Offset4>60</Offset4> </scale>
The application of this rule to snapshot generates 5 binary attributes: “Age < 8”, “8 <= Age < 16”, …, “60 <= Age”.
FCART uses Lucene full text search engine [
The concept lattice visualizer is an example of interactive visualizer. It can be used to browse the collection of objects with binary attributes given as a result of query to snapshot (with structured and text attributes). The user can select and deselect objects and attributes and the lattice diagram is modified accordingly. The user can click on a concept. In a special window the screen shows names of objects in the extent and names of attributes in the intent. Names of objects and attributes are linked with initial snapshot records and fields. If the user clicks on the name of an object or an attribute, the content of the object or attribute description is shown in a special window according to the snapshot profile.
Fig. 2 demonstrates the result of building a sublattice from a concept lattice. The multi-document interface allows us to inspect several artifacts, so a sublattice will be opened in a new window.
The user can customize settings of lattice browsing in various ways. The user can specify whether nodes corresponding to concepts show numbers of all (or only new) objects and all (or only new) attributes in extent and intent respectively, or names of all (or only new) objects and all (or only new) attributes. Separate settings can be specified for the selected concept, concepts in the order filter, and the remainder of the lattice. The visual appearance can be changed: zooming, coloring, and other tools are available.
Right clicking on the name of an attribute user can choose several options: one can build a sublattice containing only objects with selected attribute; build a sublattice containing only objects without selected attribute; or find the highest concept with a selected attribute. Right clicking on the name of an object allows one the same actions.
If we built a formal context using a query to a snapshot then we can simply look for a definition of each attribute (in form of a query rule from RDB) and a source of each object (in form of XML- or JSON-file) in left part of the visualizer window. If a filter rule is present in query then we can see comparison between sets of objects in the context and records in the snapshot.
Linking analytic artifacts with snapshots are very important for subsequent analysis of the same data collection. Researcher can simply interpret results of the analysis by viewing initial pieces of data.
FCART is a powerful environment being in active development. The next major release of the local version 0.8 is planned for March 2013 and after that the system will be freely available to the FCA community. In this article we considered in details the powerful preprocessing tools of the system.
We intend to improve methodology, extend the set of solvers, optimize some
algorithms, and use the proposed system for solving various knowledge discovery
problems. We already have tested new solvers based on concept stability [
This work was carried out by the authors within the project “Mathematical Models, Algorithms, and Software Tools for Intelligent Analysis of Structural and Textual Data” supported by the Basic Research Program of the National Research University Higher School of Economics.