Aprendizaje No-Supervisado

Question 1

Clustering NS?

Answer 1

Clustering es llamado aprendizaje no- supervizado, sin embargo, no es lo único que es llamado así.
• Clustering consiste en organizar los datos en grupos cuyos miembros son parecidos de alguna forma.
• Es decir, un clúster es un conjunto de datos que son similares de alguna forma, y a su vez son “disimiles” a los ejemplos contenidos en otros clústers.
• En la jerga de clustering, cada instancia en los datos es llamada objeto o data point.

Question 2

Tipos de clustering

Answer 2

• Hay dos tipos de clustering: particional y jerárquico.
• La idea es agrupaciones intrínsecas de los datos de entradas mediante el uso de un algoritmo de clustering y una medida de distancia.

Question 3

Clustering Particional: K-means

Answer 3

• Es simple y eficiente.
• Dado un número de k de clústers y un conjunto de datos, este algoritmo particiona iterativamente los datos en los k clústers de acuerdo a una medida de distancia.
• Cada clúster tiene un centro, llamado centroid, que representa al clúster.
• El centroid es la media de todos los puntos dentro del clúster.
• Al comienzo el algoritmo escoge k datos como los centroides semilla.
• Después, calcula la distancia de centroide semilla con cada dato. Cada dato es asignado al centroide que está más cerca.

• Después que todos los datos son asignados, el centroide de cada clúster es re-calculado utilizando los datos en cada clúster.
• El proceso se repite hasta una condición de término:
– No hay más, o muy pocas, re-asignaciones de datos a otros clústers. Es decir, no ha mucho movimiento.
– No hay más, o muy pequeño, cambio en los centroides.
– Muy poca disminución en la suma del error cuadrático (SSE).

Question 4

Ventajas de KMEANS

Answer 4

• Las principales ventajas de K-means es que es simple y eficiente.
• Es fácil de entender y de implementar.
• Su complejidad es O(tkn), donde n es el número de datos, k el de clústers y t el número de iteraciones.
• Dado que k y t son pequeños, normalmente, se considera un algoritmo lineal con respecto al tamaño del conjunto de datos.

Question 5

DESVENTAJAS de kmeans

Answer 5

– Es necesario tener definido el concepto de media. Por ende, hay un problema con atributos basados en categorías. Hay una variación llamada k-modes, que utiliza la moda en vez de la media. Entonces, cada componente es el valor más frecuente de cada atributo, y la distancia es el número de atributo-valor que coinciden.
– Muchas veces no se sabe el valor de k de ante- mano
– El algoritmo es sensible a outliers.

Question 6

Outlier

Answer 6

es un punto que esta lejano a culquier cluster que ha formado.

Question 7

Solución 1 Outlier

Answer 7

• Una forma de lidiar con los outliers es remover los puntos que están más lejos de los centroides que otros puntos.
• Es primordial esperar varias iteraciones antes de remover un punto, porque podría ser un clúster pequeño de puntos.
• Se puede utilizar una cota.

Question 8

Solución 2 outlier

Answer 8

Otra forma de combatir los outliers es random sampling:
– Se escoge un pequeño subconjunto de los datos.
– Se hace aleatoriamente.
– Se utiliza este subconjunto para calcular los centroides.
– Después se añaden el resto de los puntos:
• Al centroide más cercano, o
• Utilizar los clústers para hacer aprendizaje supervisado y etiquetar el resto de los puntos.
• Usar los clústers como semillas para aprendizaje semi- supervisado.

Question 9

aprendizaje semi-supervisado. (breve)

Answer 9

– Es un paradigma que aprende de un conjunto reducido de ejemplos etiquetados y de un conjunto grande de datos no etiquetados.

Question 10

problema de K-means son las semillas iniciales:

Answer 10

– Diferentes semillas pueden terminar en diferentes centroides alcanzando un óptimo local.

• Hay varios métodos para escoger semillas iniciales:
– Calcular el centroide del conjunto completo de datos. Se escoge el punto más lejano al centroide, y después se escoge el punto más lejano al previamente escogido, así sucesivamente. Este método no funciona bien con outliers.

