Как кластеризовать наборы (пользователи / документы) с распределенным MinHash, используя технику объединения?

Question

У меня есть большие сомнения в том, как я должен кластеризовать наборы, используя MinHash вместе с техникой объединения.

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

Моя цель - использовать MinHash для кластеризации пользователей в соответствии со сходством их подписей. В локальных настройках без полос это было бы тривиально: если их хэш подписи одинаков, они попадают в один кластер.

Если мы разделим подписи по группам и обработаем их независимо, я могу обработать группу, как я говорил ранее, и сгенерировать группу кластеров для каждой группы. Мой вопрос: как я должен объединить эти кластеры? Просто объединить их, если у них есть хотя бы элемент общего? Или я должен сделать что-то другое?

Спасибо

Answer 1

MinHash не является автономным алгоритмом кластеризации. Он предназначен в качестве фильтра-кандидата для обнаружения почти дубликатов.

При поиске похожих документов вы вычисляете минусы для поиска кандидатов. Тогда вам еще нужно проверить этих кандидатов - они могут быть ложными срабатываниями! Чем больше подписей согласны, тем больше вероятность, что они действительно совпадают.

Поэтому, если вы снова рассмотрите сценарий с почти дубликатом: если a является почти дубликатом b, а b является почти дубликатом c, то a также должен быть почти дубликатом c. Если это так, вы можете выбросить все эти совпадения (после проверки) вместе. Если он не рассматривает иерархическую кластеризацию как стратегию слияния (или не слияния) кандидатов.