Научные труды

Источник: Сборник материалов журнала «Известия Тульского Государственного Университета. Технические науки». — 2024. — № 5. — С. 157-162.

УДК 004.89

DOI: 10.24412/2071-6168-2024-5-157-158

ОПТИМИЗАЦИЯ ИЕРАРХИЧЕСКОЙ КЛАСТЕРИЗАЦИИ ПРИ РЕАЛИЗАЦИИ РЕКОМЕНДАТЕЛЬНЫХ СИСТЕМ

К.А. Андреева, М.Е. Коржова, А.И. Барсуков

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

Ключевые слова: набор данных, иерархическая кластеризация, совместная фильтрация, «холодный старт», рекомендательная система, анализ данных, подготовка данных.

Введение

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

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

Формально, задачу нахождения рекомендации можно представить в виде математической записи:

∀ u ∈ U, s'_u = argmax_{s ∈ S} h(u, s) (1)

где U – множество пользователей; S – множество объектов, которые могут быть рекомендованы пользователю; h – функция, определяющая, насколько некоторый объект s удовлетворяет некоторого пользователя u. Таким образом, необходимо выбрать такой объект s’, который принадлежит множеству объектов S, и при котором значение удовлетворенности для каждого пользователя u ∈ U максимально.

Существует несколько типов рекомендательных систем, включая коллаборативную фильтрацию, контентную фильтрацию и гибридные системы, которые сочетают в себе оба подхода. Коллаборативная фильтрация основана на сходстве между пользователями и их историей взаимодействия с платформой. Контентная фильтрация основана на сходстве между элементами, которые пользователь рассматривает, с элементами, которые он предпочитает [7],[8],[9],[10].

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

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

Проблема холодного старта рекомендательных систем заключается в том, что при отсутствии достаточного количества данных о предпочтениях пользователей и характеристиках товаров система не может сделать точных рекомендаций. Это может произойти, например, при запуске новой системы, при привлечении новых пользователей или при добавлении новых товаров в каталог. Для решения проблемы холодного старта можно использовать методы генерации баз псевдо-данных. Эти данные создаются с помощью алгоритмов и моделей, которые имитируют поведение реальных пользователей и товаров. Затем эти псевдо-данные могут быть использованы для обучения рекомендательных моделей. Существуют различные способы генерации баз псевдо-данных [11],[12].

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

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

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

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

Важной проблемой при анализе данных является их разреженность, что сильно влияет на производительность рекомендательных систем, этот факт может снизить вероятность нахождения пользователей (или объектов) со схожими оценками. Эта проблема возникает вследствие того, что рекомендательные системы обычно работают с огромным количеством объектов и пользователей. Например, конкретный пользователь не сможет прочитать и оценить все новинки литературы [13],[14],[15].

Особенности сбора и подготовки данных

При построении рекомендательных систем необходимо учитывать следующие особенности:

1. Задача: необходимо конкретно определить задачу, которую должна решать рекомендательная система. Например, в электронной коммерции это может быть увеличение продаж, в социальных сетях – улучшение пользовательского опыта, в музыкальных сервисах – увеличение времени прослушивания и т.д.
2. Контекст: рекомендации могут зависеть от контекста, в котором они предоставляются. Например, в электронной коммерции рекомендации могут зависеть от местоположения пользователя, времени суток и т.д.
3. Персонализация: рекомендации должны быть персонализированными и учитывать предпочтения пользователя. Для этого необходимо анализировать историю его покупок, просмотров, оценок, месторасположения и другой личной информации.
4. Конфиденциальность и надежность: необходимо обеспечить защиту конфиденциальности пользователей и устойчивость алгоритмов к манипуляциям и искажению данных. Также необходимо обеспечить надежность системы и ее устойчивость к сбоям.
5. Интерфейс: интерфейс рекомендательной системы должен быть понятным и удобным для пользователя. Рекомендации должны быть легко доступны и понятны, чтобы пользователь мог быстро найти интересующий его контент.

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

Источники данных для обучения

При разработке РС программисты часто сталкиваются с проблемой недостатка обучающего набора данных. Исходя из анализа открытых источников в Интернете, были определены следующие источники для обучения:

1. MovieLens 25M Dataset – набор рейтинговых данных сайта MovieLens. Данные описывают пятизвездочный рейтинг фильмов и действия с тегами по более чем 60 тысячам фильмов от 1,5 миллионов пользователей с 1995 по 2019 годы.
2. Netflix Prize – набор данных временных рядов с рейтингами примерно 100 миллионов фильмов. Более 480000 пользователей имеют уникальный идентификатор.
3. Book-Crossing – содержит набор данных с рейтингами около 300 тысяч книг и обезличенные демографические данные о читателях.
4. Amazon Review Data – содержит набор обзоров, рейтингов и данных продуктов и просмотры ссылок.
5. Yahoo! Music User Ratings – набор данных компании Yahoo! Music о предпочтениях пользователей к музыке.
6. LastFM – содержит информацию о социальных сетях, тегах и прослушивании музыкальных исполнителей от 2 тысяч пользователей.
7. Social Network Influencer – набор данных компании Peerindex, включающий парные предпочтения пользователей и функции активности в Twitter.
8. Steam Video Games – набор данных о действиях пользователей и их характеристиках от хостинга Gaming Steam.

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

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

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

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

