learning - Implementación de Python del algoritmo OPTICS(Clustering)

machine-learning cluster-analysis

Question

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)).

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.

Answer 1

Ahora existe la biblioteca pyclustering que contiene, entre otros, una implementación de OPTICS en Python y C ++.

Answer 2

Consulte "Enfoques de agrupamiento basados ​​en densidad" en http://www.chemometria.us.edu.pl/index.php?goto=downloads

Answer 3

Desea ver una curva de relleno de espacio 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).

Answer 4

No conozco una implementación pitón completa y exacta de OPTICS. 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 en 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 umbrales absolutos tal como se publica aquí (¡en cuyo caso el resultado será aproximadamente el de DBSCAN!).

El documento original de OPTICS contiene un enfoque sugerido para convertir el resultado del algoritmo en clusters reales:

http://www.dbs.informatik.uni-muenchen.de/Publikationen/Papers/OPTICS.pdf

La implementación de OPTICS en Weka está esencialmente sin mantenimiento y es igualmente 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 que hay 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 en contra de esta versión "oficial".

Answer 5

Si bien no es técnicamente OPTICS, hay 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 aún logra el rendimiento O (n log (n)) usando algoritmos de árbol de expansión mínimo basados ​​en árboles de bolas y árboles de bolas, y puede manejar conjuntos de datos bastante grandes .

Answer 6

EDITAR: se sabe que no se trata de 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í hay un ejemplo rápido de cómo crear clusters 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)