The vast amount of data generated over the last decades has brought new challenges to the analytics science. Visual data analysis and knowledge representation employ methods such as Formal Concept Analysis (FCA) in order to identify groupings of patterns from the analysis process [14]. FCA provides an intuitive understanding of generalization and specialization relationships among objects and their attributes in a structure known as a concept lattice. A concept lattice is traditionally represented by a Hasse diagram illustrating the groupings of objects described by common attributes. A Hasse diagram is a graph where concepts appear as vertices on the plane connected by line segments or curves. The layout of the partially ordered set may be seen as a layered diagram [2]. Lattices visualization becomes a problem as the number of clusters grows significantly with the number of objects and attributes. Interpreting the lattice through a direct visualization of the line diagram rapidly becomes impossible and more synthetic representations are needed.
In this work we propose alternatives to the traditional lattice representation, firstly by enhancing the readability of concept lattices though colouring and distortion techniques; secondly by extracting and visualizing trees derived from the lattices structure. The tree extraction from the original lattice has some unique advantages: it eliminates all edges crossing and the resulting hierarchy is also easier to interpret and to represent. Moreover, this representation still provides an overview of the dataset, highlighting significant properties of the lattice. In order to extract trees from lattices, we define a set of parent concept selection criteria, including the stability and support indexes [1,4] provided by FCA literature, confidence index as well as topological features of the lattice.
The paper is organized as follows. Section 2 provides background on lattice representations; Section 3 proposes a set of criteria for transforming concept lattices into trees; Section 4 discusses colouring and distortion techniques for enhancing interpretations of lattices. Section 5 presents instantiations of the suggested criteria and visualizations in the biology domain, followed by a discussion in section 6. Section 7 finally concludes and presents perspectives for future work.
As mentioned above, FCA analysis produces lattices, usually represented as layered directed acyclic graph graphs, named Hasse diagrams, that illustrate 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 as illustrated in figure 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 flying birds, containing Finch and Eagle objects, is more specific than the one which contains all birdsflying or not-, and thus contains a smaller number of objects (the first concept has an extra one, the ostrich). This partial order provides different levels of abstraction and native navigation links from a given concept.
As mentioned earlier, such diagrams are usually layered graphs, where concept vertices are assigned to horizontal layers according of the number of common attributes, 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 as is the case in more real word applications [13], which leads to reduced graph readability and aesthetics [3].
To reduce the complexity of lattices, simplified diagrams can be produced by displaying only concepts with a sufficient support [4]. Visualisations can also be restricted to portions of the data [5], and concept number reduction is possible by incorporating conditions into the data mining process [6]. Finally, conceptual measures can be applied to identify the most relevant concepts and filter outliers [7].
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 [8][9][10]. However these techniques do not provide a clear view of the entire lattice.
Other FCA visualization approaches map the distances between concepts to visual variables, in order to highlight patterns. For example in [11] 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 visualization, e.g. showing both a general Hasse diagram and a tag cloud for representing the neighbours of a specific concept (for a review see [12]).
Our approach consists in representing lattices not as Hasse diagrams, but as trees. We use different criteria to extract trees from lattices, and visualize 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.
Trees are a common and easily understandable visual representation. We consider them as a visualization alternative to large cluttered concept lattices, which preserves all lattice entities and some of its structure. In order for a tree visualization to be an effective alternative to a lattice, the extraction of the tree from the lattice needs to preserve the most essential features of the original structure. The present approach consists in extracting a tree from a concept lattice by choosing one single parent concept for each concept of the lattice. We start from the most specific concepts i.e. the parent concepts of the lower bound of the lattice, at the bottom of the Hasse diagram and select a single parent concept for each of them, and reproduce this recursively. Choosing a single parent concept at each step leads to an information loss. 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. Before proceeding, we briefly recall the FCA terminology [14]. Given a (formal) context K = (G,M, I), where G is called a set of objects or extent, M is called a set of attributes or intent, and the binary relation I ⊆ G×M specifies which objects have which attributes, the derivation operators (•)' are defined for A ⊆ G and B ⊆ M:
In the following sections we consider various strategies for selecting parent concepts, including the stability and support indexes from FCA literature, confidence, as well as topological features of the lattice.
The stability index measures the proportion of subsets of objects of a given concept whose derivation is equal to the intent of this concept [1]. In other words, the stability indicates the probability of preserving a concept intent while removing some objects of its extent. We recall the definition of stability:
Card is a cardinality function. The stability index of (A,B) is defined as:
Using the lattice in figure 1 as an example, we calculate the stability for concepts 2 and 4 in order to select a parent for concept 5 (0.25 and 0.5 respectively); we keep the one with highest stability, in this case we therefore remove the edge between concepts 2 and 5. 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. Another measure which can be used for assigning to each concept a unique upper neighbor is the notion of 'support' [4]:
The use of support as parent selection criteria may lead to trees containing concepts that have fewer specialization levels since in general, generic concepts have higher support values than their most specific counterparts [4]. Concept stability and support measures have been widely used in FCA and their combination has been promising [1] in reducting the lattice.
This approach relies on clustering parent and child concepts which share most of their attributes or objects. Parent and child having a great number of attributes in common are supposed to be grouped together following the principle of similarity clustering and local predictability [15]. Its definition is:
In the same animal's context illustrated by the lattice in figure 1, we have potential parent concepts 2 and 4 sharing the same number of objects with concept 5, but concept 4 has more attributes in common with 5, so it should be chosen as the unique parent of concept 5.
The confidence value of a concept estimates how likely an object which has an attribute set A, also has an attribute set C [14]. In other words, it tries to measure how strong the implication of the parent attributes in the child objects is. For instance, considering the lattice in figure 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.
An advantage of this method is its consistency with the interpretation of concept lattices. Taking our animals context as example, there is a 50% probability that an animal that is a flying bird is also a flying and preying bird. By contrast, an animal that is preying has only 33% of chance to be also a flying bird.
Common graph drawing 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 visualizations, 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 ConExp1 . In our work we use these as well as other visual variables in a Hasse diagram to represent possible tree extraction criteria. This provides several benefits to lattice and extracted tree understanding. First, it enables users to rapidly associate the dimension/criteria in question (e.g. stability, support in Figure 2) with concepts, thus justifying the choices made during the tree extraction process. Second, visualizing different extraction criteria using various visual variables, allows users to compare these criteria in order to choose the one that better fits their needs. Third, irrespective of the tree extraction process, matching visual attributes to concept attributes establishes a benchmark/comparison among concepts, making it possible to compare at a glance different concepts, even if they do not have a link in common, as well as gain insights on the whole lattice itself. Finally, prominent features of the lattice like specialization and generalization can be better understood: for instance the power of implications of different concepts can be rendered by edge thickness. The concept node itself can be a visual metaphor for the intent and extent. In the example of figure 2, a pie chart replaces the traditional box representation to depict the proportion of objects (blue) and attributes (yellow). In this way users can be guided in understanding and choosing criteria for extracting trees to simplify the lattice representation.
In this section we discuss a case study of a concept lattice to qualitatively examine the nature of the trees resulting from different criteria. The techniques for lattice transformation and drawing were implemented in a visual analytics tool called CUBIST Analytics and applied to a dataset containing 8 animals and 9 attributes which produced a lattice with 19 concepts (figure 3). Each of the measures proposed revealed particular aspects on the analysis of a lattice, illustrated in table 2.
Table 1 a) shows the tree generated with stability as parent selection criterion. In practice, it resulted in a tree with very stable concepts more likely to retain their subsequent children. For instance, the concept {lives in land} was the preferred parent of the concept that holds our notion for amphibians: {lives on land, lives in water} because it is more stable than its counterparts.
The measure of shared objects was the criterion that generated the tree in table 1 b). Parent concepts sharing most objects with child concept were the preferred candidates. As an example, the concept {lives on land} shares more objects with {lives on land, needs chlorophyll} than concept {needs chlorophyll} does, therefore it was the chosen parent in this case. Table 1 c) the tree was generated from confidence criterion, therefore children nodes are associated with the parent with which the relationship of confidence is the highest among the candidates. As a result, the relation {can move, has limbs} has a stronger implication in {lives on land} than {lives on land} has for {can move, has limbs}, for example.
Some may argue that due to the tree construction, the present approach breaks the original lattice meaning, and therefore subsequent mathematical models based on this structure. It is noteworthy to observe however, that only the links in the lattice graph structure are removed and the lattice structure remains semantically valid, since there is no need to take out the attributes or objects that concepts have in common with their parents.
The choice of parent selection criteria for tree transformation corresponds to a classification problem to some extent. Deciding if a Lion is more "mammal" than it is "preying" it's 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 mammal which are "closer" to Lion than other concepts, then it may reasonable to be chosen as its parent. As general recommendations, one should use the criteria that best fits to their analysis task (table 2).
Table 1. Examples of trees generated from the lattice in figure 3 for each of the proposed measure.
In addition to the tree-extraction strategies, the use of colours, size, shaping and thickness for both nodes and edges in the original lattice to represent the criteria metrics (such as stability, support, specialization or implication) can enhance the interpretation of a concept lattice, and aid users in their choice and interpretation of the created trees.
The labelling strategy for identifying concepts should be taken into account as well. Merely placing attributes and objects names on concepts may be cumbersome for large lattice analysis (used in most FCA visualizations). In this case, it is recommended to represent the concept's intent and extent with visual metaphors like the pie chart shown in figure 2.
It 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.
Confidence It measures how strong the implication is between a parent concept in a child concept.
Implication is one of the desired interpretation of a concept lattice.
Traditional software in FCA makes little use of visualization techniques, producing poorly readable lattice graphs when the number of concepts exceeds a few dozens. In this work we have presented a transformation approach to extract trees from concept lattices, attempting to minimize both semantic and conceptual loss in favour of readability and interpretation. We have also presented ways to visually show the extraction criteria in the original lattice. 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. Domain experts can thus visually explore larger datasets that traditional visualizations of concept lattice cannot represent effectively. Each of the tree construction measures proposed in our work provides particular insights valuable to different analysis tasks, identified in our paper as recommendations.
In the future we plan to combine two or more criteria for parent selection with other lattice reduction techniques (e.g. icebergs lattices [4]). We also plan to conduct user experiments to understand when users want to have full lattice views vs. tree views, which metrics for creating trees are of most interest to them and under which circumstances, and assess if our visual indications allow users to understand the extraction tree process.
Acknowledgments. This work is partly funded by the CUBIST project ("Combining and Uniting Business Intelligence with Semantic Technologies"), funded by the European Commission's 7th Framework Programme of ICT, under topic 4.3: Intelligent Information Management.'