• En la práctica, frecuentemente resulta fácil para los humanos escoger las semillas. Por ejemplo, data points que son muy diferentes.
• K-means no funciona bien cuando hay que descubrir datos que no son hiper-esferas.

Question 11

Clustering Jerárquico

Answer 11

• Produce un árbol, también llamado dendrogram (a), que consiste en un conjunto de clústers anidados.
• Los datapoint están en las hojas del árbol, y el árbol parte con un único nodo llamado raíz.
• Cada nodo del árbol tiene hijos, y cada hermano particiona los datos que tiene el padre

Question 12

Clustering Jerárquico - Agglomerativos (bottom-up):

Answer 12

Construye el árbol mediante la amalgama de los clústers más cercanos. Así sube niveles en el árbol. Es el método más usado

Question 13

Clustering Jerárquico - Divise (top-down):

Answer 13

Parte con todos los datos en un clúster, la raíz. Divide los nodos en hijos sucesivamente, hasta alcanzar clústers de puntos individuales.

Question 14

Clustering Jerárquico - calculo distancia

Answer 14

• Para calcular la distancia entre dos clústers:
– Single-Link
– Complete-Link
– Average-Link

Question 15

• Single-Link:

Answer 15

– La distancia entre dos clústers es la distancia de los dos puntos más cercanos.
– Bueno para encontrar clústers de forma no- eliptica.
– Es sensible a datos ruidoso.
– La complejidad es O(n2), con n el número de datos.

Question 16

Complete-Link

Answer 16

– Une dos clústers tal que su distancia máxima es la mínima entre todos los clústers.
– No tiene el problema de los datos ruidosos, pero tiene el problema de los outliers.
– En general, produce mejores resultados que el método de Single-Link.
– La complejidad es O(n2log n), con n como el número de datos.

Question 17

Average-Link:

Answer 17

– La distancia es el promedio entre todos los pares de puntos de un clúster.
– La complejidad es O(n2log n), con n como el número de datos.

Question 18

Otros metodos de calculo de distnancia entre clusters

Answer 18

– Centroid: la distancia está dada por el centroide de los
dos clústers.
– Ward: Se amalgama los clústers que incrementan el error de menor forma. El error (SSE) se calcula como la diferencia entre el clúster nuevo y los que se une.

Question 19

Clustering jerárquico tiene ventajas

Answer 19

– Puede tomar cualquier métrica de distancia.
– No tiene un k definido, es decir puede explorar cualquier nivel de granuralidad.
– Clúster jerárquico agglomerativo produce generalmente los mejores resultados.
– Son más complejos computacionalmente.
– Ineficiente y poco práctico para conjuntos de datos muy grandes.
• Alguna veces se puede aplicar métodos de escalamiento (scale-up methods) para combatir el problema con los conjuntos de datos muy grandes.
• La idea es encontrar en primera instancia muchos clústers pequeños utilizando un algoritmo eficiente.
• Después se utiliza el centroide de esos clústers para representar los clústers, y de ahí ejecutar el clustering jerárquico final.

Question 20

Funciones de Distancia

Answer 20

• Para atributos numéricos: – Minkowski
– Euclidean
– Manhattan
– Weighted Euclidean – Squared Euclidean – Chebychev

• Otros tipos de atributos:
– Binarios: Por ejemplo, el genero (masculino y femenino). Normalmente no hay una relación de orden. Las métricas se basan en la proporción de coincidencias en los valores: ambos falsos o verdaderos.

– Simétricos: si ambos estados tienen la misma importancia, por ende tienen el mismo peso. La función de distancia más usada es la distancia de simple coincidencias:

– Asimétricos: Si un valor es más importante que el otro. Por convención, se toma como el positivo (1) como el estado más importante o raro. Una distancia que se puede utilizar es la Jaccard:

Question 21

Estandarización de Datos

Answer 21

• La idea de estandarización es que todos los atributos puedan tener igual impacto en el cómputo de la distancia.
• En especial, cuando se usa la distancia euclidiana.
• El objetivo es prevenir que hayan clústers dominados por atributos con una alta variación.

Question 22

