biblioteca en java para la aplicación de los conjuntos

UNIVERSIDAD CENTRAL “MARTA ABREU” DE LAS VILLAS FACULTAD DE MATEMÁTICA, FÍSICA Y COMPUTACIÓN

Biblioteca en Java para la aplicación de los conjuntos aproximados en el

aprendizaje automatizado

Trabajo de Diploma para optar por el Título de

Licenciado en Ciencia de la Computación

Autor

Alejandro Geraldo Gómez Boix

Tutoras

Dra. Leticia Arco García

Lic. Adis Perla Mariño Rivero

Santa Clara, 2013

Hacemos constar que el presente Trabajo de Diploma ha sido realizado en la facultad de Matemática,

Física y Computación de la Universidad Central “Marta Abreu” de Las Villas (UCLV) como parte de la

culminación de los estudios de Licenciatura en Ciencia de la Computación, autorizando a que el

mismo sea utilizado por la institución para los fines que estime conveniente, tanto de forma total

como parcial y que además no podrá ser presentado en eventos ni publicado sin la previa

autorización de la UCLV.

______________________________

Firma del Autor

Los abajo firmantes, certificamos que el presente trabajo ha sido realizado según acuerdo de la

dirección de nuestro centro y que el mismo cumple con los requisitos que debe tener un trabajo de

esta envergadura referido a la temática señalada.

______________________________ ______________________________

Firma del Tutor Firma del Tutor

________________________

Jefe del Seminario de Inteligencia Artificial

PENSAMIENTO

La diferencia entre construcción y creación es exactamente esto: una

cosa construida puede ser querida solo después de ser construida; pero

una cosa creada es querida antes de que exista.

Gilbert Keith Chesterton

DEDICATORIA

A la memoria de mis abuelos: Merido y Bertalina.

A quienes le debo mucho.

A mi padre y mi madre, que poco tienen y lo dan todo.

A mi hermana, por estar.

AGRADECIMIENTOS

Quisiera agradecer a todos los que de una forma u otra han hecho

posible la realización de este trabajo.

A mi padre y mi madre por la guía y el tesón.

A mi hermana...

A mis abuelos, que aunque ausentes les debo mucho por la persona en

la que me he convertido.

A mi tía Milagros, por apoyarme siempre.

A mis tutoras Leticia y Adis, por su orientación y su paciencia hacia

mi persona.

A la profesora María Matilde por toda la ayuda brindada.

A mis amigos, con los cuales he pasado estos largos 5 años, por pasar

momentos difíciles y gratos, por aguantarme.

A los viejos amigos, que siempre han estado junto a mí.

RESUMEN

Se dice Aprendizaje Automatizado a aquellos métodos de solución de problemas de aprendizaje por

las computadoras. Existen métodos de aprendizaje automatizado incorporados al Weka que utilizan la

Teoría de los Conjuntos Aproximados (Rough Set Theory; RST) para su funcionamiento; sin embargo,

su incorporación al Weka incluye la implementación por separado de las facilidades de RST necesarias

para el funcionamiento de cada uno de ellos, ya que no existe una biblioteca que encapsule todos los

elementos de RST que se aplican en métodos de aprendizaje automatizado. El objetivo general del

trabajo de diploma consiste en desarrollar una biblioteca en Java que incorpore los principales

elementos de la RST clásica y extendida, aplicables en el desarrollo de métodos de aprendizaje

automatizado y su validación. Los principales resultados obtenidos son: (1) la biblioteca que encapsula

las definiciones, conceptos y medidas de RST aplicables en el desarrollo de métodos de Aprendizaje

Automatizado, con la finalidad de incorporar esta biblioteca a la herramienta Weka, (2) la

implementación de un algoritmo para el cálculo de reductos que utiliza el modelo de optimización

basado en colonias de hormigas y (3) la incorporación al Weka de un paquete para la validación del

agrupamiento, el cual incorpora medidas de la Teoría de conjuntos aproximados, y por tanto, hace

uso de la biblioteca creada.

ABSTRACT

It is called Machine Learning to those problem solving methods of learning by computers. There are

machine learning methods incorporated to Weka that use the Rough Set Theory (RST) for its

operation, however to join it to Weka includes the separated implementation of RST facilities that are

necessary for the operation of each one of them, since there is no library that encapsulates all

elements of RST applied in machine learning methods. The general objective of this research paper is

to develop a Java library that incorporates the main elements of the classical and extended RST,

applicable in the development of machine learning methods and its validation. The main results are:

(1) the library that encapsulates the definitions, concepts and measures of RST, applicable in the

development of Machine Learning methods, in order to incorporate this library to a Weka tool, (2) the

implementation of a algorithm for calculating reducts that uses an optimization model based on ant

colonies and (3) the incorporation to Weka of a package for clustering validation, which incorporates

measures of rough sets theory, and thus makes use of the created library.

TABLA DE CONTENIDOS

INTRODUCCIÓN ................................................................................................................................................. 1

1 TEORÍA DE CONJUNTOS, RELACIONES BINARIAS Y TEORÍA DE CONJUNTOS APROXIMADOS ..................... 7

1.1 TEORÍA BÁSICA DE CONJUNTOS .................................................................................................................. 7

1.1.1 Notaciones de conjuntos ............................................................................................................... 7

1.1.2 Operaciones sobre conjuntos ......................................................................................................... 8

1.2 RELACIONES BINARIAS ............................................................................................................................. 8

1.3 TEORÍA DE CONJUNTOS APROXIMADOS ...................................................................................................... 11

1.3.1 Teoría de los conjuntos aproximados clásica ................................................................................ 13

1.3.2 Conjuntos aproximados en sistemas de información incompletos ................................................. 16

1.3.2.1 Conjuntos aproximados basados en una relación transitiva ................................................................ 17

1.3.2.2 Conjuntos aproximados monótonos ................................................................................................... 18

1.3.2.3 Conjuntos aproximados para sistemas de información incompletos basados en una relación no simétrica

......................................................................................................................................................... 19

1.3.3 Conjuntos aproximados basados en relaciones de similaridad ...................................................... 20

1.3.4 Medidas para realizar inferencias ................................................................................................ 25

1.3.5 Reductos ..................................................................................................................................... 29

1.3.5.1 Tipos de reductos............................................................................................................................... 30

1.3.5.2 Cálculo de reductos ........................................................................................................................... 32

1.4 CONSIDERACIONES PARCIALES DEL CAPÍTULO ............................................................................................... 33

2 BIBLIOTECA EN JAVA QUE PERMITE TRABAJAR CON LOS CONJUNTOS APROXIMADOS ........................... 34

2.1 GENERALIDADES DEL LENGUAJE JAVA ........................................................................................................ 34

2.2 DESARROLLO DE BIBLIOTECAS EN JAVA ....................................................................................................... 35

2.3 CONCEPCIÓN GENERAL DE LA BIBLIOTECA RST ............................................................................................. 36

2.3.1 Diseño de la biblioteca RST .......................................................................................................... 38

2.3.2 Diagrama de clases ..................................................................................................................... 39

2.3.3 Cálculo de reductos ..................................................................................................................... 46

2.3.3.1 Optimización basada en colonias de hormigas.................................................................................... 46

2.3.3.2 Cálculo de reductos usando ACO ........................................................................................................ 48

2.3.3.3 Diseño e implementación ................................................................................................................... 53

2.4 CONCLUSIONES PARCIALES DEL CAPÍTULO ................................................................................................... 54

3 UTILIZACIÓN DE LA BIBLIOTECA RST DESDE WEKA .................................................................................. 56

3.1 MEDIDAS PARA LA VALIDACIÓN DEL AGRUPAMIENTO UTILIZANDO RST ............................................................... 56

3.2 GENERALIDADES DE WEKA ..................................................................................................................... 59

3.2.1 Entrada de datos ......................................................................................................................... 60

3.2.2 Interioridades de Weka ............................................................................................................... 61

3.2.3 Validación del agrupamiento en Weka......................................................................................... 65

3.3 PAQUETE PARA VALIDAR AGRUPAMIENTOS EN WEKA UTILIZANDO RST .............................................................. 67

3.4 CONCLUSIONES PARCIALES DEL CAPÍTULO ................................................................................................... 70

CONCLUSIONES Y RECOMENDACIONES ........................................................................................................... 71

REFERENCIAS BIBLIOGRÁFICAS ........................................................................................................................ 72

ANEXOS ........................................................................................................................................................... 75

ANEXO 1. TRANSFORMACIONES DE DISTANCIAS A SIMILITUDES .................................................................................... 75

ANEXO 2. DISTANCIAS, SIMILITUDES Y DISIMILITUDES MÁS USADAS PARA COMPARAR OBJETOS ............................................ 76

ANEXO 3. ALGUNAS VARIANTES PARA EL CÁLCULO DEL UMBRAL DE SIMILITUD ENTRE OBJETOS ............................................ 78

1

INTRODUCCIÓN

Desde el surgimiento de la computación se han tratado de ingeniar métodos con el objetivo de lograr

que la computadora aprenda por sí misma. El interés es lograr programarla para que mejore

automáticamente con su propia experiencia. En particular, el campo de la Inteligencia Artificial (IA)

que estudia los métodos de solución de problemas de aprendizaje por las computadoras se le

denomina Aprendizaje Automatizado (Machine Learning). Aún no se ha podido lograr que las

computadoras aprendan casi tan bien como el hombre aprende, sin embargo se han creado

algoritmos que son eficaces para ciertos tipos de tareas de este ámbito, emergiendo así una

comprensión teórica de aprendizaje.

El Aprendizaje Automatizado se ha convertido en un campo multidisciplinario, mostrando resultados

de inteligencia artificial, probabilidades y estadística, filosofía, teoría de cómputo, teoría de control,

teoría de información, psicología, neurobiología, ciencia cognoscitiva, complejidad computacional y

otros campos. La creación de diversos algoritmos de aprendizaje automatizado ha traído consigo la

difícil tarea de seleccionar alguno de ellos cuando se requiera su utilización. La herramienta WEKA

(Waikato Environment for Knowledge Analysis) es un ambiente de trabajo para la prueba y validación

de algoritmos de la IA, que ha tenido gran difusión entre los investigadores y docentes de esta área.

En el Laboratorio de Inteligencia Artificial del Centro de Estudios de Informática de la Universidad

Central “Marta Abreu” de Las Villas (CEI-UCLV) se desarrollan varias investigaciones que aplican

elementos de la Teoría de los Conjuntos Aproximados (Rough Set Theory; RST) en el desarrollo de

métodos de aprendizaje automatizado (Mitchel, 1997). Tal es el caso de la aplicación de RST en el

preprocesamiento de los conjuntos de entrenamiento para los algoritmos de aprendizaje

automatizado (Caballero, 2008), el desarrollo de medidas internas de validación del agrupamiento

utilizando RST (Arco, 2009), el desarrollo de algoritmos que combinan RST y optimización basada en

colonias de hormigas para la selección de rasgos (Gómez, 2010), la creación de métodos de

aprendizaje para dominios con datos mezclados basados en la teoría de los conjuntos aproximados

extendida (Filiberto, 2011) y la aplicación de un método de aproximación de funciones basado en el

enfoque de los prototipos más cercanos utilizando relaciones de similaridad (Bello, 2012), por solo

Introducción

2

citar algunos ejemplos.

Es política del laboratorio de Inteligencia Artificial del CEI-UCLV incorporar al Weka1 los nuevos

métodos de aprendizaje automatizado creados. De esta forma es posible comparar los nuevos

métodos con los clásicos ya existentes en una misma plataforma, además, se enriquecen los módulos

del Weka como es el caso de la extensión al módulo de validación del agrupamiento utilizando RST

(Castellanos, 2008).

Una de las teorías que ha servido de base para el desarrollo de nuevos métodos de aprendizaje

automatizado es RST; sin embargo, los investigadores han implementado los elementos de RST

embebidos en el propio código del algoritmo que proponen. Por consiguiente, la implementación de

la nueva forma de selección de rasgos trae incluida la parte de RST que necesita para su

procesamiento, las medidas de validación del agrupamiento incorporan los elementos de RST en su

implementación, el método de aproximación de funciones igualmente incluye los elementos de RST

necesarios para esa propuesta y los métodos de edición también incorporan las facilidades de RST

que permiten preprocesar los conjuntos de entrenamiento. De esta forma se complejiza la

implementación de los nuevos métodos, se requiere mayor esfuerzo de los programadores y se

dificulta la reutilización de código. Todo ello constituye una problemática a la cual aún no se le ha

dado respuestas definitivas, lo cual justifica el planteamiento del problema siguiente.

Planteamiento del problema:

Existen métodos de aprendizaje automatizado incorporados al Weka que utilizan RST para su

funcionamiento; sin embargo, su incorporación al Weka incluye la implementación por separado de

las facilidades de RST necesarias para el funcionamiento de cada uno de ellos, ya que no existe una

biblioteca que encapsule todos los elementos de RST que se aplican en métodos de aprendizaje

automatizado.

El objetivo general del trabajo de diploma consiste en desarrollar una biblioteca en Java que

incorpore los principales elementos de la teoría de los conjuntos aproximados clásica y extendida, en

1 WEKA es una herramienta de código abierto escrita en Java. Está disponible en http://www.cs.waikato.ac.nz/˜ml/weka

bajo licencia pública GNU

Introducción

3

particular aquellas definiciones, conceptos y medidas aplicables en el desarrollo de métodos de

aprendizaje automatizado y su validación.

Este se desglosa en los siguientes objetivos específicos:

1. Seleccionar las definiciones, conceptos y medidas de RST aplicables en los métodos de

aprendizaje automatizado que permiten la edición de conjuntos de entrenamiento, la

selección de rasgos, los métodos de clasificación, el agrupamiento y la aproximación de

funciones, así como medidas de validación.

2. Implementar la biblioteca en Java que incorpore los elementos de RST identificados que

permiten el desarrollo de algoritmos de aprendizaje automatizado.

3. Incorporar al Weka algún algoritmo de aprendizaje automatizado que haga uso de la

biblioteca de RST implementada en Java.

Las preguntas planteadas son:

¿Cuáles conceptos, definiciones, medidas y extensiones de RST se utilizan en la creación de

algoritmos de aprendizaje automatizado?

¿Cómo diseñar la biblioteca de RST de forma tal que sea fácilmente utilizable en la

implementación de métodos de aprendizaje automatizado incorporados al Weka?

¿Qué consideraciones se requieren al incorporar a Weka un método de aprendizaje

automatizado o medidas de validación que requieren la utilización de la biblioteca de RST

implementada en Java?

Justificación del trabajo de diploma:

En el año 1992, Ian Witten, profesor del Departamento de Ciencia de la Computación de la

Universidad de Waikato, Nueva Zelanda, creó una aplicación que más tarde, en 1993, recibiría el

nombre de Weka, creándose con ello una interfaz e infraestructura para la misma. Su nombre Weka

(Gallirallus australis) se debe a un ave endémica de este país, de aspecto pardo y tamaño similar a

una gallina, se encuentra en peligro de extinción y es famosa por su curiosidad y agresividad. En 1994

Introducción

4

fue terminada la primera versión de Weka, aunque no publicada, montada en una interfaz de usuario

con varios algoritmos de aprendizaje escritos en lenguaje C. Muchas versiones de Weka fueron

desarrollándose hasta que en octubre de 1996 se publica una primera versión. En julio de 1997 se

publica la versión 2.2 con la inclusión de nuevos algoritmos de aprendizaje y con la facilidad de

configurar la corrida de una gran escala de experimentos. Cerca de esta fecha se toma la decisión de

rescribir Weka en lenguaje Java. A mediados de 1999 es liberada la versión 3 de Weka con todo su

código implementado en Java. Después de la versión 3 se han publicado varias versiones, cada una de

ellas ofreciendo esencialmente como mejora la adición de nuevos algoritmos.

La aplicación comenzada por Ian Witten en 1992 aún continúa ampliándose. El desarrollo de mejores

extensiones al sistema ha dejado de concentrarse en el lugar donde fue creado, para dispersarse por

todo el mundo, donde cantidad de científicos incluyen y validan sus propios modelos. Este ambiente

de aprendizaje automatizado está contenido por una extensa colección de algoritmos de la

Inteligencia Artificial, útiles para ser aplicados sobre datos mediante las interfaces gráficas de usuario

(GUI: Graphical User Interface) que ofrece o para usarlos dentro de cualquier aplicación. Contiene las

herramientas necesarias para realizar transformaciones sobre los datos, tareas de clasificación,

regresión, agrupamiento, asociación y visualización.

En el CEI-UCLV se han desarrollado y se desarrollan nuevos métodos de aprendizaje automático. Se

han creado varios algoritmos para la selección de rasgo (Gómez, 2010) y edición de conjuntos de

