С Новым годом! Форум программистов, компьютерный форум, киберфорум
Python
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.64/11: Рейтинг темы: голосов - 11, средняя оценка - 4.64
 Аватар для Vorobushek
0 / 0 / 0
Регистрация: 24.02.2013
Сообщений: 73

DBSCAN MemoryError

15.04.2018, 20:06. Показов 2406. Ответов 13
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Задача пропарсить лог запросов поисковика объемом в 500 метров и выделить запросы, связанные с просмотром телевидения.
Решать решил в Jupyter с помощью лемматизации -> tfifd критерия -> DBSCAN кластеризации. На моменте использования DBSCAN от матрицы векторов все время появляется ошибка в разных ее вариациях MemoryError. Посерфил по инету и нашел решения, в частности ипользовать алгоритм 'Ball Tree', использовать меньше зону эпсилон, использовать другие метрики, но ничего из этого не дало результата. Причем матрицу беру даже очень маленькую, всего в 3000 строк, и уже ошибка, при матрице в 1000 строк - нет ошибки. Кто-нибудь сталкивался?

код под спойлером. Лог по ссылке,

Код Python
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
from sklearn.feature_extraction.text import TfidfVectorizer
 
import numpy as np
import pandas as pd
 
from sklearn.feature_extraction.text import TfidfVectorizer
 
df = pd.read_csv('C:\\Users\\name\\Desktop\\Log', delimiter = '\t', encoding = 'utf-8')
 
df_sample = df.sample(10000) #ограничиваем скок брать, если >1000 то MemoryError
 
df_sample.head()
 
from urllib.parse import urlparse,parse_qs
url = 'http://foo.appspot.com/abc?def=ghi'
parsed = urlparse(url)
print(parse_qs(parsed.query)['def'][0])
 
def get_request_text(url):
    parsed = urlparse(url)
    result = parse_qs(parsed.query)
    if 'text' in result:
        return result['text'][0]
    else:
        return None
 
 
df_sample['text'] = df_sample.request.apply(get_request_text)
 
df_sample.head()
 
df_sample = df_sample[~df_sample.text.isnull()]
 
df_sample.shape
 
import pymorphy2
morph = pymorphy2.MorphAnalyzer()
 
def to_normal_form(word):    
    return morph.parse(word)[0].normal_form
 
 
df_sample['text_normal'] = df_sample.text.apply(to_normal_form)
 
df_sample.head()
 
 
tfidf_v = TfidfVectorizer(min_df=10,max_features=10)
some_tf_matrix = tfidf_v.fit_transform(df_sample.text_normal)
 
from sklearn.cluster import DBSCAN
 
model = DBSCAN(n_jobs=-1, algorithm='ball tree')
 
print(some_tf_matrix)
 
print(model.fit(some_tf_matrix))

0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
15.04.2018, 20:06
Ответы с готовыми решениями:

