Aprendizaje No-Supervisado Flashcards
(32 cards)
Clustering NS?
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.
Tipos de clustering
- 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.
Clustering Particional: K-means
- 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).
Ventajas de KMEANS
- 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.
DESVENTAJAS de kmeans
– 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.
Outlier
es un punto que esta lejano a culquier cluster que ha formado.
Solución 1 Outlier
- 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.
Solución 2 outlier
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.
aprendizaje semi-supervisado. (breve)
– Es un paradigma que aprende de un conjunto reducido de ejemplos etiquetados y de un conjunto grande de datos no etiquetados.
problema de K-means son las semillas iniciales:
– 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.
Clustering Jerárquico
- 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
Clustering Jerárquico - Agglomerativos (bottom-up):
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
Clustering Jerárquico - Divise (top-down):
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.
Clustering Jerárquico - calculo distancia
• Para calcular la distancia entre dos clústers:
– Single-Link
– Complete-Link
– Average-Link
• Single-Link:
– 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.
Complete-Link
– 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.
Average-Link:
– 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.
Otros metodos de calculo de distnancia entre clusters
– 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.
Clustering jerárquico tiene ventajas
– 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.
Funciones de Distancia
• 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:
Estandarización de Datos
- 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.
Estandarización de Datos
• Range
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,
Estandarización de Datos z-score
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.
Atributos Mixtos
- 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.