entrenamiento (Caballero, 2008). Se han creado varios clasificadores, entre ellos modelos híbridos

que combinan el razonamiento basado en casos con los sistemas basados en reglas y con los sistemas

neuroborrosos (Rodríguez, 2009), clasificadores basados en reglas, aquellos que resuelven problemas

cuando las clases están desbalanceadas y otros aplicables a problemas de multietiquetas (Filiberto,

2011). También, se han trabajado las redes neuronales recurrentes (Guevara, 2007, Bonet, 2009) y

nuevos modelos de redes bayesianas para la clasificación (Arboláez, 2008, Chávez, 2009). Se han

desarrollado nuevos algoritmos de aproximación de funciones (Bello, 2012). Se ha trabajado con tipos

de datos conjunto y con datos borrosos y las consecuentes particularidades que tienen que tener los

algoritmos que utilicen estos tipos de datos (González, 2010). Se realizan estudios sobre las

peculiaridades de los datos de alta dimensión y las características de los algoritmos que permiten

manejarlos (Carbonell, 2010). Además, nuevos métodos de agrupamiento y medidas de validación del

Introducción

5

agrupamiento han sido creados (Castellanos, 2008, Arco, 2009).

Desde el año 2006 el Laboratorio de Inteligencia Artificial se ha propuesto incorporar en el Weka los

métodos de aprendizaje automatizado creados. Inicialmente se formuló una metodología para

extender el ambiente de aprendizaje automatizado Weka (Matías and L.I.Araujo, 2006, Morell et al.,

2006) y así guiar la incorporación de los métodos a esta herramienta. A pesar de la existencia de la

metodología, cada uno de los autores fue incorporando los métodos de manera espontánea, sin

permitir la reutilización de código, y mezclando en la implementación elementos de la nueva

propuesta con elementos de las técnicas computacionales y matemáticas necesarias para su

desarrollo.

En la actualidad, a partir de la creación de proyectos entre el CEI-UCLV y la unidad de desarrollo de

software de la FAR (UCI-FAR) se formaliza la propuesta de crear el Weka Cubano que tendrá

encapsulado en forma de paquetes todos los algoritmos de aprendizaje automático desarrollados

como resultados de la labor investigativa en el CEI-UCLV y otros grupos de investigación cubanos.

Esto permitirá no solo la validación de nuevas propuestas, sino que ofrecerá una herramienta

reutilizable para dar solución con tecnología propia a los disímiles problemas de aprendizaje

automático que se presentan en las organizaciones. El diseño, implementación y documentación de la

herramienta facilitarán la inclusión permanente de nuevos paquetes que recojan nuevos algoritmos.

De esta forma se contribuirá a la visibilidad de nuestros resultados científicos, ya que los paquetes

creados se colocan en un repositorio de paquetes en Internet y los desarrolladores de Weka los

revisan antes de ponerlos a disposición del público. Además, se incluirán las publicaciones científicas

que sustentan los resultados incorporados en los paquetes.

Lo anteriormente expuesto justifica este trabajo de diploma que pretende contribuir a la propuesta

de Weka Cubano, ya que se creará una biblioteca de RST para dar soporte a todos los métodos de

aprendizaje automatizado que se incorporarán al Weka Cubano, brindando la posibilidad de

implementación más sencilla y reutilizando código.

El presente trabajo se encuentra estructurado en introducción, tres capítulos, conclusiones,

recomendaciones, referencias bibliográficas y tres anexos. El primer capítulo se dedica al estudio de

los principales elementos de la Teoría de conjuntos aproximados clásica y sus extensiones. Este

Introducción

6

capítulo concluye con el concepto de reducto y la teoría de su cálculo. En el segundo capítulo

abordamos el diseño y concepción de la biblioteca, la cual implementa los conceptos, elementos y

medidas mencionados en el capítulo 1. El tercer capítulo hace alusión a las medidas de validación del

agrupamiento utilizando los conjuntos aproximados, y cómo se logra la creación de un paquete en

Weka que permita el cálculo de las medidas y la aplicación de la biblioteca creada.

7

1 TEORÍA DE CONJUNTOS, RELACIONES BINARIAS Y TEORÍA DE CONJUNTOS APROXIMADOS

En el presente capítulo se presenta una descripción de los conceptos esenciales involucrados en la

teoría básica de conjunto, así como las definiciones, conceptos y medidas de la Teoría de

Conjuntos Aproximados aplicables en los métodos de aprendizaje automatizado, analizando la

teoría clásica para después analizar sus extensiones. Finalmente abordamos el concepto de

reducto, el cual constituye la base de algunos métodos que se desarrollan usando conjuntos

aproximados.

1.1 TEORÍA BÁSICA DE CONJUNTOS

G. Cantor creó una nueva disciplina matemática entre 1874 y 1897: la teoría de conjuntos. Desde

entonces disímiles debates han acontecido en el seno de la teoría de conjuntos, sin dudas por

hallarse estrechamente conectados con importantes cuestiones lógicas. Algunos años más tarde la

teoría axiomática de Zermelo (1908) y refinamientos de ésta debidos a Fraenkel (1922), Skolem

(1923), von Newman (1925) y otros, sentaron las bases para la teoría de conjuntos actual.

Concepto de conjunto:

La definición inicial de Cantor (Devlin, 1993) es totalmente intuitiva: un conjunto es cualquier

colección C de objetos determinados y bien distintos x de nuestra percepción o nuestro

pensamiento (que se denominan elementos de C), reunidos en un todo.

Dado un elemento a y un conjunto X utilizamos la expresión: a X, para declarar que a es un

elemento o miembro de X. Para expresar lo contrario escribimos: a X.

A partir de dos conjuntos X y Y decimos que X es un subconjunto de Y si y solo si cada elemento de

X es un elemento de Y, esto se denota como: X Y.

1.1.1 Notaciones de conjuntos

Si un conjunto es finito podemos describirlo mediante la enumeración de sus miembros: si X

consiste en los objetos a1, a2,…, an, podemos denotar a X mediante {a1, a2,…, an}. Esta definición es

conocida como definición por extensión (Devlin, 1993). Cuando el número de objetos es infinito o

Capítulo 1: Teoría de conjuntos, relaciones binarias y teoría de conjuntos aproximados

8

demasiado numeroso se utiliza el método de definición por intensión (Devlin, 1993), que consiste

en la descripción de un conjunto mediante una o varias propiedades que caracterizan a los

elementos de ese conjunto. En este trabajo solo abarcaremos conjuntos finitos, descritos a partir

del listado de cada uno de sus elementos.

1.1.2 Operaciones sobre conjuntos

Existe un número de operaciones simples (Devlin, 1993) que pueden ser aplicadas a conjuntos,

formando nuevos conjuntos a partir de conjuntos dados. A continuación se consideran las más

comunes:

La unión de dos conjuntos X y Y da como resultado un conjunto consistente en los miembros de X

junto con los miembros de Y, esta operación se denota por X Y.

La intersección de dos conjuntos X y Y da como resultado un conjunto formado por aquellos

objetos que son miembros de ambos conjuntos y se denota por X Y.

La diferencia de dos conjuntos X y Y es el conjunto formado por aquellos elementos de X que no

son miembros de Y, esta operación se denota por X −Y.

En teoría de conjuntos es conveniente definir una colección sin objetos como un conjunto, el

conjunto vacío o nulo. Este conjunto es usualmente denotado mediante el símbolo derivado de

una letra escandinava.

Se dice que dos conjuntos son disjuntos si no tienen ningún miembro en común o lo que es lo

mismo: X Y = .

1.2 RELACIONES BINARIAS

Un par ordenado es un conjunto con dos elementos en un orden específico. Usamos la notación

(a, b) para denotar el par ordenado en la cual el primer elemento o componente es a y el segundo

elemento objeto es b.

De esta forma, dos pares ordenados (a, b) y (c, d) son iguales si sus correspondientes

componentes son iguales. Es decir, (a, b) = (c, d) si y solamente si a = c y b = d.


9

El producto cartesiano de dos conjuntos A y B es el conjunto de todos los pares ordenados (x, y)

donde x A y y B. Denotándolo, A x B = {(x, y) : x A y B }, por lo tanto (x, y) A x B si y

sólo si x A y B.

El producto cartesiano A x B no es igual al producto cartesiano B x A (no es conmutativo). Si los

conjuntos A y B tienen elementos comunes, entonces los elementos del producto cartesiano de la

forma (a, a), se les llama elementos diagonales. Si el producto cartesiano fuese de un mismo

conjunto A x A puede escribirse de forma simbólica como A2.

Relaciones entre conjuntos

Llamamos relaciones entre los conjuntos A y B y que representaremos por la letra R, a cualquier

subconjunto del producto cartesiano A x B. (No es necesario que todos los elementos de A estén

considerados)

R : A B

Formalmente: una relación binaria de A en B es R* = (A, B, R) con R A x B

Notación: Indistintamente escribimos (x, y)R o xRy

Se dice que b es homólogo o imagen de a a todo elemento del conjunto B tal que el par (a, b)

pertenece al subconjunto relación R es decir: (a, b) R, siendo R el subconjunto relación.

La primera componente del par (a, b) que pertenece a G se llama preimagen, mientras que la

segunda componente recibe el nombre de elemento imagen. Cuando b es el elemento imagen de

a por la relación R escribiremos b = R(a).

Conjunto origen, de partida o inicial: llamaremos así al conjunto A.

Conjunto de llegada o final: Es el conjunto B.

Se llama conjunto dominio, denotándolo Dom(R), al conjunto formados por todos los elementos

de A que son preimagen por la relación R (o que tienen una imagen).

Se llama conjunto recorrido, y se representa por Rec(R), al conjunto formado por todos los

elementos de B que son elementos imágenes por la relaciones R.


10

Se llama relación inversa a la relación que resulta de cambiar el orden de los conjuntos A x B por

B x A. La relación inversa la designaremos por R−1.

Se llama relación binaria definida en un conjunto A, a la relación de A en A:

Formalmente: una relación binaria de A en B es R* = (A, B, R) con R A x B

Notación: Indistintamente escribimos (x, y)R o xRy

Dominio e imagen de una relación:

Dom (R) = {x A | y B, (x, y)R}

Im (R) = {y B | x A, (x, y)R}

Se llama relación binaria definida en un conjunto X, a la relación de X en X; R X2.

Diremos que una relación binaria sobre un conjunto X es una relación de equivalencia si satisface

las siguientes propiedades:

1. Reflexiva: para todo x X se cumple xRx.

2. Simétrica: si xRy, entonces yRx.

3. Transitiva: si xRy y yRz, entonces xRz.

Llamaremos clase de equivalencia de x X a R(x) = {y X : xRy}.

Si R es una relación de equivalencia sobre el conjunto X. Entonces, se cumple que:

i. R(x) = R(y) si, y sólo si xRy.

ii. Si R(x) ≠ R(y), entonces R(x) R(y)=.

Dada una relación de equivalencia sobre un conjunto X, llamaremos conjunto cociente al formado

por todas las clases de equivalencia, lo notaremos por X/R, indicando así que es el conjunto X

partido por la relación de equivalencia R.

X/R = {R(x) : xX}


11

1.3 TEORÍA DE CONJUNTOS APROXIMADOS

La filosofía de los conjuntos aproximados está basada en la suposición de que con todo objeto de

un universo U está asociada una cierta cantidad de información (datos y conocimiento), expresado

por medio de algunos atributos usados para describir el objeto. Todo el conocimiento sobre el

dominio de aplicación está contenido en el conjunto de objetos, llamado Sistema de Decisión; este

sistema puede ser innecesariamente grande, en parte porque es redundante en al menos dos

formas; primero, el mismo objeto u objetos idénticos (según alguna relación) pueden aparecer

varias veces; segundo, algunos de los atributos que describen los objetos del universo son

superfluos.

Informalmente se pueden definir los conjuntos aproximados de la forma siguiente:

Los objetos que tienen la misma descripción son inseparables (similares) con respecto al conjunto

de atributos considerados. Esta relación de inseparabilidad constituye la base matemática de la

teoría, y la misma induce una partición del universo U en bloques de objetos inseparables.

Cualquier subconjunto X del universo U se puede expresar en términos de estos bloques de forma

exacta o aproximada. En el último caso el conjunto X se puede caracterizar por dos conjuntos

ordinarios denominados aproximación inferior y aproximación superior. La aproximación inferior

de X está formada por todos los bloques que son subconjuntos de X, y la aproximación superior

consiste de todos los bloques que tienen una intersección no vacía con X. A la aproximación

inferior de X pertenecen los objetos que con certeza pertenecen a X, a la aproximación superior

pertenecen los objetos que pudieran pertenecer a X, y en el conjunto diferencia de ambos

conjuntos están los objetos que no se puede determinar con certeza su pertenencia a X. La

cardinalidad (cantidad de objetos) de este conjunto diferencia se puede usar como una medida de

la vaguedad de la información sobre X.

En la Teoría de los conjuntos aproximados la estructura de información básica es el Sistema de

información.

Definición 1.1: (Sistema de Información)


12

Sea un conjunto de atributos A=A1, A2,...,An y un conjunto U no vacío llamado universo de

ejemplos (objetos, entidades, situaciones o estados, etc.) descritos usando los atributos Ai. Al par

(U,A) se le denomina Sistema de información.

A cada atributo Ai se le asocia un dominio Vi. Se tiene una función f: U x A V tal que f(x,Ai)Vq

para cada Ai A, x U, llamada función de información.

Se dice que un atributo Ai A separa o distingue un objeto “x” de otro “y” si y solo si:

(R1) Separa(Ai,x,y) f(x,Ai) f(y,Ai) (1.1)

En caso contrario se dice que x e y son inseparables respecto al atributo Ai. Para todo sistema de

información se puede definir una matriz de separación MA, la cual es una matriz |U|x|U|, cada

entrada MA(x,y) A contiene el conjunto de atributos que distinguen y separan los elementos x e

y de U:

MA(x,y)={ Ai A : Separa(Ai,x,y) } (1.2)

Si entre los valores de un atributo Ai se puede establecer una organización jerárquica, por

ejemplo, mediante una relación is-a, lo cual se puede modelar mediante una relación de orden

parcial sobre Vi (ab, se lee como a es una instancia de b), entonces la separabilidad se define

como:

(R2) Separa(Ai,x,y) f(x,Ai) not f(y,Ai) y f(y,Ai) not f(x,Ai) (1.3)

Definición 1.2: (Sistema de decisión)

Si a cada elemento de U se le agrega un nuevo atributo d llamado decisión indicando la decisión

tomada en ese estado o situación entonces se obtiene un Sistema de decisión (U, A{d}, donde

dA).

El valor de la decisión puede representar un número de la clase en la cual clasificar el objeto,

mientras que en un sistema de control la decisión significa una acción que se debe ejecutar en el

estado descrito por el objeto, entre otras alternativas de interpretación.

El atributo de decisión d induce una partición del universo de objetos U. Sea Vd el conjunto de

enteros {1,...,m}, entonces {X1,...,Xm} es una colección de clases de equivalencias, llamadas clases


13

de decisión, donde dos objetos pertenecen a la misma clase si ellos tienen el mismo valor para el

atributo decisión.

Xi= { x U : d(x)=i } (1.4)

Definición 1.3: (Relación de inseparabilidad):

Si (x,y) IB se dice que los objetos x e y son B- inseparables.

1.3.1 TEORÍA DE LOS CONJUNTOS APROXIMADOS CLÁSICA

Una relación de inseparabilidad (indiscernibility relation) que sea definida a partir de formar

subconjuntos de elementos de U que tienen igual valor para un subconjunto de atributos B de A

(BA) es una relación de equivalencia. Es decir, es una relación binaria R UxU que es reflexiva,

simétrica y transitiva.

La clase de equivalencia de un elemento x de U es el conjunto de todos los elementos y de U tal

que xRy; es decir, los elementos de U que son similares a x considerando los atributos contenidos

en B. Una relación de equivalencia induce una partición del universo U. Por B(x) se denota al

conjunto de todos los yU tal que yRx; es decir, el elemento de la partición al que pertenece el

objeto x.

Sea el sistema de información (U,A), y los conjuntos BA y XU, se puede aproximar X usando

solamente la información contenida en B construyendo dos conjuntos llamados aproximación

inferior (B*) y aproximación superior (B*) respectivamente del conjunto X para la relación B. Un

conjunto aproximado es cualquier subconjunto XU definido a través de sus aproximaciones

inferior y superior.

Definición 1.4: (Aproximaciones de un conjunto)

La aproximación inferior de un conjunto (con respecto a un conjunto dado de atributos) se define

como la colección de casos cuyas clases de equivalencia están contenidas completamente en el

conjunto; mientras que la aproximación superior se define como la colección de casos cuyas clases

