Clustering Flashcards
Qué tipo de problemas es el que más comúnmente se asocia al clustering?
El llamado aprendizaje no supervisado, ya que permite, dado un conjunto de datos, encontrar clusters y de esta forma poder agruparlos bajo cierto criterio.
Explique el algoritmo de clustering jerárquico.
- El algoritmo empieza considerando cada dato como un cluster.
- En cada paso une los dos clusters más cercanos entre sí.
- itera hasta qudar todos los datos en un solo cluster.
Qué hiperparámetros hay que definir para el algoritmo de clusetering jerárquico? Ejemplifique
- distancia a usar.
Se usa la que mejor ajuste. - cómo calcular la distancia entre clusters.
Se puede tomar: - distancia mínima entre dos puntos de cada cluster
- distancia máxima entre dos puntos de cada cluster
- el promedio de las distancias de todos los puntos de un cluster contra todos los puntos del otro cluster
- la distancia entre los promedios de los puntos de cada cluster (centroides)
- el método de Ward (Ward suggested a general agglomerative hierarchical clustering procedure, where the criterion for choosing the pair of clusters to merge at each step is based on the optimal value of an objective function. This objective function could be “any function that reflects the investigator’s purpose.”) [https://en.wikipedia.org/wiki/Ward%27s_method]
Ventajas y desventajas de tomar distancia mínima entre dos puntos de cada cluster en clustering jerárquico.
Ventajas: Puede separar formas no elípticas de clusters, siempre y cuando la distancia entre clusters no sea demasiado grande.
Desventajas: sensibilidad al ruido.
Ventajas y desventajas de tomar distancia máxima entre dos puntos de cada cluster en clustering jerárquico.
Ventajas: se comporta bien con datos ruidosos.
Desventajas: tiene bias hacia clusters globulares y tiende a partir clusters grandes.
Ventajas y desventajas de tomar el promedio de las distancias de todos los puntos de un cluster contra todos los puntos del otro cluster en clustering jerárquico.
Ventajas: se comporta bien con datos ruidosos.
Desventajas: tiene bias hacia clusters globulares.
Qué desventaja tiene el clustering jerárquico?
Es sensible a los outliers.
En cada iteración hay que calcular la distancia entre cada par de clusters.
De qué forma se puede evitar calcular las distancias entre cada par de clusters en clustering jerárquico?
Se puede encarar con LSH. Por cada cluster creado se calcula el centroide y se usa LSH para determinar cuáles juntar próximamente.
Qué hiperparámetros recibe K-means?
Recibe un solo hp: k.
centroide vs clusteroide
un clusteroide es un centroide que es además uno de los datos dados.
un centroide es el punto promedio de los puntos en un cluster dado.
Describa el algoritmo K-means.
- Se inicializan k centroides al azar.
- Se asigna cada punto al cluster mas cercano.
- Se recalculan los centroides.
Se demuestra que el algoritmo converge.
Que problema tiene K-means y como se lo puede mitigar?
Al ser un algoritmo que encuentra un minimo local, es muy sensible a la posicion inicial del centroide.
Se lo puede mitigar haciendo varias corridas del algoritmo y quedandose con la version de menor dispersion.
Esto no es tan problematico si se piensa que luego de unas pocas iteraciones el resultado ya cambia muy poco, por lo que no es necesario correr el algoritmo hasta el final.
Describa el algoritmo K-means++.
Lo unico que cambia con respecto a k-means es que no inicializa los centroides al azar.
Se arranca inicializando un centroide. Para inicializar el segundo centroide se busca que el mismo este alejado del primero, por lo que a cada punto le es asignada una probabilidad de acuerdo a su distancia al perimer centroide y en base a dicha probabilidad se elgie el proximo centroide al azar.
Cual es el problema de k-means++ y como se lo mitiga?
El problema es que para datos masivos, debe realizar k iteraciones sobre los datos para elegir los centroides, lo cual es muy ineficiente.
La alternativa que existe en estos casos se denomina k-means parallel. En lugar de k se hacen log(k) pasadas, agregando en cada iteracion en lugar de 1, l centroides.
Finalmente, como se obitenen mas de k centroides, se definen los centroides finales clusterizando los candidatos a centroides ponderados por la probabilidad con la cual fueron seleccionados. Este paso se puede hacer con, por ejemplo, clustering jerarquico.
Valor de k a utilizar y metricas usadas al respecto.
La forma de buscar k es mediante un Grid-Search con diferentes valores posibles.
Como métrica para evaluar la calidad de cada valor de k se puede usar un promedio de nuestra función de distorsión para varias iteraciones de K-Means o el diámetro promedio de los clusters.
