In this paper we are interested in studying concise representations of concepts and dependencies, i.e., implications and association rules. Such representations are based on equivalence classes and their elements, i.e., minimal generators, minimum generators including keys and passkeys, proper premises, and pseudo-intents. All these sets of attributes are significant and well-studied from the computational point of view, while their statistical properties remain to be investigated. This is the purpose of this paper to study these singular attribute sets and in parallel to study how to evaluate the complexity of a dataset from an FCA point of view. In the paper we analyze the empirical distributions and the sizes of these particular attribute sets. In addition we propose several measures of data complexity relying on these attribute sets in considering real-world and related randomized datasets.
In this paper we are interested in measuring “complexity” of a dataset in terms of Formal
Concept Analysis (FCA [
For example, the number of intents gives the size of the lattice, while the number of
pseudointents gives the size of the Duquenne-Guigues basis [
In this paper we discuss alternative ways of defining the “complexity” of a dataset and how it
can be measured in the related concept lattice that can be computed from this dataset. For doing
so, we introduce two main indicators, namely (i) the probability that two concepts 1 and 2 are
comparable, (ii) given two intents and , the probability that the union of these two intents is
again an intent. The first indicator “measures” how close is the lattice to a chain, and the second
indicator “measures” how close the lattice is to a distributive one [
This paper presents an original and practical study about the complexity of a dataset through
an analysis of specific elements in the related concept lattice, namely intents, pseudo-intents,
proper premises, keys, and passkeys. Direct links are drawn with implications and association
rules, making also a bridge between the present study in the framework of FCA, and approaches
more related to data mining, actually pattern mining and association rule discovery. Indeed, the
covering relation of the concept lattice makes a concise representation of the set of association
rules of the context [
For studying practically this complexity, we have conducted a series of experiments where we measure the distribution of the diferent elements for real-world datasets and then for related randomized datasets. Actually these randomized datasets are based on corresponding real-world datasets where either the distribution of crosses in columns is randomized or the whole set of crosses is randomized while keeping the density of the dataset. We can observe that randomized datasets are usually more complex in terms of our indicators than real-world datasets. This means that, in general, the set of “interesting elements” in the lattice is smaller in real-world datasets.
The paper is organized as follows. In the second section we introduce the theoretical background and necessary definitions. Then the next section presents a range of experiments involving real-world and randomized datasets. Finally, the results of experiments are discussed and then we propose a conclusion.
Here we recall basic FCA definitions related to concepts, dependencies, and their minimal representations. After that we illustrate the definitions with a toy example. Let us consider a formal context = (, , ) and prime operators: ′ = { ∈ ∣ ∀ ∈ ∶ }, ⊆ ′ = { ∈ ∣ ∀ ∈ ∶ }, ⊆ (1) (2)
We illustrate the next definitions using an adaptation of the “four geometrical figures and their
properties” context [
Definition 1 (Intent or closed description). A subset of attributes ⊆ if ″ = . is an intent or is closed
In the running example (Table 1), = {, } = ″ is an intent and is the maximal subset of attributes describing the subset of objects ′ = { 3, 4}.
is a pseudo-intent if: 1. ≠ ″ 2. ″ ⊂ for every pseudo-intent ⊂
Pseudo-intents are premises of implications of the cardinality-minimal implication basis
called “Duquenne-Guigues basis” [
1 2 3 4 a b c d e x x x
x x x x x x g1 g2 e b g3 g4
is a proper premise if: ∪ ⋃ ( ⧵ {} )″ ≠ ″ ∈
In the running example (Table 1), = {, } is a proper premise since the union of with the closures of its subsets does not result in the closure of , i.e., {, }∪{} ″∪{} ″ = {, }∪{}∪{, } = {, , } ≠ {, , , , } .
Proper premises are premises of the so-called “proper-premise base” (PP-base, see [
is a generator if ∃ ⊆ ∶ ″ = .
In this paper, every subset of attributes is a generator of a concept intent. A generator is called non-trivial if it is not closed. In the current example (Table 1), = {, , } is a generator of = {, , , , } since is an intent, ⊆ , and ″ = .
Definition 5 (Minimal generator, key). A set of attributes ⊆ of ″ if ∄ ∈ ∶ ( ⧵ {}) ″ = ″. is a key or a minimal generator
In the following we will use “key” rather than “minimal generator. A key is inclusion minimal
in the equivalence class of subsets of attributes having the same closure [
generator if is a minimal generator of ″ and has the minimal size among all minimal generators of ″.
In the following we will use “passkey” rather than “minimum generator. A passkey is
cardinality-minimal in the equivalence class of subsets of attributes having the same closure. It
should be noticed that there can be several minimum generators and one is chosen as a passkey,
but the minimal size is unique. In [
Finally, for illustrating all these definitions, we form the context (2 , , ) of all classes of “characteristic attribute sets” of as they are introduced above. = {intent, pseudo-intent, proper premise, key, passkey}, while states that a given subset of attributes in 2 is a characteristic attribute set in . The concept lattice of this context is shown in Figure 2.
subset of attributes generator description ae, be, ce, de, abd, abe, ace, ade bce, bde, cde, abcd, abce, abde, acde, bcde 2.2. Towards Measuring Data Complexity “Data complexity” can mean many diferent things depending on the particular data analysis problem under study. For example, data can be claimed to be complex when data processing takes a very long time, and this could be termed as “computational complexity” of data. Alternatively, data can be considered as complex when data are hard to analyze and to interpret, and this could be termed as “interpretability complexity” of data. For example, it can be hard to apply FCA or machine learning algorithms, such as clustering, classification, or regression. Accordingly, it is quite hard to define data complexity in general terms.
If we consider the dimension of interpretability, then the size of the “patterns” to interpret and their number are definitely important elements to take into account. In the following, the expression “pattern” refers to “interesting subsets of attributes” in a broad sense. In an ideal case, one prefers a small number of patterns, to facilitate interpretation. Indeed, a small number of rules with a few attributes in the premises and in the conclusions is simpler to interpret than hundreds of rules with more than ten attributes in the premises and conclusions. Thus, it is natural to study how the number of patterns is distributed w.r.t. their size. In most of the cases, large numbers of patterns are associated with computational complexity. Then controlling the size and the number of patterns is also a way to control computational complexity.
It should also be mentioned that the number of patterns is related to the so-called
“VCdimension” of a context [
Additionally, we decided to measure the “lattice complexity”, i.e., the complexity of the corresponding concept lattice, with two new measures related to what could be termed the “linearity” of the lattice. Indeed, the simplest lattice structure that can be imagined is a chain, while the counterpart is represented by the Boolean lattice, i.e., the lattice with the largest amount of connections and concepts. However, it should be noticed that the Boolean lattice may be considered as complex from the point of view of interpretability, but very simple from the point of view of implication base, which is empty in such a lattice.
Then, a first way to measure the closeness of the lattice to a chain is the “linearity index” which is formally defined below as the probability that two random concepts are comparable in the lattice.
Definition 7. Let us consider a concept lattice ℒ, ℒ ∗ = ℒ ⧵ {⊤, ⊥}, where |ℒ | denotes the number of the concepts in ℒ, ⊤ and ⊥ being the top and bottom elements of ℒ. The linearity index LIN(ℒ ) is defined as:
LIN(ℒ ) = {
2 |ℒ ∗|⋅(|ℒ ∗|−1)
∑ { , }⊂ℒ ∗
1( < ∨ > ) if |ℒ | > 3, (3) where { , } is an unordered pair of concepts, and 1 is the indicator function taking the value 1 when the related constraint is true.
The linearity index is maximal for a chain, i.e., the lattice related to a linear order. It is
minimal for the lattice related to a nominal scale which is also the lattice related to a bijection.
One example of such a lattice is given by the so-called M3 lattice which includes a top and
a bottom element, and three incomparable elements. In particular, when a lattice includes a
sublattice such as M3 it is not distributive [
This index does not directly measure how well the lattice is interpretable. One of the main
interpretability properties is the size of some particular sets, such as the size and the structure
of the implication basis. One of the simplest structure for the implication basis can be found in
distributive lattices, where pseudo-intents are all of size 1 [
Definition 8.
DIST(ℒ ) =
2 |ℒ | ⋅ (|ℒ | − 1)
∑ { , }≠ ⊂ (ℒ ) 1( ∪ ∈ (ℒ )), (4) where (ℒ )
is the set of concept intents in ℒ.
The distributivity index is maximal for distributive lattices, and this includes chain lattices
which are distributive lattices [
In order to study some ways of measuring data complexity, we need to compare the behavior of diferent complexity indices for “simple” and “complex” data. However, beforehand we cannot know which dataset is complex. Accordingly, we will generate synthetic complex datasets and compare them with real-world datasets. One way of generating complex data is “randomization”. Actually, randomized data cannot be interpreted since any possible result is an artifact of the method. For randomized data we know beforehand that there cannot exist any rule or concept that have some meaning. Thus, randomized data are good candidate data for being considered as “complex”.
Now we discuss which randomization strategy should be used for generating such data. A natural way is making randomized data similar in a certain sense to the real-world data they are compared to. Firstly, when considering reference real-world data, it seems natural to keep the same number of objects and attributes as they are in the real-world data. Moreover, the “density” of the context, i.e., the number of crosses, significantly afects the size and the structure of the related concept lattice. Thus, to ensure that randomized data are “similar” to the real-world data it is also natural to keep the density of data. This gives us the first randomization strategy, i.e., for any real-world dataset we can generate a randomized dataset with the same number of objects and attributes, and with the same density. Then, the crosses in the original context will be randomly spread along the new context in ensuring that the density is the same as in the original real-world data.
For example, let us consider the context given in Table 2, where there are 8 objects, 6 attributes, and 35 crosses. Thus, any context with 8 objects, 6 attributes, and 35 crosses, can be considered as a randomization of this original context. In our first randomization strategy, we suppose that the probability of generating any such randomized context is equally distributed. descriptions generator intent key
passkey
The randomized formal contexts for such strategy were studied in [
Although such randomization strategy considers objects and attributes diferently, it corresponds to typical cases in data analysis. Indeed, in typical datasets, objects stand for observations that are described by diferent attributes. The attributes correspond to any hypothesis in the data domain. Then, analysts are usually interested in discovering some relations between attributes, and the hypothesis of attribute independence is a natural null hypothesis in such a setting.
For example, let as consider again the context in Table 2, and that the numbers of objects and attributes remain the same in the randomized context. Then a randomized context following the second strategy is any context having 8 crosses for the first attribute, 2 crosses for the second attribute, 5 crosses for the third attribute, etc. Accordingly, when we are randomizing data from a given real-world dataset, we should have in mind that many randomized datasets can be generated w.r.t. the same randomization strategy. Thus, for the sake of objectivity, it is not enough to study only one random dataset for a given real-world dataset, but it is necessary to generate several randomized datasets and then to estimate the distribution of a characteristic under study within all randomized datasets.
In the next section we study diferent ways of measuring the complexity of a dataset and we observe that the complexity of randomized datasets is generally higher than the complexity of the corresponding real-world dataset.
For this preliminary study we selected 4 small real-world datasets in order to support an eficient computing of all necessary elements of the lattice. Eficiency matters here because we involve randomization and computations are repeated hundreds of times for one dataset. The study includes the following datasets: “Live in water1”, “Tea ladies2” “Lattice of lattice properties3”, and “Bob Ross episodes4”. For the sake of eficiency the fourth dataset was restricted to only ifrst the 20 attributes.
The datasets are analyzed in two diferent ways. Firstly, the characteristic attribute sets are computed, e.g., concepts, keys, passkeys, pseudo-intents, and proper premises, and then the relations existing between these elements are discussed. Secondly, we study the complexity of a dataset in studying its characteristic attribute sets and their distributions w.r.t. the size of these attribute sets. We also compared all the two numerical indicators, namely the linearity and the distributivity indices, for real-world and randomized datasets.
In this section we study the relations between the diferent characteristic attribute sets. The experiment pipeline reads as follows.
• Given a context = (, , )
, we compute all possible “attribute descriptions”, i.e., subsets of attributes in 2 , and we check whether a description verifies some characteristic such as being an intent, a key, a passkey…. • Given = {,
, , , context (2 , ,
) where has a characteristic in .
-, - }
, we construct the is the relation indicating that a given set of attributes • Finally, we construct the “lattice of descriptions” based on the context (2 , , ). This lattice shows the relations existing between all generators –subsets of attributes– in a given dataset.
The “description context” for the “Bob Ross” dataset is given in Table 2 and the corresponding lattice is shown in Figure 3. From the lattice we can check that any two classes of descriptions may intersect if this is not forbidden by their definition (e.g., a description cannot be both an intent and a pseudo-intent). Although such a lattice is computed for a particular dataset, this is the general lattice structure which is obtained most of the time. In some small datasets it may happen that some characteristic attribute sets are missing. For example, in the “Live in water” lattice, the properties of being a key, being a passkey, and being a proper premise, all coincide and collapse into one single node.
It is also very interesting to analyze the proportions of the sizes of classes of descriptions. For example, in the “Bob Ross” context restricted to 20 attributes, there are 220 possible descriptions,
generator subset of attributes
description but there are only 112 of them which are closed, and only 259 of them which are minimal generators. Thus, the large majority of the descriptions are “useless” in the sense that they do not correspond to any of the characteristic attribute subsets introduced above. In the next subsection we consider the distributions of these characteristic attribute subsets.
For analyzing data complexity, we start by comparing the numbers of elements in real-world data and in randomized data. In the Figures 4 and 5, the distributions of the diferent characteristic elements for “Bob Ross” dataset are shown. Along the horizontal axis, the sizes of the elements are shown, i.e., the number of attributes in the intent, pseudo-intent, key, etc. Along the vertical axis the number of elements of the corresponding sizes are shown.
Red crosses show the values corresponding for real-world data and the boxplots visualize the values found in random data. There were 100 randomizations and thus boxplots are based on these 100 values. A box corresponds to the 50% middle values among 100 values. In addition, it should be noticed that these two figures difer in the randomization strategy. Figure 4 corresponds to density-based randomization while Figure 5 shows randomization based on column permutations.
From both figures we can observe that randomized data contain significantly larger numbers of elements than the real-world data. Moreover, the sizes of the elements for randomized data are larger than the sizes of real-world data. Similar figures can be built for “Tea Ladies” and “Lattice of lattice properties” datasets. However, it is not possible to distinguish the real-world dataset and the randomized data for the “Live in Water” dataset5. This can be explained by the fact that either the dataset does not contain deep dependencies, or that the dataset is too small, i.e., the randomized dataset cannot be substantially diferent from the original one.
Let us now study how the linearity index and the distributivity index measure the complexity of a dataset. Figures 7 and 6 show the values of the linearity and distributivity indices correspondingly w.r.t. diferent randomizations. From these figures we can see that datasets built from density-based randomization are more diferent from real-world datasets than the randomized datasets built from column-wise permutations. We also notice that the values of the linearity and distributivity indices show a substantial dependence w.r.t. density of the corresponding context. Indeed, if we examine the randomized datasets, we can see that the distributions of the linearity and distributivity indices are diferent. This can be explained either by the context density and by the context size. Thus, we cannot have any reference values for these indices that would split between “complex” and not “simple” data. However, comparing the values of the index to the distribution of these indices allow one to decide on complexity of the data. Finally, in all datasets but “Live in water”, both linearity and distributivity indices have higher values for real-world datasets than for randomized datasets. This shows again that real-world datasets are more structured than their randomized counterparts.
In this paper we have introduced and studied “concise representations” of datasets given by related contexts and concept lattices, and characteristic attributes sets based on equivalence classes, i.e., intents, keys (minimal generators), passkeys (minimum generators), proper premises, and pseudo-intents. We have also defined two new indices for measuring the complexity of a dataset, namely the linearity index for checking the direct dependencies between concepts or how a concept lattice is close to a chain, and the distributivity lattice which measures how close is a concept lattice to a distributive lattice. In the latter, all pseudo-intents are of length 1, leading to sets of simple implications. We have also proposed a series of experiments where we analyze real-world datasets and their randomized counterparts. As expected, the randomized datasets are more complex that the real-world ones.
The future work will be to improve this study in several directions, by studying more deeply the role of both indices, the linearity index and the distributivity index, by analyzing more larger datasets, and more importantly by analyzing the complexity from the point of view of the generated implications and association rules. This paper is another step in the analysis of the complexity of datasets in the framework of FCA, and we believe that FCA can bring a substantial support for analyzing data complexity in general. 5All the figures that cannot be shown in this paper are visible in supplementary materials, see https://yadi.sk/i/8_ 5EEvY4zNi82g
The work of Sergei O. Kuznetsov on this paper was supported by the Russian Science Foundation under grant 22-11-00323 and performed at HSE University, Moscow, Russia. (b) Keys (c) Passkeys (d) Pseudo-intents (e) Proper premises (b) Keys (c) Passkeys (d) Pseudo-intents (e) Proper premises (a) Live in water
(b) Lattice (c) Tea Lady Randomization based on column permutations (d) Bob Ross (e) Live in water (f) Lattice (g) Tea Lady (h) Bob Ross (a) Live in water
(b) Lattice (c) Tea Lady Randomization based on column permutations