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

Sexta Clase: Aprendizaje No Supervisado

Aprendizaje Automático sobre
Grandes Volúmenes de Datos

Clase 6

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-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

Material de lectura

Clase pasada:

Capítulo 13 del Owen et al. (2012)
http://ufal.m.cuni.cz/~zabokrtsky/courses/np104/html/feature_engineering.pdf

Ésta clase:

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)

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

BDML-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

Preguntas

Binning: una técnica de reducción del espacio de valores (de
256 valores de una byte a 3 valores)
Feature selection: ¾cuántas features? No se sabe bien, tomar
un porcentaje de las mejores es una posibilidad
Clustering e ingeniería de features:

una técnica de binning muy usada es particionar los datos y
usar el cluster en vez del dato original
Técnicas de clustering se usan mucho con lenguaje natural,
para tener features más informativas que simplemente palabras
Pre-procesamiento no-supervisado de las features de entrada
es la clave de Deep Learning

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

BDML-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

Reducción de dimensionalidad

Selección de features es una técnica de reducción de
dimensionalidad

Otras involucran todas las features a la vez y generan un
cambio de coordenadas, de un espacio mayo a uno menor
Una muy utilizada es descomposición en valores singulares
(SVD) o también llamada análisis de componentes principales
(PCA)

Tomamos nuestras instancias como las y armamos una matriz
M, entonces

M T ME = EL

donde E es la matriz de los autovectores y L es la matriz
diagonal de los autovectores
Si Ek son las primeras k columnas de E , entonces MEk es una
representación en k dimensiones de M
Véase http://infolab.stanford.edu/~ullman/mmds/ch11.pdf

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

BDML-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

En qué van a ser evaluados

Dos algoritmos en detalle:

Naive Bayes
Decision Trees

Dos algoritmos a nivel conceptual:

SVM
Regresión logística

Ingeniería de features a nivel conceptual (práctico va a ser en
la competencia kaggle y/o el proyecto)

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

BDML-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

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
aprendizajengrande@librelist.com es optativo

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

Feedback 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-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

Aprendiendo lo que uno no sabe

Un poco mágico
Tenemos un modelo, queremos estimar sus parámetros
Tenemos parámetros, queremos construir un modelo
Conocer la respuesta, buscar la pregunta
Muy ligado al concepto de distancia entre instancias

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

BDML-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

Mi tesis

Mi tesis doctoral (http://duboue.net/thesis.html) consistió en
una mezcla de aprendizaje supervisado y no supervisado
Datos: texto e información simbólica sin alinear

Actor, born Thomas Connery on
August 25, 1930,
in Fountain-
bridge, Edinburgh, Scotland, the
son of a truck driver and char-
woman. He has a brother, Neil,
born in 1938. Connery dropped
out of school at age fteen to
join the British Navy. Connery is
best known for his portrayal of the
suave, sophisticated British spy,
James Bond, in the 1960s. . . .

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

BDML-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

Clustering

Un tipo de aprendizaje no supervisado
Descubre estructura presente en los datos
Knowledge Discovery and Data Mining

El objetivo de los métodos de clustering es descubrir grupos
signicativos presentes en los datos

¾Cómo evaluar algo que no sabíamos que existía?

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

BDML-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

Una cuestión de distancias

El concepto central en clustering es la denición de una
distancia entre instancias
Cada denición de distancias induce un agrupamiento de los
datos, basado en esa métrica
La distancia es donde se incorpora la información humana

Entre otros puntos, por ejemplo, el número de clusters

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

BDML-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

Ejemplos de distancias

Datos de censo de la clase anterior:

age: continuous.
workclass: Private, Self-emp-not-inc, Self-emp-inc, Federal-gov,
Local-gov, State-gov, Without-pay, Never-worked.
sex: male, female.
education: Bachelors, Some-college, 11th, HS-grad,
Prof-school, Assoc-acdm, Assoc-voc, 9th, 7th-8th, 12th,
Masters, 1st-4th, 10th, Doctorate, 5th-6th, Preschool.
education-num: continuous.
marital-status: Married-civ-spouse, Divorced, Never-married,
Separated, Widowed, Married-spouse-absent,
Married-AF-spouse.
occupation: Tech-support, Craft-repair, Other-service, Sales,
Exec-managerial, Prof-specialty, Handlers-cleaners,
Machine-op-inspct, Adm-clerical, Farming-shing,
Transport-moving, Priv-house-serv, Protective-serv,
Armed-Forces.

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

BDML-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

Ejemplo de distancia

Un polinomio con coecientes ad hoc y distancias ad hoc para
cada componente

dist(i1, i2) = α1distage(age1, age2)+α2distworkclass (workclass1, workclass2)+α3disteducation(education1, education2)+. . .

Donde las distancias por componente pueden ser denidas
matemáticamente o vía una tabla:

distage(x, y ) = (x − y )2

distworkclass (a, b) =

a/b

private

0

private

self
gov't
unpaid

self
0.3
0

gov't
0.7
0.9
0

unpaid

1.0
0.7
0.3
0

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

BDML-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

Tipos de clustering

Algoritmos por partición
Algoritmos jerárquicos
Algoritmos por densidad
Algoritmos "fuzzy"

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

BDML-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

Algoritmos por partición

Partir los datos en un número de particiones (clusters) donde
no hay relaciones fuera de las particiones
Las particiones optimizan una cierta función objetivo

La función objetivo enfatiza estructura local o global de los
datos y su optimización es usualmente un proceso iterativo

El número de clusters es normalmente un parámetro del
algoritmo
El más conocido es K-Means que vamos a ver hoy
Otros ejemplos incluyen PAM y CLARA

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

BDML-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

Algoritmos jerárquicos

Van uniendo clusters más pequeños en clusters más grandes o
dividiendo clusters más grandes
El resultado es un árbol de clusters (un dendrograma)

Puede ser transformado en una partición cortando el
dendrograma a un nivel particular

Aglomerativo
Divisivo
El algoritmo más sencillo requiere una matrix de proximidad
completa
Un algoritmo más eciente es BIRCH (incremental, bueno con
datos con ruido pero sensible al órden y limitado en tamaño)

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

BDML-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

Todos los pares

Calcular la matrix de proximidad de manera completa es
intratable para gran número de datos
Ejemplo de dendrograma

Cargos laborales, distancia es la proximidad de los textos de
sus perles en LinkedIn
Trabajo realizado para MatchFWD (Montreal, 2011)

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

BDML-clase6-1/09

Sexta Clase: Aprendizaje No Supervisado

Clase anterior
Aprendizaje No Supervisado
Clustering

Algoritmos por densidad

Los clusters se consideran regiones del espacio de datos de alta
densidad, separados por regiones de baja densidad.
El más conocido es DBSCAN

La idea detrás de DBSCAN es que para cada punto en el
cluster, un entorno de cierto radio debe contener un mínimo
número de puntos en el cluster.
Soporta ruido (outliers) y puede descubrir clusters de forma
arbitraria.
Tiene parámetros complejos de elegir, como el radio y el
número de puntos en el entorno

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

BDML-clase6-1/09

Sexta