Кластеризация профилей пользователей в рекомендательных системах поддержки жизнеобеспечения на основе реальных неявных данных © С. А. Филиппов © В. Н. Захаров © С. А. Ступников © Д. Ю. Ковалев Институт проблем информатики ФИЦ ИУ РАН, Москва stanislav@philippov.ru VZakharov@ipiran.ru ssa@ipi.ac.ru dm.kovalev@gmail.com Аннотация жизнеобеспечения, активно использует рекомендательные системы для решения задач Данная работа посвящена описанию решения адресного продвижения товаров и услуг с учетом ключевой задачи в контексте построения конкретных пользовательских предпочтений. рекомендательных систем поддержки Основным источником информации о жизнеобеспечения. Этой задачей является выявление пользовательских предпочтениях являются данные пользовательских предпочтений и формализация их об активности пользователей при посещении посредством формирования поведенческих конкретного интернет-ресурса. Эти данные профилей с последующим выявлением групп собираются в основном неявным образом пользователей со схожими характеристиками. (протоколирование действий пользователей) и Основным источником информации о обладают следующими основными свойствами: пользовательских предпочтениях является массив значительный объем и быстрое изменение (или неявно собираемых данных об их действиях при обновление) данных во времени. При этом адаптация навигации по страницам Интернет магазинов. Под под конкретного пользователя – весьма сложная поддержкой жизнеобеспечения понимается круг задача, поскольку для ее решения необходимо задач по обеспечению населения необходимыми для принимать во внимание как присущие человеку их жизнедеятельности продуктами, включая неопределенность и спонтанность в рамках продукты питания, бытовой химии, косметики и конкретного интернет-ресурса, так и множество многое другое. Эти задачи, как правило, решают неопределенностей, связанных с особенностями магазины (в том числе и интернет-магазины) оптовой функционирования Интернет. и розничной торговли. Авторами работы Одним из простейших подходов к выработке представлен подход к построению рекомендаций является использование рекомендательной системы, основанный на решении статистических метрик для выявления, например, задачи коллаборативной фильтрации с наиболее популярных, дешевых (дорогих), близких использованием методов кластерного анализа по заданным характеристикам объектов и данных для выявления групп пользователей со предложение их пользователям без учета их схожими предпочтениями. Достоинства решения персональных предпочтений. Более сложные продемонстрированы на примере тестового массива алгоритмы выявляют предпочтения пользователей данных, полученного из действующего интернет- посредством формирования поведенческого магазина Thaisoap. Работа выполнена при поддержке профиля пользователя, который, в свою очередь, Министерства образования и науки РФ, уникальный определяется на основании анализа его активности идентификатор проекта RFMEFI60414X0139. при выборе товаров и услуг. Также в настоящее Введение время развиваются подходы, основанные на использовании нечеткой логики, позволяющей Современная электронная коммерция, учитывать различные типы неопределенностей и сопровождающая и поддерживающая процессы кластеризовать пользовательские профили [1]. Самым распространенным подходом при Труды XVIII Международной конференции реализации рекомендательных систем в электронной DAMDID/RCDL’2016 «Аналитика и управление коммерции является метод коллаборативной данными в областях с интенсивным фильтрации (collaborative filtering). Данный подход использованием данных», Ершово, 11-14 октября позволяет вырабатывать рекомендации, основанные 2016 на модели предшествующего поведения 98 пользователей с учетом поведения других каких тематических разделах и группах пользователей со сходными характеристиками [2]. принимает участие каждый пользователь и Для выделения групп пользователей со сходными насколько активно. характеристиками, как правило, используются Другими достаточно распространенными различные методы извлечения данных (data mining), примерами протоколирования действий которые, в свою очередь, используют алгоритмы пользователей являются счетчики посещений кластеризации. В частности, в работе [3] страниц, прокси-серверы и интернет-провайдеры. указывается, что решение вопросов идентификации Собранные данные о пользовательской групп пользователей по своей природе опирается на активности характеризуются большим объемом и использование методов кластеризации. разнородностью. Традиционные базы данных Кластеризация данных может быть также малоприменимы для работы с этими данными по использована для генерации профилей причине больших объемов данных и повышенных пользователей на основе информации о действиях требований к производительности [4]. Как правило каждого пользователя, а затем для формирования используются так называемые NoSQL системы групп пользователей на основе их профилей. управления данными (HBase, Cassandra). Их Основной задачей, которую авторы данной характерными особенностями являются отказ от работы ставили перед собой, является разработка транзакций, практически линейная комбинированного подхода к построению масштабируемость, высокая скорость обработки рекомендательных систем, обеспечивающего запросов, отсутствие жесткой схемы данных. наиболее полное использование всех данных о В контексте проблемы персонализации контента посетителях интернет-магазинов с целью выработки (а также прогнозирования, выявления предпочтений рекомендаций наиболее адекватно отражающих их и групп схожих ресурсов) встает задача обработки ожидания (пертинентность предложения). Научно этих данных и выявления определенных практическая новизна работы заключается в идее закономерностей, позволяющих сделать выводы о комбинированного использования методов Item-Item конкретных предпочтениях пользователей. Таким CF и User-User CF, что позволяет минимизировать образом, основной целью обработки данных о недостатки каждого из них и добиться более пользовательской активности является извлечение высокого качества работы рекомендательной полезной информации, которая может, в свою системы в целом. Данная статья входит в серию очередь, использоваться для решения следующих статей по данной проблематике и посвящена задач [5]: решению задачи коллаборативной фильтрации User- User CF с использованием методов кластеризации 1. Кластеризация ресурсов. Группирование для выявления групп пользователей со схожими схожих по множеству посетителей ресурсов предпочтениями. Предполагается, что при наличии в несколько кластеров (групп) ресурсов. качественных данных о пользовательской Кластеризация позволяет строить каталоги активности метод User-User CF дает наиболее ресурсов, а также выявлять недостатки адекватные прогнозы. Использование методов существующих тематических каталогов. кластеризации для решения задачи выявления групп 2. Кластеризация пользователей. пользователей со схожими характеристиками Группирование схожих пользователей в позволяет добиться хорошего быстродействия и кластеры аналогично кластеризации качества работы алгоритма. ресурсов. Позволяет выявлять группы пользователей со схожими интересами. 1 Персонализация контента 3. Построение устойчивых поведенческих профилей пользователей в виде перечня Практически все современные интернет-ресурсы, групп ресурсов, посещаемых как данным ориентированные на работу с большим количеством пользователем, так и схожими с ним пользователей, собирают информацию об их пользователями. активности и анализируют (обрабатывают) ее с 4. Построение расширенных профилей целью персонализации своего контента для каждого пользователей, включающих социально- конкретного пользователя. В качестве наиболее демографические данные (анкеты), характерных примеров можно выделить: описательные статистики и поведенческие 1. поисковые машины, которые собирают и профили. Расширенные профили позволяют систематизируют информацию о страницах в классифицировать новых пользователей, сети Интернет заинтересовавших выявлять зависимости между конкретных пользователей; пользовательским поведением и социально- 2. интернет-магазины, которые собирают и демографическими характеристиками. систематизируют сведения о предпочтениях 5. Сегментация клиентской базы на основе своих пользователей в части товаров и услуг; расширенных профилей позволяет выделять 3. форумы, интернет-дневники и социальные сегменты, как по анкетным данным сети, которые собирают информацию о том, в клиентов, так и по их поведению. Эта 99 информация используется при семантической модели, сингулярное разложение, маркетинговых исследованиях. вероятностный латентный семантический анализ, 6. Прямой маркетинг. Предоставление скрытое распределение Дирихле и марковской рекламы и маркетинговых предложений процесс принятия решений на основе моделей. конкретному пользователю на основе его Данный подход имеет целый ряд преимуществ и поведенческого профиля. характеризуется более высоким качеством рекомендаций по сравнению с первым подходом. 7. Персонализация контента. Представление Гибридный подход сочетает преимущества каждому пользователю сайта наиболее подходов, основанных на соседстве и моделях. интересной для него информации в наиболее Данный подход является наиболее эффективным с удобном для него виде. Знание точки зрения качества предсказаний, но при этом информационных предпочтений наиболее сложный в реализации и наиболее пользователя позволяет динамически требовательный к производительности аппаратной перестраивать контент сайта. платформы. 8. Построение карт сходства ресурсов и Основными проблемами, связанными с пользователей. Позволяет отображать реализацией и практическим использованием множества наиболее посещаемых ресурсов и алгоритмов коллаборативной фильтрации, являются наиболее активных пользователей в виде разреженность данных, проблема холодного старта и точечного графика. Схожим ресурсам масштабируемость. Разреженность данных (пользователям) соответствуют близкие изначально присуща исходным данным, которые точки на карте. Карту сходства можно используются для построения тематических использовать как графическое средство профилей пользователей (покупатели навигации. просматривают и(или) оценивают только Существуют различные методы и подходы, ограниченное число товаров и (или) услуг). Тем используемые на практике при решении самым качество рекомендаций может быть очень перечисленных выше задач. Весь класс этих методов низким, особенно на начальных этапах эксплуатации принято называть методами коллаборативной рекомендательной системы (когда еще не накоплено фильтрации. достаточное количество данных о пользовательской активности). Проблема разреженности данных 2 Коллаборативная фильтрация напрямую связана с проблемой холодного старта, когда рекомендательная система должна Результатом первого этапа обработки данных о вырабатывать рекомендации, имея минимальное пользовательской активности является построение количество данных о пользовательских матрицы активности, которая может нести предпочтениях. Проблема масштабируемости различную информацию о действиях пользователя. становится особенно острой для крупных интернет- Это может быть бинарная информация о посещении магазинов, продающих тысячи товаров миллионам или не посещении заданного ресурса данным покупателей. При таком количестве товаров и пользователем, частота (или число) пользований покупателей сложность алгоритма резко возрастает, ресурса r пользователем u, стоимость или рейтинг, что усугубляется тем фактом, что рекомендательная проставленный пользователем u для ресурса r и т.д. система должна давать результат в считанные Для оценки степени схожести пользователей в плане секунды. Дополнительно к перечисленному выше их предпочтений и построения поведенческих можно добавить проблему ограничения профилей могут использоваться различные функции разнообразия предложений. Рекомендательные сходства (метрики). Наиболее популярными среди системы, использующие коллаборативную них являются: косинусная мера, коэффициент фильтрацию, склонны предлагать товары, уже корреляции Пирсона, евклидово расстояние, пользующиеся популярностью, что препятствует коэффициент Танимото, Манхэттенское расстояние продвижению новых товаров и услуг [7]. и другие [6]. Для решения задачи коллаборативной 3 Кластеризация пользовательских фильтрации используются три основных подхода: основанный на соседстве (memory based), профилей основанный на модели (model based) и гибридный Одним из способов решения задачи подход (hybrid). Первый подход исторически коллаборативной фильтрации, успешно появился первым и характеризуется как достаточно используемых при реализации рекомендательных простой в плане реализации, а также эффективный с систем в современных системах электронной точки зрения производительности. Но коммерции, является кластеризация. В настоящее рекомендации, вырабатываемые с помощью данного время кластеризация – объединение в группы схожих метода, являются наименее точными. Подход, объектов – является одной из фундаментальных основанный на моделях при выработке задач в области анализа данных и Data Mining [8]. рекомендаций, использует такие методы как метод Существует большое количество методов байесовских сетей, кластеризации, латентной кластеризации, которые условно можно разбить на 100 следующие основные группы: использующие просмотрены (User-User переход между вероятностный подход (К-means, EM-алгоритм), категориями), и когда нет (внутрикатегориальная использующие методы искусственного интеллекта персональная фильтрация). (нейронные сети, генетические алгоритмы), В результате обработки поступивших данных для использующие теоретико-графовые модели, каждого пользователя в матрице активности было иерархические алгоритмы. В контексте решения определено число обращений к конкретной задачи коллаборативной фильтрации наибольшее категории товаров. Таким образом, каждая строка распространение получили алгоритмы, матрицы активности пользователей представляет использующие вероятностный подход и собой вектор оценок, соответствующих различным иерархические алгоритмы. категориям товаров (тематический профиль пользователя). Профиль пользователя характеризует В рамках проводимых исследований по степень его интереса к каждой группе товаров. повышению пертинентности информации в рекомендательных системах поддержки На рисунке 1 представлен фрагмент матрицы жизнеобеспечения авторы работы оценили активности пользователей, построенный в возможность применения всех приведённых выше результате обработки log-файла интернет-магазина методов кластеризации, а также их комбинации. В Thaisoap за недельный период времени. Число строк результате проведенного имитационного таблицы превысило пять тысяч (количество моделирования было установлено, что наиболее уникальных посетителей за данный период времени), подходящим с учётом существующих для работы число столбцов 180 (категории товаров). ограничений по скорости и объемам обработки данных для выявления групп пользователей со схожими предпочтениями (User-User CF) был признан метод кластеризации К-средних (K-means). В целом данный статистический метод прост в реализации и является хорошо масштабируемым [9]. Вычислительная сложность алгоритма О(nkl), где n – число объектов, k - число кластеров, l - число итераций. Одним из недостатков данного метода является необходимость заранее задавать число кластеров для разбиения. Для решения этой задачи проводится предварительный анализ исходных данных, позволяющий посредством минимизации суммы внутрикластерных расстояний выявить оптимальное число кластеров для разбиения. Рисунок 1 Матрица активности пользователей Следующим шагом стала проверка метода интернет-магазина Thaisoap кластеризации на тестовом массиве данных, предоставленных интернет-магазином Thaisoap. Предварительным этапом перед выявлением Магазин ориентирован на продажу натуральной групп пользователей со схожими характеристиками тайской косметики и кокосового масла. Каталог методами кластеризации является вычисление товаров магазина содержит более попарных расстояний между элементами матрицы 1 500 наименований товаров, которые разбиты на 180 активности пользователей. В качестве метрики классов (44 корневых классов, 136 подклассов). расстояния (функция сходства) было использовано Ежедневно магазин посещают в среднем около расстояние Евклида (геометрическое расстояние в 1 500 посетителей и проводят на нем (в среднем) многомерном пространстве), которое является одной порядка 11 минут каждый (на каждого посетителя из наиболее простых для реализации и часто приходится в среднем 28 переходов по ссылкам). используемых на практике метрик на сегодняшний день. Таким образом исходными данными для На рисунке 2 представлена гистограмма построения матрицы активности пользователей расстояний, полученная в результате обработки стали log-файлы (размер файла с записями за неделю матрицы с попарными расстояниями между превышает 100 МБ). При этом из всех объектами. Для построения гистограммы предоставленных неявных данных для публикации использовался статистический пакет R. было решено выбрать вычисления по наиболее Предварительное рассмотрение результатов универсальному агрегированному показателю – позволяет сделать вывод, что предпочтения (вектора число обращений к конкретной категории товара. активности) пользователей интернет-магазина Кластеризация по данному показателю позволяет Thaisoap не сильно отличаются (т.е. скорее всего сформировать рекомендацию постоянному большинство пользователей интересуются схожими пользователю сразу в двух случаях: и когда все категориями товаров). Данный вывод можно сделать товары в категории, к которой тяготеет пользователь, исходя из того, что около 90% данных на 101 гистограмме сосредоточено на отрезке расстояний от основании данных за другие недели дало схожие 0 до 5. результаты. Таким образом использование метода К-средних на реальных данных с одной стороны подтвердило результаты имитационного моделирования, а с другой стороны выявило недостатки анализа только предпочтений групп пользователей со схожими интересами только по одному агрегированному неявному показателю (User-User CF): для большинства посетителей отсутствует возможность сформировать сколь-либо персональное информационное предложение и требуется как расширенный анализ оставшихся неявных данных, так и иных методов, например, коллаборативной Рисунок 2 Гистограмма расстояний. фильтрации посредством анализа взаимосвязей Следующим шагом было определение между объектами (Item-Item CF). оптимального числа кластеров, требуемого для применения метода кластеризации К-средних. На рисунке 3 приведены результаты расчёта внутрикластерной суммы квадратов расстояний по методу локтя (Elbow method). Данный метод дал число в 30 кластеров. Рисунок 4 Результат работы алгоритма кластеризации Рисунок 3 Анализ количества кластеров Заключение Таким образом были получены все необходимые параметры и проведена кластеризация данных по В заключение необходимо отметить, что матрице активности пользователей. На рисунке 4 в использование различных алгоритмов кластеризации графическом виде представлен результат работы для решения задачи коллаборативной фильтрации в алгоритма кластеризации. Анализ полученных настоящее время является одним из перспективных результатов позволяет выделить несколько наиболее направлений. Большие объемы данных о крупных кластеров пользователей с номерами 1, 9, пользовательской активности и высокие требования 20, 21 и 22. Пользователи из кластера под номером 1 к быстродействию рекомендательных систем (размер кластера 1 384) демонстрируют слабое накладывают определенные ограничения на предпочтение ко всем категориям товаров. используемые алгоритмы. Поэтому наибольшее Возможно, что в кластер с номером 1 попали применение в этой области получили алгоритмы, посетители сайта, которые пришли без конкретной основанные на оптимизации некоторой целевой цели, например, просто ознакомиться с функции, определяющей оптимальное (в контексте предлагаемым ассортиментом товаров. задачи) разбиение множества объектов на кластеры. Пользователи из кластера номер 9 (размер 180) В частности, большой популярностью пользуются демонстрируют явное предпочтение к категории cat9 алгоритмы семейства К-средних (К-means, fuzzy С- ("Лицо"). Пользователи из кластера номер 20 (размер means, Густафсон-Кесселя), которые в качестве 1 366) демонстрируют предпочтение к категории cat7 целевой функции используют сумму квадратов ("Кокосовое Масло"). Сумма квадратов расстояний взвешенных отклонений координат объектов от относительно других кластеров мала, что говорит о центров искомых кластеров. небольшом различии объектов внутри кластера. В статье на примере данных интернет-магазина Пользователи из кластера номер 21 (размер 622) Thaisoap показаны достоинства и недостатки демонстрирую также предпочтение к категории cat7 кластеризации по простому агрегированному ("Кокосовое Масло"). Пользователи из кластера неявному показателю – числу обращений к номер 22 (размер 180) демонстрирую предпочтение к конкретной категории товара с использованием категориям cat47 ("MUST HAVE Зима 2016") и cat49 алгоритма кластеризации К-средних (K-means). В ("ХИТЫ нашего магазина"). Проведение расчётов на том числе была подтверждена слабая применимость 102 метода в условиях холодного старта (для новых или Магистра, Вычислительный Центр им. А.А. малоактивных пользователей). В данном случае Дородницина РАН, 2007. требуется применение иных неявных показателей [6] Xiaoyuan Su, Taghi M. Khoshgoftaar A survey of или принципиально других методов, например, Item- collaborative filtering techniques // Advances in Item CF, которые соответственно дают больше Artificial Intelligence, Volume 2009 (2009), Article информации о пользователе за единицу времени или ID 421425, 19p. лучше работают в ситуациях, когда данные о [7] Fleder D., Hosanagar K. Blockbuster Culture's Next пользовательской активности минимальны. При Rise or Fall: The Impact of Recommender Systems этом по мере накопления данных о предпочтениях on Sales Diversity // Management Science, Vol. 55, пользователей при выработке рекомендаций No. 5, May 2009, pp. 697-712. рассмотренный метод начинает давать всё более [8] Барсегян и др. Методы и модели анализа данных: уместные предложения и рекомендуется к OLAP и Data Mining. – СПб., 2004. использованию как основной. [9] Adam Coates and Andrew Y. Ng. Learning Feature Representations with K-means // Stanford Литература University, 2012, Статья в сети Интернет, URL: http://www.cs.stanford.edu/~acoates/papers/coatesn [1] А.Н.Алфимцев, В.В. Девятков, С.А.Сакулин g_nntot2012.pdf. Персонализация в гипертекстовых сетях на основе распознавания действий пользователей и Clustering of user profiles нечеткого агрегирования // Вестник МГТУ based on real implicit data им.Баумана, Сер. «Приборостроение», 2012, №3. in e-commerce recommender systems [2] М. Тим Джонс Рекомендательные системы: Stanislav A. Philippov, Victor N. Zakharov, Часть 1. Введение в подходы и алгоритмы // Sergey A. Stupnikov, Dmitriy Yu. Kovalev Статья в сети Интернет, URL: This work is devoted to description of key tasks in the http://www.ibm.com/developerworks/ru/library/os- context of building the online store information systems. recommender1/, 2013. The main objective is to identify user preferences and [3] Марманис Х., Бабенко Д. Алгоритмы their formalization through the formation of the users’ интеллектуального Интернета // СПб.-М.: behavioral profiles followed by the identification of user Символ, 2011. – 466 с. groups with similar characteristics. The main source of [4] С.А.Филиппов, В.Н.Захаров, С.А.Ступников, information about user preferences is implicitly an array Д.Ю.Ковалев Организация больших объемов of data collected about their actions when navigating данных в рекомендательных системах through the pages of online shopping. The authors поддержки жизнеобеспечения, входящих в present an approach to building a recommendation состав глобальных платформ электронной system based on collaborative filtering problem solving коммерции // XVII международная конференция using cluster analysis techniques to identify groups of «Аналитика и управление данными в областях с users with similar preferences. Advantages of the интенсивным использованием данных» solution are demonstrated on the example of test data set DAMDID/RCDL’2015. Обнинск, 2015. obtained from the current online store Thaisoap. A [5] В.А. Лексин Технология персонализации на unique identifier of the project supported by the Ministry основе выявления тематических профилей of education and science of the RF is пользователей и ресурсов Интернет // ВКР RFMEFI60414X0139. 103