PDF de programación - Arquitectura lambda aplicada a clustering de documentos en contextos Big Data

Universidad Nacional de Educación a Distancia

Tesis de Máster



Arquitectura lambda aplicada a

clustering de documentos en

contextos Big Data



Máster universitario en I.A. avanzada:
Fundamentos, métodos y aplicaciones



Autor:

Alberto Vallejo Martínez

Directores:

Raquel Martínez Unanue
Álvaro Rodrigo Yuste



Octubre de 2015

Contenido

Contenido ........................................................................................................................................... 2

Lista de Figuras.................................................................................................................................. 4

Lista de Tablas ................................................................................................................................... 6

Resumen ............................................................................................................................................. 7

Palabras clave ..................................................................................................................................... 7

Abstract .............................................................................................................................................. 8

Keywords ........................................................................................................................................... 8

1

Introducción ........................................................................................................................... 10

1.1 Motivación ..................................................................................................................... 10

1.2

1.3

1.4

Descripción del problema ........................................................................................... 10

Objetivos ........................................................................................................................ 12

Estructura de la memoria............................................................................................. 12

2

Preliminares ............................................................................................................................ 13

2.1

Big Data .......................................................................................................................... 13

2.1.1 Generalidades ......................................................................................................... 13

2.1.2 Desafíos de Big Data ............................................................................................. 13

2.1.3 Map-Reduce ............................................................................................................ 15

2.1.4

Apache Spark .......................................................................................................... 16

2.2

Arquitectura lambda ..................................................................................................... 18

2.2.1

Ventajas y aplicaciones de la arquitectura lambda ............................................. 23

2.3

Representación de los datos ........................................................................................ 24

2.3.1 Modelo de espacio vectorial ................................................................................. 24

2.3.2

La maldición de la dimensionalidad .................................................................... 25

2.3.2.1

El valor de referencia y sus problemas ....................................................... 25

2.4

Reducción de dimensionalidad ................................................................................... 25

2.4.1

Latent Dirichlet Allocation (LDA) ...................................................................... 27

2.4.2

Probabilistic Latent Semantic Analysis (PLSA) ................................................. 29

2.4.3

PLSA y LDA en Big Data..................................................................................... 30

2.5

Clustering en Big Data ................................................................................................. 31

2.5.1

k-means en Big Data.............................................................................................. 32



2

2.6

Flujo de datos (Streaming) ........................................................................................... 34

2.6.1

Clustering incremental ........................................................................................... 35

2.7 Métodos de evaluación................................................................................................. 37

2.7.1

Evaluación de la escalabilidad .............................................................................. 37

2.7.2

Evaluación de la calidad ........................................................................................ 38

3 Diseño del método propuesto ............................................................................................. 40

3.1

3.2

3.3

3.4

Descripción .................................................................................................................... 40

Algoritmos utilizados ................................................................................................... 42

Conjunto de datos maestro ......................................................................................... 43

Arquitectura Lambda ................................................................................................... 44

3.4.1

Batch Layer ............................................................................................................. 44

3.4.2

Speed Layer ............................................................................................................. 45

3.4.3

Serving Layer .......................................................................................................... 47

4

Experimentos y resultados ................................................................................................... 49

4.1

4.2

4.3

Juegos de datos .............................................................................................................. 49

Experimentos ................................................................................................................ 49

Estudio de la calidad ..................................................................................................... 50

4.3.1

Análisis de Batch Layer ......................................................................................... 50

4.3.2

Análisis de Speed Layer ......................................................................................... 52

4.3.3

Conclusiones ........................................................................................................... 53

4.4

Estudio de la escalabilidad ........................................................................................... 53

4.4.1

Análisis de Batch Layer ......................................................................................... 53

4.4.1.1

Interpretación ................................................................................................. 58

4.4.2

Análisis de Speed Layer ......................................................................................... 59

4.4.2.1

Resultados globales ........................................................................................ 59

4.4.2.2

Resultados TF-IDF y LDA .......................................................................... 61

4.4.2.3

Interpretación ................................................................................................. 62

4.5

Análisis global ................................................................................................................ 62

5

Conclusiones y trabajos futuros ........................................................................................... 64

Agradecimientos .............................................................................................................................. 65

Bibliografía ....................................................................................................................................... 66

Anexo I ............................................................................................................................................. 74

Hashing de rasgos .................................................................................................................. 74



3

Lista de Figuras

Figura 2.1. Fases del procesamiento en Big Data. (Fuente Labrinidis & Jagadish, 2012) .... 14
Figura 2.2. Signatura de funciones Map y Reduce ..................................................................... 15
Figura 2.3. Arquitectura de Apache Spark................................................................................... 17
Figura 2.4. Comparativa de rendimiento Hadoop vs Spark, ejecutando Regresión Logística.
(Fuente: Zaharia et al., 2012) ......................................................................................................... 18
Figura 2.5. Diagrama con las capas de la arquitectura lambda. ................................................ 20
Figura 2.6. Ejemplo. Se inicia el procesamiento de la capa batch sobre el dataset completo
........................................................................................................................................................... 22
Figura 2.7. Ejemplo. Llega un documento nuevo ...................................................................... 22
Figura 2.8. Ejemplo. La capa batch termina su procesamiento ......................................