Formal Concept Analysis (FCA) has been extensively used in a wide range of problems, e.g, as the basis for semantic search engines and as a means of organising information based on its meaning. FCA has also been used to mine data for groups of items and their associated transactions to identify, for example, groups of products that are frequently purchased together.

One critical issue of the traditional concept lattice visualisation is that it grows dramatically with the number of objects and attributes. On the other hand, the analysis process can be greatly enhanced with aid of visual analytics techniques.

Following a user-centered design methodology, the present thesis addresses the problem of mining and visualising concepts over a data stream. The proposed approach is twofold: First, compute formal concepts in a data stream using a distributed architecture, in order to overcome the limitations of scalability of traditional approaches. Second, we design a visual analytics interface to allow selecting, comparing, filtering, detailing and overview of concept lattice features.

We present three use cases that demonstrate the application of the proposed techniques in a real-world setting. The three use cases are: a) Aircraft cabin design, where new visualisations for continuous data helped analysts to quickly identify classes of comfort for passengers; b) Genes co-expression analysis using a combination of both analytics features and semantic integration; and c) Prediction of possible failures from telemetry data in real-time. I would never have been able to finish this thesis without the guidance of my committee members, help from friends, and support from my family.

I sincerely thank my supervisors Marie-Aude Aufaure and Bénédicte Le Grand for their endless support and encouragement without which this research work would not have been attainable. Marie-Aude always motivated me to deliver the best and offered me many great opportunities. Bénédicte guided my through the course of my Ph.D. with brilliant ideas and discussions. I felt encouraged every time I attended her meeting.

I woud like to express my greatest gratitude to professors Nizar Messai and Anastasia Bezerianos for their useful comments, remarks and engagement through the learning process of this thesis.

Thanks to everyone who I interacted with at École Centrale, all MAS-BI members, staff and Centrale Recherche S.A., for their support and worthy contributions during the course of my studies.

An illustration of the Landmark model (circle indicates a transaction).

As a new transaction arrives it is added to the processing. . . . . . . . . Computing technology quickly scaled in importance during and after WWW I and II, a period when a number of breakthroughs were conceived, such as the transistor in early 1950s, space exploration missions between 1957 and 1975, personal computers with Apple I in 1976, to name a few. Great computing power and new techniques fostered innovations in virtually all areas, from military to science, government, manufacturing, agriculture, and even literature. In the late twentieth century, the world saw the rise of Capitalism, an economic system based on capital accumulation. Capitalism's focus on economic growth kept the wheels of technology turning at even greater pace. As

Capitalism had started to spread more widely by the end of the last century, almost the entire world shared one ambition: produce more to sell more and produce efficiently to cost less. A new world, with an number of possibilities ever experienced by humanity.

We now live in a age of acceleration with a torrent of inventions, devices and interconnectedness. The advance of technology is a by-product of humans eagerness to consume, accumulate wealth and live longer. Understanding the forces that drive these innovations is a preamble to any modern scientific research. Moreover, dealing with the huge volume of information generated daily has become a challenge.

Humans deal with information complexity by seeing patterns, using their imagination, experience and intuition. Computers can only deal with numbers as they have no intuition, as commonly thought. The idea that machines could outstrip humans intellectually is a question that long appeared in science fiction. A range of technologies that enhances human cognition are used to discover patterns, predict trends; they have allowed us to take better and fast decisions, in ways that were previously unachievable.

Information has become the umbrella resource of many applications to a point where unimportant information prevails over meaningful information by a large margin. In this context, Business Intelligence (BI) emerged as a discipline that aims to take all relevant, available data and convert it into knowledge. BI uses technologies and applications to gather, represent and analyse data to support decision making.

The greater computing power achieved by recent distributed computation techniques made it more challenging to extract relevant information. Although the field of data mining is being heavily investigated, there are still few methods able to convey a large volume of stream data in meaningful insights.

Motivation

For each produced bottle of milk, there are roughly 2,000 transactions involved in the whole process from harvesting to distribution. The whole milk, once approved for use, is pumped into storage silos where it undergoes pasteurization, homogenization, separation and further processing. In each phase, hundreds of transactions are produced and serve as input for the subsequent phases. A transaction in this case may contain information about the operation performed, current state, history, nutritional information, batch, validity, and other domain specific properties (FAO, 1999).

In other contexts, WalMart records 20 million sales transactions in a single day, whereas

Google handles 150 million searches, and AT&T produces 270 million call records. The figures also hold for an increasing number of small-sized institutions that are generating more data, more often. It is not only important to process huge amounts of data stream, but do fast and reliably.

Data in transactions are an increasingly part of our daily lives and there is a growing need to extract relevant information from them. Facebook reached 4 billion active users as of 2011. Youtube claims they reached the same number by 2013. Although being known for their huge IT infrastructure, none of theses services can deal effectively with the entirety of data their users produce everyday. Facebook's CEO Mark Zuckerberg has admitted that they were unable to answer a simple question such as "Who was the 4 billionth user to sign up? ". Like most companies, sampling is Facebook's best bet.

"Doing data analytics at this scale is a big challenge, and one of the things you have to do is sample" (BusinessWeek, October 04 2012).

Distributed computation techniques such as Map/Reduce along with powerful frameworks like Hadoop 1 have helped fill this gap by employing a divide-and-conquer approach: big problems are split into smaller parts that can be computed concurrently and partial results are merged at the end of the computation.

Despite the great computing opportunities these frameworks provide, it has only increased the need for means of identifying and understanding relevant information. Modern support decision programs have shift from purely "number crunching" methods in favour of more semantic approaches.

Formal Concept Analysis (FCA) may play an important role in this context, by employing more intelligent means in the analysis process. FCA became popular in the early 80's as a mathematical theory of data analysis based on the philosophical notion of a concept and concept lattice [START_REF] Ganter | Formal Concept Analysis[END_REF].

In FCA, concepts are formalized as groups of objects (representing studied elements) associated with groups of attributes, which are the objects' features. Hierarchical relationships between these groups are formed and visualized and can be used for information 1 Apache Hadoop. http://hadoop.apache.org retrieval. Information organized in this way has a close correlation to human perception and the combination with visualisation is therefore interesting for Business Intelligence.

FCA has been used as the basis for semantic search engines [START_REF] Ducrou | An intelligent user interface for browsing and searching mpeg-7 images using concept lattices[END_REF] and as a means of organising information based on its meaning [START_REF] Becker | The toscanaj suite for implementing conceptual information systems[END_REF].

FCA has also been used to mine data for groups of items and their associated transactions [START_REF] Lakhal | Efficient Mining of Association Rules Based on Formal Concept Analysis[END_REF]) to identify, for example, groups of products that are frequently purchased together. Other use case examples of FCA include:

• Marketing: finding groups of customers with similar behaviour given a large database of customer data containing their properties and past buying records;

• Biology: hierarchical classification of plants, animals, genes, given their features;

• Internet: document classification; clustering clickstream data to discover groups of similar access patterns and creating recommender systems;

• Search: Google's algorithm predicts and displays search queries based on other users search activities.

• E-Commerce: Amazon Recommendation, e.g. customers who bought digital camera, may be interested in a memory card or extra battery.

Formal concept mining is a computationally intensive task and the vast majority of existing algorithms do not take advantage of concurrent processing techniques [START_REF] Krajca | Parallel recursive algorithm for fca[END_REF]. In the case of data stream mining, this becomes even more important as data stream algorithms should not block their process when new data arrives in the stream.

Another gap in the application of FCA to Business Intelligence concerns visual analytics.

In FCA, the hierarchical relationships between concepts are displayed in a structure called concept lattice, which is traditionally represented by a static node-link diagram called Hasse diagram [START_REF] Ganter | Formal Concept Analysis[END_REF]. The concept lattice visualisation can be greatly enhanced by visual analytics features and interlinked with best practices from known BI visualisations. Visual analytics features may be used to manage and navigate the complex concept interrelationships, by condensing and clustering the results, and by sub-dividing and filtering data. Today, only a small number of tools are able to deal with lattice visualisation and the support for interactive analysis is limited (Carpineto and Romano, 2004a, Eklund et al., 2010[START_REF] Bach | [END_REF][START_REF] Kuznetsov | Reducing the representation complexity of lattice-based taxonomies[END_REF].

Current Challenges

Business Intelligence traditionally focuses on storing large amounts of structured data into a data warehouse and makes use of OLAP (OnLine Analytical Processing) to provide multi-dimensional analytical queries capabilities. and implicit facts can be inferred within the database using sound logical rules. The semantic analytics deals mostly with qualitative information and usually relies on graphbased visualisations.

Real-time BI is designed to provide computation results over a stream as soon as they become available. In Real-time BI, the processing runs indefinitely as the system aggregates statistics every time new data arrives in the stream. Storage of computed information is usually kept in memory allowing fast read/write of data.

Real-time FCA mining over data stream poses several theoretical and practical challenges:

Computational Complexity. Best performing FCA algorithms such as In-Close2 [START_REF] Andrews | In-close2, a high performance formal concept miner[END_REF], FCbO (Outrata and Vychodil, 2012a), Norris [START_REF] Norris | An algorithm for computing the maximal rectangles in a binary relation[END_REF] and Bordat [START_REF] Bordat | Calcul pratique du treillis de galois d'une correspondance[END_REF] have polynomial computational complexity regarding the number of objects or attributes in a dataset. In contrast, lookups in stream mining must have linear complexity at most in order to avoid the lack computational resources. To achieve low time-complexity, the stream mining algorithm should make use of techniques such as caching, pipelining and hash checking, to store and use results of previous computation.

Memory Space. A stream mining algorithm needs to guarantee that data will fit in current storage space. In worst case, mining concepts generates 2 M itemsets for Real-time User Feedback. A stream mining algorithm runs indefinitely when deployed, therefore results of the current computation should be promptly available at user's request. The real-time system should push updates to user's interface without further request. For instance, in case of monitoring systems, analysts are usually concerned with data within the most recent window of time (current day, last few hours, etc).

Interactive Visualisations. User interaction with data is closely related to its visual representation. Interactive visualisation technology displays numerous aspects of multidimensional data using interactive pictures and charts. The colour, size, shape and motion of objects represent the multidimensional aspects of the data. Card et al. (1999) defined information visualisation as "the use of computer-supported, interactive, visual representations of abstract data to amplify cognition". A good visual representation can amplify user cognition by providing more information, faster, with less cognitive effort.

BI platform vendors are currently promoting these technologies as an alternative and enrichment to traditional reporting and online analytical processing capabilities [START_REF] Andrews | Hype Cycle for Business Intelligence and Performance Management[END_REF].

The objectives of this thesis are presented in the following Section.

Goals

The goals of this thesis are two-fold: Firstly, to provide distributed scalable real-time computing of formal concepts over data stream. Real-time computation in FCA goes beyond the aggregate functions used in traditional batch processing of concepts and poses several challenges, as explained in the previous Section. In particular, highperformance computing and low memory footprint will be required to deal with large data streams.

Secondly, to develop new visual analytic features to navigate in complex concept interrelationships, by going beyond the standard approaches used for FCA hierarchical structures visualization, and by interlinking with best practices from known BI visualizations. In particular, by adding new features such as condensing and clustering the results, and sub-dividing and filtering data.

The the proposed solution is outlined in next section.

Overview of the Proposed Solution

In order to meet the first goal, a novel distributed approach for mining formal concepts over data streams is proposed. It computes and maintains closed itemsets incrementally and can return the current closed frequent itemsets in real time on user's request. The approach is comprised of several components that carry out the computation of concepts from a basic transaction, filter and transform data, store and provide analytic features to visually explore data.

To meet the second goal, a visual analytics tool for FCA is implemented, called Cubix.

The techniques implemented in Cubix allow selecting, comparing, filtering, detailing and overview of concept lattice features. Cubix's workflow allows users to carry out an analysis starting from a real data set, converting it into a formal context, simplifying the context to make it manageable, and visualizing the result as a concept lattice.

Another way of providing a different perspective of the conceptual structure is to represent it as a tree rather than as a lattice. Transforming a concept lattice into a tree can thus be useful for navigating in large lattices. In the experiments, statistically motivated criteria were explored to evaluate single parent concepts in the tree transformation process.

Our approach was tested in three real-world use cases. The three use cases are: a)

Aircraft cabin design, where new visualisations for continuous data helped engineers to quickly identify classes of comfort for passengers; b) Genes co-expression analysis using a combination of both analytics features and semantic integration; and c) Prediction of possible failures from telemetry data in real-time. This work is part of a three year FP7 funded project CUBIST 2 , which aims at uniting Semantic Technologies and Business Intelligence in order to facilitate analysis of large volumes of structured and unstructured data.

Contributions

Thesis Organisation

The remainder of this thesis is organised as follows.

Chapter searching and clustering data are also described. Finally, a new approach for transforming concept lattices into trees is presented, in order to facilitate lattice browsing in large contexts. We finish the chapter with a case study in the web tourism domain.

We introduce the use cases for our approach in Chapter 5. It describes Cubix, an analytics tool for Formal Concept Analysis that implements all the visual analytics features presented in Chapter 4. In Chapter 5 we present three use cases that demonstrate the application of the approach in real-world settings. The three use cases are: a) Aircraft cabin design, where new visualisations for continuous data helped analysts to quickly identify classes of comfort for passengers; b) Genes co-expression analysis using a combination of both analytics features and semantic integration; and c) Our distributed approach was used to the prediction of possible failures from telemetry data in realtime.

Finally, a summary of the contributions of this thesis is presented in Chapter 6, along with the conclusions and future work.

Appendices A to B contain other material that you will find helpful as you read this thesis.

Chapter 2

Background on Formal Concept Analysis

Introduction

Formal Concept Analysis (FCA) is a field of mathematics based on a formalization of the philosophical notion of concept and concept hierarchy. In a seminal paper from Rudolf Wille in 1982, "Restructuring Lattice Theory" [START_REF] Wille | Restructuring lattice theory: an approach based on hierarchies of concepts[END_REF], Wille creates the basis of FCA upon previous works on applied lattice theory and order theory that emerged in the 30's. He advocates for a formal interpretation basis that would allow a rational communication. In the popular book "Formal Concept Analysis: Foundations and Applications" [START_REF] Ganter | Formal Concept Analysis[END_REF], the following quote expresses the ambitions of FCA community:

The aim and meaning of Formal Concept Analysis as mathematical theory of concepts and concept hierarchies is to support the rational communication of humans by mathematically developing appropriate conceptual structures which can be logically activated. (p.

2)

The notion of formal conceptual logics for communication is not new, though. It draws its roots from Propositional Logics which seeks to define a formal system to assess the validity of statements while avoiding the bias of natural language. The development of the modern so-called "symbolic" logic from mid-nineteenth century is one remarkable event in paving the ground for FCA as we know it.

An important aspect of Formal Concept Analysis, in contrast to its philosophical notion, is that it relies on a context rather than reality. Therefore, the real-world meaning of a concept lattice is subject to a particular interpretation depending on the context. One implication is that concepts may not have an explicit correspondence between different contexts. Some effort has been put to make FCA constructs flexible enough to comply with different degrees of interpretation (see Fuzzy FCA Quan et al. ( 2004)).

Nowadays, FCA find its practical applications in a wide range of problems, e.g., as the basis for semantic search engines [START_REF] Ducrou | An intelligent user interface for browsing and searching mpeg-7 images using concept lattices[END_REF] and as a means of organising information based on its meaning [START_REF] Becker | The toscanaj suite for implementing conceptual information systems[END_REF]. FCA has also been used

to mine data for groups of items and their associated transactions [START_REF] Lakhal | Efficient Mining of Association Rules Based on Formal Concept Analysis[END_REF]) to identify, for example, groups of products that are frequently purchased together.

Terminology and Formalism

In the following, FCA terminology used in this thesis will be introduced. We used the same terminology employed in the original work by [START_REF] Ganter | Formal Concept Analysis[END_REF] where G denotes the set of objects (in German: Gegenstände) and M the set of attributes (in German: Merkmale). More details can be found in monographs [START_REF] Ganter | Formal Concept Analysis[END_REF] and (Carpineto and Romano, 2004b).

In classic FCA, data is converted into a binary matrix called formal context through a process involving discretisation and booleanisation. Discretisation [START_REF] Jin | Data discretization unification[END_REF] refers to the process of converting continuous data into sets of intervals or classes, e.g. age from 18 to 25, 26 to 50, etc, whereas data booleanisation [START_REF] Imberman | Finding association rules from quantitative data using data booleanization[END_REF] involves creating a binary relation with pairs of attribute-values for each attribute's value. This process is known as "Scaling" and can be seen as a type of binned aggregation.

In mathematical terms, a formal context is defined as a triple K = (G, M, I), with G being a set of objects, M a set of attributes and I a relation defined between G and M. The relation I is understood to be a subset of the cross product between the sets it relates, so I ⊆ G × M . If an object g has an attribute m, then g ∈ G relates to m by I, so we write (g, m) ∈ I, or gIm.

Definition (Derivation Operators). For a subset of objects A ⊆ G, a derivation operator ↑ is defined to obtain the set of attributes, common to the objects in A, as follows:

A ↑ = {m ∈ M | ∀g ∈ A : gIm}
In a similar manner, for a subset of attributes B ⊆ M, the derivation operator ↓ is defined to obtain the set of objects, common to the attributes in B, as follows: [START_REF] Ganter | Formal Concept Analysis[END_REF]. We may use the single quote symbol ' as a replacement for ↑ and ↓.