de equivalencia están al menos parcialmente contenidas en el conjunto.


14

A partir de diferentes representaciones de una relación de equivalencia, se pueden obtener tres

definiciones constructivas de las aproximaciones (Bello et al., 2012):

Definición basada en Elemento:

B*(X) = {x U: B(x) X}

B*(X) = {x U: B(x) X }

Definición basada en Gránulo:

B*(X) = {B(x) U/B: B(x) X}

B*(X) = {B(x) U/B: B(x) X }

Definición basada en Subsistema:

B* (X) = {Z: Z U/B, Z X}

B* (X) = {Z: Z U/B, X Z}

Los elementos de B*(X) son todos y solamente aquellos objetos del universo U los cuales

pertenecen a las clases de equivalencia generadas por la relación IB contenidas en X; mientras que

los elementos de B*(X) son todos y solamente aquellos objetos de U los cuales pertenecen a las

clases de equivalencia generadas por la relación de inseparabilidad conteniendo al menos un

objeto x perteneciente a X.

Estas tres definiciones son equivalentes y ofrecen diferentes interpretaciones de las

aproximaciones. De acuerdo a la primera definición, un elemento x pertenece a la aproximación

inferior de un conjunto X si todos sus objetos inseparables están también en X, mientras que un

elemento pertenece a la aproximación superior si al menos uno de los objetos inseparables a él

pertenece a X.

En el caso de la definición basada en gránulo, la aproximación inferior de X es la unión de las

clases de equivalencias que son subconjuntos de X, mientras que la aproximación superior es la

unión de las clases de equivalencias que tienen una intersección no vacía con X.


15

Un tercer enfoque para definir las aproximaciones inferior y superior se basa en el concepto de

subsistema. En este sentido, la aproximación inferior de X es el mayor conjunto definible en el

subsistema (U/B) que está contenido en X, y la aproximación superior es el menor conjunto

definible en (U/B) que contiene a X.

Basada en estas definiciones, es posible establecer enlaces entre los conjuntos aproximados y

otras teorías.

A partir de las aproximaciones inferiores y superiores de un conjunto se define la región límite de

X para la relación de equivalencia B:

Definición 1.5: (Región límite)

BNB(X)= B*(X) – B*(X) (1.5)

Si el conjunto BNB es vacío entonces el conjunto X es exacto respecto a la relación de equivalencia

B. En caso contrario, BNB(X) , el conjunto X es inexacto o aproximado con respecto a B. El

principal objetivo de esta teoría es la síntesis de aproximaciones para los conceptos. En la Figura

1.1 se representan estos conceptos.

Usando las aproximaciones inferior y superior de un concepto X se definen tres regiones para

caracterizar el espacio de aproximación:

i) la región positiva: POS(X)= B*(X).

ii) la región límite: BND(X)= BNB(X).

iii) la región negativa: NEG(X)= U- B*(X).

De acuerdo a los estudios presentados en (Bell and Guan, 1998) y (Deogun, 1998), la complejidad

computacional de encontrar el conjuntos B*(X) o el conjunto B*(X) es O(lm2), donde l es el número

de atributos que describen los objetos y m es la cantidad de objetos en el universo.


16

Figura 1.1 Regiones de los conjuntos aproximados.

Aquí U está representado por un conjunto de celdas. La Aproximación inferior B*(X) la constituyen

las celdas marcadas con “+”. La aproximación superior B*(X) la representa la unión de las celdas

blancas y las marcadas con “+”. La región límite de X, BNB(X) la conforma la colección de las celdas

blancas. Los elementos del conjunto de las celdas marcadas con “–“ con certeza no pertenecen a X

(conforman la también llamada “región negativa”) .

1.3.2 Conjuntos aproximados en sistemas de información incompletos

Usualmente existen dos enfoques para atender el problema de la información incompleta en el

contexto de los conjuntos aproximados. El primero es un método indirecto que consiste en

transformar el sistema de información incompleto en uno completo empleando algún

procedimiento de los que existen para este problema. El segundo es extender la teoría de los

conjuntos aproximados clásica para procesar sistemas de información incompletos (Bello et al.,

2012).

Definición 1.6: (Sistema información incompleto)

Se denomina Sistema de información incompleto a todo sistema de información en el cual exista

al menos un objeto el cual posee al menos un atributo cuyo valor no se conoce.

Un valor nulo para un atributo puede significar que el valor es desconocido, pero también que no

es aplicable ese atributo al objeto específico. Puede ocurrir en modelos como las bases de datos

relacionales y los sistemas de información tal y como se definen para la teoría de conjuntos

aproximados, pues en ambos todos los objetos del universo tienen los mismos atributos.


17

El problema de valores omitidos tiene una complejidad diferente para rasgos continuos y rasgos

discretos. Para atributos continuos poco se puede en tal caso, mientras que para los rasgos

discretos es posible tratar el valor omitido como un valor más del dominio de ese rasgo. Grzymala-

Buze (Grzymala-Busse, 1991), enfrenta el problema transformando una tabla de decisión con

valores desconocidos a otra, posiblemente inconsistente, en la cual los valores para todos los

atributos son conocidos, reemplazando los valores desconocidos por todos los valores del dominio

de ese atributo. En otras palabras, convierte el problema de valores desconocidos al problema de

datos inconsistentes, y luego los procesa usando los conjuntos aproximados. En (Barbara, 1992),

los valores omitidos se interpretan como valores no interesantes de un atributo con los cuales se

asocia una medida de probabilidad.

1.3.2.1 Conjuntos aproximados basados en una relación transitiva

El enfoque clásico de los conjuntos aproximados basados en las relaciones de inseparabilidad

requiere que los datos sean completos, es decir, se conocen los valores para los atributos

condición en todos los objetos. Usualmente hay dos formas para enfrentar el problema de los

datos incompletos en la teoría de los conjuntos aproximados. El primero es una vía indirecta, en la

cual el sistema de información incompleto se transforma en uno completo usando algún método

de completamiento; la segunda es una alternativa directa en la cual se extiende la teoría de los

conjuntos aproximados para procesar los sistemas de información incompletos (Bello et al., 2012).

Definición 1.7: (Relación I)

Sean x, y U, donde y es el sujeto y x es el objeto referente. Se dice que y es inseparable de x, con

respecto al conjunto de atributos P C, denotándolo por yIPx, si para todo q P, se cumple:

i) f(x,q) *,

ii) f(x,q) = f(y,q) or f(y,q )= *.

Nótese que el objeto referente x no puede tener valores desconocidos en el conjunto de atributos

P.

La clase de objetos inseparables de x se representa como:


18

IP(x)= {y U : yIPx) (1.6)

La relación IP no es necesariamente reflexiva ni simétrica, pero si transitiva.

Para cada P C se define el conjunto UP de objetos sin valores desconocidos para los atributos en

P.

UP={x U : f(x,q)* para cada qP (1.7)

A partir de estas definiciones y la relación I se puede construir la aproximación inferior y superior

de un conjunto X U con respecto a un conjunto de atributos de condición P C según la

definición 1.8:

Definición 1.8: (Aproximaciones de un conjunto según la relación I)

IP*(X) = {x UP : IP(x) X} (1.8)

IP*(X)= { x UP : IP(x) X≠} (1.9)

Se satisfacen las relaciones de inclusión y complementariedad siguientes:

Para cada X U y para cada P C: IP*(X) IP*(X).

Para cada X U y para cada P C: IP*(X) = UP - IP*(U-X).

1.3.2.2 Conjuntos aproximados monótonos

Una propiedad muy útil de la aproximación inferior en los conjuntos aproximados clásicos es la

monotonía. Lo cual significa que si un objeto x U pertenece a la aproximación inferior de un

conjunto X con respecto a P C, entonces x pertenece también a la aproximación inferior de X

con respecto a cualquier conjunto de atributos RC cuando PR.

Sin embargo, la forma de construir las aproximaciones para sistemas de información incompletos

no satisface esta propiedad. Lo cual queda claro dado el hecho siguiente:

Es posible que f(x,q) * para todo q P pero f(x,q)=* para algún q R-P.


19

Para obtener la propiedad de monotonía se redefine la relación de inseparabilidad I, denotándola

por II.

Definición 1.9: (Relación II)

Sean x, y U y P C, yIIPx, significa que para todo q P, se cumple:

i) f(x,q) = f(y,q),

ii) f(x,q) = * and/or f(y,q) = *.

La relación IIP es reflexiva y simétrica, pero no transitiva.

Para cada P C se define el conjunto U*P de objetos sin valores desconocidos para algún atributo

en P.

U*P={xU : f(x,q) * para algún qP } (1.10)

La clase de objetos inseparables de x de acuerdo a la nueva relación se representa como:

IIP(x)= {y U : yIIPx } (1.11)

A partir de estas definiciones se puede construir la aproximación inferior y superior de un

conjunto X U con respecto a un conjunto de atributos de condición P C como sigue:

Definición 1.10: (Aproximaciones de un conjunto según la relación II)

IIP*(X)= { x U*P : IIP(x) X } (1.12)

IIP*(X)= { x U*

P : IIP(x) X } (1.13)

1.3.2.3 Conjuntos aproximados para sistemas de información incompletos basados en

una relación no simétrica

Otra alternativa de relación para el caso de los sistemas de información incompletos se define de

la forma siguiente (Bello et al., 2012):

Definición 1.11: (Relación III)


20

Sean x, y U, el objeto x es similar al objeto y (xIIIy), para todo q BA, si y solo si:

i) f(x,q) = f(y,q), o

ii) f(x,q) = *.

La relación III es reflexiva y transitiva, pero no simétrica. Se basa en la idea de una relación de

inclusión, es decir, un objeto x se considera similar a otro y, si y solo si, la descripción de x está

incluida en la descripción de y. Aquí el principio en que se basa el autor es que un valor

desconocido significa que ese atributo no se necesita para describir el objeto; a diferencia de las

dos relaciones anteriores donde los valores desconocidos se interpretan como falta de

información o conocimiento imperfecto sobre el objeto.

Usando la relación III se construyen dos conjuntos, RB(x) y RB-1(x), el primero es el conjunto de los

objetos similares a x, y el segundo el conjunto de objetos a los cuales x es similar:

RB(x)={ y U : yIIIx },

RB-1(x)={ y U : xIIIy }.

Dados estos conjuntos las aproximaciones inferior y superior de un conjunto X dado BA y un

sistema de información incompleto se definen como:

Definición 1.12: (Aproximaciones de un conjunto según la relación III)

B*(X)= { x U : RB-1(x) X} (1.14)

B*(X)= RB(x), x X (1.15)

Este modelo para la teoría de los conjuntos aproximados para sistemas de información

incompletos es un caso particular de la definición de conjuntos aproximados basados en

relaciones de similaridad, tomando como relación de similaridad la Relación III.

1.3.3 Conjuntos aproximados basados en relaciones de similaridad

Diariamente se encuentran situaciones donde se tiene que distinguir entre grupos similares o se

tiene que clasificar algunos elementos como similares. Por eso, la medida de similaridad se


21

convierte en una importante herramienta para decidir la semejanza (el grado de similaridad) entre

dos grupos o entre dos elementos. Ella puede definirse sobre un conjunto arbitrario de objetos de

interés como objetos físicos, situaciones, problemas, etc.. El uso del término similaridad en la

Inteligencia Artificial da la idea de una relación borrosa entre las representaciones de dos objetos.

Una medida de similaridad consiste de tres partes principales (Bello et al., 2012):

Medidas locales de similaridad usadas para comparar los valores de los rasgos

(denominadas funciones de comparación de rasgos, en (Bello et al., 2012) se proponen

algunas).

Pesos asociados a los rasgos los cuales representan la importancia relativa de cada

atributo.

Una medida de similaridad global que indica el grado de similaridad entre dos objetos a

partir de las medidas locales y los pesos (llamada función de semejanza, algunas aparecen

en (Arco, 2009)).

Una generalización del enfoque clásico de los conjuntos aproximados es reemplazar la relación de

inseparabilidad binaria, la cual es una relación de equivalencia, por una relación de similaridad

binaria más débil. En la definición original del concepto de conjuntos aproximados, existe una

relación R que define la inseparabilidad entre los objetos que tienen el mismo valor para los

atributos considerados por R. Por eso, cada relación es una relación de equivalencia.

Tal definición de R puede ser muy restrictiva en muchos casos. Considerar el uso de una relación

de similaridad en lugar de una relación de inseparabilidad resulta relevante. En realidad debido a

la imprecisión en la descripción de los objetos, pequeñas diferencias entre objetos no se

consideran significativas en el proceso de discriminación (formación de las clases de

equivalencias); como sucede frecuentemente con los atributos cuantitativos debido a

imprecisiones en la medición de los mismos, fluctuación aleatoria de algunos parámetros, etc..

Una opción para enfrentar este problema es discretizar tales atributos, lo cual puede traer

consecuencias indeseadas, como el hecho de asociar valores muy cercanos a valores discretos

diferentes. Otra alternativa es considerar la similaridad entre los valores. Entre los conceptos de


22

similaridad e incertidumbre existe una relación mayor que el simple hecho de la definición de

ambas medidas sobre un intervalo real [0,1].

El propósito es extender la relación de inseparabilidad R aceptando que los objetos que no son

inseparables, pero sí suficientemente cercanos o similares se pueden agrupar en la misma clase.

En otras palabras, construir una relación de similaridad R' a partir de R flexibilizando las

condiciones originales de inseparabilidad (Arco, 2009).

Definición 1.13: (Relación de similaridad extendida)

Sea R una relación de inseparabilidad que es una relación de equivalencia definida sobre U. Se

dice que R' es una relación de similaridad extendida desde R, si y solo si,

(i) Para todo x U, R(x)R'(x)

(ii) Para todo x U, Para todo y R'(x), R(y)R'(x)

Donde R'(x) es la clase de similaridad de x, es decir,

R'(x)={ y U : yR'x } (1.16)

Realmente, las relaciones de similaridad son frecuentemente definidas directamente, no como

extensiones de relaciones de equivalencia.

Desde la perspectiva de las propiedades de las relaciones, el carácter transitivo de la relación de

separabilidad es la base. Si la relación es transitiva entonces ella define una partición de U en

bloques de elementos indistinguibles; mientras que relaciones no transitivas dan pie al uso de

relaciones de similaridad. Las similaridades entre los objetos se pueden representar por una

relación binaria R que forma clases de objetos los cuales son idénticos o al menos no

notablemente diferentes en términos de la información disponible sobre ellos.

En general las relaciones de similaridad no generan particiones sobre el universo U, sino clases de

similaridad para cada objeto x U (cubrimientos). La clase de similaridad de x, de acuerdo a la

relación de similaridad R se denota por R(x) y se define como:


23

R(x)= { y U : yRx } (1.17)

Se lee como conjunto de elementos y que son similares a x de acuerdo a la relación R.

La relación R es sólo reflexiva (cada objeto es similar a si mismo). Pero no es transitiva: y es similar

a x y a z, pero z no es similar a x.

y R(x) y y R(z) NOT z R(x), para x, y y z U.

La no transitividad de la relación de similaridad está dada por el hecho de que una serie de

pequeñas diferencias no pueden ser propagadas manteniendo el carácter de pequeñas. Tampoco

tiene que ser simétrica: y es similar a x según R, pero x no es similar a y de acuerdo a R.

y R(x) NOT x R(y), para x, y U.

Pues la relación R es direccional, donde el sujeto es y, y el referente es x. Aunque la mayoría de las

funciones de semejanza son simétricas, varios autores han argumentado el hecho de que la

similaridad no debe ser tratada como una relación simétrica.

Definición 1.14: (Relación de tolerancia y Espacio de tolerancia)

Cuando la relación R XxU es reflexiva (xRx) para cualquier xU, y es simétrica (xRy yRx) para

cualquier par de elementos x, y U, se denomina Relación de tolerancia. El par (U,R) se denomina

Espacio de tolerancia.

Entonces se define la relación inversa R-1, donde xR-1y significa también los objetos y de U

similares a x; luego R-1(x) es la clase de los objetos referentes a los cuales x es similar:

R-1(x)= { y U : xRy } (1.18)

De acuerdo a las propiedades de la relación de similaridad R, un objeto puede pertenecer a

diferentes clases de similaridad simultáneamente. Esto significa que la relación de similaridad

induce un cubrimiento sobre U que no tiene que ser una partición. Un concepto relacionado a la

similaridad entre objetos es el de objeto no ambiguo.

Definición 1.15: (Objeto no ambiguo)


24

Dado un subconjunto X U y una relación de similaridad R sobre U, un objeto x U se llama no

ambiguo si se cumple una de las condiciones siguientes:

i) x X sin ambigüedad, es decir, xX y R-1(x) X, los cuales se denominan positivos.

