Formal Concept Analysis (FCA) provides mathematical models, methods and algorithms for data analysis. However, by now there is no easily available program system, which would provide data analyst with unified, intelligible and transparent access to various external data sources with large amount of heterogeneous data for subsequent FCA-based knowledge discovery. The lack of such tools complicates spreading FCA methods among big data analysts and miners of unstructured data. In this paper, we describe advances and new functionality in external data querying and preprocessing subsystems of Formal Concept Analysis Research Toolbox (FCART), which helps processing data of different types in a unified way.
By now, mathematical models of Formal Concept Analysis (FCA) [
Around the middle of the last decade, there were several successful
implementations for transforming a relatively small formal context into a line diagram
and computing implications and association rules. In [
Formal Concept Analysis Research Toolbox (FCART) [
In previous papers, we have described the system architecture, main workflow and
stages of data extraction from various external sources. Here we would like to
describe recent progress in the distributed version [
Data analysis is highly dependent on preprocessing, i.e., transformation from the source data format to the target data format, in which data are processed. An important functionality of any data analysis system is to support analyst in preprocessing transformations, making them transparent and easy. 2.1
From an analyst point of view, there is a gap between FCA analytical artifacts workflow and data and the legacy data. Fig. 1 illustrates this gap between “analyzable” and “external” data. It should be emphasized that it is not a gap between concrete data formats or access protocols, it is the gap in ways of thinking and knowledge representation.
The four main questions of object-attribute-value (or object-attribute) representation of data are trivial: 1) What are objects? 2) What are attributes? 3) How do we gather values of attributes? 4) How do we interpret values of attributes?
However, such questions bring into being a great many technological questions.
For now, we can observe specific data preprocessing techniques of concrete data
analysis projects. Can we propose fully unified approach? In general, the answer is
no. However, we can try to adapt some common techniques for most popular classes
of initial data formats and external data sources. On the one hand, we can see
appearance of such terms as “Data Tidying” [
Analyzable Data
Integrated Preprocessed Data (Analyst-oriented representation)
Heterogeneous Data
with specific API FCA-oriented query
Gap!
Data Snapshot (Multivalued Context)
Binary Context Concept Lattice
Other Artifacts
Relational Data (accessed by SQL queries) 1. Basic FCA algorithms have very high computational complexity. 2. Big concept lattices are not suitable for interactive processing and visualizing.
There were many attempts to adapt FCA-based methods for complex tasks. For
example, building Iceberg Lattices [
The core of the FCART supports knowledge discovery techniques, based on Formal Concept Analysis, clustering, multimodal clustering, pattern structures and others. From the analyst point of view, basic FCA workflow in FCART has four stages. 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/JSON and other data sources (querying external source is described by an External Data Query Description – EDQD). EDQD can be constructed by some visual External Data Browser (see later). 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 (a many-valued context) 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 other artifacts based on the binary context within an analytic session.
Later in this paper we will discuss mainly the first stage and using EDQDs. Hadley
Wickham in [
The current distributed version of FCART consists of the following four parts: 1. FCART AuthServer for authentication and authorization, as well as integration of algorithmic and storage resources. 2. FCART Intermediate Data Storage (IDS) for storage and preprocessing (initial converting, indexing of text fields, etc.) of big datasets. 3. FCART Thick Client (Client) for interactive data processing and visualization in integrated graphical multi-document user interface. 4. FCART Web-based solvers (Web-Solvers) for implementing independent resourceintensive computations.
IDS plays important role in effectiveness of whole data analysis process because all data from external data storages, session data and intermediate analytic artifacts saves in IDS. All interaction between user and external data storages goes through the IDS. All interactions between Client, Web-Solvers and IDS go through a RESTful Web-API. The http-request to the IDS web-service constructed from two parts: prefix part and command part. Prefix part contains domain name and local path (e.g. http://zeus2.hse.ru:8444/). The command part describes what IDS has to do and represents some function of the Web-API. Using web-service commands, FCART client can query data from external data storages in uniform and efficient way.
Early we already have implemented populating IDS from external data sources, but now we extend the set of providers and improve data providers’ EDQDs. 3
Readers may have noticed that a simplest case of legacy data for object-attribute
representation is relational data that meet the well-known conditions of E. Codd [
Documents are kept in many data formats (only ISO standards describe more then 400
formats, for example see [
XML and its extensions have regularly been criticized for verbosity and complexity. JSON is lightweight alternative which focus on representing (serializing) programming language level objects with complex data structures rather than documents, which may contain both highly structured and relatively unstructured content. JSON is an open standard format that uses human-readable text to transmit data objects consisting of attribute–value pairs.
Traditional relational databases are not convenient for fast processing of big amounts of unstructured textual datasets with metadata. Document-oriented databases operating with documents in XML or JSON format are successfully used for storing, retrieving and managing big amounts of textual data in last decade. Both FCART IDS and FCART Client can handle XML and JSON documents as input format. XML format is complex and relatively hard to process at the same time. JSON format is more easy to use and lightweight. FCART uses JSON internally as a main format for data serialization and intercomponent communication. 3.2
Preliminary problem of the discussed concepts is a terminological one. Table 1
illustrates the difference in approaches to defining terms for basic data-related
concepts in SQL Servers (as stated in the SQL ISO Standard [
In IDS we use data representation in form of “Databases” with hierarchical
structure of “Collections” of JSON “Documents”. Each of the Documents may
contains heterogeneous “Fields”. Each Collection can possess metadata, which
describes structure of Documents and data types of Fields using JSON Schema [
Extracting data is complicated by the fact that any Internet data source may have its own API. For example, we consider Social Network Services as a data source. That is why one needs mechanism to describe how data should be extracted, preprocessed and stored in IDS. For unified data access we developed External Data Query Description (EDQD) language. Each EDQD is a JSON formatted document. It aims to unify access to different data sources. By using EDQD FCART represents data from various data sources as a IDS Collection. There is no way to create a single query with fixed fields that would be with various data sources because each data source has its own set of functions, its own API. However, we developed the most common EDQD types and field set for mentioned above data sources types (Fig. 2).
EDQD for IDS Intermediate Data Storage
IDS Web-service interface
Http Request Parser IDS Import/Export Tools Communication Subsystem
Indexing Subsystem MongoDB
Elasticsearch Snapshot Profile
JSON Collection
EDQD for SQL EDQD for Text EDQD for SD
External data
Relational Data (accessed by SQL queries) Network Data (Graph models)
Data Snapshot (Multivalued Context)
EDQD for SNS
Each field is a JSON object. An EDQD query includes next fields:
─ ID – this field describes a unique identifier GUID.
─ TYPE – this field describes type of data source. For now, FCART supports next
types: “FS Folder”, “FS File”, “TSQL”, “REST”, “SOAP”, ”Facebook”, etc. Also
EDQD with type “IDS” can refer to documents which are already stored in IDS.
─ URI [
This are the common fields for all EDQD queries. Below we have described specific for data sources EDQD queries.
Creating EDQD is a complex task, which needs visual tool for development. For now, External Data Browsers have been prepared to help user constructing EDQD for local JSON/XML files, unstructured text files and SQL data sources. Other types of EDQD can be created via direct JSON editing. 4.1
EDQD for a SQL data source is the most straightforward. For now, IDS supports connection to the Microsoft SQL 2014 (and its earlier versions) and Postgres 9.5.2 (and its earlier versions). EDQD for SQL has the following fields: ─ “ID” – GUID (Globally Unique Identifier). ─ “TYPE” – DBMS Type. Can be “TSQL” or “PS”. ─ “URI” – This field is empty for that EDQD query type. ─ “CS” – Connection String. ─ “QUERY” – TSQL or PL-SQL query. ─ “TRANSFORMATION” – For now it describes mapping a column name to a target field path in JSON document. }
EDQD for Text (a collection of files with unstructured text) provides ability to extract and transform data from unstructured texts. To analyze data from unstructured data file we need to create an inverted index. Using inverted index reduces searching time for every text word.
The inverted index is a central component of indexing search engine. A goal of a
search engine implementation is to optimize the speed of the query: find the
documents where word X occurs. Once a forward index is developed, which stores
lists of words per document, it is next inverted to develop an inverted index. Querying
the forward index would require sequential iteration through each document and each
word to verify a matching document. The time, memory, and processing resources to
perform such a query are not always technically realistic. Instead of listing the words
per document in the forward index, the inverted index data structure is developed
which lists the documents per word [
To create inverted index, we use full-text search engine. For now, there are many
full-text search engines, which provides rapid search, complicated query language and
REST interface. Solr [
Initial sets of automatically extracted keywords may be very big. We can have additional instruments for such sparse contexts with many uniform attributes like sorting and searching attributes (Fig. 3) or analyzing attributes usage statistics. But more proper way to generate initial context is using adjustable query.
Example of EDQD for a query to a folder with text files: { “ID”: {6F9619FF-8B86-D011-B42D-00CF4FC964FF}, “TYPE”:”FS folder” “URI”:”file://localhost/c|/source/” “CS“:”” “QUERY”:”” “TARGET”:” file://localhost/c|/target” “TRANSFORMATION”: { “field”: { “name”: “” “target_field”:”body”, “type”:”text”, “indexing”: True} }
Field “Transformation” is the most interesting part of EDQD for a local text-files folder. “Name” refers to a field of result IDS document is affected. “Target_field” describes name in IDS document. “Type” describes type of the source field. The value of the EDQD field “Type” determines operations and transformations which are applicable to a document field. By now, FCART supports an indexing operation on the “text” type. By default, the value of “Indexing” field is False. }
EDQD for web-service interface provides ability to extract data from web-service. In the current version FCART supports REST and SOAP interfaces. EDQD for webservice has the following fields: ─ “ID” – GUID (Globally Unique Identifier). ─ “TYPE” – Web-service type. Can be “REST” or “SOAP”. ─ “URI” – URI of web-service. ─ “CS” - This field is empty. ─ “QUERY” – JSON document which contains query. ─ “TRANSFORMATION” – JSON document which describes field mapping.
Example of EDQD query to an Elasticsearch REST interface: { “ID”: {6F9619FF-8B86-D011-B42D-00CF4FC964FF}, ”TYPE”:”REST”, “URI”:”http://elasticsearch:1234/index_name/mapping_name/”, “CS”: “”, “QUERY”: “{ "query": { "bool": { "must": [ {"match":{"address": "mill" }}, {"match":{"address": "lane" }} ] }}}”, “TRANSFORMATION”: “{ “field”:{ “target_field”: “body”, “indexing”: True}” }
REST interfaces can iterate set of elements, which are returned by query. Query field contains JSON document written on Elasticsearch query language (https://www.elastic.co/guide/en/elasticsearch/reference/current/index.html).
Transformation field contains JSON document, which describes target field and preprocessing operation. The current version of FCART supports only indexing operation. 4.5
In this paper, main problems of external data access in FCA-based analytics software were addressed and some real cases were examined while implementing new functionality in the FCART system. The demo version of FCART client is available at https://cs.hse.ru/en/ai/issa/proj_fcart and the test version of the IDS Web-service is available at http://zeus2.hse.ru:8444.
For FCA-based data analysis fundamental requirements for software are as follows: 1. The ability to merge heterogeneous data sources in a query to external data. 2. The ability to cache frequent queries. 3. The automatic populating of query metadata. 4. The support of many formats of local data files to communicate with other software tools easily. 5. The support of apriori prescribed constraints on FCA algorithms and visualization schemes. 6. The availability of common and special “quick and dirty” methods of query result visualization with low computational complexity.
When prototyping clinical decision support system components, we have realized the importance of having local and web-based versions of the preprocessing tools. So unification of external data access tools is the first step in satisfying informal analysts’ wishes. We also understand importance of other subsystems, including efficient data transformation algorithms, dashboards, etc. However, without unified and reproducible access to initial data no one can build real data analysis workflow.
Improved mechanisms of query data work faster, more intelligible and provide necessary information to data analyst. The next steps in our development process are adding new External Data Browsers, increasing efficiency of EDQD processing and standardizing new API for running Web-Solvers inside IDS instead of Client. Acknowledgments This work was carried out by the authors within the project “Mining Data with Complex Structure and Semantic Technologies” supported by the Basic Research Program of the National Research University Higher School of Economics.