Я ищу достойную реализацию алгоритма OPTICS в Python. Я буду использовать его для создания кластеров точек точек ((x, y)) на основе плотности.
Я ищу что-то, что принимает пары (x, y) и выводит список кластеров, где каждый кластер в списке содержит список (x, y) пар, принадлежащих этому кластеру.
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)
Я не знаю полной и точной реализации 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. Вы можете протестировать любую другую реализацию против этой "официальной" версии.
В то время как технически ОПТИКА существует реализация HDBSCAN * для python, доступная по адресу https://github.com/lmcinnes/hdbscan. Это эквивалентно ОПТИКЕ с бесконечным максимальным эпсилон и другим методом извлечения кластера. Поскольку реализация обеспечивает доступ к сгенерированной кластерной иерархии, вы можете извлечь кластеры из нее с помощью более традиционных методов OPTICS, если вы предпочитаете.
Обратите внимание, что, несмотря на то, что это не ограничивает параметр epsilon, эта реализация по-прежнему достигает производительности O (n log (n)), используя алгоритмы минимального спаривания дерева kd-tree и ball tree, и может обрабатывать довольно большие наборы данных.
См. "Подходы кластеризации на основе плотности" на http://www.chemometria.us.edu.pl/index.php?goto=downloads
Вы хотите посмотреть кривую пространственного заполнения или пространственный индекс. Sfc уменьшает сложность 2d до сложности 1d. Вы хотите посмотреть на блог с пространственным индексом квадроциклов Nick hilbert. Вы хотите загрузить мою реализацию sfc на phpclasses.org(hilbert-curve).