Python Реализация алгоритма OPTICS (Clustering)

Я ищу достойную реализацию алгоритма OPTICS в Python. Я буду использовать его для создания кластеров точек точек ((x, y)) на основе плотности.

Я ищу что-то, что принимает пары (x, y) и выводит список кластеров, где каждый кластер в списке содержит список (x, y) пар, принадлежащих этому кластеру.

Ответы

Ответ 1

EDIT: известно, что не является полной реализацией OPTICS.

Я сделал быстрый поиск и нашел следующее (Optics). Я не могу ручаться за его качество, однако алгоритм кажется довольно простым, поэтому вы должны быстро его проверить и адаптировать.

Вот краткий пример создания кластеров на выходе алгоритма оптики:

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)

Ответ 2

Я не знаю полной и точной реализации OPTICS на Python. Ссылки, размещенные здесь, кажутся просто грубыми приближениями идеи OPTICS. Они также не используют индекс для ускорения, поэтому они будут работать в O(n^2) или, скорее, даже O(n^3).

ОПТИКА имеет ряд сложных вещей, помимо очевидной идеи. В частности, пороговое значение предлагается сделать с относительными пороговыми значениями ( "xi" ) вместо абсолютных порогов, как указано здесь (в этот момент результат будет примерно равен DBSCAN!).

Оригинальная бумага OPTICS содержит предлагаемый подход к преобразованию выхода алгоритма в реальные кластеры:

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

Реализация OPTICS в Weka по существу не поддерживается и так же неполна. Он фактически не создает кластеры, он только вычисляет порядок кластеров. Для этого он создает дубликат базы данных - это действительно не Weka-код.

В Java существует довольно обширная реализация, доступная в ELKI в группе Java, опубликовавшей OPTICS. Вы можете протестировать любую другую реализацию против этой "официальной" версии.

Ответ 3

В то время как технически ОПТИКА существует реализация HDBSCAN * для python, доступная по адресу https://github.com/lmcinnes/hdbscan. Это эквивалентно ОПТИКЕ с бесконечным максимальным эпсилон и другим методом извлечения кластера. Поскольку реализация обеспечивает доступ к сгенерированной кластерной иерархии, вы можете извлечь кластеры из нее с помощью более традиционных методов OPTICS, если вы предпочитаете.

Обратите внимание, что, несмотря на то, что это не ограничивает параметр epsilon, эта реализация по-прежнему достигает производительности O (n log (n)), используя алгоритмы минимального спаривания дерева kd-tree и ball tree, и может обрабатывать довольно большие наборы данных.

Ответ 5

Вы хотите посмотреть кривую пространственного заполнения или пространственный индекс. Sfc уменьшает сложность 2d до сложности 1d. Вы хотите посмотреть на блог с пространственным индексом квадроциклов Nick hilbert. Вы хотите загрузить мою реализацию sfc на phpclasses.org(hilbert-curve).