B ↓ = {g ∈ G | ∀m ∈ B : gIm} Operators ↑: 2 X -→ 2 Y and ↓: 2 Y -→ 2 X form the so-called Galois connection (Ganter
The double derivation operator ↑↓ (") is a closure operator. The images of a closure operator are closed sets.

Definition (Formal Concept

). A pair A, B is a formal concept in a given formal context (G, M, I) only if A ⊆ G, B ⊆ M, A ↑ = B and B ↓ = A.
The set A is the extent of the concept and the set B is the intent of the concept. A formal concept is, therefore, a closed set of object/attribute relations, in that its extension contains all objects that have the attributes in its intension, and the intension contains all attributes shared by the objects in its extension.1 The Table 2.1 shows an example of a formal context of some living organisms in the water.

For example, w.r.t. the context in Table 2.1, {has limbs}' = {bream, frog, dog} is not a formal concept because {bream, frog, dog}' = {needs water to live, can move, has limbs}. Notice that formal concepts forms maximal rectangles in the incidence matrix.

A partial order ≤ can be established between concepts iff :

A, B ≤ C, D ←→ A, B ⊆ C, D
× × bream × × × × frog × × × × × dog × × × × × water weeds × × × × reed × × × × × bean × × × × corn × × × ×
The set K = (G, M, I) together with ≤ form a complete lattice whose structure is described by the Main Theorem of Formal Concept Analysis [START_REF] Ganter | Formal Concept Analysis[END_REF].

Property (Concept Lattice). Let C K be a set with all concepts in context K and L = C K , ≤ K be a complete lattice where the supremum and infimum are defined respectively as:

n i=1 (A i , B i ) = (( n i=1 A i ) ′′ , n i=1 B i ) and n i=1 (A i , B i ) = (( n i=1 A i , ( n i=1 B i ) ′′ )

Concept Lattices

As mentioned above, FCA analysis produces lattices, usually represented as layered directed acyclic graph graphs, named Hasse diagrams illustrating the groupings of objects described by common attributes. Hasse diagrams display the partially ordered sets (posets) between concepts in a hierarchical fashion, where each concept may have several parent concepts. The following concept lattice about organisms that live on the water was generated by the formal context in Table 2.1 (Figure 2.1). The partial order among concepts of the lattice is materialized through the generalization and specialization relationships. For instance, the concept representing the set of animals that "has limbs" (middle left) is more specific than the concept "can move" (upper left), in other words, all animals that "has limbs" can move, but not all animals that "can move" has limbs, which is the case of "fish leech"2 . This partial order provides different levels of abstraction and native navigation links from a given concept. Concept lattices in particular suffer from considerable edge crossings, especially if the number of concepts exceeds a few dozen as is the case in more real word applications [START_REF] Kuznetsov | Reducing the representation complexity of lattice-based taxonomies[END_REF], which leads to reduced graph readability and aesthetics [START_REF] Ware | Cognitive measurements of graph aesthetics[END_REF] (Figure 2.2).

To reduce the complexity of lattices, simplified diagrams can be produced by condensing or clustering concepts according to similarity [START_REF] Gerd | Computing iceberg concept lattices with titanic[END_REF]. Visualisations can also be restricted to portions of the data [START_REF] Ducrou | An intelligent user interface for browsing and searching mpeg-7 images using concept lattices[END_REF], and concept size reduction is possible by incorporating conditions into the data mining process [START_REF] Zaki | Efficient algorithms for mining closed itemsets and their lattice structure[END_REF]. Finally, conceptual measures can be applied to identify the most relevant concepts and filter outliers (Le Grand et al., 2009).

To deal specifically with the visual complexity of Hasse diagrams, several approaches allow users to dynamically explore and reveal specific parts of the diagram, using visual query languages [START_REF] Blau | A Visual Language for Querying and Updating Graphs[END_REF][START_REF] Cruz | A graphical query language supporting recursion[END_REF][START_REF] Consens | Hy+: a hygraph-based query and visualization system[END_REF].

However these techniques do not provide a clear view of the entire lattice.

Other FCA visualisation approaches map the distances between concepts to visual variables, in order to highlight patterns. For example in Michel Soto (2009) similar concepts are represented as similarly coloured pixels placed in the 2D space along a Peano-Hilbert curve, so that similar concepts are placed close to each other. Nevertheless, in these representations detailed relationships between concepts are lost.

Finally, systems often provide users with hybrid/combined lattice visualisation, e.g.

showing both a general Hasse diagram and a tag cloud for representing the neighbours of a specific concept (for a review see [START_REF] Eklund | A survey of hybrid representations of concept lattices[END_REF]).

There are many algorithms for drawing such lattices, additive-line diagrams, hybrid layouts and even 3D layouts have been proposed. In Chapter 4 we will discuss them in detail.

Overview of FCA algorithms

A naive algorithm for computing concepts would check if every combination of subsets B ⊆ M is a closed itemset. This would require an exponential number of lookups in a list that may have exponential size 3 . Instead, FCA algorithms typically employ some heuristic to verify if a given subset is worth of computation. This can be done for example, using extra canonicity tests, defining an ordering between subsets, using data structures for storing previous results, etc.

The algorithms in FCA are basically divided in three classes: The batch algorithms, which procedure takes into account the entire context for batch processing; Incremental algorithms, which build the concept lattice from each object in the context and update the structure as a new object is added; and the assembling algorithms derive new concepts from previously calculated subsets (for a survey see [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF]). In the following sections, we describe the mainstream algorithms in each category.

Batch Algorithms

Batch algorithms generate sets of concepts from scratch, in a top-down fashion (from minimal to maximal intents) or vice-versa. Bernhard Ganter [START_REF] Ganter | Two basic algorithms in concept analysis[END_REF] introduced the idea of defining a lexicographic order for subsets in order to avoid multiple computations of the same concept. A lexicographic order relation A B exists if there is some lexically-ordered element e ∈ A that does not belong to B. For example, {a, c, d} comes before {a, c, e} because d is the smallest item that belongs to A but not B. This is a common technique among FCA algorithms.

Ganter's NextClosure algorithm [START_REF] Ganter | Two basic algorithms in concept analysis[END_REF] works by finding closures incrementally from a lexicographically ordered group of items. The generation of a concept is considered canonical if its extent contains no object preceding the current object. The procedure is illustrated in Algorithm 1.

NextClosure takes as input a subset B ⊆ M of the lexicographic next closure set. It starts from the last (lexicographic) attribute (line 4) and checks if attribute is not already in 3 For a set with N elements, there exists 2 N possible subsets (powerset). Another class of algorithms has a slightly different way of checking concepts: the Closeby-One (CbO) familly of algorithms [START_REF] Krajca | Advances in algorithms based on cbo[END_REF]. It is possible to determine if a concept is new by efficiently examining its canonicity. The original CbO procedure is illustrated in Algorithm 2.

i ←-i -1 if not B[i] then D ←-B ∪ {i} C ←-D ′′ if C \ B contains no element < i then N extClosure(C)
The procedure takes as input a formal concept A, B and an attribute y ∈ M (first attribute to be processed) as its arguments. The procedure recursively descends through the space of formal concepts, beginning with A, B = ∅ ′ , ∅ ′′ . In line 3, the algorithm checks the halting condition: when the least formal concept has been reached or y > |M |, i.e., there are no more remaining attributes to be processed. If the halting condition test fails, the algorithm goes through all attributes j ∈ Y such that j >= y and j is not in An improvement over the original CbO was proposed in (Outrata and Vychodil, 2012a) called Fast Close-by-One or FCbO. The algorithm used an extra canonicity test to avoid redundant computations. The result is equivalent to a pruned CBo recursion tree where the number of comparisons is drastically reduced.

if B = M or y > |M | then return; end for j ← y to |M | do if j / ∈ B then C ←-A ∩ {j} ′ D ←-C ′ if B ∩ M j = D < ∩M j then CloseByOne(< C, D >, j +
The new canonicity test takes advantage of the fact that the failure in the canonicity test in line 11 of CbOs algorithm can be propagated to sub-nodes and thus eliminating the need of extra computation. Because this information must be propagated in the top-down direction, from the root node of the call tree to the leaves, the algorithm uses a breath-first search strategy as opposed to the recursive calls of the original CbO. The algorithm and proof of its correctness can be found in (Outrata and Vychodil, 2012a).

Notice that in the worst case, FCbO collapses into CbO (all branches are computed)

with an additional linear time-delay overhead introduced by the new canonicity test.

In this scenario (worst case) FCbO has polynomial time-delay O(|G||M | 3 ). However, heuristically it performs better than the previously mentioned algorithms because the pruning happens frequently (A performance comparison can be found in [START_REF] Outrata | Fast algorithm for computing fixpoints of galois connections induced by object-attribute relational data[END_REF]).

Parallel and distributed versions of FCbO were proposed [START_REF] Krajca | Parallel recursive algorithm for fca[END_REF]. We will discuss them in Section 2.5.4.

Another variant of CbO is the In-Close algorithm [START_REF] Andrews | In-close, a fast algorithm for computing formal concepts[END_REF]. It uses incremental closure and matrix searching to quickly compute all formal concepts in a formal context.

While in CbO the closure is computed at each iteration, In-Close on the other hand, completes closure incrementally and only once per concept, as it iterates across the attributes. As a result the test of canonicity requires iteration over a relatively small portion of the formal context.

A new version of In-Close was proposed in [START_REF] Andrews | In-close2, a high performance formal concept miner[END_REF]. In In-Close2, attributes tested in parents are propagated down in the tree, so that during the closure of a child concept these attributes do not need to be tested for inclusion. In-Close2 also reorders the context table in a way that maximal rectangles formed by the incidence relation are grouped for performance gain. Experiments show that in average, In-Close2 outperforms FCbO by a small margin [START_REF] Andrews | In-close2, a high performance formal concept miner[END_REF].

Whilst batch FCA algorithms can perform better in average than the other classes of algorithms, it requires several lookups in the entire dataset. Any change in the context table means that the algorithm should re-compute all items again. As we will see further in this chapter, this become an issue as a growing number of applications have dynamic datasets.

Incremental Algorithms

The incremental paradigm aims at carrying efficiently the required changes of the current result leading to its updated version. The incremental update of an existing lattice L starts from a single object o i ∈ G, and progressively incorporates any new object o i+1 upon its arrival in the lattice, carrying out a set of structural updates. A good incremental algorithm will make the necessary changes at a minimal cost.

An incremental version of the CbO algorithm is presented in [START_REF] Norris | An algorithm for computing the maximal rectangles in a binary relation[END_REF], commonly referred to as Norris' algorithm.

In Godin's algorithm [START_REF] Godin | Incremental concept formation algorithms based on galois (concept) lattices[END_REF] To decrease the number of comparisons, the algorithm uses a hash with the intent's cardinality in its key and a corresponding list of subsets with that cardinality (line 14).

The execution goes through the subsets with lower cardinality, checking if a concept needs to be updated and carrying out the changes (lines 17-30).

In [START_REF] Van Der Merwe | Addintent: A new incremental algorithm for constructing concept lattices[END_REF] Particularly interesting for dynamic contexts, the incremental algorithms are more suitable to stream processing because updating the concept lattice is less computationally expensive than building the concept lattice from scratch for each transaction in the stream. As we demonstrate in Chapter 3, we implemented a distributed algorithm FCAStream which draws principles from incremental algorithms in FCA.

Assembling Algorithms

The Assembly algorithms are an evolution of incremental algorithms in that they assemble lattices from partial structures based on context concatenation upon a shared object Algorithm 3: Godin's incremental algorithm Data: A new object o ∈ G and its corresponding attributes B ⊆ M . begin [START_REF] Valtchev | Building concept (galois) lattices from parts: Generalizing the incremental methods[END_REF]. It divides a formal context into parts (vertical or horizontal split) and then calculates the concept lattice for each corresponding part. The partial lattices are finally assembled into a single one. One advantage of this approach is that the computation of partial lattices can be done in parallel, thus making this approach one of the most scalable among all existing FCA algorithms.

/* Concept X, Y is the top concept in the lattice */ X, Y = sup(L) if X, Y = ∅, ∅ then replace X, Y by {o}, B else if not B ⊆ Y then if X = ∅ then Y ∪ B else create C, D ←-∅, (Y ∪ B) add link X, Y → C, D /*

General Remarks on FCA Algorithm's Performance

The behaviour of an FCA algorithm may vary significantly depending on a number of factors including the relative sizes of G and M , the size of I, and the density of the context, i.e., the size of I relative to the product |G||M | [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF].

Experimental results of [START_REF] Kuznetsov | Comparing performance of algorithms for generating concept lattices[END_REF] highlight Norris (incremental),

CloseByOne and NextClosure (both bottom up) algorithms as the best algorithms when the context is dense and large, whereas Godin's algorithm should be used for small and sparse contexts.

Evidently, the construction of the lattice diagram graph requires an additional computational effort. Hence, algorithms generating only the concept set are in general faster than those that carry the ordering and linking of concepts.

Most FCA algorithms employ techniques to avoid repetitive generation of the same concept. In this task, choosing an adequate data structure is essential. For instance Bordat [START_REF] Bordat | Calcul pratique du treillis de galois d'une correspondance[END_REF]) uses a tree structure to store previously computed concepts and allow efficient search. Godin's algorithm (Algorithm 3) uses a hash based on intent cardinality.

Subsets of attributes can be represented by a bit-array where each bit corresponds to an attribute in lexicographic order. Set operations can be replaced by the corresponding logical operations, e.g. A ∩ B = bit array(A) & bit array(B).

For example, if M = {a < b < c < d < e < f }, the subset S = {a, c, d, e} will be written as: Some algorithms for FCA achieve better performance if attributes are processed in a particular order. The overhead of physically sorting the context is outweighed by the saving in memory load. For example, In-Close2 [START_REF] Andrews | In-close2, a high performance formal concept miner[END_REF] sorts context columns in ascending order of support. This allows quick memory retrieval according to the spatial locality principle of memory. It also sorts rows in the context to reduce the Hamming Distance, i.e., the number of positions in which the corresponding symbols are different in a string or, in their case, a bit-array. Experiments show that these techniques improve the algorithm's efficiency over 33% for large contexts [START_REF] Andrews | In-close2, a high performance formal concept miner[END_REF].

Current Issues in FCA for Big Data Analysis

In this section we discuss the challenges current FCA algorithms face in the light of big data analysis, when the input data exceeds hundreds of thousands objects/attributes.

Size and Complexity of Data

Since the number of concepts can grow dramatically with the number of attributes and objects, reducing the number of concepts generated has become a major challenge in the FCA community [START_REF] Priss | Lattice-based information retrieval[END_REF][START_REF] Gerd | Computing iceberg concept lattices with titanic[END_REF][START_REF] Carpineto | Using concept lattices for text retrieval and mining[END_REF]. Dataintensive applications like biogenetics, space telemetry data and real-time monitoring generate massive, noisy data, impractical to handle with current FCA representations.

Density and noise of a context are factors that increase the number of formal concepts [START_REF] Andrews | Analysis of large data sets using formal concept lattices[END_REF]. In this case, relevance measures such as stability and support can minimise input data needed for the computation of concept lattices [START_REF] Godin | Experimental comparison of navigation in a galois lattice with conventional information retrieval methods[END_REF].

The problem of reduction in FCA is analogous to the dimensionality reduction in data mining. The assumption is that not all variables or dimensions are important or that a few set of variables are significant for understanding the phenomena of interest. However, in FCA, concepts add a new challenge: how to remove information while preserving some of the most essential conceptual features?

Reduction methods are basically divided into two strategies: those that group similar objects or concepts, and those that act by removing irrelevant concepts. Reduction can take place in the scaling phase, for instance, reducing the columns with low support or through the creation of sub-contexts [START_REF] Andrews | In-close2, a high performance formal concept miner[END_REF], during the concept mining phase, e.g. keeping concepts with enough support [START_REF] Gerd | Computing iceberg concept lattices with titanic[END_REF], or in the concept lattice, through visual cluttering reduction techniques (Michel Soto, 2009).

An intuitive solution for reducing the formal context is to select sub-contexts or restrict the scaling of data to only attributes and values of interest [START_REF] Cole | Scalability in formal concept analysis[END_REF]. For instance, it is possible to specify larger intervals for a continuous attribute such as 'date';

or group together similar objects and attributes. [START_REF] Kumar | Short communication: Concept lattice reduction using fuzzy k-means clustering[END_REF] use Fuzzy K-Means (FKM) clustering to collapse certain rows of a formal context, introducing equivalence relations between certain nodes of the object-attribute lattice. Another intuitive idea is to filter out irrelevant objects and/or attributes below a certain frequency threshold, thus simplifying the context table [START_REF] Gerd | Computing iceberg concept lattices with titanic[END_REF].

Many reduction methods are based on the factorisation of the binary table into some canonical form, thereby simplifying the formal context. A direct application of Singular

Value Decomposition (SVD) and Non-negative Matrix Factorisation was done to reduce formal contexts in [START_REF] Snsel | On concept lattices and implication bases from reduced contexts[END_REF]. Although this method is able to 'compress' the formal context, it does not take into consideration any conceptual heuristic and it is not clear to the user which changes were made to the original context. On the other hand, the number of nodes and edges of a lattice could be significantly reduced by establishing an equivalence relationship between certain nodes of the lattice with aid of matrix factorisation methods.

Cheung and Vogel [START_REF] Cheung | Complexity reduction in lattice-based information retrieval[END_REF] introduce the notions of 'congruence ′ and 'quotient ′ that use SVD to define the equivalence relation for the construction of quotient lattices. The resulting context is a merge of rows or columns that maintains the homomorphism in a simplified concept lattice. These methods are very sensible to noise, meaning that minor differences in data may lead to highly biased contexts during the factorisation process. Another problem is that the computational complexity of SVD methods makes it impractical for large matrices (Aswani [START_REF] Kumar | Short communication: Concept lattice reduction using fuzzy k-means clustering[END_REF].

Alternatively, reduction can happen at concept level, during or after concepts computation. The selection of relevant concepts and groupings can be performed by the algorithm that computes concepts. For instance, the 'Iceberg' lattice approach [START_REF] Gerd | Computing iceberg concept lattices with titanic[END_REF] removes concepts below a certain frequency threshold, i.e. minimum support. One problem with the support is that it tends to select the most generic concepts as they are more likely to contain more objects. The stability index measures the proportion of subsets of objects of a given concept whose derivation is equal to the intent of this concept. In other words, stability indicates the probability of preserving a concept intent while removing some objects of its extent [START_REF] Kuznetsov | Reducing the representation complexity of lattice-based taxonomies[END_REF].

The notion of clustering is well known in the data-mining domain. It is a process of grouping together entities based on their similarities. Clustering of concepts (as opposed to clustering of objects or attributes) can be useful to facilitate the browsing of concepts and to identify zones of interest. Some conceptual similarity measures can be based on: a) the concept lattice topology (e.g. counting the number of links between two concepts); b) the intent/extent similarity (e.g. applying Jaccard ) or c) calculating the confidence between pairs of concepts.

Scaling

FCA method is usually limited by the rigidity of its input format (binary data). Some works have proposed to extend it to complex data [START_REF] Ferré | A logical generalization of formal concept analysis[END_REF][START_REF] Ganter | Pattern structures and their projections[END_REF][START_REF] Messai | Many-valued concept lattices for conceptual clustering and information retrieval[END_REF], among them the Similarity-based Formal Concept Analysis (SFCA) method which considers similarity to directly classify non-binary data into lattice structures called Many-Valued Concept Lattices (MV lattices) [START_REF] Messai | Many-valued concept lattices for conceptual clustering and information retrieval[END_REF]. Besides extending FCA to complex data and avoiding loss of information in transformation phases, the SFCA classification process produces MV lattices with different granularity levels which allows progressive data exploration [START_REF] Messai | Using domain knowledge to guide lattice-based complex data exploration[END_REF].

Another approach consists in transforming continuous-valued formal context into manyvalued formal context first, then on the basis of many-valued formal context, finding equivalence classes for the continuous-value contexts [START_REF] Ganter | A formal concept analysis approach to rough data tables[END_REF].

Scaling in a data stream is dynamic, that is, the process of scaling occurs as new data arrives in the stream. For example, in many cases one cannot know the distribution and possible maximal and minimal values in case of continuous attributes. A temperature sensor can transmit streams of data with current temperature, but it is not known

× × × b × × × × × c × × d × × 1 2 3 4 5 6 a × × × b × × × × c × × d a priori
whether a given temperature is the possible maximum. Because of this, the minimum and maximum values need to be maintained and eventually updated for each incoming data, thus requiring the scaling process to restart.

Noisy and Missing Data

Quite often, a data set contains outliers or missing data. These exceptions can drastically increase the number of concepts generated [START_REF] Andrews | Analysis of large data sets using formal concept lattices[END_REF][START_REF] Pensa | Towards fault-tolerant formal concept analysis[END_REF][START_REF] Boulicaut | Free-Sets: a Condensed Representation of Boolean Data for the Approximation of Frequency Queries[END_REF]. Noise is most common in real data such as surveys, logs, genes expression, when values can be biased, missing or some mistake was introduced in the data. Table 2.2 illustrates a noisy and a 'quiet' data set [START_REF] Andrews | Analysis of large data sets using formal concept lattices[END_REF].

Reduction of formal contexts can be achieved by removing noise or outliers from the data. The notion of fault-tolerant FCA5 was introduced by Pensa and Boulicaut in [START_REF] Pensa | Towards fault-tolerant formal concept analysis[END_REF] to allow a certain number of 'exceptions' to occur in a concept. Based on the idea of "free-sets" [START_REF] Boulicaut | Free-Sets: a Condensed Representation of Boolean Data for the Approximation of Frequency Queries[END_REF], the method seeks to find maximal rectangles of true values in the context bounded by δ exceptions.

Andrews and Orphanides (2010) proposed a method to reduce noise based on mining a context for concepts that satisfy a minimum support (and/or stability) and then re-writing the context using only those concepts. One advantage of their approach compared to the "truncation" of formal context is that it preserves the concepts essential features at a cost of computing concepts twice.

Parallel and Distributed Computation of Concepts

Most existing FCA algorithms were designed to work on small binary tables, with less than hundreds objects/attributes stored in the memory of a single computer. Among the few parallel and distributed algorithms, a parallel variant of FCbO was proposed, called Parallel FCbO [START_REF] Krajca | Parallel recursive algorithm for fca[END_REF]. The authors later proposed a distributed map-reduce version of the FCbO algorithm [START_REF] Krajca | Distributed algorithm for computing formal concepts using map-reduce framework[END_REF]. The algorithm offer insights on the algorithm design. Surveys on the issues related to the distributed frequent itemset mining can be found in [START_REF] Zaki | Parallel and distributed association mining: a survey[END_REF] and (Kumar et al., 2010).

Data Stream Processing

High memory and computational requirement of FCA based algorithms prohibits their use in data stream environment. Each node of the concept lattice stores the extent (set of transactions) along with the intent (a closed itemset) which contributes to high memory usage. Furthermore, processing of a new transaction involves computation of the intersection of its extent with the extent of different nodes in the lattice, making it computationally expensive [START_REF] Gupta | Mining closed itemsets in data stream using formal concept analysis[END_REF].

Visualisation of Large Concept Lattices

The Hasse diagram used to represent FCA is well suitable for a small number of concepts. When it expands to a few dozens of concepts, as is the case in more real word applications, its comprehension becomes compromised. This is an issue in relation to the amount of data displayed, as well as graph readability and aesthetics (Melo et al., 2011a).

In spite of this, concept lattice visualisation saw a marginal improvement over several To deal specifically with the visual complexity of Hasse diagrams, several approaches allow users to dynamically explore and reveal specific parts of the diagram, using visual query languages [START_REF] Blau | A Visual Language for Querying and Updating Graphs[END_REF][START_REF] Cruz | A graphical query language supporting recursion[END_REF]. Layout algorithms like the additive lines diagram [START_REF] Ganter | Formal Concept Analysis[END_REF] have the advantage of being configurable through the choice of the representation set, and the technique produces a high number of parallel edges, which in turn improves readability. Nested lines diagrams [START_REF] Kuznetsov | Algorithms for the construction of concept lattices and their diagram graphs[END_REF] have been proposed to display the direct product of two concept lattices, however, they are not always simple to interpret.

Visual Analytics Features

Visual analytics techniques are often used in Business Intelligence to synthesize information and provide insights in the decision making process [START_REF] Daniel | Visual analytics: Scope and challenges[END_REF]. Current FCA tools lack interactive features that allow selecting, filtering, searching and transforming conceptual data. Recent studies have highlighted that the visualisation of concept lattices can be greatly enhanced with aid of visual analytics techniques.

To cite a few examples, [START_REF] Priss | Lattice-based information retrieval[END_REF] use the lattice representation to show the concepts hierarchy in thesauri. Each concept is viewed as a facet in an information retrieval system. In [START_REF] Akand | A Visual Analytics Approach to Augmenting Formal Concepts with Relational Background Knowledge in a Biological Domain[END_REF] authors propose an algorithm that generates a browse-able concept lattice designed for biology applications. [START_REF] Ducrou | Fca-based browsing and searching of a collection of images[END_REF] introduce Im-ageSleuth, a tool for browsing and searching annotated collections of images. It allows drill-up and drill-down the results and it suggests similar concepts if none was retrieved by the user's query. In [START_REF] Villerd | Using concept lattices for visual navigation assistance in large databases: Application to a pantent database[END_REF] In common with these studies is that they are application-specific and provide few analytic features, mostly based on drawing options and attribute/object selection. There is little or no emphasis on the knowledge discovery beyond what the concept lattice inherently provides. In this thesis, we focus on the combination of techniques to support analytical reasoning and insights based on concept lattices.

Chapter Summary

This chapter introduced FCA, its formal definitions and the terminology that will be used throughout this thesis. We investigated the mainstream algorithms in the FCA literature: batch algorithms, incremental algorithms and assembling algorithms. Each algorithm has strengths and weaknesses, and its success will largely depend on the constraints imposed by the application domain, such as dynamic data, availability of resources, concept lattice visualisation, and so on. We listed the main issues that current FCA methods face when applied to Big Data analysis. To reduce the complexity of lattices simplified diagrams can be produced by condensing or clustering concepts. Visualisations can also be restricted to portions of the data and concept size reduction is possible by incorporating conditions into the data mining process, such as minimum support and stability. Conceptual measures can be applied to identify the most relevant concepts and filter outliers.

There is not a single all-encompassing method to solve all the mentioned problems. In general, combined approaches are required to tackle with domain specific issues. We therefore conclude that a) Incremental FCA algorithms are more suitable to handle stream data; b) There are few FCA algorithms able to run in a parallel or distributed environment, and c) Synthetic and meaningful representations for concept lattices are needed.

Chapter 3

Real-time Distributed

Computation of Formal Concepts

Introduction

A data stream is an sequence of items that arrive in timely order. As opposed to data in static databases, data streams are unbounded, infinite and data distribution may vary with time [START_REF] Chi | Catch the moment: maintaining closed frequent itemsets over a data stream sliding window[END_REF]. In BI, stream concept analysis help users both qualitatively (co-occurrence among items, classes and hierarchies) and quantitatively (number of co-occurrences, strength of the implication, distribution of sub-items, etc).

Computing formal concepts can be seen as computing the closed frequent itemsets of their intents. Frequent itemsets can also be used to derive Association Rules, which provide a valuable information on how the frequent patterns are related to each other.

There is a growing number of applications in association rule stream mining, for example, to predict frequency estimation of Internet packet streams [START_REF] Demaine | Frequency estimation of internet packet streams with limited space[END_REF]; to discover alarming incidents from data streams [START_REF] Cai | Maids: mining alarming incidents from data streams[END_REF]; or to estimate missing data in sensor networks [START_REF] Halatchev | Estimating missing values in related sensor data streams[END_REF].

Although the field of data stream mining is being heavily investigated, there is still a lack of a holistic approach for mining closed itemsets from very large data streams. The bottleneck arises due to the limit in computational resources for stream mining, while most algorithms cannot run in parallel (Jiang and Gruenwald, 2006a).

This chapter addresses this problem by employing a divide-and-conquer approach: big problems are split into smaller parts that can be computed concurrently and partial results are merged at the end of the computation. This technique has been proven very effective to process large volumes of data when it is associated with a distributed environment, such as Hadoop1 .

A distributed environment brings extra challenges to the computation of formal concepts, for example, it must guarantee that data shared across nodes are consistent.

Another issue is that the number of signals transmitted among nodes should be the minimum possible to prevent network overflow and latency, thus caching and pipe-lining of operations are desirable.

Our distributed approach is not limited to the concept miner algorithm. We propose an architecture covering the entire data stream mining overflow, from data filtering and transformation, to closed itemset processing, and real-time visualisation.

The remainder of the chapter is organised as follows. A review of the particular issues of data stream mining is provided in Section 3.2. Section 3.3 formalises the terminology and presents a review of the state of the art on frequent itemset mining algorithms. Our approach for distributed computation of concepts is presented in Section 3.4 along with conclusions in Section 3.5.

General Issues in Mining Data Streams

The primary goal of data stream mining is to compute all subsets of items, hereafter called "transactions", which occur in at least a fraction of the stream. A data stream is a unbounded sequence of tuples continuously generated at a rapid rate. In contrast with batch algorithms, stream mining algorithms should satisfy the requirements listed below.

Each transaction should take at most once to look up a data stream, that means that stream mining algorithms should have linear time O(N ) where N is the size of the stream. Anything above this constraint may fall into a ever increasing, unmanageable computational cost (Jiang and Gruenwald, 2006a).

Another issue is to maintain memory usage within a limited range, although new data elements are continuously arriving from a data stream. This indicates that, at some point, some data must be discarded. As we will see later, this is a non-trivial task and may affect either the correctness or completeness (or both) of the stream mining algorithm.

The stream mining algorithm should use the result of previous computation and make the changes incrementally at minimum cost. This is usually done using a synopsis data structure, typically a prefix-tree, to store and maintain itemsets and frequency count in a compact way.

Finally, a stream mining algorithm runs indefinitely when executed. However, the realtime analysis of a data stream requires that results be promptly available when requested, therefore partial results should be provided.

Data Processing Model

In most cases, it is not practical to store and compute the entire data from the stream.

Instead, most algorithms select portions of the stream that should be processed to mine itemsets, while insignificant data is discarded. Not all itemsets have equal importance in the mining of new itemsets. For example, an itemset that has much less support than a predefined minimum support is not necessarily monitored since it cannot be a frequent itemset in the near future, nor can it generate closed itemsets. Similarly, old itemsets may not me as relevant as new itemsets because users are, in general, interested in the recent itemsets. There are three main processing model to cope with this problem: the landmark model, the damped model and sliding window model.

Landmark Model

The Landmark model mines all frequent itemsets over the entire history of stream data from a specific time point called landmark to the present (Figure 3.1). This is the case of most batch itemset mining algorithms, such as FP-Growth (Han et al., 2000a) and CHARM [START_REF] Zaki | Charm: An efficient algorithm for closed association rule mining[END_REF] when used to mine streams. Notice that, because it is an accumulative model, the required amount of memory grows with the number of transactions. As a new transaction arrives it is added to the processing.

Damped Model

The Damped model mines frequent itemsets in stream data where each transaction has a weight, which decreases over time causing recent transactions to be more important than previous ones (Figure 3.2). A decay function is typically employed to assign weights to transactions. For example, in [START_REF] Gupta | Mining closed itemsets in data stream using formal concept analysis[END_REF], the decay function affects the support count of the transaction, with older transactions contributing less.

In contrast with the Landmark model, the Damped model may have newer transactions out of the window if its support, combined with the decay function, does not reach the minimum threshold (e.g. Figure 3.2 time span 3). This is a remarkable feature of this model vis-à-vis the Sliding Window model.

Sliding Window Model

The A strong feature in favour of this model is that it guarantees that data can fit into the memory, because the number of transactions to manage is constrained by the size of the sliding window. Nevertheless, all transactions in the window need to be maintained in order to remove their effects on the current mining results when they are out of range of the sliding window. This model is used by many algorithms [START_REF] Chi | Catch the moment: maintaining closed frequent itemsets over a data stream sliding window[END_REF][START_REF] Hyuk | Finding recent frequent itemsets adaptively over online data streams[END_REF][START_REF] Li | Incremental updates of closed frequent itemsets over continuous data streams[END_REF] including the algorithm proposed in this thesis.

Data Structure

Having an appropriate data structure is fundamental for handling large amounts of data streams coming continuously. An inefficient data structure will largely affect the mining process, ultimately leading to a bottleneck in the system, if the stream rate is greater than what the data structure is able to handle in linear time.

One of the tasks of the data structure is to keep an overall state of the mining process in order to use the results of previous computation to make changes incrementally. Besides managing itemsets, the data structure should keep the state like frequency count, itemset statuses, transactions in the current window, etc. Frequent Itemset mining algorithms typically employ some variant of a Prefix-tree (also known as Trie) to store transactions and itemsets. A prefix-tree can handle insertions and searching operations in linear time in worst case (O(M ) where M is the size of the transaction).

For example, in (Chang and [START_REF] Hyuk | Finding recent frequent itemsets adaptively over online data streams[END_REF], the different combinations of items that appear in each transaction are maintained in a prefix-tree lattice structure. A node in the lattice contains an item and it denotes an itemset composed of items that are in the nodes of its path from the root. In (Manku and Motwani, 2002a) a lattice data structure is used to store itemsets, approximate frequencies of itemsets, and maximum possible errors in the approximate frequencies. In some cases more than one data structure is necessary. For example, Chi et. al. [START_REF] Chi | Catch the moment: maintaining closed frequent itemsets over a data stream sliding window[END_REF] propose a variant of a prefix tree called Closed Enumeration Tree (CET) to store closed frequent itemsets, while another prefix-tree, FP-Tree is used to store all transactions. Additionally, a hashset is used to store information about closed itemsets for checking in constant time (O(1)). We will describe some of these data structures in detail in the following sections.

Frequent Itemsets Mining Over Stream

Preliminaries

Before proceeding, let us formalise our terminology to avoid ambiguity. Let M = {i 1 , i 2 , . . . , i n } be a set of n elements, called items. A subset Y ⊆ M is called an itemset. Each transaction I is a set of items in M . Given a set of transactions T , the support of an itemset I is the number of transactions that contain I.

We assume that there is a lexicographical order among the items in M and we use X ≺ Y to denote that itemset I is lexicographically smaller than item J. For the sake of clarity, we may represent an itemset e.g. {A, B, C} as ABC, given A ≺ B ≺ C.

Formal concepts are mathematically defined as closed itemsets for their intents. Although both terms differ in their philosophy 2 , we may use both terms interchangeably.

Recalling the definition of formal concept in Section 2.2, let T and Y be subsets of all the transactions and items appearing in a data stream D, respectively. A closed itemset can be defined by two operators, ↓ and ↑ where T ↑ = {j ∈ M |∀t ∈ T, j ∈ t} and 2 FCA has a particular emphasis on the dual relationship of objects and attributes.

Y ↓ = {t ∈ D|∀i ∈ Y, i ∈ t}. An itemset X is said to be closed if and only if ↑: 2 T -→ 2 Y
and ↓: 2 Y -→ 2 T where the composite function ↑↓ (") is called a closure operator.

Overview on Algorithms for Frequent Itemsets Mining

Frequent Itemsets Mining (FIM) over streams are not fundamentally different from those processing relational data. Indeed, most stream mining algorithms are variants of nonstream ones. Nevertheless, as explained in Section 3.2, the applicability of the former type of algorithms may be compromised for stream processing. For example, FIM algorithms that require several scans over the data may fall into exponential computational complexity as opposed to incremental ones, which build a intermediary structure and carry only the needed changes as new data arrives. The frequent itemsets mining algorithms can be either deterministic or approximative, i.e., itemsets are discovered if they score higher than some probability threshold. We are interested in the deterministic class of algorithms for this study. This section provides an overview of the most relevant algorithms, starting from frequent itemset mining algorithms for static data, closed itemsets mining, stream algorithms and lastly, closed itemsets mining algorithms for stream data. A timeline with the algorithms is provided in Appendix A.

Mining Frequent Itemsets with Candidate Generation: The Apriori algorithm

One of the most popular frequent itemset mining algorithm is the Apriori algorithm [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF]. It uses a twofold approach to generate candidate itemsets and test if they are frequent. As intuition suggests, generating all possible candidate itemsets is a costly operation. The testing phase compare candidate's support with a given threshold.

Although the Apriori algorithm suffers from considerable overhead by generating potentially useless candidates, it is widely regarded as a pioneer algorithm for itemset mining and its simplicity serves as a good pedagogic example to contrast with other approaches.

Mining Frequent Itemsets without Candidate Generation

Another branch of frequent itemsets mining algorithms correspond to those without candidate itemset generation. The widely known algorithm FP-Growth (Han et al., 2000a) is also a two steps approach: First it builds a compact data structure called the FP-Tree, which is in fact a prefix tree. Then it extracts frequent itemsets directly from the FP-tree. An example of a FP-Tree is as follows. Nodes in the FP-Tree correspond to items and have a counter. FP-Growth reads 1 transaction at a time and maps it to a path in the tree (Figure 3.4).

A lexicographical ordering is applied to the itemsets, so paths can overlap when transactions share items (when they have the same prefix), in this case, counters are incremented. Pointers are maintained between nodes containing the same item, creating singly linked lists (dotted lines). The more paths that overlap, the higher the compression in this structure. This allows FP-tree to fit in memory, given a number of itemsets.

It is worth noting that in the worst case scenario each itemset would produce a path in the tree. If this happens, the storage space is no better than the plain storage of itemsets cause a FP-Tree requires additional space for pointers and counters3 .

The second step consists in mining frequent itemsets extracted from the FP-Tree by traversing it in bottom-up fashion.

Mining frequent patterns can be viewed as first mining 1-itemset and progressively growing each 1-itemset by mining on its "conditional pattern" base recursively. A "conditional pattern" are the items which sufix is dependent of. For example, in Figure 3.4(d) one conditional pattern for {e} is {c,d,a:1} and the other is {a,d}. Then, for each conditional pattern, frequent itemsets are derived as permutations of the items, e.g. for {e} and {c,d,a} we have: {e},{e,a},{e,c},{e,d},{e,a,c},{e,a,d},{e,c,d} and {e,a,c,d}.

An item header table is used to record the occurrences of the same item across the tree (e.g. Figure 3.4(c)).

FP-Groth is not adapted for stream mining, because it scans data multiple times. For mining frequent itemsets over stream, Chang and [START_REF] Hyuk | Finding recent frequent itemsets adaptively over online data streams[END_REF] proposed a damped window based algorithm, called estDec for finding recent frequent itemsets adaptively over an Lower-weighted itemsets may be pruned from the prefix tree (called monitoring lattice).

A single pass algorithm was proposed to count frequency of data elements over a data stream in (Manku and Motwani, 2002b). In the Lossy Counting algorithm, the set of frequent itemsets in a data stream is found when a maximum allowable error rate and a minimum support is given. A set of newly generated transactions in a data stream is loaded together into a fixed-sized buffer in main memory and they are batch-processed 4 .

The information about the previous mining result up to the latest batch operation is maintained in a linear data structure containing the information about the itemset, count and error.

Mining Closed Frequent Itemsets

Whilst mining all itemsets is desirable, it is not necessary to compute them all. It is sufficient to compute only closed itemsets which is a set much smaller than all and all other rules can be derived from them [START_REF] Zaki | Charm: An efficient algorithm for closed association rule mining[END_REF]. Several algorithms have been proposed to mine closed itemsets over static datasets: Closet [START_REF] Pei | Closet: An efficient algorithm for mining frequent closed itemsets[END_REF],

CHARM [START_REF] Zaki | Charm: An efficient algorithm for closed association rule mining[END_REF], Closet+ [START_REF] Wang | Closet+: Searching for the best strategies for mining frequent closed itemsets[END_REF], CHARM-L [START_REF] Zaki | Efficient algorithms for mining closed itemsets and their lattice structure[END_REF], FP-Close [START_REF] Grahne | Efficiently using prefix-trees in mining frequent itemsets[END_REF], DCI-Closed [START_REF] Lucchese | Dci closed: A fast and memory efficient algorithm to mine frequent closed itemsets[END_REF] (see [START_REF] Duneja | Article: A survey on frequent itemset mining with association rules[END_REF] for a survey).

CHARM [START_REF] Zaki | Charm: An efficient algorithm for closed association rule mining[END_REF] When a new transaction arrives, it checks the closed frequent itemsets stored in a hash table with its support and tidsum information to decide its node type according to the node properties and incrementally updates the associated nodes information.

An improvement over the original algorithm is presented in [START_REF] Li | Incremental updates of closed frequent itemsets over continuous data streams[END_REF] In [START_REF] Chen | Gc-tree: a fast online algorithm for mining frequent closed itemsets[END_REF] Our contribution. In this chapter, we propose a novel distributed architecture for mining formal concepts over data streams. It computes and maintains closed itemsets online and incrementally, and can output the current closed frequent itemsets in real time based on users' query. Our approach is comprised of several components that carry the computation of concepts from a basic transaction, filter and transforms data as well as provides analytic features to visually explore data.

The core of our approach is the distributed concept mining algorithm. The algorithm is a variant of the Moment algorithm introduced in [START_REF] Chi | Catch the moment: maintaining closed frequent itemsets over a data stream sliding window[END_REF]. We chose Moment because it has fairly decoupled procedures and, with some modifications, the CET operations may run in parallel. Other approaches seemed to require much more effort or were impractical. Nevertheless, when implementing and analysing the original Moment algorithm, we noticed the following issues:

• When deleting an transaction from the CET, a closed item set may become intermediate, however, there is no guarantee that the algorithm will carry out this change because only nodes added in the list F will be visited, and for a itemset be added in F it needs to become non-frequent (see Explore in [START_REF] Chi | Catch the moment: maintaining closed frequent itemsets over a data stream sliding window[END_REF]). The algorithm ignores the fact that a closed frequent itemset may become intermediate.

• The leftCheck( ) procedure might cause the pruning of a node that contains a closed itemset in its descendants (see Deletion in [START_REF] Chi | Catch the moment: maintaining closed frequent itemsets over a data stream sliding window[END_REF]).

We tackle these issues in our approach and we introduce an extra verification step to reduce the amount of useless subsets generated (Section 3.4.3.2). To the best of our knowledge, this is the first distributed approach to compute and visualise formal concepts over a data stream.

A Distributed Approach to Compute Formal Concepts over Data Streams

In this section, we describe our distributed approach for mining concepts in real-time over a data stream. For this task, we used Storm5 , a distributed real-time data processing platform. Strom provides abstractions to carry on distributed computation similarly to "Map Reduce jobs" in Hadoop, however, when jobs in Hadoop eventually finish, in Storm a topology runs until the process is interrupted by the user. Storm is able to process over a million tuples per second per node. It is scalable, fault-tolerant, and uses persistent queuing to guarantee that the data will be processed. A brief introduction to Storm is given in the next section.

We may refer to "node" as an object in one of our data structures. "Node" is a term often used in distributed computation to refer to independent computation units. In this case we will refer to them hereafter as "computation unit".

Storm Topologies, Spouts and Bolts

There TelemetrySpout. It is a stream generator for the telemetry use case we discuss in Chapter 5. This unit produces tuples from sensor data to the rest of the topology.

FilterBolt. It emits a transaction only if a condition is satisfied for the incoming transaction.

ScalingBolt. It processes a transaction and replaces continuous-valued attributes to multi-categorical values.

FPTreeBolt. It adds the transaction to the FP-Tree and emits the input transaction.

6 When multiple nodes request the same resource. RemoveFromCETBolt. It deletes the oldest transaction in the sliding window from the CET tree. Notice that the deletion bolts run concurrently with the addition bolts.

In the following section we describe how the above Storm topology fits in the overall architecture we propose in this thesis.

System Architecture

The architecture of the real-time system is a client-server comprising mainly of three components: the concept mining algorithm that runs on top of a Storm topology; the user interface/analytics component, called Cubix; and a Node.js server that pushes updates to the client browsers in real-time (RT) (Figure 3.6).

The concept mining algorithm works offline in that no user interaction is required. It works independently of the other modules and outputs all formal concepts in the current window.

The user interaction is done in the Cubix analytics. It provides visualisations, filtering and searching capabilities, and a number of analytics tools (discussed in Section 4).

When the user makes a request, Cubix passes the request to the Node.js server which collects the current closed concepts from the CET and pushes updates to client browsers in real-time via websockets.

Storing Itemsets in the Window

Having an efficient way to store and retrieve itemsets and transactions is a key factor in FIM algorithms. In a distributed environment it adds an extra challenge: the structure is shared across multiple computing units, thus it is necessary to manage a consistent state and racing conditions. In the next sections, we describe the data structures we are using for storing transactions and itemsets.

CET Node Properties

We use a synopsis data structure called Closed Enumeration Tree -CET, described in Section 3.4.3.4, to monitor only the frequent itemsets that may become closed itemset or has a closed itemset in their descendants. We then prune all descendants of "unpromising" and "infrequent" itemsets. This approach was first proposed in [START_REF] Chi | Catch the moment: maintaining closed frequent itemsets over a data stream sliding window[END_REF] and it defines node properties to make assumptions about potential closed itemsets.

We introduce a new node property, "Idle" to indicate itemsets that are to be deleted from the CET if not updated after a number of transactions δ. The rationale for this property is as follows. After analysing common bottlenecks in the performance of frequent itemset mining algorithms using the sliding window model, we discovered that the re-computation of previously deleted itemsets can be amortized by keeping the itemset in the synopsis. This way, if a node has become infrequent and then frequent in a interval < δ is will not need to be generated again. This situation occurs notably when the minimum support has a low value (which is often the case in anomaly detection systems we explain in Section 5.5).

The CET node properties are described as follows.

Infrequent gateway nodes. All descedants of a infrequent gateway node are also infrequent.

This definition is derived from the apriori property [START_REF] Agrawal | Fast algorithms for mining association rules in large databases[END_REF]. If an item set occurs N times, all its subsets occurs at least N times, in other words, if n I is an infrequent gateway node, then any node n J where J ⊃ I represents an infrequent itemset. All descendants of infrequent gateway nodes are pruned from the CET.

Unpromising gateway nodes. An unpromising gateway node has no closed itemset in its descendants.

A node n I is an unpromising gateway node if there exists a closed frequent itemset J such that J ≺ I, J ⊃ I, and J occurs in the same transactions of a frequent itemset I.

Descendants of an unpromising gateway node are pruned because no closed nodes can be found there.

Idle nodes. An itemset marked as "idle" is to be removed from CET if it is not updated after δ transactions. A node n I is idle if it one of its antecedents is either "infrequent" or "unpromising". If a idle node is not updated after δ transactions it is then permanently deleted from the CET.

Intermediate nodes. An intermediate node has at least one child with the same support.

If n I is a intermediate node, it has a child node n J such that J has the same support as I does and n I is not an unpromising gateway node. Intermediate nodes must not be pruned from the CET tree because it has at least one closed node among its descendants.

Closed nodes. An itemset is closed if none of its immediate supersets has the same support.

A node n I is closed if there is no parent node n J such that J has the same support as I. These nodes represent closed frequent itemsets in the current sliding window (see definition in Section 2.2).

An Extra Checking to Reduce the Number of Itemsets Generated

The original Moment algorithm judges closed itemsets not via closure checking as it is traditionally done, but through checking and updating the nodes properties as described in the previous section. A drawback of this approach is that it needs to store extra information besides the closed itemsets themselves. The CFI-Stream algorithm for instance, uses closure check on the fly through a series of conditions, and only the closed frequent itemsets need to be stored (Jiang and Gruenwald, 2006b). Nevertheless, benchmarks showed no significant performance difference between the two approaches (Jiang and Gruenwald, 2006b).

The bottleneck of Moment's algorithm is that the explore routine needs to generate subsets and check node properties. As we mention in Section 2.4.4, we can incorporate conditions to the algorithm in order to reduce the number of unnecessary comparisons.

The extra checking we propose takes advantage of the fact that if an itemset I and a newly generated J such that J ⊂ I have the same support, I cannot be closed because J is a smaller set containing all items of I, therefore I does not need to be generated. In the example of figure 3.7, the itemset AC do not need to be generated because ABC ⊂ AC and supp(ABC) = supp(AC). This checking is done in the SubsetGenBolt we describe in Section 3.4.6.

Storing Transactions in the FP-Tree

Each transaction in the stream is identified by an unique ID (we refer to it as TID), which is given by the current time in milliseconds in our case. The support of an itemset is the sum of the TIDs comprising all transactions in which the itemset takes part. We call it tidsum.

We need to store all transactions in order to calculate the support and the tidsum for transactions in the window. This can be done efficiently with a prefix tree like the FP-Tree (Han et al., 2000b), as introduced in Section 3.3.2.

In our implementation, we store the FP-Tree in a key-value memory cache where each node contains information about its items, support, children and the next item in the linked list. Table 3.2 illustrates the storage for the FP-Tree in Figure (3.8). To compute support and tidsum in this structure, we iterate through each item in the header table, navigating through the concerned nodes in the tree using the linked list (dotted arrows). The insertion and search in the tree have O(logN ) time complexity in average and O(N ) in the worst case (i.e. when every itemset form a separate branch in the tree).

Marking Boundaries with a Closed Enumeration Tree (CET)

A prefix-tree is used in several stream mining algorithms to store transactions and itemsets in a compact way [START_REF] Chi | Catch the moment: maintaining closed frequent itemsets over a data stream sliding window[END_REF], Jiang and Gruenwald, 2006a[START_REF] Hyuk | Finding recent frequent itemsets adaptively over online data streams[END_REF][START_REF] Li | Incremental updates of closed frequent itemsets over continuous data streams[END_REF][START_REF] Grahne | Efficiently using prefix-trees in mining frequent itemsets[END_REF][START_REF] Lucchese | Dci closed: A fast and memory efficient algorithm to mine frequent closed itemsets[END_REF]. The Closed Enumeration Tree (CET) was introduced in the Moment algorithm [START_REF] Chi | Catch the moment: maintaining closed frequent itemsets over a data stream sliding window[END_REF] to store a dynamically selected group of itemsets (Figure 3.9). The itemsets in CET tree are used to determine "boundaries" to represent closed itemsets, itemsets that may become closed in the future, and itemsets that cannot generate closed itemsets.

As explained in Section 3.4.3.1, some heuristics are applied at each insertion to the CET to unecessary storage space and computation. In the example of Figure 3.9(b), node {c,d} is not generated because {c} is a unpromising gateway node. Like the FP-Tree previously mentioned, the CET is stored in a key-value memory database in a similar fashion, with one caveat: children ID's are stored in a lexicographically sorted collection7 . This is because we are often exploring those itemsets using the ≺ and ≻ relations.

In addition to the CET, we use an additional hash table to enable quick lookup about which transactions a given closed itemset occurs. The key of the hash is comprised of both tidsum and support, and it stores a pointer to the corresponding closed node in the CET. We will refer to this hash table as CET hash table.

Filtering and Scaling

Two major pre-processing tasks in FCA is to filter irrelevant attributes and objects, and distribute multi-valued attributes into ranges so that each value of a multi-valued attribute becomes nominally a one-valued attribute (see Discretisation and Booleanisation in Section 2.2).

This algorithm in the FilterBolt transmits a transaction only if pre-defined filter condition is satisfied. For example, some types of analysis may be focused on transactions containing particular attributes-values. The filtering conditions are pre-defined by a domain expert.

The ScalingBolt transforms multi-valued attributes (Algorithm 4). It takes as input the transaction I, a intervals mapping M and a dictionary D. The intervals mapping is a dictionary containing the partitions for each attribute 8 . This is only possible if the maximum and minimum values of a given attribute is known apriori. For example, if a sensor is sending information about temperature in Celsius, the dictionary would contain intervals such as "[<-100]", "[-100:-50]", ..., "[>100]". For each multi-valued attribute a corresponding interval in M (lines 4 and 5).

One may argue in favour of a "floating" intervals approach, where the system automatically redistributes ranges according to the upcoming values of attributes. However, in the sliding window approach, keeping a floating interval would require the update of maximum and minimum values for each multi-valued attribute at each addition/deletion of a transaction from the window. This could be done efficiently with a double-ended priority queue, where the consultation time complexity is O(1) and insertion O(log N).

Most importantly, it would require the re-computation of all itemsets with the new attribute scales.

In order to reduce the amount of memory used to store the string representation of attributes, the algorithm uses a second dictionary D to replace the name of each attribute by a more compact representation, typically a index number (line 9). A bit array representation for itemsets may be used, however, large bit arrays tend to have long streams of zeroes or ones. This phenomenon wastes storage and processing time. Each pair attribute-value is represented by a bit in the bit array, this representation would not be suitable for sparse data such a text, where the number of 0's would account for most storage space. Thus, instead of compressing bit arrays as streams of bits, we might assign them a index from the dictionary D. Experiments of Moment show that the boundary in CET is stable so the update cost is little.

Subset Generation

Once that FPTreeBolt added the transaction to the FP-Tree, we start the frequent itemset mining phase with the SubsetGenBolt. This module generates subsets of item-ids along with their frequencies in the current transaction in lexicographic order. Not all possible subsets need to be generated. As we have seen earlier, unpromising and infrequent nodes cannot generate closed itemsets and thus the subsets of these nodes do not need to be generated. Algorithm 5 shows the procedure.

First, it skips any unpromising or infrequent nodes (lines 2 and 3). Then, for each item in the current transaction, it goes recursively through the corresponding CET path incrementally appending new items (if they are not there already) until it completes the powerset of the transaction (lines 8-17).

The powerset generation has exponential time complexity O(2 N ), and this is the most costly operation in the entire system. Fortunately, this operation is not frequent since most itemsets should fit in some existing branch of the CET and most importantly, this is a non-blocking operation due to the parallelism the approach provides. For example, while the SubsetGenBolt is running the procedure, another thread (or machine) is consuming the incoming tuples. Alternatively, the system administrator can increase the number of threads for SubsetGenBolt without affecting the topology. Load balancing and fault-tolerance are managed by Storm.

Updating CET Tree

For each upcoming transaction we need to update the support in the FPTree and the parts of the CET related to the transaction. We also need push the transaction to the sliding window and pop the oldest one from it. These tasks are performed by the IncrementBolt, AddToCETBolt, DecrementBolt and RemoveFromCETBolt.

In the following sections we explain each of them in detail.

Removing a Transaction from the Sliding Window

When deleting a transaction from the window, we decrement the support count and tidsum for each node (RemoveFromCETBolt 8 line 3). If the node has become infrequent its descendants must be pruned and the node marked as infrequent (lines 5 and 6). In the RemoveFromCETBolt, for each "promising' 'child n ′ I of n I it checks if there is a node with the same support and containing all items of the current node using hashCheck( ) (line 5). If so, n ′ I is unpromising and has its descendants pruned from CET (lines 6 and 7). Otherwise, the procedure goes recursively until it reaches the leaves of the CET (line 10). Then, the procedure verifies if closed nodes have changed by looking at their immediate children. .12 illustrates the updates in the CET when deleting each transaction.

The Distributed Caching Problem

In a distributed environment, locally caching of data may become a problem when nodes request the data stored in the cache of another node. Consider the following scenario.

A node "A" generates a new itemset I, stores it in its cache and proceeds generating the children of I. When the powerset of the itemset I is complete, the cache flushes data to the database. Another node "B" generating an itemset J needs to know if J or any of its children was already generated. However, J may have been generated by node "A" but it is stored in its cache.

In our experiments this situation occurred frequently. There should be a trade-off between the amount of data in the cache and the frequency in which it is flushed to the database. A workaround is to assign a hash key for each itemset processed so that a newly created itemset will be stored in the same storage address of the existing one, thus avoiding duplicates. That does not solve, however, the fact that multiple nodes might be computing the same itemset. As future work, we will investigate a strategy based on broadcasting across bolts in order to communicate which itemsets are being processed by which node.

Chapter Summary

This chapter described a novel distributed architecture to mine formal concepts over a data stream. A review on the main algorithms for itemset mining over stream was provided in Section 3.3.2. Using a synopsis data structure, typically a prefix-tree, stream mining algorithms use the result of previous computation and make changes incrementally as new data arrives in the stream.

In most cases, it is not practical to store and compute the entire data from the stream.

Instead, most algorithms select portions of the stream that should be processed to mine itemsets. The main processing models are: the Landmark model, the Damped model and Sliding Window model.

Our proposed distributed approach is described in Section 3.4. The distributed mining algorithm checks and maintains closed itemsets in an incrementally and in parallel.

Information are shared across the bolts using a remote memory database. An extra checking is done in order to reduce the number of itemsets generated (Section 3.4.3.2).

The next chapter is dedicated to the Visual Analytics component of the architecture presented in Section 3.4.2.

Chapter 4

Visual Analytics for Formal Concept Analysis

Introduction

When FCA is applied to Business Intelligence, data is typically large, complex and dynamic -new questions are raised everyday by business experts and managers alike.

The analysis is performed on a more frequent basis than traditional applications of FCA, therefore interactive features are needed. Because the nature of the task is not linear, which is the case of information retrieval systems, it is necessary to provide a number of tools. For most tasks, only a few of these tools are used, but they are all important in the sense that they can be combined to address different analysis needs. This is the "Photoshop" paradigm.

FCA provides semantic groupings of objects and attributes based on their co-occurrence.

In real-world datasets the resulting concept lattices are often too large to allow users to answer their analysis questions. Through a series of participatory design sessions with our user groups, we assessed the benefits of FCA in their analysis goals and investigated alternative ways to improve the visual representation and exploration of the lattice structure.

This chapter discusses our proposal for visual analytics for concept lattices, where new visualisations are proposed together with novel visual analytics features that enhance data representation and support different analysis tasks (Section 4.3). We extended the visual analytics to Association Rules, as we explain in Section 4.4. Finally, in Section 4.5, we propose a tree extraction algorithm to simplify lattice browsing and visualisation while preserving the most essential features of the original structure. As we will discuss in Section 4.5, trees are common and have easily understandable visual representations.

We consider them as a visualisation alternative to large cluttered concept lattices, which preserves all lattice entities and some of its structure. Finally, Section 4.6 introduces

Cubix, an analytics tool for Formal Concept Analysis that implements all proposed visual analytics features. It runs in the distributed architecture described in Chapter 3.

Visual Representation of Concept Lattices

Concept lattices carry meaningful information on how formal concepts are related to each other and their properties are well defined in the FCA literature [START_REF] Gerd | Computing iceberg concept lattices with titanic[END_REF], Eklund and Villerd, 2010[START_REF] Kuznetsov | Algorithms for the construction of concept lattices and their diagram graphs[END_REF][START_REF] Wille | Lattices in data analysis: how to draw them with a computer[END_REF]. As R.

Wille noted in his 1989 paper [START_REF] Wille | Lattices in data analysis: how to draw them with a computer[END_REF]:

"Lattices in data analysis are more than just mathematical structures:

They carry meaning. Therefore, drawings of such lattices should not only reflect the mathematical structure but also give a meaningful presentation for the data." (p.

2)

The Hasse diagrams used in FCA are usually layered graphs, where concept vertices are assigned to horizontal layers according of the number of common attributes in each concept, and are ordered within each layer to reduce edge crossings. FCA lattices in particular suffer from considerable edge crossings, especially if the number of concepts exceeds a few dozen; this is unfortunately the case in most real word applications [START_REF] Roth | Towards concise representation for taxonomies of epistemic communities[END_REF], which leads to reduced graph readability and aesthetics [START_REF] Ware | Cognitive measurements of graph aesthetics[END_REF].

A good lattice representation will provide a clear overview of the structure, allowing a clear understanding of specialization and generalization for a given concept. [START_REF] Eades | Algorithms for drawing graphs: An annotated bibliography[END_REF] listed the following qualities for a graph drawing algorithm:

• display of symmetry;

• avoidance of edge crossings;

• avoidance of bends in edges;

• uniformity of edge lengths;

• uniformity of distribution of vertices.

For general graphs, the problem of a determining a planar layout of a graph with least edges crossing (the Crossing Number ) is NP-hard. Therefore some heuristic methods are used, like the force based layout algorithms where initial vertex placement by continuously moving the vertices according to a system of physical forces.

Layout algorithms like the additive line diagram [START_REF] Ganter | Formal Concept Analysis[END_REF] have the advantage of being configurable through the choice of the representation set, and the technique produces a high number of parallel edges, which in turn improves readability.

New Alternative Visualisations for Concept Lattices

We propose alternative visualisations for the concept lattice, based on the Hasse diagram and tree-like visualisations. In order to display a tree visualisation the concept lattice has some of its edges pruned, as we explain in Section 4.5. Each visual component of the interface is seen as a view, i.e. a "perspective" on the underlying data, in our design pattern model. This is important to keep the visualisation states synchronized across the analytic features, as we explain in Section 4.4.1.

In the following sections we discuss the three proposed visualisations for the Hasse diagram: matrix, sankey and heat map.

Matrix

A Matrix is a traditional and compact way to visualise dense relationships relationships among entities. This visualisation is particularly interesting for BI experts because of their familiarity with tabular data. Additionally, it facilitates the understanding of the relations among entities through a conceptual point of view, i.e, noticing which sets of objects and sets of attributes may form a concept. Whilst the matrix visualisation for concepts was well received by our users, it is limited to certain applications. It only makes sense with a small set of objects and attributes that can fit on a screen, since scrolling could potentially cause the user to loose reference of the same occurring concept on the cells out of the visible screen. Second and most importantly, it is not able to display hierarchical features of a concept lattice 1 . To tackle specifically that issue, an alternative to the matrix visualisation is a variant of a diagonally-filled matrix, called GeneaQuilts (Bezerianos et al., 2010), which can represent hierarchies through links between the different layers in the matrix. A major drawback is, however, that the drawing of links between non-subsequent layers may result in multiple edges crossing.

Sankey

Another proposed visualisation for concept lattices is the Sankey diagrams [START_REF] Schmidt | Der Einsatz von Sankey-Diagrammen im Stoffstrommanagement[END_REF]. This class of diagrams are usually employed to depict flow, in which the width of the arrows is shown proportionally to the flow quantity. In the case of a concept lattice, this flow can correspond to the actual links between concepts. There is a strong focus on how entities are connected, therefore, it can be used to guide the exploration of links in the concept lattice. One advantage of this visualisation is that it makes easy to see, for instance, how objects are boiled down in throughout the hierarchy of concepts.

A "Heat map" Visualisation for Multi-Valued Concepts

Similarity Formal Concept Analysis (SFCA) compute formal concepts without the need of data scaling, multi-valued attributes are grouped together with respect to a similarity threshold [START_REF] Messai | Many-valued concept lattices for conceptual clustering and information retrieval[END_REF]. The result of SFCA are multi-valued concept lattices, in which concepts may have attributes with continuous values.

To help the analyst to quickly identify intervals in the concepts and compare with other concepts in the lattice, we designed a new visualisation based on "heat maps". In this visualisation, each concept is depicted as an array of rectangles (Figure 4.3). Each

1 Unless we establish a drawing order to the overlapping rectangles, for example.

Visualisation of Association Rules

It is possible to compute association rules from formal concepts via subset generation.

Association Rules are of the form {premise} =⇒ {conclusion}, e.g. {"fly", "lay eggs"} =⇒ {"bird"} and are known to establish implication among categorical variables. One of the most known use case is the market basket analysis, which seeks to discover products that are often brought together, for example, butter is often bought together with milk.

Whilst the example is obvious, there are cases where association rules can highlight interesting relationships. For example is known that babydiapers and beer are often bought together (fathers going to buy nappies for their babies, would buy beer as well).

Because most items are categorical, association rules carry very little information about the way they can be visualised. Data mining software typically represent them as a list of logical sentences, impractical for a large number of rules.

We implemented two new visualisations combined with statistics and charts to enable progressive exploration of the ruleset. A Matrix view display each rule in a row and the concerned pairs of attribute-value in columns (Figure 4.4). In this visualisation, the colour of the cells indicates whether the attribute is in the premise (purple) or in the conclusion (yellow) of a rule. The confidence of each rule is represented by the opacity of each cell: the brighter the colour, the higher the confidence is. Rules are sorted from premise to conclusion and in lexicographic order for convenience.

In the example of The positions follow a circular path given by PosX and PosY. The label is rotated θ degrees to "flip" the label to be read conveniently, i.e., avoid placing labels up-side down as illustrated in Figure 4.6. In the next section, we describe the proposed interactive features that play together with the lattice visualisation.

Visual Analytics of Concept Lattices

Visual analytics can be seen as an integral approach combining visualisation, human factors and data analysis [START_REF] Daniel | Visual analytics: Scope and challenges[END_REF]. According to Thomas et al., "Visual analytics is the science of analytical reasoning facilitated by interactive visual interfaces" [START_REF] Thomas | A visual analytics agenda[END_REF]. It is the tight integration of computational analysis by algorithms and highly interactive visualisations. The human intuition and background knowledge are key aspects in the process, orchestrating the interface elements to produce (or induce) a desired state that will ultimately lead to some knowledge gain. The system, on the other hand, has to provide meaningful representations and exploration methods on the data. Interactions that affect the state of the interface should provide smooth transitions to help users cognitive memory and traceability.

The potential of using analytics features to enhance FCA was acknowledged as early as in 1995, when Carpineto & Romano implemented a visual interface for large lattice called

Ulysses [START_REF] Carpineto | Ulysses: a lattice-based multiple interaction strategy retrieval interface[END_REF]. They suggested a "Fish eye" representation of concept lattices so that the focus on one concept node would expand its similar neighbours proportionally. Ulysses allows users to reduce the search result space by adding constraints to the lattice. Later with CREDo (Carpineto and Romano, 2004a) only parts of the lattices are displayed similar to file/folder displays, where a second level of the hierarchy is indented and can be expanded or collapsed interactively by users. [START_REF] Priss | Lattice-based information retrieval[END_REF] used the lattice representation to show the concepts hierarchy in thesauri.

Each concept is viewed as a facet in an information retrieval system. [START_REF] Akand | A Visual Analytics Approach to Augmenting Formal Concepts with Relational Background Knowledge in a Biological Domain[END_REF] propose an algorithm that generates a browse-able concept lattice designed for biology applications. [START_REF] Villerd | Using concept lattices for visual navigation assistance in large databases: Application to a pantent database[END_REF] used visual analytics in an indexed document collection to display concept lattices in a global view and concept details in a local view.

The system expands/collapses information according to selections made in the concept In the next sections we describe each of the proposed analytic features for concept lattice: a dashboard, the use of visual variables to enhance lattice exploration, search and selection, visual filters and clustering. All the proposed analytics work analogously for concept lattices and association rules. The techniques were implemented in Cubix, which will be discussed in detail in Section 4.6.

The Model-View-ViewModel (MVVM) Pattern

Typical visual analytic tasks include exploration, filtering, selection and data transformation. All interface elements must be consistent at each operation. For example, when the user searches for "all retail stores with revenue above X " he or she will expect that the visualisations change to match with his or her query.

Maintaining a consistent state across multiple visualisations and triggering updates only to concerned parts is a challenge faced by modern analytics systems. To cope with this, we implemented a variant of the Model-View-Controller pattern, called Model-View-ViewModel (MVVM) 3 . A ViewModel is an abstraction of the view that serves to mediate between a view (e.g. Hasse diagram) and a model (e.g. concept lattice).

The application maintains a synchronized state through event handlers (for a detailed explanation on MVVM, see [START_REF] Hall | Pro WPF and Silverlight MVVM: Effective Application Development with Model-View-ViewModel[END_REF]). For example, when the user click on a filter, the action is sent to the data model which in turn triggers the corresponding event listeners causing the visual components to be updated. It also allows switching visual components without affecting the underlying data structure.

Dashboard

In addition to the main concept lattice visualisation, several charts display different aspects of the underlying conceptual structure such as co-occurrence of attributes, concepts distribution, stability versus support, etc. (Figure 4.7). Some charts are updated when the user points the mouse over a concept, highlighting details of the concept. Similarly, a selection of a point/series in the chart will highlight the concerned concepts in the lattice. This technique is called Linking and Brushing [START_REF] Ward | Linking and brushing[END_REF].

Visual Variables

Common analytic techniques include the assignment of different colours, shapes and sizes to nodes and edges, according to different dimensions or properties. This approach is underused in traditional lattice visualisations, where the main visual variable used is node/link colour to reflect user selections or node size to indicate the immediate presence of an extent or intent as displayed in ConExp4 .

We use these as well as other visual variables in a Hasse diagram to enhance the understanding of conceptual data. Prominent features of the lattice like specialization and generalization can be better understood, for instance, the confidence of implications of different concepts can be rendered by edge thickness. Figure 4.8 shows a concept lattice where the size of the node is proportional to its support, the confidence by edge thickness and colour to represent the cluster the concept belongs to.

Search and Selection

Search and selection are two of the most common operations in decision-support systems.In our analytic tool, a concept can be selected manually (by clicking) or by searching for properties in the concept lattice.

A search bar provides auto-completion of text and highlights the selected concepts in lattice (Figure 4.9).

Visual Filters

The number of concepts can grow dramatically with the number of objects and attributes, yielding poorly readable concept lattices. The filter bar displays the current distribution of attributes in the lattice and allows the user to visually select and filter concepts (Figure 4.10). The filter bar has an additional visualisation, which is a lattice view for each attributes (Figure 4.11). This visualisation allows identification of attribute-value correlations and it is particularly interesting for complex multi-valued attributes. A history of activated filters is displayed at the bottom and it allows the user to remove a given filter non-sequentially.

It is worth noticing that the filters act on the concept lattice rather than on the context itself. Current FCA tools such as ToscanaJ and Conexp, allow filtering on the context, and the lattice needs to be computed again.

Concept Clustering

Clustering of concepts can be useful to facilitate the analysis and to identify zones of interest. Some similarity measures are based on the concept lattice topology (e.g. counting the number of links between two concepts); Intent/extent similarity (e.g. Jaccard );

or confidence between two pairs of concepts.

Concept similarity (Jaccard). It is a coefficient for calculating the ratio of shared attributes between concepts. We define concept similarity as:

CSim(A, B) = |m a ∩ m b | |m a | + |m b | + |g a ∩ g b | |g a | + |g b | (4.4)
Proximity. Conceptual proximity is the topological distance between concepts A and B in the concept lattice.

prox(A, B) = 1 - shortestDistance(A, B) diameter(Lattice) (4.5)
Strength. It is the average concept similarity value (CSim) along the shortest path between a pair of concepts.

In the example of Figure 4.8, a k-means clustering algorithm [START_REF] Hartigan | A K-means clustering algorithm[END_REF] was used to identify clusters (the number of clusters is defined by the user).

Tree Extraction and Visualisation from Concept Lattices

Browsing concept lattices becomes a problem as the number of clusters grows significantly with the number of objects and attributes. Interpreting the lattice through a direct visualisation of the Hasse diagram rapidly becomes difficult and more synthetic representations are needed. A common approach is to show or hide parts of the lattice via interactive exploration of subsets of terms or neighbours of a focus concept [START_REF] Ducrou | An intelligent user interface for browsing and searching mpeg-7 images using concept lattices[END_REF]. [START_REF] Carpineto | Using concept lattices for text retrieval and mining[END_REF] defined constraints to be applied to the concept lattice in order to simplify lattice querying and navigation.

Trees are good alternatives to represent concept lattices in this context, because they do not suffer from edges crossings and they are natural metaphors for navigation history since there is only one parent per child. Additionally, users are familiar with that structure as trees are used to navigate through folders and files in most operating systems.

In [START_REF] Carpineto | Using concept lattices for text retrieval and mining[END_REF] it was noted that trees are particularly interesting structures to represent concept lattices for browsing, however, authors pointed out that their main disadvantage is the amount of replicated information when concepts have multiple parents. In the current work we avoid duplication by selecting only one parent for each concept in the lattice. One inherent challenge is to formally define the notion of best parent among the potentially numerous parents of a concept. A previous work by Le Grand et al. (2009) used an approach to extract trees from lattices based on the assignment of weights to attributes. Concepts with higher average weights were selected as parents while the other concepts were removed from the resulting tree.

Our approach consists in representing lattices not as Hasse diagrams, but as trees. As

Tree Extraction based on the Selection of One Parent per Layer

In a previous work by Le [START_REF] Benedicte | XML Topic Maps and Semantic Web Mining[END_REF], authors presented an approach to extract trees from concept lattices based on the selection of one parent concept per hierarchical layer in the lattice. The process starts by collecting all most specific concepts (i.e. the lower bound parent concepts at the second lowest layer of the concept lattice) so all objects are present in the new structure. A single parent concept is then selected for each of these concepts, and the process continues recursively until reaching the top of the lattice. The choice of a single parent for each concept therefore removes links and eventually concepts5 .

The goal is to select parents according to their relevance from user's point of view, for example, taking into account the attributes that are most significant to him or her. The challenge is to find the set of criteria that best suits users' expectations. Trees extracted from the same concept lattice can be very different, as shown in Figures 4.13 A hierarchy of parent selection criteria was defined in [START_REF] Trad | Powerconcept: Conceptual metrics distributed computation[END_REF] to extract a tree from the concept lattice generated from on a corpus of 126 web pages dedicated to tourism. The algorithm works as follows:

• For each concept, called the current concept, it selects the parent concept which is located at the shortest distance from the upper bound of the lattice (in order to minimize the number of links);

• if several parent concepts satisfy this condition, it favours those which have already been selected as a single parent by other concepts of the same level as the current concept;

• If the last condition is not sufficient, it selects the concept with higher average of attribute weights, previously assigned by the user.

Figure 4.15 shows the conceptual tree extracted according to these criteria from the lattice generated from the tourism data set. Outer arcs represent most general concepts, i.e., those situated on the top in Hasse diagrams. To facilitate the interpretation of the tree, the intent of each of the concepts in the top layer is displayed. The surface of each arc is proportional to the number of leaves of the corresponding sub-tree to provide a glimpse of the most significant topics in the data set, in this case pages devoted to France, food, camping, and the region Loire. This visualisation has some limitations.

While it is easy to see the top-most categories, children nodes have smaller drawing space than their parents, even though they are more numerous. The nested nodes in the tree are thus harder to discern. We addressed this issue by inverting the drawing order of parents and children, as we explain in Section 4.5.3.

Tree-extraction based on Conceptual Indexes

The initial tree extraction approach presented above has one main disadvantage: the elimination of concepts which can lead to a loss of information. The present approach leverages conceptual measures as criteria to select parent concepts, keeping the link with the parent that scored the best with the considered index. As with the previous approach, the process starts with the most specific concepts i.e., at the bottom of the Hasse diagram and recursively computes the index for each of the candidates and eliminate links to all parent concepts except the one with the selected parent. The pseudo-code of the algorithm is provided in Algorithm 10.

Choosing a single parent concept at each step leads to some information loss, although in this case only links are removed. Our goal is to minimize this loss by selecting parents using the most relevant criteria according to the kind of analysis performed by the analyst. In the following sections we consider various strategies for selecting parent concepts, including the stability [START_REF] Kuznetsov | Reducing the representation complexity of lattice-based taxonomies[END_REF] and support [START_REF] Gerd | Computing iceberg concept lattices with titanic[END_REF] indexes from FCA literature, as well as the confidence and similarity measures.

Algorithm 10: ExtractTree Data: A concept lattice L. begin The stability index measures the proportion of subsets of objects of a given concept whose derivation is equal to the intent of this concept [START_REF] Kuznetsov | Reducing the representation complexity of lattice-based taxonomies[END_REF]. In other words, stability indicates the probability of preserving a concepts intent while removing some objects of its extent. A more stable concept is less dependent on individual members in the extension. We recall the definition of stability:

foreach concept A, B in Concepts(L) do Parents[ A, B ] ←-list of parent concepts of A, B if |P arents[ A, B ]| > 1 then max score ←--1 foreach concept C, D in Parents[ A, B ] do Score[ C, D ] ←-score for concept C, D if Score[ C, D ] > max score then SelectedParent[ A, B ] ←-C, D max score ←-Score[ C, D ]
Definition. Let K = (G, M, I) be a formal context and A, B be a formal concept of K. The stability index of A, B is defined as:

stability(A, B) = |C ⊆ A|C ′ = B| 2 |M | (4.6)
Using the context in table 1 as an example, we calculate the stability for concepts 3 and 5 in order to select a parent for concept 6 (0.25 and 0.5 respectively); we keep the one with highest stability, in this case we therefore remove the edge between concepts 3 and 6. The idea behind the choice of the parent concept with the highest stability is that we expect to keep parent concept's meaning even if some of the objects or attributes are removed. On the other hand, the support measure is the relation between the intent closure and the total number of objects [START_REF] Gerd | Computing iceberg concept lattices with titanic[END_REF]:

Definition. Let B ⊂ M .
The support count of the attribute set B in K is:

support(B) = |B ′ | |G| (4.7)
The use of support as parent selection criterion may lead to trees containing concepts with fewer specialization levels since generic concepts generally have higher support values than their most specific counterparts.

Parent Selection Based on Similarity

This measure relies on clustering parent and child concepts that share most of their attributes or objects. A parent and a child concept having a great number of attributes

similarity(E) = |B ∩ D| |M | (4.8)
In the same animals' context of Figure 4.16(a), we have potential parent concepts 3 and 5 sharing the same number of objects with concept 6, but concept 5 has more attributes in common with concept 6, so it should be chosen as the unique parent of concept 6 if the similarity criterion is considered.

Parent Selection Based on Confidence

The confidence value of a concept estimates how likely it is that an object with an attribute set A, also has an attribute set C [START_REF] Ganter | Formal Concept Analysis[END_REF]. In other words, it tries to measure how strong the implication of the parent concept to a child concept is. For instance, considering the formal context in Table 1, what is the probability of a given object that is {Bird, Flying} to be also {Bird, Flying, Preying}? The following paragraph formalizes its definition.

Definition. Let a concept A, B be such that A ∈ G and B ∈ M . Let concept C, D be a child (specialization) of A, B . The shared attribute index of an edge

E = C, D → A, B : conf idence(E) = |C| |M | (4.9)
An advantage of this method is its consistency with the interpretation of concept lattices.

Taking our context as example (Figure 4.16), there is a 50% probability that an animal that is a {Flying, Bird} be also a {Flying, Preying, Bird}. By contrast, a {Preying, Mammal} has only 33% of chance of being also a {Flying, Bird}.

A "Sunburst" Visualisation for Concept Lattice

We improved the radial-filling visualisation shown Figure 4.12. Because the number of concepts tends to increase in the most specific levels, the previous visualisation suffered from decreasing inner space. We decided to invert the way the hierarchy is displayed, top nodes are now in inner layers while more specific concepts are located in outer, more spacious layers. This visualisation layout is called "Sunburst" [START_REF] Stasko | An evaluation of space-filling information visualizations for depicting hierarchical structures[END_REF] and provides a overview of the distribution (depicted as the size of the arcs, Figure 4.17(c)).

One challenge is to assign label to concepts in a tree visualisation like the sunburst.

Concepts are labelled using elements from its intent and/or extent. It may become an issue if the number of attributes or objects is too long to be displayed, causing text overlaps. In the sunburst for example, layers with a large number of concepts tend to have smaller arc size. A common technique to cope with this problem is to only assign labels that were not previously assigned to any of its parents, i.e., avoid repeating labels that already appeared in parent concepts. We used this technique combined with a logic that hides the label of a concept if the arc size is too small to fit the text. Optionally, the user can zoom in the areas of interest and hidden labels will appear accordingly. In this section, we discuss a case study of a concept lattice to qualitatively examine the nature of the trees resulting from different criteria. For the sake of the example, we selected a sub-context from the dataset containing only 87 concepts. In this particular context, the original concept lattice depicted by the Hasse diagram contained 216 edges between concepts, reduced to 82 after the tree extraction (38% of the original edges). Each of the proposed measures revealed particular aspects on the analysis of a lattice, as illustrated in Figures 4.19 and 4.20.

The left column in Figures 4.19 and 4.20 shows the complete tree extracted from the lattice using the corresponding criterion, whereas the column on the right displays a particular part of the tree that we discuss. As explained previously, each concept is labelled in a non-repetitive way, i.e., labels assigned to parents are not be displayed in the respective children. Since labels can change from one visualisation to the other depending on the parent selected, colours were applied to each concept for easy identification (all concepts have the same colour in all visualisations e.g. "loisirs/voyage/camping"). This criterion tends to group concepts that have frequent objects in their extent. Notice that the concept containing {"montagne"} (mountain) accounted for many other concepts containing that attribute in contrast with confidence and similarity, for instance.

This occurs because there are many web pages relating the keywords {"montagne", "ski"} and {"montagne", "restaurant"}, thus making the corresponding concepts more likely to be selected as parent in this criterion. On the other hand, the concept which contains {"ski"} has only one sub-concept {"voyage"} in contrast with the trees extracted using confidence and similarity (Figures 4.20(a) and 4.20(c)). We can infer that pages containing {"ski"} alone are not as popular as other keywords, because they are commonly associated with either {"montagne", "transport"} or {"loisir", "voyage"} as the corresponding concepts show.

The stability (intent) index was the criterion that generated the tree in Figure 4.19(c).

With this index, concepts that retain the same set of web pages when some of their keywords are removed are the best candidates for parent selection. In the detail of Figure 4.19(d) the concept containing {"gastronomie", "ski", "montagne"} was the preferred parent to append the child concept {"gastronomie", "ski", "montagne", "voyage", "loisir"} contrarily to the selection made in the tree using support (Figure 4.19(b))

where the parent is {"montagne", "ski", "voyage"}. This suggests that despite having fewer occurrences (web pages), the concept {"gastronomie", "ski", "montagne"} has a smaller set of keywords that together correspond to the same pages. For instance, pages that talk about "gastronomy in the mountains" can cite "ski" as one activity to do in the mountains but the absence of that keyword is not crucial to describe the page. sharing most objects with a particular child concept were the best candidates. As an example, the concepts involving {"gastronomie", "ski"} were appended to the concept {"ski"} because there are more pages in common with the later than there are pages shared with the concept {"gastronomie"}. The same rationale explains the same parent selection for the confidence criteria: a page containing both keywords "gastronomie" and "ski" is more likely to be about "ski' than about "gastronomie". These choices contrast with those using stability and support ( In Figures 4.20(c) the tree was generated using the confidence criterion, i.e. children concepts are associated with the parent to which the relationship of confidence is the highest among the candidates. As a consequence, the concept {"voyage"} was the parent selected for the concept containing {"camping", "voyage"} as opposed to the concept {"camping"}, because usually camping implies going on a trip whereas going on a trip does not necessarily mean to go camping.

Guidelines on How to Choose the Parent Selection Criteria

The extraction of a tree from the original lattice implies that some links are removed and in some cases this can be misleading, depending on the selection criteria. Nevertheless, the process is able to keep some of the most essential conceptual features and provides different perspectives to the analysis, for example, on frequent patterns or on the implications between the concepts. It is also possible to display different trees at once in order to get a more comprehensive view.

When two parent concepts have the same score, the parent with the first computed score is selected by the algorithm. This could lead to an undesired non-deterministic result for the same input parameters. We stress that even non-deterministically in those cases, the process yields results consistent with the chosen metric. One way of tackling the issue is to define "tie-break" scores, i.e., other indexes to be used to define the best parent.

For instance, if two concepts have the same support, the parent selection second criteria can be stability.

The choice of parent selection criteria for tree transformation corresponds to a classification problem. Deciding if a "Lion" is more "mammal" than it is "preying" it is not always straightforward, hence we rely on the measures that attempt to keep the context semantics when looking at the entire concept lattice. For instance, if we have more objects described by the "mammal" set which are semantically closer to "Lion" than other concepts, then it may reasonable to be chosen as its parent. To guide the user in the choice of the selection criteria, the visual variables presented in Section 4.4.3 may be used to highlight the effect a given parent selection criteria yields. Table 4.1 presents a general recommendation for the parent selection criteria that are more suitable for some analysis tasks. Measures how likely a concept is to change if some of their attributes or objects are removed.

Stable concepts are less impacted by noise and usually represent strong correlation with real world entities (e.g.: a concept that encapsulates our notion of "mammal").

Observing real world analogies

Support

Measures the frequency of the concept itemset.

Frequent concepts are usually generic concepts since they aggregate a larger number of objects than the specialized ones.

Frequent pattern analysis

Similarity

Represents the degree of similarity between parent and child nodes.

Concepts that share most attributes or objects should be linked together because they are similar.

Similarity analysis

Confidence Measures how strong the implication is between a parent concept in a child concept.

Implication is one of the most intuitive interpretation of a concept lattice.

Implication analysis

Cubix: A Visual Analytics Tool for FCA

Cubix is a Visual Analytics tool that implements all proposed techniques described in this chapter. Cubix is part of a three-year project CUBIST 6 ad result of a series of participatory design with our end users. As a first step we conducted interviews with three types of use cases attempting to find patterns within their data: a company conducting market intelligence, computational biology, and a space control centre operation monitoring. All users had in common large amounts of data of which they wanted to answer mainly the following types of questions: frequent pattern detection, anomaly detection and pattern comparison. An example of frequent pattern detection is "during the first stage of a mouse embryo development what are the genes expressed together most often?". An example of an anomaly detection is "what are the sensor and telemetry logs of a space load on the International Space Station that may be related to a specific instrument malfunction?". Finally, a pattern comparison question would be "Are the jobs available in Liverpool similar to those in Manchester?" FCA allowed them to 6 http://www.cubist-project.eu create semantic groupings of objects and attributes based on their co-occurrence and progressively explore the lattice to look for answers to their questions. Based on recommendations from our users, we use the notions of support, stability and association (explained in Section 4.5.2.1) as filters, since these strategies help our users answer questions of the form most frequent pattern. But we also represent these notions visually on the lattice to enhance data understanding. For instance, the power of implications of different concepts can be rendered by edge thickness. In this way users can be guided in understanding and choosing criteria for reducing their lattices. Using these criteria we can also extract a tree structure to simplify the lattice representation (Section 4.5).

System Overview

Ontology Integration

Cubix can be integrated with a RDF/OWL triple store which enables the conceptual analysis on top of SPARQL queries. The conceptual analysis of ontologies provides unique information on the semantic data, by grouping entities belonging to particular properties in a hierarchical fashion. The process starts when the user enters a SPARQL query, which is then sent to the triple store via Cubix. The results are automatically scaled to a formal context, formal concepts are then mined and visualized in the analytics view. Currently, only Sesame and Owlim are supported in Cubix.

Similar Tools

Over the past decade a number of FCA analysis and visualization tools have appeared.

Their purpose is to generate the concept lattice of a given formal context and the corresponding association rules. ToscanaJ 7 , Galicia 8 and Concept Explorer (ConExp) 9 are among the most popular ones. They can compute and visualize concept lattices but are not designed to do so for large numbers of concepts and the support for interactive analysis is limited.

Recently, OpenFCA 10 , an open source FCA-based web application has drawn attention in the area for its ability to create formal contexts, mine and visualize concepts and explore association rules. It is one of the first tools with a highly interactive layout for concept analysis. There are a few limitations however, for instance, the only method for reducing large lattices is based on defining a maximum tree depth.

Specialized tools like FCA Bedrock 11 can scale data into formal contexts and has become a essential step in order to employ FCA in a Business Intelligence context. Facettice, a tool for visualizing and navigating in concept lattices demonstrated that visualization and interaction techniques can greatly enhance the understanding of conceptual data.

However, the tool was not designed to support interactive analysis.

Cubix extends the features of existing tools, from data scaling to the visual exploration of the concept lattice and association rules.

Chapter Summary

In this chapter, we described techniques for the visual exploration of concept lattices through searching, filtering and sub-selection of concepts and attributes; clustering and transforming concepts, and encoding lattice's properties using visual variables. We presented novel visualisations for concept lattice and association rules. Additional information can be found in (Melo et al., 2012) and (Melo et al., 2011b In order to facilitate navigation in large concept lattices, we propose a transformation approach to extract trees from concept lattices, attempting to minimize both semantic and conceptual loss in favour of readability and interpretation. This is an important step in the visual analysis of conceptual structures, as the resulting tree structures are visually easier to understand than cluttered lattice graphs. Each of the tree construction measures proposed in our work provides particular insights valuable to different analysis tasks, identified in our work as recommendations.

These contributions represent an important step in the visual analysis of conceptual structures, as domain experts can get semantically rich insights that traditional FCA tools do not provide. The first part of the chapter describes the design and evaluation methodology carried throughout the thesis. It outlines the procedures, test users and evaluation results. The second part of this chapter discusses the idiosyncrasies of each use case and presents further discussion from an user-centered perspective.

Methodology

It is widely recognized that understanding social and organisational context is critical for the success of many systems today. Human Computer Interaction (HCI) literature provides methods that help the system designer to collect and analyse users and their surrounding environment, and further enhancing the interface [START_REF] Lazar | Research Methods in Human-Computer Interaction[END_REF]. In the User-Centered Design (UCD) paradigm end users have an active role during all phases of the development process, as opposed to traditional software engineering where user evaluations are usually conducted in later stages [START_REF] Daniel Fitton | Rapid prototyping and user-centered design of interactive display-based systems[END_REF].

Users are only a part of the puzzle. They carry information, perform tasks, collaborate, adapt to new circumstances, set goals, in a complex and dynamic environment. It is therefore, necessary to have a holistic approach to study users and their environment where the system can be seen as a medium in which the user will serve to accomplish his or her goals. One of the most important aspects of system modelling is the task analysis [START_REF] Hackos | User and task analysis for interface design[END_REF]. For this reason, users from the three use cases were encouraged to participate in the design and prototyping sessions in a task-oriented way, besides the usual evaluation at the end of the process. The methodology is described in the following sections.

Design and Prototyping

As a first step we conducted interviews with three types of users attempting to find patterns within their data: users conducting market intelligence, computational biology, and space control centre operation monitoring. All users had in common large amounts of data within which they wanted to answer 3 types of questions: frequent pattern detection, anomaly detection and pattern comparison. An example of frequent pattern detection is "during the first stage of a mouse embryo development what are the genes expressed together most often?". An example of anomaly detection is 'what are the sensor and telemetry logs of a space load on the International Space Station that may be related to a specific instrument malfunction". And a pattern comparison question would be "are the jobs available in Liverpool similar to those in Manchester?".

Open questionnaires were used to gather information about user's background, common tasks and goals (Appendix C. The interviews were complemented with observations in order to get insights on implicit tasks1 . All users had previous experience with analytics systems at different levels and this aspect was taken into account.

Low-Level Tasks Taxonomy for Formal Concept Analysis

To guide our analysis, the main low-level tasks for Formal Concept Analysis were identified. These are common tasks performed by users on a concept lattice in order to match with the use cases aforementioned. This is based on works of [START_REF] Amar | Low-level components of analytic activity in information visualization[END_REF] and [START_REF] Lee | Task taxonomy for graph visualization[END_REF] on graph analysis complemented by user interviews. Table 5.1 outlines the most important tasks for FCA.

Concept Lattice Tasks

Description

Follow Path

Display concept hierarchy for a given concept Find specialization/generalization Find antecedents or descendants for a given concepts

Filter

Find concepts satisfying some conditions on objects and attributes Find Classes Given a set of items, find the frequent co-occurrence patterns Characterize Distribution Given a concept and a quantitative attribute, find the distribution of the items in the concept Cluster Find similar concepts Correlate Items Determine useful relationships between concepts Scan Quickly review a set of items Set Operation

Find the intersection of two or more concepts

Although concept lattice analysis share some similarities with graph analysis, they differ on a few important points. For example, graphs have much more topological importance than lattices, so finding neighbours or central nodes or clusters does not make much sense in concept lattice analysis. Concept lattice analysis in turn, has much more browsing and correlation tasks requirements. A comprehensive study on low-level task for FCA remains to be done in the literature.

Participatory Design

Once the subset of tasks the interface should act upon are identified, the first prototypes can be designed. In the participatory design sessions users are encouraged to create their own version of the interface and communicate its behaviour. Although this technique is not intended to literally design the interface, it provides a good understanding on how users expect the interface to behave, what are the expected inputs and outcomes. Figure The main features were identified across the three use cases, in a way that the prototyping focused in the commonalities rather than individual aspects. The following table (Table 5.2) summarises the differences between the three use cases given five high-level features:

Data browsing, lattice exploration, multiple facets, visual analytics and search.

Early Evaluations

This section describes the evaluation methodology in the early stages of the development process. Sections 5.3,5.4 and 5.5 provide an in-depth discussion on each use case with further evaluation results.

Test Users

Operators from the Space Control Center at SAS, biologists and bio-informaticians at Heriot-Watt University took part in the evaluation. These two populations have different background experience with analytic systems as operators are far more experienced than both biologists and bio-informaticians. This poses a challenge to the design: How can the interface be simple enough so that less experienced users make good use of it and at the same time allowing experienced users to use its advanced functions? The solution we propose, as we will see later in this chapter, consists on a set of configurable views for each use case and user skill.

Procedure

In an evaluation, data is gathered from users which reflects their judgement of their usage of the evaluated product [START_REF] Hackos | User and task analysis for interface design[END_REF]. The first evaluation was carried with the aid of a leader user for each use case to conduct the evaluation in place.

Before the evaluation, we provided some material about Cubix, including a short tutorial describing its main functionalities.

To evaluate the features of our first version of the prototype, we have used a sample of a traffic accident dataset 2 and conduced an analysis for most common causes between different combinations of attributes (e.g. road surface, weather, accident severity, etc).

FCA allowed us to answer pattern identification questions such as "What can be considered the main causes of accident severity: serious' ?" or "how many accidents are 'light conditions: darkness' and 'accident severity: serious' ?".

The evaluation consisted of three parts: 1) A leader user from each use case provided three tasks that should be performed using Cubix with the dataset provided; 2) The users performed the assigned tasks while communicating their thought process 3 as we record audio and screen capture; 3) A survey (Appendix D) is collected from users and conduct an interview with the leader user.

2 Traffic accidents dataset released by the Department for Transport: http://data.gov.uk/dataset/road-accidents-safety-data 3 Also known as the "Think Aloud" method [START_REF] Fonteyn | A Description of Think Aloud Method and Protocol Analysis[END_REF] Some examples of tasks are:

• How many accidents are "light conditions: darkness" and "accident severity: serious" ? Do you think this should be another way of doing this task? How?

• What can be considered the main causes of accident severity: serious"?

• How likely is an and "accident severity: serious" occur during weekends (Sat-Sun)?

• What about the surface conditions of the fatal accidents?

• What the probability of causing serious or fatal accidents when it snows?

• what are the differences between accidents on Saturday or Sunday?

The choice of a common, unfamiliar dataset for the evaluation was intended to avoid domain-specific bias when performing the tasks in the prototypes.

Evaluation Results

Below, we outline the results of the quantitative evaluation for each component. The detailed evaluation for each use case is described in the following sections. EMAGE documents the result of an experiment using a series of textual annotations.

Each annotation is a triple: gene tissue-level of expression. For the sake of brevity, both genes are referred to by short names or identifiers rather than their full name. For example, the gene bone morphogenetic protein 4 is referred to as Bmp4. Tissues are often present in several Theiler Stages and there can be multiple instances of a tissue in a single Theiler Stage. Thus each TS has its own anatomy called EMAP and each tissue is uniquely identified by an EMAP number. For example the orbito-sphenoid bone in TS 23 is EMAP:8385.

A number of computational methods have been proposed to help biologists discover unexpected patterns and formulate interesting hypotheses. Popular techniques employ unsupervised classification methods such as clustering, to group and visualise co-expressed genes (see [START_REF] Prelić | A systematic comparison and evaluation of biclustering methods for gene expression data[END_REF] for a survey). The main limitation of most clustering algorithms is that they do not allow clusters to overlap, a counter-intuitive idea in this domain as genes are not restricted to a specific function and usually take part in several biological processes when interacting with other genes. User-defined constraints, such as object exclusion, attribute exclusion and attribute restriction, applied to the data, allow different analyses to be carried out and the creation of sub-contexts which only focus on particular portions of the data. Next, In-Close is applied to the context file generated in the previous step. Using a trial and error approach, the user has to find an appropriate minimum size to mine a small number of large concepts, i.e., find the largest co-expressions of genes within the data. Finally, a third tool, Concept Explorer 7 was used to visually display the corresponding concept lattice.

Whilst the above workflow required three standalone tools and FCA expertise, the same workflow can be achieved through a combination of different techniques provided by Cubix. Most of the complexity has been hidden, empowering the biologists to run the entire workflow themselves. Additionally, whilst FCA could only be visualised via a static lattice, Cubix provides a series of analytical features and is able to deal with the implicit relationships and inconsistencies in the EMAGE data.

In this case study we investigated how Cubix can address the challenges of gene expression analysis, through filtering and clustering of large amounts of data, interactive exploration of co-expressed genes and display of relevant statistics.

Querying and Converting the Gene Expression Ontology Data to Formal Contexts

In contrast with traditional FCA, which takes as input a binary table of objects and attributes, our approach is based on the querying of ontology data which is then converted to a formal context in a process transparent to the user. The conceptual analysis of ontologies provides unique information of gene expression data, by grouping entities belonging to particular properties in a hierarchical fashion and highlighting patterns of co-occurrence for those groups. Because biologists have little or no knowledge of SPARQL, the language we use to query ontologies, a set of pre-defined queries are available.

The procedure consists in translating each object o, attribute a and their incidence relation I in the result table such as o ∈ G and a ∈ M , to create the formal context K = (G, M, I). As the number of variables in a query can be arbitrary, Cubix has an option that allows users to select whether a given column in the result table is an object column, attribute or none. Contrarily to traditional FCA tools, in Cubix the formal context is transparent to the user. The data is displayed in a table where its rows contain attributes, followed by attribute values and objects, in the columns (Figure 5.7). We found that this structure is more accessible to non-FCA experts. Filtering, sub-selection and conversion operations are possible through functionalities that came from the aforementioned tool FcaBedrock. The formal context, once created, is passed to the concept miner, which returns the number of formal concepts to the user. If the number of formal concepts is too high, the user can exclude from the computation concepts with fewer than a user-specified number of attributes and objects (so-called minimum support), to simplify the context further.

Apart from the user being able to manually define minimum-support criteria, in Cubix, the minimum-support feature is being reconfigured to be automatically calculated and applied to the formal context without user intervention.

Visual Analysis of Expression Clusters

Using Association Rules to Highlight Gene Expression Occurrence Patterns

The use of association rules analytics brought complementary insights to the analysis of gene co-expression clusters. For example, after filtering the rules generated for the context in Figure 5.7 by confidence down to a manageable size, results revealed a few interesting facts. A significant amount (75%) of the genes detected in the embryo were also detected in the primitive endoderm (Figure 5.10) in TS9. This is not surprising, since the later tissue is part of the former in the anatomy hierarchy. On the other hand, another rule showed that 71% of the genes detected in the mesoderm were detected also in the ectoderm (against 62% the other way around) in TS9. This follows an intuitive reasoning since both tissues are part of the same organ.

Discussion

This use case demonstrated the use of Cubix to the analysis of gene expression data where overlapping groupings are generated by Formal Concept Analysis and interactively analysed in Cubix. Cubix's workflow allows users to carry out an analysis starting from querying a semantic database, converting it into a formal context, simplifying the context to make it manageable, and visualising the result as a concept lattice and associated relevant statistics.

Existing tools for genes expression analysis, such as Cytoscape 8 and Orange 9 have specific advantages, e.g. Cytoscape can run efficient analysis in network data and Orange is a machine learning tool with some predictive features. In contrast, Cubix operates at a conceptual level and it is less data-mining centric and more analytics oriented (i.e, dashboards, drill-down, selection and filtering, etc). Besides, those tools are designed to run locally whereas Cubix is being designed to run on a cluster of computers eventually in the cloud. This will allow scalable analysis of data of orders of magnitude higher than the mentioned tools.

Although most of the functionalities in Cubix can be used with other data than EMAGE (with the corresponding scaling of data), as future work we will extend our experiments to other genes expression data sets like cancer and brain development. We also intend to provide a public web service API to allow interoperability with other platforms.

For further information about this use case see [START_REF] Melo | A conceptual approach to gene expression analysis enhanced by visual analytics[END_REF].

Case Study: A Visual Analytics Approach for Aircraft Cabin Design

This case study is part of the Complex System Design Lab (CSDL) 10 project which involves 27 industrial and academic partners and aims at providing a collaborative environment for complex system design. Since the simulation of design choices usually outputs large and high dimensional datasets, the CSDL platform should allow efficient analysis of such datasets to identify the right conception choices.

CSDL industrial partners have provided a use case which corresponds to a commercial aircraft cabin air control system. In this use case, the goal is to identify relevant design configurations which ensure comfort conditions in terms of air temperature and velocity inside the cabin. Typical fields of temperature and velocity are obtained using the same fluid model as in (Bui et al.) to the comfort. Moreover, a measure of the energy consumed by the air-conditioning system is also considered to estimate the price at which this comfort comes.

As we discussed previously, in FCA, complex data needs to be transformed into a boolean matrix in the scaling process. In order to provide flexible scaling we used a concept miner algorithm based on Similarity Formal Concept Analysis (SFCA) introduced by [START_REF] Messai | Many-valued concept lattices for conceptual clustering and information retrieval[END_REF]. SFCA considers similarity to directly classify non-binary data into lattice structures called Many-Valued Concept Lattices (MV lattices) using a similarity threshold θ for each multi-valued attribute.

Besides extending FCA to complex data and avoiding the loss of information due to truncation in FCA scaling, SFCA produces MV lattices with different granularity levels (i.e. similarity levels) to allow progressive data exploration.

In this use case we investigated the usefulness of Cubix to provide a support for combining numerical values (quantitative) analysis together with qualitative analysis to aid decision makers in the process of complex system design. In particular, we show how Cubix can be used to highlight crucial information a designer may need to validate design choices. The analysis is facilitated by a novel visualization for MV concepts.

Simulation Dataset of the Aircraft Cabin Test Case

The use case dataset corresponds to the simulation results of 100 randomly chosen configurations of design parameters (the 13 input parameters). 9 output criteria have been defined to assess the quality of each configuration in terms of passengers comfort and energy cost. The mean values of temperature and velocity of each of the four seats are computed which resulted in 8 criteria associated with the comfort of the passengers.

The dissipated energy is computed based on the velocity as a measure of the loss of energy due to the fluid viscosity.

In order to quickly appreciate the comfort in each seat and hence simplify the dataset exploration and the experiments evaluation, comfort scores were computed for the values of the comfort output criteria (temperature and velocity). The scores are in a three points scale (0: uncomfortable, 1: acceptable, 2: comfortable) computed according to ANSI/ASHRAE Standards (ASHRAE, 2004) as follows:

score(T) =              0 if T < 21 or T > 24 1 if 21 ≤ T < 22.5 or 23.5 < T ≤ 24 2 if 22.5 ≤ T ≤ 23.5 score(V) =              0 if V > 1 1 if 0.2 < V ≤ 1 2 if V ≤ 0.2
These rules can be translated as expressions for a given score in Cubix (Figure 5.12). The score is then computed for each concept in the lattice and it may be used for filtering or assigning colours according to the resulting value. If two or more expressions are satisfied for a given concept, the last added rule has the priority.

Extracting Comfort Classes and Their Corresponding Design Parameters' Ranges

Our objective is to determine the design parameters that are important to qualify the experiments such that all of the four passengers seats are satisfied. We make the assumption that the temperature is more important than the velocity to define the thermal comfort of the passengers. Therefore, we focus our analysis on the experiments that offer the maximum comfort for the passengers from the temperature point of view only: we By analysing this MV lattice, it turns out that S silver can be described using three

Identifying Comfort Classes Using the "Heat map" Visualization

When the relevant concepts are identified, i.e. the comfort classes in our case, the analyst will take decisions based on concepts that fit best his or her goals.

The filtering capabilities provided by Cubix helped the analytics to boil down the large number of concepts to a handful of concepts. The task of the analyst is then to identify which concepts contains the parameters within the intervals he or she is looking for.

For example, for the parameters of air speed and temperature, large ranges mean that comfort may be compromised. On the other hand, smaller ranges indicate stronger guarantees on comfort. The heat map visualisation described in Section 4.2.2 has been useful in this context. Figure 5.14 shows the concepts as an array of square rectangles where each rectangle represents an attribute, its width is proportional to the size of the interval and the colour indicates the average (median) value of the interval, varying from blue to red. This representation allows to straightforwardly read the maximal ranges of variation of all the design parameters together with the corresponding comfort score for temperature and air speed in each concept.

Discussion

In this use case we presented a visual and conceptual approach for decision support applied in a collaborative complex system design project. The approach takes advantage of the use of Similarity-based Formal Concept Analysis (SFCA) to classify, visualize, and explore simulation data in order to help system designers to identify relevant design choices.

The approach is illustrated on an aircraft cabin design case study which concerns the simulation of different configurations of the ventilation system to study the passengers comfort in the cabin. The classification of simulation data with their corresponding comfort scores using Cubix allows to derive for each simulated input parameter the maximal interval of values which guarantee an acceptable comfort level.

We implemented a new visualisation for MV lattices that consists on the filtering and assigning colours to concepts based on user-defined scores. A colour gradient is assigned according to the "global score" of a concept. For instance, the score of "maximum comfort" is attributed when the scores of velocity and and temperature are equal to 2 and the colour. This simplification is important because in Complex System Design the number of parameters are usually overwhelming to the analyst to overview and compare. Alternatively, users can filter concepts that are below a score threshold. This is particularly important during the extraction of comfort classes.

The obtained results have been evaluated by new simulations which converged to the same solutions in terms of passengers comfort as well as in terms of input parameters ranges. Details of this study can be found in [START_REF] Messai | Conceptual analysis of complex system simulation data for decision support: Application to aircraft cabin design[END_REF]. It may happen that the payload manifests an unforeseen thermal situation. For example, when the temperature of one or several sensors changes in an unusual way, albeit within the nominal limits. The operator is then charged with finding similar occurrences inside the telemetry archive and with the determination of typical thermal and power profiles.

Analysing such a large number parameters is a tough task even to the most experienced operator. Figure 5.16 shows the user interface of the SOLAR monitoring system. Whenever there is an anomaly, it is important for the operators to quickly retrieve information about the telecommands sent during a specific time period and the results of those commands. Other examples of unexpected behaviour include:

• A telemetry parameter was out of its predefined soft values;

• An error code was issued by SOLAR;

A clear need is to find patterns of failure in the flow of telemetry parameters with the aim to transpose these to the prediction of future failures (forensic analysis). This is a common problem in many stream mining systems such as aeronautics, military surveillance, biochemical analysis and fraud analysis.

Several anomaly detection techniques have been proposed in literature. Some are based on machine learning algorithms, such as neural networks [START_REF] Zhang | A hierarchical anomaly network intrusion detection system using neural network classification[END_REF], distancebased algorithms to detect outliers [START_REF] Lazarevic | A comparative study of anomaly detection schemes in network intrusion detection[END_REF] or adapted clustering algorithms [START_REF] Wu | Factor-analysis based anomaly detection and clustering[END_REF] (See [START_REF] Ahmed | Machine learning approaches to network anomaly detection[END_REF] for a review).

In this use case, we apply Formal Concept Analysis to retrieve the combination of parameters that indicates an anomalous behaviour. The analysis of all possible combinations of parameters is boiled down to a handful of formal concepts.

Telemetry Dataset

SOLAR has been operational for more than four years, already, sending one telemetry packet every second or so. Over a year, this represents approximately 3.10e7 packets.

Each telemetry packet contains 343 parameters. 44 parameters do not change at all or very rarely. Among the others, 135 have binary readings, such as ON and OFF.

Others are continuous valued attributes. Example of parameters include: temperature, power supply, pointing device telemetry and system variables for the different parts of the device.

Telemetry data from the SOLAR payload is managed by Space Applications Services (SAS). A subset of the data, covering the 30-day period (26-Sep-2008/ 25-Oct-2008) related to the particular SOVIM failure, has been provided to the CUBIST project.

Anomaly Detection with Real-Time Distributed Computation of

Concepts

Our approach consists in simulating the telemetry stream to identify which pairs of parameters-values are related to an anomaly. Anomalies are characterized by a particular attribute in the transaction. We also investigate the sequence of concepts that preceded a anomaly, in an attempt to predict new anomalies. Because anomalies occur very rarely, we filter concepts according to maximum support rather than minimum support.

The anomaly detection mechanism works as follows. We applied the approach described in Chapter 3 to mine formal concepts in the current sliding window.

Whenever an anomaly occurs, all current concepts in the window are stored in a monitor data structure (a linked list) in the sequence they appeared prior to the error. Then, whenever a new transaction appears in the window, the algorithm checks for the occurrences in the monitoring table sequentially. The assumption is that if an anomaly occurs, looking at the sequence of previous concepts may be a good indicator of when the next anomaly may occur. Figures 5.17 New transactions in the stream are matched with those in the monitoring table. If a sequence of transactions in the stream matches with any subsequence of concepts in the monitoring table, a signal is send to the interface to indicate increase in the risk of a new anomaly. Otherwise, if the order of concepts arriving in the stream does not match with the one in the monitoring list, the risk signal set to 0.

Experiments showed that the real-time analysis of telemetry data can be useful to restrict the number of parameters that need to be analysed when an anomaly happens. In one experiment, operators discovered that variation in voltage in two connected circuits may lead to an increase in the temperature in another device, which eventually causes it to overheat and trigger an error.

We implemented a user interface to show the current concepts in the window, the stored sequence of concepts when the last anomaly happened and the risk status (Figure 5.18).

As explained before, if any upcoming transaction matches with the sequence, the risk signal is incremented and displayed in form of a gauge.

In this first version of the UI, operators had difficulty in tracking every change in the concepts within the current window, as concepts may change too frequently 11 . As future work, we plan to use a time-sensitive sliding window that updates the window every hour, so operators can carefully investigate each concept in the current window.

We are currently investigating the minimum number of attributes that are most likely to cause an anomaly. In the experiments, concepts related to an anomaly had between 50 and 200 pairs parameter-value. Heuristically, operators can discard most of the a attributes. For instance, "SOLAR PB1 Ovtemp" is a flag to indicate if the temperature of the internal PB1 device is above normal conditions. It is therefore expected that the parameter "SOLAR PB1 temp" used to indicate PB1's temperature, displays a high temperature value. Reducing the number of attributes that are not involved in the occurrence of an anomaly can greatly improve operators' productivity in discovering the causes of it.

Discussion

Our real-time approach helped operators to identify the combination of parameters that could potentially cause a breakdown. In most cases there is no explicit correlation between the parameters and the error; it is assumed that the co-occurrence of certain pairs of parameters-values is most likely to cause an anomaly. Operators can use Cubix for further analysis on static telemetry data, once the monitoring parameters are known. Although it is hard to claim that the sequence insight worked due to the limited amount of data available for the experiments, the preliminary results are encouraging. It provided insights on how some anomalies are related to a sequence of concepts, e.g. the variation off the voltage of a particular device may lead to its malfunction.

One important issue that appeared during our experiments concerns the scaling of continuous attributes. Some sequences of transactions did not match those in the monitoring structure because of a small difference in the way the scaling was done. For example, a given temperature attribute is scaled in equals intervals of 10 degrees, e.g., "Temperature:[20-30]". A new transaction containing "Temperature=31" will be scaled to the interval "Temperature:[30-40]", and two concepts are considered unrelated even if their difference is only one degree in temperature (among 342 other attributes). We believe that a more flexible approach would be more effective in comparing different, albeit similar concepts. Similarity Formal Concept Analysis (SFCA, [START_REF] Messai | Conceptual analysis of complex system simulation data for decision support: Application to aircraft cabin design[END_REF]), used in the aircraft cabin design use case in Section 5.4 is a alternative to consider.

SFCA is able to mine concepts over continuous attributes using a similarity threshold instead of scaling data.

Chapter Summary

This chapter presented the three use cases where our approach was evaluated. Cubix was used to highlight genes co-expression clusters, filter and highlight patterns in genes expression data. Cubix was also used in the design of complex systems, where the number of simulation parameters was reduced to a few concepts. The visualisation of multi-valued lattices helped the analyst to take decisions about which intervals of parameters they want to guarantee for each comfort class. Finally, the distributed approach was used as an attempt to predict possible failures from telemetry data in real-time.

Chapter 6

Conclusions and Future Work

Recap

The advances in technology for creation, storage and dissemination of data have dramatically increased the need for tools that effectively provide users with means of identifying and understanding relevant information. As more institutions are incorporating realtime solutions in their business practices, many traditional data mining methods are simply not suitable to this end. New data mining methods have to be developed taking into account the strict constraints that stream processing requires: one pass algorithm, limited memory space and incremental changes.

Formal Concept Analysis (FCA) is a relatively young discipline and has drawn the attention of Business Intelligence (BI) analysts because of its simplicity and unique insights it provides. In FCA, the concept lattice displays the generalization and specialization relationships among objects and their attributes. This hierarchical structure can provide reasoning for classification and clustering, implication discovery and rule learning.

Concept mining is a computationally intensive task and the vast majority of existing algorithms do not take advantage of parallel processing techniques.

The present thesis addressed the problem of mining and analysing formal concepts over a data stream. The proposed approach is comprised of several distributed components that carry the computation of concepts from a basic transaction, filter and transforms data, stores and provides analytic features to visually explore data. The distributed architecture is built on top of a real-time platform called Storm.

In addition to the concept mining architecture, we proposed several visual analytics techniques to enhance data understanding and exploration in FCA. These analytics features allow filtering, selecting, searching and clustering concepts in the concept lattice and association rules. We have proposed new visualisations such as the Matrix of concepts, the Sankey lattice and the Heat map visualisation for multi-valued concepts.

Transforming a concept lattice into a tree can be useful for browsing large concept lattices. In our experiments we explored statistically motivated criteria to evaluate single parent concepts in the tree extraction process. A case study on the web tourism domain demonstrated the usefulness of the tree extraction method.

Based on our participatory design session, we developed a visual analytics tool for FCA called Cubix. Cubix's workflow allows users to carry out an analysis starting from a real data set, converting it into a formal context, simplifying the context to make it manageable, and visualizing the result as a concept lattice. Cubix can also generate formal contexts from SPARQL queries to a triplestore.

Finally, we presented three use cases that demonstrate the application of the approach in real-world settings: aircraft cabin design, where new visualisations for continuous data helped analysts to quickly identify classes of comfort for passengers; Genes co-expression analysis using a combination of both analytics features and semantic integration; and real-time telemetry data analysis for anomaly detection. Experimental evaluations show that our approach is useful and provides better insights than current state of the art in FCA.

Summary of Contributions

In a nutshell, the contributions of this thesis are:

Distributed concept mining over data stream:

• Distributed concept mining architecture;

Visual Analytics:

• New visualisations for concept lattice and association rules;

• Combination of visual analytics features with conceptual metrics;

• Tree extraction algorithm from concept lattices;

• Visual analytics tool for Formal Concept Analysis: Cubix.

Although there is a growing interest on distributed frequent itemset mining over data stream, such systems are still in their infancy, and a lot of exciting work remains to be done in the design, implementation, and visualisation. I hope that this thesis will serve as a reference for the state of the art for both researchers and practitioners interested in building visual analytics and distributed Formal Concept Analysis systems.

Limitations and Future Work

Improvements in the Frequent Itemset Mining Algorithm. In the future, the algorithm could be improved by incorporating extra canonicity tests to assess if a itemset may become a closed itemset in the future. The PFCbO algorithm [START_REF] Outrata | Fast algorithm for computing fixpoints of galois connections induced by object-attribute relational data[END_REF]) and CFI (Jiang and Gruenwald, 2006b) are good examples of how a good canonicity test can drop the computation cost when mining formal concepts. Also, with some changes, the CET Nodes can be represented in the FP-tree, thus reducing the storage space needed.

Performance Benchmarks. We are currently evaluating the performance and scalability of our approach in comparison with the state of the art algorithms. To provide a fair comparison, we implemented a distributed version of the Moment algorithm [START_REF] Chi | Catch the moment: maintaining closed frequent itemsets over a data stream sliding window[END_REF]. The datasets are provided by the IBM Quest Synthetic Data Generator1 , which is commonly used in the benchmarks of data stream mining algorithms. The results of this evaluation are going to be published along with the benchmark code.

Large Concept Lattice Visualisation. We plan to explore other visual metaphors and more sophisticated navigation and interaction techniques for dealing with very large lattices (up to 10k concepts), and ways to navigate and zoom into different levels of concepts clusters. We also plan to release the tool under an open source license. A recent paper by [START_REF] Liu | immens: Real-time visual querying of big data[END_REF] showed how interactive visualisations for big data can

"

  Better try and fail To worry as life passes by Better still try in vain To sit down and wait until the end I prefer walking in the rain To hide in sad days I'd rather be happy, mad though, To a conformity life." Distributed Computation of Formal Concepts and Analytics by Cassio Melo Les progrés de la technologie pour la création, le stockage et la diffusion des données ont considérablement augmenté le besoin d'outils qui permettent effectivement aux utilisateurs les moyens d'identifier et de comprendre l'information pertinente. Malgré les possibilités de calcul dans les cadres distribuées telles que des outils comme Hadoop offrent, il a seulement augmenté le besoin de moyens pour identifier et comprendre les informations pertinentes. L'Analyse de Concepts Formels (ACF) peut jouer un rôle important dans ce contexte, en utilisant des moyens plus intelligents dans le processus d'analyse. ACF fournit une compréhension intuitive de la généralisation et de spécialisation des relations entre les objets et leurs attributs dans une structure connue comme un treillis de concepts. Cette thèse aborde le problème de l'exploitation et visualisation des concepts sur un flux de données. L'approche proposée est composé de plusieurs composants distribués qui effectuent le calcul des concepts d'une transaction de base, filtre et transforme les données, les stocke et fournit des fonctionnalités analytiques pour l'exploitation visuelle des données. La nouveauté de notre travail consiste à: (i) une architecture distribuée de traitement et d'analyse des concepts et l'exploitation en temps réel, (ii) la combinaison de l'ACF avec l'analyse des techniques d'exploration, y compris la visualisation des règles d'association, (iii) des nouveaux algorithmes pour condenser et filtrage des données conceptuelles et (iv) un système qui met en uvre toutes les techniques proposées, Cubix, et ses étude de cas en biologie, dans la conception de systèmes complexes et dans les applications spatiales. Real-time Distributed Computation of Formal Concepts and Analytics by Cassio Melo

I

  have spent part of my Ph.D studies at UCSD -databases lab, where I had an great experience as a researcher. I would like to thank professor Yannis Papakonstantinou, Kian Win and the FORWARD team for the opportunity, knowledge and pleasant moments we shared together. I would like to thank the members of the CUBIST project (Combining and Uniting Business Intelligence with Semantic Technologies). They have been very enthusiastic of this work and made it possible. I would like to thank my loved ones, who have supported and encouraging me with their best wishes. A special thanks to Dina, who reviewed this work over and over giving me excellent suggestions. Last but not least, I would like to acknowledge the European Commission 7th Framework Programme of ICT for funding the integrity of my Ph.D thesis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Current Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5 Overview of the Proposed Solution . . . . . . . . . . . . . . . . . . . . . . 8 1.6 Thesis Organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 Background on Formal Concept Analysis 11 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Terminology and Formalism . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 Concept Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.4 Overview of FCA algorithms . . . . . . . . . . . . . . . . . . . . . . .

3 . 2

 32 An illustration of a Damped model for stream processing. Circle indicates a transaction, diameter indicates its weight. Grey nodes represent the transactions that are out of the window. . . . . . . . . . . . . . . . . . . 3.3 An illustration of the Sliding Window model. . . . . . . . . . . . . . . . . 3.4 An example of a FP-Tree after reading each transaction. . . . . . . . . . 3.5 An illustration of a Storm topology with bolts and spouts. . . . . . . . . . 3.6 System architecture showing system's components (in blue) and the requests between them. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Itemset generation phase. AC is not generated because of ABC. . . . . . . 3.8 An example of a FP-Tree with itemsets {a,b} and {b,c,d}. . . . . . . . . . 3.9 An example of a Closed Enumeration Tree (CET). Dashed nodes: Unpromising gateway nodes; Borderless: Intermediate nodes; Solid rectangles: Closed Itemsets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.10 An example of adding a new transaction {a,b,d} to the FP-Tree. Support and Tidsum are updated for existing nodes and a new node is appended. 3.11 Changes on the CET when adding transactions. Consider minimum support = 2. Dashed circles: Infrequent gateway nodes; Dashed squares: Unpromising gateway nodes; Borderless: Intermediate nodes; Solid square: Closed nodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.12 Changes on the CET when deleting transactions. Minimum support = 2. Dashed circles: Infrequent gateway nodes; Dashed squares: Unpromising gateway nodes; Borderless: Intermediate nodes; Solid square: Closed nodes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Visualisation of a concept lattice using matrix. . . . . . . . . . . . . . . . Last century was pivotal in the course of humanity. World War I and World War II were the deadliest moments in history, yet these were notable landmarks in the development of new technologies. The need of secure transmission of information motivated the emergence of the field today known as cryptography. The first cryptographic machine, Enigma, was invented by a German at the end of World War I and used by Britain's codebreakers as a way of deciphering German signals traffic during World War II. It has been claimed that thanks to the information gained through this machine, the war was reduced by two years.

Figure 1 . 1 :

 11 Figure 1.1: Lifecycle of different Business Intelligence paradigms: Classical BI; Semantic BI and Real-time BI. The scope of this thesis is highlighted in red.

.

  The novelty of the work consists of: (i) a distributed processing and analysis architecture for mining concepts in real-time; (ii) the combination of FCA with visual analytics and exploration techniques, including association rules analytics; (iii) new algorithms for condensing and filtering conceptual data and (iv) a system that implements the proposed visual analytics techniques, called Cubix, and its use cases in Biology, Complex System Design and Space Applications.

  2 provides an overview of FCA algorithms and their place in modern computing systems. This chapter defines what formal concepts are mathematically and describes the main concept mining algorithms. It also describes the challenges when mining concepts in the light of big data applications. Chapter 3 describes the proposed approach for the real-time distributed computation of formal concepts. It provides an overview of the main paradigms and data structures used for frequent itemset pattern mining over data stream. The frequent itemsets mining algorithms we examine are based on candidate generation, batch algorithms, closed frequent itemset (CFI) and CFI over a sliding window model. The distributed architecture of the proposed approach is built on top of a real-time platform called Storm. At the end of the chapter, benchmarks of the approach compared with current state of the art algorithms are presented. Chapter 4 presents the Visual Analytics techniques developed in this thesis. The chapter starts by providing an overview on the current state of art of concept lattice drawing algorithms. New proposed visualisations are explained such as the concept-matrix and the concept-sankey visualisation. Several analytics features that allow filtering, selecting,

Figure 2 . 1 :

 21 Figure 2.1: Concept lattice for the life in the water context. Dark background labels represent attributes, white background labels represent objects.

Figure 2 . 2 :

 22 Figure 2.2: Concept lattice containing 83 concepts.

Algorithm 1 :

 1 NextClosure Data: A closed subset B such that B ⊆ M . begin /* Print or list < B ′ , B > as a formal concept */ print(< B ′ , B >) i ←-|M | success ←-F alse while not success and i > 0 do

  line 11). It then creates a new pair (C, D) = ((B ∪ {i}) ′′ , B ∪ {i}) (lines 9-10). If the canonicity test 4 passes (line 11) the algorithm selects the pair as concept candidate and continues the execution with the new concept as input (line 12). In the example, the algorithm implemented is recursive. Ganter's algorithm computes the set of all concepts in time O(|G| 2 |M ||L|), where |L| is the size of the concept lattice, and has polynomial delay O(|G| 2 |M |).

Algorithm 2 :

 2 Close-by-One Data: A concept < A, B > such that A ⊆ G and B ⊆ M and an attribute y ∈ M . begin /* Print or list < A, B > as a formal concept */ print(< A, B >)

Figure 2 . 3 :

 23 Figure 2.3: Bit-array illustration for the set S = {a, c, d, e}.

  modifies the original CbO (Algorithm 2) splitting it into two parts, one (Map function) responsible for the iteration over the attribute set and concept generation (equivalent to lines 1-10 of CbO's algorithm); and the other (Reduce function) performs the canonicity test (equivalent to line 11 of Algorithm 2). If the canonicity test passes then the input pair is passed on to the next iteration. Experiments showed that the distributed variant significantly outperforms the original version with at least five computing nodes. Since the problem of computing formal concepts can be translated to the computation of closed frequent itemsets of their intents, research in distributed frequent itemset mining can

  years, and current FCA tools are mostly limited to the Hasse diagram representation (Figure 2.4).

Figure 2 . 4 :

 24 Figure 2.4: Tools for visualising concept lattice.

  authors use visual analytics in an indexed document collection to display concept lattices in a global view and concept details in a local view. The system expands/collapses information according to selections made in the concept lattice. Toscana (Becker and Correia, 2005) and ConExp 6 also use concept lattice representations but do not provide further interaction and other visualisation features (Figures 2.5(a) and 2.5(b) respectively). These tools focus on the usability of concept lattices and consider them as primary interface for interacting with a formal context. A more interactive tool, ConfExplore 7 uses animated transitions and incremental lattice exploration (Figure 2.5(c)). More recently, Bach (2010) introduces a FCA tool, called Facettice, for faceted navigation and lattice exploration for multidimensional taxonomies (Figure 2.5(d)).

  (a) ToscanaJ. Nested line diagram. (b) Conexp. Drawing options of the left, concept lattice in the center and attribute/object selection on the right. (c) Confexplore. On top, drawing options, concept lattice in the center and attribute/object selection on the right. (d) Facettice. On the left, the facet and value hierarchy, Facet Lattices on top, the concept lattice in the center and the lists of results on the right.

Figure 2 . 5 :

 25 Figure 2.5: Visual Analytic tools for Formal Concept Analysis.

Figure 3 . 1 :

 31 Figure 3.1: An illustration of the Landmark model (circle indicates a transaction).As a new transaction arrives it is added to the processing.

Figure 3 . 2 :

 32 Figure 3.2: An illustration of a Damped model for stream processing. Circle indicates a transaction, diameter indicates its weight. Grey nodes represent the transactions that are out of the window.

  Sliding Window model operates on a dynamically selected set of transactions, called transaction window. New transactions are added to the window while others are removed. Sliding window models are further classified into two categories: transactionsensitive and time-sensitive (Figures 3.3(a) and 3.3(b) respectively). The transactionsensitive type is bounded by a fix number of transactions, in a FIFO data structure, while the time-sensitive window is dictated by fixed units of time, which may lead to a varying number of transactions in the window.

Figure 3 . 3 :

 33 Figure 3.3: An illustration of the Sliding Window model.

Figure 3 . 4 :

 34 Figure 3.4: An example of a FP-Tree after reading each transaction.

  , called New-Moment. The NewMoment algorithm uses a bit-sequence representation for itemsets in order to meet the requirement of limited memory space of the maintenance of closed frequent itemsets generated. Experiments show that NewMoment outperforms the original Moment algorithm and has smaller memory footprint. Jiang and Gruenwald (2006b) propose a new algorithm for mining closed itemsets in a sliding window, called CFI-Stream. When performing addition and deletion operations, the CFI-Stream algorithm checks each itemset in the transaction on the fly and updates the associated closed itemsets supports. Current closed itemsets are maintained and updated in real time in a prefix-tree called DIrect Update (DIU) tree. In contrast with Moment, CFI-Stream maintains only closed itemsets in the structure and checks closure as a new transaction arrives. Author's benchmark shows that CFI-Stream and Moment algorithm have comparable running times, but CFI-Stream requires less storage space.

  the authors propose an algorithm that exploits the lexicographic order relation combined with the closure climbing technique which obtains closure generators for itemsets. This algorithm uses an in memory data structure called GC-Tree (Generator and frequent Closed itemsets Tree) to store all the frequent closed itemsets in the current sliding window. Gupta et al. (2010) proposed an algorithm, CLICI (Concept Lattice based Incremental Closed Itemset), for mining all recent closed itemsets in landmark window model. The algorithm uses a decay function to assign higher weights to recent itemsets. The synopsis data structure, called CILattice, stores all recent closed itemsets in the stream. Periodically, the lattice is traversed and all nodes having a support count less than threshold are are removed from the lattice.

  are three abstractions in Storm: spouts, bolts, and topologies. A spout is a source of streams in a computation. A bolt processes any number of input streams and produces any number of new output streams. Most of the logic of a computation is into bolts, such as functions, filters, streaming joins, database calls, etc. Each bolt may have one or several instances running in parallel. A topology is a network of spouts and bolts, with each edge in the network representing a bolt subscribing to the output stream of some other spout or bolt. In Storm, topologies run indefinitely when deployed. Figure3.5 illustrates a Storm topology for the distributed computation of concepts. Each bolt is introduced below and explained in detail in the following sections.Each bolt runs sequentially with regard to a given transaction, but many transactions are processed in parallel in this schema. A memory dataset is employed to keep the data structures synchronized across the bolts. This adds an extra challenge to manage the state synchronized and to manage "race conditions" 6 . The orange colour indicate which bolts access the memory dataset.

Figure 3 . 5 :

 35 Figure 3.5: An illustration of a Storm topology with bolts and spouts.

SubsetGenBolt.

  It generates and stores the subsets of items of a given transaction by traversing the Closed Enumeration Tree (CET) described in Section 3.4.3.4. It emits the transaction. IncrementBolt. It increments the support count and tidsum of the nodes in the FPTree and emits the current transaction to AddToCETBolt. AddToCETBolt. Responsible for appending the transaction to CET and carrying the necessary changes. It may emit a tuple to SubsetGenBolt when necessary. DecrementBolt. It decrements the support count and tidsum from the oldest transaction in the sliding window. It emits the oldest transaction in the sliding window to the RemoveFromCETBolt.

Figure 3 . 6 :

 36 Figure 3.6: System architecture showing system's components (in blue) and the requests between them.

Figure 3 . 7 :

 37 Figure 3.7: Itemset generation phase. AC is not generated because of ABC.

Figure 3 . 8 :Table 3 . 2 :

 3832 Figure 3.8: An example of a FP-Tree with itemsets {a,b} and {b,c,d}.

  Figure 3.9: An example of a Closed Enumeration Tree (CET). Dashed nodes: Unpromising gateway nodes; Borderless: Intermediate nodes; Solid rectangles: Closed Itemsets.

Algorithm 4 :

 4 ScalingBolt Data: A transaction T , intervals mapping M and a dictionary D. begin /* Scaling of multi-valued attributes */ foreach multi-valued item t ∈ T do find the interval [a, b] in M where a ≤ t < b replace t by the interval [a, b] end /* Replace string representation */ foreach item t ∈ T do replace t by the corresponding string in the dictionary D end send modified transaction T to FPTreeBolt end 3.4.5 Update FPTree After the transaction has been manipulated by the ScalingBolt, it is sent to FPTree-Bolt which adds the itemset to the FP-Tree mentioned before. The algorithm iterates over each item in the transaction, finding its way through the paths of the FP-Tree in a top-down fashion. If the current item in the transaction exists in the FP-Free, it updates the tidsum and support for the node, otherwise, it appends a new node with the current item and proceeds to the next item in the transaction. Figure 3.10 illustrates the addition of a new transaction in the FP-Tree. Notice that the existing {d} node have its "next" pointer updated to the newly created node.

Figure 3 . 10 :

 310 Figure 3.10: An example of adding a new transaction {a,b,d} to the FP-Tree. Support and Tidsum are updated for existing nodes and a new node is appended.

9Figure 3 . 11 :

 311 Figure 3.11: Changes on the CET when adding transactions. Consider minimum support = 2. Dashed circles: Infrequent gateway nodes; Dashed squares: Unpromising gateway nodes; Borderless: Intermediate nodes; Solid square: Closed nodes.

Figure 3 . 12 :

 312 Figure 3.12: Changes on the CET when deleting transactions. Minimum support = 2. Dashed circles: Infrequent gateway nodes; Dashed squares: Unpromising gateway nodes; Borderless: Intermediate nodes; Solid square: Closed nodes.

Figure 4 .

 4 1 shows a new matrix visualisation for concept lattices, where objects are displayed in rows and attributes in columns. Each formal concept is depicted as coloured, overlapping layers in the relation. This visualisation also reacts to mouse over and highlights the same concept in other object × attribute squares.

Figure 4 . 1 :

 41 Figure 4.1: Visualisation of a concept lattice using matrix.

Figure

4. 2

 2 shows an example of this visualisation for a concept lattice.Any Hasse drawing algorithm can be used as a basis for the Sankey diagram for concept lattices, provided the following changes: The diagram is rotated 90 counter-clockwise, so it is read from left to right. The width of a node is equal to the sum of the thickness of the edges connecting to it. Edges follow a Bézier path to give an idea of flow. The space between the layers are noticeably larger than the usual Hasse diagram.

Figure 4 . 2 :

 42 Figure 4.2: Visualisation of a concept lattice using the Sankey diagram. Edges thickness is given by the confidence value of the implication between two concepts.

Figure 4 . 3 :

 43 Figure 4.3: A "heat map" visualisation for concept lattice. Colour indicates position in the range (from blue to red), width shows the length of the interval.

Figure 4 . 4 ,

 44 rule id15 has the highest confidence. It represents the implication between {dance} and {electro} music. The matrix visualisation provides a good overview of the ruleset and the integration with the analytics features allows filtering and drilling down of rules. The second visualisation is a Radial graph showing how attribute-value pairs imply one to the other (Figure 4.5). The confidence of a rule is represented by the thickness of the connecting line. The connecting line is a gradient from purple to yellow, to indicate premise and conclusion respectively. The algorithm to generate this visualisation has a special treatment to position labels. The X, Y coordinates of a label and the angle of rotation is given by the following equations:

Figure 4 . 4 :

 44 Figure 4.4: Visualisation of Association Rules using the Matrix visualisation.

Figure 4 . 5 :

 45 Figure 4.5: Visualisation of a concept lattice using the Radial graph visualisation.

Figure 4 . 6 :

 46 Figure 4.6: Illustration of labels positioning in the Radial AR Visualisation.

  lattice. More recently,[START_REF] Bach | [END_REF] proposed an interface, called Facettice, for faceted navigation and data analysis using interactive Hasse diagrams. In the diagram, nodes have additional information encoded as bar charts to depict the distribution of values for a given attribute in the concept. Additional attribute-lattices 2 are visualised and allows filtering by node clicking.

Figure 4 . 7 :

 47 Figure 4.7: Dashboard for FCA a) Distribution chart, b) Co-occurrence chart, c) Comparison chart and d) Attribute implication graph.

