IX Международная студенческая научная конференция Студенческий научный форум - 2017

В статье описана задача генерации пользовательских рекомендаций и возможные пути её решения. Работа выполнена в рамках курсового проекта по дисциплине «Machine Learning», научный руководитель – к. ф.-м. н. доцент Синева И. С.

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

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

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

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

Рис. 1. Интерфейс раздела личных лент веб-сайта Sports.ru .

Подписки (выбор пользователем интересующей темы) на теги хранятся в базе данных в формате {user_id;tag_id}, где ключом является только комбинация из двух значений. Из этих данных создадим матрицу размера , где – число уникальных user_id, – число уникальных tag_id. Элементы данной матрицы заполняются по следующему правилу:

.

Заранее стоит исключить неактивных пользователей (дата последнего визита раньше 1 июня 2016 года и менее 5 тегов в подписках) и непопулярные теги (менее 10 подписок). Таким образом, матрица имеет размер порядка .

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

Характер исходной выборки (отсутствие обучающей матрицы) вынуждает использовать обучение без учителя. Для матрицы, состоящей из элементов , где большая часть элементов равна нулю, целесообразно использовать метод бинарной кластеризации Proximus [3].

На первом шаге алгоритма проводится факторизация исходной матрицы. Факторизация – разложение некой матрицы на векторы и , такие, что (результаты данной операции изображены на рис. 2). Это возможно сделать при помощи двух следующих алгоритмов, которые показывают хорошую сходимость на больших массивах бинарных данных. Первый – дискретный – заключается в минимизации ошибки:

(1)

что эквивалентно максимизации функции

(2)

Исходные данные	Аппроксимированные данные

Рис. 2. Аппроксимация исходной матрицы

Если зафиксировать и обозначить , то , максимизирующий функцию, задаётся следующим уравнением:

(3)

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

	(4)

Глобальный максимум функций (2) и (4) не находится в одной точке, однако их поведение высоко коррелировано, поэтому можно использовать как непрерывную аппроксимацию . Зафиксировав и определив , необходимо максимизировать функцию

(5)

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

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

(6)

где – номер строки матрицы .

Видно, что факторизация (6) не даёт никакой информации об , и позже будет использована факторизация и ее рекурсивное разбиение. С другой стороны, проверяется адекватность строк при помощи вектора и критерия сходимости. Если критерий достигнут, считается, что , иначе производится рекурсивное разбиение как , так и . Критерий адекватности факторизации – нормированный радиус Хэмминга для расстояний Хэмминга. Расстояние Хэмминга определяется по формуле

(7)

где – число ненулевых значений бинарного вектора .

Тогда, имея набор бинарных векторов и вектор , можно определить радиус Хэмминга:

(8)

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

Реализация алгоритма Proximus на языке программирования Python представлена на рис. 3.

Рис. 3. Программный код алгоритма Proximus на языке Python

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

• --input-file – файл, содержащий исходную матрицу,

• --output-file – файл, содержащий матрицу принадлежности к классам,

• --algorithm – алгоритм аппроксимации матрицы (дискретный / непрерывный),

• --inits – метод инициализации исходной матрицы,

• --min-cluster-size – минимальное число кластеров на выходе.

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

.

В случае, если был указан параметр output-file, данные будут записаны в указанный файл, иначе выведутся на экран.

При помощи программы Proximus были получены персональные рекомендации, самые популярные из которых описаны в табл. 1. Можно отметить, что около 95% предложенных результатов являются релевантными. Ошибки возникают в случаях, когда подписки достаточно специфичны и их тяжело объединить в одну группу.

Таблица 1. Результаты работы программы.

Подписки пользователя	Все подписки внутри кластера	Полученные рекомендации
Спартак, Каррера, Промес, Аленичев	Спартак, Каррера, Промес, Аленичев, Попов, Ребров, Карпин	Попов, Ребров, Карпин
Зенит, СКА, Халк, Аршавин	Жулиано, Зенит, СКА, Ломбертс, Шатов, Халк, Дзюба, Аршавин	Жулиано, Ломбертс, Шатов, Дзюба
РФПЛ, трансферы, ЦСКА, Еременко	Слуцкий, РФПЛ, ЦСКА, Вагнер Лав, Еременко, Семак, трансферы	Слуцкий, Вагнер Лав, Семак

СПИСОК ЛИТЕРАТУРЫ

1. Синева И. С. Будущий интернет: сетевой подход // Фундаментальные проблемы радиоэлектронного приборостроения. – 2010. – Т. 10. – № 1-3. – С. 237-240.

2. Gorbunov J. A., Krotov L.N., Krotova E.L. Legitimate User Profiling Based on the Third Order Spline Approximation of the Initial Data Sequence // World Applied Sciences Journal 29. – 2014. – №12. – pp. 1605-1610.

3. Koyutürk M., Grama A. PROXIMUS: a framework for analyzing very high dimensional discrete-attributed datasets // KDD’03 Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. – New York.: ACM, 2013. – pp. 147-156.

 

7

 

Код для цитирования: Скопировать