Being able to have a quick look at a dataset is essential in many applications. One way is to summarize the dataset by means of a small set of patterns. In this paper we suggest defining such set of patterns as the closed elements of delta-classes of equivalence. This approach allow us to propose an overview of a dataset and then, if necessary, any delta-class of equivalence can be expanded to provide more detailed information about a certain part of the dataset. To demonstrate our proposal we deeply studied the Titanic dataset about survival of passengers and showed the connections between the passenger attributes and a possible dataset summary in terms of patterns.
In this paper, we are interested in pattern or itemset mining in tabular data.
There is a considerable amount of work on many aspects of this subject,
especially regarding algorithms and search for interesting patterns [
An alternative to the exhaustive enumeration of itemsets is based on
“sampling” [
Then, in each approach a particular set of itemsets is returned, which provides a “multifaceted view” of the intrinsic structure underlying the data.
Our approach is based on Δ-classes of equivalence, the generalization of standard classes of equivalence based on closure operator. A user-set parameter Δ measures how much a closed set can differ from its upper neighbors in the partial order of closed sets.
A Δ-class of equivalence allows one to characterize the distribution underlying the data, i.e., when Δ is large, there are only a few Δ-classes of equivalence whose elements are very stable, while when Δ is small, the number of Δ-classes increases and the related information becomes less stable. Moreover, the Δclasses of equivalence are very stable for large Δ and do not significantly depend on the data sampling used for the analysis.
In this paper we study Δ-classes for Titanic dataset. In particular, we show what kind of conclusions w.r.t. the passengers of Titanic can be made. Further we study what kind of information can be stored in “implications” of the Δ-classes of equivalence. In particular, such implications can show what information is usually associated with a set of attributes.
The paper has the following structure. First we introduce basic definitions related to generalized closure operator. Then in Section 3 we evaluate this closure operator on Titanic dataset. 2
Δ-classes of equivalence
The proposed approach is introduced in terms of Formal Concept Analysis
(FCA) [
We should note that operators (·)↑↓ and (·)↓↑ form closure operators on 2G and 2M , respectively. Hereafter, we focus on the operator (·)↓↑ and its generalizations. Let us reformulate the definition in terms of “instance counting”. Let B be any set of attributes.
Definition 1. An attribute set B is closed iff (∀m ∈ M \B)|(B ∪{m})↓| 6= |B↓|. It can be seen that (·)↓↑ maps any set of attributes to a closed set of attributes. Let us reformulate Definition 1 in the following equivalent way. B is closed iff (∀m ∈ M \ B)[|B↓| − |(B ∪ {m})↓| ≥ 1].
|B↓| − |(B ∪ {m})↓| ≥ Δ ≥ 1.
In [
Definition 3. Given an attribute set B, its equivalence class EquivΔ(B) is the
set of all attribute sets with the closure equal to the closure of B, i.e.,
This form allows changing the threshold 1 at the end of the formula to any other
positive value. The larger this value, the less attribute sets would pass a test
similar to the one from Definition 1. This leads to the definition of Δ-closedness
of an attribute set [
Definition 2. A set of attributes B is called Δ-closed if for any m ∈ M : (3) (4) (5) (6)
EquivΔ(B) = {X ⊆ M | (X)Δ = (B)Δ}.
Moreover, since according to Definitions 1 and 2 if a set of attributes is Δ-closed than it is necessary closed. Thus, these Δ-classes of equivalence are joins of several closure-based classes of equivalence. It allows introducing a new derivation operator related to Δ-closure.
A↑Δ = (A↑)Δ, A ⊆ G
B↓Δ = (B)Δ↓, B ⊆ M
The new Δ-derivation operator allows defining Δ-concepts ordered within a lattice in the similar way to the classical formal concepts. Moreover, since any Δ-closed set of attributes is a closed set of attributes, than the set of Δ-concepts are subset of formal concepts and the order of Δ-concepts is a suborder of the corresponding formal lattice.
Finally, we should discuss Δ-implications since they provide a useful tool for finding associations between attribute sets.
Definition 4. A rule A → B is called Δ-implication if B = AΔ \ A, i.e., A and Δ A ∪ B are from the same Δ-class of equivalence.
Since Δ-closure can change the support of the attribute set a Δ-implication is not necessary an implication. However, the set of Δ-implications is subset of all association rules, thus they are more easy analysable. In particular, given an implication A → B, the set B is the set of attributes that are associated with A in most samples from the underlying distribution.
In the next section we experimentally show how such lattices of Δ-concepts
and the corresponding implications can be used for data analysis. Moreover,
since Δ-concepts can be found in polynomial time3 [
In this paper we use Titanic dataset downloaded (train dataset) from Kaggle4. This is one of the most known datasets with easily interpretable patterns that do not require deep diving into the domain knowledge. The dataset describes 891 passengers of the last Titanic ship travel. Every passenger is described with name, age, sex, the number of parents and/or children and the number of spouse and/or siblings travelled together with the passenger. The ticket price and the ticket class is also known as well as the survival state of the passenger after the Titanic shipwreck.
All numerical data is divided into 5 percentiles and then inter-ordinal scaling is used on top of these percentiles. For example, for the quantity Age it is known from the data that 51 of the passengers were below 19 years old, the next 15 between 19 and 25, then between 25 and 32 and then between 32 and 41 and finally the last 15 of the passengers were above 41 years old. Then new binary attributes are formed based on these limits (19, 25, 32,41), these eight attributes are “Age ≥ 19,” “Age ≤ 19”. “Age ≥ 25,” “Age ≤ 25”. “Age ≥ 32,” “Age ≤ 32”. “Age ≥ 41,” “Age ≤ 41”.
Additionally, from the ”Name” field the social status is extracted, including ”Mr”, ”Mrs”, ”Master”, etc. It makes in total 49 attributes. 3.2
Even for such relatively simple data the total number of concepts is 9002. It is not hard to build such a lattice. However, analysis of the lattice is quite hard. It is hardly possible to draw the whole lattice and the only way is to navigate it from the top or from the bottom concepts. However, Δ-classes of equivalence give another means for such analysis and navigation.
Let us first increase the Δ threshold for the lattice. If Δ = 90, then the lattice size is only 11 and it can be drawn. It is shown in Figure 1. For every concept the corresponding extent size and Δ-measure are shown. Every attribute is shown outside of the concept with an arrow attached to the concept of the first attribute entry. It can be seen that the lattice involves only 9 attributes out of 49. All other attributes are attached to the BOTTOM concept and are not shown. It 3 Being more precise the enumeration procedure can be set in such a way, that it finishes in input-polynomial time. It is achieved by iteratively increasing the threshold θ if the number of the already found patterns is too large. The result is the set of all patterns with Δ ≥ θ. However, if θ is automatically set to be too high, the procedure still finishes in input-polynomial time but the result set is empty. 4 https://www.kaggle.com/c/titanic means that starting for any attribute a from this set, one has Δ({a}↓) < 90, i.e., smaller than the threshold. For example, the attribute fare ≥ 8 is introduced to the lattice at the very top concept. It means that |∅↓| − |{fare ≥ 8}↓| < 90, i.e., for most of objects fare ≥ 8. Moreover, since the top concept in this lattice has the maximal value of Δ, its extent is the most typical extent for all passengers. Since we cannot make it more precise without excluding less objects than 175.
Then we can see that there are 5 concepts below the top concept. They are the only concepts that are significantly different from their children. Accordingly, this concept lattice for Δ = 90 shows the structure of different groups of passengers (formal concepts with Δ-closure for Δ = 90. A concept is only shown if there is no more precise description that contains similar number of objects.
This setting allows finding and prioritizing the association rules related to a certain set of attributes. Let us study female subpopulation of the passengers. In particular, we can try to Δ-close the following description sex = female. What Δ should be used? One of the reasonable choice is the maximal Δ such that Δ-closure of sex = female is different from M . For example in Figure 1 no concept with sex = female is found. It means that for Δ ≥ 90, {sex = female}↓↑Δ = M . If the whole lattice is available it corresponds to the concept with the maximal Δ-measure such that the intent of the concept is a superset of {sex = female}. In the form of Δ-implication it can be written as5:
{sex = female} →Δ {fare ≥ 10}.
It suggests that women rarely buy cheapest tickets. Moreover, since we do not find class ≤ 2 attribute, it means that they can afford the 3rd class, but nevertheless not the cheapest tickets. What about men?
{sex = male} →Δ {title = Mr, fare ≥ 8}.
Now we see that the preference for more expensive tickets is missing. However, we see that most of the men are titled ”Mr”. It is not the classical closure assuming that all men are Mr. Indeed, the correspondence between the title and sex is shown in Table 1. {title = Master} →Δ {sex = male, age ≤ 19, fare ≥ 10, class ≥ 2}. We can see, that Master corresponds to young men from 2nd and 3rd class but not with the cheapest tickets. It is a quite strange combination and a deeper investigation is needed. However, it is not an artefact of the procedure. If we check the original dataset all findings are supported, i.e., they are mostly from the 2nd and 3rd class, but not so cheap. The proposed procedure was useful here only for highlighting such finding. In contrast, for Miss-title no new information is found.
Let us now formulate a question about women that had cheap tickets: {sex = female, fare ≤ 10} →Δ {title = Miss, class = 3, fare ≤ 8}. In fact if decision is to travel cheap, then it is the cheapest option. Similar, answer will be given for men traveled cheap. However, the group of men that traveled cheep is about 7 times larger than the group of women. Thus, if we would have just requested ”who traveled cheap”, than the result would be the group of men.
Finally, let us ask how age affects the travel behavior.
{age ≤ 25} →Δ {class ≥ 2, 8 ≤ fare ≤ 40}. 5 For simplicity, the attribute sets are shown with reduction, i.e., if by knowing that fare ≥ 10 we can conclude that fare ≥ 8, the last attribute is not shown. Thus, young people usually travel in the 2nd or 3d class. Similarly, for people aged more than 41 years.
{age ≥ 41} →Δ {class ≤ 2, fare ≥ 22}, i.e., such people usually prefer the 1st or 2nd class and the fare is more than 22.
Let us finally show that we can be interested also in combinations of attributes. For example, what about women of age more than 41 years? {age ≥ 41, sex = female} →Δ {class = 1, fare ≥ 40, title = Mrs} So in contrast to generally aged people, women usually travel in the 1st class and they are titled Mrs. 4
Based on Titanic dataset Δ-classes of equivalence are shown to be useful for
exploratory data analysis. In particular, it can be used to systematize the dataset
and to prioritize association rules related to certain requests, e.g., every
attribute can be associated with the most frequent attributes taken into account
co-occurrences of the attributes. Since, Δ-classes of equivalence can be found
in polynomial time [