Алгоритмы кластеризации Python

Я просматривал scipy и sklearn для алгоритмов кластеризации для конкретной проблемы, которую я имею. Мне нужно каким-то образом характеризовать популяцию N частиц в k группах, где k не обязательно известно, и в дополнение к этому не известны априорные длины связывания (аналогично этому question).

Я пробовал kmeans, который хорошо работает, если вы знаете, сколько кластеров вы хотите. Я пробовал dbscan, который плохо работает, если вы не сообщите характерную шкалу длины, на которой перестать искать (или начинать искать) кластеры. Проблема в том, что у меня есть потенциально тысячи этих кластеров частиц, и я не могу тратить время на то, чтобы рассказать алгоритмы kmeans/dbscan, из чего они должны уйти.

Вот пример того, что dbscan find:

Вы можете видеть, что здесь действительно существуют две отдельные популяции, хотя корректировка эпсилонного фактора (максимальное расстояние между соседними параметрами кластеров), я просто не могу заставить его видеть эти две популяции частиц.

Есть ли какие-нибудь другие алгоритмы, которые будут работать здесь? Я ищу минимальную информацию заранее - другими словами, я бы хотел, чтобы алгоритм мог принимать "умные" решения о том, что может представлять собой отдельный кластер.

Ответ 1

Я нашел тот, который не требует априорной информации/догадок и очень хорошо подходит к тому, что я прошу сделать. Он называется Mean Shift и находится в SciKit-Learn. Это также относительно быстро (по сравнению с другими алгоритмами, такими как распространение аффинности).

Вот пример того, что он дает:

Я также хочу отметить, что в документации указано, что он может плохо масштабироваться.

Ответ 2

При использовании DBSCAN может быть полезно масштабировать/нормализовать данные или заранее, так что оценка эпсилона будет относительной.
Существует реализация DBSCAN - я думаю, что она одна Анони-Мусс где-то обозначается как "плавающий", который приходит с функцией эпсилон-оценки. Он работает, пока его не кормят с большими наборами данных.
Существует несколько неполных версий ОПТИКИ в github. Может быть вы можете найти его, чтобы адаптировать его для своей цели. Все еще пытаясь разобраться в себе, какой эффект имеет minPts, используя один и тот же метод извлечения.

Ответ 3

Вы можете попробовать минимальное остовное дерево (алгоритм zahn), а затем удалить самый длинный край, похожий на альфа-формы. Я использовал его с триангуляцией delaunay и вогнутым корпусом: http://www.phpdevpad.de/geofence. Вы также можете попробовать иерархический кластер, например, clusterfck.

Ответ 4

Ваш график указывает, что вы выбрали параметр minPts слишком мал.

Посмотрите OPTICS, которая больше не нуждается в параметре epsilon для DBSCAN.