Working with ImplicationSets

Introduction

In this vignette, we present the main functionalities and data structures of the fcaR package when working with formal contexts and concepts, in FCA.

We load the fcaR package by:

library(fcaR)

Datasets

We are going to work with two datasets, a crisp one and a fuzzy one.

The classical (binary) dataset is the well-known planets formal context, presented in

Wille R (1982). “Restructuring Lattice Theory: An Approach Based on Hierarchies of Concepts.” In Ordered Sets, pp. 445–470. Springer.

knitr::kable(planets, format = "html", booktabs = TRUE)
small medium large near far moon no_moon
Mercury 1 0 0 1 0 0 1
Venus 1 0 0 1 0 0 1
Earth 1 0 0 1 0 1 0
Mars 1 0 0 1 0 1 0
Jupiter 0 0 1 0 1 1 0
Saturn 0 0 1 0 1 1 0
Uranus 0 1 0 0 1 1 0
Neptune 0 1 0 0 1 1 0
Pluto 1 0 0 0 1 1 0

The other formal context is fuzzy and is defined by the following matrix I:

knitr::kable(I, format = "html", booktabs = TRUE)
P1 P2 P3 P4 P5 P6
O1 0.0 0.0 0.5 0.5 1.0 0
O2 1.0 1.0 1.0 0.0 0.0 0
O3 0.5 0.5 0.0 0.0 0.0 1
O4 0.0 0.0 0.0 1.0 0.5 0
O5 0.0 0.0 1.0 0.5 0.0 0
O6 0.5 0.5 0.0 0.0 0.0 1

Working with ImplicationSets

Although ImplicationSet objects can be created ad hoc, the usual way to get implications is by the application of the NextClosure algorithm to a FormalContext object.

Thus, let us create different formal contexts with the previous datasets:

fc_planets <- FormalContext$new(planets)
fc_I <- FormalContext$new(I)

Extraction of the canonical basis of implications

The function find_implications() use the NextClosure algorithm in a formal context to extract the canonical basis of implications:

fc_planets$find_implications()
fc_I$find_implications()

We can inspect the implications by doing:

fc_planets$implications
#> Implication set with 10 implications.
#> Rule 1: {no_moon} -> {small, near}
#> Rule 2: {far} -> {moon}
#> Rule 3: {near} -> {small}
#> Rule 4: {large} -> {far, moon}
#> Rule 5: {medium} -> {far, moon}
#> Rule 6: {medium, large, far, moon} -> {small, near, no_moon}
#> Rule 7: {small, near, moon, no_moon} -> {medium, large, far}
#> Rule 8: {small, near, far, moon} -> {medium, large, no_moon}
#> Rule 9: {small, large, far, moon} -> {medium, near, no_moon}
#> Rule 10: {small, medium, far, moon} -> {large, near, no_moon}
fc_I$implications
#> Implication set with 12 implications.
#> Rule 1: {P6 [0.5]} -> {P1 [0.5], P2 [0.5], P6}
#> Rule 2: {P5 [0.5]} -> {P4 [0.5]}
#> Rule 3: {P3 [0.5], P4 [0.5], P5 [0.5]} -> {P5}
#> Rule 4: {P3 [0.5], P4} -> {P3}
#> Rule 5: {P3, P4 [0.5], P5} -> {P4}
#> Rule 6: {P2 [0.5]} -> {P1 [0.5]}
#> Rule 7: {P1 [0.5]} -> {P2 [0.5]}
#> Rule 8: {P1 [0.5], P2 [0.5], P4 [0.5]} -> {P1, P2, P3, P4, P5, P6}
#> Rule 9: {P1 [0.5], P2 [0.5], P3 [0.5]} -> {P1, P2, P3}
#> Rule 10: {P1 [0.5], P2} -> {P1}
#> Rule 11: {P1, P2 [0.5]} -> {P2}
#> Rule 12: {P1, P2, P3, P6} -> {P4, P5}

Internally, an ImplicationSet consists of two matrices (one for the left-hand sides and the other for the right-hand sides of the rules). We can get these (sparse) matrices as:

fc_planets$implications$get_LHS_matrix()
#> 7 x 10 sparse Matrix of class "dgCMatrix"
#>    [[ suppressing 10 column names '1', '2', '3' ... ]]
#>                            
#> small   . . . . . . 1 1 1 1
#> medium  . . . . 1 1 . . . 1
#> large   . . . 1 . 1 . . 1 .
#> near    . . 1 . . . 1 1 . .
#> far     . 1 . . . 1 . 1 1 1
#> moon    . . . . . 1 1 1 1 1
#> no_moon 1 . . . . . 1 . . .
fc_planets$implications$get_RHS_matrix()
#> 7 x 10 sparse Matrix of class "dgCMatrix"
#>    [[ suppressing 10 column names '1', '2', '3' ... ]]
#>                            
#> small   1 . 1 . . 1 . . . .
#> medium  . . . . . . 1 1 1 .
#> large   . . . . . . 1 1 . 1
#> near    1 . . . . 1 . . 1 1
#> far     . . . 1 1 . 1 . . .
#> moon    . 1 . 1 1 . . . . .
#> no_moon . . . . . 1 . 1 1 1

The main practical use of an ImplicationSet is to compute the closure of a set of attributes, by using the closure() function:

# Let us build a set of attributes
S <- SparseSet$new(attributes = fc_planets$attributes)
S$assign(large = 1, far = 1)
S
#> {large, far}

fc_planets$implications$closure(S)$closure
#> {large, far, moon}

Cardinality, size and support of the implication set

Some quantities can be computed for an ImplicationSet:

