Алгоритм, используемый для генерации рекомендаций в Новостях Google?

Question

Я изучаю механизмы рекомендаций, и я просмотрел статью , которая определяет, как Новости Google генерируют рекомендации для пользователей по новостям, которые могут представлять их интерес, на основе совместной фильтрации.

Одна интересная техника, которую они упоминают, это Minhashing. Я прошел через то, что он делает, но я уверен, что то, что у меня есть, является нечеткой идеей, и есть большая вероятность, что я ошибаюсь. Вот что я могу из этого сделать: -

1. Соберите набор всех новостей.
2. Определить хеш-функцию для пользователя. Эта хеш-функция возвращает индекс первого элемента из новостей, которые просматривал этот пользователь, в списке всех новостей.
3. Соберите, скажите «n» количество таких значений и представьте пользователя с этим списком значений.
4. На основе количества сходств между этими списками мы можем рассчитать сходство между пользователями как количество общих элементов. Это значительно уменьшает количество сравнений.
5. На основе этих мер сходства группируйте пользователей в разные кластеры.

Это как раз то, что я думаю. На шаге 2 вместо определения постоянной хеш-функции может оказаться возможным изменить хеш-функцию таким образом, чтобы она возвращала индекс другого элемента. Таким образом, одна хеш-функция может возвращать индекс первого элемента из списка пользователя, другая хеш-функция может возвращать индекс второго элемента из списка пользователя и так далее. Таким образом, природа хеш-функции, удовлетворяющей условию минус-независимых перестановок , звучит как возможный подход.

Может ли кто-нибудь подтвердить, что я считаю правильным? Или часть рекомендаций Новостей Google, функционирующая как-то иначе? Я новичок во внутренних реализациях рекомендаций. Любая помощь очень ценится.

Спасибо!

Answer 1

Я думаю, что вы близко.

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

Затем, чтобы получить новую хэш-функцию, а не выбирать второй элемент (который будет иметь некоторые запутанные зависимости от первого элемента), они выбирают совершенно новую перестановку и снова берут первый элемент.

Люди, которые имеют одинаковое хеш-значение 2-4 раза (то есть один и тот же первый элемент в 2-4 перестановках), собираются в кластер. Этот алгоритм повторяется 10-20 раз, так что каждый человек попадает в 10-20 кластеров. Наконец, даются рекомендации, основанные (небольшое количество) других людей в 10-20 кластерах. Поскольку вся эта работа выполняется с помощью хэширования, люди помещаются непосредственно в группы для их кластеров, и большое количество сравнений не требуется.