ii) x X sin ambigüedad, es decir, xU-X y R-1(x) U-X, es decir, R-1(x) X=, los cuales se

denominan negativos.

Los objetos yU que no son positivos ni negativos se denominan ambiguos respecto a X.

Las relaciones de equivalencia inducen particiones del universo U, mientras las relaciones de

similaridad generan un cubrimiento del universo. Un cubrimiento del universo U es una familia de

subconjuntos no vacíos cuya unión es igual a U, y es posible que exista una intersección no vacía

entre pares de esos subconjuntos. Una partición de U es un cubrimiento de U, de modo que el

concepto de cubrimiento es una extensión (generalización) del concepto de partición.

Una vez definido el concepto de relación de similaridad se pueden construir los conjuntos

aproximados basados en éstas. Esta extensión de la teoría de los conjuntos aproximados también

evita la necesidad de discretizar los atributos de dominio continuo. En (Greco, 2001) se presenta

un estudio de esta problemática. Entre las extensiones realizadas a la RST basadas en relaciones

de similaridad está la siguiente.

Definición 1.16: (Aproximaciones basadas en similaridad)

R. Slowinski y D. Vanderpooten (Slowinski and Vanderpooten, 2000) definen la aproximación

inferior y superior de un conjunto X de la forma siguiente. Sea XU y R una relación binaria

reflexiva definida sobre U, entonces:

R*(X)={ xU : R-1(x) X } (1.19)

R*(X)= R(x), xX; (1.20)

lo cual es equivalente a:

R*(X)= { xU : R-1(x) X } (1.21)


25

También se cumple, como en los conjuntos aproximados basados en relaciones de equivalencia,

que:

R*(X) X R*(X) (1.22)

R*(X)= U – R*(U-X) (1.23)

El uso de relaciones de similaridad ofrece mayores posibilidades para la construcción de las

aproximaciones; sin embargo, se tiene que pagar por ésta mayor flexibilidad, pues es más difícil

desde el punto de vista computacional buscar las aproximaciones relevantes en este espacio

mayor.

Finalmente en la Figura 1.2 se muestra la RST extendida.

Figura 1.2 Representación de RST extendida.

1.3.4 Medidas para realizar inferencias

Sobre la base del conocimiento en B los objetos que pertenecen a B*(X) pueden ser clasificados

con certeza como miembros de X, los objetos miembros de B*(X) pueden ser solamente

clasificados como posibles miembros de X. Los elementos en BNB no pueden ser clasificados con


26

absoluta certeza como miembros del conjunto X. Los elementos del conjunto U-B*(X) con certeza

no pertenecen a X.

Por eso, los conjuntos aproximados pueden ser vistos como un modelo matemático de los

conceptos vagos, es decir, aquellos en los que los elementos del universo no pueden ser

clasificados con certeza como elementos o no del concepto. Las principales medidas construidas a

partir de los conjuntos aproximados son las siguientes(Bello et al., 2012).

Definición 1.17: Precisión de la aproximación (accuracy of the approximation)

La vaguedad del concepto o conjunto X, también llamada precisión de la aproximación (accuracy),

con respecto a la relación B se puede caracterizar matemáticamente por el coeficiente:

XB

XBXB *

* (1.24)

Donde X denota la cardinalidad del conjunto X, y 0B(X)1. Si B(X)=1, el conjunto X será duro

o exacto con respecto a la relación de equivalencia B, mientras que si B(X)1, el conjunto X es

aproximado o vago con respecto a B. Esta magnitud mide el grado de perfección o integridad del

conocimiento sobre el conjunto X considerando los atributos incluidos en la relación de

equivalencia.

Definición 1.18: Calidad de la aproximación (quality of approximation)

La calidad de la aproximación de X por medio de los atributos en B se define por:

X

XBXB

*

(1.25)

Esta medida de calidad representa la frecuencia relativa de los objetos correctamente clasificados

por medio de los atributos en B. Además, 0 B(X) B(X) 1.

La medida de Deogun es una unificación de estas dos medidas, la cual se define en la expresión:


27

XPOS*sX*s

XPOSXXB