MemoryError
здравствуйте, получаю ошибку MemoryError=Ошибка памяти на строке strings1 = strings1.replace(val.replace('~', ''), '<SPAN...

memoryerror python
здравствуйте, получаю ошибку memoryerror, что это такое, читал - где-то напряг машину, возникает ошибка на строке s1 =...

MemoryError при заполнении list
Задание Over The Road, в нем нужно вернуть адрес дома на противоположной улице, адреса вот так располагаются: 1| |6 3| |4 5| |2...

13
1741 / 913 / 480
Регистрация: 05.12.2013
Сообщений: 3,074
15.04.2018, 21:47
Цитата Сообщение от Vorobushek Посмотреть сообщение
ипользовать алгоритм 'Ball Tree'
Выложенный скрипт не может запуститься из-за этой строки
Python
1
model = DBSCAN(n_jobs=-1, algorithm='ball tree')
правильно
Python
1
model = DBSCAN(n_jobs=-1, algorithm='ball_tree')
После исправления запустилось, вывод ниже, но ждать окончания работы скрипта надоело, MemoryError не было, попробуйте обновить все модули

ghi
(4, 3) 1.0
(6, 3) 1.0
(8, 3) 1.0
(13, 8) 0.7094890582973894
(13, 4) 0.7047164508909123
(16, 3) 1.0
(17, 4) 1.0
(21, 0) 1.0
(25, 3) 1.0
(29, 4) 1.0
(34, 5) 1.0
(43, 9) 1.0
(49, 3) 0.6005465157785039
(49, 0) 0.7995898213373525
(50, 3) 1.0
(52, 8) 1.0
(54, 1) 1.0
(55, 5) 1.0
(60, 4) 1.0
(61, 3) 0.6038651169256176
(61, 7) 0.7970865201221321
(67, 3) 1.0
(82, 2) 1.0
(83, 1) 1.0
(86, 3) 1.0
: :
(9809, 3) 1.0
(9814, 5) 1.0
(9817, 2) 1.0
(9818, 3) 1.0
(9831, 1) 1.0
(9834, 3) 1.0
(9840, 1) 1.0
(9852, 3) 1.0
(9854, 1) 1.0
(9859, 0) 1.0
(9861, 4) 1.0
(9871, 7) 1.0
(9872, 3) 1.0
(9874, 1) 1.0
(9876, 3) 1.0
(9882, 6) 1.0
(9883, 0) 1.0
(9884, 5) 1.0
(9892, 5) 1.0
(9898, 7) 1.0
(9901, 8) 1.0
(9903, 7) 1.0
(9904, 3) 1.0
(9906, 1) 1.0
(9915, 4) 1.0
D:\Books\Test\Python\tensorflow\venv\lib \site-packages\sklearn\neighbors\base.py:212: UserWarning: cannot use tree with sparse input: using brute force
warnings.warn("cannot use tree with sparse input: "
#Тут все начало тормозить, но не вылетало
ghi
ghi
0
 Аватар для Vorobushek
0 / 0 / 0
Регистрация: 24.02.2013
Сообщений: 73
15.04.2018, 22:22  [ТС]
Забавно, но на MacOS запускается без проблем, а вот на винде не работает.
Я так и писал через нижнее подчеркивание, на форуме просто в ручную исправлял, опечатался.

У вас мак или винда? и какая версия?

я даже попробовал на компе и на ноуте. на обоих вин 10.1, и не работает этот скрипт
0
1741 / 913 / 480
Регистрация: 05.12.2013
Сообщений: 3,074
15.04.2018, 22:28
win10 x64
0
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
15.04.2018, 22:56
Цитата Сообщение от Vorobushek Посмотреть сообщение
и не работает этот скрипт
Если налить в стакан объемом в 200 мл воды на 300 мл - будет StakanOwerflow :-)

У вас какой объем памяти на компе? И сколько ядер? Скрипт запускает обработку модели в multiprocessing - 1 процесс на одно ядро.
Данные, загруженные в память занимают ~600 mb (на x64 больше) + каждый процесс жрет по 400-600 mb (на x64 больше).
Итог: eсли у вас мало памяти и много ядер - MemoryError.
На windows запуск нового процесса достаточно ресурсоемкая операция. Попробуйте уменьшить n_jobs до 1. Будет работать медленее, но, зато, возможно, хватит памяти.

P.S. C n_jobs=1 у меня вполне быстро отработалось с 5000 сэмплов. И памяти чуть меньше гига ушло.
А вот с 10 тыс. тоже не получается - мало ОЗУшки, да и на 32-битной винде один процесс может использовать только 2 гига памяти и все. :-)

Добавлено через 1 минуту
P.P.S. Алгоритм я выставил "auto".
2
 Аватар для Vorobushek
0 / 0 / 0
Регистрация: 24.02.2013
Сообщений: 73
15.04.2018, 23:42  [ТС]
Это я понял. у меня i7, 8gb ram. Но на обычном макбуке запускается на 100000 строку без проблем!
0
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
15.04.2018, 23:52
Цитата Сообщение от Vorobushek Посмотреть сообщение
Но на обычном макбуке
Сколько памяти на обычном макбуке и сколько ядер?
Если ядро только одно, то я уже сказал - памяти для одного процесса хватает.

