Introducción:
El presente proyecto corresponde a la realización de un proyecto de data-mining, que busca tener una primera experiencia práctica en el uso de herramientas de minado de datos. Para ello, se trabajará utilizando la herramienta Weka, un software hecho en Java, de licencia open source. El problema a abordar, consiste en estudiar la factibilidad de realizar un clasificador de imágenes (fotografías), a partir de información extraída de cada una de éstas, tratando de clasificar cada imagen en una de cuatro categorías pre definidas. Se compararán algoritmos de clasificicación, y se expondrán los resultados al final del trabajo.
Problema: (business understanding)
En la actualidad, el manejo de imágenes se ha hecho cada vez más masivo, a partir de la popularización de los medios fotográficos (cámaras digitales), así como de la difusión de éstas a través de internet. La cantidad de imágenes que existen disponibles, cada día crece más, y surge la necesidad de encontrar formas de extraer algún tipo de semántica, más alla del sólo uso de metadatos (la solución más utilizada hoy en día).
Lo que se quisiera tener, es un medio de catalogar imágenes, lo que permitiría poder realizar agrupaciones, clasificaciones de éstas, para poder realizar mejores búsquedas, tanto en sitios web, como en repositorios privados (por ejemplo, una colección particular de imágenes de algun usuario).
Si bien esta meta podría ser un tanto ambiciosa, se quiere realizar una primera aproximación al problema. Para ello, se propone la siguiente idea: cada imagen será transformada a un conjunto de atributos, extraídos de la información de los colores que la componen. En particular, se utilizará información estadística acerca de las cuatro componentes de color del colorspace CMYK, ampliamente utilizado en la impresión de imágenes.
Herramientas disponibles
Se desea utilizar una herramienta de minería de datos, para realizar el estudio de las imágenes. Entre las opciones disponibles, se revisaron diversas alternativas en el campo del software open source. Entre los programas disponibles, se pueden mencionar los siguientes:
De estas alternativas, se ha seleccionado el software Weka, dado que es quizás la más completa de las opciones, sin caer en la complejidad de Pentaho o Yale. La interfaz que provee es suficiente para los propósitos del proyecto a desarrollar. Además, es el software con mejor documentación disponible en la red. Entre sus principales características, se puede mencionar: - gran cantidad de algoritmos de aprendizaje, herramientas de preprocesado y métodos de evaluación. - interfaces gráficas para la realización de análisis y experimentos. - ambiente para la comparación de algoritmos.
Además de la herramienta de minado de datos, se recurrirá al lenguaje Perl, y al programa ImageMagick (de linux), dedicada al procesamiento avanzado de imágenes, utilizando linea de comandos. Estas serán las herramientas que se usarán para el pre-procesado de los datos (las fotografías).
Datos disponibles (data understanding)
Para realizar la experiencia, se dispuso de una colección de 200 fotografías (parte de la colección personal del autor), las cuales fueron separadas en cuatro grupos, según las categorías definidas para el experimento: {nocturnas, urbanas, gente, paisajes}. Las imágenes fueron elegidas de manera que fueran lo más representativas posibles de cada una de sus categorías. El propósito es que el modelo logre capturar el concepto de la clasificación automática, tratando de emular la metodología utilizada por las personas.
La 'ídea'' es la siguiente: cada categoría debiera presentar ciertas dominantes de color, o intensidad de color (incluído el negro). Según una primera aproximación, se podría esperar lo siguiente:
- nocturnas: dominante negra, con partes claramente amarillas (provenientes de fuentes lumínicas de tungsteno). - urbanas: en general, luminosas, con presencia mayoritaria de color gris. - gente: presencia de color ''piel'', además de menor luminosidad, ya que las fotografías son en general más ''cerradas''. - paisajes: fotografías luminosas, con gran parte de la imagen en azul/celeste (el cielo), y muchas veces, verde.
Las colecciones de imágenes utilizadas, fueron las siguientes:")
Pre-procesamiento de los datos: reducción dimensional (data preparation)
El problema de análisis de imágenes, presenta un primer gran problema: cada instancia (imagen) corresponde, en teoría, a un vector de 3*n componentes, con n el número de pixels de la imagen (esto para el caso de una imagen de 24 bits, en el modelo clásico RGB de representación de imágenes en formato digital). Claramente, realizar la tarea de clasificación sobre vectores de esta dimensión, es un problema irrealizable en la práctica.
La solución que existe para estos casos, es la de aplicar una reducción dimensional, es decir, proyectar cada ejemplar de la entrada (la señal de entrada), en un espacio de menor dimensionalidad. Para esto, existen básicamente dos alternativas: selección de características o extracción de características. El primero caso, corresponde a elegir algunas de las componentes del vector de entrada. Sin embargo, este caso no es aplicable, ya que la dimensión seguiría siendo inmanejable. La segunda opción, es la que será utilizada en este caso, para lo cual se recurrirá a indicadores estadísticos de cada imagen.
El espacio de color de una imagen, corresponde al modelo utilizado en su representación: RGB, CMYK, HSV, entre otros. Una primera aproximación sería utilizar el espacio RGB (el colorspace natural en dispositivos digitales: {red, green, blue}). Sin embargo, se elegirá realizar una transformación de las imágenes, al espacio CMYK {cyan, magenta, yellow, black}. El motivo de esta elección se basa en la posibilidad de contar con al componente negro de manera explícita, lo cual permitirá entender de mejor manera los patrones de las imágenes.
Esta transformación se realizará utilizando un programa en perl, que realizará la transformación del espacio de color. A continuación, el mismo programa obtendrá el conjunto de datos a utilizar, a través de la aplicación ImageMagick (identify), la cual permite extraer la información que será utilizada. Finalmente, se obtendrá para cada archivo de imagen, los siguientes valores: - componente C (cyan) : media y desviación standard - componente M (magenta) : media y desviación standard - componente Y (yellow) : media y desviación standard - componente K (black) : media y desviación standard
Esto arrojará un vector de 8 componentes, lo cual corresponderá a la reducción dimensional buscada.
El programa de preprocesamiento, será ejecutado por separado para cada uno de los cuatro grupos de imágenes (en directorios diferentes). De esta manera, se agregará en cada caso la clase a la cual pertenece cada imagen. Finalmente, se dispondrá de cuatro archivos de texto con el siguiente formato:
{c-mean, c-sd, m-mean, m-sd, y-mean, y-sd, k-mean, k-sd, clase}
200.36,56.4659,216.558,43.2201,230.792,33.534,199.839,56.1583,nocturna
167.537,19.3646,163.186,19.3659,161.588,22.5161,155.203,21.8438,gente
100.051,75.8246,93.5235,69.124,109.475,86.9608,90.9557,69.4633,paisaje
Estos archivos serán combinados, para producir finalmente un conjunto de datos (parcialmente mezclados), que constuirán la entrada al sistema (un archivo de tipo arff, de Weka).
El archivo de entrada, finalmente utilizado, fue el siguiente:
Implementación del modelo: Weka (modeling)
A continuación, se mostrará el proceso seguido para implementar diversos modelos de clasificación, utilizando el software elegido.
Dentro de las opciones principales del software, están el Experimenter (enfocado a análisis estadístico de grandes conjuntos de datos), el KnowledgeFlow (una herramienta fundamentalmente gráfica, para construir esquemas de experimentación usando la GUI provista), y el Explorer. Esta última es la opción elegida, por que se adecua perfectamente a las necesidades del proyecto: cargar un archivo de datos, y desarrollar alguna de las tareas disponibles, utilizando uno de varios algoritmos.
Las tareas disponibles en el sistema, son las siguientes:
La tarea a abordar es la de clasificación. Para ello, en primer lugar se hará la carga de datos a través de un archivo .arff definido previamente (generado por el programa en perl mencionado anteriormente). Esta archivo se compone de 200 registros, divididos en cuatro grupos de 50 elementos. Los datos fueron mezclados para evitar cualquier partición desafortunada al momento de dividir los conjuntos de datos. Una vez cargados los datos, se tiene la siguiente pantalla:
La siguiente etapa, es seleccionar los algoritmos de clasificación a utilizar. Se elegirá un algoritmo de cada una de tres familias distintas disponibles en el software: Redes Bayesianas, MultilayerPerceptron y el Arbol de Decision J48.
Una vez elegido el algoritmo a utilizar, se debe seleccionar el modo de entrenamiento: básicamente, se trata de determinar la forma en que se distribuirán los conjuntos de aprendizaje y de testing. El método elegido, fué el de validación cruzada, utilizando un número de particiones de 10 (la validación cruzada consiste en: dado un número n se divide los datos en n partes y por cada parte, se construye el clasificador con las n-1 partes restantes y se prueba con esa).. esto para cada una de las n particiones.
Resultados
Una vez implementados los diferentes modelos, se obtuvieron los resultados de su ejecución.
Redes Bayesianas: === Classifier model (full training set) === Bayes Network Classifier not using ADTree
Time taken to build model: 0.02 seconds
=== Stratified cross-validation === Correctly Classified Instances 124 62 % Incorrectly Classified Instances 76 38 %
=== Detailed Accuracy By Class ===
Precision Class 0.553 paisaje 0.386 urbana 0.98 nocturna 0.578 gente
=== Confusion Matrix ===
| a | b | c | d | <-- classified as |
|---|---|---|---|---|
| 26 | 19 | 0 | 5 | | a = paisaje |
| 14 | 22 | 0 | 14 | | b = urbana |
| 0 | 0 | 50 | 0 | | c = nocturna |
| 7 | 16 | 1 | 26 | | d = gente |
Red Neuronal: === Classifier model (full training set) ===
Time taken to build model: 11.03 seconds
=== Stratified cross-validation === Correctly Classified Instances 149 74.5 % Incorrectly Classified Instances 51 25.5 %
=== Detailed Accuracy By Class ===
Precision Class 0.619 paisaje 0.629 urbana 0.98 nocturna 0.75 gente
=== Confusion Matrix ===
| a | b | c | d | <-- classified as |
|---|---|---|---|---|
| 39 | 9 | 0 | 2 | | a = paisaje |
| 18 | 22 | 0 | 10 | | b = urbana |
| 0 | 0 | 49 | 1 | | c = nocturna |
| 6 | 4 | 1 | 39 | | d = gente |
Arbol de Decisión: === Classifier model (full training set) === J48 pruned tree
Number of Leaves : 22 Size of the tree : 43
Time taken to build model: 0.08 seconds
=== Stratified cross-validation === Correctly Classified Instances 130 65 % Incorrectly Classified Instances 70 35 %
=== Detailed Accuracy By Class === Precision Class 0.571 paisaje 0.477 urbana 0.962 nocturna 0.564 gente
=== Confusion Matrix ===
| a | b | c | d | <-- classified as |
|---|---|---|---|---|
| 28 | 14 | 0 | 8 | | a = paisaje |
| 13 | 21 | 0 | 16 | | b = urbana |
| 0 | 0 | 50 | 0 | | c = nocturna |
| 8 | 9 | 2 | 31 | | d = gente |
output-bayes
output-perceptron
output-j48
Conclusiones (evaluation)
De los resultados obtenidos en la ejecución de los diferentes modelos, se analizaron algunos indicadores de la salida obtenida en cada caso. Concretamente, se utilizó como medio de comparación, los indicadores de correctitud de instancias clasificadas, el detalle de precisión de clasificación por clases, y la matriz de confusión de cada caso.
De estas observaciones, se puede concluir que el algoritmo que mejor comportamiento tuvo, fue el de Redes Neuronales (el perceptrón multicapa), el cual arrojó un 75% de instancias correctamente clasificadas, versus un 65% y un 62% de los otros dos casos. A su vez, de la observación de la precisión por categorías, se puede comprobar un hecho esperable quizas: la categoría 'ñocturna'', es lejos la que presenta mejores índices. Esto se debería a la fuerte presencia de la componente Black en esta clase de imágenes. A su vez, el peor indicador de precisión se observó en el caso de la categoriía 'úrbana''. Esto puede ser debido a que esta clase de fotogrfías es quizás la de mayor variabilidad: se esperaba encontrar una tendencia hacia la tonalidad gris, sin embargo, los resultados demuetran que el esquema planteado (basado en CMYK) no fue suficiente para realizar la clasificación de esta categoría.
En general, se observa que existe efectivamente una cierta correlación entre los atributos planteados y las clases propuestas. Sin embargo, el resultado sería insuficiente si se toma en cuenta que los ejemplos presentados al sistema, ya eran casos relativamente 'íntencionados''. Existe a su vez un gran conjunto de imágenes cuya clasificación resulta difusa incluso para los humanos. La idea del proyecto era al menos aproximarse a la presencia de patrones en las imágenes, a partir de los datos estadísticos de su espacio de color CMYK.
Como alternativa, para un siguiente intento en esta dirección, sería interesante utilizar otra alternativa para la extracción de características. Por ejemplo, obtener la cantidad de puntos presentes, para cada uno de un conjunto de colores de una paleta predefinida. La tarea sería catalogar a priori, cada pixel de la imagen, asignándola a una cierta clase (color), y de esta manera, contabilizar la cantidad de color presente en la imagen, para cada componente de la paleta propuesta.