Вопрос или проблема
Я пытаюсь использовать minhash для генерации кластеров и определения сходств, и в основном полагаюсь на идеи из этих источников.
- http://www2007.org/papers/paper570.pdf
- https://chrisjmccormick.wordpress.com/2015/06/12/minhash-tutorial-with-python-code/
Данные, с которыми я работаю, состоят из взаимодействий между пользователями и предметами. Существует 2,2 миллиона уникальных пользователей и 440 миллионов уникальных предметов. В общей сложности в данных только 905 миллионов записей, поэтому они очень разреженные.
В моем подходе я вычисляю H минимальных хэш-значений для каждого пользователя, перераспределяя предметы (которых 440 миллионов). У пользователей широкий диапазон взаимодействий с предметами. У пользователя с наибольшим количеством взаимодействий 2,5 миллиона взаимодействий, наименьшее количество взаимодействий – 1, среднее – 403, а медианное значение составляет всего 26.
В документе Google о Google News они рекомендуют конкатенировать 2-4 ключа (LSH) и делать это 10-20 раз. Я предполагаю, что это хорошо работает, когда пользователь взаимодействует с меньшим количеством предметов, таких как новостные статьи, но это слишком мало для того, что я делаю. Когда я тестирую это количество ключей для пользователей с более чем 1000 взаимодействиями, многие из них не имеют ни одного совпадения с другими пользователями по конкатенированным minhash-значениям. Это проблема, потому что я могу вручную вычислить косинусное или жесткое сходство для некоторых из этих пользователей и увидеть приемлемое количество сходства для моих нужд. Я нашел лучшие результаты, не конкатенируя хэш-ключи и используя до 200.
Для большей части моих групп хэш-ключей существует около 2 миллионов уникальных хэш-ключей для 2,24 миллиона пользователей. Таким образом, количество коллизий довольно низкое.
Есть ли у вас советы по увеличению количества кластеризации? Я думаю о том, чтобы использовать 1000 хэш-ключей и объединять пользователей, если они совпадают по больше чем одному. Спасибо заранее.
Один из вариантов – изменить хэш-функции на функцию, которая с большей вероятностью будет иметь коллизии. Например, хэширование Пирсона является 8-битным хэшем, который будет иметь гораздо больше коллизий, чем более распространенные хэш-функции.
Ответ или решение
При выборе числа хешей для мин-хеширования в условиях работы с крайне разреженными данными важно учитывать несколько факторов, которые по своей сути влияют на количество коллизий и качество кластеризации. В данной ситуации вы стремитесь повысить количество совпадений (коллизий) между пользователями, что, в свою очередь, улучшит результирующие кластеры.
Основа мин-хеширования
Мин-хеширование используется дляApproximate Membership Query (AMQ) и анализа схожести. Главной его цель является определение вероятности наличия схожести между двумя наборами, где каждый набор представлен с помощью минимальных хешей. Это позволяет эффективно приблизительно оценить степени схожести (например, через коэффициенты Жаккара или косинусной схожести) между пользователями.
Число хешей: Оптимизация
-
Размер выборки хешей: В процессе работы с пользователями, которые имеют различные объемы взаимодействий с элементами, рекомендуется использовать более высокий объем хешей. Вы упомянули использование 200 хешей, что является хорошим началом, особенно учитывая вашу разреженность. Если вы стремитесь к увеличению коллизий, рассмотрите вариант увеличения числа хешей до 500-1000. Это обеспечит более высокую вероятность совпадений при условии, что хеши будут правильно выбраны.
-
Хеш-функции: Как упомянуто, изменение используемых хеш-функций может значительно повлиять на результат. Например, использование хеш-функций, которые имеют более высокую вероятность коллизий, таких как Pearson хеширование, может повысить уровень совпадений. Это может быть особенно полезно в условиях разреженных данных, когда традиционные хеши дают низкую вероятность коллизий.
-
Конкатенация хешей: Ваша идея о параллельном использовании одновременно 1000 хешей может быть применена более эффективно. Попробуйте реализовать несколько конкурирующих наборов хешей и использовать метрики, чтобы отслеживать и анализировать, как много кластеров формируется из них. Использование алгоритмов, подобных Locality Sensitive Hashing (LSH), как вы упомянули, может быть успешно адаптировано для вашей ситуации, при этом комбинирование 2-4 ключей может быть правильно откалибровано на основании ваших конкретных данных.
-
Статистика взаимодействий: Учитывая, что пользователей с минимальным взаимодействием крайне мало, фокус на тех, у кого количество взаимодействий высоко, может помочь. Ваша методология, которая пытается приравнять пользователей с 1000+ взаимодействиями, является обоснованной. Используйте это для ваши порога совпадений.
Кластеризация: Дополнительные рекомендации
-
Анализ данных: Используйте результаты вычислений схожести, чтобы определить наиболее похожие группы пользователей. Идентификация паттернов в потреблении контента может предоставить полезную информацию для дальнейшего улучшения кластеризации.
-
Гибридные подходы: Рассмотрите возможность интеграции других методов кластеризации, таких как алгоритмы K-средних или иерархическая кластеризация, используя мин-хеш как один из факторов при определении схожести.
Наши исследования показывают, что переборы различных комбинаций подходов приведут к получению более точных и практичных результатов для ваших специфических требований. Главное — это исследовать, тестировать и адаптироваться на основе полученных данных.