Реализация алгоритма OPTICS (кластеризация) в Python
Я ищу достойную реализацию алгоритма OPTICS в Python. Я буду использовать его для формирования кластеров точек ((x,y) на основе плотности).
Я ищу что-то, что принимает пары (x, y) и выводит список кластеров, где каждый кластер в списке содержит список (x, y) пар, принадлежащих этому кластеру.
6 ответов
РЕДАКТИРОВАТЬ: известно, что следующее не является полной реализацией ОПТИКИ.
Я сделал быстрый поиск и нашел следующее ( Оптика). Я не могу ручаться за его качество, однако алгоритм кажется довольно простым, поэтому вы сможете быстро его проверить / адаптировать.
Вот быстрый пример того, как построить кластеры на выходе алгоритма оптики:
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)
Я не знаю о полной и точной реализации OPTICS на python. Ссылки, размещенные здесь, кажутся лишь приблизительным приближением идеи ОПТИКИ. Они также не используют индекс для ускорения, поэтому они будут работать в O(n^2) или, более вероятно, даже O(n^3),
У ОПТИКИ есть много хитрых вещей, помимо очевидной идеи. В частности, предлагается установить пороговое значение с относительными пороговыми значениями ("xi") вместо абсолютных пороговых значений, как указано здесь (в этот момент результат будет приблизительно таким же, как у DBSCAN!).
Оригинальная статья OPTICS содержит предложенный подход к преобразованию вывода алгоритма в фактические кластеры:
http://www.dbs.informatik.uni-muenchen.de/Publikationen/Papers/OPTICS.pdf
Реализация OPTICS в Weka практически не поддерживается и столь же неполна. На самом деле он не создает кластеры, он только вычисляет порядок кластеров. Для этого он создает копию базы данных - это не совсем код Weka.
Кажется, существует довольно обширная реализация, доступная в ELKI на Java группой, которая опубликовала OPTICS в первую очередь. Возможно, вы захотите протестировать любую другую реализацию с этой "официальной" версией.
Хотя технически это не ОПТИКА, существует реализация HDBSCAN* для python, доступная по адресу https://github.com/lmcinnes/hdbscan. Это эквивалентно ОПТИКЕ с бесконечным максимальным эпсилоном и другим методом выделения кластера. Поскольку реализация предоставляет доступ к сгенерированной кластерной иерархии, вы также можете извлечь кластеры из нее с помощью более традиционных методов OPTICS.
Обратите внимание, что, несмотря на не ограничение параметра epsilon, эта реализация по-прежнему достигает производительности O(n log(n)) с использованием алгоритмов минимального связующего дерева на основе kd-дерева и шарового дерева и может обрабатывать довольно большие наборы данных.
В настоящее время существует библиотека pyclustering, которая содержит, среди прочего, реализацию OPTICS на языке Python и C++.
Теперь он реализован в разрабатываемой версии (scikit-learn v0.21.dev0) sklearn (модуль обучения кластеризации и машинного обучения для python)
вот ссылка: https://scikit-learn.org/dev/modules/generated/sklearn.cluster.OPTICS.html
См. "Кластерные подходы на основе плотности" на http://www.chemometria.us.edu.pl/index.php?goto=downloads
Вы хотите посмотреть на кривую заполнения пространства или пространственный индекс. Sfc уменьшает 2d сложность до 1d сложности. Вы хотите взглянуть на блог пространственного индекса дерева квадратов кривой Гильберта. Вы хотите скачать мою реализацию sfc на phpclasses.org (кривая Гильберта).