Estandarización de Datos

• Range

Answer 22

divide cada valor por el rango de valores válidos de los atributos talque los rangos de los valores transformados estén entre 0 y 1.
• Dado el valor xif del f-ésimo atributo del i- ésimo data point, el nuevo valor rg(xif) es,

Question 23

Estandarización de Datos z-score

Answer 23

El método de z-score transforma el valor de un atributo basado en la media y en la desviación estándar del atributo.
• El z-score indica cual lejos y en qué dirección el valor se desvía desde la media del atributo, expresado en unidades de la desviación estándar del atributo.

Question 24

Atributos Mixtos

Answer 24

• Es posible que un data set contenga atributos de diferente valores.
• Una alternativa es escoger el atributo dominante y convertir los atributos de otros tipos al tipo dominante.
• Otra forma de manejar atributos mixtos es calcular la distancia de cada atributo de los dos puntos de datos de manera separada, y combinar las distancias individuales para producir una distancia final.

Question 25

Evaluación

Answer 25

• Como no tenemos etiquetas, no sabemos los clústers correctos.
• Inspección del usuario: un panel de expertos examina los resultados. Como los expertos difieren frecuentemente, se toma un promedio.
– Es una tarea que consume mucho tiempo.
– Consume muchos recursos humanos.
– Es fácil para algunos tipos de datos, pero no para otros.

• Utilizar un set de datos anotados y que se pueden utilizar para clasificación.
• Entropía: para cada clúster podemos medir su
entropía.

Question 26

Evaluación

• Purity:

Answer 26

mide el grado en que un clúster contiene sólo una clase de datos:
purity(D )  max (Pr (c )) ijij
• La purity total está dada por:
D
i   purity(D )
• También se puede utilizar recall, precisión y F- Score basado en la clase más frecuente de un clúster.

Question 27

Métricas

Answer 27

Rand Index: determina el grado de similitud entre las etiquetas dadas U y la solución V generada por el algoritmo
de clustering:

Question 28

Métricas

• La varianza interna

Answer 28

calcula la suma de las desviaciones cuadradas entre todos los ítems de datos y su centro asociado

Question 29

Métricas

• El índice de Dunn

Answer 29

determina el ratio mínimo entre el diámetro del clúster y la distancia inter clúster para un particionamiento dado.
– La idea es que elementos dentro de un clúster deben estar más cerca que aquellos en clústeres diferentes.

Question 30

Fuzzy C-Means

Answer 30

Es un método que permite a un data-point pertenecer a dos o más clústeres.
• Se basa en la minimización de la siguiente función objetivo:

• El particionamiento fuzzy o difuso es un proceso iterativo que busca optimizar Jm mediante la actualización de los grados de membrecía uij y los centros cj:

Question 31

K-means vs. FCM:

Answer 31

En las funciones de membrecía, K- means tiene 0’s y 1’s, y FCM grados de membrecía [0,1].

Question 32

Clustering con Algoritmo Genéticos

Answer 32

• Uno de los problemas de los algoritmos de clustering tipo K-means es que el valor de “k” es ingresado por el usuario. O bien, varios “k” deben probarse.
• Por lo general, el valor de “k” es desconocido.
• La idea es utilizar algoritmos genéticos para
solucionar este problema.
• La solución de K-means también depende del punto de partida.
– K-means puede converger a un óptimo local.

• Hay varias versiones de algoritmos genéticos que apuntan a resolver algunos de estos problemas de clustering.
• Si uno considera el k fijo, podría diseñar un GA donde cada individuo de la población representa los centros de cada uno de los “k” clústers.
• Entonces, uno podría utilizar como función objetivo la suma de las distancias de cada punto al centro del clúster respectivo.
• Elobjetivo,entonces,seríaminimizaresta distancia.

En general, la selección y la mutación no presentan problemas.
• La función objetivo (minimizar el SSE) puede optimizarse recalculando las partes “nuevas”.
– Si los centroides no cambian, entonces, no es necesario calcular la función objetivo completa de nuevo.
– Sin embargo, si cambian los centroides …. Habría que ver si el actual sigue siendo el más cercano.