Estudio de simulación para análisis de técnicas cluster

Aguilar Simón, Gonzalo (2018). Estudio de simulación para análisis de técnicas cluster. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S.I. Industriales (UPM), Madrid.

Descripción

Título: Estudio de simulación para análisis de técnicas cluster
Autor/es:
  • Aguilar Simón, Gonzalo
Director/es:
  • Mira McWilliams, José Manuel
Tipo de Documento: Proyecto Fin de Carrera/Grado
Grado: Grado en Ingeniería en Tecnologías Industriales
Fecha: Febrero 2018
Materias:
Palabras Clave Informales: Cluster, K-means, Self-Organizing Maps (SOM), nodo, mixtura, dato, variable, análisis, parámetro, centroide, Multi Dimensional Scaling (MDS), mapa
Escuela: E.T.S.I. Industriales (UPM)
Departamento: Ingeniería de Organización, Administración de Empresas y Estadística
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (3MB) | Vista Previa

Resumen

Introducción y objetivos El objetivo del presente Trabajo de Fin de Grado el aprendizaje de las dos técnicas fundamentales de clustering: K-means y Self-Organizing Maps, y el desarrollo de experimentos computacionales de simulación que permitan profundizar en el grado de comprensión y comparación que se tiene de las mismas. Así, se estudiarán las ventajas e inconvenientes que presenta cada uno de los dos algoritmos en el tratamiento de los datos, se compararán entre ellos y se revisará la relevancia de sus parámetros principales en la obtención de resultados de calidad. El análisis de datos Desde la primera mitad del siglo XX la recopilación y análisis de datos han ido ganando importancia de manera exponencial para las organizaciones de cara a la toma de decisiones. Esto ha ido unido estrechamente al aumento del flujo de información al que el ser humano se ha visto expuesto, aumento que se ha incrementado notablemente con la llegada de internet. Sin embargo, el análisis de datos no es simple ni acostumbra a proporcionar información clara y concisa, pues los paquetes de datos raramente son perfectos: no es infrecuente encontrar listas incompletas, con algunas incongruencias o de poca utilidad. Es por ello que, durante los últimos años, se han desarrollado distintos métodos para el análisis masivo de datos (o Big Data) con el objetivo de extraer la mayor cantidad de información útil de los mismos y con la mayor precisión posible. Así, optimizar la obtención de la información se ha convertido en una tarea fundamental para los analistas. De esta necesidad surgió el concepto conocido como Machine Learning, que aúna algoritmos basados en distintas ciencias (neurociencia, física, estadística…) para lograr que los ordenadores y sistemas de procesamiento de datos aprendan a través de la práctica o entrenamiento y efectúen sus tareas con cada vez mayor precisión. Dentro del mundo del Machine Learning, destacan los algoritmos que conforman el Deep Learning, que se fundamenta en lograr que los ordenadores aprendan de la experiencia y comprendan el mundo en términos de jerarquía de conceptos, con cada uno de ellos definido por su relación con otros más simples. En otras palabras, el Deep Learning consiste en analizar fenómenos mediante la búsqueda de patrones dentro de una gran muestra de datos y, al mismo tiempo, aprender de ello. A su vez, este aprendizaje puede ser supervisado, semi supervisado y no supervisado. En particular, este proyecto se centrará en el aprendizaje no supervisado. El conjunto de algoritmos más importantes dentro del aprendizaje no supervisado son los empleados en el clustering o agrupación de los datos en conjuntos conocidos como clusters. Definición y aplicaciones del clustering Si bien no existe una definición globalmente aceptada del concepto de clustering, se puede definir como una serie de algoritmos para dividir paquetes de datos en grupos más pequeños homogéneos internamente y heterogéneos entre sí (clusters) siguiendo un criterio predeterminado, con el objetivo de facilitar la extracción de información. El clustering es una práctica cada vez más instaurada en todas las ciencias que dependan tanto de la investigación como de la predicción. Así, de acuerdo con Everitt y Dunn (2001), se aplica en infinidad de campos y áreas de trabajo, entre las que destacan la ingeniería, las ciencias computacionales, la medicina y genética, la economía y las ciencias de la tierra. Los objetivos del clustering, según Aldenderfer y Blashfield (1984), se pueden resumir en cuatro aspectos: ▪ Desarrollar una clasificación. ▪ Investigar esquemas conceptuales que sean de utilidad para la agrupación de entidades. ▪ Llegar a hipótesis a través de la exploración de datos. ▪ Probar la hipótesis y tratar de asegurar que los tipos definidos a partir de otros procesos realmente se pueden encontrar en los paquetes de datos. Algoritmos de Clustering estudiados. Dada la gran variedad de concepciones de clustering, se ha desarrollado multitud de métodos o algoritmos para clasificar los datos, cada uno con ciertas ventajas e inconvenientes respecto a los demás. Este Trabajo de Fin de Grado se centrará en dos de ellos: K-means y SOM. K-means El primer algoritmo que se va a estudiar es K-means. Esta técnica agrupa los datos en un número de clusters k asignado previamente por el analista. Para ello, K-means asigna a cada dato uno de los k grupos posibles en función de la distancia de cada dato al centro del grupo. Para mejorar la precisión de los resultados, se realizarán varias iteraciones. SOM. En segundo lugar, se analizará el mapeado auto organizado (Self-Organizing Map) o SOM. Este método representa el set de datos en estudio en un mapa de dimensiones reducidas, generalmente bidimensional, conservando la topología de los mismos. Estos mapas se dividirán en nodos distintos. Así, puntos con valores o características similares en el espacio original, aparecerán el mismo nodo o en nodos vecinos, mientras que los puntos distintos se dispondrán en nodos lejanos. En el algoritmo SOM, se depende en particular de un parámetro conocido como el parámetro de aprendizaje α, que determina el grado en el que un nodo se aproximará a un dato, arrastrando con él a sus nodos vecinos. Por otro lado, el número de nodos vecinos que se ven arrastrados por el movimiento de uno queda determinado por el parámetro r o σ, conocido como parámetro de vecindad. Implementación. Para poder analizar K-means y SOM, se han desarrollado varios sets de datos de entre dos y tres dimensiones o variables, cada uno enfocado a probar el algoritmo de una manera y ver cómo responde. Asimismo, dada la complejidad del algoritmo SOM, se ha desarrollado un conjunto de experimentos particulares para poder ver su dependencia del número de iteraciones y del parámetro de aprendizaje. En primer lugar, se ha simulado una mixtura de distribuciones formando cuatro nubes esféricas en tres dimensiones para poner a prueba los algoritmos en un caso sencillo que pueda servir como referencia para empezar a comprenderlos. Así, se han estudiado en este primer experimento los mapas que elabora SOM, así como la precisión de asignación de los centroides por parte de K-means. Estas nubes han sido modificadas con distintos propósitos particulares: ▪ Se ha optado por incrementar la dispersión de los datos para estudiar la capacidad de K-means para asignar cada punto a su nube original a la hora de hacer el clustering en casos en los exista solapamiento entre las nubes de la mixtura. ▪ Se ha aumentado la dispersión de las nubes según la dirección de uno de los ejes en sentido positivo para estudiar el comportamiento de K-means y SOM ante nubes de datos que pierden la simetría. En un segundo experimento, con el objetivo de estudiar la capacidad de ambos algoritmos para mostrar en sus resultados la correlación que pueda existir entre las distintas variables o dimensiones, se han sometido a una mixtura de datos creados según una distribución normal multivariada con correlación. En tercer lugar, se ha creado un set de datos dispuestos de manera homogénea a lo largo de tres planos para poner a prueba el comportamiento de K-means y de SOM en un caso en el que hay 3 clusters claramente definidos, pero no tanto el centroide de cada uno al existir dispersión tan solo a lo largo del plano y, como se ha comentado, homogéneamente (los datos se han distribuido de manera uniforme a lo largo de tres planos dispuestos a lo largo del eje o variable z). Tras estos experimentos se ha podido detectar la sencillez del algoritmo K-means frente a la gran complejidad que presenta SOM. Por esta razón, se han desarrollado una serie de experimentos para poder comprender mejor este último algoritmo. Así, se ha podido ver cómo va colocando los nodos a medida que se van procesando los datos, la mejora de los resultados a medida que se realizan iteraciones y la influencia que tiene el parámetro de aprendizaje α. Por último, se ha decidido comparar el comportamiento de K-means antes y después de someter a los datos a una reducción dimensional mediante un algoritmo conocido como Multi Dimensional Scaling (MDS), para ver cómo afectan los procesos de reducción del número de variables a K-means. No se ha hecho lo mismo con SOM ya que, al elaborar sus mapas, reduce las dimensiones de la mixtura. Conclusiones. Tras la realización de los experimentos, se ha podido estudiar en profundidad los algoritmos de clustering SOM y K-means, llegando a los resultados que se detallan a continuación. Por un lado, K-means se descubre como un algoritmo muy especializado en el clustering de nubes de datos con geometrías ciertamente nodales que presenta una programación y aplicación muy sencilla. Especializado en posicionar los centroides los clusters y en asignar adecuadamente los puntos a cada uno, pierde eficacia ante mixturas no nodales o que presentan una marcada asimetría. Además, los resultados que ofrece deben ser interpretados por personal especializado al proporcionar matrices de datos numéricas. Por otro lado, SOM demuestra ser un algoritmo de programación compleja que permite, previa reducción dimensional que mantiene la topología de los datos, la elaboración de mapas bidimensionales que muestran la clasificación de datos en nodos en función de su valor, asignándolos mediante el estudio individual de cada dato durante varias iteraciones. A lo largo de las iteraciones se van moviendo los nodos en función de su similitud al dato en estudio, arrastrando con él a los nodos vecinos. De este modo, se logra mantener unidos los datos más similares en los nodos. Por otro lado, el hecho de ir reduciendo los parámetros r y α permite ir alejando los nodos más distintos y concentrando los más similares en los mismos nodos. Una cualidad fundamental de los mapas SOM frente a K-means es que permiten detectar con facilidad la correlación entre las distintas variables que afectan a los datos, información esencial en la toma de decisiones.

Más información

ID de Registro: 50283
Identificador DC: http://oa.upm.es/50283/
Identificador OAI: oai:oa.upm.es:50283
Depositado por: Biblioteca ETSI Industriales
Depositado el: 20 Abr 2018 15:59
Ultima Modificación: 20 Abr 2018 15:59
  • InvestigaM
  • GEO_UP4
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM