Desde hace unas fechas quería escribir algunas reflexiones sobre la práctica que me mandaron para una asignatura de Inteligencia Artificial en la que vimos un método de clasificación conocido como LVQ (Learning Vector Quantization). El objetivo fue clasificar un conjunto de datos de 8124 hongos almacenados en un fichero .csv y mostrar su precisión de comestibilidad o venenosidad.
Antes de comenzar a leer, adjunto los ficheros de la práctica.
El método de clasificación que utilizamos en esta práctica es el Vector Quantization que fue propuesto por Kohonen con el fin de representar la frontera de decisión entre clases, más que la distribución de clases. En este post expongo la memoria de mi práctica pensando que quizá puede serle util a cualquiera de vosotros.
El fichero .csv fue extraído del repositorio de la Universidad de California (USA), este conjunto proviene de sampleos de Estados Unidos y fueron recogidos en el año 1981 por The Audubon Society Field Guide to North American Mushrooms. Esta muestra se compone de hongos de la familia de los Agaricus y Lepiota. Cada especie se identifica como comestible (e), venenosa (p) o como desconocida (y por tanto no recomendable).
Para esto, parte de un conjunto de prototipos iniciales que modifica mediante las siguientes reglas de actualización: dado un objeto x, el prototipo mc, más cercano a éste, es actualizado acercándolo al objeto si es clasificado correctamente por el prototipo, o alejándolo en caso contrario. El efecto de la actualización es mover los prototipos hacia los patrones de su propia clase, y alejarlos de los de otra clase.
Hemos desarrollado un programa en Java que realiza lo siguiente:
1- Extrae los elementos del fichero mushroom.csv (con lo que el fichero csv es necesario que se encuentre en el mismo directorio del ejecutable) y los almacena en un vector multidimensional de 8125 filas y 23 columnas:
8125 = 8124 setas + 1 primera fila que contiene los nombres de cada atributo. Puede ser un error bastante común el declarar el vector de 8124 en lugar de 8125, de esta forma no trataríamos a la última seta. Este vector será de tipo String.
2- Con el vector multidimensional obtenido llamado “muestra”, realizamos un proceso de binarización, tras el cual conseguiremos un vector multidimensional de 8124 filas (eludimos la primera fila de los nombres de los atributos) y de 128 columnas (una columna por cada nuevo atributo). Este vector será de tipo númerico y contendrá valores de 0.0 en todas sus posiciones inicialmente que serán cambiadas a 1.0 – a excepción de un caso “missing” que explicamos más adelante- cuando se produzca una coincidencia. Este proceso lo realizamos de la manera siguiente:
3- Tras ello ya tenemos la matriz “boletsbinari” con los valores numéricos pertinentes para realizar nuestras operaciones. En este momento, indicamos cuantas setas y cuantas particiones compondrán nuestro proceso de training, una vez definidos, calculamos los centroides de nuestra matriz boletsbinari. Para ello crearemos un vector llamado centroides compuesto por las 10 particiones y los 128 atributos. Y calculamos los centroides de cada partición almacenándolos en este nuevo vector.
El proceso de binarización se realiza “manualmente”, es decir, mediante sentencias condicionales (“if”), de este modo iremos formando nuestra nueva matriz, ejemplo:
//veil-color: brown=n,orange=o,white=w,yellow=y
if (muestra[j][17].equals("n")) boletsbinari[j-1][91] = 1.0;
if (muestra[j][17].equals("o")) boletsbinari[j-1][92] = 1.0;
if (muestra[j][17].equals("w")) boletsbinari[j-1][93] = 1.0;
if (muestra[j][17].equals("y")) boletsbinari[j-1][94] = 1.0;
Esto quiere decir, que si encuentra el carácter “n” en la columna número 17, asigne un valor de 1.0 en la columna 91 de la nueva matriz, sin embargo si encuentra el carácter “o”, deberá asignar un valor de 1.0 pero en la siguiente columna de la nueva matriz y así con todo el muestreo.
4- Con nuestro vector “centroides” completo, podremos comenzar nuestro proceso con el Vector Quantization, que veremos un poco más adelante en las respuestas a los puntos de la práctica.
2. Explicación de como hemos tratado la función de factor de aprendizaje:
3. Explicación general sobre el algoritmo implementado, explicando todos aquellos detalles que consideremos relevantes y las decisiones de diseño tomadas.
5- Por último, clasificaremos los resultados y los mostraremos.
Pasamos, por tanto, a contestar a los puntos propuestos de la práctica:
1. Explicación de como hemos generado los conjuntos de trainning y test.
Nuestro conjunto de training está formado por 6770 setas divididas en 10 particiones resultando 677 setas por partición, se componen desde la primera seta hasta la 6770, con ellas realizamos el cálculo de los centroides.
Nuestro conjunto de test lo forman las setas restantes a partir de la 6770, esto es, 8124-6770=1354 setas (que vendrían a componer las dos siguientes particiones del training: 677*2=1354 setas).
2. Explicación de como hemos tratado la función de factor de aprendizaje:
Hemos declarado una variable double con valor de 0.5, a la cual en cada iteración le iremos restando 0.0005, de este modo tras 1000 iteraciones, nuestra n(t) será igual a 0 y el proceso finalizará:
Haré 1000 iteraciones de la siguiente forma:
1ª iteración: n(0) = 0,5
2ª iteración: n(1) = 1- (10-3)\2 = n(0) -0,0005
3ª iteración: n(2) = n(1) – 0,0005
Y así sucesivamente hasta n(1000) = 0
De este modo la primera neurona escogida ( la más próxima al primer objeto ) se aproximará al primer objeto y el proceso será convergente por que nu =0 al final ).
En nuestro programa hemos llamado “c” a nuestro factor de aprendizaje.
double c=0.5;
3. Explicación general sobre el algoritmo implementado, explicando todos aquellos detalles que consideremos relevantes y las decisiones de diseño tomadas.
Como hemos mencionado previamente, las 6770 setas las divido en 10 particiones (porque ese nº es multiplo de 10 ). Por tanto, cada partición posee 677 setas.
Las primeras 667 setas formaran un grupo cuya neurona o centroide es la media aritmética de sus valores.
Las siguientes 677 setas formaran el segundo grupo, con su media aritmética como centroide, y así sucesivamente.
Conocidos los 10 centroides iniciales p1 , p2 , ….. p12 y tomando como primer objeto la una seta aleatoria comprendida en el rango seta 1 hasta seta 5770 ya que se toma desde la seta aleatoria hasta la seta aleatoria + 1000, empezará el proceso iterativo con n(0) = 0.5
1º busco todas las distancias euclídeas de la seta aleatoria seleccionada con cada uno de los 10 centroides, les llamo
DP(1,1) , DP(1,2) , DP(1,3) , … , DP(1,10).
2º Escojo la menor de ellas , supongo que es DP(1,n) . Eso significa que la seta aleatoria se encuentra en la partición n.
3º Ahora viene un proceso de acercamiento del centroide pn a la seta 1
El nuevo pn:= antiguo pn + n(0)( seta1 – antiguo pn)
4º Además del acercamiento, opcionalmente viene la penalización , es decir , los demás centroides , se van a alejar de la seta aleatoria del siguiente modo:
nuevo pj := antiguo pj - n(0)( seta1- antiguo pj)
5º Los nuevos centroides les vuelvo a llamar p1 , p2 , ….. p10 y tomo la siguiente seta. Con esta segunda seta, vuelvo al apartado 1 y repito la operación hasta que mi n(t) sea 0, es decir, 999 veces más.
Tras el proceso, podré observar el porcentaje de setas de clase p y de clase e que posee cada grupo y cuantas de ellas se han clasificado bien y cuantos no para obtener la precisión.
Al principio de la práctica, con el objetivo de comprender correctamente los objetivos de la misma y poder comprobar los avances, así como si mi código y programa funcionaban correctamente, Carmen Pellicer me explicó el funcionamiento a través de una tabla de Excel con 12 setas inventadas de 10 atributos cada una, estas 12 setas las convertí en un fichero csv para poder ir desarrollando la práctica. Este ejemplo puede ser descargado desde aquí.
- IA2_prueba_con_12_setas.xls
- setas_sin.class Ejecutable del ejemplo de mis 12 setas sin penalizar.
- setas_sin.java Fuente del ejemplo de mis 12 setas sin penalizar.
- setas_con.class del ejemplo de mis 12 setas con penalización.
- setas_con.java del ejemplo de mis 12 setas con penalización.
- 12setas.csv Archivo csv que contiene las 12 setas.
En el fichero de Excel IA2_prueba_con_12_setas.xls se puede encontrar la muestra con el cálculo de los centroides y distancias euclídeas así como el vector quantization a 10 de las 12 setas. En el primer libro o pestaña se encuentra el ejemplo aplicándole del VQ sin penalización, mientras que en la segunda pestaña se encuentra el mismo ejemplo pero en este caso penalizándolo. En todo momento, se puede consultar el origen de los valores. Confiamos en que todos estos cálculos sean correctos y si los consultores de la asignatura desean utilizarlo en algún momento para ejemplo para próximos cursos no tendremos ningún problema en ello, pensamos que podría ser de utilidad.
En nuestro ejemplo, aplico el proceso a 12 setas inventadas definidas cada una de ellas con 10 digitos binarios, con una partición formada por tres centroides p1 ,p2 ,p3 y un factor de aprendizaje inicial n(0) = 1 que se decrementará cada vez en 0,1
Penalización a las clases no ganadoras.
Tras el acercamiento que realizamos a los centroides ganadores en cada iteración, realizamos un alejamiento o penalización al resto de centroides. Así de esta forma, si la partición a la que pertenece la mínima distancia euclidea es, por ejemplo, la número
3. Cambiaremos el centroide de la partición 3 y alejaremos al resto:
En ambos casos, tanto en nuestro ejemplo de las 12 setas como en la práctica de la asignatura hemos visto que la penalización es realmente fuerte para los centroides no ganadores, esto hace que el alejamiento inicial sea tan grande que, unido con el acercamiento del centroide ganador, las setas se agrupen hacia la partición inicial quedándose inamovibles en el resto de iteraciones.
Por ello presentamos dos versiones del programa, una versión en la que no penalizamos a las clases perdedoras y otra versión en las que sí penalizamos. A continuación mostramos un ejemplo de no penalización de centroides, para ello explicamos los parámetros que se muestran:
C: Es el decremento de n(t).
iSeta: Nos sirve para contar de 0 a 1000 setas ordinalmente (1ªseta,2ªseta,etc). Sin tener en cuenta
seta: Seta de la muestra comprendida entre la primera seta generada aleatoriamente a la seta aleatoria + 1000.
position: Nos indica a qué partición pertenece la distancia euclidea mínima de entre todas las particiones. Con esta variable acercaremos el centroide.
//Alejamos centroides PENALIZACION
for (int l=0; l<particiones;l++){
if(l!=position){
for (int j=2;j<atributosbin;j++)
{
//Modificamos el centroide:
centroides[l][j]=centroides[l][j]-c*(boletsbinari[seta][j]-centroides[l][j]);
}
}
}
4. Tratamiento de los Valores Nulos.
Los valores nulos se encuentran todos ellos en el atributo 11 llamado Stalk-root, en ello encontramos un ? que nos indica que no se tiene información sobre ese atributo en algunas setas Vector Quantization, hemos elegido darle un valor de 0.5 en este atributo en el momento de la binarización cuando nuestro programa encuentra algún carácter “?”.
5. Precisión y tiempo de cálculo del algoritmo.
Precisión:
Al finalizar el programa, éste muestra la precisión obtenida, esto lo realiza analizando la clase de las setas obtenidas en cada una de las particiones tras el cambio de centroides realizado por el vector de quantization. El análisis consiste en contar las setas de una clase y de otra y determinar la partición por el número de setas con la mayor clase obtenida, así pues, si en una partición obtenemos 80 setas comestibles y 20 venenosas, la partición será del tipo comestible y tendría un 80% de precisión.
La pregunta nos indica el tiempo de cálculo del algoritmo, con lo cual el contador lo pondremos justo antes de efectuar el algoritmo y contará hasta que finalice el algoritmo, si lo pusieramos al inicio y final del programa no podríamos tener una referencia del tiempo de coste del algoritmo ya que las impresiones en pantalla variarían muchísimo el tiempo.
Así pues antes del algoritmo hemos puesto un contador:
inicia = 0.0;
inicia = System.currentTimeMillis();
Y lo terminamos de la siguiente forma:
termina = System.currentTimeMillis() – inicia;
Luego, una vez acabado el programa, indicamos el tiempo de ejecución del algoritmo.
Tras las pruebas realizadas, el algoritmo suele tardar alrededor de 2.568 segundos.
Herramientas utilizadas para la realización de la práctica
Hemos desarrollado el programa utilizando el entorno de programación “Eclipse” y la versión 1.6.0 de Java y Eclipse 3.3.1.1
Referencias Consultadas.