Figure 4 . 8 :

 48 Figure 4.8: Concept lattice enhanced with visual variables depicting different properties.

Figure 4 . 9 :

 49 Figure 4.9: Search in the concept lattice.

Figure 4 .

 4 Figure 4.10: Visual filter bar.

Figure 4 .

 4 Figure 4.11: Lattice filter bar.

  we explain in the next section, we propose different criteria to extract trees from lattices and visualise the resulting trees. Trees are inherently simpler hierarchical structures than Hasse diagrams and due to their applicability in many domains, there is a plethora of tree representations. These include: indented outline trees, sometimes called "tree lists" (common in file browsers such as windows Explorer), traditional layered node-link diagrams in 2D or 3D (e.g. ConeTrees -[START_REF] Robertson | Cone trees: animated 3d visualizations of hierarchical information[END_REF]), spatially transformed tree diagrams (e.g. Radial trees[START_REF] Bachmaier | Drawing phylogenetic trees[END_REF]) as well as several space optimization (Space Optimized trees Nguyen and Huang (2002)) and space-filling tree visualisation techniques (e.g. TreeMaps[START_REF] Johnson | Tree-maps: a space-filling approach to the visualization of hierarchical information structures[END_REF]).

  and 4.13, which represent two distinct trees extracted from the lattice of Figure4.12. Notice that the concept C6 is lost in the tree extraction process illustrated in Figure4.14.Trees are displayed in three different forms: the left one (Figure4.13(a)) represents the tree as extracted from the lattice, the one in the middle (Figure4.13(b)) is the traditional representation of a tree without crossing links, and the visualisation on the right (Figure4.13(c)) shows the layers of the tree as concentric arcs, from the most generic (outer layers) to the most specific (inner layers). The size of each arc is proportional to the number of children in the corresponding sub-tree.

