This tutorial has been given by Daniel Borchmann at the 11th ICFCA 2013. There are also some slides (partial tex) and even an exercise sheet (partial tex) from this tutorial.
Note: the corresponding Org Mode file contains source blocks that can be exectued directly. See Setting up Emacs to Run Clojure Code for how to exectue those blocks from within the document.
As conexp-clj is a general purpose tool for Formal Concept Analysis, it lets
you easily work with the basic structure of FCA, namely formal contexts. This
page discusses in which ways conexp-clj can work with and on formal contexts.
conexp-clj lets you easily create formal contexts in a number of ways. We
shall describe some of them in the following.
The fasted way to construct a formal context is just by writing it down, as in the following example.
(def ctx-1 (make-context [1 2 3] [1 2 3] <=))To see the formal context, just evaluate its variable explicitly
ctx-1 |1 2 3
--+------
1 |x x x
2 |. x x
3 |. . x
This is the ordered set called Chevron (in ASCII Art, don’t type this into the prompt)
5 6
| \ / |
| 4 |
2 3
\ /
1
To obtain a formal context for this, we can use the following command
(def ctx-2 (make-context #{1 2 3 4 5 6}
#{1 2 3 4 5 6}
#{[1 1] [1 2] [1 3] [1 5]
[1 6] [2 2] [2 5] [3 3]
[3 6] [4 4] [4 5] [4 6]
[5 5] [6 6]}))
ctx-2 |1 2 3 4 5 6
--+------------
1 |x x x . x x
2 |. x . . x .
3 |. . x . . x
4 |. . . x x x
5 |. . . . x .
6 |. . . . . x
One can enter the cross-table explicitly, using the function make-context-from-matrix,
like this
(def ctx-3 (make-context-from-matrix 6 6
[1 1 1 0 1 1
0 1 0 0 1 0
0 0 1 0 0 1
0 0 0 1 1 1
0 0 0 0 1 0
0 0 0 0 0 1]))
ctx-3 |0 1 2 3 4 5
--+------------
0 |x x x . x x
1 |. x . . x .
2 |. . x . . x
3 |. . . x x x
4 |. . . . x .
5 |. . . . . x
Here, instead of writing out the sets of objects and attributes explicitly, we
have just entered their cardinality 6. With this, the set of objects and
attributes automatically gets set to #{1 2 3 4 5 6}. From time to time, this
may save some typing time.
For some experiments it is often helpful to randomly create contexts. Here is how this can be done in conexp-clj. Of course, the exact result is probably not the one you see here
(rand-context #{1 2 3} 0.5) |1 2 3
--+------
1 |x . .
2 |x . x
3 |x x .
Here, the first parameter is the set of objects and attributes and the second parameter is the probality for the incidence.
Having created a formal context, there a plenty of possibilities to work with it. To illustrate this, let us define the Chevron again
(def ctx-1 (make-context-from-matrix ['a 'b 'c 'd 'e 'f]
['a 'b 'c 'd 'e 'f]
[1 1 1 0 1 1
0 1 0 0 1 0
0 0 1 0 0 1
0 0 0 1 1 1
0 0 0 0 1 0
0 0 0 0 0 1]))
ctx-1 |a b c d e f
--+------------
a |x x x . x x
b |. x . . x .
c |. . x . . x
d |. . . x x x
e |. . . . x .
f |. . . . . x
Note that 'a denotes the symbol named a.
The most basic operation on formal contexts is to retrieve its components. This can be done as follows
(objects ctx-1)#{a e c b d f}
(attributes ctx-1)#{a e c b d f}
(incidence ctx-1)#{[a f] [a a] [f f] [c c] [d f] [a e] [d e] [a b] [c f] [d d] [a c]
[e e] [b b] [b e]}
To see if ctx-1 is clarified, you can also use
(object-clarified? ctx-1)true
(attribute-clarified? ctx-1)true
or both steps at once using
(context-clarified? ctx-1)true
If ctx-1 would not be clarified, one could obtain a clarified version of
ctx-1 by using
(clarify-attributes ctx-1)
(clarify-objects ctx-1)
(clarify-context ctx-1)As another example, for ctx-1, we could for instance compute the arrow relations
(e.g. to see which objects or attributes are irreducible)
(up-arrows ctx-1)#{[d c] [e b] [f c] [e f] [f e] [b f] [a d] [d b] [c e]}
(down-arrows ctx-1)#{[c b] [d c] [b a] [b f] [a d] [b c] [d b] [c a] [c e] [d a]}
To directly see whether ctx-1 is reduced, one could also use
(context-reduced? ctx-1)false
and to obtain a reduced version of ctx-1
(reduce-context ctx-1) |b c d e f
--+----------
a |x x . x x
b |x . . x .
c |. x . . x
d |. . x x x
Now I want to get all objects, which attribute a and b have in common
(attribute-derivation ctx-1 #{'a 'b})#{a}
The same can be done for sets of objects
(object-derivation ctx-1 #{'c 'd 'f})#{f}
Instead of using this long names, there are also the abbreviations aprime and
oprime available.
If you want to compute the closure of a given set of objects or attributes in our context use
(context-attribute-closure ctx-1 #{'a 'b})#{a e c b f}
(context-object-closure ctx-1 #{'a 'b})#{a b}
We can compute all intents and extents via
(extents ctx-1)(#{}
#{d}
#{a}
#{a d}
#{a b}
#{a c}
#{a c d f}
#{a e b d}
#{a e c b d f})
(intents ctx-1)(#{}
#{f}
#{c f}
#{e}
#{e f}
#{e d f}
#{e b}
#{a e c b f}
#{a e c b d f})
To get all formal concepts use
(concepts ctx-1)([#{a e c b d f} #{}]
[#{a} #{a e c b f}]
[#{} #{a e c b d f}]
[#{a e b d} #{e}]
[#{a b} #{e b}]
[#{d} #{e d f}]
[#{a d} #{e f}]
[#{a c} #{c f}]
[#{a c d f} #{f}])
If you are only interested in the number of formal concepts, you can instead write
(count (concepts ctx-1))9
Finally, you can compute the concept lattice via
(concept-lattice ctx-1)Lattice on 9 elements.
Note that this will not give you a picture of the lattice, but a representation of the algebraic structure. To get an picture of the lattice, do the following
(use 'conexp.gui.draw)
(draw-lattice (concept-lattice ctx-1))This will open up a new window which should look like this
You get the canonical base with (who would have guessed that!)
(canonical-base ctx-1)((#{d} ⟶ #{e f})
(#{b} ⟶ #{e})
(#{c} ⟶ #{f})
(#{e b f} ⟶ #{a c})
(#{e c f} ⟶ #{a b})
(#{a} ⟶ #{e c b f}))
There a several further operations you can do with contexts, e.g. the context apposition. We define two contexts:
(def ctx-1 (make-context #{1 2 3} #{1 2 3} <))
(def ctx-2 (make-context-from-matrix [1 2 3]
['a 'b 'c 'd]
[1 1 0 1
1 0 1 0
0 0 1 1]))
;; show both context in a vector
[ctx-1 ctx-2][ |1 2 3
--+------
1 |. x x
2 |. . x
3 |. . .
|a b c d
--+--------
1 |x x . x
2 |x . x .
3 |. . x x
]
The apposition of these two contexts is
(context-apposition ctx-1 ctx-2) |[1 0] [2 0] [3 0] [a 1] [b 1] [c 1] [d 1]
--+------------------------------------------
1 |. x x x x . x
2 |. . x x . x .
3 |. . . . . x x
Note how the two sets of attributes are automatically made disjoint by considering pairs with different second entry.
To compute the dual context, we use
(dual-context ctx-2) |1 2 3
--+------
a |x x .
b |x . .
c |. x x
d |x . x
Now we can build the subposition of ctx-1 and the dual of ctx-2
(context-subposition ctx-1 (dual-context ctx-2)) |1 2 3
------+------
[1 0] |. x x
[2 0] |. . x
[3 0] |. . .
[a 1] |x x .
[b 1] |x . .
[c 1] |. x x
[d 1] |x . x
If you want to invert a given context use
(invert-context ctx-1) |1 2 3
--+------
1 |x . .
2 |x x .
3 |x x x