La teoría de conjuntos aproximativos. Una herramienta Data Mining

1. Resumen
2. Fundamentos teóricos
3. Ejemplo de aplicación
4. Conclusiones

I RESUMEN

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

II FUNDAMENTOS TEÓRICOS

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.

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.

III EJEMPLO DE APLICACIóN

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.

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.

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.

IV CONCLUSIONES

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).

V BIBLIOGRAFíA

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 –