Even for small or medium sized contexts, the corresponding concept lattice soon becomes too large to be nicely displayed and understood, which renders a naive application of FCA for visual analytics challenging. Concept lattices depict all information of the underlying formal context. In certain settings, one can consider the context to be noisy or incomplete, and moderate and meaningful changes of the context such that the corresponding lattices significantly shrink in size and complexity are in those settings permissible. In this paper, such an approach is taken. The formal definitions for the approach are given, and using an implementation, several examples are provided which show the usefulness of the approach.
number of concepts shown to the user [8,9]. It is not only the number of concepts which often render the visualization of lattices complicated: Even with good layout algorithms, the Hasse-diagram of a lattice often contains a significant number of crossing edges, which is the main problem for the visual comprehension of graphs.
concept lattice to choose a uniquely given upper neighbor. By doing so, one can transform a lattice into a tree (with loss of information), which in turn can be better displayed compared to lattices. Finally, Boulicaut et al consider in [2,7] “noisy” formal contexts and directly change the incidence relation I in order to reduce the number of formal concepts. For CUBIST, in line with the approach of Boulicaut et al, Simon
which clearly shows the advantage of this approach.
In this paper, we follow up the notion of considering contexts to be noisy and to extend the incidence relation in order to simplify the derived concept lattices. In the next section, we provide the mathematical definition on how we change the incidence relation. As described in the following section, this approach has been implemented into a small FCA-tool in order to show its effectiveness. A thorough, though artificial example is given in the next section, before we turn to examples based on real data out of the CUBIST project.
2
Let a formal context (O,A,I) be given. Our basic idea is to understand the context to
be noisy or incomplete, and we are aiming at adding crosses to I such that the derived
lattice becomes smaller (hence, easier to read and understand). For an object o O
and an attribute a A, our starting point is the well-known equation
oIa
Ù
oII aI Ù
aII oI Ù
oI ĺ
a
(
DiffObj(o,a) := { x O | x oII and x aI } and
DiffAtt(o,a) := { y A | y aII and y oI }
The straight-forward approach taken in this paper, is, roughly speaking, as follows: the bigger DiffObj(o,a) or DiffAtt(o,a), the less we like to add an additional cross between o and a. In order to do so, it is possible to take only DiffObj(o,a) into account (this approach is reasonable in contexts having a small amount of attributes, but a large amount of objects, which is standard in traditional BI settings), or only DiffAtt(o,a), or both. Moreover, we can either relate DiffObj(o,a) and DiffAtt(o,a) to the overall sets of objects and attributes, i.e. taking a global approach, or relate them only to the concepts generated by o and a, i.e. taking a local approach. This gives rise to six different ways to measure “an approximate incidence measure” between o and a as follows:
GObj(o,a) := 1-( |DiffObj(o,a)/|O| ) GAtt(o,a) := 1-( |DiffAtt(o,a)|/|A| ) GObj,Att(o,a) := 1-1/2 ( |DiffObj(o,a)|/|O| + |DiffAtt(o,a)|/|A| ) LObj(o,a) := 1-( |DiffObj(o,a)|/| oII | ) LAtt(o,a) := 1-( |DiffAtt(o,a)|/| aII | ) LObj,Att(o,a) := 1-1/2 ( |DiffObj(o,a)|/| oII | + |DiffAtt(o,a)|/ | aII| ) Fig 1: Six approaches to measure the incidence between objects and attributes For any of these incidence measures S { GObj , GAtt , GObj,Att , LObj , LAtt , LObj,Att } we obviously have for all o,a:
0 S(o,a) 1 and S(o,a) = 1 Ù
oIa
JS,t := { (o,a) | S(o,a) t }
(
{ }൯ | | | = 1 െ |್ೀೕ |(ǡ ) = ܮ ܱܾ݆ (ǡ ܽ )
We will now exemplify (
Please note the following: x For o10, we have o10I ĺ a3 and o10I ĺ a1 , but not o10I ĺ a2 . This implication is violated by exactly one object, namely o10 itself. If we consider a threshold of 0.9 (that is, as we have 10 objects in total, we set a cross between o and a iff the condition oIĺ a is violated by at most one object), then we should add a cross between o10 and a2. Note that the high amount of objects which have a1 as attribute (i.e. o3 - o9) is not relevant. x For o1, we have o1Iĺ a3 and o1Iĺ a2 , but not o1Iĺ a1 . This implication is violated by exactly two objects, namely o1 itself, and o2. If we consider a threshold of 0.8 (that is, now we set a cross between o and a iff the condition oIĺ a is violated by two or less objects), then we should add a cross between o1 and a1 x A similar consideration applies of course to o2 .
The approximate incidence measure S:=GObj and the concept lattices for the incidence relations I=JS,1 , JS,0.9 and JS,0.8 is depicted in the next figure.
S := GObj
Fig 2: A simple example for GOBJ
number of formal concepts, and one can hardly make statements on how the concept lattices change. For the herein defined extensions of the incidence relations, the situation is different. We start with a simple result which does not generally apply to extensions of incidence relations.
Lemma: Let (O,A,I) be a formal context, let S { GObj , GAtt , GObj,Att , LObj , LAtt ,
let J:= JS,t . Then, for all o1,o2 O; we have o1I o2I Ö o1J o2J . Similarly, for all a1,a2 A we have a1I a2I Ö a1J a2J .
Let a A be an attribute . As we have o1I o2I and hence o2II o1II , we obtain DiffObj(o2,a) DiffObj(o1,a) and DiffAtt(o2,a) DiffAtt(o1,a); thus S(o1,a) S(o2,a) . Particularly, we get o1 J a Ù S(o1,a) t => S(o2,a) t Ù o2Ja. Q.e.d.
As stated in the introduction, a thorough investigation of the approximate incidence relations will be the subject of a different paper. Here we only provide a remark that even though we can prove statements about the relationship between I and JS,t which do not hold for I and any extension J I , the dependencies between I and JS,t have to be investigated further. For example, the author conjectured that we have PJ = PIIJ for all sets of objects P O, but the context in Fig 3, together with the approximate incidence measure GObj(o,a), shows that this equation does not generally hold. To see this, consider a threshold t=0.8, P:={o0,o1,o2}: we then have PIIJ = {o1, o2, o3, o4 } and PJ={o1, o2, o3, o4, o6, o7, o8 }
Fig 3: Counterexample for PJ = PIIJ 3
Fig 4: screenshot of a tool which implements approximate incidence relations
Fig 5: The different metrics as the appear in the tool
The slider allows to adjust the threshold t . A cell for an object o and an attribute a is marked grey iff S(o,a) 1 (where S stands for the selected measure). One can now either store only the single derived context with the incidence relation JS,t , or a set of derived contexts, where all thresholds 0.9, 0.91, …, 0.99 (these thresholds are manually chosen and so far hardcoded) and all six measures are used (thus, 60 Burmeister files are stored).
Fig 6: Example context and lattice for approximate incidence relations
Global local O b j e c t s A t t r i b u t e s o b j s a n d a t t s
Fig 7: All six approximate incidence measures for the example
Fig 8: Concept lattices for thresholds 0.8 and 0.9 and all six measures
The example of this section is based on the Heriot-Watt University use case in the research project CUBIST, in particular, it is built upon a real data set, namely embryo gene expression data. Gene expression information describes whether or not a gene is expressed (active) in a location. There is a fixed set of levels of expressiveness: A gene can in some location be detected, or more one can more precisely state that it is weakly, moderate or strongly detected. Moreover, it can be stated that a gene is not detected, that it is possible for the gene to be expressed, or that it is not examined. Based on public available data, we have generated a context where the objects are (names of) mouse genes (we have a total of 6613 formal objects in the context), the attributes are the seven different levels of expressiveness, and a cross is set between a gene and a level if that gene is detected in some location with that level of expressiveness. The resulting lattice, having 81 formal concepts, is depicted below.
Fig 9: Genes and Levels of Expressiveness without approximation
The lattice clearly shows a well-known challenge for FCA. Most of possible combinations of attributes are indeed instantiated objects in the context, often by few only, (the clarified context still contains 77 objects), which leads to an explosion of the number of concepts. Amongst the concepts, we have some formal concepts with large number of objects, but most concepts are rather small and render the lattice clutterd and hard to read. As we have many objects and only few attributes, it is sensitive to apply the global object-based measurement GObj to the context. With a (quite high) threshold of 97 already, the concept lattice is reduced significantly, as shown in Fig 10.
Fig 10: Genes and Levels of Expressiveness with approximation, threshold 0.97 6
promising experimental results.
Of course, first of all, this approach has to be thoroughly investigated from a formal point of view. It has to be proven that for each approximate incidence measure, the number of formal concepts decreases when the threshold is decreased. More specifically, it has to be investigated how for a given measure and two thresholds t1 t2 how the concept lattice for t1 can be mapped onto the concept lattice for t2 . It has to be scrutinized how the different measures relate to each other. And it has to be investigated how the approach taken in this paper relates to other research, most importantly the work of Boulicaut et al.
visualization with a slider to adjust the threshold for a given measure such that adjusting the threshold with the slider leads to animated transitions between the derived lattices. Here the mappings which have been mentioned in the section about the formal investigations are likely to be helpful, and further mathematical investigations might be needed.
the approach taken in this paper is envisioned to bring FCA closer to business intelligence applications and visual analytics, where one needs easy-to-understand and interactive visualizations for large amounts of data, and where a certain and controlled loss of information for the sake of simplified diagrams is permissible. 7