E.T.S.

de Ingeniera Industrial,
Informtica y de Telecomunicacin

Aprendizaje de distancias basadas en

disimilitudes para el algoritmo de
clasificacin kNN

Grado en Ingeniera Informtica

Trabajo Fin de Grado

Mikel Xabier Uriz Martin
Mikel Galar Idoate
Pamplona, 26 de enero de 2015

RESUMEN

El objetivo de este proyecto es el de tratar de mejorar el algoritmo KNN (k

vecinos ms cercanos) sustituyendo la distancia Euclidea clsica por disimilitudes
parametrizadas que sern ajustadas utilizando un algoritmo gentico. La idea es que el
algoritmo gentico aprenda diferentes parmetros para luego calcular las distancias
entre instancias utilizando esos parmetros, en vez de utilizar otras distancias clsicas
como la Euclidea.
Tambin consideramos la opcin de poder realizar la seleccin de instancias y
de atributos, de esta manera, el algoritmo gentico podr excluir las instancias que
sean ruido. Al utilizar esta tcnica se acelerara el clculo de las distancias, ya que al
disminuir el nmero de instancias y de atributos, se requieren menos clculos a la hora
de calcular las distancias.
Al final, realizaremos una comparativa con las diversas variantes que se puedan
dar y el algoritmo KNN original, para ver si existe mejora a la hora de clasificar.

Palabras clave: k-vecinos ms cercanos, disimilitudes, algoritmos genticos,

clasificacin.

ndice
1.

2.

3.

4.

5.

Introduccin .............................................................................................................. 4
1.1.

Sistemas de clasificacin .................................................................................... 4

1.2.

Algoritmo de los K vecinos ms cercanos .......................................................... 4

1.3.

Algoritmos genticos ......................................................................................... 5

1.4.

Objetivos ............................................................................................................ 5

Tcnicas utilizadas ..................................................................................................... 6

2.1.

Medidas de disimilitud....................................................................................... 6

2.2.

Algoritmo KNN ................................................................................................... 7

2.3.

Algoritmos genticos ......................................................................................... 9

2.4.

Algoritmo CHC .................................................................................................. 12

Propuestas ............................................................................................................... 14
3.1.

Algoritmo KNN con medidas de disimilitud ..................................................... 14

3.2.

Algoritmo gentico .......................................................................................... 15

3.3.

Seleccin de instancias. ................................................................................... 16

3.4.

Seleccin de caractersticas ............................................................................. 17

3.5.

Modelo completo ............................................................................................ 18

Marco experimental ................................................................................................ 21

4.1.

Mtodos en la comparativa ............................................................................. 21

4.2.

Datasets ........................................................................................................... 22

4.3.

Configuracin de parmetros para cada mtodo............................................ 24

4.4.

Test estadsticos y evaluacin .......................................................................... 26

Estudio experimental .............................................................................................. 27

5.1.

Introduccin y objetivos .................................................................................. 27

5.2.

Resultados ........................................................................................................ 27

5.3.

Test estadsticos ............................................................................................... 39

6.

Conclusiones y lneas futuras .................................................................................. 43

7.

Bibliografa .............................................................................................................. 44

1. Introduccion
Este proyecto consiste en desarrollar un sistema de clasificacin basado en el
algoritmo de los k vecinos ms cercanos. Ms concretamente, tratamos de aprender
diferentes parmetros para la fase de clculo de distancias del algoritmo de los k
vecinos ms cercanos donde introducimos el uso de disimilitudes.

1.1. Sistemas de clasificacin

Un sistema de clasificacin trata de clasificar en diferentes clases o categoras
una serie de ejemplos o instancias que representan cierta informacin de un
problema. En el mbito del aprendizaje automtico, el objetivo de estos sistemas es
aprender a decidir cul es la clase a la que pertenecen los ejemplos nuevos sin
etiquetar. Existen dos tipos clasificacin:
-

Clasificacin supervisada: En este tipo de clasificacin, se tiene un conjunto de

datos de los cuales ya sabemos su clasificacin, llamados instancias de
entrenamiento o conjunto de entrenamiento. Utilizando dichos ejemplos
hacemos que el sistema aprenda ciertos parmetros los cuales sern
utilizados para clasificar nuevas instancias.
Clasificacin no supervisada: En este tipo de clasificacin no se tiene un
conjunto de datos de los cuales se sabe la clase. En este caso el sistema aparte
de clasificar tiene que establecer las clases.

1.2.

Algoritmo de los K vecinos ms cercanos

El algoritmo los K vecinos ms cercanos (KNN) es un algoritmo de clasificacin

supervisada. Este algoritmo trata de clasificar el ejemplo utilizando un conjunto de
datos de los cuales ya se conoce su clase. Primero calcula la distancia entre el ejemplo
que se quiere clasificar y todos los elementos del conjunto y selecciona los K ejemplos
con menor distancia. La clase para el ejemplo que se quiere clasificar ser la clase que
ms se repita en esos K ejemplos.

1.3.

Algoritmos genticos

Los algoritmos genticos son algoritmos que realizan bsquedas basadas en

heursticas que imitan el proceso de seleccin natural. El objetivo de estos algoritmos
es buscar una solucin para problemas de optimizacin y bsqueda.
Los algoritmos genticos utilizan una poblacin que son los candidatos a la
solucin. Cada candidato es un cromosoma que est compuesto por genes, que
codifican los parmetros que se quieren aprender. Estos candidatos van
evolucionando y en cada generacin van quedando los que mejor se adaptan, es decir,
los que ms se aproximan a la mejor solucin en base a la funcin objetivo establecida.
Primero se evala cada candidato y se obtiene una puntuacin relacionada con
la bondad de esa solucin. Cuanto mayor sea esta puntuacin mayor ser la
probabilidad de reproduccin de este individuo. Cuando dos individuos se cruzan se
obtienen descendientes que comparten caractersticas (genes) de los padres. Si algn
individuo no consigue adaptarse bien, su probabilidad de reproduccin ser menor. De
esta manera, generacin a generacin se van consiguiendo individuos que se adaptan
mejor, es decir, se van encontrando mejores soluciones al problema dado.

1.4.

Objetivos

El objetivo de este proyecto es el de utilizar un algoritmo gentico para

aprender diferentes parmetros que se utilizaran para calcular las distancias entre los
ejemplos en el algoritmo de los K vecinos ms cercanos. La distancia es calculada
utilizando medidas de disimilitud restringidas, que miden lo distintos que son dos
ejemplos. De esta manera tratamos de mejorar al algoritmo original de los K vecinos
ms cercanos, y a algunas de sus variantes.

2. Tcnicas utilizadas
2.1.

Medidas de disimilitud

Estas medidas son las que utilizaremos para calcular la distancia entre
ejemplos. Las medidas de disimilitudes pueden construirse por medio de unas
funciones llamadas automorfismos. Estas funciones las representamos con el smbolo
y son funciones continuas y estrictamente crecientes. La definicin de la funcin es
la siguiente: : [, ] [, ] donde () = y () = siendo [, ] .
En este proyecto trabajamos con nmeros reales entre 0 y 1, por lo tanto
nuestro valor de sera 0 y el de 1.
Por otra parte, la funcin de automorfismo que hemos elegido es () = ,
siendo un nmero real en el rango (0, ). Como se puede observar, esta funcin
cumple las condiciones: (0) = 0 = 0 y (1) = 1 = 1.
La distancia que utilizamos se basa en medidas de disimilitud restringidas. Estas
funciones tienen que cumplir las siguientes propiedades:
1)
2)
3)
4)

(, ) = (, ) , [0,1]
(, ) = 1 = 0 = 1 = 1 = 0
(, ) = 0 =
, , [0,1], (, )
(, ) (, ) (, )

Las medidas de disimilitud restringidas se construyen a partir de dos

automorfismos 1 y 2 en el intervalo [0,1]. La distancia que tenemos es (, ) =
11 (|2 () 2 ()|) que devuelve un nmero real entre 0 y 1 que indica lo
diferente que son los elementos, siendo 1 que son totalmente diferentes y 0 que son el
mismo.
Utilizando los automorfismos citados, la funcin de distancia que obtenemos es
(, ) = (| 2 2 |)

1
1

. Ya que el primero automorfismo es la inversa de la

funcin () = se obtiene que 1 () =

= . Con esto se puede definir la

funcin de la distancia como (, ) = | 2 2 | .

Esta funcin de distancia se aplica entre dos nmeros, y normalmente los
ejemplos vienen definidos por varios valores en forma de vector, por lo tanto podemos
calcular la distancia entre los elementos del vector, pero no la distancia entre dos
6

ejemplos. Para calcular la distancia general, tenemos que agregar los resultados. Para
ello definimos una funcin : ()() [0,1] donde se cumple:
1) (, ) = (, ) , ()
2) (, ) = 0 =
3) (, ) =
1
4) (, ) ( , )
Definimos la funcin de agregacin : [0,1] [0,1] y que cumple:
1) (1 , , ) = 0 1 = = = 0
2) (1 , , ) = 1 1 = = = 1
3)
Finalmente obtenemos la siguiente funcin de disimilitud:

(, ) = =1
( , )

En nuestro caso hemos elegido la media aritmtica como funcin de

agregacin. Uniendo todas las funciones, la funcin de disimilitud resultante es:

=1

=1

1
1
1
2
2
(, ) = ( , ) = [ | |]

2.2.

Algoritmo KNN

Como ya se ha dicho, el algoritmo de los K vecinos ms cercanos es un

algoritmo de clasificacin supervisada. Es un algoritmo muy fcil de entender e
implementar y que funciona bien en varios casos. Dado un conjunto de entrenamiento
y un ejemplo para clasificar, el algoritmo devuelve la clase mayoritaria de los K
ejemplos ms cercanos.
A diferencia de otros algoritmos que utilizando el conjunto de entrenamiento
aprenden algunos parmetros y luego utilizando estos ltimos clasifican la nueva
instancia, el algoritmo KNN clasifica la nueva instancia utilizando el conjunto de
entrenamiento sin necesidad de aprender ningn parmetro. El algoritmo de KNN es el
siguiente:

ALGORITMO 1
ENTRADA: D, el conjunto de entrenamiento, el elemento para test, z, que es el vector a clasificar, y L, el
conjunto de clases.
SALIDA: cz L, la clase de z
para cada objeto y D hacer
Calcular d(z, y), la distancia entre z e y;
fin
Seleccionar N D, los k elementos ms cercanos a z dentro del conjunto de entrenamiento;
=

( = ( )) ;

donde I () es una funcin que devuelve 1 si el argumento es cierto, 0 en otro caso.

El algoritmo recibe un conjunto de entrenamiento, una instancia a clasificar y

un vector que contiene las diferentes clases del conjunto. Por cada instancia del
conjunto de entrenamiento, se calcula la distancia entre esa instancia y la instancia
que se quiere clasificar. Una vez que tenemos todas las distancias calculadas,
seleccionamos las k con menor distancia. Para terminar agregamos los resultados
obtenidos en las distancias de las k instancias seleccionadas para obtener una
prediccin de la clase final.
Una de las cosas a tener en cuenta es el valor de k, es decir, el nmero de
vecinos a tener en cuenta para clasificar la nueva instancia. Si el valor es muy pequeo,
entonces el resultado puede ser sensible a instancias que son ruido. Si el valor es muy
alto, dentro de los k ms cercanos podemos incluir instancias que son de otra clase.
Esto se puede ver en la siguiente figura:

Figura 1. Diferentes tipos de vecindarios segn el valor de k.

Otra cosa que hay que tener en cuenta es como realizar la agregacin final. Una
de la forma de hacerlo es por el mtodo del voto. Cada una de las k instancias
seleccionadas vota por la clase a la que pertenece y la clase mayoritaria es la que se le
asigna a la instancia a clasificar. Otra forma de hacer la agregacin es a travs del voto
ponderado. Cada una de las k instancias vota por la clase a la que pertenece pero con
8

