INFORMATION RECOMMENDATION SYSTEM ADAPTED TO CLOUD ADVERTISING SERVICE
Authors:
1.
Astrakhan State Technical University
2.
Astrakhan State Technical University
(Professor)
Type:
Article
Pages:
from 88
to 96
Status:
Published
Received:
05.04.2015
Accepted:
25.04.2015
Published:
25.04.2015
Subject area:
VAC 05.12.2013 Системы, сети и устройства телекоммуникаций
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK [004.946:658.62]:[338.47:654.15]
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
VAC 05.13.01 Системный анализ, управление и обработка информации (по отраслям)
VAC 05.13.06 Автоматизация и управление технологическими процессами и производствами (по отраслям)
VAC 05.13.10 Управление в социальных и экономических системах
VAC 05.13.18 Математическое моделирование, численные методы и комплексы программ
VAC 05.13.19 Методы и системы защиты информации, информационная безопасность
UDK [004.946:658.62]:[338.47:654.15]
GRNTI 20.01 Общие вопросы информатики
GRNTI 28.01 Общие вопросы кибернетики
GRNTI 49.01 Общие вопросы связи
GRNTI 50.01 Общие вопросы автоматики и вычислительной техники
GRNTI 82.01 Общие вопросы организации и управления
Language:
Russian
Keywords:
recommendation system, hybrid method of recommendations, mutual recommendations, implicit and explicit selection criteria
Abstract (English):
The paper considers the problem of information overload of the users of large-scale Internet services. The amount of data in the global information space is growing much faster than the ability of an individual user or client to handle them. As a result, information overload has become a serious problem for all Internet services. The solution of the problem is the implementation of the recommendation system. The methods of the recommendations in the related subject areas are described, as well as adaptation of these methods to the domain of advertising services is made. Two categories of the users are defined: advertisers - companies that wish to order advertising services and distributors - people who are ready to provide this advertising service. The main objective of this internet-service is to make as many transactions between advertisers and distributors as possible. The objects of the recommendations in this system are users. The analysis of selection of the users’ criteria is made; definitions of explicit and implicit criteria are provided. The evaluation function of correspondence of the users, which is based on the algorithm of vector spatial modeling, is considered. The algorithm enhancing the quality of the recommendations by taking into account the interests of the recommended and recommended sites, which in their turn partially solve the problem of information overload of the users of the resource is presented.
The paper considers the problem of information overload of the users of large-scale Internet services. The amount of data in the global information space is growing much faster than the ability of an individual user or client to handle them. As a result, information overload has become a serious problem for all Internet services. The solution of the problem is the implementation of the recommendation system. The methods of the recommendations in the related subject areas are described, as well as adaptation of these methods to the domain of advertising services is made. Two categories of the users are defined: advertisers - companies that wish to order advertising services and distributors - people who are ready to provide this advertising service. The main objective of this internet-service is to make as many transactions between advertisers and distributors as possible. The objects of the recommendations in this system are users. The analysis of selection of the users’ criteria is made; definitions of explicit and implicit criteria are provided. The evaluation function of correspondence of the users, which is based on the algorithm of vector spatial modeling, is considered. The algorithm enhancing the quality of the recommendations by taking into account the interests of the recommended and recommended sites, which in their turn partially solve the problem of information overload of the users of the resource is presented.
Keywords:
recommendation system, hybrid method of recommendations, mutual recommendations, implicit and explicit selection criteria
recommendation system, hybrid method of recommendations, mutual recommendations, implicit and explicit selection criteria
Введение Последние достижения в области информационных и сетевых технологий обеспечили всевозможные способы работы с информацией и позволили вести коммерческую деятельность в сети Интернет. В 2012 г. объем российского рынка розничной торговли во всемирной сети достиг 405 млрд руб. По данным исследовательской компании «eMarketer» [1] каждый второй пользователь интернета когда-либо пользовался услугами интернет-магазинов. Количество данных в этом глобальном информационном пространстве растет гораздо быстрее, чем способность отдельного пользователя или клиента обработать их. В результате информационная перегрузка пользователей стала серьезной проблемой всех масштабных интернет-сервисов, решение которой состоит в разработке рекомендательной системы. Система рекомендаций - информационная система, которая, основываясь на данных о пользователе, пытается предсказать, какие именно объекты будут наиболее интересны конкретному пользователю, предлагая их в первую очередь. В настоящее время рекомендательные системы активно используются в таких областях как электронная коммерция, реклама, медиа- индустрия, рекрутинг и т. д. Подобные системы обрабатывают информацию о различных типах объектов, а также о том, каким именно образом пользователи взаимодействовали с объектом (купили, посмотрели, послушали и т. д.). Примерами таких сервисов являются Amazon [2], Netflix [3], Movielens [4], Youtube.com [5] и др. Кроме того, существуют системы, в которых в качестве объекта рекомендаций выступают пользователи. Такие информационные системы эксплуатируются в социальных сетях [6], [7] и найме персонала [8-10]. Для предоставления рекомендаций данные системы используют методы коллаборативной фильтрации. [11]. Рекомендательные системы имеют огромный потенциал и для рекламной сферы деятельности. Новейшие рекламные стартапы уже внедрили данные системы в свой продукт и в настоящее время производят тестирование, сбор информации от пользователей и модернизацию. Сервис «CrowdAdvertising» (CA) [12] не является исключением. CrowdAdvertising - интернет-площадка для поиска людей, оказывающих рекламные услуги. Пользователи делятся на две категории: рекламодатели (РД) - компании, которые желают заказать рекламную услугу, и рекламораспространители (РР) - лица, готовые оказать ту или иную рекламную услугу. Сервис выполняет роль биржи, он способствует организации взаимодействия обеих категорий пользователей между собой. Основная его задача - подобрать РД, подходящих РР для проведения эффективной рекламной компании [11]. По данным статистики сервиса на найм одного РР РД тратит в среднем 20 мин., за это время он просматривает примерно 15 резюме. С одной стороны, на организацию достаточно крупной рекламной компании, где количество участников превышает 100 чел., затрачивается большое количество времени, что порой сдвигает сроки рекламных компаний, а в худшем случае делает её невозможной. С другой стороны, по статистике CA 80 % РР пользуется сервисом разово, т. е. после участия в одной рекламной компании они больше не используют сервис. На основании опросов клиентов был сделан вывод, что пользователи прибегают к услугам сервиса не только с целью заработка, главная цель для них - участие в интересном проекте, помощь в продвижении любимых компаний, групп, идей. Цель данного исследования - предложить алгоритм рекомендаций, который позволит сократить время, затрачиваемое на вовлечение РР в рекламный проект, а также увеличит степень удовлетворенности РР при оказании рекламных услуг. Обзор существующих методов. Преимущества, недостатки, ограничения В социальных сетях рекомендации строятся на основании схожести интересов пользователей, близости позиций друг относительно друга в социальном графе, т. е. чем больше у двух пользователей общих знакомых, тем больше вероятность их потенциальной дружбы. В ходе взаимодействия с системой, пользователи, взаимодействуя с объектами, формируют матрицу рейтингов. Рейтинг - оценка пользователя, данная какому-либо объекту системы (музыка, новости и т. д. другого пользователя), как правило, в интервале [0, 1]. Из таких рейтингов и составляется матрица, где каждый столбец - пользователь, строка - объект системы, а элемент - рейтинг, выставленный пользователем. Такая матрица формируется явными или/и неявными способами. Явные способы основаны на оценках пользователей, которые они выставляют после взаимодействия с объектом. Это матрицы рейтингов в чистом виде. Неявные способы, позволяют заполнить матрицу на основании анализа истории взаимодействия пользователей с объектами. При большом количестве пользователей и объектов матрица рейтингов достигает значительных масштабов, поэтому обработка информации занимает достаточно большое количество времени, а иногда и вовсе становится невозможной. В этом случае прибегают к помощи алгоритмов SVD (Singular Value Decomposition) [13] и MMMF (мульти-мастер MySQL failover) [14], которые привносят в систему масштабируемость и быстроту. Выработка рекомендаций обычно основана на методе коллаборативной фильтрации [15]. Данный метод рекомендует объекты на основании поиска похожих пользователей, а также пытается сгрупировать похожих друг на друга пользователей и порекомендовать одному из них объекты, которые заинтересовали бы другого, похожего на него пользователя (или группу пользователей). Существуют различные вариации данного подхода: основанные на пользователях (user-based) и предметах (item-based). В used-based схожесть определяется коэффициентом корреляции между рейтингами объектов пользователей. Чем больше совпадений в оценках, тем больше один пользователь похож на другого. В item-based, аналогично предыдущим примерам, схожесть предметов определяется коэффициентом корреляции между рейтингами данного предмета у пользователей системы. Рейтинги хранятся в рейтинговой матрице пользователей. Для вычисления корреляции обычно используют коэффициент корреляции Пирсона или косинус угла между векторами, которые состоят из рейтингов пользователей или объектов системы. Основные недостатки метода коллаборативной фильтрации - разреженность матрицы рейтингов и её масштабов, а также проблема «холодного старта» (формирование списка рекомендаций для новых пользователей или новых объектов) [16]. Но в то же время данная фильтрация достаточно эффективна, главным образом из-за того, что в ней учитывается история оценок. Ещё один метод, успешно зарекомендовавший себя в социальных сетях - социальный. Кроме истории взаимодействия пользователей и предметов в нем используются социальные связи между пользователями. Характерной чертой данного метода является учет схожести пользователей. Для повышения расчетов схожести используются косвенные оценки качества их связей (история сообщений, общие фотографии, совпадающее место работы, учебы и т. д.). В области электронного рекрутинга большинство систем использует стандартные методы фильтрации, основанные на поиске ключевых слов в базе данных. Данный факт, безусловно связан со сложностью задачи выработки рекомендаций в этой сфере. Сложность заключается в том, что системе необходимо учитывать как унарные атрибуты (рост, возраст, психические способности, индивидуальность личности и её соответствие поставленным задачам), так и атрибуты, зависимые от других факторов, людей, обстоятельств (взаимоотношения с другими членами команды) [17]. Из [17] видно, что для выработки рекомендаций было принято использовать вероятностную модель. Необходимо было разделить все навыки соискателя на типы: - концепт (аналитические навыки); - характеристика (разряд); - средство (диплом); - оценка (университет, выдающий диплом). Отсюда следует, что любого человека можно описать комбинацией типов его способностей. Далее строится вероятностная гибридная модель рекомендаций, которая преобразуется во множество термов и адаптируется под вероятностный скрытый семантический анализ, описанный Т. Хофманном [16]. Затем модель обрабатывается на основании гибритного подхода, основанного на концепциях коллаборативной фильтрации и анализа контента. В сочетании эти модели дополняют друг друга. Параметры модели оценивают, используя алгоритм максимально-ожидаемого результата [18]. Модель окончательных результатов в рейтинговой матрице включает вероятность того, что рекрутер X оценил кандидата Y с оценкой V [10], где 0 V 1, при этом 0 - не подходит, а 1 - подходит. Вероятностный подход автоматически рекомендует кандидатов, которые лучше всего подходят на вакансию, на основании анализа рейтингов и с учетом основных навыков РР [17]. Данный метод достаточно эффективен и может быть применен в качестве выработки рекомендаций в сфере рекрутинга. Однако он имеет существенные недостатки такой предметной области как рекламная деятельность. 1. Характер работы. Метод ориентирован на условия, когда РД и РР настроены на длительное сотрудничество. 2. Двунаправленность рекомендаций, т. е пользователям должно быть выгодно работать друг с другом. Такую двунаправленную рекомендацию сложно подобрать, т. к. системе трудно понять мотивацию как РД, так и РР. При выборе рекламных компаний это могут быть как интерес, деньги, хобби, так и пиар, скрытая реклама и т.д. Таким образом, в сервисе CA в роли объекта рекомендаций выступает как отдельный человек (РР), так и компания, пользующаяся рекламными услугами (РД). Определение двунаправленной рекомендации Для решения проблемы двунаправленной рекомендации сам рекомендательный процесс должен быть разделен на две части: рекомендация для РД и рекомендация для РР. В соответствии с рекомендациями для РД справедливо следующее утверждение: РР с наиболее высокой степенью соответствия должен быть рекомендован в первую очередь (выражается числом в интервале [0, 1], где 1 - полностью соответствует, 0 - полностью не соответствует). Таким образом, получаем: РД - u, - множество всех РР для данного u , когда P1(u, v) - степень соответствия между u и каждым v в V. Поскольку существуют РР, не входящие в V, должно выполняться соотношение: , где v0 - РР, не входящие в V. Аналогично, в соответствии с рекомендациями для РР справедливо, что РД с наиболее высокой степенью соответствия должны быть рекомендованы в первую очередь. Отсюда следует, что РР - v, U - список всех РД для данного v, когда P2(v, u) - степень соответствия между v и каждым u в U. Поскольку существуют РД, не входящие в U, должно выполняться соотношение , где u0 - РД, не входящие в . Для взаимной рекомендации между u и v, требования должны удовлетворять обе стороны, следовательно, необходимо выбирать только те объекты, которые в наибольшей степени соответствуют пересечению их предпочтений. Таким образом, взаимная рекомендация для РД представлена в виде: . Аналогично, для РР: . Взаимная рекомендация должна учитывать критерии выбора как РД u, так и РР v. Критерии выбора - требования, определенные РД при поиске РР (явно или неявно), а также требования РР при поиске рекламной компании РД. Чтобы получить единый набор рекомендаций, необходимо объединить множества RR(u) и RR(v) , где ω1, ω2 - весовые коэффициенты, которые могут изменяться в зависимости от ситуации. Согласно векторной пространственной модели (Vector Space Model), любой текст состоит из множества термов, каждый из которых имеет весовой коэффициент, устанавливаемый в зависимости от его значимости. Используя данную модель, мы можем представить текст в виде вектора где d - документ; - различные термы; ωi(d) - вес терма ti в d; tfi(d) - частота повторения. Частота повторения - отношение числа вхождения некоторого терма к общему количеству термов документа: , где ni - число вхождений терма в документ, а в знаменателе - общее число термов в документе. Таким образом, оценивается важность слова в пределах отдельного документа. Для того чтобы вычислить вес терма, обычно используется алгоритм TF-IDF [20]: , где N - количество всех слов текста, ni - число вхождений ti в d. Подобие между текстами d1 и d2 выражается косинусом угла между двумя векторами: (1) Явные и неявные предпочтения Вектор называется вектором явных предпочтений u, где P0 - вектор признаков u и вектор критериев выбора РР v. Векторназывается вектором неявных предпочтений v, где P1 - вектор признаков v и - вектор критериев выбора РД u. Неявные предпочтения вычисляются на основании истории взаимоотношений между пользователями. Когда РД хотят провести рекламную акцию, они описывают требования к РР, формализуют критерии отбора (личные качества, необходимый опыт работы и т. д.). После этого РР посылают запросы на участие в рекламной акции. РД изучают профиль РР, его резюме и принимают решение о принятии или отклонении запроса. Если РД положительно реагируют на запрос (например, назначают собеседование, пишут сообщения), это означает, что вероятность совпадения повышается, а если РД реагируют на запрос нейтрально или отрицательно, то вероятность уменьшается. Введем обозначения. Пусть A - множество критериев РР v, a - критерий множества A, va - значение a, n - частота присутствия va в профиле, отправленном на рассмотрение РД u, тогда , - неявное предпочтение РД u. Пусть B - множество критериев РД u, b - критерий множества B, vb - значение b, m - количество положительных ответов среди профилей с vb, тогда , PI(v) - неявное предпочтение РР v. Расчет комплексного сходства предпочтений Каждый u, v преобразуется в векторную пространственную модель, принимая при этом векторную форму . Степень сходства явных предпочтений определена формулой (1), где ω(u), ω(v) рассчитываются аналогично весу термов в документе, таким образом, степень соответствия РД и РР выражается формулой где ωi(u) - вес критерия РД; ωi(v) - вес критерия РР; n - количество всех критериев по которым определяется сходство. Для неявных предпочтений соответствие pu РР критериям выбора РД: (3) где va,i - значение характеристики РР; n - количество всех критериев; N - количество запросов на предоставление рекламных услуг, отправленое каждому РД. Общее предпочтение для каждого из пользователей состоит из явных и неявных предпочтений. Комплексное соответствие между пользователями рассчитывается по формуле (4) где α, β - весовые коэффициенты, которые в сумме дают 1 (). Sim(u, v) удовлетворяет требованиям РД, но во взаимных рекомендациях необходимо достигнуть удовлетворения обеих сторон. Согласно формуле (4), мы можем получить соответствие РР v и РД u. Взаимное значение рекомендации будет вычисляться следующим образом: (5) Алгоритм двунаправленных рекомендаций Поддержка взаимных двунаправленных рекомендаций реализуется следующим образом. Прежде всего анализируются профили РД и РР, из которых извлекается необходимая информация. Затем ищутся явные и неявные предпочтения пользователей, в соответствии с историей их взаимодействия. Далее рассчитываются сходства на основе явных и неявных предпочтений. Наконец, вычисляется комплексное сходство и генерируется список рекомендаций. Основные шаги алгоритма. 1. Обработка пользовательских предпочтений. В соответствии с требованиями кандидата определяются критерии каждого пользователя, которые затем извлекаются и преобразуются в векторную форму, чтобы получить явные предпочтения PE. Далее анализируется информация о запросах на участие в проектах, подсчитывается количество запросов с содержанием различных критериев, вычисляются неявные предпочтения PI в соответствии с частотой употребления каждого из критериев. 2. Расчет сходства пользователей. Происходит расчет соответствия пользователей по формулам (2)-(4), а в конце вычисляется комплексная оценка по формуле (5). 3. Генерация рекомендаций. Полученные оценки сортируются в порядке убывания, после чего система составляет список рекомендаций. Алгоритм вычисления соответствий содержит в себе следующие шаги. Входные параметры РД u, РР v, параметры и выходные параметры . 1. Извлечь явное предпочтение Pu из профиля u 2. Извлечь из резюме критерий v 3. Получить 4. 5. Для каждого критерия aA делать 6. Вычислить значение n атрибута a в V 7. Если n = 0 тогда 8. Иначе 9. 10. Получить 11. Конец Если 12. Конец Цикла 13. 14. Вернуть Данный алгоритм разделен на несколько частей. Первая часть (строки 1-4) - извлечение критериев выбора, преобразование их в векторную форму как для РД, так и для РР, вычисление степени соответствия на основании явных предпочтений векторной пространственной модели. Вторая часть (строки 5-13) - вычисление степени соответствия неявных предпочтений. Заключительная часть (строки 14-15) - вычисление комплексного соответствия как комбинации явных и неявных предпочтений, по (4). Алгоритм вычисления двухсторонней рекомендации состоит из следующих шагов. Входные данные: РД - u, M - количество необходимых участников рекламного проекта и выходные данные: список рекомендаций R. 1. Извлечь критерий Pu из профиля u 2. Для каждого v делать 3. 4. Если тогда 5. Извлечь критерий Pu для v 6. 7. 8. Конец Если 9. Конец Цикла 10. Для каждого до M делать 11. Если тогда 12. Сортировать 13. Конец Если 14. Конец Цикла 15. Вернуть R. Данный алгоритм реализует взаимные рекомендации между РД и РР. Первая часть (строки 1-9) - вычисляет взаимную оценку согласно алгоритму вычисления соответствий. Вторая часть (строки 10-15) - формирует лист рекомендаций. Заключение Взаимные рекомендации - это новое направление исследований в области рекомендательных систем. Описаны методы рекомендаций в различных предметных областях, произведена адаптация этих методов к сфере рекламных услуг. Произведен анализ критериев отбора пользователей, даны определения явных и неявных критериев. Рассмотрен алгоритм, позволяющий повысить качество рекомендаций за счет учета интересов рекомендуемого и рекомендованного объектов, что в свою очередь частично решит проблему информационной перегрузки пользователей ресурса.
1. URL: http://www.emarketer.com/Article/Global-B2C-Ecommerce-Sales-Hit-15-Trillion-This-Year-Driven-by-Growth-Emerging-Markets/1010575 (data obrascheniya: 27.03.2015).
2. URL: http://www.amazon.com/ (data obrascheniya: 27.03.2015).
3. URL: https://www.netflix.com (data obrascheniya: 27.03.2015).
4. URL: https://movielens.org/ (data obrascheniya: 27.03.2015)
5. URL: http://www.youtube.com/ (data obrascheniya: 27.03.2015)
6. Kunegis Jérôme. Online Dating Recommender Systems: The Split-complex Number Approach / Jérôme Kunegis, Gerd Gröner, Thomas Gottron. Dublin, 2012. P. 37-44.
7. Brozovsky Lukas. Recommender System for Online Dating Service / Lukas Brozovsky, Vaclav Petricek. KSI MFF UK Malostransk´e n´am. Prague. Czech Republic. 2007.
8. Laptev V. V. Metod ocenki deyatel'nosti razrabotchikov ob'ektno-orientirovannogo programmnogo obespecheniya. / V. V. Laptev, A. V. Morozov // Vestn. Astrahan. gos. tehn. un-ta. Ser.: Upravlenie, vychislitel'naya tehnika i informatika. 2010. № 1. S. 122-126.
9. Al-Otaibi Shaha T. Job Recommendation Systems for Enhancing E-recruitment Process / Shaha T. Al-Otaibi, Mourad Ykhlef. Las Vegas Nevada. 2013. P. 433-440.
10. Färber Frank. An automated recommendation approach to selection in personnel recruitment / Frank Färber, Tim Weitzel, Tobias Keim // The Fifth Framework Programme Information Society Technologies, 2000. P. 41-48.
11. Savchenko P. N. Ispol'zovanie sistemy rekomendaciy v processe vybora reklamorasprostraniteley / P. N. Savchenko, I. Yu. Kvyatkovskaya // Materialy 12-y Mezhdunar. nauch.-prakt. konf. «Perspektivy razvitiya informacionnyh tehnologiy». Novosibirsk, 2014. 150 s.
12. URL: http://crowda.azurewebsites.net/ (data obrascheniya: 27.03.2015).
13. Sarwar B. Incremental singular value decomposition algorithms for highly scalable recommender systems / B. Sarwar, G. Karypis, J. Konstan, J. Riedl // Fifth International Conference on Computer and Information Science, 2002. P. 399-404.
14. Rennie D. M. Fast maximum margin matrix factorization for collaborative prediction / D. M. Rennie, N. Srebro / Proceedings of the 22nd International Conference on Machine Learning, 2005 // URL: http://people.csail.mit.edu/jrennie/papers/icml05-mmmf.pdf.
15. Krzywicki Alfred. Interaction-Based Collaborative Filtering Methods for Recommendation in Online Dating / Alfred Krzywicki, W. Wobcke, X. Cai, Ashesh Mahidadia, Michael Bain, Paul Compton, Yang Sok Kim // IEEE Intelligent Systems. 2007. No. 22 (3). P. 48-55.
16. Hofmann T. Probabilistic latent semantic analysis / T. Hofmann // Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI), 30 July - 1 August, Stockholm. 1999. P. 289-296.
17. Malinowski J. Decision Support for Team Staffing: An Automated Relational Recommendation Approach / J. Malinowski, T. Weitzel, T. Keim // Decision Support Systems. 2008. Vol. 45. No. 3. P. 429-447.
18. Dempster A. P. Maximum likelihood from incomplete data via the EM algorithm / A. P. Dempster, N. M. Laird, D. B. Rubin // Journal of the Royal Statistical Society. Series B (Methodological). 1977. Vol. 39. No. 1. P. 1-38.
19. Salton G. A vector space model for automatic indexing / G. Salton, A. Wong, C. S. Yang // Communications of the ACM. 1975. Vol. 18. No. 11. P. 613-620.
20. Zhongxiu He. The calculation method research of webpage content based on vector space model / He. Zhongxiu // Computer and modernization. 2010. No. 9 (14). P. 53-55.
