![](http://webcf.waybackmachine.org/web/20200612110325im_/https://habrastorage.org/getpro/habr/avatars/165/9cc/56a/1659cc56a36e1eea615f2ac283955bba.jpg)
Агломеративная кластеризация: алгоритм, быстродействие, код на GitHub
Несколько лет назад мне потребовалось очень качественно кластеризовать относительно неплотные графы среднего размера (сотни тысяч объектов, сотни миллионов связей). Тогда оказалось, что алгоритма с подходящим набором свойств просто не существует, несмотря на всё разнообразие методов, придуманных человечеством за многие десятилетия. Имеющиеся решения работали либо просто очень плохо, либо очень плохо и к тому же медленно.
К счастью, оказалось, что идеи, заложенные в метрики качества кластеризации, о которых я рассказывал в прошлой статье, можно адаптировать и создать на их основе алгоритм кластеризации. Он достигает очень высоких показателей качества и к тому же работает очень быстро благодаря некоторым удачным аналитическим свойствам оптимизируемых величин. Алгоритм относится к классу агломеративных: основной операцией является слияние нескольких уже имеющихся кластеров в один более крупный кластер.
Об этом алгоритме и пойдёт речь в статье. Под катом читателей ждут математическое описание алгоритма, техники уменьшения его временной сложности, код на GitHub и модельные наборы данных.