Graded preconcept lattices: An extension of FCA using functional degrees of inclusion and similarity

This paper introduces a more nuanced FCA framework by defining a ‘degree of conceptuality’ for any pair of fuzzy sets (a preconcept). This creates a graded lattice where standard concepts are the top-cut, and lower cuts represent ‘approximate’ lattices. The idea is also extended to implications, defining ‘phi-valid’ rules.

Keywords

Graded preconcept lattice, Functional inclusion, Degree of conceptuality, Phi-valid implications, Approximate FCA, F-inclusion

Standard L-FCA defines a crisp dichotomy: a pair $(A,B)$ either is or is not a concept. This paper introduces a more nuanced framework based on the functional degree of inclusion and similarity. We move from the set of concepts to the full lattice of “preconcepts” $(A,B) \in L^G \times L^M$ and equip it with a “degree of conceptuality,” $\mathcal{D}(A,B)$. This degree measures how close the pair is to being a true formal concept. We show that the set of standard formal concepts corresponds to the top-cut of this graded preconcept lattice. We study the algebraic structure of the intermediate $\alpha$-cuts of this lattice, revealing a nested hierarchy of “approximate” concept lattices. Furthermore, we extend this graded approach to implications, defining “$\varphi$-valid” implications that hold up to a certain functional degree. This work provides a deep generalization of FCA, allowing for a multi-granularity analysis of conceptual structures and dependencies.

Introduction

The definition of a formal concept $(A,B)$ requires strict equality: $A^\uparrow = B$ and $B^\downarrow = A$. This rigidity can be a limitation when dealing with noisy or approximate data, where a pair might be “almost” a concept but fails the strict criteria.

Inspired by the work of Šostak et al. and the theory of functional inclusion by Madrid and Ojeda-Aciego, we propose a framework to “grade” the notion of a concept. Instead of a binary decision, we assign to every possible pair of fuzzy sets (a preconcept) a degree of conceptuality. A higher degree signifies that the pair is closer to satisfying the closure conditions.

This leads to a new, richer structure: the graded preconcept lattice. By taking cuts at different levels of conceptuality, we can explore a spectrum of conceptual structures, from a very relaxed one at low grades to the standard, crisp concept lattice at the highest grade. Our contributions are:

1. The formal definition of the “degree of conceptuality” for preconcepts based on functional similarity indices.
2. A theoretical analysis of the algebraic structure of the $\alpha$-cuts of the graded preconcept lattice.
3. The introduction of “$\varphi$-valid implications” and an exploration of their relationship to standard implications and association rules.

Methodology and expected theoretical results

The framework builds upon the similarity indices $S_{eq}, S_{\cup\cap}, S_{\wedge}$ from.

Graded preconcept lattices

For any preconcept $(A,B) \in L^G \times L^M$, we define its degree of conceptuality as: $$\mathcal{D}(A,B) = S(A^\uparrow, B) \wedge S(A, B^\downarrow)$$ where $S$ is a chosen similarity index. * Main theoretical result 1: We will prove that the $\top$-cut of this graded structure, $\{(A,B) \mid \mathcal{D}(A,B) = \top\}$, is precisely the standard concept lattice $\mathfrak{B}(\mathbb{K})$. We will then study the structure of the $\alpha$-cuts for $\alpha < \top$. We hypothesize that they form specific types of ordered algebraic structures (e.g., semi-lattices or lattices under certain conditions on $\alpha$).

$\varphi$-valid implications

We relax the validity condition for an implication $A \to B$. Instead of requiring $B \subseteq A^{\downarrow\uparrow}$, we define it to be $\varphi$-valid (for some $\varphi \in \Omega$, the lattice of inclusion indices) if: $$\mathrm{Inc}(B, A^{\downarrow\uparrow}) \ge \varphi$$ * Main theoretical result 2: We will explore the properties of $\varphi$-validity. We will investigate the relationship between this new concept and standard association rules. An implication that is $\varphi$-valid for a “high” $\varphi$ but not $\top$-valid is essentially a high-confidence association rule. We will formalize this connection and explore whether a basis of $\varphi$-valid implications can be defined.

Work plan

• Months 1-4: Formalize the theory of graded preconcept lattices. Prove the main result about the structure of $\alpha$-cuts.
• Months 5-7: Develop the theory of $\varphi$-valid implications. Establish the formal connection to association rules.
• Months 8-10: Investigate the potential for defining a “basis” of $\varphi$-valid implications and sketch an algorithm for its computation.
• Months 11-12: Write the manuscript for a journal that appreciates deep theoretical generalizations of formal systems.

Potential target journals

1. Fuzzy Sets and Systems (Q1): The absolute best target, as the work is a direct and deep extension of fuzzy set theory applied to FCA’s foundations.
2. International Journal of Approximate Reasoning (Q2): An excellent fit due to its focus on non-standard logics and reasoning under uncertainty.
3. Order: A strong candidate if the paper focuses primarily on the algebraic structure of the $\alpha$-cuts and the graded preconcept lattice.

Minimum viable article (MVA) strategy

The two main ideas (graded concepts and graded implications) are distinct enough to warrant separate publications.

• Paper 1 (The MVA - graded preconcept lattices):
  • Scope: This paper introduces the concept of the “degree of conceptuality” and the graded preconcept lattice. The main contribution would be the theoretical analysis of the structure of the $\alpha$-cuts. The paper would show how standard FCA emerges as a special case.
  • Goal: To introduce a major theoretical generalization of the concept lattice itself.
  • Target venue: A top-tier theoretical journal like Fuzzy Sets and Systems.
• Paper 2 (Graded implications):
  • Scope: This paper introduces the concept of $\varphi$-validity for implications. It would build the formal connection to association rules and explore the logical properties of this new system. The main goal would be to investigate the existence of and algorithms for finding bases of $\varphi$-valid implications.
  • Goal: To provide a logical foundation for approximate rules that is more general than standard association rules.
  • Target venue: International Journal of Approximate Reasoning.