Implementación en Python del Algoritmo de ÓPTICA (Clustering)
Estoy buscando una implementación decente del algoritmo OPTICS en Python. Lo usaré para formar clusters de puntos basados en densidad (pares (x,y)).
Estoy buscando algo que tome pares (x,y) y genere una lista de clústeres, donde cada clúster de la lista contenga una lista de pares (x, y) pertenecientes a ese clúster.
6 answers
EDITAR: lo siguiente es conocido por no ser una implementación completa de la ÓPTICA.
Hice una búsqueda rápida y encontré lo siguiente ( Óptica). No puedo garantizar su calidad, sin embargo, el algoritmo parece bastante simple, por lo que debería ser capaz de validarlo/adaptarlo rápidamente.
Aquí hay un ejemplo rápido de cómo construir clústeres en la salida del algoritmo de ó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)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-08-13 09:58:27
No soy consciente de una completa y exacta implementación de python de la ÓPTICA. Los enlaces publicados aquí parecen aproximaciones aproximadas de la idea ÓPTICA. Tampoco utilizan un índice para la aceleración, por lo que se ejecutarán en O(n^2) o más probablemente incluso O(n^3).
La ÓPTICA tiene una serie de cosas difíciles además de la idea obvia. En particular, se propone que el umbral se haga con umbrales relativos ("xi") en lugar de umbrales absolutos como se indica aquí (momento en el que el resultado será aproximadamente el de DBSCAN!).
El documento original de OPTICS contiene un enfoque sugerido para convertir la salida del algoritmo en clústeres reales:
Http://www.dbs.informatik.uni-muenchen.de/Publikationen/Papers/OPTICS.pdf
La implementación de la ÓPTICA en Weka es esencialmente no mantenida e igual de incompleta. En realidad no produce clústeres, solo calcula el orden del clúster. Para ello hace un duplicado de la base de datos - no es realmente código Weka.
Parece haber una implementación bastante extensa disponible en ELKI en Java por el grupo que publicó OPTICS en primer lugar. Es posible que desee probar cualquier otra implementación contra esta versión "oficial".
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-07-31 13:54:53
Aunque técnicamente no es ÓPTICA, hay una implementación HDBSCAN * para python disponible en https://github.com/lmcinnes/hdbscan . Esto es equivalente a la ÓPTICA con un epsilon infinito máximo, y un método de extracción de cúmulos diferente. Dado que la implementación proporciona acceso a la jerarquía de clústeres generada, también puede extraer clústeres a través de métodos ÓPTICOS más tradicionales, si lo prefiere.
Tenga en cuenta que a pesar de no limitar el parámetro epsilon, la implementación aún logra un rendimiento O(n log(n)) utilizando algoritmos de árbol de expansión mínimo basados en kd-tree y ball-tree, y puede manejar conjuntos de datos bastante grandes.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-04-15 16:47:18
Ahora existe la biblioteca pyclustering que contiene, entre otros, una implementación de Python y C++ de OPTICS.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2018-06-11 08:19:37
Ver "Enfoques de clustering basados en densidad" en http://www.chemometria.us.edu.pl/index.php?goto=downloads
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-04-01 16:04:55
Desea ver una curva de relleno de espacio o un índice espacial. Un sfc reduce la complejidad 2d a una complejidad 1d. Quieres ver el blog de Nick Hilbert curve quadtree spatial index. Quieres descargar mi implementación de un sfc en phpclasses.org (hilbert-curve).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-04-23 21:27:39