Использование памяти DBSCAN scikit-learn
ОБНОВЛЕНО:. В конце концов, решение, которое я выбрал для кластеризации моего большого набора данных, было предложено Anony-Mousse ниже. То есть, используя ELKI DBSCAN implimentation для моей кластеризации, а не для scikit-learn. Его можно запустить из командной строки и с правильной индексацией, выполняет эту задачу в течение нескольких часов. Используйте графические интерфейсы и небольшие образцы данных для разработки вариантов, которые вы хотите использовать, а затем перейдите в город. Стоит посмотреть. Anywho, читайте дальше для описания моей оригинальной проблемы и некоторого интересного обсуждения.
У меня есть набор данных с ~ 2,5 миллионами выборок, каждый из которых имеет 35 функций (значения с плавающей запятой), которые я пытаюсь сгруппировать. Я пытался это сделать с помощью scikit-learn реализации DBSCAN, используя метрику расстояния Манхэттена и значение epsilon, оцененное по некоторым небольшим случайным образцам, взятым из данных. Все идет нормально. (здесь приведен фрагмент, для справки)
db = DBSCAN(eps=40, min_samples=10, metric='cityblock').fit(mydata)
Моя проблема на данный момент заключается в том, что я легко исчерпал память. (Сейчас я работаю на машине с 16 ГБ ОЗУ)
Мой вопрос в том, что DBSCAN рассчитывает парную матрицу расстояний "на лету", когда она работает, и что то, что поглощает мою память? (2,5 миллиона ^ 2) * 8 байтов, очевидно, глупо большое, я бы это понял. Должен ли я использовать метод fit()? И, в общем, есть ли способ обойти эту проблему, или я вообще лаяю здесь неправильное дерево?
Извиняется, если ответ обернется очевидным. Я несколько раз задумывался над этим. Спасибо!
Добавление: Также, если бы кто-нибудь мог объяснить разницу между fit(X) и fit_predict(X) более явным образом, я также был бы признателен за это - я боюсь, что я просто не совсем понял.
Добавление # 2: Конечно, я просто попробовал это на машине с ~ 550 ГБ ОЗУ и все еще взорвался, поэтому я чувствую, что DBSCAN, вероятно, пытается сделать парную матрицу расстояний или что-то, что я, я хочу это сделать. Думаю, теперь большой вопрос - как остановить это поведение или найти другие методы, которые могли бы удовлетворить мои потребности больше. Спасибо за то, что вы здесь.
Приложение № 3 (!): я забыл приложить трассировку, вот она,
Traceback (most recent call last):
File "tDBSCAN.py", line 34, in <module>
db = DBSCAN(eps=float(sys.argv[2]), min_samples=10, metric='cityblock').fit(mydata)
File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/base.py", line 329, in fit_predict
self.fit(X)
File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/cluster/dbscan_.py", line 186, in fit
**self.get_params())
File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/cluster/dbscan_.py", line 69, in dbscan
D = pairwise_distances(X, metric=metric)
File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/metrics/pairwise.py", line 651, in pairwise_distances
return func(X, Y, **kwds)
File "/home/jtownsend/.local/lib/python2.6/site-packages/sklearn/metrics/pairwise.py", line 237, in manhattan_distances
D = np.abs(X[:, np.newaxis, :] - Y[np.newaxis, :, :])
MemoryError
Ответы
Ответ 1
Проблема, очевидно, заключается в нестандартной реализации scikit-learn в scikit-learn.
DBSCAN не нуждается в матрице расстояний. Алгоритм был разработан с использованием базы данных, которая может ускорять функцию regionQuery и эффективно возвращать соседей в пределах радиуса запроса (пространственный индекс должен поддерживать такие запросы в O(log n)).
Однако реализация в scikit, по-видимому, вычисляет полную матрицу расстояний O(n^2), которая обходится как в память, так и во время выполнения.
Итак, я вижу два варианта:
-
Возможно, вы захотите попробовать реализацию DBSCAN в ELKI, которая при использовании с индексом R * -tree обычно значительно быстрее, чем наивная реализация.
-
В противном случае вы можете захотеть переопределить DBSCAN, поскольку реализация в scikit очевидно, не слишком хороша. Не бойтесь этого: DBSCAN действительно просто реализовать самостоятельно. Самая хитрая часть хорошей реализации DBSCAN - это функция regionQuery. Если вы можете получить этот запрос быстро, DBSCAN будет быстрым. И вы можете использовать эту функцию для других алгоритмов.
Обновление: теперь sklearn больше не вычисляет матрицу расстояний и может, например, использовать индекс kd -tree. Однако из-за "векторизации" он все равно будет предварительно вычислять соседей каждой точки, поэтому использование памяти sklearn для большого эпсилона равно O (n²), тогда как, насколько я понимаю, версия в ELKI будет использовать только O (n) память. Поэтому, если вам не хватает памяти, выберите меньший эпсилон и/или попробуйте ELKI.
Ответ 2
Вы можете сделать это, используя scikit-learn DBSCAN с метрикой haversine и шаровым алгоритмом. Вам не нужно предварительно компилировать матрицу расстояний.
В этом примере кластеры за миллион точек долготы широты GPS с DBSCAN/haversine и позволяет избежать проблем с использованием памяти:
df = pd.read_csv('gps.csv')
coords = df.as_matrix(columns=['lat', 'lon'])
db = DBSCAN(eps=eps, min_samples=ms, algorithm='ball_tree', metric='haversine').fit(np.radians(coords))
Обратите внимание, что это специально использует scikit-learn v0.15, так как некоторые ранние/более поздние версии, похоже, требуют вычисления полной матрицы расстояния, которая быстро взрывает оперативную память. Но если вы используете Anaconda, вы можете быстро установить это с помощью:
conda install scikit-learn=0.15
Или создайте чистую виртуальную среду для этой задачи кластеризации:
conda create -n clusterenv python=3.4 scikit-learn=0.15 matplotlib pandas jupyter
activate clusterenv
Ответ 3
Алгоритм DBSCAN фактически вычисляет матрицу расстояний, поэтому здесь нет никаких шансов.
Для этого большого количества данных я бы рекомендовал использовать MiniBatchKMeans.
Вы не можете использовать метку Манхэттена из коробки, но вы можете сделать свою собственную реализацию. Возможно, сначала попробуйте стандартную реализацию с евклидовой метрикой.
Я не знаю много алгоритмов кластеризации, которые не выполняют попарные расстояния.
Используя недавно внедренный чит-лист нижний центр: хотя удача.
Ответ 4
Я столкнулся с той же проблемой, когда использовал старую версию на sklearn 0.19.1, потому что сложность была O (N ^ 2).
Но теперь проблема была решена в новой версии 0.20.2 и больше нет ошибок памяти, и сложность становится O (nd), где d - это среднее число соседей. это не сложность кумира, но намного лучше чем старые версии.
Проверьте примечания в этом выпуске, чтобы избежать высокого использования памяти: https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html
Ответ 5
Эта проблема с sklearn обсуждается здесь:
https://github.com/scikit-learn/scikit-learn/issues/5275
Существует два варианта:
Один из них - использовать OPTICS (для которого требуется sklearn v21+), который является альтернативным, но тесно связанным алгоритмом с DBSCAN:
https://scikit-learn.org/dev/modules/generated/sklearn.cluster.OPTICS.html
Остальные должны прекомпретировать матрицу смежности или использовать вес образца. Более подробную информацию об этих параметрах можно найти в разделе Примечания здесь:
https://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html
