UN SISTEMA PARA LA AGRUPACIÓN AUTOMÁTICA DE DATOS

Resumen:

En el Proyecto Fin de Carrera que se pretende realizar vamos a desarrollar un sistema para la agrupación automática de datos o patrones, es decir, para la formación de grupos o categorías, basado en una medida de similitud dada que se establece entre dichos patrones. El sistema utiliza diferentes técnicas de agrupación de datos (clustering) basadas en particiones, como son el algoritmo de las k-Medias de MacQueen, el de los K-Medoides de Kaufman y Rousseuw, el algoritmo ISODATA de Ball y May, y las redes neuronales autoorganizadas de Kohonen.  La entrada del sistema puede ser un conjunto de p patrones o individuos de una población, y cada uno de ellos constituido por N características dadas, junto con una medida de similitud que se establece entre dichos patrones y el número de grupos a formar. Asimismo, la entrada puede ser simplemente una matriz de similitud cuyo elemento s_ij nos da la analogía o similitud entre el patrón i y el patrón j, y el número de grupos a formar. Además de la formación de los grupos el sistema puede determinar los patrones prototipo de cada grupo.

 1.     Introducción

 En muchas ocasiones nos encontramos gestión y manipulación de gran cantidad de información (conocimiento) que suele venir recogida en una matriz de datos (muestra), donde las filas corresponden a las diferentes características, propiedades o atributos de un patrón (individuo, objeto, ente, etc.) y las columnas corresponden a una característica determinada presentada por cada uno de los patrones. Con el análisis de grupos se pretende formar clases o categorías según una medida de similitud de manera que los patrones o individuos de una misma clase tengan características similares.

 Se han propuesto muchos algoritmos para la formación de grupos y categorías. En este proyecto nos vamos a centrar en aquellos algoritmos basados en particiones. El más conocido es el algoritmo de las K-Medias de MacQueen que utiliza los centroides de cada grupo para ir formando los diferentes grupos iterativamente. Sin embargo, requiere que los patrones sean numéricos para poder determinar los centroides y no se puede utilizar cuando no conocemos los patrones sino sólo la similitud entre ellos, como ocurre cuando existen características de tipo cualitativo (atributos). En este caso se puede utilizar el algoritmo de las K-Medoides de Kaufman y Rousseuw. También existe otros algoritmos similares, como el algoritmo ISODATA de Ball y May. Por otra parte, los algoritmos basados en rede neuronales competitivas y redes neuronales autoorganizadas permiten también la formación de grupos o categorías siguiendo un proceso de aprendizaje no supervisado. Finalmente, los algoritmos basados en medidas difusas permiten la asignación de un patrón a un grupo utilizando una función de pertenencia. Todos estos algoritmos recogidos de diferentes paradigmas constituirán el sistema de formación de grupos que se pretende diseñar.

  2.    Objetivos

 En este proyecto se pretende desarrollar un sistema de formación automática de grupos que incorpora algoritmos clásicos, algoritmos basados en redes de neuronas artificiales y algoritmos basados en la lógica difusa.

 3.    Métodos y fases de trabajo

 El problema de la formación de grupos basada en particiones consiste en agrupar p patrones  dados (x¹, x²,…,x^p) en M clases C₁,C₂,…,C_M, de manera que la suma total  de las similitudes entre los patrones de la misma clase sea máxima, es decir,

Dicha función no es convexa y puede tener muchos mínimos locales. Además, constituye un problema de optimización combinatoria NP- difícil.

 Las tareas que se van a realizar en el análisis de datos son:

      1.      Fase:

Implementación de algoritmos de agrupación clásico, basados en centroides, como el algoritmo de las K-medias y el algoritmo ISODATA.

      2.      Fase:

Implementación del algoritmo de agrupación basados en medoides: Algoritmo de los K-medoides

3.      Fase:

Implementación de algoritmos basados en redes de neuronas artificiales autoorganizadas, en las que tenemos que seleccionar el número de grupos y  la función de vecindad.

      4.      Fase:

Implementación del algoritmo de las c-medias, basado en lógica difusa.

 5.      Fase:

Análisis comparativo de los algoritmos propuestos, utilizando el conjunto de datos IRIS (ver figura 1), datos de VIRUS (ver figura 2) y datos de ciertas características de impacto medio ambiental de  municipios de la provincia de Málaga.

 4.    Medios disponibles

  Se dispone para su realización de un ordenador Pentium IV  (1800 Mhz.) del laboratorio de Inteligencia Computacional y Análisis de Imágenes. Los programas se desarrollarán utilizando el entorno de programación VISUAL C.

 5.    Bibliografía y referencias

 [1] Cherkassky, V. and F. Mulier.  Learning from Data: Concepts, Theory and Methods. John Wiley & Sons, Inc. New York, 1998.

[2] Cherkassky, V, J. H. Friedman and H. Wechsler. From Statistics to Neural Networks. Springer-Verlag, Berlín, 1991.

[3] Haykin, S., Neural Network:  A Comprehensive Foundation. New York: IEEE Press, 1994.

[4] Kohonen, T. Self-Organization Maps. Springer Series in Information Sciences, vol. 30, Berlín, 1997.

[5] Linde Y., Buzo A., & Gray R.M. (1980). An Algorithm for vector quantizer design. IEEE  Trans. on Communication, vol. 28(1), pp. 84-95.

[6] Mérida Casermeiro, G. Galán Marín y J. Muñoz Pérez (2001). An efficient Multivaluated  Hopfield Network for the Traveling Saleman Problem. Neural Processing Letters, 14, pp. 203-216.

[7] Muñoz Pérez J., J.A. Gómez Ruiz, E. López Rubio y M.A. García Bernal (2002). “Expansive and Competitive Learning for Vector Quantization”. Neural Processing Letters, 15, pp. 1-13.

[8] Muñoz-Pérez J. y G. Galán Marín (2001). Design and Analysis of Maximum Hopfield Networks. IEEE Trans. Neural Networks, vol. 12, pp. 329-339.

[9] Pal N.R., Bezdek J.C., & Tsao E.C. (1993). Generalized clustering networks and Kohonen’s  self-organizing  scheme.   IEEE  Trans.  Neural  Networks, vol. 4(4), pp. 549-557..

[10] Ritter, H., T. Martinetz and K. Schulten. Neural Computation and Self-Organizing Maps. Addison-Wesley, Deutschland, 1992.

[11] Smith, M. Neural Networks for Statistical Modelling. van Nostrand Reinhold, New York, 1993.

[12] Xu L., A. Krzyzak and E. Oja, (1993) “Rival Penalized Competitive Learning for Clustering Analysis, RBF Net, and Curve Detection,” IEEE Trans. Neural Networks, vol. 4(4), pp. 636-649.

[13] Yair, E., Zeger K., & Gersho A. (1992). Competitive learning and soft competition for vector quantizer  design.   IEEE  Trans. Signal  Processing, vol. 40(2), pp. 294-308.