Исследование и разработка алгоритмов рекомендательных систем на основе графовых моделей данных

• Автор: Бритвина, Екатерина Васильевна
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Нижний Новгород
• Количество страниц: 92 с. : ил.

ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. АЛГОРИТМЫ ПОСТРОЕНИЯ РЕКОМЕНДАТЕЛЬНЫХ СИСТЕМЫ И ИХ ПРИЛОЖЕНИЯ
1.1 Что такое рекомендательные системы
1.2 Основные алгоритмы рекомендательных систем
1.3 Проблемы масштабируемости
1.4 Проблемы «холодного старта»
1.5 Некоторые известные рекомендательные системы
1.6 Замечания об оценивание качества рекомендательных систем
1.7 Основная идея разработанного подхода
ВЫВОДЫ ПО ГЛАВЕ
ГЛАВА 2. ГРАФОВЫЕ МОДЕЛИ ПРОСТРАНСТВА ПРЕДПОЧТЕНИЙ И РЕАЛИЗАЦИЯ АЛГОРИТМА ПОИСКА
2.1. Основные понятия навигации в пространствах с расстоянием и топологией
2.2. Модель пространства предпочтений и постановка задачи
2.2.1 Графовая модель пространства предпочтений с полностью неизвестной матрицей предпочтений («холодный старт»)
2.2.2 Графовая модель пространства сервисов с полностью известной матрицей предпочтений
2.2.3 Графовая модель пространства предпочтений с частично известной матрицей предпочтений
2.3. Алгоритм поиска максимальных элементов на графе предпочтений
2.4. Параллельная реализация поиска максимальных элементов на графе предпочтений
ВЫВОДЫ ПО ГЛАВЕ
ГЛАВА 3. АЛГОРИТМЫ ПОИСКА МАКСИМАЛЬНО РЕЛЕВАНТНЫХ ЭЛЕМЕНТОВ НА ГРАФАХ
3.1. Метрическое отношение релевантности и его свойства
3.2. Постановка задачи поиска максимально релевантных элементов
3.3. Решение задачи релевантности методом локальной дискретной оптимизации со случайным поиском на графах

3.4. Построение функции внутреннего расстояния, индуцированного отношением релевантности
3.5. Численные эксперименты, по анализу работы системы релевантного выбора
Выводы по Главе
ГЛАВА 4. ПРИЛОЖЕНИЯ РАЗРАБОТАННЫХ АЛГОРИТМОВ В РЕКОМЕНДАТЕЛЬНЫХ СИСТЕМАХ
4.1 Самообучающийся интеллектуальный пульт управления телевизионным приемником БшаЧТУ
4.4 Защита 1Р подсетей от несанкционированного доступа и ГЮоБ атак методом псевдослучайной смены сетевых адресов
ВЫВОДЫ ПО ГЛАВЕ
ЗАКЛЮЧЕНИЕ
СПИСОК ЛИТЕРАТУРЫ
Приложение

ВВЕДЕНИЕ
Актуальность работы. Одним из бурно развивающихся направлений совершенствования индустрии электронной коммерции является развертывание рекомендательных систем - инструментов автоматической генерации предложений по услугам на основе изучения персональных потребностей клиентов. Одними из первых рекомендательных систем были система Интернет-магазина Amazon и система компании Google. В 1992 г. в качестве основного алгоритма для рекомендательных систем был предложен метод коллаборативной фильтрации. Он основан на использовании в рекомендательной системе информации о доступных треках всех пользователей. Этот метод позволил решить задачу достаточно эффективно, оказался весьма совершенным и в настоящее время улучшение показателя качества рекомендательной системы на 10% оценивается в конкурсе Netflix Prize в 1 миллион долларов.
Анализ публикаций показывает, что несмотря на это остается ряд принципиальных проблем построения рекомендательных систем, которые требуют разработки новых алгоритмов, специфических для этого класса систем обработки данных. Первая из этих проблем носит название проблемы масштабируемости, а вторая - «холодного старта». Наличие проблемы масштабируемости требует от алгоритмов рекомендательных систем возможность неограниченного наращивания числа как пользователей, так и числа вариантов возможных рекомендаций. При этом наращивание не должно требовать замены в коде программы реализации алгоритмов и повторной обработки всех уже обработанных данных и допускать высокую параллельность вычислений. Проблема «холодного старта» заключается в необходимости обеспечения работоспособности алгоритма для генерации рекомендаций пользователям, которые впервые вошли в систему, и

2.2.2 Графовая модель пространства сервисов с полностью известной матрицей предпочтений.
Сформулируем задачу построения окрестности произвольно выбранной точки в множестве Y для случая, когда все значения матрицы предпочтения известны. В этом случае эта матрица представляет собой числовую таблицу, число строк в которой равно числу элементов в множестве клиентов X, а число столбцов - число элементов множества объектов Y.
Каждый і-й столбец этой матрицы можно рассматривать как координатный вектор соответствующего этому столбцу объекта из Y. При таком рассмотрении множество Y оказывается погруженным в координатное пространством размерности, равной числу элементов m в множестве клиентов X. В координатном пространстве можно ввести различные метрики, которые могут быть использованы для построения графа на Y. Итак, ключевым моментом для построения окрестностей точек из множества сервисов в случае, когда известны значения функции предпочтений для всех клиентов, является рассмотрение каждого сервиса как точки, для которой известны координаты. В качестве координат служат значения функции предпочтения со стороны всех клиентов.
Выберем в качестве метрики известную метрику Ы. То есть для любой пары точек У[У;- Є Y определим расстояние р через соответствующие элементы матрицы предпочтений следующим образом

Для конструирования графа, с топологией, согласованной с введенной метрикой воспользуемся разработанным в [15,16,17] методом, названным построением графов метризованного тесного мира MSW (Metrized Small World). Как показано в этих работах, если на дискретном множестве существует функция расстояния, то на нем может быть построен граф, обладающий свойствами тесного мира (MSW граф). То есть расстояние между