Figure 4 .

 4 Figure 4.12: Original concept lattice.

Figure 4 .

 4 Figure 4.13: An example of tree extraction without concept loss.

Figure 4 .

 4 Figure 4.14: An example of tree extraction with concept loss.

Figure 4 .

 4 Figure 4.15: Tree extracted using the one parent selection per layer approach.

  Selection based on Stability and Support

  (a) The formal context of Animals (b) The concept lattice of Animals

Figure 4 .

 4 Figure 4.16: An example of Concept Lattice.

Figure 4 .

 4 Figure 4.17: Tree-extraction process and Sunburst visualisation.

4. 5 . 4

 54 Case Study of the Tree Extraction Process on the Tourism Web Pages Data Set

Figure 4 .

 4 18 shows the Hasse diagram of a lattice containing 2,214 concepts and 7,758 links, constructed from a corpus of 126 web pages dedicated to tourism, characterized by their most common words from 60 words extracted from thesaurus.

Figure 4 .

 4 Figure 4.18: Concept lattice for the tourism web pages data set.

Figure 4 .

 4 Figure 4.19(a) shows the tree generated with extent support as parent selection criterion.

Figure 4 .

 4 Figure 4.20(a) depicts the tree generated by the similarity criterion. Parent concepts

Figure 4 .

 4 Figure 4.19: Trees generated from the lattice in Figure 4.18 using Support and Stability as parent selection criteria. Colour is assigned for each concept for comparison.

  Figures 4.19(a) and 4.19(c)).

