Boolean Matrix Factorization (BMF) is a technique used to decompose a binary matrix \(I\) (representing a formal context) into two smaller binary matrices:
The goal is that the Boolean product of these matrices approximates the original data: \[ I \approx A \circ B \] where the composition \(\circ\) is the standard Boolean matrix product (i.e., using logical OR for addition and logical AND for multiplication). In the context of Formal Concept Analysis (FCA), this corresponds to finding a small subset of formal concepts (which act as factors) that can explain or reconstruct the original data.
[!NOTE] Currently,
fcaRonly supports factorization for Boolean (binary) contexts. If you have a fuzzy context, you must binarize it first.
fcaR implements several state-of-the-art Boolean Matrix
Factorization algorithms:
Let’s use a binary dataset describing different dog breeds and their characteristics. We want to see if we can reduce these breeds to a few “archetypes” (factors).
We define a binary matrix where each row represents a dog breed and each column represents a characteristic:
# Create a binary matrix (5 breeds x 5 attributes)
I <- matrix(c(
1, 1, 0, 0, 0, # Labrador: Friendly, Playful
1, 1, 0, 0, 0, # Golden Retriever: Friendly, Playful
0, 0, 1, 1, 0, # German Shepherd: Guard, Aggressive
0, 0, 1, 1, 0, # Rottweiler: Guard, Aggressive
1, 0, 0, 0, 1 # Chihuahua: Friendly, Small
), nrow = 5, byrow = TRUE)
rownames(I) <- c("Labrador", "Golden Ret.", "G. Shepherd", "Rottweiler", "Chihuahua")
colnames(I) <- c("Friendly", "Playful", "Guard", "Aggressive", "Small")
# Initialize the FormalContext
fc <- FormalContext$new(I)
print(fc)
#> FormalContext with 5 objects and 5 attributes.
#> Friendly Playful Guard Aggressive Small
#> Labrador X X
#> Golden Ret. X X
#> G. Shepherd X X
#> Rottweiler X X
#> Chihuahua X XWe apply the GreConD algorithm to decompose the context:
Let’s print the two factor matrices to see how they describe our data:
This matrix connects the original dog breeds (objects) to the discovered latent factors:
print(A$incidence())
#> F1 F2 F3
#> Labrador 1 0 0
#> Golden Ret. 1 0 0
#> G. Shepherd 0 1 0
#> Rottweiler 0 1 0
#> Chihuahua 0 0 1F1) is present in
Labrador and Golden Ret..F2) is present in
G. Shepherd and Rottweiler.F3) is present only in
Chihuahua.This matrix connects the latent factors to the original characteristics (attributes):
print(B$incidence())
#> Friendly Playful Guard Aggressive Small
#> F1 1 1 0 0 0
#> F2 0 0 1 1 0
#> F3 1 0 0 0 1F1) is characterized by the
attributes Friendly and Playful.F2) is characterized by the
attributes Guard and Aggressive.F3) is characterized by the
attributes Friendly and Small.Combining these observations: 1. Factor 1
(F1) represents the archetype of a
“Friendly and Playful Dog” (exhibited by Labradors and
Golden Retrievers). 2. Factor 2 (F2)
represents the archetype of a “Guard/Protective Dog”
(exhibited by German Shepherds and Rottweilers). 3. Factor 3
(F3) represents the archetype of a “Small
and Friendly Dog” (exhibited by Chihuahuas).
The Rice-Siff Factorization (RSF) family represents a hybrid BMF approach. Instead of performing an exhaustive combinatorial sweep of the attribute space (like GreConD), it guides the greedy selection of factors using a hierarchical agglomerative clustering method derived from the Rice-Siff algorithm.
The core of the RSF algorithm relies on a state-dependent semi-metric \(\rho_{un}\), which quantifies the distance between candidate concepts based on the currently uncovered cells in the residual relation \(R_{un}\): \[ \rho_{un}((X_1, Y_1), (X_2, Y_2)) = 1 - \frac{|(X_1 \times Y_1) \cap (X_2 \times Y_2) \cap R_{un}|}{|(X_1 \times Y_1) \cup (X_2 \times Y_2)|} \]
By prioritizing merges that overlap on remaining uncovered cells, the agglomeration natively converges to formal concepts that maximize the coverage of the residual matrix.
To prevent the combinatorial explosion in high-dimensional contexts, RSF-ES introduces two key optimizations: 1. Zero-weight Filtering: Candidates whose generating components have no coverage on \(R_{un}\) (\(w = 0\)) are pruned early. 2. Topological Pruning: The agglomerative loop is immediately broken when the minimum distance reaches \(\rho_{un} = 1.0\). In graph-theoretic terms, a distance of \(1.0\) indicates that the candidates belong to disjoint connected components in the residual relation. Fusing them would restrict the resulting formal intent without yielding any structural gain, making further merging redundant.
These optimizations allow RSF-ES to achieve up to a 10x speedup on dense or high-dimensional matrices compared to standard RSF while maintaining mathematical exactness.
You can use both RSF and RSF-ES directly
inside the factorize method:
# Factorize using RSF
res_rsf <- fc$factorize(method = "RSF")
print(res_rsf$factor_attribute$incidence())
#> Friendly Playful Guard Aggressive Small
#> F1 1 1 0 0 0
#> F2 0 0 1 1 0
#> F3 1 0 0 0 1
# Factorize using RSF-ES (Highly optimized)
res_rsfes <- fc$factorize(method = "RSF-ES")
print(res_rsfes$factor_attribute$incidence())
#> Friendly Playful Guard Aggressive Small
#> F1 1 1 0 0 0
#> F2 0 0 1 1 0
#> F3 1 0 0 0 1For large binary datasets, ASSO is a classic alternative heuristic. It uses pairwise association confidence to generate candidate factors.
# Factorize using ASSO
res_asso <- fc$factorize(method = "ASSO", threshold = 0.6)
# Print the resulting factor-attribute matrix
print(res_asso$factor_attribute$incidence())
#> Friendly Playful Guard Aggressive Small
#> F1 1 1 0 0 0
#> F2 0 0 1 1 0
#> F3 1 0 0 0 1The authors are grateful to Dr. Martin Trnecka, from Palacký University Olomouc, for his generosity in sharing the original source code and granting permission for its porting to R and C/C++. This contribution was pivotal in enabling the high-performance implementation of these algorithms and the subsequent rigorous comparative analysis.