La Teoría de Conjuntos Aproximativos
(TCA), que viene de la denominación inglesa Rough Set
Theory (Pawlak, 1982), es una teoría que se ha venido
desarrollando desde la década de los 80, cuyo autor es el
investigador polaco Zdzislaw Pawlak. A través de todo este
tiempo, como
toda teoría, se ha ido enriqueciendo con nuevos aportes,
derivados de una mayor investigación sobre sus alcances y
bondades, tanto para aplicaciones teóricas como
prácticas. Teniendo en cuenta que es una herramienta Data
Mining, actualmente tiene aplicaciones en diferentes campos,
sobretodo en sistemas de apoyo
a la decisión y sistemas gerenciales de información.
Las herramientas
Data Mining, definidas de una forma resumida, vienen a ser el
conjunto de procedimientos y
técnicas que buscan extraer patrones dentro
de un conjunto de datos (Marakas,
1998). En ese sentido, la TCA se basa en el concepto de
"indiscernibilidad". Considerando que indiscernir
significa no conseguir distinguir una cosa de otra, por medio de
los sentidos o
de la inteligencia
humana, lo que busca la TCA es encontrar todos aquellos objetos
(acciones,
alternativas, candidatos, pacientes, etc) que producen un mismo
tipo de información, es decir, aquellos objetos que son
"indiscernibles" (Pawlak y Slowinski, 1993). A partir de este
concepto es que entonces se generan las bases de matemáticas de esta teoría.
Así, el presente trabajo busca
mostrar los alcances de esta teoría, y mediante un ejemplo
simple en el área del diagnóstico médico, tratar de dar un
mejor entendimiento de ella.
Palabras clave: Teoría de Conjuntos
Aproximativos, Rough Set Theory, Data Mining
Se tenemos en cuenta que a todo objeto se le puede
asociar algún tipo de información basados en sus
atributos/características, entonces es factible
representar estos atributos por medio de una tabla de
información. Dentro de una tabla de
información, las filas representan los objetos, en cuanto
que las columnas representan los atributos. Las entradas de la
tabla, que no son otra cosa más que pares (objeto,
atributo), vienen a ser los valores de
cada objeto para cada atributo. La tabla de información
debe ser entendida, en términos prácticos, como una
matriz finita,
tal como se observa en la tabla 1.
|
| Atributo 1 |
| Atributo 2 |
| ………. | Atributo n |
Objeto 1 |
| Valor 1, 1 |
| Valor 1, 2 |
| ………. | Valor 1, n |
Objeto 2 |
| Valor 2, 1 |
| Valor 2, 2 |
| ………. | Valor 2, n |
……… |
| ………. |
| ………. |
| ………. | ………. |
Objeto m |
| Valor m, 1 |
| Valor m, 2 |
| ………. | Valor m, n |
Tabla 1: Representación de una
tabla de información
En relación a los atributos, debemos mencionar
que la TCA divide los atributos en: atributos de
condición (criterios, pruebas,
síntomas, etc) y en atributos de decisión
(decisiones, clasificaciones, taxonomias, etc). La TCA usa la
noción de atributo, en vez de criterio, debido a que el
dominio
(escala) de un
criterio tiene que estar ordenado de acuerdo a las preferencias,
sean estas crecientes o decrecientes; en cuanto que, el dominio
de un atributo no necesita ser ordenado. De esa forma, la
noción de criterio puede ser usada cuando el orden de la
preferencia del dominio del atributo es importante en
algún determinado contexto (Zopounidis y Dimitras,
1998).
2.1 Tabla de Información y Relación de
Indiscernibilidad
Esta teoría supone que una situación de
decisión puede ser representada por una tabla de
información, formada por una cuádrupla:
S = <U, Q, V, f>
donde:
U es un conjunto finito de objetos,
Q es un conjunto finito de atributos,
V = (Vq es el dominio del atributo q), y
f: U ´
Q ® V
es una función,
llamada función de información, tal que
f(x,q) Î
Vq para todo q Î Q, x Î U
Así, dado que S = <U, Q, V, f> esta
definida como una tabla de información, y
PÍ
Q, además que, x e
y Î
U; entonces, las variables
x e y son indiscernibles para el conjunto de
atributos P definidos en S, si y solo si
f(x,q)=f(y,q), para todo q Î P. Cada
PÍ
Q da lugar a una relación binaria
en U, denominada relación de
indiscernibilidad, denotada por Ip, y que
representa una relación de equivalencia para cada
P. Las clases de equivalencia de la relación
Ip son llamadas de conjuntos elementales
en S, e Ip(x) denota un conjunto
P-elemental conteniendo objetos x Î U. La familia de
todas las clases de equivalencia de la relación
Ip en U, son denotadas como
U |
Ip.
A cada objeto se asocia un descriptor, denotado por
DESP(X), el cual hace una descripción del conjunto P-elemental
x Î
U |
Ip en relación a
los valores de
los atributos de P, es decir:
DESP(x) = <(q,v) :
f(x,q)=v, "
x Î
U, "
q Î
P>
2.2 Aproximaciones de los Conjuntos y
Regiones
Sea PÍ Q y
YÍ
U. Entonces, la aproximación
P-inferior de Y (denotada por PY) y la
aproximación P-superior de Y (denotada por
Y) son
definidas de la siguiente manera:
PY = {x Î U:
Ip(x)Í Y},
Y = {x Î U: }
El conjunto P-frontera de Y, denotado por
Bnp(Y), esta definido como:
Bnp(Y) = Y – PY
A partir de las aproximaciones superior e inferior, son
definidas tres regiones (ver figura 1):
- La Región Positiva: Denotada por
POS(Y), esta región está conformada por
todos los elementos de U que con seguridad
pueden ser clasificados como elementos de Y, a partir de
los atributos P. Definida así, en realidad la
región Positiva es equivalente a la aproximación
inferior, esto es:
POS(Y) = PY
- La Región Frontera:
Denotada por Bnp(Y), esta región esta
conformada por todos elementos de U, que por lo menos
presentan un atributo de Y. Se define como:
Bnp(Y) = Y – PY
- La Región Negativa: Denotada por
NEG(Y), esta región esta conformada por todos los
elementos de U, que con seguridad no son elementos de
Y, considerando los atributos P. Se define
como:
NEG(Y) = U – Y
Figura 1: Relaciones entre las
aproximaciones y las regiones
2.3 Precisión de la
Aproximación
Con cada conjunto Y Î U, esta asociado un ratio
llamado precisión de la aproximación del
conjunto Y, en relación al conjunto de atributos
P, definidos en la cuádrupla S = <U, Q, V,
f>. La precisión de la información
a P(Y), se
define como:
donde card() representa la cardinalidad del
conjunto.
2.4 Calidad de la
Aproximación:
Suponiendo que tenemos una tabla de información S
= <U, Q, V, f>, con PÍ Q, y Y= {Y1, Y2,
…., Yn} siendo una
clasificación de U, donde además los subconjuntos
Yi, con i =1, 2, …, n, son clases disyuntivas
de Y. Con esa base, la aproximación inferior de Y en S
puede ser denotada como:
PY = { PY1,
PY2, ….,
PYn}
Entonces, la calidad de la aproximación de la
clasificación de Y, por el conjunto de atributos P, esta
definida por la siguiente relación:
La relación expresa cuantos objetos de P
están correctamente clasificados en relación a
todos los objetos de U.
2.5 Dependencia de los atributos y
Reducciones
Una de las características más importantes
de la TCA, es que esta puede descubrir dependencias entre los
atributos. En problemas de
clasificación que usan múltiplos atributos,
generalmente lo ideal es trabajar con el menor número de
atributos, pero, sin que ello signifique una pérdida de
calidad al momento de realizar la
clasificación.
Se dice que el conjunto de atributos RÍ Q depende del conjunto de
atributos PÍ
Q en S (denotado como P® R), si y solo si,
IPÍ IR. Es bueno resaltar
que el descubrimiento de dependencias entre los atributos es de
importancia primordial en la TCA, ya que de ello depende tener
que hacer una mayor o menor cantidad de cálculos, debido a
que se podrían eliminar atributos sin que ello signifique
una pérdida de información.
Así mismo, al subconjunto mínimo R
Í P
Í Q, tal
que g
P(Y) = g R(Y), se le denomina
Y-reducción de P, la cual puede ser representada
como REDY(P). Según esta definición, un
sistema puede
poseer más de una Y-reducción. A la
intersección de todas las Y-reducciones se le denomina
Y-núcleo de P, al cual se le representa como
NUCY(P). Entonces, de la definición anterior
tenemos que:
NUCY(P) = Ç
REDY(P)
El núcleo NUCY(P), viene a ser la
colección de los más importantes atributos de una
tabla de información.
2.6 Reglas de Decisión
Slowinski y Stefanowski (1989) establecen que dada una
tabla de información, S = <U, Q, V, f>, a partir de
ella se puede deducir un conjunto de reglas de decisión.
Para transformar una tabla de información en una tabla de
decisión. Para ello, se necesita definir un conjunto de
atributos (Q), tal que:
Q=CÈ D y CÇ D=Æ
donde C representa los atributos de condición, y
D los atributos de decisión.
Así, sea U| IC una familia de todos
los conjuntos C-elementales denominados clases de condiciones y
designados por Xi (i = 1, 2, …, m). Sea
también, la familia U| ID, la familia de todos los
conjuntos D-elementales designados por Yj (j = 1, 2,
…, n), y denominados clases de decisiones. Entonces, se
define (C, D), la regla de decisión, como siendo la
relación causal DESC(Xi) Þ
DESD(Yj).
Dada esta definición, las reglas tendrían
la forma de sentencias lógicas del tipo SI …
ENTONCES, que relacionan los descriptores de las clases de
decisión y de condición. El conjunto de reglas para
cada clase de
decisión Yj (j = 1, 2, .., n) es denotado por
{rij}, y es definido
como:
{rij} =
{DESC (Xi) Þ DESD (Yj) :
Xi Ç
Yj ¹ Æ
, i = 1, 2, …, k}
La regla rij, será
determinística, si y solo si, Xi
Í Yj;
en caso contrario será no-determinística. En otras
palabras, si DESC(Xi) solo implica
DESP(Yj), entonces la regla es determinística;
de no ser así, será
no-determinística.
Según Pawlak y Slowinski (1993), existen
diferentes procedimientos que permiten derivar reglas de
decisión, sin embargo, los algoritmos
existentes usan algunas de las siguientes estrategias:
- Generación de un conjunto mínimo de
reglas, cubriendo todos los objetos de una tabla de
decisión. - Generación de un conjunto exhaustivo de
reglas, buscando obtener todas las posibles reglas de una tabla
de decisión. - Generación de un conjunto "fuerte" de reglas,
que eventualmente podría ser discriminante, pero
cubriendo a muchos objetos de la tabla de decisión, es
decir, no se llega a cubrir necesariamente a todos los
objetos.
El presente ejemplo esta basado en el modelo
propuesto por Pawlak (1991), el cual usa la tabla de
información S = <U, Q, V, f>, mostrada en la tabla
2.
Paciente | Dolor de Cabeza C | Dolor Muscular M | Temperatura T | Gripe G |
1 | No | Si | Alta | Si |
2 | Si | No | Alta | Si |
3 | Si | Si | Muy alta | Si |
4 | No | Si | Normal | No |
5 | Si | No | Alta | No |
6 | No | Si | Muy alta | Si |
Tabla 2: Tabla de información
sobre un grupo de
pacientes
- U = {1, 2, 3, 4, 5,
6} …….…. Objetos
(Pacientes) - C = {Dolor de cabeza, dolor muscular, temperatura} …………
Atributos de Condición - D = {gripe} …………
Atributos de Decisión - Q = {Dolor de cabeza, dolor muscular, temperatura,
gripe} ……….. Atributos
Recordar que Q = C È D
- VDolor de cabeza = Vc = {Si,
No} ………… Dominio del
atributo - VDolor muscular = Vm = {Si,
No}
VTemperatura = Vt = {Normal,
Alta, Muy alta}
VGripe = Vg = {Si,
No}
- f(1,Vc) = No, f(2,Vm) = No,
f(3,Vt) = Muy alta, f(4,Vg) =
No,
f(5,Vc) = Si, f(4,Vt) = Normal,
etc. …… Función de Información (Paciente,
Atributo)
- DESQ (1) = [f(1,Vc),
f(1,Vm), f(1,Vt), f(1,Vd)] =
[No, Si, Alta, Si] ……..
Descriptores
DESQ (4) = [f(4,Vc),
f(4,Vm), f(4,Vt), f(4,Vd)] =
[No, Si, Normal, No]
- U|
IQ = {{No, Si, Alta, Si}, {Si, No, Alta,
Si}, {Si, Si, Muy alta, Si},
{No, Si, Normal, No}, {Si, No, Alta, No}, {No, Si, Muy
alta, Si}}
De forma práctica se dice que:
U|
IQ = {{1}, {2}, {3}, {4}, {5}, {6}}
Debido a que Atributos = Q, se dice que son
D-indiscernibles, por lo tanto, U| IQ esta conformado por
átomos de Q, caso contrario, serían sólo
conjuntos elementales
Si se define P = {Dolor muscular, Temperatura},
entonces:
U|
IP = {{Si, Alta}, {No, Alta}, {Si, Muy Alta},
{Si, Normal}} = {{1}, {2, 5}, {3, 6}, {4}}
En este caso como PÍ Q, entonces
U| IP
esta conformado solamente por conjuntos elementales.
- IQ = {(1,1), (2,2), (3,3), (4,4), (5,5),
(6,6)}
IP = {(1,1), (2,2), (2,5), (3,3), (3,6),
(4,4), (5,5), (5,2), (6,6), (6,3)}
Por lo tanto, P depende de Q (Q® P), ya que
IQÍ IP
- Considerando los atributos P = {Dolor muscular,
Temperatura}, con los cuales se piensa aproximar un conjunto
Y1 de pacientes, los cuales "presentan
positivamente Gripe", esto es, Y1 = {1, 2, 3, 6),
entonces dado que U| IP = {{1}, {2, 5}, {3, 6},
{4}}, tenemos:
PY1 = {1, 3, 6} Þ Card
(PY1) = 3
Y1 = {1, 2, 3, 5, 6} Þ Card (Y1) =
5
Bnp(Y1) = {2, 5}
a
P(Y1) = 3 / 5 =
0.6
De la misma forma, considerando los atributos P, con
los cuales se piensa aproximar un conjunto Y2 de
pacientes, los cuales "no presentan positivamente Gripe",
esto es, Y2 = {4, 5}, entonces dado que
U|
IP = {{1}, {2, 5}, {3, 6}, {4}},
tenemos:
PY2 = {4} Þ Card (PY2) =
1
Y2 = {2, 4, 5} Þ Card (Y2) = 3
Bnp(Y2) = {2, 5}
a
P(Y2) = 1 / 3 =
0.33
Para encontrar la calidad de la aproximación,
tenemos que: Y = {Y1,
Y2}. Observe que
Y1 y Y2 son disjuntos.
g
P(Y) = (3 + 1) / 6 =
0.667
- Para descubrir las dependencias y obtener las
reducciones, primero se debe encontrar la calidad de la
aproximación para todos los atributos del ejemplo. La
tabla 3 muestra los
resultados.
Atributos | c | m | t | c, m | c, t | m, t | Q |
Calidad de la | 0.000 | 0.000 | 0.500 | 0.167 | 0.667 | 0.667 | 0.667 |
Tabla 3: Calidad de la
aproximación para todos los atributos
De los resultados obtenidos en la tabla 3, queda
claro que:
I(c,t) = IQ, I(m,t)
= IQ,
I(c,m) ¹ IQ, It
¹
IQ, Im ¹ IQ, Ic ¹
IQ
Significa que (c,t) y (m,t) son
reducciones de Q, en cuanto que el resto no lo es.
Tener en cuenta que se considera que (c,t) y
(m,t) son reducciones de Q,
porque:
g
Q(Y) = g c,t(Y) =
g m,t(Y)
= 0.667
El núcleo se determina por medio de la
intersección de las reducciones, esto es:
NUCY(Q) = (c,t) Ç (m,t) =
t
En este caso el núcleo esta formado por un
solo atributo, el atributo t. Por ello, diremos que
t es el núcleo de Q, y representa al
atributo más significativo de Q, el cual no
puede dejar de ser considerado, ya que su
eliminación significa obtener aproximaciones de baja
calidad.
En relación a los atributos c y
m, estos pueden ser mutuamente intercambiables.
Así, queda a criterio personal, trabajar o con los atributos
(c,t), o con (m,t), considerando que ambos grupos
de atributos producen la misma calidad de
información en relación a Q.
- Finalmente llegamos a la parte de la
obtención de las reglas de decisión, del tipo
SI-ENTONCES. Recordar que las reglas son definidas
como:
{rij} =
{DESC (Xi) Þ DESD (Yj) :
Xi Ç Yj ¹ Æ , i = 1, 2, …, k}
Por lo tanto, si trabajáramos con todos los
atributos (c,m,t) tendríamos reglas de la siguiente
forma:
1. Si f(x,c) = No y f(x,m) = Si y f(x,t) = Alta,
entonces f(x,g) = Si
2. Si f(x,c) = Si y f(x,m) = No y f(x,t) = Alta,
entonces f(x,g) = Si *
3. Si f(x,c) = Si y f(x,m) = Si y f(x,t) = Muy alta,
entonces f(x,g) = Si
4. Si f(x,c) = No y f(x,m) = Si y f(x,t) = Normal,
entonces f(x,g) = No
5. Si f(x,c) = Si y f(x,m) = No y f(x,t) =
Alta, entonces f(x,g) = No *
6. Si f(x,c) = No y f(x,m) = Si y f(x,t) = Muy alta,
entonces f(x,g) = Si
Si trabajáramos con los atributos (c,t)
tendríamos reglas de la siguiente forma:
1. Si f(x,c) = No f(x,t) = Alta, entonces f(x,g) =
Si
2. Si f(x,c) = Si f(x,t) = Alta, entonces f(x,g) =
Si *
3. Si f(x,c) = Si f(x,t) = Muy alta, entonces f(x,g)
= Si
4. Si f(x,c) = No f(x,t) = Normal, entonces f(x,g)
= No
5. Si f(x,c) = Si f(x,t) = Alta, entonces f(x,g) =
No *
6. Si f(x,c) = No f(x,t) = Muy alta, entonces f(x,g)
= Si
Si trabajáramos con los atributos (m,t)
tendríamos reglas de la siguiente forma:
1. Si f(x,m) = Si y f(x,t) = Alta, entonces f(x,g)
= Si
2. Si f(x,m) = No y f(x,t) = Alta, entonces f(x,g) =
Si *
3. Si f(x,m) = Si y f(x,t) = Muy alta, entonces
f(x,g) = Si **
4. Si f(x,m) = Si y f(x,t) = Normal, entonces
f(x,g) = No
5. Si f(x,m) = No y f(x,t) = Alta, entonces f(x,g) =
No *
6. Si f(x,m) = Si y f(x,t) = Muy alta, entonces
f(x,g) = Si **
Es notorio el hecho que se presenta en el primer grupo
de reglas, donde los pacientes 2 y 5, son C-indiscernibles
(para los atributos de condición, en este caso c, m y
t); pero no D-indiscernibles (para los atributos de
decisión). Análogamente ocurre para el segundo y
tercer grupo de reglas, con los mismos pacientes. Cuando
acontece eso, se dice que son casos de "frontera", y por tanto
no pueden ser clasificados de manera apropiada con la
información disponible. De allí que lo más
apropiado sería considerar un grupo mayor de atributos
para explicar la enfermedad con una mayor certeza. Sin embargo,
mismo así, para los tres conjuntos de reglas,
todavía se podría obtener información,
sólo que tendríamos cuatro reglas
"determinísticas" (para los casos 1, 2, 4, y 5), y una
regla "no determinística" (para los casos 3 y 6). La
nueva regla no determinística hace que para las casos 3
y 6 se fusionarían de la siguiente forma:
Si …….., entonces f(x,g) =
(Si o No)
Un otro hecho notorio, lo observamos en el tercer
conjunto de reglas, para los pacientes 3 y 6. En este conjunto
de reglas para los atributos (m,t), vemos que en realidad
contamos con cinco reglas, ya que las reglas 3 y 6 son iguales,
por tanto sólo tendríamos 5 reglas, siendo todas
determinísticas.
El objetivo del
presente trabajo es dar a conocer los lineamientos básicos
de esta relativamente nueva teoría. Por esa razón
consideramos de suma importancia la difusión de esta
teoría, considerando que la TCA ha sido y continúa
siendo utilizada en diversas aplicaciones prácticas (ver
Pawlak, 1991), sobre todo en temas como: análisis de decisión, sistemas
expertos, sistemas de apoyo a la decisión,
reconocimiento de patrones, etc. Las principales ventajas que
tornan atractiva la TCD en relación a otras teorías, son:
- Dada una tabla de información, la TCA permite
la reducción de los atributos, sin pérdida de la
calidad de la información. - Más allá de la determinación de
los atributos, no es necesaria información adicional, lo
que conlleva a no tener influencias humanas en los resultados,
ya que no se realizan estimaciones por parte de
especialistas. - Esta teoría es particularmente útil en
el tratamiento de datos ambiguos, principalmente cuando los
métodos
tradicionales –como los estadísticos- no ofrecen
resultados satisfactorios. - Se puede explicar el porqué de políticas adoptadas, mediante las reglas
de decisión. - Implementaciones prácticas son fáciles,
debido a la simplicidad de su teoría.
Para finalizar, diremos que las últimas
tendencias de investigación de esta teoría,
están relacionadas con estudio de sistemas con
información incompleta, determinación de reglas
con más de un atributo (Pawlak, 1991), y el uso de
relaciones de dominancia y comparaciones par a par (Greco et
al, 2001).
Greco, S.; matarazzo, b.; slowinski, r.; 2001. Rough
sets theory for multicriteria decision analysis, European Journal
of Operational Research, no 129, p. 1-47.
MARAKAS, G.; 1998. Decision Support Systems in the 21st
Century, Prentice-Hall, New York, E.U.A.
PAWLAK, Z.; 1982. Rough Sets, International Journal of
Information & Computer Sciences, vol. 11, p.
341-356.
PAWLAK, Z.; 1991. Rough Sets – Theoretical Aspects
of Reasoning about Data, Kluwer Academic Publishers, Boston,
London.
PAWLAK, Z.; SLOWINSKI, R.; 1993. Decision Analysis using
Rough Sets. ICS Research Report no 21, Institute of
Computer Science, Warsaw University of Technology, Warsaw,
Poland.
SLOWINSKI, R.; STEFANOWSKI, J.; 1989. Rough
Classification in Incomplete Information Systems, Mathematical
and Computer Modelling, vol. 12, no 10/11, p.
1347-1357.
ZOPOUNIDIS, C.; DIMITRAS, A.; 1998. Multicriteria
Decision Aid for the prediction of business failure, Kluwer
Academic Publishers, Netherlands.
M.Sc. William David Morán
Herrera
Laboratório de
Matemáticas/LCMAT/Universidade Estadual do Norte
Fluminense
Av. Alberto Lamego, 2000/Campos/RJ/Brasil –
CEP:28.030-480 – Tel/Fax:
+552227261632 –
Lic. Javier Martín Morán
Herrera
Marketer de Agro Industrial Paramonga S.A.A., Grupo Wong
– Av. Javier Prado Este 5245/Lima/Perú
Tel: 3170400 An. 2006, Fax: 3170402 –