Figure 4 .

 4 Figure 4.20: Trees generated from the lattice in figure 4 for each proposed measure.

Figure 4 .

 4 Figure 4.21: Cubix user interface displaying the adult data set. Its main components: 1) Toolbar; 2) Visualisation canvas; 3) Dashboard; 4) Selection & entities bar and; 5) Filter bar.

Figure 4 .

 4 Figure 4.21 shows the layout organisation of Cubix and its main components. All panels are collapsible allowing a novice user to view only the concept lattice or, to an expert user, several tools can be displayed on the screen.

Figure 4 .

 4 21 -2 displays the selected visualization for the concept lattice (sunburst). The other visualizations available are: Hasse diagram, Matrix, Sankey, Icicle and Tree. A filter bar (Figure 4.21 -5) has two functions, first it allows the filtering of concepts through the visual selection of attributes; second, it displays the current conceptual distribution for each attribute. As seen in Section 4.4.4, it is possible to perform text searches of attributes in concepts, with an auto-completion feature to help users easily search for both attributes and values in concepts. The results are dynamically highlighted as the user searches in the different concept nodes.

  Similar to the concept lattice analytics, all interface controls work analogously with association rules(Figure 4.22). The semantic dashboard adapts to the analysis of association rules, for instance, one chart displays support, stability and confidence on a scatterplot matrix. If an item from the chart is selected it filters the association rules to be displayed.