un peso. Este peso podra depender de la distancia que hay entre l y la instancia a
clasificar, cuanto menos distancia mayor ser el peso del voto. En el caso de este
proyecto aplicaremos el voto sin ponderar.
Por ltimo, otra de las cosas que hay que seleccionar en este algoritmo es la
distancia. Normalmente se aplica la distancia Euclidea o la de Manhattan, aunque hay
otro tipo de distancias que se pueden aplicar. En este caso emplearemos las distancias
creadas mediante disimilitudes explicadas en el apartado anterior.

2.3.

Algoritmos genticos

Como ya se ha explicado en la seccin 1.3., los algoritmos genticos imitan la

evolucin natural. Una poblacin inicial va evolucionando y obteniendo mejores
resultados cruzando individuos de la poblacin y/o mutndolos. Cada individuo,
tambin llamado cromosoma, se representa como una cadena de valores, donde cada
elemento se llama gen, y cada uno de estos genes hace referencia a un parmetro que
se quiere ajustar. El esquema de un algoritmo gentico es el siguiente:

Figura 2. Esquema general de un algoritmo gentico.

Primero iniciamos una poblacin aleatoriamente, dando un valor aleatorio a

cada gen de cada cromosoma. Una vez que tenemos la poblacin, evaluamos cada
cromosoma. En este punto ya tenemos como de bueno es cada individuo. Si esta
9

poblacin satisface la condicin de parada (que se supere el nmero de iteraciones,

que se encuentre la solucin ptima,) devolvemos el mejor cromosoma. Si no
satisface esa condicin, seleccionamos los progenitores y se realiza la reproduccin,
cruzando los progenitores y si se da el caso, se mutan alguno de los genes de los
descendientes que se crean. Una vez que tenemos los descendientes, los evaluamos y
seleccionamos los mejores cromosomas (de la poblacin anterior y los descendientes
creados) sin superar el tamao de la poblacin anterior. Se vuelve a comprobar la
condicin de parada y si se satisface se devuelve el mejor cromosoma. Si no, se repiten
de nuevo estos pasos. La poblacin que se genera generacin tras generacin, siempre
ser mejor o igual a la anterior, ya cada generacin nos quedamos con los mejores.
En este algoritmo, hay que tener en cuenta los siguientes aspectos:
-

Representacin: Lo primero que tenemos que decidir es como vamos a

representar el cromosoma. Tenemos que decidir el nmero de genes y tipo de
cada gen. Por ejemplo, el problema del viajante tendremos tantos genes como
destinos tengamos y cada uno de estos genes ser un nmero entero que
represente cada destino. Otro tipo de representacin podra ser un numero
binario (0 o 1) por gen, donde cada gen representa cada uno de los ejemplos
del conjunto de entrenamiento y 1 significa que si utilizamos ese ejemplo para
clasificar y un 0 que no (seleccin de instancias).
Funcin de evaluacin: Es la funcin que se utiliza para calcular lo bueno que
es cada uno de los cromosomas de la poblacin. El valor que devuelve esta
funcin se llama fitness. Si el problema es de maximizacin, cuanto mayor sea
el fitness mejor es el cromosoma, al contrario que en un problema de
minimizacin, cuanto menos fitness mejor cromosoma. En el caso del problema
del viajante tendramos la funcin de evaluacin como una funcin que calcula
el total de la distancia que se recorre. En el caso de la seleccin de instancias,
podra ser la precisin que se obtiene despus de seleccionar alguna de los
ejemplos.
Condicin de parada: pueden ser varias, que se llegue a la mejor solucin, que
se supere el nmero de iteraciones previamente escogido,
Seleccin de progenitores: Es el criterio que se sigue a la hora de escoger los
padres para la reproduccin. Hay varias formas. Las ms usadas son:
Seleccin elitista: Se garantiza la seleccin de los miembros ms aptos
de cada generacin.
Seleccin proporcional a la aptitud: los individuos ms aptos tienen
mayor probabilidad de ser seleccionados, pero no la certeza.
Seleccin del mtodo de la ruleta: A cada uno de los individuos de la
poblacin se le asigna una parte proporcional a su valor fitness, de tal
manera que la suma de todos los porcentajes sea la unidad. Los mejores
individuos tendrn mayor porcentaje que los peores. Se genera un
10

nmero aleatorio, y el individuo que este en esa posicin es el

seleccionado.
Seleccin por mtodo del torneo: En este caso se eligen aleatoriamente
individuos (normalmente es 2) y se selecciona el mejor de los .
Tambin se puede hacer con un mtodo probabilstico. En vez de pasar
el mejor, se genera un nmero aleatorio en el intervalo [0,1], y si ese
nmero es mayor que una cota fijada previamente se escoge el mejor
individuo, en caso contrario el menos apto.
Cruce: El cruce consiste en combinar dos cromosomas, llamados progenitores,
y generar nuevos cromosomas, llamados descendientes. Estos descendientes
comparten alguna de las caractersticas (genes) de los progenitores. Hay varios
mtodos de cruce, y difieren dependiendo de la representacin. Por ejemplo,
alguno de los cruces para cromosomas binarios:
Cruce sobre un punto: Se elige un punto aleatorio del cromosoma. La
primera parte del primer progenitor y la segunda parte del segundo,
ser el primer descendiente, y la primera parte del segundo progenitor
y la segunda parte del primero, ser el segundo descendiente. Ejemplo:

Figura 3. Ejemplo de cruce sobre un punto

Cruce multipunto: Es la generalizacin del anterior tomando varios

puntos.
Por ejemplo para los reales tenemos otros mtodos diferentes. El siguiente es
uno:
Recombinacin simple: Se elige un punto al azar. Los genes desde el
inicio hasta el punto formaran parte de los genes de los descendientes,
y el resto son calculados utilizando la media aritmtica. Ejemplo:

Figura 4. Ejemplo de recombinacin simple

11

Mutacin: La mutacin es la alteracin de alguno de los genes de un

cromosoma. Por ejemplo, en un cromosoma donde cada gen es binario, su
valor puede cambiar de 0 a 1 o de 1 a 0 con la probabilidad que establezcamos.
En general esta probabilidad es muy baja, se intenta que muten pocos genes
por generacin.
Seleccin de la siguiente generacin: Una vez creados los descendientes y unir
los descendientes con los progenitores, tenemos que hacer la seleccin de la
siguiente generacin. Existen varias tcnicas:
Seleccin por edad: Cada individuo solo est presente en el algoritmo
durante un nmero fijado de generaciones. Esto puede llevar a la
eliminacin de los mejores adaptados.
Seleccin basada en la adaptacin: En este grupo se encuentran los
mtodos de la ruleta y del torneo, anteriormente mencionados. A parte
de estos existen otros:
Reemplazar el peor: Se eliminan los peores individuos. Puede
producir convergencia prematura.
Elitismo: La idea de este mtodo es la de mantener siempre en
la poblacin al mejor adaptados entre los progenitores y los
descendientes.
El pseudo-cdigo del algoritmo gentico es:
ALGORITMO 2

poblacion = generarPoblacionAleatoriamente()
generacion = 0
evaluar (poblacion)
mientras (no condicionDeParada) hacer
padres = seleccionProgenitores (poblacion)
hijos = cruzar (padres)
hijos = mutar (hijos)
evaluar (hijos)
poblacion = seleccionSiguientePoblacion (hijos, poblacion)
generacion = generacion + 1
fin mientras
devolver mejor individuo

2.4.

Algoritmo CHC

El algoritmo CHC es un algoritmo gentico sencillo y robusto que normalmente

ofrece buenos resultados. Originalmente este algoritmo estaba pensado para utilizar
cromosomas con representacin binaria, pero actualmente tambin se puede utilizar
con codificacin real. En este proyecto se utilizan ambos tipos de cromosomas.

12

Una de las caractersticas de este algoritmo es la seleccin elitista, es decir, los

mejores individuos de la poblacin son los que se seleccionan para la nueva poblacin.
Otra caracterstica importante es que este algoritmo tiene un mecanismo de
prevencin de incesto que evita que, los cromosomas seleccionados para procrear, lo
hagan si son muy parecidos. Para esto calculamos la distancia de Hamming entre los
cromosomas, y si la mitad de esa distancia es mayor que un umbral , estos
cromosomas no son cruzados. Normalmente ese umbral es un cuarto de la longitud
del cromosoma, que se va reduciendo 1 cada vez que no obtenemos nuevos
descendientes. Tambien hay que decir que este algoritmo no tiene mutacion. Cuando
la poblacin generacin a generacin no vara, la poblacin es restablecida.
Normalmente se utiliza el umbral , cuando este es 0 se incia el proceso de reincio. En
este proceso se mantiene el mejor individuo y el resto es generado aleatoriamente
puediendo incluir parte de los genes del mejor.
El pseudo-codigo del algoritmo CHC es el siguiente:
ALGORITMO 3
poblacion = generarPoblacionAleatoriamente()
d = LongitudCromosoma / 4
evaluar (poblacion)
mientras (no condicionDeParada) hacer
padres = seleccionProgenitores (poblacion)
hijos = cruzar (padres)
evaluar (hijos)
seleccionSiguientePoblacion (hijos, poblacion)
si poblacion no ha cambiado entonces
d=d1
fin si
si d < 0 entonces
poblacion = reiniciar (poblacion)
d = LongitudCromosoma / 4
fin si
fin mientras
devolver mejor individuo

13

3. Propustas
3.1.

Algoritmo KNN con medidas de disimilitud

Nuestro objetivo consiste en utilizar las medidas de disimilitud previamente

comentadas para calcular la distancia entre instancias en el algoritmo KNN. Como ya
hemos dicho, estas medidas emplean funciones llamadas automorfismos. En este caso
utilizaremos los siguientes automorfismos:
1 =

2 =

Del primer automorfismo tenemos que realizar la inversa, por la definicin de la

disimilitud. Por lo tanto nos queda:
1 =

La funcin de disimilitud que nos queda es la siguiente:

(, ) = (| |)

Por lo tanto esa es la funcin que utilizaremos para calcular la distancia (en un
atributo) entre la instancia x y la instancia y. Utilizando la agregacin antes comentada:

1
1
(, ) = [(|() () |) ]

=1

Por cada uno de los atributos tenemos un valor y un valor . Se calcula la