21

)(

(1.26)

donde s1 y s2 son factores de escala tal que s1+s2=1.

Las definiciones para las aproximaciones de un conjunto X se pueden extender a una clasificación,

es decir, una partición Y= {Y1, ..., Yn} de U. Los subconjuntos Yi son clases disjuntas de Y. Las

aproximaciones inferior y superior se definen como B*Y= {B*Y1,..., B*Yn}, y B*Y= {B*Y1,..., B*Yn},

respectivamente.

Definición 1.19: Calidad de la clasificación (quality of classification)

El coeficiente:

U

YiB

Y

n

iB

1

*

)(

(1.27)

se denomina calidad de la clasificación. Esta es una de las medidas más usadas de la RST, pues ella

permite medir el grado de consistencia del sistema.

Empleando el concepto de inseparabilidad se puede definir la función de pertenencia a conjuntos

aproximados. Si el concepto o conjunto X es vago sus contornos no están rigurosamente definidos

por lo que surge la incertidumbre relacionada con la cuestión de la pertenencia de los elementos

al conjunto.

Definición 1.20: Función de pertenencia aproximada (Rough membership function)

La función de pertenencia de un elemento x a un conjunto X según la relación de equivalencia B se

define como:

xB

xBXxB

X

(1.28)

Obviamente el grado de pertenencia está en el intervalo [0,1]. La función de pertenencia puede

ser comprendida como un coeficiente de la certidumbre que un elemento x sea miembro del


28

conjunto X. Esta medida cuantifica el grado de correspondencia relativa entre el conjunto X y la

clase de equivalencia a la cual pertenece x.

Con esta medida de pertenencia se pueden redefinir los conceptos de aproximaciones inferior y

superior de un conjunto de la forma siguiente:

B*(X)= xU XB(x) (1.29)

B*(X)= xU X

B(x) > 1- (1.30)

Otra medida asociada a los conjuntos aproximados es la denominada aspereza (roughness) del

conjunto, la cual representa el grado de incompletitud del conocimiento sobre el conjunto

aproximado a partir de los atributos considerados en la relación de equivalencia y se calcula como:

B(X)=1 - B(X) (1.31)

Las medidas precisión y calidad de la aproximación están asociadas a cada concepto, por tanto,

ofrecen una valoración local de cada grupo obtenido. Sin embargo, en muchos casos es necesario

medir la calidad y la precisión como un todo considerando el sistema de información y los

conceptos X1, …, Xk definidos sobre él, con k total de conceptos. El coeficiente calidad de la

clasificación, expresión (1.32), describe la inexactitud de los conceptos, expresando la proporción

de los objetos que pueden estar correctamente asignados a los grupos en el sistema. Si ese

coeficiente es uno, el sistema de información según los conceptos definidos es consistente, en

otro caso es inconsistente (Pawlak, 1991).

U

XRk

i

i 1

* )(

(1.32)

La precisión de la clasificación, definida en (Arco, 2009), expresa las posibles clasificaciones

correctas. En la expresión (1.33) se observa que su esencia es mostrar la proporción entre la

cantidad de objetos que pudieran estar bien clasificados y la cantidad de objetos que pudieran o

no pertenecer a las clases del sistema de información.


29

k

i

i

k

i

i

XR

XR

1

*

1

*

)(

)(

(1.33)

En (Magdaleno, 2008) se propone la Medida-F aproximada (Rough F-measure; RFM) y la forma de

cálculo se muestra en (1.34), donde α es un parámetro entre 0 y 1 que permite regular la

influencia de la precisión y la calidad de la clasificación en el índice general. Si α =1 entonces RFM

coincide con la precisión, si α =0 entonces RFM coincide con la calidad de la clasificación. α =0.5

significa igual peso para la precisión y la calidad de la clasificación.

)/1)(1()/1(

1

GG

RFM

(1.34)

En (Arco, 2009) se proponen las expresiones (1.35) y (1.36) como otras formas para medir la

pertenencia aproximada de un objeto x a un concepto X.

X

xRXxX

)()(

(1.35)

)(

)()(

xRX

xRXxX

(1.36)

1.3.5 Reductos

Definición 1.21: (Reducto)

Dado un sistema de información S=(U,A), donde U es el universo y A es el conjunto de atributos,

un reducto de éste es un conjunto mínimo de atributos BA tal que IA = IB.

En otras palabras, un subconjunto E de atributos es un reducto del conjunto de atributos A si E es

ortogonal y preserva la clasificación generada por A:

E=RED(A) ( EA, IND(E)=IND(A), E es ortogonal).


30

El cálculo de reductos es una tarea compleja; de allí que se hayan desarrollado diversos métodos

para ejecutarla. El problema de encontrar el conjunto de reductos mínimos es NP-duro y

representa uno de los principales punto de atención en la teoría de los conjuntos aproximados. En

este proceso no es posible escapar del costo computacional exponencial del mismo, a menos que

se aplique alguna técnica de Inteligencia artificial. Existen buenos métodos heurísticos que

computan reductos de una manera satisfactoria, decreciendo el costo de cómputo.

Definición de Núcleo

Asociado al concepto de reducto, está el concepto de núcleo (core) del sistema de información S.

El núcleo está constituido por el conjunto de atributos que pertenecen a la intersección de todos

los reductos del sistema de información.

Definición 1.22: (Núcleo)

SductR

RSNucleoRe

(1.37)

Una alternativa es considerar como relevantes a aquellos atributos que pertenecen al núcleo del

sistema. También se consideran relevantes aquellos atributos que pertenecen a reductos

dinámicos con una estabilidad suficientemente alta (Bello et al., 2012).

Comenzar la búsqueda de los reductos o sus variantes a partir de los rasgos en el núcleo puede

conducir a una rápida identificación de subconjuntos de rasgos útiles, estrechándose la búsqueda

considerablemente. Pero está claro que identificar los atributos que pertenecen al núcleo a partir

del sistema de información es un problema de inducción en sí.

1.3.5.1 Tipos de reductos

El cálculo de los reductos de un sistema de decisión es un proceso computacionalmente costoso.

Por otra parte, usualmente los ruidos presentes en el universo obligan a trabajar con cierta

incertidumbre. Esto ha llevado al desarrollo de algunas variantes para el concepto de reducto que

constituyen métodos para calcularlos. En (Bello et al., 2012) se muestran dos variantes del

concepto de reducto, denominadas: reductos dinámicos (dynamic reducts) y reductos

aproximados (approximated reducts).


31

Una alternativa es computar los llamados reductos dinámicos. El procedimiento consiste en

calcular reductos para algún subconjunto del universo, y seleccionar los reductos más estables, es

decir, los que aparecen más frecuentemente, estos se denominan reductos dinámicos, pueden ser

inconsistentes con el sistema de decisión original, pero son adecuados para inferir reglas a partir

de ellos.

Los reductos dinámicos son calculados a partir del coeficiente de estabilidad de un reducto en una

familia de subsistemas de un sistema de decisión.

Sea un sistema de decisión S=(U, A{d}). Un subsistema de S es cualquier sistema de información

Si=(Ui, A{d}), tal que UiU. Sea F una familia de subsistemas de S.

Definición 1.23: (Coeficiente de estabilidad de un reducto)

El coeficiente de estabilidad (CoefSta) de un reducto CRED(Si,d) se define por la expresión (1.38)

F

dSREDCFSCCoefSta

ii ,:

(1.38)

Definición 1.24: (Reductos dinámicos)

Sea un número real en el intervalo [0,1]. El conjunto DR(S,F) de (F, )-reductos dinámicos se

define por la expresión:

1:,, CCoefStadSREDCFSDR (1.39)

Definición 1.25: (Reducto aproximado)

Si en lugar de considerar el conjunto de atributos de condición C, se usa un subconjunto BC de

él, entonces se obtiene un reducto aproximado de C. El error de utilizar ese reducto aproximado

se calcula según la expresión (1.40).

DC

DBBe DC

,

,1,

(1.40)


32

Este valor expresa cuán exactamente el conjunto de atributos B aproxima el conjunto de atributos

de condición C con relación al conjunto de atributos de decisión D.

El concepto de reducto aproximado es una generalización del concepto de reducto. Un

subconjunto mínimo B de los atributos de condición C, tal que e(C,D)(B)=0, es un reducto.

1.3.5.2 Cálculo de reductos

El cálculo de reductos se puede ver como un caso de particular de un problema más general de

selección de rasgos en el cual el objetivo es encontrar un subconjunto que maximiza algún criterio

y donde cada rasgo se selecciona o no. Los algoritmos para la selección de rasgos buscan a través

del espacio de rasgos el mejor subconjunto entre los 2N-1 subconjuntos candidatos, donde N

denota la cantidad de rasgos. Cada estado representa un subconjunto de rasgos en el espacio de

búsqueda. Todas las técnicas de selección tienen en común dos componentes importantes: una

función de evaluación usada para evaluar subconjuntos de rasgos y un procedimiento de

búsqueda que genera los subconjuntos.

La función de evaluación estima la capacidad discriminatoria del subconjunto de rasgos para

distinguir entre diferentes clases. Esta mide la calidad (goodness) de un subconjunto que ha sido

generado por el procedimiento de búsqueda. Existen diferentes tipos de funciones de evaluación

tales como medidas de distancia, medidas de información (por ejemplo, la entropía), medidas de

dependencia, medidas de consistencia y medidas de error en la clasificación. Una de las medidas

de la RST más populares es la calidad de la clasificación. Algunas de las medidas satisfacen la

llamada propiedad de monotonía; es decir, (X+) (X), donde denota una función de

evaluación, X describe un subconjunto de rasgos y X+ denota un subconjunto extendido que

contiene a X (Bello et al., 2012).

La segunda componente del proceso de selección de rasgos es el procedimiento de búsqueda. Las

estrategias de búsqueda son importantes porque el proceso de búsqueda es muy costoso, y una

búsqueda exhaustiva del subconjunto óptimo no es factible para problemas de dimensión media.

Por eso, los métodos aproximados son más apropiados. Ejemplo de estas estrategias son la

búsqueda heurística, métodos probabilísticos, y los algoritmos híbridos.


33

Los métodos de búsqueda heurísticas (del griego heuriskein, que significa encontrar) están

orientados a reducir la cantidad de búsqueda requerida para encontrar una solución. Cuando la

solución de un problema se presenta como un árbol de búsqueda el enfoque heurístico intenta

reducir el tamaño del árbol cortando nodos pocos prometedores. La calidad del nodo se estima

numéricamente por una función de evaluación heurística f(n). Una función de evaluación

heurística es una función que hace corresponder situaciones del problema con números, (f(n)

). Es decir, da una medida conceptual de la distancia entre un estado dado y el estado objetivo.

Estos valores son usados para determinar cuál operación ejecutar a continuación, típicamente

seleccionando la operación que conduce a la situación con máxima o mínima evaluación. En (Bello

et al., 2012) se proponen algunas heurísticas para el cálculo de reductos, tal como el ascenso de

colina (Hill-Climbing), con algunas de sus adaptaciones y la metaheurística Optimización basada en

colonias de hormigas (Ant Colony Optimization, ACO).

1.4 CONSIDERACIONES PARCIALES DEL CAPÍTULO

En el presente capítulo hemos abordado los principales conceptos y definiciones de la teoría

básica de conjuntos, la cual sirve de base para la Teoría de Conjuntos Aproximados. En un primer

momento se analizó la teoría clásica la cual está sostenida sobre las relaciones de equivalencia.

Posteriormente analizamos una de sus extensiones la cual hace referencia a Sistemas de Decisión

con información incompleta, en este aspecto se analizaron tres relaciones de inseparabilidad

entre objetos. La primera analizada no permite que el objeto referente tenga valores perdidos,

mientras que las otras si dan esta posibilidad.

A continuación se analiza la extensión basada en relaciones de similaridad, esta es de gran

importancia dado que en situaciones donde se tiene que distinguir entre grupos similares o se

requiere clasificar algunos elementos como similares esta extensión se convierte en una

importante herramienta para decidir el grado de semejanza entre grupos o elementos.

Finalmente, se da a conocer el concepto de reducto, el cual constituye prácticamente la base de

los métodos que se desarrollan usando conjuntos aproximados, pues están directamente

relacionado con la relación de separabilidad.

34

2 BIBLIOTECA EN JAVA QUE PERMITE TRABAJAR CON LOS CONJUNTOS APROXIMADOS

Este capítulo alude a las generalidades de la biblioteca RST: su diseño, características y lenguaje de

desarrollo. Expone los diagramas creados para las fases de análisis y diseño de la biblioteca y el

funcionamiento de la misma. Además, presenta una reseña del lenguaje Java en el cual esta fue

creada.

2.1 GENERALIDADES DEL LENGUAJE JAVA

Dado que Weka está desarrollo en Java se escogió este lenguaje, desarrollado por Sun

Microsystems de ORACLE, para desarrollar la biblioteca de RST. Java es un lenguaje de

programación que es distribuido actualmente como software libre bajo una licencia GNU GPL

(General Public License), lo cual lo hace un gran candidato para el uso en el desarrollo de

aplicaciones en países del tercer mundo. El lenguaje Java fue creado para trabajar con objetos y

de manera independiente a la plataforma. Esto es posible debido a la JVM (Java Virtual Machine)

la cual es una máquina genérica, que ejecuta un código creado al compilar un programa, que corre

indistintamente en cualquier ordenador que tenga instalada dicha máquina virtual. Java es un

lenguaje robusto justamente por la forma en que está diseñado, no permite el manejo directo del

hardware ni de la memoria. Implementa además mecanismos de seguridad que limitan el acceso a

recursos de las máquinas donde se ejecuta.

La Plataforma Java (Wikipedia, 2013)se compone de un amplio abanico de tecnologías, cada una

de las cuales ofrece una parte del complejo de desarrollo o del entorno de ejecución en tiempo

real. Por ejemplo, los usuarios finales suelen interactuar con la máquina virtual de Java y el

conjunto estándar de bibliotecas. Para el desarrollo de aplicaciones, se utiliza un conjunto de

herramientas conocidas como JDK (Java Development Kit) o herramientas de desarrollo para Java.

Principales características de Java (Schildt, 2001):

Universalidad: Aunque es un programa interpretado no es en principio tan rápido como

un programa equivalente compilado, las prestaciones de Java son sin embargo mejores

Capítulo 2: Biblioteca en Java que permite trabajar con los conjuntos aproximados

35

que las de cualquier lenguaje interpretado. Este hecho, junto con la sencillez de

programación en Java ha propiciado que se hayan escrito intérpretes de pequeño tamaño

adaptados a prácticamente cualquier plataforma, desde mainframes y ordenadores

personales (con cualquier sistema operativo: Windows, Macintosh OS, Unix,...) hasta

dispositivos electrónicos de bajo coste. También se suele hacer referencia a la

universalidad de Java con términos equivalentes como transportabilidad, o independencia

de plataforma, pues para ejecutar un programa basta compilarlo una sola vez, a partir de

entonces, se puede hacer correr en cualquier máquina que tenga implementado un

intérprete de Java.

Sencillez: Java es un lenguaje de gran facilidad de aprendizaje, pues en su concepción se

eliminaron todos aquellos elementos que no se consideraron absolutamente necesarios.

Por otro lado, Java dispone de un mecanismo conocido como "recogida de basura", el cual

usando la capacidad multitarea de Java hace que, durante la ejecución de un programa,

los objetos que ya no se utilizan se eliminen automáticamente de la memoria. Dicho

mecanismo facilita enormemente el diseño de un programa y optimiza los recursos de la

máquina que se esté usando para la ejecución del mismo (con los lenguajes tradicionales,

la eliminación de objetos y la consiguiente optimización de recursos debe planificarse

cuidadosamente al idear el programa).

Orientación a objetos: Un objeto es un elemento de programación, autocontenido y

reutilizable, y que podríamos definir como la representación en un programa de un

concepto, representación que está formada por un conjunto de variables (los datos) y un

conjunto de métodos (o instrucciones para manejar los datos).

Seguridad: En general, se considera que un lenguaje es tanto más seguro cuanto menor es

la posibilidad de que errores en la programación, o diseños malintencionados de

programas (virus), causen daños en el sistema.

2.2 DESARROLLO DE BIBLIOTECAS EN JAVA

En Ciencia de la Computación, una biblioteca (library) es un conjunto de subprogramas utilizados

para desarrollar software. Las bibliotecas contienen código y datos, que proporcionan servicios a


36

programas independientes, es decir, pasan a formar parte de éstos. Esto permite que el código y

los datos se compartan y puedan modificarse de forma modular. Algunos programas ejecutables

pueden ser a la vez programas independientes y bibliotecas, pero la mayoría de éstas no son

ejecutables. Ejecutables y bibliotecas hacen referencias (llamadas enlaces) entre sí a través de un

proceso conocido como enlace, que por lo general es realizado por un software denominado

enlazador (Barrientos, 2009).

Ventajas de Java para el desarrollo de Bibliotecas (Alwang et al., 1998):

Se intensifica y acelera la entrega de mejoras de la aplicación, garantizando por

consiguiente una mayor versatilidad y adaptabilidad a las tecnologías emergentes y a las

necesidades crecientes, en materia de servicios, de la comunidad de usuarios de las

Bibliotecas.

No sólo las mejoras llegan antes a las Bibliotecas, incrementando su rendimiento, sino que

también llegan con un menor coste financiero del mantenimiento del software.

La sencillez de las construcciones de que consta Java permiten obtener un código de

tamaño reducido, por lo que la penalización en que se incurre (con respecto a la

utilización de un lenguaje compilado) por la necesidad de interpretarlo se reduce

considerablemente, y las diferencias en la rapidez de ejecución serán inapreciables por el

usuario.

2.3 CONCEPCIÓN GENERAL DE LA BIBLIOTECA RST

Entre los IDE disponibles para Java se seleccionó el NetBeans 6.8, el cual es un ambiente de

programación cómodo, que compila en tiempo real y fácil de usar para depurar un programa.

La biblioteca se encuentra encapsulada como un paquete bajo el nombre de RST, para la creación

de la misma accedemos en la barra de menú File/New Project, como se muestra en la Figura 2.1.


37

Figura 2.1 Cuadro de diálogo para la creación de un proyecto en Java.

Seleccionamos el tipo de proyecto Java Class Library, a continuación le pondremos nombre a la

biblioteca y la ubicación en disco como se muestra en la Figura 2.2.

Figura 2.2 Cuadro de diálogo para la creación de una nueva biblioteca en Java.


38

Para utilizar la misma la importamos mediante import RST, o en caso que deseemos acceder a

sus componentes internas lo hacemos mediante

import RST.<nombre_de_la_componente>

La compilación y construcción del paquete RST el cual contiene las extensiones agregadas a Weka

fue realizada usando Apache Ant versión 1.9.1 (Foundation, 2013), dicho paquete puede cargarse

en cualquier versión de Weka posterior a la 3.7.7.

2.3.1 Diseño de la biblioteca RST

Como planteamos con anterioridad, la biblioteca se encuentra encapsulada en un paquete con el

nombre RTS, para su concepción se ha diseñado una estructura de paquetes, uno dentro de otro,

para de esta manera separar las diferentes extensiones de la teoría de conjuntos aproximados.

Como se muestra en la Figura 2.3 se ha desglosado en los paquetes missing, reducts y measures,

dentro de este último se encuentran distance, similarity y conversor.

En el paquete missing hemos agrupado las clases correspondientes a los conjuntos aproximados

en sistemas de información incompletos. En measures se encuentran encapsuladas las clases que

hacen tratamiento a los conjuntos aproximados basados en relaciones de similaridad. Dentro de

distance se encuentran medidas de distancia, análogamente en similarity se encuentran medidas

de similaridad. Finalmente en conversor se han implementado varias formas de convertir una

medida de distancia en una medida de similaridad.


39

Figura 2.3 Diagrama de paquetes.

2.3.2 Diagrama de clases

La técnica del diagrama de clases se ha vuelto muy importante en los métodos orientados a

objetos. El diagrama de clases describe los tipos de objetos que hay en un sistema y las diversas

clases de relaciones estáticas (asociaciones, subtipos) que existen entre ellos. También muestran

los atributos y operaciones de una clase y las restricciones a que se ven sujetos, según la forma en

que se conecten los objetos (Fowler and & Scott, 1997).

En la Figura 2.4 se ilustran las clases principales de la biblioteca mediante un diagrama de clases

en UML. En el mismo, solo se hace mención a las clases más importantes de la biblioteca, ya que

se omitieron algunas medidas de similitud y distancia, para así hacer el diagrama menos extenso y

facilitar su concepción general.

El paquete RST contiene a las clases RoughSet y ClassicRoughSet, como se observa en la Figura 2.5.

La clase RoughSet, es una clase abstracta de la cual heredan todas clases que correspondan a una

extensión de RST. Esta contiene las principales medidas internas de RST para realizar inferencia:

accuracyAprox(): Precisión de la aproximación, según la expresión (1.24).


40

qualityAprox(): Calidad de la aproximación, según la expresión (1.25).

Deogun(): Deogun, según la expresión (1.26).

qualityClassification (): Calidad de la clasificación, según la expresión (1.27).

membership(): Función de pertenencia aproximada, según la expresión (1.28).

roughness(): Aspereza del conjunto, según la expresión (1.31).

qualityGeneral(): Calidad de la clasificación, según la expresión (1.32).

accuracyGeneral(): Precisión de la clasificación, según la expresión (1.33).

roughFMeasure(): Medida-F aproximada, según la expresión (1.34).

membershipConcept(): Pertenencia aproximada, según la expresión (1.35).

membershipUnion(): Pertenencia aproximada, según la expresión (1.36).

Además, posee el método concept(), el cual es el encargado de buscar los elementos que

pertenecen a la clase pasada por parámetro y los métodos abstractos relationshipClasses(),

lowerAprox(), upperAprox() y relationship(), los cuales son necesarios sobrescribir según las

particularidades y definiciones de la extensión de la teoría. El método relationship() constituye la

base de la teoría ya que él establece la relación entre dos objetos (instancias) para los atributos

especificados. El método relationshipClasses() devuelve todas las clases de relación según la

relación establecida en relationship(). Los métodos lowerAprox() y upperAprox() calculan la

aproximación inferior y superior de un conjunto dado, respectivamente. Esta clase, además, posee

los métodos positiveRegion(), negativeRegion() y boundaryRegion(), estos calculan la región

positiva, región negativa y región frontera de los conceptos, respectivamente. La clase

ClassicRoughSet corresponde a la teoría de los conjuntos aproximados clásica, y además de los

métodos heredados por RoughSet, posee los métodos lowerAproxMembership() y

upperAproxMembership(), los cuales calculan la aproximación inferior y superior de un conjunto

según las expresiones (1.29) y (1.30), respectivamente.


41

En la Figura 2.6 se muestra el diagrama de clases del paquete missing. Este contiene tres clases:

MissingValuesRI, MissingValuesRII y MissingValuesRIII, estas clases corresponden a las

extensiones mencionadas en el epígrafe 1.3.2. Las clases MissingValuesRI y MissingValuesRII

poseen, además, un método llamado noMissValues(), el cual calcula el conjunto de objetos que no

poseen valores perdidos, según las expresiones (1.7) y (1.10), respectivamente. La clase

MissingValuesRIII posee el método relationshipXTo() que calcula los elementos a los cuales x es

similar.

El paquete measure se muestra en la Figura 2.7, este contiene a las clases SimilarityRelationship,

Measure y Threshold. La clase SimilarityRelationship, tiene como atributos un objeto de tipo

Measure y un objeto de tipo Conversor, contiene el método relationshipXTo() que calcula los

elementos a los cuales x es similar, según la expresión (1.18). Además, contiene los métodos

lowerAproxMembership() y upperAproxMembership(), los cuales calculan la aproximación inferior

y superior de un conjunto según las expresiones (1.29) y (1.30), respectivamente.

De la clase Measure extienden dos clases: Similarity y Distance. Para implementar una medida de

similitud basta con extender de Similarity e implementar el método relation(), de forma análoga

procedemos si queremos implementar una medida de distancia, pero extendiendo de la clase

Distance. En el Anexo 2 se muestran las funciones de distancias y similitudes implementadas en la

biblioteca.

El otro atributo de la clase SimilarityRelationship es el objeto Conversor, esta interfaz tiene como

objetivo permitir que se utilicen distintas variantes para convertir de una medida de distancia a

una de similitud, en el Anexo 1 se muestran las variantes implementadas en la biblioteca.

La clase Threshold posee distintos métodos para el cálculo del umbral de similitud entre objetos,

en la biblioteca se incluyen todos aquellos relacionados en el Anexo 3.


42

Figura 2.4 Diagrama de clases.


43

Figura 2.5 Clases del paquete RST.


44

Figura 2.6 Clases del paquete missing.


45

Figura 2.7 Clases del paquete measure.


46

2.3.3 Cálculo de reductos

En la literatura varias metaheurísticas han sido utilizadas para calcular reductos, incluyendo

Recocido Simulado (González, 2011), Algoritmos Genéticos (Bello et al., 2012), Colonias de

Hormigas (Bello, 2005b, Bello, 2005a, Bello, 2005c). En este Trabajo de Diploma se utilizan

Colonias de Hormigas pues los algoritmos de optimización de colonias de hormigas se aplican

exitosamente en muchos problemas de optimización combinatoria. Ellos tienen una ventaja sobre

los enfoques recocido simulado y los algoritmos genéticos en problemas similares cuando el grafo

puede cambiar su estructura de manera dinámica, el algoritmo de colonia de hormigas puede

seguir corriendo continuamente y adaptar los cambios en tiempo real (Dorigo, 2007).

2.3.3.1 Optimización basada en colonias de hormigas

La Optimización basada en Colonias de hormigas (Ant Colony Optimization; ACO) son modelos

poblacionales inspirados en el comportamiento de las hormigas naturales. Para el cual realizan un

proceso constructivo y estocástico guiado por unos rastros de feromona que va depositando cada

hormiga, dando una medida de cuan deseado ha sido un determinado camino, y a través de una

función de visibilidad que evalúa la calidad del desplazamiento. Es un ejemplo clásico de

comunicación indirecta (stigmergy) (Dorigo, 2007).

Los algoritmos ACO se inspiran directamente en el comportamiento de las colonias reales de

hormigas para solucionar problemas de optimización combinatoria. Se basan en una colonia de

hormigas artificiales, esto es, unos agentes computacionales simples que trabajan de manera

cooperativa y se comunican mediante rastros de feromona artificiales. Los algoritmos de ACO son

esencialmente algoritmos constructivos: en cada iteración del algoritmo, cada hormiga construye

una solución al problema recorriendo un grafo de construcción G. Cada arista del grafo, que

representa los posibles pasos que la hormiga puede dar, tiene asociada dos tipos de información

que guían el movimiento de la hormiga:

• Información heurística, que mide la preferencia heurística de moverse desde el nodo r

hasta el nodo s, o sea, de recorrer la arista ars. Se denota por ηrs. Las hormigas no

modifican esta información durante la ejecución del algoritmo.


47

• Información de los rastros de feromona artificiales, que mide la “deseabilidad aprendida”

del movimiento de r a s. Imita a la feromona real que depositan las hormigas naturales en

forma numérica. Esta información se modifica durante la ejecución del algoritmo

dependiendo de las soluciones encontradas por las hormigas. Se denota por τrs.

El modo de operación básico de un algoritmo ACO es como sigue: las m hormigas (artificiales) de

la colonia se mueven, concurrentemente y de manera asíncrona, a través de los estados

adyacentes del problema (que puede representarse en forma de grafo con pesos). Este

movimiento se realiza siguiendo una regla de transición que está basada en la información local

disponible en las componentes (nodos). Esta información local incluye la información heurística y

memorística (rastros de feromona) para guiar la búsqueda. Al moverse por el grafo de

construcción, las hormigas construyen incrementalmente soluciones. Opcionalmente, las

hormigas pueden depositar feromona cada vez que crucen un arco (conexión) mientras que

construyen la solución (actualización en línea paso a paso de los rastros de feromona). Una vez

que cada hormiga ha generado una solución se evalúa ésta y puede depositar una cantidad de

feromona que es función de la calidad de su solución (actualización en línea de los rastros de

feromona). Esta información guiará la búsqueda de las otras hormigas de la colonia en el futuro.

Además, el modo de operación genérico de un algoritmo de ACO incluye dos procedimientos

adicionales, la evaporación de los rastros de feromona y las acciones del demonio. La evaporación

de feromona la lleva a cabo el entorno y se usa como un mecanismo que evita el estancamiento

en la búsqueda y permite que las hormigas busquen y exploren nuevas regiones del espacio. Las

acciones del demonio son acciones opcionales -que no tienen un contrapunto natural- para

implementar tareas desde una perspectiva global que no pueden llevar a cabo las hormigas por la

perspectiva local que ofrecen. Ejemplos son: observar la calidad de todas las soluciones generadas

y depositar una nueva cantidad de feromona adicional sólo en las transiciones/componentes

asociadas a algunas soluciones, o aplicar un procedimiento de búsqueda local a las soluciones

generadas por las hormigas antes de actualizar los rastros de feromona. En ambos casos, el

demonio reemplaza la actualización en línea a posteriori de feromona y el proceso pasa a llamarse

actualización fuera de línea de rastros de feromona.

Para los modelos existen distintos criterios de parada, entre los que se encuentran:


48

• Se alcanza un número máximo de iteraciones o ciclos.

• Se obtiene una solución con una calidad deseada.

• Se alcanza un tiempo límite o predeterminado de procesamiento.

• Se obtiene un número máximo de evaluaciones de la función objetivo.

En ACO el significado de los rastros de feromona y la función heurística o de visibilidad, dependen

totalmente del problema a resolver. En el caso de los rastros de feromona, cuando tenemos un

problema de secuenciación (Viajante de Comercio, Secuenciación de Tareas,..), donde el orden en

que aparezcan las componentes en una solución, influye en la calidad de esta. En este caso los

rastros de feromona son asociados a los arcos del grafo, con el objetivo de premiar las buenas

secuencias de las componentes. En otros problemas (Selección de Rasgos, Cubrimiento de

Conjuntos,..), donde los cambios de posición entre componentes de una solución no varía la

calidad de esta, los rastros de feromona se asocian a los nodos del grafo. En estos problemas, lo

que interesa es qué componente se seleccionó y no el orden en que aparecen.

Dentro de los algoritmos ACO las diferencias fundamentales radican; en la regla de transición de

estados que utilizan para la construcción de las soluciones, y en el momento y la forma en que

actualizan los rastros de feromona. De aquí la justificación de la cantidad de modelos existentes.

2.3.3.2 Cálculo de reductos usando ACO

El cálculo de reductos es un ejemplo de problema discreto complejo. Este problema puede ser

modelado de la forma siguiente usando un enfoque híbrido en el cual la generación de

subconjuntos se realiza mediante un algoritmo ACO y la evaluación de estos subconjuntos se

ejecuta usando una medida de calidad de la RST. Sea A={a1, a2,…; aNr} un conjunto de rasgos. Este

conjunto se puede visualizar como una red de nodos cada uno de los cuales representa un rasgo y

que están completamente conectados por enlaces bidireccionales. Valores de feromona i están

asociados a cada nodo ai. Esta es una diferencia del modelo respecto a la representación

tradicional de los modelos basados en colonias de hormigas (Bello et al., 2012) donde la feromona

se asocia a los enlaces, y también con respecto al algoritmo propuesto por Jensen and Shen


49

(Jensen and Shen, 2003). De modo que en el modelo usado no es significativo el orden en que

fueron seleccionados los rasgos a los efectos de la actualización de los valores de la feromona.

En el primer paso cada hormiga se asigna a un nodo. El conjunto bk denota el subconjunto de

rasgos que forma la k-ésima hormiga. De modo que inicialmente bk {ai}, donde ai es el rasgo

asociado al nodo donde es asignada inicialmente la k-ésima hormiga. Las hormigas ejecutan un

proceso de selección hacia delante en que cada hormiga k expande su subconjunto bk paso a paso

añadiendo nuevos rasgos; para realizar esto, la k-ésima hormiga analiza todos los rasgos del

conjunto A-bk, y selecciona el próximo rasgo a incluir en bk de acuerdo a la regla de selección del

algoritmo ACO. Se usa la medida calidad de la aproximación de la clasificación, según la expresión

(1.25), como información heurística en la regla. Este valor también se usa para determinar si el

subconjunto bk es un reducto.

Se realizó el estudio del algoritmo ACS-RST-FS (Bello, 2005c) basado en Ant Colony System.

Aspectos fundamentales de ACS-RST-FS:

a) Espacio de búsqueda: Se utiliza un grafo completo en el cual hay un nodo por cada

atributo. Cada nodo ai, correspondiendo al i-ésimo rasgo tiene asociado un valor de

feromona i.

b) Distribución inicial de las hormigas: Al inicio de cada ciclo las hormigas se distribuyen