Figure 4 .

 4 Figure 4.22: Association Rules Analytics in Cubix.

  This chapter provide details of each of the three use cases that demonstrate the application of the proposed techniques in a real-world setting. The three use cases are: a) Aircraft cabin design (Complex Systems Design Laboratory, CSDL), where new visualisations for continuous data helped analysts to quickly identify classes of comfort for passengers; b) Genes co-expression analysis using a combination of both analytics features and semantic integration (Heriot-Watt University, HWU); and c) Prediction of possible failures from telemetry data in real-time (Space Application Services, SAS).

5. 1 Figure 5 . 1 :

 151 Figure 5.1: Prototypes designed by the users of the biological use case (HWU).

Figure 5 . 2 :

 52 Figure 5.2: UI Component Questions.

Figure 5 . 3 :

 53 Figure 5.3: UI Component Questions.

Figure 5 . 4 :

 54 Figure 5.4: UI Component Questions.

Figure 5 . 5 :

 55 Figure 5.5: UI Component Questions.

Figure 5 . 6 :

 56 Figure 5.6: An Illustration of an Annotated Schema for In situ Gene Expression Data in Theiler Stage 14.

Figure 5 . 7 :

 57 Figure 5.7: Genes, tissues and level of expression in Theiler Stage 9.

Figure 5 .

 5 Figure 5.8 visualises a tree as a Sunburst[START_REF] Stasko | An evaluation of space-filling information visualizations for depicting hierarchical structures[END_REF] extracted from the concept lattice using support as parent selection criteria. The context in Figure5.7 was filtered to focus on gene Bpm4. In this visualisation, each concept is an arc and the hierarchy is represented from the innermost to the outermost layer.

