PDF de programación - Estudio y análisis de las técnicas del pipeline de OCA aplicadas a datos simulados de la misión GAIA

Estudio y análisis de las técnicas del
pipeline de OCA aplicadas a datos

simulados de la misión GAIA

Trabajo Fin de Máster

presentado por D. Juan Gabriel Pérez Liñana

Máster en Inteligencia Artificial Avanzada. UNED.

Directores:

Dr. D. Luis Manuel Sarro Baro

Dr. D. Miguel García Torres

Septiembre de 2012

Índice general

Agradecimientos

Resumen

Abstract

1 Introducción

1.1 Contexto del trabajo . . . . . . . . . . . . . . . . . . . . . . .

1.2 Objetivos perseguidos . . . . . . . . . . . . . . . . . . . . . . .

1.3 Estructura del trabajo . . . . . . . . . . . . . . . . . . . . . .

2 Revisión del área

2.1 Divide y vencerás . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Metodología incremental

. . . . . . . . . . . . . . . . . . . . .

xi

xiii

xv

1

1

2

3

7

8

9

2.3 Paralelización . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.4 Trabajo con grandes bases de datos . . . . . . . . . . . . . . . 12

3 Estudio de los datos

17

3.1 Descripción de los datos utilizados . . . . . . . . . . . . . . . . 17

3.2 Problemas en las muestras . . . . . . . . . . . . . . . . . . . . 21

3.3 Atributos presentes . . . . . . . . . . . . . . . . . . . . . . . . 24

3.4 Análisis de los datos

. . . . . . . . . . . . . . . . . . . . . . . 25

3.5 Preparación para la experimentación . . . . . . . . . . . . . . 29

3.5.1 Extracción y preprocesado de datos . . . . . . . . . . . 29

3.5.2 Normalización . . . . . . . . . . . . . . . . . . . . . . . 30

3.5.3 Disminución de la dimensionalidad . . . . . . . . . . . 34

iii

4 Técnicas empleadas en la experimentación

39

4.1 K-medias

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.1.1 K-means++ . . . . . . . . . . . . . . . . . . . . . . . . 41

4.1.2 K-means# . . . . . . . . . . . . . . . . . . . . . . . . . 43

4.2 Algoritmo HMAC/MAC . . . . . . . . . . . . . . . . . . . . . 43

4.2.1 Algoritmo de tipo EM . . . . . . . . . . . . . . . . . . 43

4.2.2 Mode Association Clustering MAC . . . . . . . . . . . 48
Árbol KD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.3

5 Escalando el algoritmo

55

5.1 Pipeline para el procesado de datos . . . . . . . . . . . . . . . 56

5.2 Medición del coste espacial y temporal

. . . . . . . . . . . . . 62

5.2.1 Pruebas de rendimiento de K-means++ y K-means# . 62

5.2.2 Pruebas de rendimiento del algoritmo PCA incremental 66

5.2.3 Velocidad de ejecución de MAC y K-medias

. . . . . . 67

5.2.4 Algoritmo MAC frente a variación utilizando árboles kd 69

6 Experimentos iniciales

75

6.1 Experimentación con componentes principales . . . . . . . . . 75

6.2 Análisis de resultados y líneas de investigación para su mejora

78

7 Segunda fase de experimentación

81

7.1 Datos astrométricos . . . . . . . . . . . . . . . . . . . . . . . . 81

7.2 Momentos estadísticos

. . . . . . . . . . . . . . . . . . . . . . 83

7.3 Eliminación de agrupación curvilínea de gran densidad . . . . 86

7.4

Incorporación a los experimentos

. . . . . . . . . . . . . . . . 87

7.5 Análisis de los clusters obtenidos

. . . . . . . . . . . . . . . . 89

7.5.1 Problemas encontrados . . . . . . . . . . . . . . . . . . 90

7.5.2 Parámetros estelares estudiados . . . . . . . . . . . . . 92

7.5.3 Herramienta desarrollada . . . . . . . . . . . . . . . . . 94

7.5.4 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . 95

8 Introducción de ruido

99

8.1 Efecto de incrementar G . . . . . . . . . . . . . . . . . . . . . 100

v

8.2 Efecto de introducir ruido sintético . . . . . . . . . . . . . . . 102

9 Conclusiones y trabajos futuros

105

9.1 Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

9.2 Trabajos futuros

. . . . . . . . . . . . . . . . . . . . . . . . . 107

A Glosario

B Pseudocódigo de MAC

C Aplicaciones complementarias desarrolladas

D HMAC a través del bandwidht

Bibliografía

109

113

119

123

127

Índice de figuras

3.1 Esquema de la generación del corpus SDSS . . . . . . . . . . . 18

3.2 Representación de las diferentes clases

. . . . . . . . . . . . . 27

3.3 Espectro de estrella tipo Phoenix sin normalizar . . . . . . . . 32

3.4 Normalización por suma del módulo . . . . . . . . . . . . . . . 32

3.5 Normalización por área unidad del espectro

. . . . . . . . . . 33

3.6 Comparación de espectros BP normalizados de estrellas SDSS

y Ultrafrías.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.7 SSE diferencia espectro original y calculado por componentes

principales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.1 Ejemplo de ejecución del K-medias . . . . . . . . . . . . . . . 40

4.2 Pseudocódigo del K-means++ . . . . . . . . . . . . . . . . . . 42

4.3 Pseudocódigo del K-means# . . . . . . . . . . . . . . . . . . . 43

4.4 Ejemplo de distribución EM . . . . . . . . . . . . . . . . . . . 46

4.5 Ejemplo de mezcla con dos distribuciones normales