sobre los nodos del grafo de acuerdo a la relación entre la cantidad de hormigas (m) que

se utiliza y la cantidad de rasgos (Nr), siguiendo las reglas siguientes, donde na es la

cantidad de atributos:

i) If m < na, then Distribución inicial aleatoria de las hormigas.

ii) If m = na, then Una hormiga es asociada con cada nodo.

ii) If m > na, Las primeras Nr hormigas se sitúan según la regla (ii) y el resto según (i).

c) Función heurística y regla de selección: La función heurística () de los algoritmos ACO

usada como función de evaluación de un subconjunto de rasgos B es (B)= B(Y).


50

caseotherinI

qqifYi i

k aBi 0)(*max

(2.1)

donde I se selecciona usando la expresión:

k

j

BAa

b

aB

a

j

b

aB

a

j

k

j

j

k

k BAaifY

Y

Baif

aBp

kj

jk

jk

*

*

0

,

(2.2)

d) Cálculo del valor de feromona inicial: Se estudiaron tres alternativas para calcular los

valores iniciales de feromona:

i) valores aleatorios para i (0), i=1,…,Nr

ii) i (0)=1/Nr,

iii) i (0)= wA,D(ai), donde wA,D(ai) es el peso del rasgo ai de acuerdo a la RST, es

decir,

}{,

}{,1,

dA

daAaw i

idA

(2.3)

Donde (A,{d}) expresa el grado de dependencia entre el conjunto de atributos A y el

rasgo de decisión {d}.

e) Criterio de parada de una hormiga (Ant Stopping Criteria; ASC): El criterio de parada de

una hormiga establece la condición que indica cuando una hormiga termina su trabajo en

un ciclo. Esto se produce cuando el conjunto bk ya contiene los Nr rasgos o cuando se

alcanza un subconjunto de rasgos B con igual calidad de la aproximación de la clasificación

que el conjunto de todos los rasgos.


51

f) Criterio de parada del proceso (Process Stopping Criteria; PSC): Los algoritmos desarrollan

una secuencia de ciclos (NC=1, 2, ..., NCmax). En cada ciclo todas las hormigas construyen

un subconjunto de rasgos. El proceso termina cuando se alcanza el valor NCmax.

g) Tamaño de la población: en (Bello et al., 2012) derivaron las siguientes reglas que

permiten calcular el tamaño de la población en función de la cantidad de rasgos (m=f(n)),

las reglas establecidas son:

R1: If n19 then m = n;

R2: If 20n49 then

[If 2/3*n24 then m=24 else m = Round[2/3*n]]

R3: If n 50 then

[If [1/2 * n 33 then m = 33 else m = Round[1/2*n]]

donde Round[x] denota el valor entero más cercano a x.

Complejidad

Considerando que el costo de encontrar las aproximaciones inferior y superior es O(Nr*n2), donde

n es la cantidad de objetos, según (Bell and Guan, 1998) y (Deogun, 1998), la complejidad de los

algoritmos anteriores se puede estimar en O(NC*m*Nr2*n2), donde NC es la cantidad de ciclos. En

el caso en que la cantidad de hormigas sea similar a la cantidad de rasgos la complejidad es

O(NC*Nr3*n2).

En el algoritmo ACS-RST-FS se consideran las variables:

• m: cantidad de hormigas.

• n: número de atributos.

• i: el valor de feromona asociado al rasgo ai.

• NCmax: número máximo de ciclos.

• Bk: denota el subconjunto de rasgos B asociado con la hormiga k.


52

• ASC: Criterio de parada de las hormigas, es verdadero cuando el conjunto B ha sido

completado, es decir, el conjunto B tiene la misma calidad de la clasificación que A.

• PSC: Criterio de parada del proceso de búsqueda es verdadero si se alcanza la condición

de parada (número máximo de ciclos).

Algoritmo ACS-RST-FS:

PSC Falso

NC 1

Calcular i (0) i=1,.., na, (valores iniciales de la

feromona)

Repeat

P1: Estado inicial para cada ciclo.

La colonia de hormigas se distribuye en el espacio de

rasgos de acuerdo a las reglas en b).

Cada hormiga k se asocia al rasgo ai, k=1,…,m,

Set Bk {ai} de acuerdo a las reglas.

ASCk False, k=1,…,m.

P2: Repeat

for k=1 to m do

if ASCk = False then

Seleccionar el nuevo rasgo ai* a ser agregado a

Bk (Bk Bk {ai*}) de acuerdo expresión (2.1)

i (1-) * i + * i(0), donde ai* es el

rasgo más recientemente agregado (regla de

actualización local de la feromona)

Update ASCk. ¿Encontró la hormiga k un

reducto?

endIf

endFor

Until ASCk is True for all ants.


53

En (Bello et al., 2012) se realizó un estudio experimental para evaluar el algoritmo propuesto

previamente y analizar el comportamiento de los parámetros del modelo ACO. Para el mismo se

estudió el desempeño para diversas combinaciones de parámetros. Seguidamente se muestran los

resultados alcanzados, los cuales muestran la relevancia que tiene en el proceso de selección de

rasgos la asignación de los valores adecuados para algunos de los parámetros.

La relación clave es entre los parámetros y q0 se muestra en la Tabla 2.1 Relación de parámetros

para el algoritmo ACS-RST-FS.. La combinación (=1, q0=0.3) produce aproximadamente tres

veces más reductos que la combinación (=5, q0=0.9), independientemente de la cantidad de

hormigas (m) y el número de ciclos. Pero en el caso de la combinación (=5, q0=0.9) se obtienen

reductos más cortos.

Tabla 2.1 Relación de parámetros para el algoritmo ACS-RST-FS.

Parámetros m=9 m=15 m=24 m=33

=1, q0=0.3

58 104 143 175

=5, q0=0.9

30 33 45 56

2.3.3.3 Diseño e implementación

Dado que el propio diseño de la biblioteca incluye el paquete reducts, el cual tiene como finalidad

encapsular todos los reductos que se calculen en la Teoría de conjuntos aproximados,

P3: Cuando todas las hormigas han terminado en el ciclo:

Seleccionar el mejor subconjunto de rasgos Bk y

For each ai Bk do

i (1-) * i + * Bk(Y)

endFor

NC NC+ 1

Update PSC ¿Se alcanzó el número máximo de ciclos?

Until PSC is True.


54

procederemos a incorporar en el mismo las clases que permitan implementar el algoritmo ACS-

RST-FS. En la Figura 2.8 se muestran las clases para la implementación de dicho algoritmo.

La interfaz ACOinterfaz define el comportamiento de los algoritmos inspirados en ACO. La

principal función de la clase ACOabtract es SetAllAnts(), la cual se encarga de ubicar a las

hormigas.

La clase ACSabstract brinda la base para la clase ACSrstfs, cuyo método principal es Run(), como

tal este método ejecuta el algoritmo para el cálculo de reductos. Una vez que ejecutemos el

algoritmo ACS-RST-FS la clase ACSrstfs posee dos métodos para dar resultados: getAllReducts() y

getBestReduct(), el primero nos devuelve una lista con todos los reductos, cada reducto se

devuelve como un arreglo de atributos y el segundo nos da el mejor reducto (basado en el

tamaño, mientras menos atributos tenga el reducto, mejor es).

Figura 2.8 Clases del paquete reducts.

2.4 CONCLUSIONES PARCIALES DEL CAPÍTULO

En este capítulo se presentó el diseño de la biblioteca RST, la cual está desarrollada en Java, como

IDE se utilizó el NetBeans 6.8 ya que es un ambiente de programación cómodo, que compila en


55

tiempo real y fácil de usar para depurar un programa. Abordamos las principales características y

ventajas del lenguaje Java, argumentando de esta manera por qué su usó para el desarrollo de la

biblioteca.

La biblioteca RST logró incorporar los elementos de la teoría de conjuntos aproximados

identificados en el Capítulo 1 que permiten el desarrollo de algoritmos de aprendizaje

automatizado. Como resultado se obtuvo un paquete global y dentro de este los paquetes missing

y measures, los cuales cubren las extensiones para valores perdidos y la extensión basada en

relaciones de similaridad, respectivamente.

Finalmente se incorporó el algoritmo ACS-RST-FS para el cálculo de reductos, dicho algoritmo está

inspirado en la Optimización basada en colonias de hormigas.

Se verificó el funcionamiento de cada método de la biblioteca a partir de la aplicación de los

mismos a pequeños Sistemas de Información, para los cuales se conoce los valores a obtener en

cada caso.

56

3 UTILIZACIÓN DE LA BIBLIOTECA RST DESDE WEKA

En el presente capítulo se ilustra la factibilidad del uso de la biblioteca RST desde la incorporación

de métodos en el Weka. Particularmente presentaremos cómo implementar en Weka las medidas

para validar el agrupamiento basadas en la Teoría de Conjuntos Aproximados, utilizando la

biblioteca RST. Abordaremos sobre las generalidades de la herramienta para el Aprendizaje

Automatizado: Weka. Ofreceremos detaller de la implementación del paquete de validación del

agrupamiento en Weka.

3.1 MEDIDAS PARA LA VALIDACIÓN DEL AGRUPAMIENTO UTILIZANDO RST

En este epígrafe describiremos aquellas medidas definidas en (Arco, 2009) para evaluar resultados

de agrupamientos, así como el algoritmo que permite su utilización para tales efectos.

La validación del agrupamiento utilizando RST es no supervisada y permite que el cálculo común

inicial de las relaciones y aproximaciones inferiores y superiores pueda ser reutilizado por varias

medidas de calidad, inclusión y proximidad de conceptos.

Los objetos a agrupar están descritos por rasgos y constituyen el sistema de información que es el

punto de partida para aplicar RST. Cada grupo resultante de un proceso de agrupamiento al cual

dichos objetos son sometidos constituye un concepto Xi. En esta propuesta solo consideran

resultados de agrupamientos duros y deterministas, precisamente la mayoría de los métodos de

agrupamiento implementados en el Weka tienen esta clasificación. De ahí la importancia de

incorporar estas medidas para enriquecer el módulo de evaluación del agrupamiento del Weka.

Estas medidas de validación se basan en la Teoría de los Conjuntos Aproximados extendida,

utilizando relaciones de similaridad.

La propuesta de validación del agrupamiento utilizando RST (Arco, 2009) considera las medidas

clásicas de calidad y precisión de aproximaciones y de sistemas de decisión (1.24).

Adicionalmente, en (Arco, 2009) se presentan nuevas medidas que permiten caracterizar mejor

los resultados de los agrupamientos.

Capítulo 3: Utilización de la biblioteca RST desde Weka

57

Si bien las medidas calidad y precisión del agrupamiento (expresiones (1.32) y (1.33),

respectivamente) logran medir globalmente el nivel de inconsistencia, calidad y precisión de los

conceptos en un sistema de información dado, consideran que cada grupo tiene igual repercusión

en la evaluación. Sin embargo, no todos los grupos deben tener igual influencia al evaluar el

agrupamiento, en (Arco, 2009) se ponderan los mismos. Por tal motivo, se obtienen expresiones

generalizadas de precisión y calidad de la clasificación considerando la ponderación de los grupos

por su cardinalidad, calculando el peso wi asociado al grupo Xi como wi = │Xi│/│U│. En (Arco, 2009)

se propone la calidad y precisión generalizadas del agrupamiento, como se muestran en las

expresiones (3.1) y (3.2), respectivamente. El peso asociado a un grupo Xi se representa por wi,

cumpliéndose las restricciones wi0 y 11

k

i

iw .

U

wXRk

i

ii

G

1

* )('

(3.1)

k

i

ii

k

i

ii

G

wXR

wXR

1

*

1

*

)('

)('

(3.2)

Varios criterios pueden ser empleados para ponderar los grupos y así captar mejor las

propiedades deseadas; por ejemplo, similitud dentro del grupo, pertenencia de los objetos al

grupo y cardinalidad del grupo.

La media de la pertenencia aproximada de los objetos a cada grupo también puede ser empleada

para ponderar los grupos (Arco, 2009). Su expresión se muestra en (3.3).

i

XxiX

iX

x

w i

(3.3)


58

En (Arco, 2009) se propusieron dos nuevas medidas de pertenencia aproximada, descritas en las

expresiones (1.35) y (1.36). Las expresiones (3.4) y (3.5) muestran las variantes de ponderación

que se derivan de ellas, respectivamente.

A partir de los conceptos de RST a aplicar y las definidas, en (Arco, 2009) se propone un algoritmo

para guiar la aplicación de RST en la validación del agrupamiento. Las entradas a este algoritmo

son: la colección de objetos (sistema de información), el resultado del agrupamiento (conceptos),

la medida y umbral de similitud, y formas de ponderación de los grupos. Las salidas del algoritmo

son los valores de las medidas de precisión y calidad aplicadas a los grupos y al agrupamiento en

general.

Algoritmo. Aplicación de RST en la validación del agrupamiento.

1. Obtener las clases de similitud (1.17) para cada objeto en

el sistema de información.

2. Calcular las aproximaciones inferiores (1.19) y superiores

(1.20) por grupo.

3. Calcular calidad (1.24) y precisión (1.25) por grupo.

4. Calcular calidad (1.32) y precisión (1.33) del

agrupamiento.

5. Para cada variante de cálculo de peso especificada:

a. Calcular los pesos por grupos.

b. Calcular calidad (3.1) y precisión (3.2) generalizadas

del agrupamiento.

De esta forma es posible medir la vaguedad o imprecisión de cada grupo obtenido y del

agrupamiento en su totalidad. Si la región límite es pequeña, entonces se obtendrán mejores

i

XxiX

iX

x

w i

(3.4)

i

XxiX

iX

x

w i

(3.5)


59

resultados de las medidas utilizadas en la evaluación (valores cercanos a uno). Valores altos de las

medidas indican un mejor agrupamiento.

Los resultados de los pasos 1 y 2 del algoritmo son comunes para la aplicación posterior de

cualquier medida de validación basada en RST. En el cálculo de la complejidad temporal de estos

dos pasos interviene la complejidad de la medida de similitud que se emplee. En el cálculo de la

complejidad se considera: n número de objetos, m número de rasgos que describen dichos

objetos, y k número de grupos. La complejidad temporal del primer paso es O(mn2), la que está

dada por la obtención del conjunto de objetos relacionado con cada objeto. La complejidad

temporal del cálculo de las aproximaciones es O(kn2), ya que para el peor caso se considera que a

cada grupo pertenecen todos los objetos y cada objeto está relacionado con todos. Por tanto, la

complejidad de este procesamiento, previo al cálculo de las medidas basadas en RST, es O(wn2),

donde w = max{k, m} (Arco, 2009).

3.2 GENERALIDADES DE WEKA

Weka es un sistema multiplataforma y de amplio uso probado bajo sistemas operativos Linux,

Windows y Macintosh. Puede ser usado desde la perspectiva de usuario mediante las seis

interfaces que brinda, a través de la línea de comando desde donde se pueden invocar cada uno

de los algoritmos incluidos en la herramienta como programas individuales y mediante la creación

de un programa Java que llame a las funciones que se desee.

Weka (versión 3.5.2) dispone de seis interfaces de usuario diferentes que pueden ser accedidas

mediante la ventana de selección de interfaces (GUI Chooser), que constituye la interfaz de

usuario gráfica (GUI: Grafic User Interface):

Interfaz para línea de comando (Simple CLI: Command Line Interface): permite invocar

desde la línea de comandos cada uno de los algoritmos incluidos en Weka como

programas individuales. Los resultados se muestran únicamente en modo texto. A pesar

de ser en apariencia muy simple es extremadamente potente porque permite realizar

cualquier operación soportada por Weka de forma directa; no obstante, es muy

complicada de manejar ya que es necesario un conocimiento completo de la aplicación. Su

utilidad es pequeña desde que se fue recubriendo Weka con interfaces. Actualmente ya


60

prácticamente sólo es útil como una herramienta de ayuda a la fase de pruebas. Es muy

beneficiosa principalmente para los sistemas operativos que no proporcionan su propia

interfaz para línea de comandos.

Explorador (Explorer): interfaz de usuario gráfica para acceder a los algoritmos

implementados en la herramienta para realizar el aprendizaje automatizado. Es el modo

más usado y descriptivo. Permite realizar operaciones sobre un sólo archivo de datos.

Experimentador (Experimenter): facilita la realización de experimentos en lotes, incluso

con diferentes algoritmos y varios conjuntos de datos a la vez.

Flujo de conocimiento (KnowledgeFlow): proporciona una interfaz netamente gráfica para

el trabajo con los algoritmos centrales de Weka. Esencialmente tiene las mismas

funciones del Explorador aunque algunas de ellas aún no están disponibles. El usuario

puede seleccionar los componentes de Weka de una barra de herramientas, y conectarlos

juntos para formar un “flujo del conocimiento” que permitirá procesar y analizar datos.

Visualizador de Arff (ArffViewer): interfaz para la edición de ficheros con extensión arff.

Log: muestra la traza de la máquina virtual de acuerdo a la ejecución del programa.

3.2.1 Entrada de datos

Weka denomina instancia a cada uno de los casos proporcionados en el conjunto de datos de

entrada, cada una de las cuales posee propiedades o rasgos que la definen. Los rasgos presentes

en cada conjunto de datos son llamados atributos.

El formato de archivos con el que trabaja Weka es denominado arff, acrónimo de Attribute-

Relation File Format. Este formato está compuesto por una estructura claramente diferenciada en

tres partes:

Sección de encabezamiento: se define el nombre del conjunto de datos.

Sección de declaración de atributos: se declaran los atributos a utilizar especificando su tipo. Los

tipos aceptados por la herramienta son:


61

a) Numérico (Numeric): expresa números reales2

b) Entero (Integer): expresa números enteros

c) Fecha (Date): expresa fechas

d) Cadena (String): expresa cadenas de textos, con las restricciones del tipo String3

e) Enumerado: expresa entre llaves y separados por comas los posibles valores (caracteres o

cadenas de caracteres) que puede tomar el atributo.

Sección de datos: se declaran los datos que componen el conjunto de datos.

El formato por defecto de los ficheros que usa Weka es el arff, pero eso no significa que sea el

único que admita. Esta herramienta tiene intérpretes de otros formatos como CSV, que son

archivos separados por comas o tabuladores (la primera línea contiene los atributos) y C4.5 que

son archivos codificados según el formato C4.5, donde los datos se agrupan de tal manera que en

un fichero .names estarán los nombres de los atributos y en un fichero .data los datos en sí. Al leer

Weka ficheros codificados según el formato C4.5 asume que ambos ficheros (el de definición de

atributos y el de datos) están en el mismo directorio, por lo que sólo es necesario especificar uno

de los dos. Además, las instancias pueden leerse también de un URL (Uniform Resource Locator) o

de una base de datos en SQL usando JDBC.

3.2.2 Interioridades de Weka

Weka se implementa en Java, lenguaje de alto nivel ampliamente difundido y multiplataforma, lo

que posibilita que sistemas escritos en este lenguaje como Weka puedan ejecutarse en cualquier

plataforma sobre la que haya una máquina virtual Java disponible. Esta herramienta sigue los

preceptos del código abierto (open source), por lo su código fuente está totalmente disponible,

permitiendo la modificación del mismo. Solo es necesario recompilarlo para posteriormente

2 debido a que weka es un programa anglosajón la separación de la parte decimal y entera de los números reales se

realiza mediante un punto en vez de una coma.

3 entendiendo como tipo string el ofrecido por java.


62

agregar extensiones al sistema. Además es un software de distribución gratuita lo que posibilita su

uso, copia, estudio, modificación y redistribución sin restricciones de licencias.

Las clases de Weka están organizadas en paquetes. Un paquete es la agrupación de clases e

interfaces donde lo habitual es que las clases que lo formen estén relacionadas y se ubiquen en un

mismo directorio. Esta organización de la estructura de Weka hace que añadir, eliminar o

modificar elementos no sea una tarea compleja. Está formado por 10 paquetes globales, y dentro

de ellos se agrupan otros paquetes que aunque su contenido se ajusta al paquete padre ayudan a

organizar aún mejor la estructura de clases e interfaces.

Los paquetes globales son:

“associations”: contiene las clases que implementan los algoritmos de asociación.

“attributeSelection”: contiene las clases que implementan técnicas de selección de

atributos.

“classifiers”: agrupa todas las clases que implementan algoritmos de clasificación y estas a

su vez se organizan en subpaquetes de acuerdo al tipo de clasificador.

“clusterers”: contiene las clases que implementan algoritmos de agrupamiento.

“core”: paquete central que contiene las clases controladoras del sistema.

“datagenerators”: paquete que contiene clases útiles en la generación de conjuntos de

datos atendiendo al tipo de algoritmo que será usado.

“estimators”: clases que realizan estimaciones (generalmente probabilísticas) sobre los

datos.

“experiment”: contiene las clases controladoras relacionadas con el modo

Experimentador.

“filters”: está constituido por las clases que implementan algoritmos de

preprocesamiento.


63

“gui”: contiene todas las clases que implementan los paneles de interacción con el

usuario, agrupadas en subpaquetes correspondientes a cada una de las interfaces.

El paquete “core” constituye el centro del sistema Weka. Es usado en la mayoría de las clases

existentes. Las clases principales del paquete “core” son: Attribute, Instante, e Instances.

Mediante un objeto de la clase Attribute podremos representar un atributo. Su contenido es el

nombre, el tipo y en el caso de que sea un atributo nominal, los posibles valores.

Los métodos más usados de la clase Attribute son:

enumerateValues: retorna una enumeración de todos los valores de un atributo si es de

tipo nominal, cadena, o una relación de atributos, o valor nulo en otro caso.

index: retorna el índice de un atributo.

Los métodos isNominal, isNumeric, isRelationValued, isString, isDate retornan verdadero si el

atributo es del tipo especificado en el nombre del método.

name: retorna el nombre del atributo

numValues: retorna el número de valores del atributo. Si este no es nominal, cadena o

relación de valores retorna cero.

toString: retorna la descripción de un atributo de la misma manera en que puede ser

declarado en un archivo “.arff”.

value: retorna el valor de los atributos nominales o de cadena

La clase Instance se utiliza para manejar una instancia. Un objeto de esta clase contiene el valor

del atributo de la instancia en particular. Todos los valores (numérico, nominal o cadena) son

internamente almacenados como números en punto flotante. Si un atributo es nominal (o

cadena), se almacena el valor del índice del correspondiente valor nominal (o cadena), en la

definición del atributo. Se escoge esta representación a favor de la programación orientada a

objetos, incrementando la velocidad de procesamiento y reduciendo el consumo de memoria.


64

Esta clase es serializable por lo que los objetos pueden ser volcados directamente sobre un fichero

y también cargados de uno. En Java un objeto es serializable cuando su contenido (datos) y su

estructura se transforman en una secuencia de bytes al ser almacenado. Esto hace que los objetos

puedan ser enviados por algún flujo de datos con comodidad.

Un objeto de la clase Instances contiene un conjunto ordenado de instancias, lo que conforma un

conjunto de datos. Las instancias son almacenadas, al igual que la clase Instance, como números

reales, incluso las nominales, que como se explicó anteriormente, utilizando como índice la

declaración del atributo e indexándolas según este orden.

Los métodos más útiles de la clase Instance son:

• classAttribute: devuelve la clase de la que procede el atributo

• classValue: devuelve el valor de la clase del atributo

• value: devuelve el valor del atributo que ocupa una posición determinada

• enumerateAttributes: devuelve una enumeración de los atributos que contiene esa

instancia

• weight: devuelve el peso de una instancia en concreto

Los métodos más útiles de la clase Instances:

• numInstances: devuelve el número de instancias que contiene el conjunto de datos.

• instance: devuelve la instancia que ocupa la posición i.

• enumerateInstances: devuelve una enumeración de las instancias que posee el conjunto

de datos.

• attribute: existen dos métodos con este nombre, la diferencia es que uno recibe como

parámetro el índice del atributo, y el otro el nombre, ambos retornan el atributo.

• enumerateAttributes: retorna una enumeración de todos los atributos.


65

• numAttributes: retorna el número de atributos como un entero.

• attributeStats: calcula estadísticos de los valores un atributo especificado.

Una de las características más interesantes de Weka es la posibilidad de modificar su código y

obtener versiones adaptadas con funcionalidades que no contengan las versiones oficiales,

ampliando así sus posibilidades de uso. Desde el inicio se diseñó como una herramienta orientada

a la extensibilidad, por lo que se creó una estructura factible para ello. Sin embargo, cuando se

desean incorporar nuevos métodos al Weka y lograr que sean utilizados por toda la comunidad de

aprendizaje automatizado, no debemos modificar el código y así tener que recompilarlo, porque

de esta forma se limitará el uso de los métodos incorporados. Por tal motivo, Weka posee

módulos para la incorporación de nuevos paquetes sin la necesidad de modificar el código fuente.

De esta forma, se hace uso de la verdadera posibilidad de extensibilidad de Weka.

3.2.3 Validación del agrupamiento en Weka

Muchos de los algoritmos de clasificación supervisada disponibles en Weka antes de ser usados

necesitan especificar qué datos serán usados como conjunto de entrenamiento y como conjunto

de prueba. Estos son conjuntos disjuntos, el primero de ellos utilizado por los algoritmos de

Aprendizaje Automatizado supervisado para realizar el proceso de aprendizaje fijando sus

parámetros (ejemplo, los pesos de una RNA), mientras que los ejemplos del conjunto de prueba se

utilizan para medir el desempeño del algoritmo. Estos conjuntos se utilizan para la validación,

tanto de los métodos supervisados, como de los métodos no supervisados (aunque por supuesto

en estos últimos no se realiza un proceso de aprendizaje).

Weka implementa cuatro variantes para la validación:

• Usar los mismos datos como conjunto de entrenamiento y de prueba, conformado con

todas las instancias del archivo de datos (Use training set).

• Usar todas las instancias del conjunto de datos solamente como conjunto de

entrenamiento, y proporcionar como conjunto de prueba un nuevo archivo de datos

(Supplied test set).


66

• Realizar una validación cruzada estratificada con un número de particiones dado (Folds

Crossvalidation). La validación cruzada (Witten et al., 2011) parte de dividir los datos en n

partes. Luego, se forman n muestras diferentes tomando como conjunto de prueba una

de ellas, y como conjunto de entrenamiento las n−1 partes restantes. Se dice estratificada

porque cada una de las partes conserva las propiedades de la muestra original (porcentaje

de elementos de cada clase).

• Tomar un porcentaje del conjunto de datos como muestra de entrenamiento y lo restante

como muestra de prueba (Percentage split).

Los algoritmos de agrupamiento que se encuentran en el paquete weka.clusterers funcionan de

una manera similar a los métodos de clasificación en weka.classifiers, salvo que una validación

cruzada no se realiza de forma predeterminada si el archivo de prueba no se encuentra.

Si el agrupamiento se lleva a cabo mediante el modelado de la distribución probabilística de los

casos, es posible determinar lo bien que el modelo se ajusta a los datos mediante el cálculo de la

probabilidad de un conjunto de datos de prueba dado por el modelo. Weka mide la bondad de

ajuste por el logaritmo de la probabilidad, o log-likelihood: y mientras mayor sea el valor, mejor

será el modelo que se ajusta a los datos. En lugar de utilizar un único conjunto de prueba, también

es posible calcular una estimación de la validación cruzada de probabilidad logarítmica

Weka también da como salida cuántos casos son asignados a cada grupo. Para los algoritmos de

agrupamiento que no modelan la distribución probabilística de instancias, éstas son las únicas

estadísticas que da Weka. Es fácil saber qué grupos generan una distribución probabilística: ellos

son subclases de la clase weka.clusterers.DistributionClusterer.

Validación cruzada (cross-validation)

Cuando la cantidad de datos para el entrenamiento y las pruebas es limitada el método de

retención se reserva una cierta cantidad para la prueba y utiliza el resto para el entrenamiento (y

establece parte de eso a un lado para la validación, si es necesario). Es común mantener una

tercera parte de los datos para prueba y utilizar las restantes dos terceras partes para el

entrenamiento.


67

Puede ocurrir que la muestra utilizada para el entrenamiento (o de prueba) podría no ser

representativa. En general, no se puede saber si una muestra es representativa o no. Pero hay una

sencilla comprobación que pueda ser útil: Cada clase en el conjunto de datos debe estar

representada aproximadamente por la proporción adecuada entre los conjuntos de

entrenamiento y prueba. Si todos los ejemplos con una determinada clase fueron omitidos en el

conjunto de entrenamiento, difícilmente se podría esperar que lo aprendido de esos datos

pudieran realizar un buen modelado de los ejemplos de esta clase y la situación se agravaría por el

hecho de que la clase podría ser sobre-representada en la prueba debido a que ninguna de sus

instancias lo hizo en el conjunto de entrenamiento. Debe asegurarse de que la toma aleatoria de

muestras, se realice de una manera que garantiza que cada clase se representa correctamente en

los conjuntos de entrenamiento y prueba. Este procedimiento se llama estratificación, y se podría

hablar de retención estratificada. Es de importancia señalar que la estratificación sólo proporciona

una salvaguardia contra la representación primitiva y desigual en la formación de los conjuntos de

prueba y entrenamiento.

Una forma más general para mitigar cualquier margen de error causado por la muestra elegida en

particular es repetir todo el proceso, el entrenamiento y las pruebas, varias veces con diferentes

muestras aleatorias. En cada iteración una cierta proporción, por ejemplo las dos terceras partes,

de los datos se seleccionaron al azar para la formación, posiblemente con estratificación y el resto

