Особенности системы рекомендаций для интернет ресурса с социальными функциями.

Оригинальное название: An Online Social Network-based Recommendation System

Авторы: Jorge Aranda, Inmar Givoni, Jeremy Handcock, Danny Tarlow

Адрес публикации оргинальной статьи: Department of Computer Science University of Toronto, 10 King’s College Road, Toronto, Ontario, Canada, M5S 3G4

Перевод: Заплетин Е.А.

Источник: http://www.cs.toronto.edu/syslab/courses/csc2231/07au/projects/2/aranda.pdf

Реферат

Мы представляем рекоммендательную систему для интернет сервиса, которая использует данные из анкет и связи между пользователями. Мы адаптировал реализацию алгоритма для использования на сайте BoardGameGeek(BGG). Конечный результат будет использован пользователями BGG, чтобы получить рекомендацию на основе их предыдущих оценок и данных о действиях их друзей одновременно.

В данное время мы собарали все необходимые данные от сайта BGG и начали использовать алгоритм для рекомендаций. В данный момент мы тестируем алгоритм, чтобы подобрать оптимальные настройки для него и создать web-приложение для рекомендаций.

1. Введение

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

Рекомендательные системы в интеренете были впервые популизированы благодаря Amazon.com, который хотел показывать пользователям персонализированный список товаров, которые по мнению системы будут интересны пользователю основываясь на его прошлых покупках или оценках (Linden и др. 2003). С этого момента, практическое применение рекоммендательных систем начало быстро распространятся, в то время как вычислительные мощности становится дешевле и алгритмы становятся более широко распространены.

Вместе с развитием научного поргресса в сфере рекомендательных систем, которые их сделали более быстрыми и эффективными, начали появляться фундаментальные органичения, которые состоят в том, что в истории сохраняются только данные оценок пользователей. Несмотря на развитие алгоритмов, невозможно удовлетворить определенные потребности в сфере рекомендаций без сбора и анализа дополнительной информации о объектах и пользователях системы. Одно из направлений, которое стало популярным в последние несколько лет это "content-based" фильтрация. Данное направление рассматривает объекты как набор свойств, причем некоторые из свойств являются общими для нескольких объектов (Garden and Dudek, 2006). Задача системы это определить какие именно свойства пользователю нравятся и какие свойства имеет определенный объект (обычно данные о свойствах объектов вводятся вручную).

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

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

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

2. Общие знания про рекомендательные системы в социальных сетях.

Рекомендации в социальных сетях

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

Вполне возможно, что по крайней мере некоторые сходства свойств близких людей в социальных сетях вызваны воздействием и взаимодействий людей в сети. Люди, как правило запоминают информацию, которая была конкретно предоставленна конкретно им. То есть личная информация работает лучше, чем безликий текст. Например, по мнению Hogarth, что при раздумьях над выбором нового автомобиля, мы скорее всего примем совет друга, чем данные о опросе 100 незнакомых людей.

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

Наша территория: BoardGameGeek.

BoardGameGeek (BGG) это самое популярное сообщество людей играющие в настольные и карточные игры. BGG содержит информацию о более чем 30 000 играх, вместе с соотвествующим им оценками, фотографиями, картами, отзывами и остальной информацией, которую создают пользователи. Более 40 000 зарегистрированных пользователей оценили игры на сайте BGG и многие из них указали некоторую персональную информацию в своих профилях и нашли своих друзей на сайте. Относительная открытость базы данных BGG (сайт предостовляет доступ к некоторым данным через XML API), а также ее умеренный размер подошли нам, чтобы попробовать алгоритм социально-обоснованных рекомендаций.

3. Множества данных.

Мы хотели получить данные непосредственно от администраторов BGG. Для этого мы написали им два раза по электронной почте, но не получили никакого ответа от них. Поэтому, мы решили написать ботов, которые собрали необходимые данные.

В данный момент мы закончили собирать информацию с сайта BGG. Мы собрали следующие данные:

• Игры, которые оценил хотябы один пользователь (примерно 30K);
• Пользователей, которые оценили хотябы одну игру (примерно 40K);
• Оценки игр пользователями;
• Игры в списках желаний пользователей вместе с их значимостью для каждого пользователя;
• Отношения между пользователями - ситема друзей (“GeekBuddies”).

Чтобы получить информацию о пользователях и оценках мы использовали API, предоставляемый сайтом BGG. Однако, для получения данных о играх и взаимоотношениях пользователей более проблематичноб, так как она была доступна только зарегистрированным пользователям. Чтобы преодолеть эту преграду мы создали скрипт, который притворялся вошедшим в систему пользователем. Мы посылали запросы каждые 2 секунды и собрали всю необходимую информацию за 3 дня при последовательной работе скрипта.

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

4. Алгоритм.

Мы выбрали для реализации модифицированную версию вероятностного алгоритма матричной факторизации (PMF [Minh 07]). Различные варианты этого подхода очень популярны среди участников конкурса Netflix [Netflix.com]. Алгоритм принимает в качестве входных данных матрицу рейтингов R, размероностью M × N, где Rij это оценка игры j пользователем i. Основная идея PMF, это нахождение низкоразрядного разложение R при аппроксимации его как произведение двух матриц низкого ранга:

Рисунок 4.1. Формула декомпозиции матрицы рейтингов R

Где U ∈ R[M][D], G ∈ R[D][N] , и размерность D намеренно сделана маленькой (D ≪ M,N).

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

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

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

Задача алгоритма - определить набор пользователей-прототипов и коэффициентов линейной комбинации, связанные с каждым прототипов или , другими словами, найти матрицы U и G, которые при умножении будут наиболее похожи на исходную матрицу R. Есть много способов факторизации матрицы, которые стремятся к приближение с низким рангом. (т.е. FA and PCA [Jolliffe, 86]).

PMF подходит для очень разрежанных исходных данных, так как это сводит к минимуму средне квадратичные ошибки (􏰀􏰀􏰀Sum(i, j, (R[i][j] - U[i]T*G[i])^2)) только для ненулевых элементов матрицы R. В такой модели, как только мы определяем U и G, мы можем легко предположить какие оценки пользователь поставить еще неоцененным играм (пустые ячейки матрицы оригинальной R). Тогда мы можем выбрать игры с высоким предсказанным рейтингом и рекомендовать их пользователям.

Для того, чтобы включить информацию о социальнойных отношениях пользователей. Введем матрицу дружбы F, размерностью M × M. Где F[i][j]=1, если i-ый пользователь указал j-го пользователем другом и 0 если не указал. Затем сформулируем следующую модель данных:

Рисунок 4.2. Формула декомпозиции матрицы рейтингов R с учетом рейтингов друзей

Другими словами, "внутренние" оценки каждого пользователя являются линейной комбинацией прогнозируеммых пользовательских профилей. Однако, на профиль имеют влияние "внешние" факторы - профили друзей, так как мы их добавили в исходную матрицу. Матрица друзей просто добавляет дополнительные данные. Исходя из того, что матрица F известна, мы можем вычислить матрицы U и G.

Рисунок 4.3. Формула нахождения матриц U и G

Рисунок 4.4. График квадратного отклонения ошибок для алгоритмов "реконструкция" и "базисная линия"

Рекомендации могут быть получены путем вычисления матрицы (R^) = FUG и поиска наиболее высоких вычисленных рейтингов в качестве рекомендации для пользователя.

Мы реализовали PMF нас основе языка java и Matlab API. Дополнительные алгоритмические детали приведены в приложении.

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

5. Оценка алгоритма.

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

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

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

6. Особенности реализации алгоритма.

В конечном итоге мы будем иметь web-приложение, где пользователя сайта BGG смогут авторизоваться и получить рекомендации.

