Implication (information science)

In formal concept analysis (FCA) implications relate sets of properties (or, synonymously, of attributes). An implication  AB  holds in a given domain when every object having all attributes in A also has all attributes in B. Such implications characterize the concept hierarchy in an intuitive manner. Moreover, they are "well-behaved" with respect to algorithms. The knowledge acquisition method called attribute exploration uses implications.[1]

Definitions

edit

An implication  AB  is simply a pair of sets AM, BM, where M is the set of attributes under consideration. A is the premise and B is the conclusion of the implication  AB . A set C respects the implication  AB  when ¬(CA) or CB.

A formal context is a triple (G,M,I), where G and M are sets (of objects and attributes, respectively), and where IG×M is a relation expressing which objects have which attributes. An implication that holds in such a formal context is called a valid implication for short. That an implication is valid can be expressed by the derivation operators:  AB  holds in (G,M,I) iff AB or, equivalently, iff BA".[2]

Implications and formal concepts

edit

A set C of attributes is a concept intent if and only if C respects all valid implications. The system of all valid implications therefore suffices for constructing the closure system of all concept intents and thereby the concept hierarchy.

The system of all valid implications of a formal context is closed under the natural inference. Formal contexts with finitely many attributes possess a canonical basis of valid implications,[3] i.e., an irredundant family of valid implications from with all valid implications can be inferred. This basis consists of all implications of the form PP"\P, where P is a pseudo-intent, i.e., a pseudo-closed set in the closure system of intents. See[1] for algorithms.

References

edit
  1. ^ a b Ganter, Bernhard and Obiedkov, Sergei (2016) Conceptual Exploration. Springer, ISBN 978-3-662-49290-1
  2. ^ Ganter, Bernhard and Wille, Rudolf (1999) Formal Concept Analysis -- Mathematical Foundations. Springer, ISBN 978-3-540-62771-5
  3. ^ Guigues, J.L. and Duquenne, V. Familles minimales d'implications informatives résultant d'un tableau de données binaires. Mathématiques et Sciences Humaines 95 (1986): 5-18.