algorithm - supervisada - herramienta cluster
Agrupación no supervisada con un número desconocido de clusters (3)
La respuesta de moooeeeep recomendaba el uso de clústeres jerárquicos. Quería elaborar sobre cómo elegir el umbral de la agrupación.
Una forma es calcular las agrupaciones basadas en diferentes umbrales t1 , t2 , t3 , ... y luego calcular una métrica para la "calidad" de la agrupación. La premisa es que la calidad de una agrupación con el número óptimo de clústeres tendrá el valor máximo de la métrica de calidad.
Un ejemplo de una métrica de buena calidad que he usado en el pasado es Calinski-Harabasz. Brevemente: calcula las distancias promedio entre clusters y las divide por las distancias dentro del clúster. La asignación de clúster óptima tendrá los clústeres que están separados el uno del otro y los clústeres que son "más estrechos".
Por cierto, no tiene que usar clústeres jerárquicos. También puede usar algo como k- medias, calcularlo previamente para cada k , y luego elegir la k que tenga el puntaje más alto de Calinski-Harabasz.
Avíseme si necesita más referencias y buscaré algunos documentos en mi disco duro.
Tengo un gran conjunto de vectores en 3 dimensiones. Necesito agrupar estos en función de la distancia euclidiana de modo que todos los vectores en un grupo particular tengan una distancia euclidiana entre ellos menor que un umbral "T".
No sé cuántos clusters existen. Al final, pueden existir vectores individuales que no forman parte de ningún clúster porque su distancia euclidiana no es inferior a "T" con ninguno de los vectores en el espacio.
¿Qué algoritmos / enfoque existentes deberían usarse aquí?
Mira el algoritmo https://en.wikipedia.org/wiki/DBSCAN . Se agrupa en función de la densidad local de vectores, es decir, no debe estar a más de una distancia de separación de ε , y puede determinar automáticamente el número de clústeres. También considera valores atípicos, es decir, puntos con un número insuficiente de vecinos ε , para no formar parte de un clúster. La página de Wikipedia vincula a algunas implementaciones.
Puede usar la agrupación jerárquica . Es un enfoque bastante básico, por lo que hay muchas implementaciones disponibles. Por ejemplo, está incluido en el scipy de Python.
Ver por ejemplo la siguiente secuencia de comandos:
import matplotlib.pyplot as plt
import numpy
import scipy.cluster.hierarchy as hcluster
# generate 3 clusters of each around 100 points and one orphan point
N=100
data = numpy.random.randn(3*N,2)
data[:N] += 5
data[-N:] += 10
data[-1:] -= 20
# clustering
thresh = 1.5
clusters = hcluster.fclusterdata(data, thresh, criterion="distance")
# plotting
plt.scatter(*numpy.transpose(data), c=clusters)
plt.axis("equal")
title = "threshold: %f, number of clusters: %d" % (thresh, len(set(clusters)))
plt.title(title)
plt.show()
Que produce un resultado similar a la siguiente imagen.
El umbral dado como parámetro es un valor de distancia sobre cuya base se toma la decisión de si los puntos / clústeres se fusionarán en otro grupo. La métrica de distancia que se usa también se puede especificar.
Tenga en cuenta que existen varios métodos para calcular la similitud intra e inter-clúster, por ejemplo, la distancia entre los puntos más cercanos, la distancia entre los puntos más lejanos, la distancia a los centros del grupo y así sucesivamente. Algunos de estos métodos también son compatibles con el módulo de clúster jerárquico scipys ( enlace único / completo / promedio ... ). De acuerdo con su publicación, creo que le gustaría usar un enlace completo .
Tenga en cuenta que este enfoque también permite clústeres pequeños (punto único) si no cumplen el criterio de similitud de los otros grupos, es decir, el umbral de distancia.
Hay otros algoritmos que funcionarán mejor, que serán relevantes en situaciones con muchos puntos de datos. Como otras respuestas / comentarios sugieren que es posible que también desee echarle un vistazo al algoritmo DBSCAN:
- https://en.wikipedia.org/wiki/DBSCAN
- http://scikit-learn.org/stable/auto_examples/cluster/plot_dbscan.html
- http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html#sklearn.cluster.DBSCAN
Para obtener una buena descripción de estos y otros algoritmos de agrupamiento, también eche un vistazo a esta página de demostración (de la biblioteca scikit-learn de Python):
Imagen copiada de ese lugar:
Como puede ver, cada algoritmo hace suposiciones sobre el número y la forma de los clusters que deben tenerse en cuenta. Ya se trate de suposiciones implícitas impuestas por el algoritmo o supuestos explícitos especificados por la parametrización.