Сервис будет работать следующим образом. Задача, запускаемая еженедельно, собирает новую иинформацию с сайта BGG и сохраняет ее в базу данных рекомендательного алгоритма. Алгоритм будет вычислять новые матрицы весов, которые будут загружены на web-сервер. После этого, для вычисления рекомендации для любого пользователя, приложение будет умножать матрицу данных о пользователе с матрицей весов и тем самым вычисляя наиболее подходящие ему объекты. Новым пользователям будет предложено оценить некоторые игры, для того чтобы получить исходные данные о его предпочтениях.

Идеальным вариантом была бы кооперация с BGG сайтом для получения данных в режиме реального времени, что сделает сервис более эффективным. Мы продолжаем общаться с администраторами на этот счет, но если это все же будет невозможно, то сервис будет анонсирвоан через форум BGG.

7. Вывод.

Заглушка. В финальной версии, мы обсудим результаты работы алгоритма и будущие планы.

Литература

1. R. Hogarth. Judgment and Choice, John Wiley and Sons, 1980.
2. J. Leskovec, A. Singh, and J. Kleinberg. Patterns of Influ- ence in a Recommendation Network. Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2006.
3. M. McPherson, L. Smith-Lovin, and J.M. Cook. Birds of a Feather: Homophily in Social Networks. Annual Review of Sociology, 2001, 27:415-44.
4. A. Minh, et al. Probabilistic Matrix Factorization Applied to the Netflix Rating Prediction Problem. To appear in NIPS 2007.
5. A. Narayanan and V. Shmatikov. How to Break Anonymity of the Netflix Prize Dataset. arXiv:cs/0610105v2 [cs.CR]
6. Netflix forum. http://www.netflixprize.com/community/ viewtopic.php?id=778
7. Board Game Geek. http://www.boardgamegeek.com/
8. IT Jolliffe. Principal Component Analysis. Springer- Verlag, New York NY, 1986.
9. R. Crammer et al.. Secure Distributed Linear Algebra in a Constant Number of Rounds. Lecture Notes in Computer Science, 2001.
10. M. Garden and G. Dudek. Mixed Collaborative and Content-Based Filtering with User-Contributed Semantic Features, AAAI, 2006.
11. G. Linden, B. Smith, J. York. Amazon.com Recommenda- tions: Item-to-item Collaborative Filtering. IEEE Internet Computing Industry Report, 2003.

Приложение А. Рекомендации по безопасности.

В данном приложении мы расскажем про возможность построения распределенной версии нашей рекомендательнйо системы, которая не требует матрицы дружеских отношений. Существует несколько проблем с приватностью данных, которые мы хотим обсудить.

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

Рисунок A.1. Формула квадратной оптимизации разреженной матрицы активности нового пользователя

где x это желаемый вектор результатов для пользователя, G^ это подматрица G составленно только из тех колонок, где пользователь поставил оценки, и r^ это вектор существующих оценок пользователя. Этот пользователь может легко вычислить решение локально x = (G^G^T)^(-1)(G^)^(T)(r^).

Следующий сценарий, когда новый пользователь с некотрыми оценками и друзьями (которые появилядлись в оригинальной матрицы R). Опять, пользователю необходимо решить проблему квадратной оптимизации, но в данный момент необходима матрица друзей F. В этом случае мы также посылаем пользователю матрицу U и он может получить определенные строки из данной матрицы не раскрывая, кто его друзья.

Наиболее сложная часть происходит на этапе вычисления и обучения.

Рисунок A.2. Формула вычисление матрицы активности друзей для нового пользователя

без знаний о матрице F или ее обратной версии. Мы предполагаем, что каждый пользователь сохраняет приватные данные о своих друзей. Это вектор длины (количество пользователей) с позициями i,j данных самого пользователя в матрице и позициями i,j данных его друзей.

Cуществуют две проблемы которые должны быть решены. Первая проблема, это вычисление F^(−1) при сохранении конфидециальности. Вторая проблема это те случаи, когда пользователь просто посылает нам ретроспективу F^(−1)R и мы можем найти решение для F-1.