Estoy buscando una implementación decente del algoritmo OPTICS en Python. Lo usaré para formar grupos basados en la densidad de pares de puntos ((x, y)).Implementación de Python del algoritmo OPTICS (Clustering)
Estoy buscando algo que tome en (x, y) pares y muestre una lista de clusters, donde cada cluster en la lista contiene una lista de pares (x, y) que pertenecen a ese cluster.
EDITAR: se sabe lo siguiente no sea una implementación completa de OPTICS.
Hice una búsqueda rápida y encontré lo siguiente (Optics). No puedo garantizar su calidad, sin embargo, el algoritmo parece bastante simple, por lo que debería poder validarlo/adaptarlo rápidamente.
Aquí está un ejemplo rápido de cómo construir racimos en la salida del algoritmo de la óptica:
def cluster(order, distance, points, threshold):
''' Given the output of the options algorithm,
compute the clusters:
@param order The order of the points
@param distance The relative distances of the points
@param points The actual points
@param threshold The threshold value to cluster on
@returns A list of cluster groups
'''
clusters = [[]]
points = sorted(zip(order, distance, points))
splits = ((v > threshold, p) for i,v,p in points)
for iscluster, point in splits:
if iscluster: clusters[-1].append(point)
elif len(clusters[-1]) > 0: clusters.append([])
return clusters
rd, cd, order = optics(points, 4)
print cluster(order, rd, points, 38.0)
Gracias Bashwork pero parece el mismo código exacto que lo que vartec ha sugerido. El problema con esto es que no pude entender cómo extraería la estructura de clúster (qué elementos pertenecen a qué clúster) de la salida de ese algoritmo. Por favor, eche un vistazo a la 'Nota' en la parte inferior de mi pregunta. –
El código le proporciona la salida que necesita para extraer los clústeres (el orden y la distancia de alcance). Si mira la sección de wikipedia para extraer clusters, simplemente necesita recorrer los resultados ordenados con un umbral en las distancias (umbral más bajo significa más clusters). (http://en.wikipedia.org/wiki/OPTICS_algorithm). Si esto no tiene sentido, puedo dar un código de ejemplo. – Bashwork
Acabo de ejecutar el código que ha publicado y el resultado que obtengo con un umbral de 38 es [[31.0, 87.0], [73.0, 9.0]] [[5.0, 8.0]] [[97.0, 9.0]] (3 grupos). Bajé el umbral a 10 y solo hay 1 clúster. Los datos de prueba que utilicé son los mismos que los utilizados en el enlace que proporcionó (testX). Te agradecería que pudieras corregir el código y yo otorgaré tu recompensa. –
Ver "agrupación enfoques basados en la densidad" en la http://www.chemometria.us.edu.pl/index.php?goto=downloads
Gracias para la respuesta vartec, pero la implementación me pareció incompleta. Estoy buscando algo que tome en pares (x, y) y entregue una lista de clústeres, donde cada grupo de la lista contiene una lista de pares (x, y) que pertenecen a ese grupo. –
que desea buscar en un relleno de espacio de la curva o un índice espacial. Un sfc reduce la complejidad 2d a una complejidad 1d. Desea ver el blog de índice espacial htlbert curve quadtree de Nick. Desea descargar mi implementación de un sfc en phpclasses.org (hilbert-curve).
Gracias epitafio, pero ¿cómo responde esto exactamente a mi pregunta? ¿Puedes aclarar tu respuesta un poco más? –
Un sfc es un algoritmo de agrupamiento que utiliza un fractal. Una curva hilbert tiene una dimensión fractal de 2. Si tiene datos 2d, puede subdividir fácilmente estos datos en mosaicos más pequeños. Básicamente es un reordenamiento. Es como almacenarlos en un quadtree. También puede usar un sfc adaptativo donde las regiones emtpy se omiten o tienen una granularidad menor del sfc. Sfc se usa a menudo en mapas, como google maps. – Bytemain
Suena bien y vale la pena intentarlo. Gracias. Pero todavía estoy buscando una implementación de OPTICS en Python. –
No estoy al tanto de un completa y exacta aplicación de pitón de la óptica. Los enlaces publicados aquí parecen aproximaciones aproximadas de la idea OPTICS. Tampoco usan un índice para la aceleración, por lo que se ejecutarán en O(n^2) o más probablemente incluso O(n^3).
OPTICS tiene una serie de cosas complicadas además de la idea obvia. En particular, se propone que el umbral se haga con umbrales relativos ("xi") en lugar de los umbrales absolutos tal como se publica aquí (en cuyo caso el resultado será aproximadamente el de DBSCAN).
El documento ÓPTICA original contiene un enfoque sugerido para convertir la salida del algoritmo en grupos reales:
http://www.dbs.informatik.uni-muenchen.de/Publikationen/Papers/OPTICS.pdf
La aplicación Óptica en Weka es esencialmente sin mantenimiento y tan incompleta. En realidad, no produce clústeres, solo calcula el orden del clúster. Para esto hace un duplicado de la base de datos, no es realmente el código Weka.
Parece haber una implementación bastante amplia disponible en ELKI en Java por el grupo que publicó OPTICS en primer lugar. Es posible que desee probar cualquier otra implementación en contra de esta versión "oficial".
De hecho, hay muchas implementaciones de OPTICS incompletas y clones de la versión de Weka. Debes tomar la versión ELKI como referencia. –
El umbral relativo es, en mi opinión, el punto donde una exposición relativamente clara y la transición de enfoque a algo mucho más nublado, con heurística adicional y parámetros ocultos. Probablemente no haya forma de evitar esto, pero definitivamente siento que los valores intermedios de accesibilidad ordenada constituyen un buen resultado que se sostiene por sí mismo. Lo que sucede después está abierto a diferentes enfoques, y el elegido en este documento no es tan evidente como para ser el único que vale la pena considerar. – micans
Hay al menos dos métodos más propuestos para cómo clusters exactos de la trama. Sin embargo, sin dicho método de extracción de clúster, ¿es realmente un algoritmo de agrupamiento? En algún momento, querrás obtener clústers, no solo un argumento. –
Aunque técnicamente OPTICS no existe una implementación HDBSCAN * para python disponible en https://github.com/lmcinnes/hdbscan. Esto es equivalente a OPTICS con un épsilon máximo infinito y un método de extracción de clúster diferente. Dado que la implementación proporciona acceso a la jerarquía de clúster generada, también puede extraer clústeres a través de métodos OPTICS más tradicionales, si así lo prefiere.
Tenga en cuenta que, a pesar de no limitar el parámetro épsilon, esta implementación todavía logra el rendimiento O (n log (n)) utilizando algoritmos de árboles de expansión mínima basados en árboles de bolas y árboles de bolas and can handle quite large datasets.
¿miraste SciPy: http://docs.scipy.org/doc/scipy/reference/cluster.html? – vartec
@vartec - Sí, lo hice. En realidad, estaba usando los métodos de agrupación jerárquica que se proporcionan allí (fcluster). Pero ahora, me gustaría cambiar a OPTICS. –
¿OPTICS es un algoritmo tan desconocido/desconocido que mi pregunta no recibe atención? = ( –