Figure 5 .

 5 Figure 5.8: A radial-filling "Sunburst" visualisation of the gene expression data with colours depicting clusters.

Figure 5 .

 5 Figure 5.9: A radial-filling "Sunburst" visualisation of the gene expression data with colours depicting clusters.

Figure 5 .

 5 Figure 5.10: Genes, tissues and level of expression in Theiler Stage 9.

  and the comfort design problem is parametrized by 13 continuous parameters each evolving in a range interval of possible values.These design parameters are: angles of air injection at 4 passengers' personal fan (Alpha 1..4), blown air speed at 4 passengers' personal fan (Uair 1..4), temperature of blown air at main inlet(Tair In), temperature of blown air at 4 passengers' personal fan (Tair P), blown air speed at main inlet (Uair In), external temperature (T ext), and fuselage thermal conductivity (Kappa F). The mean values of temperature and velocity for each of the four passengers' seats (seeFigure 5.11) have been computed to assess the passengers' comfort, which resulted in eight output criteria (two per passenger) related 10 http://www.systematic-paris-region.org/fr/projets/csdl

Figure 5 .

 5 Figure 5.11: Aircraft cabin schema and the main simulated input parameters.

Figure 5 .

 5 Figure 5.12: Creating conceptual scores in Cubix.

Figure 5 .

 5 Figure 5.13: MV lattice generated on S silver .

