Бизнес-модель развития цифровых издательств основана на увеличении их посещаемости. Поэтому актуальна задача удержания старых пользователей и привлечения новых. Сейчас недостаточно только производить контент, очень важно его правильно предлагать и показывать потребителю ранее неизвестные ему варианты, которые его, возможно, смогут заинтересовать.
Профилирование (в информационной науке) включает в себя сбор данных об активности посетителей интернет-ресурсов, которые в дальнейшем будут анализироваться с целью построения модели персонализированных рекомендаций [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)
Исходные данные |
Аппроксимированные данные |
|
Если зафиксировать и обозначить , то , максимизирующий функцию, задаётся следующим уравнением:
(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. Результаты работы программы.
Подписки пользователя |
Все подписки внутри кластера |
Полученные рекомендации |
Спартак, Каррера, Промес, Аленичев |
Спартак, Каррера, Промес, Аленичев, Попов, Ребров, Карпин |
Попов, Ребров, Карпин |
Зенит, СКА, Халк, Аршавин |
Жулиано, Зенит, СКА, Ломбертс, Шатов, Халк, Дзюба, Аршавин |
Жулиано, Ломбертс, Шатов, Дзюба |
РФПЛ, трансферы, ЦСКА, Еременко |
Слуцкий, РФПЛ, ЦСКА, Вагнер Лав, Еременко, Семак, трансферы |
Слуцкий, Вагнер Лав, Семак |
СПИСОК ЛИТЕРАТУРЫ
Синева И. С. Будущий интернет: сетевой подход // Фундаментальные проблемы радиоэлектронного приборостроения. – 2010. – Т. 10. – № 1-3. – С. 237-240.
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.
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