Добавлено через 3 минуты
P.S. Вы попробуйте на гаданием заняться, а профилированием кода по памяти. Многие вопросы сразу отпадут.
0
16.04.2018, 00:00

Не по теме:

а что значит на обычном макбуке?) и бывают ли необычные?)

0
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
16.04.2018, 00:24
Цитата Сообщение от Vorobushek Посмотреть сообщение
8gb ram.
Вы не поверите, но если погуглить, то окажется что у людей даже с 64 гигами MemoryError.
Суть в реализации алгоритма в sklearn: DBSCAN needs O(n*k) memory, where k is the number of neighbors within epsilon. Поэтому при некоторых критических размерностях имеющихся данных вы с ним вообще не сможете работать даже на суперобычном макбуке.
1
 Аватар для Vorobushek
0 / 0 / 0
Регистрация: 24.02.2013
Сообщений: 73
16.04.2018, 03:03  [ТС]
Про макбук узнаю.
Т.е. надо просто поиграться с параметрами дбскан и подобрать рабочие? меньше потоков взять? Я отпишусь как попробую! спасибо!

Добавлено через 28 минут
Поставил 1 поток, - заработало для 10000 строк. Однако для 50000 уже не работает, а нужно обработать более 1млн. строк... Попробовал с Ball_tree, вы ошибке посоветовал мне юпитер использовать Brute. Ошибки у них одинаковые:

Код+ошибка
Python
1
2
3
model = DBSCAN(n_jobs=1, algorithm='brute')
%%time
model.fit(some_tf_matrix)
Ошибка
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<timed eval> in <module>()
 
z:\pyidle\lib\site-packages\sklearn\cluster\dbscan_.py in fit(self, X, y, sample_weight)
    282         X = check_array(X, accept_sparse='csr')
    283         clust = dbscan(X, sample_weight=sample_weight,
--> 284                        **self.get_params())
    285         self.core_sample_indices_, self.labels_ = clust
    286         if len(self.core_sample_indices_):
 
z:\pyidle\lib\site-packages\sklearn\cluster\dbscan_.py in dbscan(X, eps, min_samples, metric, metric_params, algorithm, leaf_size, p, sample_weight, n_jobs)
    143         # This has worst case O(n^2) memory complexity
    144         neighborhoods = neighbors_model.radius_neighbors(X, eps,
--> 145                                                          return_distance=False)
    146 
    147     if sample_weight is None:
 
z:\pyidle\lib\site-packages\sklearn\neighbors\base.py in radius_neighbors(self, X, radius, return_distance)
    588             if self.effective_metric_ == 'euclidean':
    589                 dist = pairwise_distances(X, self._fit_X, 'euclidean',
--> 590                                           n_jobs=self.n_jobs, squared=True)
    591                 radius *= radius
    592             else:
 
z:\pyidle\lib\site-packages\sklearn\metrics\pairwise.py in pairwise_distances(X, Y, metric, n_jobs, **kwds)
   1245         func = partial(distance.cdist, metric=metric, **kwds)
   1246 
-> 1247     return _parallel_pairwise(X, Y, func, n_jobs, **kwds)
   1248 
   1249 
 
z:\pyidle\lib\site-packages\sklearn\metrics\pairwise.py in _parallel_pairwise(X, Y, func, n_jobs, **kwds)
   1088     if n_jobs == 1:
   1089         # Special case to avoid picklability checks in delayed
-> 1090         return func(X, Y, **kwds)
   1091 
   1092     # TODO: in some cases, backend='threading' may be appropriate
 
z:\pyidle\lib\site-packages\sklearn\metrics\pairwise.py in euclidean_distances(X, Y, Y_norm_squared, squared, X_norm_squared)
    244         YY = row_norms(Y, squared=True)[np.newaxis, :]
    245 
--> 246     distances = safe_sparse_dot(X, Y.T, dense_output=True)
    247     distances *= -2
    248     distances += XX
 