. . . . . . 47

4.6 Pseudocódigo de MAC . . . . . . . . . . . . . . . . . . . . . . 51

4.7 Pseudocódigo del árbol KD . . . . . . . . . . . . . . . . . . . 53

4.8 Ejemplo de árbol KD . . . . . . . . . . . . . . . . . . . . . . . 53

5.1 Fase de muestreo del pipeline.

. . . . . . . . . . . . . . . . . . 57

5.2 Fase de agrupación del pipeline.

. . . . . . . . . . . . . . . . . 59

5.3 Representación del proceso de resumen de información.

. . . . 60

5.4 Fase agrupación, variación multinivel

. . . . . . . . . . . . . . 61

5.5 Coste temporal K-means# vs K-means++ . . . . . . . . . . . 65
5.6 Coste temporal MAC vs Árbol KD+MAC . . . . . . . . . . . 71

vii

viii

6.1 Solapamiento de clases en experimentación inicial

. . . . . . . 76

7.1 Diagrama de Hertzsprung-Russel.

. . . . . . . . . . . . . . . . 93

7.2 Caracterización de diferentes conglomerados de estrellas . . . . 96

A.1 DPAC dentro de la organización de la misión Gaia . . . . . . . 111

B.1 Pseudocódigo ObtenerListaModas . . . . . . . . . . . . . . . . 114

B.2 Pseudocódigo EstimaModa . . . . . . . . . . . . . . . . . . . . 114

B.3 Pseudocódigo ProbabilidadAPosteriori

. . . . . . . . . . . . . 115

B.4 Pseudocódigo ActualizaModa . . . . . . . . . . . . . . . . . . 116

B.5 Pseudocódigo AgruparModas

. . . . . . . . . . . . . . . . . . 117

ix

Índice de tablas

2.1 Resumen de los paradigmas y algoritmos analizados . . . . . . 13

3.1 Número de instancias por corpus de datos

. . . . . . . . . . . 21

3.2 Atributos iniciales . . . . . . . . . . . . . . . . . . . . . . . . . 26

5.1 Porcentaje de acierto del K-medias con varias inicializaciones.

5.2 Tiempo de ejecución del K-medias con varias inicializaciones.

63

64

5.3 Escalado de K-means# frente K-means++ . . . . . . . . . . . 64

5.4 Coste PCA Incremental

. . . . . . . . . . . . . . . . . . . . . 66

5.5 Escalado en MAC y K-medias . . . . . . . . . . . . . . . . . . 68
5.6 Comparativa coste temporal MAC frente Árbol KD+MAC . . 70
5.7 Resultados Árbol kd + MAC . . . . . . . . . . . . . . . . . . 72

7.1 Resultado clustering con momentos estadísticos

. . . . . . . . 86

7.2 Resultados clustering con CP y momentos estadísticos . . . . . 89

7.3 Caracterización de diferentes conglomerados de estrellas . . . . 97

8.1 Ruido. Efecto de incrementar G en muestras . . . . . . . . . . 100

8.2 Resultados con ruido sintético . . . . . . . . . . . . . . . . . . 103

Agradecimientos

Quisiera agradecer a todas aquellas personas que me han ayudado en el desa-

rrollo del presente Trabajo Final de Máster.

En primer lugar al director del trabajo, el Dr. D. Luis Manuel Sarro

Baro, profesor del Departamento de Inteligencia Artificial de la UNED y

miembro de OCA (Object Clustering Analysis), por sus consejos y dirección,

especialmente por guiarme cuando los objetivos iniciales del proyecto cam-

biaron por causas ajenas. En segundo lugar quisiera agradecer al codirector,

Dr. D. Miguel García Torres, profesor de la Universidad Pablo de Olavide y

miembro también de OCA, sus numerosas aportaciones, desde el acceso para

algunas experimentaciones al cluster de computación del Centro Informático

Científico de Andalucía hasta los consejos sobre la utilización de LaTex como

herramienta para la composición del presente trabajo.

Para concluir, me gustaría dedicar esta memoria a mi mujer Maria Esteller,

por todo el apoyo y comprensión recibidos y por soportar innumerables fi-

nes de semana y períodos de vacaciones mi ausencia, trabajando frente al

ordenador en vez de estar junto a ella.

xi

Resumen

Este Trabajo de Fin de Máster se enmarca dentro de la misión GAIA de

la Agencia Europea del Espacio, cuyo lanzamiento está previsto para finales

de 2013. Debido al elevado volumen de datos que se generará, se ha deci-

dido crear un consorcio para el procesamiento y análisis de datos, llamado

Gaia Data Processing and Analysis Consortium (DPAC). Dicho consorcio se

encuentra dividido en 10 unidades de coordinación de las cuales, la octava

(CU8), está enfocada en la estimación de parámetros astrofísicos a partir de

las observaciones. El presente trabajo pertenece a los estudios preliminares

llevados a cabo dentro del bloque de trabajo Object Clustering Algorithm

(OCA) de CU8. El objetivo principal de OCA es desarrollar las herramien-

tas adecuadas para el análisis de los datos recibidos desde la perspectiva del

agrupamiento.

Los principales retos de OCA son estudiar la técnicas más adecuadas de

agrupamiento para la naturaleza de los datos de GAIA y ser capaz de escalar

dichas técnicas para poder tratar el gran volumen de datos que se recibirá a lo

largo de la misión. A lo largo de este trabajo se presentarán las metodologías

propuestas en la literatura para poder escalar algoritmos de agrupamiento

así como la descripción de las técnicas elegidas debido a sus propiedades.

La investigación desarrollada se puede dividir en diferentes partes:
• Es