se utiliza para la prueba. Las tasas de error en las diferentes iteraciones se promedian para

producir una tasa de error global. Este es el método de estimación de retención repetida de la

tasa de error.

3.3 PAQUETE PARA VALIDAR AGRUPAMIENTOS EN WEKA UTILIZANDO RST

El objetivo de este epígrafe consiste en ilustrar el uso de la biblioteca RTS mediante la creación de

un paquete cuyo propósito incorporar la validación del agrupamiento basado en RST al Weka.

Para lograr lo antes descrito fue necesario la creación de dos clases: RSTEvaluation.java y

ClustererAndEvaluationPanel.java. Estas clases se encapsularon en un paquete, la primera se le

incorporará al Weka en el paquete weka.clusterers y la segunda en el paquete weka.gui.explorer.

La estructura del paquete, para incorporar al Weka dichas clases, se presenta en la Figura 3.1.


68

Figura 3.1 Estructura del paquete a incorporar.

La clase RSTEvaluation.java es la encargada de guiar la aplicación de RST en la validación del

agrupamiento. Sus métodos principales son: evaluateClusterer(), setRoughSet() y

printClusterStats(). El método evaluateClusterer() tiene como función agregar a un conjunto de

instancias un nuevo atributo, dicho atributo es el grupo al cual pertenece la instancia, este recibe

como parámetros un conjunto de instancias, un arreglo el cual contiene el grupo al que pertenece

cada instancia y la cantidad de grupos. El método setRoughSet() recibe una instanciación de la

clase RoughSet, la cual contiene los elementos y medidas necesarias de RST para la validación del

agrupamiento. El método printClusterStats(), retorna una cadena de caracteres con la salida del

algoritmo para la aplicación de RST en la validación del agrupamiento.

Para visualizar y guiar el uso de la clase RSTEvaluation.java fue necesario agregar una nueva

pestaña al Explorer del Weka. Con esta finalidad se creó la clase ClustererAndEvaluationPanel.java.

En el sitio web http://weka.wikispaces.com/ se ilustra la metodología para agregar una nueva

pestaña al Explorer del Weka (esto es posible a partir de la versión 3.5.5) la cual describiremos a

continuación:

1. La clase tiene que heredar de javax.swing.JPanel.


69

2. La clase tiene que implementar la interfaz weka.gui.explorer.Explorer.ExplorerPanel.

3. Agregar el nombre de la clase a las propiedades de las pestañas, las cuales se encuentran

en el archivo Explorer.props.

Esta nueva “componente” mantiene la misma estructura funcional y visual que la pestaña

Clusterer, pero se le agregaron nuevas funcionalidades. Se le da la opción al usuario para que este

decida si quiere validar o no el agrupamiento con las medidas ofrecidas por RST. En caso que

decida validar el agrupamiento con RST, se le ofrecen varias extensiones de la teoría: la teoría

clásica, tres relaciones para valores omitidos y una extensión basada en relaciones de similaridad

la cual ofrece varias medidas de comparación entre objetos. Si la extensión seleccionada es

basada en relaciones de similaridad, el usuario decide si aplicar una función para el cálculo del

umbral de similitud o si lo desea pasar por parámetro.

Internamente esta clase mantiene en una primera etapa las mismas funciones de la pestaña

Clusterer, si el usuario decide validar con RST, se procede a crear un objeto de la clase

RSTEvaluation.java, se conforman las nuevas instancias a partir de los resultados obtenidos por el

método de agrupamiento (llamada al método evaluateClusterer() de la clase RSTEvaluation.java),

se conforma la extensión a usar de RST (dicho objeto, el cual es una instancia de la clase

RoughSet.java, se le pasa por parámetro RSTEvaluation.java mediante el método setRoughSet()) y

se procede a validar el agrupamiento (esto se hace mediante una llamada al método

printClusterStats() de la clase RSTEvaluation.java).

La pestaña incorporada al Weka a partir del nuevo paquete creado se muestra en la Figura 3.2.


70

Figura 3.2 Nueva pestaña agregada al Weka.

3.4 CONCLUSIONES PARCIALES DEL CAPÍTULO

Con la incorporación del nuevo paquete, el cual contiene las clases RSTEvaluation.java y

ClustererAndEvaluationPanel.java, se logró ilustrar el uso de la biblioteca RST, mediante la

aplicación de un algoritmo, el cual guía la aplicación de las medidas internas ofrecidas por la

Teoría de conjuntos aproximados para la validación del agrupamiento.

71

CONCLUSIONES Y RECOMENDACIONES

Como resultado de este trabajo de diploma se implementó una biblioteca en Java que logró

encapsular los elementos de la Teoría de los Conjuntos Aproximados aplicables en varios

métodos de Aprendizaje Automatizado, cumpliéndose de esta forma el objetivo general

planteado, ya que:

La definición de los sistemas de información y decisión, las relaciones entre objetos tanto

las de equivalencia, las basadas en similaridad, como las relaciones para sistemas de

información incompletos, y los consecuentes cálculos de las aproximaciones inferiores y

superiores, así como las medidas de inferencia, son los elementos que esencialmente

utilizan los métodos de aprendizaje automatizado que utilizan RST. Adicionalmente, el

cálculo de reductos es muy utilizado en métodos de aprendizaje automatizado.

La biblioteca RST implementada en Java consta de paquetes que manejan las relaciones

de equivalencia, las relaciones con presencia de valores ausentes, las relaciones de

similitud, permite el cálculo de reductos utilizando la metaheurística ACO, permite la

incorporación de varias distancias y medidas de similitud y tiene un diseño extensible

permitiendo la incorporación de otros elementos de RST.

Se creó el paquete en Weka y se agregó una nueva pestaña que ilustran el uso de la

biblioteca RST, mediante la aplicación de un algoritmo, el cual guía la aplicación de las

medidas internas ofrecidas por la Teoría de conjuntos aproximados para la validación del

agrupamiento.

Teniendo en consideración que el Weka es extensible se recomienda:

Incorporar nuevas medidas de similitud entre objetos y de semejanza entre rasgos.

Crear nuevos paquetes en Weka que incluyan métodos de aprendizaje automatizado

basados en RST.

72

REFERENCIAS BIBLIOGRÁFICAS

ALWANG, G., CLYMAN, J., DRAGAN, R. V. & SELTZER, L. (1998) Java Guide. PC Magazine, 17, 101-

209.

ARBOLÁEZ, A. (2008) Extensiones al ambiente de aprendizaje automatizado Weka-parallel con

distintos algoritmos de aprendizaje en redes bayesianas. Aplicaciones Bioinformáticas. .

Trabajo de diploma en Ciencia de la Computación. .

ARCO, L. (2009) Agrupamiento basado en la intermediación diferencial y su valoración utilizando

la teoría de los conjuntos aproximados. . Tesis de doctorado en Ciencias Técnicas. .

BARBARA, D. (1992) The management of probabilistic data. IEEE Trans. of Knowledge and Data

Engineering.

BARRIENTOS, H. (2009) Java para todos.

BELL, D. & GUAN, J. (1998) Computational methods for rough classification and discovery. Journal

of ASIS, 49.

BELLO, M. (2012) Un método de aproximación de funciones basado en el enfoque de los

prototipos más cercanos utilizando relaciones de similaridad. Trabajo de diploma en

Ciencia de la Computación.

BELLO, R. (2005a) A Model based on Ant System Colony and Rough Set Theory to Feature

Selection. Proceedings of Genetic and Evolutionary Computation Conference(GECCO05).

BELLO, R. (2005b) Using ACO and Rough Set Theory for Feature Selection. WSEAS Transactions on

Information Science and Applications.

BELLO, R. (2005c) Using Ant colony System meta-heuristic and Rough Set Theory to Feature

Selection. Proceeding of The 6th Metaheuristics International Conference (MIC2005).

BELLO, R., GARCÍA, M. M. & PÉREZ, J. N. (2012) Teoría de los conjuntos aproximados: conceptos y

métodos computacionales, Bogotá.

BONET, I. (2009) Modelo para la clasificación de secuencias, en problemas de la Bioinformática,

usando técnicas de Inteligencia Artificial. Tesis de doctorado en Ciencias Técnicas.

Referencias bibliográficas

73

CABALLERO, Y. (2008) Aplicación de la Teoría de los conjuntos aproximados en el

preprocesamiento de los conjuntos de entrenamiento para los algoritmos de aprendizaje

automatizado. . Tesis de doctorado en Ciencias Técnicas.

CARBONELL, E. (2010) Extensiones al ambiente de aprendizaje automatizado Weka para datos de

alta dimensión. Trabajo de diploma en Ciencia de la Computación. .

CASTELLANOS, M. (2008) Extensiones al módulo de validación del agrupamiento en Weka y su

evaluación. Trabajo de diploma en Ciencia de la Computación.

CHÁVEZ, M. C. (2009) Modelos de redes bayesianas en el estudio de secuencias genómicas y otros

problemas biomédicos. . Tesis de doctorado en Ciencias Técnicas.

DEOGUN, J. S. (1998) Feature selection and effective classifiers. Journal of ASIS, 49.

DEVLIN, K. J. (1993) The Joy of Sets. Springer-Verlag, p. 1-7.

DORIGO, M. (2007) Ant Colony Optimization.

FILIBERTO, Y. (2011) Métodos de aprendizaje para dominios con datos mezclados basados en la

teoría de los conjuntos aproximados extendida. Tesis de doctorado en Ciencias Técnicas.

FOUNDATION, A. S. (2013) http://ant.apache.org. .

FOWLER, M. & & SCOTT, K. (Eds.) (1997) UML Distilled, Massachusetts, E.U.A, Addison Wesley

Longman.

GARCÍA, M. M. (1999) Monografía de reconocimiento de patrones. Santa Clara, Villa Clara,

Universidad Central "Marta Abreu" de Las Villas.

GÓMEZ, Y. (2010) Algoritmos que combinan conjuntos aproximados y optimización basada en

colonias de hormigas para la selección de rasgos. Extensión a múltiples fuentes de datos. .

Tesis de doctorado en Ciencias Técnicas.

GONZÁLEZ, F. F. (2011) Feature selection in cancer research.

GONZÁLEZ, M. (2010) Extensión de algoritmos representativos del aprendizaje automático al

trabajo con datos tipo conjunto. . Tesis de Maestría en Ciencia de la Computación.

GRECO, S. (2001) Rough sets theory for multicriteria decision analysis. European Journal of

Operational Research.

GRZYMALA-BUSSE, J. W. (1991) On the unknow attributes values in learning from examples.

GUEVARA, L. E. (2007) Extensión del sistema Weka con la incorporación de Redes Neuronales

Recurrentes. . Trabajo de diploma en Ciencia de la Computación. .

http://ant.apache.org/

Referencias bibliográficas

74

JENSEN, R. & SHEN, Q. (2003) Finding rough set reducts with ant colony optimization. Proceeding

of UK Workshop on Computational Intelligence.

MAGDALENO, D. (2008) Refinamiento, evaluación y etiquetamiento de grupos textuales basados

en la teoría de conjuntos aproximados. Tesis de Master en Ciencia de la Computación.

MATÍAS, H. & L.I.ARAUJO (2006) Extensiones al ambiente de aprendizaje automatizado Weka.

Trabajo de diploma en Ciencia de la Computación.

MITCHEL, T. M. (1997) Machine learning.

MORELL, C., RODRÍGUEZ, Y., MATÍAS, H. & ARAUJO, L. I. (2006) Una metodología para extender el

ambiente de aprendizaje automatizado Weka. Informe de investigación terminada.

PAWLAK, Z. (1991) Rough Sets: Theoretical Aspects of Reasoning about Data, Dordrecht, Academic

Publishers.

RODRÍGUEZ, Y. (2009) Generalización de la métrica basada en la diferencia de valores (VDM) para

variables lingüísticas y su aplicación en sistemas basados en el conocimiento. . Tesis de

doctorado en Ciencias Técnicas.

SCHILDT, H. (2001) Java 2: The Complete Reference. McGraw-Hill.

SLOWINSKI, R. & VANDERPOOTEN, D. (2000) A generalized definition of rough approximations

based on similarity. IEEE Transactions on Data and Knowledge Engineering.

WIKIPEDIA (2013) Plataforma Java.

WITTEN, I. H., FRANK, E. & HALL, M. A. (2011) Data Mining: Practical Machine Learning Tools and

Techniques. IN THIRD (Ed., Morgan Kaufmann.

75

ANEXOS

ANEXO 1. TRANSFORMACIONES DE DISTANCIAS A SIMILITUDES

Distancia: Sea X un conjunto, una función d: X x X es llamada distancia en X si para todo x,y

X se cumple:

1. d(x, y) (no negatividad);

2. d(x, y) = d(y, x) (simétrica);

3. d(x, x) = 0.

Similaridad (Similitud): Sea X un conjunto, una función s: X x X es llamada similaridad en X si

es:

1. No negativa

2. Simétrica

3. s(x, y) < s(x, x) para todo x,y X, con igualdad si y solo si x = y.

Las principales transformaciones usadas para obtener una distancia de una similitud son:

d = 1 - s

d = (1 – s)/s

sd 1

)1(2 2sd

d = -ln s

d = arcos s

Anexos

76

ANEXO 2. DISTANCIAS, SIMILITUDES Y DISIMILITUDES MÁS USADAS PARA COMPARAR

OBJETOS

(Arco, 2009) propone las siguientes funciones de distancias:

Sean los objetos Oi y Oj descritos por m rasgos, donde Oi=(oi1, …, oim) y Oj=(oj1, …, ojm)

Distancia Euclidiana

m

k

jkikjiEuclideana ooOOD1

2, (A2.1)

Distancia Minkowski

1

1

,

m

k

jkikjiMinkowski ooOOD donde 1 (A2.2)

La distancia Minkowsky es equivalente a la distancia Manhattan o city-block, y a la distancia

Euclidiana cuando es 1 y 2, respectivamente. Para los valores de 2, la distancia Minkowsky

equivale a Supermum.

Distancia Euclidiana heterogénea (Heterogenous Euclidean – Overlap Metric; HEOM)

m

k

jkiklocaljiHEOM oodOOD1

2,, , donde

numéricoksiood

simbólicoksioodood

jkikeanNormEuclid

jkikOverlap

jkiklocal,

,,

casootroen

oosiood

jkik

jkikOverlap,1

,0, y

kk

jkik

jkikeanNormEuclid

ooood

minmax,

(A2.3)

Distancia Camberra

m

k jkik

jkik

jiCamberraoo

ooOOD

1

, (A2.4)

Correlación de Pearson

Anexos

77

m

k

kjk

m

k

kik

m

k

kjkkik

jiPearson

atributooatributoo

atributooatributoo

OOD

1

2

1

2

1, (A2.5)

donde katributo es el valor promedio que toma el atributok en el conjunto de datos.

Las expresiones de Chebychev, Mahalanobis, distancia de Hamming y la máxima distancia son

otras variantes de cálculo de distancias entre objetos.

Similitudes propuestas en (Arco, 2009):

Coeficiente Dice

m

k

jk

m

k

ik

m

k

jkik

jiDice

oo

oo

OOS

1

2

1

2

1

2

, (A2.6)

Coeficiente de Jaccard

m

k

jkik

m

k

jk

m

k

ik

m

k

jkik

jiJaccad

oooo

oo

OOS

11

2

1

2

1, (A2.7)

Coeficiente Coseno

m

k

jk

m

k

ik

m

k

jkik

jiCoseno

oo

oo

OOS

1

2

1

2

1, (A2.8)

Anexos

78

ANEXO 3. ALGUNAS VARIANTES PARA EL CÁLCULO DEL UMBRAL DE SIMILITUD ENTRE

OBJETOS

Algunas expresiones para el cálculo inicial del umbral (García, 1999):

a) La media de las similitudes entre todos los pares de objetos posibles; expresión (A3.1):

1

1 1

),()1(

2 n

i

n

ij

ji OOsnn

X (A3.1)

b) La media de los valores máximos de las similitudes entre cualquier par de objetos; expresión

(A3.2):

n

i

ji

jinj

OOsn

X1

..1max ),(max

1

(A3.2)

c) La media de los valores mínimos de las similitudes entre cualquier par de objetos; expresión

(A3.3):

n

i

ji

jinj

OOsn

X1

..1min ),(min

1

(A3.3)

d) La media ponderada de la media de las similitudes y la media de los máximos; expresión

(A3.4):

max)1( XXX w (A3.4)

La descripción de la notación utilizada es la siguiente: n es la cantidad de objetos de la colección,

ji OOs , es el valor de la similitud entre los vectores Oi y Oj, y es un valor entre 0 y 1 que

permite ponderar la media y la media de los máximos en la expresión (A3.4).

biblioteca en java para la aplicación de los conjuntos

Documents