Figure 5 .

 5 Figure 5.14: The MV concept view for the lattice in Figure 2. Colour indicates position in the range (from blue to red), width shows the length of the interval.

5. 5

 5 Case Study: Real-Time Concept Analysis for Anomaly Detection in Space Telemetry Data Three instruments make up the solar observatory (SOLAR, Figure 5.15) payload in the International Space Station (ISS). These instruments, SOVIM, SOLSPEC and SO-LACES, measure with a remarkable degree of accuracy the spectral energy irradiance of the Sun, over virtually the entire spectrum. These studies are of primary importance for atmospheric modelling, atmospheric chemistry and climatology. Over the last three years, the SOLAR science teams have gathered precious data during the minimum of solar activity. It provided the most comprehensive measurements available about the solar minima of 2008-2010 and at the time this thesis is written, it has been recording information about the solar maxima of 2012-2013.

Figure 5 .

 5 Figure 5.15: Solar observatory device (SOLAR) attached to the International Space Station.

Figure 5 .

 5 Figure 5.16: SOLAR monitoring system.

  (a) and 5.17(b) illustrate the process.

  (a) A transaction with a error (A,E) enters in the window. (b) All concepts preceding the anomaly are monitored.

Figure 5 .

 5 Figure 5.17: Monitoring concepts in the current window prior to an anomaly.

Figure 5 .

 5 Figure 5.18: Anomaly Detection UI.

Figure D. 1 :

 1 Figure D.1: UI Component Questions.

Figure D. 2 :

 2 Figure D.2: Visualisations Questions.

  . . 17 2.4.1 Batch Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4.2 Incremental Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 20 2.4.3 Assembling Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.4 General Remarks on FCA Algorithm's Performance . . . . . . . . 23 2.5 Current Issues in FCA for Big Data Analysis . . . . . . . . . . . . . . . . 24 Lifecycle of different Business Intelligence paradigms: Classical BI; Semantic BI and Real-time BI. The scope of this thesis is highlighted in red. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1 Concept lattice for the life in the water context. Dark background labels represent attributes, white background labels represent objects. . . . . . 2.2 Concept lattice containing 83 concepts. . . . . . . . . . . . . . . . . . . . 2.3 Bit-array illustration for the set S = {a, c, d, e}. . . . . . . . . . . . . . . 2.4 Tools for visualising concept lattice. . . . . . . . . . . . . . . . . . . . . . 2.5 Visual Analytic tools for Formal Concept Analysis. . . . . . . . . . . . .

	List of Figures
	1.1

2.5.1 Size and Complexity of Data . . . . . . . . . . . . . . . . . . . . . 24 2.5.2 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5.3 Noisy and Missing Data . . . . . . . . . . . . . . . . . . . . . . . . 27 2.5.4 Parallel and Distributed Computation of Concepts . . . . . . . . . 28

Table 2 .

 2 1: Example of a formal context.

	Life in Water	needs water to live	lives in water	lives on land	needs chlorophyll	dicotyledon	monocotyledon	can move	has limbs	breast feeds
	fish leech	×

  authors presented the AddIntent algorithm. The algorithm

	uses new heuristics to identify all modied concepts (in order to add o to their extents)
	and all canonical generators of new concepts (in order to generate every new concept
	exactly once).
	AddIntent approaches this problem by traversing the diagram graph of L i in a recursive
	fashion. Whenever the algorithm finds a non-canonical generator, it uses the diagram
	graph to find the canonical generator of the same concept. It then works only with
	concepts above that canonical generator, ignoring all other concepts above the non-
	canonical generator. AddIntent's time-complexity is O(|G| 2 |M ||L|).

Table 2 .

 2

					2: A 'noisy' and a 'quiet' context
	1	2	3	4	5	6
	a

Table 3 . 1 :

 31 Transactions table.

	TID	Items
	1	{a,b}
	2	{b,c,d}
	3	{a,c,d,e}
	4	{a,d,e}

  Algorithm 5: SubsetGenBolt Data: CET node n I and a transaction T . begin if n I is unpromising gateway or infrequent then J that has the same support as n I and J ⊃ I (line 4). If so, mark it as unpromising gateway node (line 5) 9 . Otherwise, if a child node n ′ I does not contain all items of n I but has the same support, mark n I as a intermediate node (lines 6 and 7). If none of the above conditions are satisfied, n I is a closed node. If n I is currently marked as an unpromising gateway node, we need to generate its powerset (line 11) and check if any of its children is a closed node by looking at the hash table (line 15). If so, mark n I as unpromising gateway and return. The worst-case time complexity of the AddToCETBolt is O(N ) (without powerset generation).

	return
	end
	lastIdx ← index of an item t in T which is the last item of n I
	for j ← lastIdx to |T | do
	curItem ← T[j]
	if n I has no children containing curItem then
	newNode ← n I ∪ curItem
	/* Store newN ode and add it as child of n I Algorithm 7: AddToCETBolt Store(newNode) Data: Itemset n I and transaction I. AddChild(n I , newNode) begin		*/
	/* Continue the recursion with the newly generated itemset foreach node n ′ I child of n I do SubsetGenBolt(newN ode, T ) AddToCETBolt(n ′ I ) else /* n ′ I , T ) SubsetGenBolt(n ′ I is the child node of n I containing curItem if hashCheck(n ′	*/ */
	end
	end
	emit to SubsetGenBolt(n ′ I ) 3.4.7.1 Adding a Transaction to the Sliding Window end
	mark n ′ I as closed
	/* Check if a new child is closed	*/
	if hashCheck(n ′ I ) = true then mark n ′ I as unpromising gateway
	end
	Algorithm 6: IncrementBolt end Data: Itemset n I and transaction I. begin end
	foreach node n ′ I child of n I do update support and tidsum of n ′ I if n ′ emit to generateSubsetsBolt(n ′ I ) I is newly frequent then Figure 3.11 illustrates the updates in the CET after reading each transaction.
	end
	end
	AddToCETBolt(I)

To add a transaction in the CET, the IncrementBolt updates the tidsum and support of the corresponding nodes (Algorithm 6 -line 3). If a node becomes frequent, its powerset needs to be generated by the SubsetGenBolt (line 5).

end

The AddToCETBolt is a depth-first procedure that visits itemsets in lexicographical order and update node properties. It goes recursively through the leaves of the tree until the top. The function hashCheck( ) checks if if there exists a previously discovered closed itemset n I ) = true then mark n ′ I as unpromising gateway else if Exists a child node n ′′ I with same support as n ′ I then mark n ′ I as intermediate else if n ′ I is unpromising gateway then /* This branch was prunned, needs to be generated again. */

  If there is no child with the same support as n ′ I , it remains closed and its entry in the hashtable is updated (line 17).

	Algorithm 9: RemoveFromCETBolt
	Data: Itemset n I and transaction I.
	begin
	foreach node n ′ I child of n I do
	if n ′ I is an unpromising gateway or infrequent gateway node then
	continue
	else if hashCheck(n ′ I ) = true then mark n ′ I as unpromising gateway mark all descedants of n ′ I as Idle
	else
	foreach node n ′′ I child of n ′ I do RemoveFromCETBolt(n ′′ I , I)
	end
	if n ′ I is closed then if there is child node n ′′ I of n ′ I with the same support as n ′ I then mark n ′ I as intermediate remove n ′ I tidsum and support from hashtable
	else
	update n ′ I tidsum and support on hashtable
	end
	end
	end
	Figure 3

If the current node n ′ I is closed and there is a child n ′′ I with the same support as n ′ I , mark n ′ I as intermediate and remove its entry in the hashtable (lines 12-15).

Table 4 .

 4 1: General recommendation for parent selection criteria.

	Criteria	Description	Rationale	Suitable
				for
	Stability

  ).

	7 toscanaj.sourceforge.net
	8 iro.umontreal.ca/ ~galicia 9 www.source-forge.net/projects/conexp
	10 www.code.google.com/p/openfca
	11 www.source-forge.net/projects/fcabedrock

Table 5 .

 5 1: Low-Level Analytic Tasks for Formal Concept Analysis.

Table 5 . 2 :

 52 General recommendation for parent selection criteria.

	Use	Data	Lattice	Multiple	Visual	Search
	Case	Browsing	Explo-	facets	Analytics
			ration
	CSDL	×			×	×
	HWU	×	×	×	×	×
	SAS	×			×

  5.3 Case Study: Genes Expression Analysis Enhanced by Visual AnalyticsA gene is a unit of instructions that directs the body how to do one essential task, i.e. create a protein. Gene expression information describes whether or not a gene is expressed (active) in a location. There are many types of gene expression experiment.

This case study focused on a technology called in situ hybridisation (ISH) gene expression. Completed ISH experiments are published online. For the mouse, one of the main resources in this field is EMAGE 4 .

Formal concepts are also known as closed itemsets. The data mining community often uses the word "item" for what we call "attribute" here. "Itemsets" are thus just the subsets of M.

Statement valid for the particular formal context in question.

The canonicity test checks if a given concept is closed, in that none of its immediate supersets has the name support as the current concept.

The noisy/missing data problem is often referred in the FCA literature as fault tolerance, although this term is commonly used in distributed systems. In this thesis, we refer to "fault tolerance" as the ability of a distributed system to keep running even when some of its computation units are shut down.

http://conexp.sourceforge.com

http://code.google.com/p/openfca/

Apache Hadoop. http://hadoop.apache.org

Heuristically the worst case scenario is highly unlikely for most applications. In text mining, however, computation may lead to worst case scenario.

http://github.com/nathanmarz/storm

Redis provides a built-in sorted collection, called ZSET, which insertion time is proportional to the logarithm of the number of elements.

Concept Explorer (ConExp) -www.conexp.org

If a concept is not selected as a single parent by any of its children concepts, it is removed from the lattice

The implicit tasks are those that the user cannot easily express in an interview because they are not the focus of attention, e.g. checking if there are new notifications in the monitoring system.

http://www.emouseatals.org/emage/

http://sourceforge.net/projects/fcabedrock

http://sourceforge.net/projects/inclose

http://www.cytoscape.org

http://orange.biolab.si

http://sourceforge.net/projects/ibmquestdatagen/

Acknowledgements

Abbreviations

8. Next to the data/use case currently implemented in the system, do you see any content from your daily life (private and professional) to be integrated in the system in future? Why do you think this would be benefit? 9. For which kind of tasks from you daily work do you believe the system can be especially useful? Please describe the tasks and the possible benefit shortly:

10. For which kind of tasks from your daily work do you believe the system is annoying / ineffective? Please describe the tasks and the possible drawbacks shortly:

Appendix D

Post-Evaluation Surveys