Comments 8
Спасибо за статью, очень интересно!
Вопрос: а зачем обязательно искать на каждом шаге пару кластеров, объединение которых дает самый лучший прирост метрики качества? Например, в известном алгоритме кластеризации графов Louvain community detection, суть примерно такая же (лишь другая метрика и пара деталей), но не ищется глобальный максимум прироста метрики, а просто для каждого кластера жадно выбирается лучший кластер, с которым его можно объединить и все. Насколько оправдано нахождение именно самого лучшего объединения? Ведь если просто жадно объединять по очереди, то сложность будет порядка O(M), где M — число связей в графе, а, как показывает Louvain, итоговый результат очень мало зависит от порядка обхода кластеров, то есть он почти детерменирован.
Вопрос: а зачем обязательно искать на каждом шаге пару кластеров, объединение которых дает самый лучший прирост метрики качества? Например, в известном алгоритме кластеризации графов Louvain community detection, суть примерно такая же (лишь другая метрика и пара деталей), но не ищется глобальный максимум прироста метрики, а просто для каждого кластера жадно выбирается лучший кластер, с которым его можно объединить и все. Насколько оправдано нахождение именно самого лучшего объединения? Ведь если просто жадно объединять по очереди, то сложность будет порядка O(M), где M — число связей в графе, а, как показывает Louvain, итоговый результат очень мало зависит от порядка обхода кластеров, то есть он почти детерменирован.
а просто для каждого кластера жадно выбирается лучший кластер, с которым его можно объединить и все
А «лоскутные» кластеры в таком подходе не появляются ли? И как определяется возможность объединения и, что не менее важно, невозможность объединения?
Ну возможность/невозможность определить несложно же. По аналогии с тем, что у Вас: находим такой кластер-кандидат для данного (из всех связанных кластеров-кандидатов), что дельта метрики при их объединении максимальна. Если дельта положительная, то объединяем, если отрицательная или нулевая, то нет. С лоскутными кластерами сложнее, но тут главный вопрос — насколько это серьезная проблема, стоит ли она столь существенного роста сложности алгоритма?
В приложениях, где кластера являются неотъемлемой частью продукта, лоскутные кластера очень вредны =)
Модифицировать описанный алгоритм так, чтобы он за один шаг делал сразу несколько склеек, довольно просто. Меня в моих приложениях качество такого варианта не устраивало, но вполне могут быть приложения, где это хороший вариант. Заодно и параллелизм улучшится.
А на сколько оно быстрее fastcluster?
Спасибо за статью. Думаю, многим читателям, как и мне, было бы очень интересно посмотреть на пару «академических примеров» из жизни, где возникает задача кластеризации именно с такими качеством и полнотой и как полученные кластеры затем в этих примерах используются.
Еще один вопрос, мне будет трудно его формализовать, поэтому я прибегну к аналогии. Вот смотрите: в нашей галактике звезды расположены не совсем исходя из равномерного по объему распределения — вообще говоря наблюдаются звездные скопления. Если Вы посмотрите на звездную карту, то сможете легко их выделить глазом. Однако есть обстоятельство, почему большинство известных мне алгоритмов кластеризации будут работать совсем не так, как работает наш «глаз». Это обстоятельство — сильный разброс масштаба: иногда десять хорошо различимых компактных скоплений, находящиеся рядом с центром галактики или в ее рукаве, занимают такой же объем как одно скопление где-нибудь на периферии.
Алгоритмы кластеризации, наподобие описанного вами, почти не учитывают локальный контекст понятия «много» или «мало» — их метрики опираются на средние величины расстояния (или близости) во всем множестве объектов. Как следствие, если они не разобьют жиденькое звездное скопление на отдельные звезды, то скорее всего «склеят» все находящиеся рядом компактные скопления.
Известны ли Вам алгоритмы, которые могут выделить звездные кластеры с ожидаемым для нас результатом?
Еще один вопрос, мне будет трудно его формализовать, поэтому я прибегну к аналогии. Вот смотрите: в нашей галактике звезды расположены не совсем исходя из равномерного по объему распределения — вообще говоря наблюдаются звездные скопления. Если Вы посмотрите на звездную карту, то сможете легко их выделить глазом. Однако есть обстоятельство, почему большинство известных мне алгоритмов кластеризации будут работать совсем не так, как работает наш «глаз». Это обстоятельство — сильный разброс масштаба: иногда десять хорошо различимых компактных скоплений, находящиеся рядом с центром галактики или в ее рукаве, занимают такой же объем как одно скопление где-нибудь на периферии.
Алгоритмы кластеризации, наподобие описанного вами, почти не учитывают локальный контекст понятия «много» или «мало» — их метрики опираются на средние величины расстояния (или близости) во всем множестве объектов. Как следствие, если они не разобьют жиденькое звездное скопление на отдельные звезды, то скорее всего «склеят» все находящиеся рядом компактные скопления.
Известны ли Вам алгоритмы, которые могут выделить звездные кластеры с ожидаемым для нас результатом?
Sign up to leave a comment.
Агломеративная кластеризация: алгоритм, быстродействие, код на GitHub