Как работает стандартный DBSCAN от sklearn? - PullRequest
Новая
       14

Как работает стандартный DBSCAN от sklearn?

0 голосов
/ 05 июля 2018

Я возился с альтернативными реализациями DBSCAN для кластеризации радиолокационных данных (например, DBSCAN на основе сетки). До этого момента я использовал стандартный евклидовый DBSCAN от sklearn, и он работал на 26 000 точек данных менее чем за секунду. Однако, когда я указываю свою собственную метрику расстояния, вот так: 

X = np.column_stack((beam, gate, time_index))
num_pts = X.shape[0]
epsilons = np.array([[beam_eps]*num_pts, [gate_eps] * num_pts, [time_eps] * num_pts]).T

metric = lambda x, y, eps: np.sqrt(np.sum((x/eps - y/eps)**2))
def dist_metric(x, y, eps):
    return np.sqrt(np.sum((x - y)**2))

db = DBSCAN(eps=eps, min_samples=minPts, metric=dist_metric, metric_params={'eps': epsilons}).fit(X)

для обработки одних и тех же данных требуется от 0,36 до 92 минут.

То, что я сделал в этом фрагменте кода, также можно выполнить, просто предварительно преобразовав данные и запустив стандартный евклидовый DBSCAN, но я пытаюсь реализовать достаточно быструю версию DBSCAN на основе Grid, для которой горизонтальный эпсилон изменяется в зависимости от на расстоянии от радара, поэтому я не смогу это сделать.

Частично медлительность в вышеуказанной метрике расстояния объясняется этим делением на эпсилон, я думаю, потому что для запуска требуется только около минуты, если я использую «пользовательскую метрику», которая является просто евклидовым расстоянием: 

metric = lambda x, y: np.sqrt(np.sum((x - y)**2))

Как евклидовому DBSCAN от sklearn удается работать намного быстрее? Я копался в коде, но пока не понял этого.

1 Ответ

0 голосов
/ 06 июля 2018

Поскольку он использует индекс.

Кроме того, он избегает медленного и интенсивного использования интерпретатора Python , но выполняет всю работу в собственном коде (скомпилированном из Cython). Это имеет огромное значение при работе с большим количеством примитивных данных, таких как двойные и целые числа, которые интерпретатор Python должен будет заполнить.

Индексы имеют все значение для поиска сходства. Они могут сократить время выполнения с O (n²) до O (n log n).

Но хотя индекс шарового дерева допускает создание пользовательских метрик, стоимость вызова интерпретатора Python для каждого вычисления расстояния очень высока, поэтому, если вы действительно хотите использовать собственную метрику, отредактируйте исходный код Cython и откомпилируйте sklearn самостоятельно. Или вы можете использовать ELKI, потому что Java JVM может компилировать код расширения в нативный код при необходимости; он не должен отступать от медленных обратных вызовов интерпретатора, таких как sklearn.

В вашем случае, скорее всего, будет гораздо лучше предварительно обработать данные. Масштабируйте его до кластеризации.

...