На начальных этапах рекомендательные системы могут столкнуться с проблемой холодного старта, когда у новых пользователей или объектов нет достаточного количества данных. Это требует дополнительных стратегий, таких как контентный анализ или рекомендации на основе популярности.

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

Таким образом, сбор и подготовка данных включает обработку данных, обновление данных и другие этапы, требующие понимания предметной области, навыков обработки данных и инженерии функций [16],[17],[18].

Методы исследования

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

1. Идентификация и обработка пропущенных значений: удаление записей или заполнение средним/часто встречающимся значением.
2. Преобразование категориальных переменных в числовые значения (One-Hot Encoding, Label Encoding, Target Encoding).
3. Масштабирование числовых переменных при различных диапазонах или единицах измерения (стандартизация или нормализация).
4. Обработка выбросов: удаление или замена на типовые значения.
5. Создание новых признаков для моделирования или анализа (комбинирование, производные переменные).
6. Нормализация данных для обеспечения согласованности и сравнимости.
7. Визуализация и исследовательский анализ данных для понимания распределения переменных и выявления аномалий.

Так как компания ОАО «РЖД» не предоставляет данные клиентов в открытом доступе, обучение системы будет проводиться на тестовых сгенерированных данных.

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

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

Применение иерархической кластеризации

Иерархическая кластеризация является методом предобработки данных перед применением совместной фильтрации (Collaborative Filtering). Она помогает разбить исходные данные на группы (кластеры) на основе их схожести. Каждый объект данных начинается в отдельном кластере, затем происходит последовательное объединение близких кластеров до одного кластера.

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

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

Иерархическая кластеризация относится к агломеративным алгоритмам и результатом является построение дерева вложения кластеров (дендрограммы), начиная снизу-вверх от мелких кластеров и восходя ко все более крупным. Пример такого дерева показан на рисунке 2.

Поиск по дереву осуществляется в противоположном направлении сверху-вниз, последовательным выбором наиболее близких центров кластеров. Выигрыш в скорости поиска зависит от количества иерархических уровней. Например, при пяти уровнях кластеризации с разветвлением на три ветви на каждом уровне и 1000 записей в каждом последнем кластере, общее число записей N = 1000 * 3 * 3 * 3 * 3 * 3 = 243000. При прямой фильтрации нужно произвести 243000 сравнений, а при спуске по дереву кластеризации — всего 1000 + 3 * 5 = 1015 сравнений, что демонстрирует значительный выигрыш в скорости.

Заключение

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

Список литературы

1. Андреева К.А., Барсуков А.И., Коржова М.Е. Рекомендательные системы и методы машинного обучения. – М.: Наука, 2022. – 312 с.
2. Resnick P., Varian H. R. Recommender systems. – Commun. ACM, 1997. – Vol. 40, No. 3. – P. 56–58.
3. Ricci F., Rokach L., Shapira B. Recommender Systems Handbook. – Springer, 2011. – 728 p.
4. Herlocker J.L., Konstan J.A., Terveen L.G., Riedl J.T. Evaluating collaborative filtering recommender systems. – ACM Trans. Inf. Syst., 2004. – Vol. 22, No. 1. – P. 5–53.
5. Su X., Khoshgoftaar T.M. A survey of collaborative filtering techniques. – Advances in Artificial Intelligence, 2009. – P. 1–19.
6. Adomavicius G., Tuzhilin A. Toward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions. – IEEE Trans. Knowl. Data Eng., 2005. – Vol. 17, No. 6. – P. 734–749.
7. Shani G., Gunawardana A. Evaluating recommendation systems. – Recommender Systems Handbook, 2011. – P. 257–297.
8. Koren Y., Bell R., Volinsky C. Matrix factorization techniques for recommender systems. – IEEE Computer, 2009. – Vol. 42, No. 8. – P. 30–37.
9. Friedman J., Hastie T., Tibshirani R. The Elements of Statistical Learning. – Springer, 2001. – 536 p.
10. Shalev-Shwartz S., Ben-David S. Understanding Machine Learning: From Theory to Algorithms. – Cambridge University Press, 2014. – 504 p.
11. Bobadilla J., Ortega F., Hernando A., Gutiérrez A. Recommender systems survey. – Knowledge-Based Systems, 2013. – Vol. 46. – P. 109–132.
12. Lops P., Gemmis M. de, Semeraro G. Content-based Recommender Systems: State of the Art and Trends. – Recommender Systems Handbook, 2011. – P. 73–105.
13. Su X., Khoshgoftaar T.M. A survey of collaborative filtering techniques. – Advances in Artificial Intelligence, 2009. – P. 1–19.
14. Patel M., Doshi N. Cold start problem in recommender systems: A review. – International Journal of Computer Applications, 2016. – Vol. 139, No. 2. – P. 1–4.
15. Jannach D., Zanker M., Felfernig A., Friedrich G. Recommender Systems: An Introduction. – Cambridge University Press, 2010. – 365 p.
16. Hu Y., Koren Y., Volinsky C. Collaborative filtering for implicit feedback datasets. – 2008. – P. 263–272.
17. He X., Liao L., Zhang H., Nie L., Hu X., Chua T. Neural collaborative filtering. – Proceedings of the 26th International Conference on World Wide Web, 2017. – P. 173–182.
18. Jiang H., Cui B., Zhang C. Social recommendation: a review. – International Journal of Machine Learning and Cybernetics, 2017. – Vol. 8, No. 4. – P. 537–556.