Spanning Concept Trees: Enhanced Algorithm and Visualisation
摘要
Describing the recursive execution of a Close-by-One algorithm, the Concept Tree can be derived efficiently from a formal context. However, its use as a proxy for interaction with the concept lattice digraph is problematic, since it can include “bypass” arcs which are not in the digraph. I have previously proposed two algorithms which remediate these bypass arcs to yield a Spanning Concept Tree. This tree resembles a Concept Tree in that the children of a vertex are in reverse lectic order of intents, but differs in that the parent of each vertex in the former is also its first upper cover in this order. In this paper, I present a third remediation algorithm which significantly improves on the computational efficiency of the first two. The spanning tree of Kuznetsov and Obiedkov can be derived both directly and efficiently from a formal context. Its natural lack of bypass arcs recommends it as an alternative proxy for interaction with the lattice digraph. The properties of this tree are explored, and visualisation techniques are proposed which compensate for the absence from the spanning tree of some lattice digraph arcs. Each of these trees has both top-down and bottom-up variants, rooted at the lattice top and bottom respectively. Permuting the formal context into a Jointly Reverse Lectic (JRL) order appears to mitigate not only topological incompatibility between top-down and bottom-up trees, but also bypass arcs in the Concept Tree. However, I demonstrate that not all JRL orders of a formal context are equally effective at doing so. The pros and cons of searching for an optimal JRL order, vice remediating the bypass arcs of one which is good enough, are accordingly canvassed.