z:\pyidle\lib\site-packages\sklearn\utils\extmath.py in safe_sparse_dot(a, b, dense_output)
    135         ret = a * b
    136         if dense_output and hasattr(ret, "toarray"):
--> 137             ret = ret.toarray()
    138         return ret
    139     else:
 
z:\pyidle\lib\site-packages\scipy\sparse\compressed.py in toarray(self, order, out)
    941         if out is None and order is None:
    942             order = self._swap('cf')[0]
--> 943         out = self._process_toarray_args(order, out)
    944         if not (out.flags.c_contiguous or out.flags.f_contiguous):
    945             raise ValueError('Output array must be C or F contiguous')
 
z:\pyidle\lib\site-packages\scipy\sparse\base.py in _process_toarray_args(self, order, out)
   1128             return out
   1129         else:
-> 1130             return np.zeros(self.shape, dtype=self.dtype, order=order)
   1131 
   1132     def __numpy_ufunc__(self, func, method, pos, inputs, **kwargs):
 
ValueError: array is too big; `arr.size * arr.dtype.itemsize` is larger than the maximum possible size.



Я пытался уменьшить eps = 0.0001 , но это не помогло((

Добавлено через 1 час 37 минут
Я понял. У меня был установлен Python 32 bit... Сейчас переустановил и все равно не смог взять 50000 строк. Но думал компьютер уже гораздо дольше.
0
Эксперт Python
5438 / 3859 / 1215
Регистрация: 28.10.2013
Сообщений: 9,552
Записей в блоге: 1
16.04.2018, 14:03
Цитата Сообщение от Vorobushek Посмотреть сообщение
Поставил 1 поток
n_jobs это не потоки, а процессы. Были бы потоки - памяти использовалось бы меньше. Но в python потоки не подходят для распараллеливания CPU-bound задач, поэтому используются процессы.
По поводу данных больших размерностей я уже сказал вам (и это легко подвердит гугл), что реализация этого алгоритма в sklearn неоптимальна и стоит поискать его имплементацию в другой библиотеке.
1
 Аватар для Vorobushek
0 / 0 / 0
Регистрация: 24.02.2013
Сообщений: 73
16.04.2018, 18:30  [ТС]
Garry Galler, ты же понимаешь заказы? может договоримся о помощи с решением этой задачи?
0
 Аватар для Vorobushek
0 / 0 / 0
Регистрация: 24.02.2013
Сообщений: 73
17.04.2018, 17:49  [ТС]
Если кому интересно, то решением данной проблемы я нашел следующие действия:

Визуализировав массив данных через TSNE, я выбрал другой алгоритм, который бы подходил для данной задачи.

Видно, что для данные разрознены по Гауссовым скоплениям, и для данной картинки подойдёт идеально метод кластеризации sklearn.mixture.GaussianMixture

Буду пробовать дальше.
Миниатюры
DBSCAN MemoryError  
0
 Аватар для Vorobushek
0 / 0 / 0
Регистрация: 24.02.2013
Сообщений: 73
17.04.2018, 21:09  [ТС]
Заработало с Гауссовой смесью!
Миниатюры
DBSCAN MemoryError   DBSCAN MemoryError  
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
17.04.2018, 21:09
Помогаю со студенческими работами здесь

Рекурсия: MemoryError: Stack overflow
Добрый день! from memory_profiler import profile import timeit import math import sys print(sys.getrecursionlimit()) ...

MemoryError при заполнении массива
Добрый день, столкнулся с MemoryError при заполнении массива данными. Действительно, получается очень большое количество, однако это...

Реализация алгоритма DBSCAN
Всем добрый день/ночь! Есть такой алгоритм кластеризации DBSCAN Я его реализовал на c++/qt Хотелось бы узнать у...

Ширина поиска в алгоритме dbscan
Добрый вечер/день! В алгоритме кластеризации dbscan (описание), после того, как мы отнесли точку (объект) к ядровому, производится ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Новые блоги и статьи
Новый CodeBlocs. Версия 25.03
palva 04.01.2026
Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru