PDF de programación - Aprendizaje Automático sobre Grandes Volúmenes de Datos - Clase 7

Septima Clase: Clustering Estadístico

Aprendizaje Automático sobre
Grandes Volúmenes de Datos

Clase 7

Pablo Ariel Duboue, PhD

Universidad Nacional de Córdoba,

Facultad de Matemática, Astronomía y Física

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

Clase pasada:

Jacob Kogan: Introduction to Clustering Large and
High-Dimensional Data (2007)
Wikipedia: Cluster Analysis (Evaluation of clustering
results)

http://en.wikipedia.org/wiki/Cluster_analysis#Evaluation_of_clustering_results

Halkidi, Batistakis & Vazirgiannis: On Clustering Validation
Techniques. Journal of Intelligent Information Systems
December (2001), Volume 17, Issue 2-3, pp 107-145.
Everitt, Landau & Leese: Cluster Analysis (2001)
Capítulo 7 del Owen et al. (2012)

Ésta clase:

Capítulo 9 del Owen et al. (2012)
Sección 6.12 del Mitchel (1997)

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

Preguntas

¾Cómo representar instancias vectorialmente?

Para más ejemplos ver Capítulo 8 del Owen et al. (2012)

¾Cómo usar los clusters?

Para más ejemplos ver Capítulo 12 del Owen et al. (2012)

¾Qué método de clustering utilizar? ¾Qué métrica usar para
evaluar?

El dilema de la abundancia
Para grandes volúmenes de datos

Usar K-Means
Validación interna: separación usando distancia entre
centroides
Robustez: separación de muestras

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

Recordatorio

El sitio Web de la materia es http://aprendizajengrande.net

Allí está el material del curso (lminas, audio)

Leer la cuenta de Twitter https://twitter.com/aprendengrande
es obligatorio antes de venir a clase

Allí encontrarán anuncios como cambios de aula, etc
No necesitan tener cuenta de Twitter para ver los anuncios,
simplemente visiten la página
Suscribirse a la lista de mail en
[email protected] es optativo

Si están suscriptos a la lista no necesitan ver Twitter

Feedback para alumnos de posgrado es obligatorio y rmado,
incluyan si son alumnos de grado, posgrado u oyentes

El "resúmen" de la clase puede ser tan sencillo como un
listado del título de los temas tratados

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

Revisión K-Means

Se basa en el concepto de elementos sintéticos:
cada cluster se lo representa por un centroide, un elemento
cticio

en vez de calcular la distancia a todos los elementos del
cluster, se la calcula sólo al elemento cticio

El algoritmo recibe como parámetro el número K de clusters
Al comienzo se toman como centroides K elementos al azar
En cada paso, se re-clasican los elementos según el centroide
al que están más cerca
Para cada cluster, se re-calcula el centroide como la media de
los elementos del cluster

¾Cómo calcular el centroide? Depende de los datos, igual que
la distancia.

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

K-Means, grácamente

Primero y segundo paso. Los elementos línea punteado son los
centroides.

(Wikipedia)

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

¾Qué es Bigdata?

Es un término comercial

Sirve para describir productos y servicios relacionados con el
manejo de datos
Según el interés de la persona en vender productos y servicios,
son los límites de lo que es bigdata

Es la progresión natural en manejo de datos

Base de datos
Datawarehouse
Soluciones de Bigdata

En el caso del aprendizaje automático, soluciones para grandes
volúmenes de datos se utilizan cuando los datos no pueden
entrar en la memoria y disco de una sola máquina

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

El valor está en los datos

Actualmente más y más empresas y particulares se dan cuenta
del valor de los datos
El acopio de datos comienza muy antes de la búsqueda de
valor en esos datos
Las soluciones de bigdata permiten extraer valor de dichos
datos

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

Las computadoras como humanizadoras

Nací en mediados de los '70
La mitad de todos los humanos que han existido están vivos en
este momento
Ya no es posible el tipo de personalización que es natural para
los humanos
El análisis de grandes volúmenes de datos permite el tipo de
personalización que nos hace falta

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

La democratización del cómputo

Algunas ideas inspiradas en la presentación de Alistair Croll
durante la semana de Bigdata en Montreal

http://www.slideshare.net/Tiltmill/cycle-time-trumps-scale-big-data-as-the-
organizational-nervous-system-montreal-big-data-week-2014

