Análisis Formal de Conceptos
(Inspirado en el artículo de FCA que se puede leer en inglés de la Wikipedia,
junto con las valiosas explicaciones de Joaquín Borrrego y Juan Galán)
El análisis formal de conceptos proporciona una metodología para derivar una jerarquía de conceptos (como una ontología) a partir de una colección de objetos y las propiedades que verifican. Cada concepto de la jerarquía obtenida representa, simultáneamente, un conjunto de objetos que comparten los mismos valores para cierto conjunto de propiedades, y dicho conjunto de propiedades.
El término fue introducido por Rudolf Wille en 1984, y se basa en la Teoría de Retículos y en la Teoría del Orden, que fue desarrollada por Garrett Birkhoff y otros en la década de los años 30, y desde su introducción ha sido aplicada con éxito en campos tan variados como la minería de datos, minería de textos, gestión del conocimiento, web semántica, desarrollo de software, biología, etc.
Introducción e Historia
La motivación original del análisis formal de conceptos (FCA, a partir de ahora) era la representación de retículos completos de objetos y sus propiedades por medio de contextos formales, que son tablas de datos que representan relaciones binarias entre objetos y atributos. En esta teoría, un concepto formal se define como un par formado por un conjunto de objetos (extensión) y un conjunto de atributos (intensión) de modo que la extensión está formada por todos los objetos que comparten los atributos dados, y la intensión la forman todos los atributos compartidos por los objetos dados. De este modo, el FCA formaliza matemáticamente las nociones clásicas de extensión e intensión.
Los pares de conceptos formales pueden estar parcialmente ordenados por la relación de contención entre sus conjuntos de objetos o, como veremos, de forma equivalente por la relación de contención (en orden contrario) entre sus conjuntos de atributos. Este orden produce un sistema jerarquizado de sub y superconceptos que se puede visualizar como un diagrama de líneas. Con estas relaciones jerárquicas la familia de conceptos obedece los axiomas matemáticos que definen un retículo.
La teoría en su forma actual se remonta al grupo de investigación dirigido por Rudolf Darmstadt Wille, Bernhard Ganter y Peter Burmeister, donde se originó el análisis de conceptos formales en la década de 1980. La base matemática, sin embargo, ya se había creado por Garrett Birkhoff en la década de los años 30 como parte de la teoría general de retículos. Antes del trabajo del grupo de Darmstadt, ya existían enfoques similares de varios grupos franceses, y sus fundamentos filosóficos apuntan principalmente a Charles S. Peirce y el pedagogo Hartmut von Hentig.
Motivación y trasfondo filosófico
En su artículo "Reestructurazión de la Teoría de Retículos" (de 1982, con el que se inicia el FCA como disciplina matemática) Rudolf Wille parte de un descontento con la teoría de retícluos en particular y con las matemáticas puras en general:
La producción de resultados teóricos - a menudo alcanzados por medio de "elaboradas gimnasias mentales" - eran impresionantes, pero las conexiones entre dominios vecinos, o incluso entre partes de una misma teoría se estaban debilitando.
La reestructuración de la teoría de retículos es un intento de revitalizar las conexiones entre dominios mediante la reinterpretación de la teoría de la manera más concreta posible, con el fin de propiciar una mejor comunicación entre los teóricos de retículos y los usuarios potenciales de dicha teoría.
Este objetivo se remonta a Hartmut von Hentig, quien en 1972 pidió una reestructuración de las ciencias con el fin de conseguir una mejor enseñanza y de hacer a la ciencia más asequible, tanto con el fin de conocerla mejor como para poder criticarla de una forma más cercana (es decir, sin necesidad de un conocimiento especializado).
El FCA corrige el punto de partida de la teoría reticular en el desarrollo de la lógica formal en el siglo XIX, donde un concepto, como predicado unario, se había reducido a su extensión. El objetivo fue trabajar con una visión de los conceptos menos abstracta, haciendo uso también de la intensión, una orientación que provenía de la lingüística y de la lógica conceptual clásica.
FCA tiene como objetivo aclarar los conceptos siguiendo la máxima de Charles S. Peirce de desplegar las propiedades observables y elementales de los objetos. En su filosofía tardía, Peirce supone que el pensamiento lógico tiene como objetivo percibir la realidad, por medio de la triada: concepto, juicio y conclusión. En este sentido, Wille dice:
El objetivo y el significado del FCA como teoría matemática sobre conceptos y sus jerarquías es apoyar la comunicación racional entre seres humanos mediante el desarrollo matemático de estructuras conceptuales apropiadas que se puedan manipular con la lógica.
Contextos y conceptos
Un contexto formal, en FCA, es una tripleta \(K = (O, A, P)\), donde \(O\) es un conjunto de objetos, \(A\) es un conjunto de atributos y \(P\) una relación binaria, \(P\subseteq O\times A\), que muestra qué objeto posee qué atributo. Formalmente, se puede considerar como un grafo bipartito que refleje las relaciones entre los conjuntos \(O\) y \(A\), o también como una una tabla con los objetos ocupando las filas de la tabla, los atributos en las columnas, y de forma que un valor booleano en la celda \((x, y)\) significa que el objeto \(x\) tiene el atributo \(y\).
Con el fin de poder trabajar más cómodamente con la relación, \(P\), entre objetos y atributos, definimos la operación de derivación (\('\)) de forma que, si tenemos dos subconjuntos \(X\subseteq O\) e \(Y\subseteq A\):
\(X'= \{y\in A:\ \forall x\in X P(x,y)\}\)
\(Y'= \{x\in O:\ \forall y\in Y P(x,y)\}\)
El operador \(''\) (es decir, aplicar el operador \('\) dos veces) verifica algunas propiedades interesantes que serán fundamentales para poder desarrollar la teoría formal (matemáticamente, por verificar las siguientes propiedades, decinos que es un operador de cierre):
- idempotente: \(X'''' = X''\),
- monótona: \(X_1\subseteq X_2 \rightarrow X_1''\subseteq X_2''\),
- extensa: \(X\subseteq X''\).
Observa que, en general, no se verifica que \(X''=X\) (puedes buscar contraejemplos usando la tabla mostrada anteriormente). Cuando un conjunto de objetos, \(X\subseteq O\) verifica que \(X''=X\) se llama cerrado. Una definición similar se obtiene para hablar de conjuntos de atributos cerrados, es decir, subconjuntos del conjunto \(A\).
Un par \((X,Y)\) se llama un concepto formal de un contexto \(K\) si verifica:
- \(X\subseteq O\), \(Y\subseteq A\),
- \(X '= Y\), \(Y '= X\).
Aunque puede parecer una definición un poco arbitraria, intuitivamente un par, \((X,Y)\), es un concepto en \(K\) si:
- cada objeto en \(X\) tiene todos los atributos de \(Y\),
- para cada objeto en \(O\) que no está en \(X\), existe un atributo en \(Y\) que el objeto no tiene,
- para cada atributo en \(A\) que no está en \(Y\), hay un objeto en \(X\) que no tiene ese atributo.
Luego, en cierta forma, conseguimos introducir en la definición formal de concepto las dos partes que filosóficamente considerábamos esenciales: por una parte, el conjunto de objetos con propiedades comunes, y por otra el conjunto de atributos que caracterizan a dichos objetos. Únicamente aquellos pares de conjuntos que tienen una conexión perfectamente cerrada establecen un concepto por sí mismos... allí donde no hay atributos faltantes ni contraejemplos entre sus objetos. En esta situación, los conjuntos \(X\) e \(Y\) son cerrados y se llaman, respectivamente, la extensión y la intensión del concepto. Para un conjunto de objetos, \(X\), el conjunto de sus atributos comunes, \(X'\), describe de alguna forma la similitud de los objetos de \(X\), mientras que el conjunto \(X''\) es la agrupación de objetos que tienen como atributos comunes a \(X'\) (en particular, estarán todos los objetos de \(X\), es decir, \(X\subseteq X''\)).
Por tanto, un concepto, en la representación matricial, se puede reconocer por medio de una submatriz máximal (no necesariamente formada por celdas contiguas) de tal manera que todas las celdas de la submatriz son verdaderas. En la representación como grafo bipartito se reconocerá como subgrafo bipartito completo (es decir, aquel que tiene todas las aristas posibles).
Retículo de Conceptos de un contexto
Los conceptos definidos anteriormente pueden ser parcialmente ordenados por inclusión:
Si \((X_1, Y_1)\) y \((X_2, Y_2)\) son conceptos, se define un orden parcial, \(\leq\), de forma que \((X_1, Y_1) \leq (X_2, Y_2)\) si \(X_1 \subseteq X_2\), o equivalentemente, si \(Y_2\subseteq Y_1\).
Cada par de conceptos en este orden parcial tiene una única máxima cota inferior (es decir, que se alcanza), que es el concepto generado por \(X_1\cap X_2\). Simétricamente, cada par de conceptos en este orden parcial tiene una única mínima cota superior, que es el concepto generado por los atributos \(Y_1\cap Y_2\).
Estas operaciones que calculan el máximo y mínimo de dos conceptos satisfacen los axiomas que definen un retículo, y es fácil probar que cualquier retículo finito puede ser generado como el retículo de conceptos de algún contexto (por ejemplo, si \(L\) es el retículo, se crea un contexto en el que \(O=A=L\) y la relación \(P(x,y) \leftrightarrow x\leq y\) en el retículo).
Álgebra de conceptos de un contexto
Modelar la negación en un contexto formal es algo problemático, porque el complementario de un concepto \((X,Y)\) (que es \((O-X, A-Y)\)) en general no es un concepto. Sin embargo, se puede considerar la unión de todos los conceptos cuya extensión está contenida en \(O-X\); o, por dualidad, la intersección de aquellos conceptos cuya intensión estén contenidos en \(A-Y\). Estas dos operaciones se conocen como negación débil y oposición débil, respectivamente.
En términos de la derivación que vimos en el apartado anterior (y teniendo en cuenta que un par \((X,Y)\) es un concepto si y solo si \(X'=Y\) y \(Y'=X\)), la negación débil y la oposición débil quedarían, respectivamente, como:
\((X,Y)^\Delta=((O-X)'',(O-X)')\)
\((X,Y)^\square=((A-Y)', (A-Y)'')\)
El retículo de conceptos con estas dos operaciones se conoce como álgebra de conceptos de un contexto. La negación débil en un retículo verifica ciertas propiedades que la hacen funcionar como un complementario débil, es decir, si \(c\) y \(d\) son dos conceptos:
- \(c^\Delta \leq c\),
- \((c\cap d) \cup (c\cap d^\Delta)=c\).
Recuperando el contexto a partir del diagrama de líneas
El diagrama de líneas del retículo de conceptos codifica suficiente información como para permitirnos recuperar el contexto original que representa:
- Cada objeto del contexto corresponde a un elemento del retículo, aquel que está formado por el conjunto de objetos minimal que contiene ese objeto, y por un conjunto de atributos que consta de todos los atributos de dicho objeto. En la representación del diagrama, estaría situado en el primer nivel que aparece en la parte inferior.
- Simétricamente, cada atributo del contexto corresponde a un elemento del retículo, el que tiene el conjunto de atributos minimal que contiene ese atributo, y con un conjunto de objetos formado por todos los objetos con ese atributo. En la representación del diagrama, estaría situado en el último nivel que aparece en la parte superior.
Podemos etiquetar los nodos del diagrama de líneas con los objetos y atributos a que corresponden. Con este etiquetado, el objeto \(x\) tiene el atributo \(y\) si y sólo si existe un camino monótono (es decir que siempre crece, o decrece, según el orden del retículo) de \(x\) a \(y\) en el diagrama.
Implicaciones y reglas de asociación con FCA
Una vez formalizados matemáticamente los conceptos, puede resultar relativamente sencillo trasladar las relaciones lógicas que encontramos entre atributos... aunque debemos tener en cuenta que las relaciones lógicas que se obtengan son aquellas que vengan confirmadas por nuestro contexto, que podría representar un conocimiento concreto en un instante de tiempo, pero que podría variar al añadir un mayor número de objetos o atributos. Por ejemplo, que en el ejemplo siguiente podamos decir que "ser animal de jungla" implica "ser mamífero" se debe a que todos los objetos que verifican la propiedad "ser animal de jungla" verifican "ser mamífero", pero en el momento que introduzcamos un objeto nuevo que sea de la jungla (por ejemplo, un manglar) y no sea mamífero, esa implicación deja de ser cierta. Por supuesto, podemos trabajar con varios atributos simultáneamente.
Consecuentemente, en FCA podemos formalizarlo de la siguiente forma: dados \(A\) y \(B\) subconjuntos de atributos, diremos que se tiene la implicación \(A\rightarrow B\) si se verifica \(A'\subseteq B'\), es decir, todos los objetos que tienen cada atributo de \(A\) también tienen cada atributo de \(B\) (observa que es coherente con la implicación intuitiva que dimos en el apartado anterior).
Con esta definición, las implicaciones obedecen las reglas de Armstrong (reflexiva, aumentativa y transitivia) comunes en las dependencias funcionales que se dan entre los atributos de una base de datos:
\[\frac{B \subseteq A}{A \rightarrow B},\ \frac{A \rightarrow B}{A\cup C \rightarrow B\cup C},\ \frac{X \rightarrow B, B \rightarrow C} {A \rightarrow C}\]
A partir de la definición de implicación y de las propiedades básicas que verifica, podemos definir un cálculo lógico que nos permitiría realizar sistemas de deducción completos sobre el contexto actual. En cierta forma, hemos pasado de tener un conocimiento por ejemplos a disponer de un conocimiento abstracto que introduce sistemas de razonamiento más elaborados en nuestro mundo, partiendo únicamente de las observaciones concretas que hemos realizado... es decir, hemos aprendido reglas generales a partir de ejemplos.
Ejemplo
Vamos a ver un ejemplo sencillo de retículo asociado a un contexto de objetos-atributos. Supongamos el siguiente contexto, que viene dado en forma de tabla de pares (objeto,atributo) por la siguiente tabla, y se muestra el diagrama de conceptos asociado a este contexto resultaría:
Puedes jugar con un pequeño generador de retículos aquí:
En una futura entrada presentaremos algo acerca de algoritmos para calcular los retículos de conceptos a partir de la tabla del contexto y mostraremos cómo programar alguno de los algoritmos básicos para hacernos una idea de la complejidad computacional que puede tener.