DBSCAN: Как кластеризовать большой набор данных с одним огромным кластером - PullRequest
Новая
       36

DBSCAN: Как кластеризовать большой набор данных с одним огромным кластером

1 голос
/ 16 марта 2020

Я пытаюсь выполнить DBSCAN на 18 миллионах точек данных, пока только 2D, но надеюсь на go до 6D. Я не смог найти способ запустить DBSCAN на этом количестве пунктов. Самый близкий, который я получил, был 1 миллион с ELKI, и это заняло час. Я использовал Spark и раньше, но, к сожалению, в нем нет DBSCAN.

Поэтому мой первый вопрос: может ли кто-нибудь порекомендовать способ запуска DBSCAN для такого большого количества данных, вероятно, распределенным способом?

Далее, мои данные таковы, что ~ 85% находятся в одном огромном кластере (обнаружение аномалий). Единственная техника, которую я смог придумать, чтобы позволить мне обрабатывать больше данных, - это заменить большой кусок этого огромного кластера одной точкой данных таким образом, чтобы он мог по-прежнему достигать всех своих соседей (удаленный кусок меньше, чем epsilon).

Может ли кто-нибудь дать какие-либо советы, правильно ли я это делаю или есть ли лучший способ уменьшить сложность DBSCAN, когда вы знаете, что большая часть данных находится в одном кластере, сосредоточенном вокруг (0.0,0.0 )

1 Ответ

2 голосов
/ 17 марта 2020

  1. Вы добавили index в ELKI и попробовали версию parallel ? За исключением версии git, ELKI не будет автоматически добавлять индекс; и даже в этом случае может помочь точное уточнение индекса проблемы.

  2. DBSCAN - это , а не - хороший подход для обнаружения аномалий - шум не такой, как аномалии. Я бы предпочел использовать обнаружение аномалий на основе плотности. Существуют варианты, которые пытаются более эффективно пропустить «прозрачные метрики», если вы знаете, что интересуетесь только верхними 10%.

  3. Если вы уже знаете, что большая часть ваших данных находится в один огромный кластер, почему бы вам не напрямую смоделировать этот большой кластер и удалить его / заменить его на меньшее приближение.

  4. Подвыборка . Как правило, не дает никаких преимуществ при использовании полных данных *1026*. Даже (или, в частности), если вас интересуют «шумовые» объекты, существует тривиальная стратегия случайного разделения ваших данных, например, на 32 подмножества, затем кластеризацию каждого из этих подмножеств и объединение результатов обратно. Эти 32 части могут тривиально обрабатываться параллельно на отдельных ядрах или компьютерах; но поскольку основная проблема имеет квадратичный c характер, ускорение будет где-то между 32 и 32 * 32 = 1024. Это особенно относится к DBSCAN: большие данные обычно означают, что вы также хотите использовать намного большие minPts. Но тогда результаты не будут сильно отличаться от подвыборки с меньшими minPts.

Но любым способом: перед масштабированием на более крупные данные убедитесь, что ваш подход решает вашу проблему, и самый умный способ решения этой проблемы . Кластеризация для обнаружения аномалий - это все равно, что пытаться с помощью молотка врезать в стену sh винт. Это работает, но, возможно, лучше использовать гвоздь вместо винта.

Даже если у вас есть «большие» данные и вы гордитесь «большими данными», всегда начинайте с подвыборки. Если вы не можете показать, что качество результата увеличивается с размером набора данных, не беспокойтесь о масштабировании больших данных, накладные расходы слишком велики, если вы не можете доказать значение .

...