Computo, lleva a automatizar cosas, las redes llevan a
interconectar pero el gran volúmen de datos lleva a predecir y
cambiar cosas
Antes había que elegir sólo dos de entre volúmen, velocidad y
variedad

Bibliotecas: gran cantidad de datos variados pero lentas
Máquina de ordenar monedas: gran cantidad de monedas y
rápido pero no son variadas

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

Los resultados inesperados de la abundancia

Los estudios y algoritmos que estamos usando no son nuevos

Pero su uso indiscriminado lo es

Antes existían soluciones especícas para grandes volúmenes
de datos, a un costo muy elevado

Censo
Bancos

Eciencia =⇒ menores costos =⇒nuevos usos =⇒
=⇒mayor demanda =⇒mayor consumo.

Con más poder de cómputo, las necesidades de procesamiento
de grandes volúmenes de datos están disparándose
La gente tiene necesidad de acceder a tecnología antes
reservada para gobiernos y empresas multinacionales

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

Data Science

Las soluciones de tipo bigdata son interdisciplinarias e
involucran:

Hardware
Software
Análisis de datos

Es el surgimiento del profesional especializado en Data Science
La semana que viene vamos a tener una reunión local de
profesionales interesados en Data Science, más detalles en
@aprendengrande

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

Conceptos de Bigdata

Algunos conceptos que serán útiles:

Storage distribuido: para manejar grandes volúmenes de datos,
es necesario poder almacenar datos en una red de
computadoras

El más conocido es HDFS

Arquitectura de cómputo distribuido: utilizar la red de
computadoras de manera ecaz

El más mencionado es Hadoop
Existe un abanico de soluciones en el sistema Watson usamos
ActiveMQ

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

Pasos del proceso de Bigdata

1 Adquicisión de datos
2 Limpieza de datos
3 Análisis de datos
4 Uso en predicción

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

Bayes revisitado

Una hipótesis h dene una función sobre los datos. Esta
función aproxima la verdadera función que genera los datos f .
La hipótesis de Maximum Likelihood es
hML = argmaxh∈H p(D|h)

Si los casos de entrenamiento son mutualmente independientes
dado la hipótesis:

hML = argmaxh∈H ∏ p(di|h)

Si asumimos que los puntos de entrenamiento pertenecen a
una distribución Normal con media σ ² centrados alrededor del
valor de f (xi ) y que los errores son distribuidos con media
uniforme entonces (di = f (xi ) + ei )
hML = argmaxh∈H ∏ 1√

− 1
2σ ² (di−µ)2

e

2πσ 2

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

Estimador ML

Manipulando algebraicamente y simplicando

hML = argmaxh∈H ∏ 1√
= argmaxh∈H ∏ 1√

2πσ 2

2πσ 2

− 1
2σ ² (di−µ)2

− 1
2σ ² (di−h(xi ))2

e

e

= argminh∈H

(di − h(xi ))2

m∑

i=1

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

Ejemplo de EM

Si observamos datos provenientes de una Gaussiana, podemos
obtener su media utilizando la función anterior:

µML = argminµ

(xi − µ)2

m∑

i=1

¾Pero qué hacemos si los datos provienen de dos Gaussianas?
Consideramos que tenemos variables ocultas, no observadas
Cada punto es de la forma (cid:104)xi , zi 1, zi 2(cid:105), zij es 1 si la instancia i
es generada por la Gaussiana j ó 0 si no.
Si los zij fueran observados, podríamos usar el estimador arriba
para calcular h = (cid:104)µ1, µ2(cid:105)

EM

1 Calcular el valor de E [zij ] asumiendo que h = (cid:104)µ1, µ2(cid:105) es cierta
2 Calcular una nueva ´h = (cid:104)´µ1, ´µ2(cid:105) asumiendo que losE [zij ] son

correctos

© 2014 Pablo Duboue, bajo licencia CC-BY-SA

BDML-clase7-3/09

Septima Clase: Clustering Estadístico

Clase anterior
Bigdata
Algoritmo EM
Thoughtland

Calculando los E [zij ]

Si asumimos que la hipótesis h = (cid:104)µ1, µ2(cid:105) es correcta, entonces

E [zij ] =

=

p(x = xi|µ = µi )
n=1 p(x = xi|µ = µn)
∑2
e− 1
n=1 e− 1
∑2

2σ ² (xi−µn)2

2σ ² (xi−µj )2

© 2014 Pablo Duboue, bajo licencia CC-BY-S