Длительное время ковыряю задачку, перепробовал различные алгоритмы кластеризации, но результат не устраивает. Наткнулся на гибридный алгоритм DeLiClu, который сочетает иерархическую кластеризацию и по плотности. Реализация от авторов алгоритма написана на Java и входит в библиотеку ELKI. Все бы хорошо, можно было бы дернуть из питона через какую-нить обертку, но под мои нужды надо кое-что допилить, а с Java я не сталкивался.

Всей работы минут 10. От меня благодарности и, при физической возможности, пиво или прочие плюшки.