fc_planets$implications$cardinality()
#> [1] 10
sizes <- fc_planets$implications$size()
# Total number of attributes in the LHS and the RHS
colSums(sizes)
#> LHS RHS 
#>  25  23
fc_planets$implications$support()
#>  [1] 0.2222222 0.5555556 0.4444444 0.2222222 0.2222222 0.0000000 0.0000000
#>  [8] 0.0000000 0.0000000 0.0000000

Export to LaTeX

A nice feature is the ability to export an ImplicationSet to LaTeX format:

fc_planets$implications$to_latex()
#> \begin{longtable}{rrcl}
#> 1: &\ensuremath{\left\{\mathrm{no_moon}\right\}}&\ensuremath{\Rightarrow}&\ensuremath{\left\{\mathrm{small},\, \mathrm{near}\right\}}\\
#> 2: &\ensuremath{\left\{\mathrm{far}\right\}}&\ensuremath{\Rightarrow}&\ensuremath{\left\{\mathrm{moon}\right\}}\\
#> 3: &\ensuremath{\left\{\mathrm{near}\right\}}&\ensuremath{\Rightarrow}&\ensuremath{\left\{\mathrm{small}\right\}}\\
#> 4: &\ensuremath{\left\{\mathrm{large}\right\}}&\ensuremath{\Rightarrow}&\ensuremath{\left\{\mathrm{far},\, \mathrm{moon}\right\}}\\
#> 5: &\ensuremath{\left\{\mathrm{medium}\right\}}&\ensuremath{\Rightarrow}&\ensuremath{\left\{\mathrm{far},\, \mathrm{moon}\right\}}\\
#> 6: &\ensuremath{\left\{\mathrm{medium},\, \mathrm{large},\, \mathrm{far},\, \mathrm{moon}\right\}}&\ensuremath{\Rightarrow}&\ensuremath{\left\{\mathrm{small},\, \mathrm{near},\, \mathrm{no_moon}\right\}}\\
#> 7: &\ensuremath{\left\{\mathrm{small},\, \mathrm{near},\, \mathrm{moon},\, \mathrm{no_moon}\right\}}&\ensuremath{\Rightarrow}&\ensuremath{\left\{\mathrm{medium},\, \mathrm{large},\, \mathrm{far}\right\}}\\
#> 8: &\ensuremath{\left\{\mathrm{small},\, \mathrm{near},\, \mathrm{far},\, \mathrm{moon}\right\}}&\ensuremath{\Rightarrow}&\ensuremath{\left\{\mathrm{medium},\, \mathrm{large},\, \mathrm{no_moon}\right\}}\\
#> 9: &\ensuremath{\left\{\mathrm{small},\, \mathrm{large},\, \mathrm{far},\, \mathrm{moon}\right\}}&\ensuremath{\Rightarrow}&\ensuremath{\left\{\mathrm{medium},\, \mathrm{near},\, \mathrm{no_moon}\right\}}\\
#> 10: &\ensuremath{\left\{\mathrm{small},\, \mathrm{medium},\, \mathrm{far},\, \mathrm{moon}\right\}}&\ensuremath{\Rightarrow}&\ensuremath{\left\{\mathrm{large},\, \mathrm{near},\, \mathrm{no_moon}\right\}}\\
#> \end{longtable}

Filtering of implications

Sometimes it is needed to work with a subset of the implications, using only the implications that fulfill certain conditions:

# Implications with P1 and P2 in the LHS and P5 in the RHS
fc_I$implications$filter(lhs = c("P1", "P2"), 
                         rhs = "P5")
#> Implication set with 2 implications.
#> Rule 1: {P1 [0.5], P2 [0.5], P4 [0.5]} -> {P1, P2, P3, P4, P5, P6}
#> Rule 2: {P1, P2, P3, P6} -> {P4, P5}

Simplification Logic

In this package, we have implemented logic tools to operate on the implications.

First, some simplification rules have been developed, named reduction, composition, generalization and simplification, that can be applied using the apply_rules() function:

fc_I$implications$apply_rules(rules = c("composition",
                                        "simplification"))
#> Processing batch
#> --> composition: from 12 to 12 in 0.002 secs.
#> --> simplification: from 12 to 12 in 0.053 secs.
#> Batch took 0.058 secs.

This enables the reduction of the cardinality and/or the size of the ImplicationSet.

In addition, the “simplification” rule to remove redundancies can be used in the computation of the closure of a set, to provide a reduced set of implications that is inferred from the set of attributes:

# Let us build a set of attributes
S <- SparseSet$new(attributes = fc_planets$attributes)
S$assign(large = 1, far = 1)
S
#> {large, far}

fc_planets$implications$closure(S, reduce = TRUE)
#> $closure
#> {large, far, moon}
#> $implications
#> Implication set with 7 implications.
#> Rule 1: {medium} -> {small, near, no_moon}
#> Rule 2: {small, near, no_moon} -> {medium}
#> Rule 3: {small, near} -> {medium, no_moon}
#> Rule 4: {small} -> {medium, near, no_moon}
#> Rule 5: {small, medium} -> {near, no_moon}
#> Rule 6: {no_moon} -> {small, near}
#> Rule 7: {near} -> {small}

Recommendations

One of the final applications of an ImplicationSet is the easy development of a recommendation system where, from an attribute set, the system would infer the value to other attribute. This is done by the recommend() function, which internally computes the closure of the attribute set:

S <- SparseSet$new(attributes = fc_I$attributes)
S$assign(P1 = 1, P4 = 0.5)

fc_I$implications$recommend(S, attribute_filter = c("P3", "P5"))
#> P3 P5 
#>  1  1