disimilitud entre el atributo de la instancia y el atributo de la instancia con el
valor y , y finalmente se calcula la media de todas las disimilitudes.
Pero antes de calcular la distancia, tenemos que convertir el gen, que es un
nmero real en el rango (0,1), a un real en el rango (0, ). Para esto utilizamos la
siguiente funcin:
(2 )2 ,
1
() = {
,
(2 (1 ))2

0.5
> 0.5

Con esta funcin, convertimos los nmeros del (0,0.5] a (0,1] y los(0.5,1) a (1, ).
Como se puede observar dndole ciertos valores a y a podemos obtener la
distancia Euclidea y la de Manhattan. La distancia de Manhattan es la suma de las
14

diferencias en valor absoluto, si los valores de y de obtienen el valor 1,

recuperamos esa funcin. Por tanto, tenemos que buscar los valores tales que el
resultado de aplicarlos a la funcin sea 1.
(2 )2 = 1 2 = 1 =

1
2

Dando el valor 0.5 a cada gen obtenemos la distancia Manhattan:

=1

=1

1
1
1
(, ) = (|()1 ()1 |) 1 = |() ()|

Para la distancia Euclidea, tenemos que elevar cada valor a 1, por lo tanto tenemos
que es 1. Luego tenemos que elevar al cuadrado la diferencia, por lo tanto tiene
que ser 0.5.
Ya hemos calculado antes que para conseguir el valor 1 tenemos que utilizar 0.5.
Para conseguir el valor 0.5:
(2 )2 = 0.5 2 = 0.5 =

0.5
2

Ese es el valor que tenemos que utilizar para obtener el valor 0.5. Finalmente
tenemos:

=1

=1

1
1
1
(, ) = (|()1 ()1 |) 0.5 = (|() ()|)2

En la formula anterior faltara hacer la raz cuadrada del resultado final, pero como
la raz es una funcin continua, no se altera el orden, es decir, si entonces
. Teniendo la distancia 1 = (, ) y 2 = (, ) si 1 2, se cumple
que 1 2 .
Por lo tanto nos queda el algoritmo KNN normal, pero utilizando las medidas de
disimilitud como distancia.

3.2.

Algoritmo gentico

Como ya se ha dicho el algoritmo gentico que vamos a utilizar es el CHC. Los

parmetros que va a tratar de ajustar este algoritmo son los valores de y que se
utilizan en los automorfismos. Los aspectos que tenemos que tener en cuenta son:

15

Representacin: Cada atributo necesita de dos parmetros (un y un ), por

consiguiente, cada cromosoma tendr tantos genes como atributos
multiplicado por 2. Cada uno de estos valores, ser un nmero real, en el
intervalo (0,1).
Funcin de evaluacin: Como lo que queremos es obtener una mejor precisin,
el valor por el cual ordenaremos la poblacin ser este. La funcin que
utilizaremos, ser el algoritmo KNN previamente explicado, donde le pasamos
el cromosoma con los valores de los s y de las s (para poder calcular la
distancia basndose en la disimilitud) y nos devuelve la precisin.
Condicin de parada: Hay tres casos en los que el algoritmo dejara de iterar y
devolvera el mejor individuo:
Se encuentra la solucin ptima. En este caso, el mejor individuo ha
obtenido 100% de aciertos de clasificacin.
Se ha superado el nmero de iteraciones previamente fijado.
Como es propio de CHC, se superan el nmero mximo de reinicios sin
mejorarse la poblacin.
Seleccin de progenitores: En este caso, seleccionamos todos los individuos de
la poblacin y los cruzamos aleatoriamente entre ellos.
Cruce: Para el cruce de reales, se va a utilizar el cruce PCBLX. Este mtodo,
dados dos cromosomas genera otros dos nuevos. El mtodo es el siguiente:
Tenemos el cromosoma = [1 , 2 , 3 , ] y = [1 , 2 , 3 , ]. Por cada
gen se calcula un valor = | |. Se calculan los valores 1 = max(0,
), 1 = min(1, + ), 2 = max(0, ) y 2 = min(1, + ). Para
el primer descendiente, por cada gen se genera un nmero aleatorio en el
rango [1 , 1 ] y para el segundo en el rango [2 , 2 ].
Mutacin: Como ya se ha dicho, el CHC no realiza el proceso de mutacin. A
cambio de este, se utiliza un mtodo de reinicio, donde si la poblacin no
cambia durante una serie de generaciones, se elimina toda la poblacin
excepto el mejor y se generan el resto aleatoriamente.
Seleccin de la siguiente iteracin: Como ya se ha dicho, el CHC es un
algoritmo que hace seleccin elitista, es decir, se seleccionan los mejores
individuos para la siguiente poblacin.

3.3.

Seleccin de instancias.

Otra de las cosas que se aade al algoritmo gentico es la posibilidad de hacer

seleccin de instancias. En este caso para la representacin utilizaremos nmeros
binarios, donde la longitud del cromosoma ser el nmero de instancias de

16

entrenamiento que tengamos. Un 1 en la posicin significa que la instancia numero

es utilizada para clasificar, y un 0 que no.
A la funcin de evaluacin tenemos que aadir un trmino que penalice la
reduccin de instancias masiva. Si no aadiramos este trmino, probablemente el
nmero de instancias sera muy bajo, ya que con pocas instancias es ms probable
tener un porcentaje de clasificacin mayor.
Definimos el ratio de reduccin como:
= 1.0

Donde # es el nmero de genes a 1 y es el nmero de

instancias.
Con todo esto definimos el nuevo fitness como:
= + (1 )
Donde es el porcentaje de clasificacin y un valor real para dar peso a
cada trmino. En este caso, si vale 1, el ratio de clasificacin sera el fitness total, y
no se tiene en cuenta el trmino de la reduccin.
Como en este caso se tratan de genes binarios el mtodo de cruce tiene que ser
otro diferente al de la parte de los reales. En este caso empleamos HUX que es un
mtodo de cruce que intercambia exactamente la mitad de los bits que son distintos
entre los padres. Esta funcin recibe adicionalmente un parmetro para indicar la
probabilidad de que un bit durante el cruce pase de ser 0 a 1.

3.4.

Seleccin de caractersticas

Como en el caso anterior, para la representacin se utilizan nmeros binarios. En

este caso, tendremos tantos genes como atributos tenga el conjunto de instancias de
entrenamiento. Del mismo modo, si tenemos un 1 en la posicin se utiliza el atributo
para clasificar. Si hay un 0, no se utiliza.
De la misma manera que en el caso anterior, tenemos que modificar la funcin de
evaluacin para evitar una alta reduccin de atributos. Primero definimos el ratio de
reduccin:
= 1.0

17

Donde # es el nmero de atributos seleccionados y es el

nmero de atributos. Con esto, la funcin de evaluacin:
= + (1 )
Donde es el porcentaje de aciertos y un valor real para dar peso a
cada trmino. Como antes, si vale 1, se carga todo el peso sobre el ratio de
clasificacin.
En este caso como tambin tenemos genes binarios, utilizamos la funcin HUX
anteriormente descrita.

3.5.

Modelo completo

El modelo completo es la combinacin de los ltimos apartados. Por una parte

tenemos la parte real y por otro la parte en binario (una parte para la seleccin de
instancias y otra para la seleccin de caractersticas). Por lo tanto nuestro cromosoma
tendr 3 + , tantos genes como atributos
multiplicado por 2 por la parte real, tambin nmero de atributos por la parte binaria
de seleccin de atributos y tantos genes como instancias de entrenamiento por la
parte de seleccin de instancias.
No siempre se va a utilizar la seleccin de instancias o la seleccin de
caractersticas. Por lo tanto un parmetro de la funcin ser si utilizamos seleccin de
instancias, seleccin de caractersticas o ambas. En este caso el nmero de genes ser
el mismo, con la diferencia que los genes que correspondan a la seleccin que no se
quiere utilizar, tendrn todos el valor 1 (se seleccionan siempre).
Para la funcin de evaluacin, combinamos las anteriores y obtenemos la siguiente
funcin:
= + (1 ) + (1 )
Donde los ratios de reduccin de instancias y de caractersticas son las
mencionadas anteriormente. Para los valores de y tenemos que tener en cuenta
que tipo de reduccin se va a realizar. Si no se utiliza reduccin de instancias, el
parmetro ser 1, de esta manera eliminamos la parte de la reduccin de instancias
y damos todo el peso a la seleccin de caractersticas y el porcentaje de instancias
bien clasificadas. Los mismo sucede con la reduccin de caractersticas, si no se utiliza
valdr 1 eliminado la parte de la reduccin de caractersticas. Si no se utiliza ninguno
de los dos mtodos, todo el peso nos quedara en el ratio de clasificacin. En cualquier
otro caso, se asigna a y los valores 0.6 y 0.99 respectivamente.

18

Para realizar el cruce, por definicin del algoritmo CHC, tenemos que calcular la
distancia de Hamming entre los progenitores, y solo cruzar aquellos cuya diferencia
sea mayor que un umbral establecido. Pero la distancia de Hamming se utiliza para
nmeros binarios. Por lo tanto hay que convertir los nmeros reales a binario.
DE NMEROS REALES A BINARIO: CDIGO GRAY
Lo que se quiere hacer es obtener nmeros binarios para calcular la distancia entre
dos cromosomas. Pero por ejemplo la diferencia entre 3 y 4 es 1, pero si pasamos los
nmeros a binario y calculamos la distancia de Hamming: 3 011 y 4 100, la
distancia es el nmero de bits diferentes por posicin, como tenemos 3 bits, y todos
son diferentes, la distancia total es 3. Por esta razn vamos a utilizar la codificacin de
gray para los nmeros binarios, que se cumple que entre dos nmeros consecutivos su
distancia de Hamming es 1. Por ejemplo la codificacin de gray con 3 bits es la
siguiente:
0 000
1 001
2 011
3 010
4 110
5 111
6 101
7 100
En el ejemplo se ve como la distancia de Hamming entre un elemento y el siguiente
(o el anterior) es 1.
El proceso para convertir un nmero real, teniendo en cuenta que estos nmeros
reales estn dentro del rango (0,1), es el siguiente:
Lo primero que hacemos es convertir el real a entero. Para ello cada valor real lo
convertimos a entero con la siguiente funcin:
() = ( 2 + 0.5)
Donde BITGEN es el nmero de bits que vamos a usar para representar cada
valor real. En este trabajo este valor es 30.
Una vez que tenemos el nmero entero lo convertimos a binario de forma
normal. Y una vez que tenemos el nmero en binario, convertimos este a binario pero
en codificacin gray. Para realizar este proceso hay que desplazar el nmero original
un bit hacia la derecha, y calcular la operacin OR exclusivo entre el nmero original y
el nmero desplazado sin acarreo.

19

Por ejemplo para el nmero 6 (110), y su valor desplazado (11) calculamos la

operacin OR exclusivo (bit a bit): 110 011 1 0 = 1, 1 1 = 0, 0 1 =
1. Resultado 101.
Una vez que ya podemos calcular las distancias, calculamos la distancia de cada
una de las partes de los cromosomas y realizamos el cruce.
Por una parte cruzamos la parte real del cromosoma utilizando el cruce PCBLX
anteriormente mencionado y para la parte binario utilizamos el mtodo HUX, tambin
explicado anteriormente.
Como se mencion en la seccin 3.1., dndole ciertos valores a y a ,
podemos recuperar las distancias euclidea y manhattan. En un principio, la poblacin
inicial se genera aleatoriamente, pero en este caso introducimos dos cromosomas que
recuperen estas dos distancias dndole los valores que hemos calculado
anteriormente y el resto lo generamos aleatoriamente.
Introduciendo estos cromosomas, partimos de que entrenamos el algoritmo
con estas distancias. En consecuencia, el algoritmo como mnimo obtendr el mismo
porcentaje de acierto, en el conjunto de entrenamiento, que el algoritmo original.

20

4. Marco xprimntal
4.1.

Mtodos en la comparativa

Para empezar vamos a utilizar el mtodo descrito en la seccin 3, con todas sus
variantes:
1.
2.
3.
4.

KNN con medidas de disimilitud

KNN con medidas de disimilitud + seleccin de instancias
KNN con medidas de disimilitud + seleccin de caractersticas
KNN con medidas de disimilitud + seleccin de instancias + seleccin de
caractersticas

Tambin se van a utilizar el algoritmo KNN original, con todas las posibles
variantes:
5.
6.
7.
8.

KNN original
KNN original + seleccin de instancias
KNN original + seleccin de caractersticas
KNN original + seleccin de instancias + seleccin de caractersticas.

Por otra parte, tambin se ha implementado el algoritmo KNN con pesos. Se utiliza
el algoritmo gentico descrito en la seccin 3. En este caso, por cada atributo tenemos
un gen (en la parte de los reales, la parte de los binarios es igual) que ser el peso que
se le da a cada atributo. La distancia que se utiliza es la distancia Euclidea,
multiplicando cada distancia entre atributos por un peso [0,1].

(, ) = (|() ()|)2
=1

Para elegir un mtodo u otro, se indica por medio de un parmetro. Tenemos otros
cuatro mtodos:
9. KNN pesos
10. KNN pesos + seleccin de instancias
11. KNN pesos + seleccin de caractersticas
12. KNN pesos + seleccin de instancias + seleccin de caractersticas
Adems se tiene la posibilidad de ejecutar el algoritmo gentico con seleccin de
instancias en paralelo. Hasta ahora todos los valores de los mtodos de seleccin se
calculaban conjuntamente con los valores reales. Pero se ha aadido la opcin de
21

ejecutar primero seleccin con el algoritmo KNN original, y despus aprender los
parmetros para las distancias. En la comparativa, nicamente se utiliza la seleccin de
instancias en paralelo. Se indica por parmetro la eleccin entre serie y paralelo.
13. KNN disimilitudes + seleccin de instancias en paralelo (primero seleccin de
instancias con KNN original y despus KNN disimilitudes)
Por ltimo, para tener ms mtodos para la comparativa se han utilizado varios
mtodos ya implementados por KEEL. Se dividen en 2 grupos, los de seleccin de
instancias y los de seleccin de caractersticas:
Seleccin de caractersticas:
14. CW
15. FS-GGA
16. FS-SSGA
Seleccin de instancias:
17. IS-AllKNN
18. IS-CHC
19. IS-ENN
20. IS-RNG
21. IS-SSMA

4.2.

Datasets

En este trabajo, para calcular las distancias se utilizan medidas de disimilitud, que
como se ha dicho, son funcin cuya entrada son nmeros reales en el rango [0,1]. Por
lo tanto todos los datos que utilicemos tienen que cumplir esta condicin. Cuando
leemos un fichero, los datos no tienen por qu cumplir esta condicin, por lo tanto, a
la hora de leer los datos tenemos que hacer una conversin. Tenemos 3 posibles tipos
de datos:
-

Reales: En este caso se nos indica en la cabecera del dataset en que rango
estn estos datos. Con esta informacin, utilizamos la siguiente funcin para
convertir los nmeros al rango que necesitamos:

() =

Con esta funcin, si es igual que el minimo, la funcin devuelve 0, y si es el
mximo 1.

22

Enteros: Como en el caso anterior, se nos dice el rango en el que estn los
datos. Utilizamos la funcin anterior para convertir los nmeros enteros a
reales en el rango [0,1].
Nominales: En este caso, en la cabecera se indica todos los posibles valores que
puede tomar este atributo. Para su paso a reales utilizamos la siguiente
funcin:

() =
1
Donde es el nmero de valores diferentes que puede tomar e es el
ndice del valor que deseamos convertir (el primer elemento tiene como ndice
0, y el ultimo 1). De esta manera el primer valor de la lista se convierte a 0,
y el ltimo a 1. El resto en nmeros reales dentro del rango deseado.

En la siguiente tabla se muestran los datasets utilizados, con la cantidad de

atributos de cada tipo, el nmero de ejemplos y el nmero de clases.

Dataset
abalone
autos
balance
car
cleveland
contraceptive
dermatology
ecoli
glass
hayes-roth
iris
led7digit
letter
newthyroid
pageblocks
penbased
satimage
segment
shuttle
tae
thyroid
vehicle
vowel

Ejemplos
418
159
625
1728
297
1473
358
336
214
132
150
500
2000
215
548
1100
643
2310
2175
151
720
846
990

Real
7
15
4
0
13
0
0
7
9
0
4
7
0
4
4
0
0
19
0
0
6
0
10

Integer
0
0
0
0
0
9
34
0
0
4
0
0
16
1
6
16
36
0
9
5
15
18
3
23

Nominal
1
10
0
6
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Clases
28
6
3
4
5
3
6
8
7
3
3
10
26
3
5
10
7
7
7
3
3
4
11

wine
yeast
appendicitis
australian
automobile
banana
bands
bupa
crx
german
ionosphere
mammographic
monk-2
movement_libras
phoneme
saheart
sonar
spectfheart
titanic
wdbc

178
1484
106
690
150
5300
365
345
653
1000
351
830
432
360
5404
462
208
267
2201
569

13
8
7
3
15
2
13
1
3
0
32
0
0
90
5
5
60
0
3
30

0
0
0
5
0
0
6
5
3
7
1
5
6
0
0
3
0
44
0
0

0
0
0
6
10
0
0
0
9
13
0
0
0
0
0
1
0
0
0
0

3
10
2
2
6
2
2
2
2
2
2
2
2
15
2
2
2
2
2
2

Tabla 1. Dataset utilizados

Todos estos datasets estn particionados en 5 partes (folders). Cada una de

estas partes ha sido creada del dataset original, incluyendo una parte del mismo.
Luego a la hora de ejecutar el algoritmo, se hace 5 veces, una por cada folder, y el
resultado final es la agregacin de estos 5 resultados, utilizando la media aritmtica.
Los datasets en los que nos hemos centrado son datasets con atributos
numricos ya que la disimilitud no tiene tanto sentido cuando tenemos atributos
nominales, aunque hemos utilizado alguno con este tipo de atributos.

4.3.

Configuracin de parmetros para cada mtodo

Por cada uno de los mtodos, se van a listar sus parmetros. Todos los mtodos
han sido ejecutados con = 1, es decir, solo se tiene en cuenta el vecino ms cercano
aunque la implementacin admite cualquier valor de .
La funcin que se ha creado para ejecutar el algoritmo gentico recibe 6
parmetros a parte del dataset que se quiere ejecutar. Los parmetros son:

24

L: Tamao de la poblacin, es decir, nmero de individuos para el algoritmo

gentico.
n_iters: Numero de iteraciones que va a realizar el algoritmo gentico.
k: Numero de vecinos.
op: Valor que indica que tipo de aprendizaje de distancias usar. El valor 1 indica
distancias basadas en medidas de disimilitud, y el valor 2 indica KNN con pesos.
algs: es un vector de 3 elementos, cuyos valores pueden ser 0 o 1. La posicin 1
indica el aprendizaje de distancias (ya sea pesos o disimilitudes), la segunda la
seleccin de instancias y la ultima la seleccin de caractersticas. Si tenemos un
1 decimos que utilizamos el mtodo correspondiente y un 0 indica que no.
sep: valor que indica si queremos hacer el proceso en serie o en paralelo. Un 1
indica que queremos hacerlo en paralelo, cualquier otro valor en serie.

Todas las ejecuciones que se hagan con el algoritmo implementado van a tener
ciertos parmetros iguales. El nmero de individuos (L) va a ser 50, k (nmero de
vecinos) ya se ha dicho que va a valer 1 y n_iters (nmero de iteraciones) va a ser
10000. El resto vara segn el mtodo:
1. KNN original: El valor de op no es necesario, ya que no se aprenden distancias,
el valor algs ser [0,0,0] (no utilizar ningn tipo de aprendizaje) y sep sera 0
para hacerlo en serie.
2. KNN original + seleccin de instancias: Igual que el mtodo anterior excepto
algs que es [0,1,0]
3. KNN original + seleccin de caractersticas: Igual que los anteriores excepto
algs que es [0,0,1]
4. KNN original + seleccin de instancias + seleccin de caractersticas: Igual que
los anteriores excepto algs que es [0,1,1]
5. KNN con pesos: El valor de op tiene que ser 2 para utilizar pesos, algs [1,0,0] y
sep 0.
6. KNN con pesos + seleccin de instancias: Igual que el anterior pero con algs
[1,1,0].
7. KNN con pesos + seleccin de caractersticas: Igual que el anterior pero con
algs [1,0,1].
8. KNN con pesos + seleccin de instancias + seleccin de caractersticas: Igual
pero con algs [1,1,1].
9. KNN con disimilitudes: Para empezar todos los mtodos utilizan op 1 para
utilizar disimilitudes y sep 0 para hacerlo todo en serie. Luego dependiendo si
se quiere utilizar seleccin de instancias y/o seleccin de caractersticas se
empleara el parmetro algs igual que en el KNN con pesos dependiendo de lo
que se quiera usar.

25

10. KNN con disimilitudes + seleccin de instancias en paralelo: Igual que el

mtodo de KNN con disimilitudes + seleccin de instancias excepto sep que
ser 1.
11. Mtodos de KEEL: Estos mtodos tienen varios parmetros pero difieren unos
de otros. Todos los para metros k sern 1 como se ha dicho, excepto en 2
mtodos. En los mtodos IS-AllKNN y IS-ENN, se utiliza un k con valor 3, ya que
este lo emplea para hacer seleccin de instancias y despus el algoritmo KNN
clasificara utilizando k con valor 1. El resto de parmetros son los valores por
defecto que trae KEEL, excepto para los de tamao de la poblacin que es 50
como ya se ha dicho, y el nmero de iteraciones 10000.

4.4.

Test estadsticos y evaluacin

En este trabajo se utilizan dos tipos de test para poder decir cul de los mtodos
anteriormente citados es mejor. Estos test se basan en un estudio estadstico, y
compara diferentes mtodos diciendo cual es mejor. Los test son el test de Wilcoxon y
el test de Friedman.
Test de Wilcoxon: Este test se utiliza para comparar un mtodo frente a otro. Para
comprobar cul de los dos mtodos es mejor utiliza los datos obtenidos en los
diferentes conjuntos utilizados en la ejecucin. Cuantos ms datasets, ms preciso ser
el resultado. Este test, va comparando los resultados obtenidos en los diferentes
datasets y va asignando rangos al algoritmo que gana en cada caso. Despus con los
resultados de estos rangos se calcula un nmero llamado el cual indica si hay
independencia estadstica. Si el es menor o igual a 0.05, entonces el mtodo con
ms rangos es mejor estadsticamente que el otro. En caso contrario no se puede
afirmar que haya diferencias estadsticas.
Test de Friedman: Este test, es utilizado para comparar varios mtodos, al
contrario que el anterior que solo compara 2. Al igual que en el anterior, hace uso de
los datos obtenidos en los diferentes conjuntos utilizados en la ejecucin, cuantos ms
datasets, ms preciso ser el resultado. Este mtodo va calculando los rangos y se
calcula tambin un que indica si hay diferencia estadstica o no. En este caso, si
es menor o igual a 0.05, se dice que el mtodo con menos rangos (en el anterior
era el que ms) es estadsticamente mejor y en caso contrario no se puede afirmar que
sea mejor.

26

5. Estudio xprimntal
5.1.

Introduccin y objetivos

El objetivo de este proyecto es mejorar el ratio de clasificacin del algoritmo KNN

aprendiendo las distancias. A parte de mejorar el algoritmo original de KNN, queremos
ver si el propuesto supera tambin al ya existente algoritmo de KNN con pesos en los
atributos. Tambin se han expuesto mtodos de seleccin de instancias y de
caractersticas, vamos a ver cul de todas las variantes es mejor. Y con todo esto,
tambin utilizaremos mtodos existentes implementados en KEEL para tener ms
mtodos en la comparativa.
Con todos los mtodos comentados tenemos 21 diferentes mtodos a comparar,
por lo tanto no podemos hacer una comparativa todos frente a todos, vamos a realizar
una comparativa por fases utilizando los test de Wilcoxon y de Friedman
anteriormente citados.

5.2.

Resultados

En este trabajo se van a exponer 5 tipos de tablas: una para los resultados de
entrenamiento, otra para los resultados de test, otras 2 con los ratios de reduccin en
seleccin de instancias y caractersticas, y otra con los tiempos de ejecucin. Los
mtodos de KEEL nicamente aparecern en las dos primeras: resultados de
entrenamiento y de test. En los casos de los resultados de entrenamiento, muestran el
porcentaje de aciertos obtenido con un valor entre 0 y 1. En los casos de seleccin,
muestran el ratio de reduccin correspondiente, tambin con un nmero entre 0 y 1.
Por ltimo, la tabla de los tiempos, muestran el tiempo que han tardado en ejecutar
cada mtodo en cada dataset. Este tiempo se muestra en segundos.
En las columnas aparecer la combinatoria del parmetro algs comentado en la
seccin 4.3, junto al parmetro op. Los mtodos de seleccin de instancias y de
caractersticas solo aparecern donde se haya usado el mtodo, ya que si no se utiliza
el mtodo el ratio de reduccin es 0.
Las filas de las tablas corresponden a los datasets, y las columnas a cada mtodo.
Aparte de los datasets, se ha agregado una fila con la media de los resultados.

27

Una de las cosas que se pueden observar, es que el mtodo propuesto (KNN con
disimilitudes) siempre consigue un mejor resultado o como mnimo igual que el KNN
original (columnas 1 y 5 de la primer parte de los datos de entrenamiento). Como se
dijo en la seccin 3.1, en el algoritmo gentico se aade un cromosoma que utiliza la
misma distancia que el algoritmo KNN original. Por lo tanto, si el algoritmo gentico no
consigue encontrar una solucin mejor, como mnimo va a tener la misma capacidad
que el KNN original.

28

000
op = 2

abalone
autos
balance
car
cleveland
contraceptive
dermatology
ecoli
glass
hayes-roth
iris
led7digit
letter
newthyroid
pageblocks
penbased
satimage
segment
shuttle
tae
thyroid
vehicle
vowel
wine
yeast
appendicitis
australian
automobile
banana
bands
bupa
crx
german
ionosphere
mammographic
monk-2
movement_libras
phoneme
saheart
sonar
spectfheart
titanic
wdbc
MEDIA

0 0 1 (FS) 0 1 0 (IS) 0 1 1 (IFS)

op = 2

op = 2

op = 2

100
op=1(disimil.)

op = 2

,1353

,2249

,4180

,4133

,2658

,2703

,7280

,8837

,8163

,7955

,9386

,9356

,7776

,7776

,8900

,8932

,8448

,7928

,8666

,9274

,8694

,8883

,9773

,9531

,5236

,5985

,6448

,6439

,6507

,6600

,4252

,4817

,5326

,5614

,5243

,5178

,9539

,9797

,9721

,9588

,9965

,9993

,7828

,7843

,8379

,8022

,8624

,8327

,7078

,7757

,7640

,7780

,8808

,8538

,7083

,8296

,7592

,8448

,8599

,7747

,9550

,9700

,9850

,9767

,9817

,9783

,5934

,5943

,7517

,7447

,5934

,6049

,8164

,8575

,7341

,7533

,8839

,8913

,9628

,9698

,9628

,9698

,9919

,9872

,9361

,9562

,9439

,9489

,9772

,9644

,9716

,9725

,9373

,9102

,9875

,9873

,8624

,8892

,8799

,8573

,9137

,9238

,9683

,9748

,9304

,9361

,9922

,9885

,9962

,9970

,9948

,9956

,9988

,9987

,6092

,6175

,6970

,6787

,7301

,7350

,8937

,9781

,9271

,9719

,9781

,9875

,6892

,7408

,7012

,7216

,7931

,7899

,9879

,9894

,8715

,8381

,9960

,9970

,9593

,9958

,9916

,9747

1,0000

,9986

,5189

,5219

,5878

,5822

,5719

,5642

,8019

,8798

,8892

,9056

,9316

,9104

,8076

,8533

,8739

,8663

,8793

,8772

,7293

,8803

,8301

,7985

,9433

,9449

,8682

,8682

,8995

,8971

,8792

,8739

,7082

,7630

,7363

,7295

,8651

,8630

,6232

,6558

,7297

,7333

,7420

,7348

,8113

,8595

,8725

,8668

,8882

,8940

,6903

,7338

,7470

,7555

,7873

,7955

,8640

,9359

,9174

,9088

,9822

,9672

,7521

,7732

,8389

,8352

,7994

,7831

,7714

1,0000

,8379

,9716

1,0000

1,0000

,8360

,8694

,8202

,8204

,8902

,8840

,8961

,8961

,8369

,8354

,9155

,9133

,6423

,6818

,7749

,7473

,7706

,7462

,8606

,9243

,8643

,8570

,9772

,9664

,7013

,8324

,8258

,8436

,9195

,9260

,7354

,7357

,7918

,7833

,7360

,7354

,9574

,9758

,9684

,9745

,9908

,9934

,7764

,8234

,8245

,8272

,8625

,8557

Tabla 2. 1 parte de train

29

1 0 1 (FS)
op=1 disimil.

abalone
autos
balance
car
cleveland
contraceptive
dermatology
ecoli
glass
hayes-roth
iris
led7digit
letter
newthyroid
pageblocks
penbased
satimage
segment
shuttle
tae
thyroid
vehicle
vowel
wine
yeast
appendicitis
australian
automobile
banana
bands
bupa
crx
german
ionosphere
mammographic
monk-2
movement_libras
phoneme
saheart
sonar
spectfheart
titanic
wdbc
MEDIA

1 1 0 (IS)

op = 2

op=1 disimil.

1 1 1 (IFS)

op = 2

op=1 disimil.

IS-REFS

op = 2

op=1 disimil.

,2460

,2453

,5018

,4343

,3902

,4124

,4573

,9214

,9278

,8601

,8429

,8079

,8188

,8554

,8460

,7928

,9096

,9052

,9004

,8996

,8992

,9770

,9531

,9372

,9226

,9489

,9220

,9031

,6187

,6061

,6827

,6776

,6397

,6406

,6860

,5287

,5039

,5796

,5935

,5933

,5855

,5779

,9888

,9881

,9951

,9881

,9651

,9707

,9902

,8542

,8312

,8654

,8521

,7992

,8119

,8550

,8621

,8445

,8459

,8084

,7770

,7886

,8131

,8580

,7917

,8921

,8618

,8940

,8655

,8372

,9783

,9783

,9800

,9917

,9650

,9783

,9917

,5943

,6040

,7593

,7624

,7444

,7369

,7536

,8841

,8861

,6924

,7347

,6699

,7311

,8030

,9860

,9884

,9953

,9930

,9802

,9826

,9849

,9694

,9631

,9767

,9662

,9544

,9576

,9640

,9843

,9839

,9116

,9346

,8736

,9214

,9564

,9071

,9160

,8732

,8822

,8472

,8737

,9024

,9889

,9847

,9500

,9556

,9573

,9571

,9563

,9977

,9978

,9963

,9963

,9963

,9963

,9960

,7185

,7085

,6920

,7003

,6587

,6803

,7102

,9875

,9830

,9802

,9795

,9726

,9740

,9313

,7713

,7710

,7184

,7580

,7092

,7597

,7653

,9955

,9960

,8351

,8187

,7593

,8192

,9212

,9958

,9986

,9930

,9916

,9860

,9846

,9986

,5655

,5568

,6043

,6216

,5878

,6147

,6103

,9152

,9057

,9316

,9222

,9152

,9151

,9293

,8703

,8775

,8924

,8906

,8681

,8725

,8902

,9326

,9244

,8616

,8461

,8161

,8097

,8612

,8790

,8739

,8984

,9012

,8990

,9026

,9033

,8349

,8130

,7829

,7699

,7116

,7315

,7925

,7087

,7275

,7652

,7761

,7428

,7478

,7652

,8871

,8832

,9020

,8901

,8641

,8710

,8905

,7360

,7323

,7800

,7890

,7575

,7548

,7848

,9843

,9615

,9558

,9444

,9231

,9202

,9544

,7925

,7865

,8618

,8596

,8497

,8536

,8539

1,0000

1,0000

,9792

1,0000

,9942

1,0000

,9722

,9007

,9041

,7588

,7686

,7601

,7603

,8436

,9145

,9123

,8369

,8425

,8480

,8411

,8403

,6975

,7219

,7873

,7857

,7533

,7565

,7901

,9675

,9615

,9062

,8654

,8306

,8245

,9387

,8811

,8914

,8344

,8576

,7987

,8305

,9064

,7360

,7357

,7918

,7918

,7863

,7863

,7916

,9842

,9815

,9886

,9837

,9701

,9758

,9895

,8523

,8464

,8498

,8479

,8248

,8334

,8562

Tabla 3. 2 parte de train

30

CW

abalone
autos
balance
car
cleveland
contraceptive
dermatology
ecoli
glass
hayes-roth
iris
led7digit
letter
newthyroid
pageblocks
penbased
satimage
segment
shuttle
tae
thyroid
vehicle
vowel
wine
yeast
appendicitis
australian
automobile
banana
bands
bupa
crx
german
ionosphere
mammographic
monk-2
movement_libras
phoneme
saheart
sonar
spectfheart
titanic
wdbc
MEDIA

FS-GGA

FS-SSGA

IS-ALLKNN

IS-CHC

IS-ENN

IS-RNG

IS-SSMA

,1353

,2249

,2172

,6406

,2873

,7545

,2707

,3142

,7280

,7328

,5672

,9788

,6745

,9531

,7125

,7409

,6496

,7776

,6200

,9978

,9072

,9813

,8644

,9068

,7458

,8238

,7157

,9884

,8827

,9489

,8764

,9494

,2863

,5639

,5084

,9763

,6271

,9621

,6070

,6297

,4270

,4732

,4530

,9009

,5384

,8983

,5642

,5905

,3032

,9790

,4945

,9985

,9651

,9842

,9714

,9783

,7828

,7843

,7367

,9856

,8283

,9833

,8461

,8528

,7008

,7687

,7266

,9873

,7032

,9685

,7441

,7580

,2972

,3921

,3921

,6808

,6610

,7128

,4471

,6666

,9567

,9600

,9600

1,0000

,9750

1,0000

,9583

,9833

,3686

,3305

,0946

,7121

,6364

,7399

,5264

,3865

,8110

,8678

,3059

,9730

,5385

,9586

,8132

,7356

,9628

,9698

,9663

,9962

,9802

,9963

,9651

,9814

,9334

,9539

,9503

,9975

,9402

,9976

,9434

,9430

,9716

,9750

,7205

,9988

,9114

,9955

,9727

,9657

,8624

,9063

,7904

,9889

,8686

,9817

,8943

,8970

,9639

,9686

,9614

,9964

,9226

,9933

,9654

,9641

,9962

,9883

,9930

1,0000

,9931

,9995

,9960

,9945

,4188

,4186

,3938

,8504

,5960

,8679

,5709

,5959

,1212

,9792

,9705

,9963

,9274

,9962

,9316

,9378

,6886

,7485

,6419

,9610

,6785

,9380

,7503

,7754

,9879

,9907

,8957

,9968

,7045

,9961

,9848

,8361

,9578

,9902

,9438

,9970

,9761

,9868

,9635

,9874

,5007

,5057

,4348

,9493

,6038

,9269

,6402

,6582

,8019

,8798

,8633

,9968

,8939

,9971

,8915

,8963

,7696

,8558

,8134

,9921

,8826

,9914

,8765

,8851

,7293

,7464

,4355

,9691

,6666

,9523

,6982

,7135

,6784

,8683

,8683

,9963

,9003

,9945

,9156

,9141

,4699

,7781

,5555

,9445

,7315

,9322

,7685

,7555

,6094

,6312

,6196

,9355

,7022

,8979

,7348

,7717

,8097

,8541

,7994

,9924

,8733

,9895

,8760

,8886

,3153

,7383

,6998

,9760

,7635

,9576

,7605

,7995

,6588

,9487

,8504

,9929

,9053

,9773

,8825

,9302

,7545

,7581

,7587

,9878

,8440

,9699

,8334

,8509

,8409

,7778

,7778

,9593

,9734

,8422

,7813

,9543

,5321

,8603

,4936

,9657

,6522

,9379

,8035

,7491

,8935

,8935

,8498

,9931

,8313

,9866

,9109

,8890

,6412

,6786

,6569

,9769

,7625

,9524

,7608

,7933

,6027

,9724

,7404

,9893

,8390

,9623

,8774

,8703

,2060

,8689

,7865

,9653

,8146

,9543

,8118

,8483

,6711

,6711

,6711

1,0000

,7902

,8726

,7368

,7509

,9569

,9811

,9438

,9991

,9750

,9936

,9714

,9807

,6628

,7869

,6893

,9577

,7937

,9461

,8063

,8202

Tabla 4. 3 parte de train

31

000
op = 2

abalone
autos
balance
car
cleveland
contraceptive
dermatology
ecoli
glass
hayes-roth
iris
led7digit
letter
newthyroid
pageblocks
penbased
satimage
segment
shuttle
tae
thyroid
vehicle
vowel
wine
yeast
appendicitis
australian
automobile
banana
bands
bupa
crx
german
ionosphere
mammographic
monk-2
movement_libras
phoneme
saheart
sonar
spectfheart
titanic
wdbc
MEDIA

0 0 1 (FS) 0 1 0 (IS) 0 1 1 (IFS)

op = 2

op = 2

op = 2

100
op=1(disimil.)

op = 2

,1571

,1963

,2551

,2389

,1892

,2092

,7487

,8565

,7252

,7106

,9075

,8513

,8029

,8029

,8735

,8800

,8495

,7853

,8883

,9305

,8495

,8831

,9658

,9612

,5524

,5114

,5761

,5724

,5186

,5358

,4406

,4725

,4575

,5269

,4739

,4732

,9550

,9609

,9385

,9355

,9691

,9608

,7894

,7626

,8175

,7785

,7775

,7623

,7128

,7332

,6741

,6782

,7895

,7707

,7451

,8571

,6143

,7808

,8187

,7423

,9467

,9467

,9667

,9400

,9467

,9333

,5188

,5163

,6390

,6528

,5188

,5113

,8364

,8702

,6466

,7050

,8732

,8787

,9674

,9674

,9395

,9256

,9581

,9395

,9401

,9435

,9363

,9455

,9490

,9364

,9737

,9619

,9182

,8819

,9718

,9746

,8786

,8726

,8603

,8258

,8741

,8678

,9723

,9706

,9178

,9277

,9844

,9784

,9936

,9977

,9945

,9950

,9968

,9972

,6148

,5557

,5337

,4946

,6277

,6010

,9028

,9791

,9251

,9709

,9695

,9556

,7022

,7056

,6218

,6680

,7056

,7141

,9939

,9828

,8374

,7980

,9848

,9919

,9546

,9438

,9496

,9668

,9779

,9435

,5465

,5317

,5654

,5640

,5330

,5324

,8208

,8303

,8589

,8403

,8403

,8398

,8102

,8247

,8521

,8390

,8015

,8204

,7468

,8366

,7174

,6939

,9186

,8568

,8806

,8806

,8951

,8919

,8770

,8770

,6904

,6849

,6301

,6575

,7562

,7342

,6145

,6058

,6203

,7043

,5797

,6203

,8194

,8162

,8546

,8592

,8101

,7994

,6830

,6850

,7060

,7110

,7050

,6790

,8774

,9030

,9002

,8831

,9002

,9115

,7700

,7832

,8193

,8254

,7724

,7748

,7548

1,0000

,7688

,9723

1,0000

1,0000

,8713

,8833

,7413

,7133

,8400

,8687

,9108

,9108

,8249

,8222

,9134

,9134

,6625

,5756

,7273

,7144

,6105

,6537

,8562

,8563

,7496

,7948

,8562

,8757

,6964

,7154

,7527

,7867

,7377

,7196

,7344

,7344

,7877

,7808

,7344

,7344

,9508

,9508

,9421

,9509

,9615

,9544

,7834

,7978

,7717

,7834

,8080

,8010

Tabla 5. 1 parte de test

32

1 0 1 (FS)
op=1(disimil.)

abalone
autos
balance
car
cleveland
contraceptive
dermatology
ecoli
glass
hayes-roth
iris
led7digit
letter
newthyroid
pageblocks
penbased
satimage
segment
shuttle
tae
thyroid
vehicle
vowel
wine
yeast
appendicitis
australian
automobile
banana
bands
bupa
crx
german
ionosphere
mammographic
monk-2
movement_libras
phoneme
saheart
sonar
spectfheart
titanic
wdbc
MEDIA

1 1 0 (IS)

op = 2

op=1(disimil.)

1 1 1 (IFS)

op = 2

op=1(disimil.)

IS-REFS

op = 2

op = 1

,2194

,1720

,2142

,2046

,2204

,2516

,2262

,8642

,8500

,6887

,7233

,7338

,6977

,7161

,8416

,7853

,8945

,8897

,8800

,8704

,8783

,9682

,9612

,9282

,9167

,9421

,9091

,8900

,5084

,5288

,5996

,5795

,5794

,5493

,5761

,4806

,4820

,5261

,5452

,5431

,5607

,5105

,9500

,9609

,9637

,9667

,9496

,9359

,9472

,7649

,7539

,8202

,8082

,7789

,7692

,7934

,7791

,7569

,7444

,7537

,7071

,6840

,7395

,8495

,7956

,8418

,7742

,8341

,7879

,7813

,9400

,9400

,9400

,9667

,9333

,9333

,9667

,5163

,5089

,6505

,6296

,6313

,6024

,6396

,8718

,8767

,6307

,6953

,6160

,6811

,7358

,9674

,9302

,9814

,9767

,9349

,9488

,9442

,9491

,9416

,9580

,9528

,9527

,9490

,9473

,9600

,9664

,8930

,9129

,8420

,9012

,9292

,8415

,8430

,8293

,8386

,8137

,8321

,8603

,9831

,9788

,9450

,9450

,9485

,9468

,9407

,9968

,9954

,9963

,9963

,9963

,9954

,9950

,5946

,6749

,5601

,5684

,5219

,5030

,5742

,9708

,9652

,9764

,9681

,9611

,9667

,9292

,6868

,7234

,6703

,6916

,6608

,6785

,6573

,9838

,9919

,7980

,7848

,7111

,7960

,8778

,9665

,9495

,9603

,9614

,9663

,9497

,9601

,5188

,5322

,5789

,5844

,5511

,5743

,5796

,8307

,8299

,8398

,8403

,8403

,8494

,8113

,8073

,8175

,8522

,8493

,8449

,8551

,8464

,8729

,8357

,7468

,7436

,7170

,7222

,6948

,8772

,8775

,8945

,8974

,8926

,8974

,8994

,6822

,6767

,6849

,6795

,6384

,6521

,7014

,5739

,6696

,6899

,6464

,6841

,6754

,6667

,7993

,8224

,8684

,8638

,8638

,8607

,8577

,7030

,6880

,7410

,7360

,7150

,7210

,7090

,9258

,9087

,9059

,8946

,9087

,8803

,9202

,7652

,7735

,8374

,8399

,8411

,8362

,8375

1,0000

1,0000

,9746

1,0000

,9953

1,0000

,9723

,8480

,8313

,6353

,6733

,6373

,6733

,7353

,9123

,9095

,8331

,8357

,8279

,8327

,8316

,6277

,5866

,7057

,7036

,6926

,6991

,7209

,8033

,7936

,7742

,7746

,7071

,7507

,8224

,7598

,7754

,7903

,7751

,7940

,7867

,7901

,7344

,7344

,7860

,7877

,7803

,7803

,7865

,9403

,9385

,9544

,9631

,9456

,9597

,9597

,8008

,7985

,7931

,7939

,7799

,7839

,7944

Tabla 6. 2 parte de test

33

CW

abalone
autos
balance
car
cleveland
contraceptive
dermatology
ecoli
glass
hayes-roth
iris
led7digit
letter
newthyroid
pageblocks
penbased
satimage
segment
shuttle
tae
thyroid
vehicle
vowel
wine
yeast
appendicitis
australian
automobile
banana
bands
bupa
crx
german
ionosphere
mammographic
monk-2
movement_libras
phoneme
saheart
sonar
spectfheart
titanic
wdbc
MEDIA

FS-GGA

FS-SSGA

IS-ALLKNN

IS-CHC

IS-ENN

IS-RNG

IS-SSMA

,1571

,1895

,2022

,2368

,2364

,2529

,2504

,2368

,7487

,7035

,5444

,5870

,1884

,5791

,1855

,1761

,6574

,8029

,6239

,8784

,8816

,8735

,8783

,8848

,7548

,8258

,7159

,8808

,4961

,8756

,7193

,4161

,3061

,5152

,5258

,5724

,5928

,5691

,5692

,5862

,4345

,4501

,4658

,4630

,4977

,4623

,4766

,5159

,2984

,9583

,4914

,9691

,8997

,9578

,9186

,9155

,7894

,7626

,7029

,8348

,7989

,8191

,8377

,8353

,7082

,7332

,7376

,6686

,6502

,6869

,6867

,7149

,3170

,4159

,4159

,4863

,5555

,5104

,3945

,6132

,9467

,9533

,9467

,9533

,9600

,9600

,9600

,9667

,4126

,3726

,0992

,3150

,5596

,4510

,5074

,4157

,8315

,8822

,3206

,7591

,5341

,7649

,7809

,6774

,9674

,9674

,9535

,9581

,9442

,9535

,9581

,9581

,9419

,9435

,9434

,9399

,9400

,9399

,9417

,9382

,9737

,9627

,7173

,9618

,9119

,9682

,9664

,9356

,8786

,8789

,7698

,8680

,8479

,8726

,8805

,8495

,9688

,9636

,9610

,9511

,9251

,9524

,9602

,9507

,9936

,9876

,9936

,9904

,9940

,9899

,9904

,9936

,4359

,4165

,3640

,5072

,4826

,4748

,5208

,5415

,1606

,9791

,9722

,9278

,9264

,9292

,9334

,9306

,6999

,7034

,6314

,6811

,6146

,6939

,6810

,6491

,9939

,9859

,9242

,9737

,7657

,9758

,9747

,8990

,9490

,9609

,9099

,9546

,9660

,9546

,9604

,9496

,5323

,5115

,4137

,5749

,5971

,5655

,5817

,5938

,8208

,8303

,8494

,8779

,8494

,8970

,8775

,8684

,7810

,8174

,8045

,8494

,8362

,8348

,8406

,8464

,7468

,7264

,4375

,5343

,2377

,5403

,1843

,2191

,6826

,8809

,8809

,9045

,8977

,9062

,9009

,9023

,5014

,7178

,5507

,6822

,6630

,6932

,6740

,6548

,6029

,5971

,5652

,6319

,5855

,6464

,6551

,6609

,8210

,8377

,7963

,8592

,6525

,8607

,8103

,6556

,3120

,6840

,6930

,7100

,6920

,7170

,6950

,6450

,6610

,9115

,8092

,8461

,8832

,8546

,8631

,9060

,7542

,7579

,7615

,7892

,8314

,8000

,8036

,8387

,8379

,7779

,7779

,7615

,9768

,7686

,7802

,9584

,5713

,8567

,5313

,7160

,6113

,7400

,7660

,7280

,9084

,9082

,8553

,8845

,8261

,8916

,9008

,8640

,6625

,5974

,6320

,6970

,6971

,7013

,6948

,6971

,6039

,8699

,6681

,7744

,7501

,8028

,8516

,7987

,2060

,7305

,7413

,7266

,7674

,7414

,7567

,7829

,6604

,6604

,6604

,6663

,7844

,7120

,7284

,7384

,9526

,9595

,9193

,9632

,9631

,9596

,9579

,9579

,6731

,7662

,6809

,7620

,7272

,7698

,7501

,7411

Tabla 7. 3 parte de test

34

0 1 0 (IS) 0 1 1 (IFS)
op = 2

abalone
autos
balance
car
cleveland
contraceptive
dermatology
ecoli
glass
hayes-roth
iris
led7digit
letter
newthyroid
pageblocks
penbased
satimage
segment
shuttle
tae
thyroid
vehicle
vowel
wine
yeast
appendicitis
australian
automobile
banana
bands
bupa
crx
german
ionosphere
mammographic
monk-2
movement_libras
phoneme
saheart
sonar
spectfheart
titanic
wdbc
MEDIA

op = 2

1 1 0 (IS)
op=1(disimil.)

1 1 1 (IFS)

op = 2

op=1(disimil.)

IS-REFS

op = 2

op = 1

,8368

,8511

,7471

,8501

,9064

,9093

,8102

,8806

,8853

,8997

,8978

,9119

,8949

,8774

,9880

,9856

,9872

,9888

,9852

,9856

,9884

,9727

,9779

,9780

,9845

,9769

,9782

,9721

,9074

,9756

,9806

,9798

,9815

,9747

,9065

,9732

,9747

,9840

,9881

,9812

,9863

,9701

,9672

,9497

,9756

,9756

,9756

,9742

,9672

,9554

,9621

,9725

,9688

,9762

,9792

,9547

,9089

,8867

,9451

,9393

,9510

,9334

,8984

,7354

,7766

,9091

,9053

,9167

,9053

,7921

,9600

,9667

,9667

,9667

,9667

,9683

,9600

,9606

,9548

,9664

,9685

,9678

,9726

,9535

,8380

,8999

,8510

,8764

,8821

,8828

,8542

,9558

,9430

,9767

,9779

,9744

,9756

,9500

,9726

,9790

,9881

,9900

,9904

,9886

,9713

,9552

,9504

,9630

,9609

,9666

,9661

,9575

,9635

,9681

,9775

,9775

,9813

,9806

,9654

,9728

,9817

,9869

,9887

,9868

,9886

,9753

,9936

,9951

,9976

,9976

,9977

,9975

,9934

,8989

,9107

,9188

,9089

,9405

,9206

,9040

,9823

,9708

,9924

,9920

,9931

,9924

,9826

,9368

,9439

,9699

,9722

,9770

,9708

,9294

,8003

,8465

,7760

,8439

,8644

,8389

,8025

,9649

,9677

,9775

,9761

,9761

,9663

,9635

,9715

,9727

,9850

,9872

,9774

,9830

,9742

,8631

,8326

,9623

,9646

,9599

,9646

,8561

,9772

,9830

,9902

,9909

,9938

,9924

,9808

,8790

,8903

,9025

,8946

,8979

,9009

,8868

,9924

,9928

,9930

,9950

,9929

,9942

,9917

,9479

,9390

,9836

,9829

,9849

,9795

,9493

,9536

,9710

,9841

,9790

,9819

,9797

,9601

,9885

,9916

,9935

,9916

,9943

,9935

,9874

,9813

,9808

,9950

,9945

,9925

,9928

,9833

,9672

,9601

,9801

,9793

,9850

,9822

,9644

,9831

,9883

,9937

,9934

,9943

,9931

,9825

,9468

,9676

,9890

,9826

,9861

,9797

,9306

,8036

,8341

,8404

,8258

,7794

,8298

,8058

,9928

,9933

,9881

,9926

,9824

,9891

,9929

,9832

,9881

,9892

,9892

,9897

,9881

,9848

,9146

,8870

,9688

,9796

,9820

,9844

,9002

,9363

,9841

,9869

,9860

,9897

,9888

,9298

,9956

,9967

,9972

,9968

,9977

,9976

,9959

,9706

,9925

,9921

,9952

,9938

,9947

,9692

,9379

,9453

,9582

,9622

,9647

,9637

,9378

Tabla 8. Reduccin de instancias

35

0 0 1 (FS) 0 1 1 (IFS)
op = 2

abalone
autos
balance
car
cleveland
contraceptive
dermatology
ecoli
glass
hayes-roth
iris
led7digit
letter
newthyroid
pageblocks
penbased
satimage
segment
shuttle
tae
thyroid
vehicle
vowel
wine
yeast
appendicitis
australian
automobile
banana
bands
bupa
crx
german
ionosphere
mammographic
monk-2
movement_libras
phoneme
saheart
sonar
spectfheart
titanic
wdbc
MEDIA

op = 2

1 0 1 (FS)
op=1(disimil.)

1 1 1 (IFS)

op = 2

op=1(disimil.)

op = 2

,6250

,7500

,7250

,5500

,8000

,7500

,8080

,8640

,8480

,8240

,8800

,8640

,0000

,0000

,0000

,0000

,0000

,0000

,1667

,3000

,0000

,0000

,1667

,1667

,5846

,7538

,6769

,6462

,7538

,8000

,4222

,6667

,4222

,4000

,5778

,6667

,5941

,7941

,7588

,7471

,8176

,8176

,2286

,5429

,2286

,1429

,6000

,5429

,4667

,6444

,4000

,4667

,7111

,6444

,2500

,2500

,2500

,2500

,2500

,2500

,5500

,5500

,5000

,4500

,7500

,5500

,0286

,0571

,0286

,0286

,0571

,1714

,4375

,4500

,3875

,3500

,5125

,4750

,3200

,4800

,4800

,2400

,6400

,4800

,6600

,9000

,7400

,7000

,9000

,8800

,2125

,3750

,2125

,2750

,5125

,4000

,5611

,8667

,7056

,7556

,9278

,8889

,6421

,7895

,7053

,7263

,8421

,8211

,7778

,7778

,7778

,7556

,7778

,7778

,2400

,2800

,3200

,1200

,3600

,3600

,7238

,9048

,7905

,7905

,9143

,9048

,5556

,6333

,6222

,6222

,8222

,6889

,3538

,4462

,3846

,3692

,4923

,5231

,4769

,6769

,5692

,6000

,7538

,6923

,1500

,3750

,1500

,2000

,4000

,4000

,5429

,7714

,6857

,5714

,8000

,7429

,5000

,8000

,6429

,5143

,8429

,8000

,8080

,8960

,8400

,8480

,8800

,8960

,0000

,0000

,0000

,0000

,0000

,0000

,5684

,8421

,7263

,6842

,8737

,8421

,4667

,6333

,4667

,3000

,6667

,6000

,5733

,9067

,6133

,5467

,9333

,8800

,5400

,8400

,8100

,7900

,8800

,8600

,7333

,9030

,7939

,8242

,9152

,9091

,4000

,6800

,2800

,2800

,4800

,4400

,5000

,6667

,5000

,5000

,5333

,5000

,7222

,8578

,8400

,8844

,7533

,8622

,0000

,3200

,0400

,0400

,1200

,1200

,4667

,7111

,7778

,5778

,7333

,6667

,6533

,8367

,7767

,8100

,9367

,9467

,7182

,9409

,9227

,8864

,9727

,9591

,0667

,3333

,0667

,0667

,2667

,2667

,6600

,8733

,8467

,8400

,9000

,8933

,4594

,6265

,5189

,4878

,6444

,6209

Tabla 9. Reduccin de caractersticas

36

000
op = 2

abalone
autos
balance
car
cleveland
contraceptive
dermatology
ecoli
glass
hayes-roth
iris
led7digit
letter
newthyroid
pageblocks
penbased
satimage
segment
shuttle
tae
thyroid
vehicle
vowel
wine
yeast
appendicitis
australian
automobile
banana
bands
bupa
crx
german
ionosphere
mammographic
monk-2
movement_libras
phoneme
saheart
sonar
spectfheart
titanic
wdbc
MEDIA

0 0 1 (FS) 0 1 0 (IS) 0 1 1 (IFS)

op = 2

op = 2

op = 2

100
op=1(disimil.)

op = 2

,0000

9,8077

44,0373

20,0753

507,3769

196,7624

,0000

4,9221

15,0337

5,5341

146,8496

107,6020

,0000

14,7969

28,4977

25,0214

634,7260

175,3677

,0000

102,1086

186,1277

177,1597

4856,2456

2712,4402

,0000

25,5912

10,9296

12,3945

414,9386

315,0883

,0000

174,4710

278,7045

138,7051

4970,8320

2526,9671

,0000

61,5419

64,0083

32,6661

1017,0798

479,7530

,0000

12,5276

22,2832

16,2643

354,9043

191,5462

,0000

3,8427

9,3735

6,0509

191,7954

82,6022

,0000

,9223

1,9182

1,2543

47,8179

21,9009

,0000

,9019

3,4169

2,7426

39,0014

14,3812

,0000

28,6441

30,0669

20,6148

512,0224

289,7101

,0000

2400,0478

8022,0596

2169,2395

17520,7754

26516,9742

,0000

5,0479

4,3726

3,9658

179,2466

56,4509

,0000

30,3882

35,2533

20,4647

1431,5182

540,5057

,0000

367,0100

173,9796

139,3809

6521,0630

2192,6215

,0000

448,3638

412,9722

94,5824

12200,4854

8829,3580

,0001

1372,3701

821,2018

384,0710

22231,5458

13537,8436

,0000

253,4925

369,3175

154,1048

10956,5868

5413,5625

,0000

2,8920

8,2188

7,6051

73,1905

37,7209

,0000

90,3873

85,8477

40,1716

2716,6718

1536,8240

,0000

184,1934

184,6907

94,9741

4929,6968

1657,9958

,0000

314,4147

412,4084

251,3974

4703,7129

1560,5427

,0000

5,9700

7,2813

4,3148

23,0732

29,0124

,0000

144,0330

196,4721

172,7970

4936,9201

2320,7494

,0000

2,0715

1,2599

1,1705

56,2256

26,0051

,0000

61,7753

68,9686

46,1077

3256,9205

2157,4592

,0000

6,8845

24,1131

9,9508

681,8463

129,9850

,0001

953,9026

1180,9215

899,4705

37105,2413

19088,3556

,0001

69,5917

64,4455

26,1513

1317,6771

763,3577

,0000

14,9226

27,8686

12,4408

669,3793

381,1384

,0000

102,9428

73,1614

53,0185

2712,9269

1526,9080

,0000

225,7394

180,7393

101,0018

5059,9277

2697,2361

,0000

21,4857

41,3117

17,4694

1184,5495

499,6242

,0000

28,2509

35,0740

30,2243

985,2631

634,4334

,0000

10,0645

21,8918

11,6495

9,0955

1,4236

,0000

101,4035

272,5198

115,7750

3569,9399

1621,6520

,0001

1511,9630

1113,7360

1034,1779

31795,6968

19698,1368

,0000

36,5859

29,8422

15,6771

692,9448

270,2852

,0000

17,6055

48,8767

14,5248

875,0564

372,5018

,0000

23,7857

27,3556

20,9028

1223,8515

445,8385

,0001

301,7542

408,0396

279,6771

7029,2146

2659,3995

,0001

108,1977

81,9997

37,5489

2913,2572

1141,3071

,0000

224,5957

351,8744

156,3370

4726,9091

2917,6588

Tabla 10. 1 parte del tiempo de ejecucin

37

1 0 1 (FS)
op=1(disimil.)

abalone
autos
balance
car
cleveland
contraceptive
dermatology
ecoli
glass
hayes-roth
iris
led7digit
letter
newthyroid
pageblocks
penbased
satimage
segment
shuttle
tae
thyroid
vehicle
vowel
wine
yeast
appendicitis
australian
automobile
banana
bands
bupa
crx
german
ionosphere
mammographic
monk-2
movement_libras
phoneme
saheart
sonar
spectfheart
titanic
wdbc
MEDIA

253,1467

1 1 0 (IS)

op = 2

op=1(disimil.)

1 1 1 (IFS)

op = 2

op=1(disimil.)

IS-REFS

op = 2

op=1(disimil.)

153,8032

226,6090

86,8633

57,2578

33,4802

113,6960

32,8287

22,3855

43,6806

16,5462

20,6059

12,8221

36,6209

725,5165

266,4028

43,4454

32,1254

46,8285

33,6793

33,8669

4349,6204

2428,9719

290,0153

119,5605

245,7184

130,8577

290,0931

128,7292

89,7000

26,4050

15,8672

16,3368

13,3013

32,4942

4001,0819

2234,6676

374,2146

163,6182

219,4621

101,1941

363,3729

527,6622

339,7815

80,0011

47,9508

35,9098

23,2348

77,4344

313,3050

167,9569

33,8944

20,7830

23,1164

16,7712

31,9999

136,1953

55,5344

27,7486

15,3582

17,0214

12,0372

27,0519

39,8466

14,8946

16,7845

9,6313

14,1640

9,0398

7,6868

30,5320

14,8083

10,7548

8,4133

10,2357

8,3174

7,0624

419,9818

269,1245

42,5205

30,7033

42,2508

31,1149

45,8651

7618,0388

6127,4751

1717,2462

949,2825

932,8859

570,3734

2205,2858

111,3482

64,5703

25,9411

13,3524

15,1204

12,0497

11,2867

502,6443

274,1000

59,2141

32,7879

31,5034

20,0809

56,2683

4889,2053

2021,0430

486,4332

189,4744

309,6033

144,6401

375,3666

4330,7166

2406,4176

423,3307

230,0560

116,3311

51,9650

300,8770

6108,7265

3365,7141

688,7395

345,9016

236,2165

114,4656

1104,9349

4210,2764

3310,1163

233,7422

156,1165

154,0057

90,7999

417,1480

65,6479

37,6704

20,3068

12,7785

15,8249

11,3215

14,5789

706,6560

422,3182

68,8185

44,7919

30,5725

26,3987

143,2791

2166,2344

956,9749

419,2985

142,4844

132,3416

70,3964

320,8571

2781,2122

1289,9479

816,9433

313,0686

361,3155

157,3704

641,9448

74,6666

38,6512

20,7569

12,1851

13,5038

9,3612

11,0214

4280,5538

2001,9954

356,7782

118,5345

276,5090

95,9513

286,6762

27,5117

17,1175

13,1002

7,8663

9,3017

7,3934

7,4527

1259,2269

1083,1385

92,8649

52,6900

36,6561

35,8528

104,8167

75,1850

40,9805

61,4843

26,1370

26,3878

13,6156

55,2745

31848,3305 19448,9245

808,9641

388,0785

813,9277

397,5476

677,4230

600,0215

427,4950

79,8101

40,0096

28,4261

19,0437

54,2720

254,5181

205,7770

32,1094

20,1733

20,6440

15,8778

23,5723

1113,0276

717,0562

83,5258

48,8986

27,3497

29,7393

86,3239

1285,5001

868,2358

127,3730

73,2749

55,2742

35,1322

243,7799

318,9405

144,8173

68,7597

31,5680

25,6925

14,9033

76,4751

706,9613

394,1448

40,7818

29,9213

38,0889

30,8903

60,7798

307,2800

141,3720

35,9680

24,0899

23,1186

17,1008

38,5620

1286,0267

315,7205

899,7967

312,7669

317,5363

91,6273

726,1824

30211,4373 17070,2477

1164,9737

560,7880

1141,5886

557,6459

1003,1236

204,1633

42,9278

21,6873

26,5359

19,0976

36,8505

266,0255

95,0032

68,2308

30,6531

25,0565

15,3874

117,6829

184,2741

108,3579

60,0533

26,7587

24,5359

14,0502

93,4272

6433,8817

2631,7854

218,0250

225,0149

230,5598

186,2466

154,1642

629,4280

260,0160

87,1613

38,3740

33,8423

18,8610

235,1503

2928,3624

1687,1949

245,1054

118,3020

146,0271

77,2334

250,0484

307,6342

Tabla 11. 2 parte del tiempo de ejecucin

38

5.3.

Test estadsticos

En las tablas anteriores se muestran los resultados obtenidos por cada mtodo en
cada dataset. Tambin se muestra la media obtenida, pero con estos valores no
podemos decir con certeza si un mtodo es mejor que otro. Para ello se van a utilizar
los test explicados en la seccin 4.4.
La comparativa va a constar de 4 fases:
1. Pesos y disimilitudes: En esta fase, vamos a comparar cada variante de pesos
con la correspondiente variante de disimilitudes. Primero comparamos con el
test de Wilcoxon cada una de las variantes de pesos con la correspondiente de
disimilitudes. Luego con la mejor de seleccin de instancias (entre pesos y
disimilitudes), la comparamos con la de seleccin de instancias y disimilitudes
en paralelo. En este punto tenemos 4 mtodos ganadores. Por ultimo
utilizamos el test de Friedman para determinar el mejor de los 4.
2. KNN original: En esta fase utilizamos el test de Friedman para determinar que
mtodo es mejor entre las variantes del KNN original. Se comparan KNN
original, KNN original + seleccin de instancias, KNN original + seleccin de
caractersticas y KNN original + seleccin de instancias + seleccin de
caractersticas.
3. Mejor de KEEL: En esta fase, vamos enfrentar los mtodos de KEEL para ver
cul es el mejor. Primero realizamos el test de Friedman para todos los
mtodos de seleccin de caractersticas (CW, FS-GGA, FS-SSGA). Luego
hacemos lo mismo para los de seleccin de instancias (IS-AllKNN, IS-CHC, ISENN, IS-RNG, IS-SSMA). Por ultimo hacemos un test de wilcoxon entre el mejor
de seleccin de caractersticas y el mejor de seleccin de instancias.
4. Final: Aqu ya tenemos 3 finalistas, 1 por cada fase. Por lo tanto realizamos un
test de Friedman entre los finalistas y ese ser el mtodo elegido como mejor.
Pero aparte de estas comparativas, se va a comparar el algoritmo propuesto con el
algoritmo KNN original, ya que uno de los objetivos era ver si mejorbamos o no. Para
ello se va a utilizar el test de Wilcoxon en cada una de las variantes.
El la figura 7 se muestran todas las comparativas realizadas, con los resultados, de
una forma ms visual. Cada camino de colores llega hasta una comparativa donde solo
sale el mejor. Los colores de estos caminos no significan nada, los caminos se han
coloreado para que se pueda seguir mejor la evolucin. En la ltima comparativa, al
mtodo ganador se le ha etiquetado con la palabra GANADOR.
Como se muestra en la figura 5, los valores contenidos en los recorridos hacen
referencia a los rangos obtenidos en los test. El test de Wilcoxon si la comparativa es
entre dos mtodos y el de Friedman cuando son ms.
39

En la figura 6, se muestran los valores fuera de los recorridos. Estos son los es comentados en la seccin 4.4. Ya se ha dicho que cuando estos valores son menores
que 0.05, se dice que hay diferencias estadsticas. En este caso, cuando se cumple esta
condicin, el aparece en negrita.

Figura 5. Diferentes de rangos

Figura 6. Diferentes pvalor-es

40

Fase 1: Pesos y disimilitudes

618
329 0.0874
575
371 0.2264
416 0.4841
530
477
470 0.9535

Disimilitudes
Pesos
Disimilitudes
KNN + FS
Pesos
Disimilitudes
KNN + IFS
Pesos
Disimilitudes
KNN + IS
Pesos

KNN

Fase 2: KNN original

Fase 3: Mejor de KEEL

Fase 4: Final

78,9
85,57 1.000
97,97 0.22735
83,57 1.000

523
423 0.5460

KNN disimilitudes + IS paralelo

KNN

88,44 0.40890
97,3 0.10877
74,81
85,44 0.40890

KNN KNN + IS
ORIGINAL KNN + FS
KNN + IFS

FS
KEEL
IS

CW
FS-GGA
FS-SSGA
IS-AllKNN
IS-CHC
IS-ENN
IS-RNG
IS-SSMA

53,73 GANADOR
65,98 0.12884
75,29 0.01499
71,87 0.00018
41,72
81,41 0.00000
105,88 0.70928
133,73 0.01075
93,47
96,09 0.84471
110,83 0.58702

393 0.3340
553

Figura 7. Todas las comparativas

Como se ha dicho antes, hay cuatro fases. A continuacin se van a explicar los
resultados de cada fase:
1. Pesos y disimilitudes: Como se ve en la figura 7, la opcin de usar
disimilitudes gana a todos los de pesos excepto cuando usamos KNN con
seleccin de instancias y caractersticas. Pero ninguno de los vencedores es
estadsticamente mejor que otros. Comparando el mejor de seleccin de
instancias (que es el de disimilitudes) frente al paralelo, gana el de serie,
pero como antes, no estadsticamente. Por ultimo cuando hacemos
Friedman entre los ganadores, gana el KNN con disimilitudes sin ningn tipo
de seleccin. Como antes sin diferencias estadsticas. Este pasa a la fase
final.
2. KNN original: En este caso, hacemos un Friedman entre las 4 variantes del
algoritmo KNN original. Como se ve, el que menos rangos tiene es KNN con

41

seleccin de caractersticas, por lo tanto es el ganador, pero sin diferencias

estadsticas.
3. Mejor de KEEL: En este caso, primero hacemos Friedman entre todos los de
seleccin de caractersticas. En la imagen se ve como el mejor es FS-GGA, y
adems es estadsticamente mejor que los otros dos mtodos. Luego
hacemos Friedman con los de seleccin de instancias, y el que menos
rangos obtiene es IS-ENN. En este caso, solo podemos decir que IS-ENN es
mejor estadsticamente que IS-CHC. Por ltimo, entre los ganadores (FSGGA y IS-ENN), hacemos un Wilcoxon. En la imagen se ve que el IS-ENN
obtiene ms rangos, por lo tanto es mejor, pero no estadsticamente.
4. Final: Para esta fase nos llegan los mejores de las fases anteriores. Tenemos
los mtodos: KNN con disimilitudes, KNN original con seleccin de
caractersticas y IS-ENN. Haciendo un test de Friedman entre todos vemos
que el que menos rangos tiene es el algoritmo propuesto (KNN con
disimilitudes), por lo tanto es el ganador. Decir que este es
estadsticamente mejor que el algoritmo IS-ENN.

Tambin se ha dicho que se quiere comparar el algoritmo propuesto en todas

sus variantes, contra el algoritmo KNN original.
A. KNN disimilitudes vs KNN original: El algoritmo KNN original obtiene 250
rangos y el algoritmo KNN disimilitudes obtiene 696. Por lo tanto el de
disimilitudes es mejor. El es 0.0060 por consiguiente, es mejor
estadsticamente.
B. KNN disimilitudes + seleccin de caractersticas vs KNN original + seleccin
de caractersticas: El KNN original obtiene 433 rangos y el KNN con
disimilitudes 513. El es 0.5959 por lo tanto el de disimilitudes es
mejor pero no estadsticamente.
C. KNN disimilitudes + seleccin de instancias vs KNN original + seleccin de
instancias: El KNN original obtiene 255 rangos y el de disimilitudes 690. El
es 0.0086, por lo tanto el de disimilitudes es mejor estadsticamente.
D. KNN disimilitudes + seleccin de instancias y caractersticas vs KNN
original + seleccin de instancias y caractersticas: El KNN original obtiene
449 rangos y el de disimilitudes 497. El es 0.8055, por lo tanto el de
disimilitudes es mejor, pero no estadsticamente.

Se ve que el mtodo propuesto es mejor que el original en todas las variantes,

pero estadsticamente nicamente en dos de las cuatro.

42

6. Conclusions y lnas futuras

En este proyecto hemos propuesto un sistema de clasificacin basado en el
algoritmo de los k vecinos ms cercanos. Este sistema aprende ciertos parmetros que
son utilizados para calcular la distancia entre los ejemplos. Adems de la distancia,
tambin se han implementado mtodos de seleccin de instancias y/o caractersticas
tanto para el algoritmo KNN original como para el propuesto.
Para comparar los resultados obtenidos hemos llevado a cabo una serie de test
estadsticos y los hemos analizado en profundidad. En resumen las conclusiones
obtenidas son las siguientes:
-

El mtodo que hemos propuesto obtiene mejores resultados que el mtodo

original en todas las variantes propuestas (seleccin de instancias y/o
caractersticas) en los datasets utilizados.
El mtodo propuesto es estadsticamente mejor que el original, y la
combinacin de nuestro mtodo con seleccin de instancias, tambin es
estadsticamente mejor que el original con seleccin de instancias.
El mtodo propuesto, es estadsticamente mejor que el mejor de los mtodos
implementados en KEEL.
El mtodo propuesto, obtiene mejores resultados que el algoritmo KNN
utilizando pesos por cada atributo.

En lo que a lneas futuras se refiere, este proyecto tiene varias ya que los
resultados obtenidos son ms que favorables:
-

La primera y ms clara de toda ellas es la de realizar el estudio con diferentes

valores para el parmetro ( = 3, = 5, ).
La segunda es la de realizar el estudio con automorfismos con construcciones
diferentes.
Utilizar diferentes tipos de agregaciones.
Utilizar diferentes funciones objetivo.
Estudiar el comportamiento del nuevo mtodo en el problema de las clases no
balanceadas.

43

7. Bibliografa
[1] J. Derrac, S. Garca and F. Herrera, IFS-CoCo: Instance and Feature selection
based on cooperative coevolution with nearest neighbor rule, Pattern
Recognition, 2010, pag. 2082-2105
[2] M. Galar, A. Fernandez, E. Barrenechea, F. Herrera, Empowering difficult
classes with a similarity-based aggregation in multi-class classification
problems, Information Sciences, vol. 264, 2014, pag. 135-157.
[3] M. Steinbach and P. Tan, kNN: k-Nearest Neighbours, The Top Ten Algorithms
in Data Mining (Chapman & Hall/CRC Data Mining and Knowledge Discovery
Series), 2009.
[4] H. Bustince, E. Barrenechea, M. Pagola y V. Mohedano, Relacin entre las
funciones de disimilaridad restringida y las funciones de equivalencia
restringida. In XIII Congreso Espaol Sobre Tecnologas y Lgica Fuzzy, 41-46,
Ciudad Real, Espaa, 2006.
[5] S. Garca and F. Herrera, Evolutionary Undersampling for Classification with
Imbalanced Datasets: Proposals and Taxonomy, Evolutionary Computation,
vol. 17, no. 3, 2009, pag. 275-306.
[6] M. Galar, A. Fernndez, E. Barrenechea, H. Bustince and F. Herrera, A Review
on Ensembles for the Class Imbalance Problem: Bagging-, Boosting-, and
Hybrid-Based Approaches, IEEE Transactions on Systems, Man, and
Cybernetics Part C: Applications and Reviews, vol. 42, no. 4, 2012.

44