This paper presents a tool for creating and visualising formal concept trees. The concept tree provides an alternative visualisation to the more commonly known concept lattice. The tool described here is an extension of the In-Close formal concept mining program, where concepts are output in a format that can be visualised in a Web Browser using the Collapsible Tree Layout from the D3.js JavaScript library. Because the visualisation is expandable and collapsible, the tool is able to deal with large trees and the user is able to explore branches with single mouse clicks and by panning and zooming the tree. So-called 'iceberg trees' can also be produced, by specifying a minimum support for objects.
There are a number of tools that visualise and explore formal concept lattices,
such as the well known Concept Explorer [
There is also a problem in concept lattices regarding size and complexity: a lattice soon becomes too large and too complex to read and manage, or even compute, and although most of the lattice visualisation tools listed above have some means or other of attempting to address the problem (such as de-selecting attributes and objects in Concept Explorer), none of them are not really capable of handling a large number of concepts, either producing a ‘bird’s nest’ of indecipherable nodes and arcs, or simply unable to compute the structure in the first place.
This paper presents a tool that creates formal concept trees from formal
contexts and visualises them using the Collapsible Tree Format from the D3.js
JavaScript library. The tree is created as an output from a modified version of
the fast concept miner, In-Close2 [
The following sections describe the use of these two components with some well known FCA examples as illustration. 2
A tree, as a formal structure, is a set of nodes connected by arcs, such that each
node has a single parent node. A lattice can be thought of as a collection of
overlapping trees [
The latest version of In-Close, In-Close2.8, has the facility to output formal concept trees in JSON format for the D3.js Collapsible Tree Layout 1. The input for the process is a formal context in the well-known Burmeister cxt format. The tree format is simply one of the output options presented to the user when In-Close2.8 is run. Figure 2 shows the Command Line interface with the well known formal context Live-in-water being used as an example.
It is worth noting that, although concept trees have been described above as
originating from lattices that have had arcs removed, this is not how In-Close
creates a concept tree. In-Close does not compute the lattice at all, it simply
computes the first occurrence of each child concept, in the manner of
Close-byOne type algorithms [
The concept tree is output as a file called concepts.json ready to be uploaded to the JavaScript program. 3
The JavaScript program can be opened in a browser that supports HTML5 (e.g. Chrome but not Internet Explorer). The concepts.json file is uploaded and visualised using the ‘Choose File’ and ’Upload->Draw Tree’ buttons, see Figure 3. By default, the tree is initially displayed to the first level of concepts below the top concept. Figure 3 shows a concept tree created from the well-known Live-in-water context.
The concepts are numbered with the top concept being number 0. Concepts are labeled with attributes (upper line) and objects (lower line). If the concept is filled in with colour, it means that it can be expanded to another level in the tree by clicking the concept. Clicking concept 2 in the Live-in-water example expands it as shown in Figure 4, revealing more specialised sub-concepts that introduce more attributes. Notice that the objects ‘move’ from concept 2 to become labeled at the appropriate sub-concept. Thus ‘frog’ and ‘dog’ are now labeled at concept 8 since, as well as living on land, they can move and they have limbs.
Clicking on an un-filled concept will collapse the tree to that concept. Thus clicking now on concept 2 will collapse concepts 7 and 8 back up to it, restoring concept 2 to its state in Figure 3. Clicking on the top concept (concept 0) will collapse the tree to a single node.
To aid the user in exploring and managing the tree, holding a mouse button down allows the tree to be dragged anywhere in the Browser window and the mouse wheel can be used to zoom in and out.
When reading the concept tree, the normal rules of attribute and object inheritance apply: attributes are inherited down the branches of the tree, objects are inherited up the branches. Thus, again looking at concept 2 in Figure 4, the objects that need water to live and live on land are frog, dog, corn, reed and bean. Looking at concept 8, frog and dog can move, have limbs, live on land and need water to live.
Figure 5 shows the Live-in-water concept tree fully expanded (a result most quickly achieved by selecting the ‘Fully Expanded’ option before uploading the tree).
When reading a formal concept tree it is important to realize that attributes and objects can be labeled more than once, something not present in a lattice where the the requisite ‘many-to-many’ connections ensure they are labeled only once. Nevertheless, the concepts in a concept tree are exactly the same concepts as those in the corresponding concept lattice.
The tree is best read from top to bottom in a manner of attribute exploration, or specialization, of concepts. Thus, in Figure 5, concept 0 contains all the objects that need water to live, concept 4 contains all the objects that need water to live and can move, and concept 5 contains all the objects that need water to live and can move and have limbs. However, concept 5 does not necessarily tell
Fig. 5. Fully Expanded Live-in-water Concept Tree you about other attributes its objects may have. For example, a frog can also live in water (concept 1) and a dog can also live on land (concept 2). Although this issue is also present when reading a lattice, the extra connections in the lattice allow a user to determine those other attributes more easily. But, so long as this limitation is kept in mind, the concept tree is still a useful and readable visualisation.
The idea of a formal concept ‘iceberg’ lattice was described by [
Although pruning using minimum support will reduce the size of a tree,
information, of course, will be lost. However, every tree, no matter how large,
begins with a single node, and, so, with expandability and collapsibility, it
becomes possible to manage very large trees, expanding and exploring branches
of interest whilst leaving the rest of the tree hidden. Figure 7 shows a small
portion of a concept tree generated from the well known ‘mushroom’ data set from
UCI [
Fig. 7. Portion of the ‘mushroom’ Concept Tree clearly not be sensible to display in its entirety, the JavaScript program is able to store and manage the entire tree.
Notice that instead of displaying individual objects, the option to show ‘object count’ has been used, displaying the number of objects in a concept and the corresponding percentage of the population. The objects in this example are simply instances in a data set, so displaying long lists of their ID numbers makes little sense. The analyst is more interested in the statistical evidence of how attributes are distributed. 6
The concept tree tool is an addition to the FCA library of tools and provides a new automated approach to visualisation in FCA. Although the concept lattice is the natural visualisation of a concept hierarchy, the tree is a useful alternative that has not previously been provided in a tool. Trees are easily created from formal contexts using the In-Close2 concept miner and easily visualised in a Web Browser using the D3.js Collapsible Tree layout. The tool is able to manage trees with hundreds of thousands of nodes since size and complexity is dealt with by the expandable and collapsible nature of the layout and by the ability to prune trees by specifying a minimum support for objects in In-Close2.
The modified In-Close2 program is available at SourceForge 2 and the JavaScript program to visualise the tree in a Web-Browser can be accessed via the Web 3.