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

На правах рукописи

Бритвина Екатерина Васильевна

ИССЛЕДОВАНИЕ И РАЗРАБОТКА АЛГОРИТМОВ РЕКОМЕНДАТЕЛЬНЫХ СИСТЕМ НА ОСНОВЕ ГРАФОВЫХ МОДЕЛЕЙ ДАННЫХ

Специальность 05.13.01. - «Системный анализ, управление и обработка информации (в науке и промышленности) по техническим наукам»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 а МАП 2015

Нижний Новгород - 2015 г.

005568858

005568858

Работа выполнена на кафедре «Информатика и системы управления» Нижегородского государственного технического университета им. P.E. Алексеева

доктор технических наук, профессор, КРЫЛОВ Владимир Владимирович

Соколов Валерий Анатольевич,

доктор физико-математических наук, профессор, заведующий кафедрой «Теоретической информатики» ФГБОУ ВПО Ярославского государственного университета им. П.Г. Демидова (г. Ярославль) Шапошников Дмитрий Евгеньевич, кандидат физико-математических наук, заместитель директора по развитию Научно-исследовательского института прикладной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского

Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт программных систем им. А.К. Айламазяна Российской академии наук (ИПС им. А.К. Айламазяна РАН) г. Переславль- Залесский

Защита диссертации состоится «11» июня 2015 года в 13 часов в ауд. 1258 на заседании диссертационного совета Д212.165.05 при Нижегородском государственном техническом университете им. P.E. Алексеева по адресу: 603155, г. Нижний Новгород, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. P.E. Алексеева и сайте http://www.nntu.ru/content/aspirantura-i-doktorantura/dissertacii Автореферат разослан « SJf » CUlAuJ 2015 года.

Научный руководитель:

Официальные оппоненты:

Ученый секретарь диссертационного совета

Суркова Анна Сергеевна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Диссертационная работа посвящена разработке и исследованию алгоритмов для рекомендательных систем - программных комплексах для анализа данных о действиях пользователей. Работа является применением методов системного анализа моделирования, оптимизации, совершенствования управления и принятия решений с целью повышения эффективности функционирования систем прикладных информационных технологий с целью автоматической генерации предложений, побуждающих пользователей к новым действиям. В диссертации выделены две основные проблемы: масштабируемость и так называемый «холодный старт» -обслуживание новых пользователей, о действиях и потребностях которых практически ничего не известно. Для эффективного решения этих проблем в диссертации предложено использовать графовые модели данных о пользователях и их потенциальных рекомендациях. Задачу генерирования рекомендации предложено интерпретировать как поиск квазиоптимального решения задачи дискретной оптимизации на паре графов, а проблему холодного старта свести к генерации ребер графа в ходе интерактивного взаимодействия системы с пользователем, обеспечивая хорошие навигационные свойства для поиска на графе. Разработаны эвристические алгоритмы на основе структур графов тесного мира, обеспечивающих логарифмическую сложность поиска на больших графах. Использование графов тесного мира решает проблему масштабируемости, а разнообразие структур таких графов обеспечивает эволюционную адаптацию для решения проблемы холодного старта.

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

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

\

Актуальность работы. Одним из бурно развивающихся направлений совершенствования индустрии электронной коммерции является развертывание рекомендательных систем - инструментов автоматической генерации предложений по услугам на основе изучения персональных потребностей клиентов. Одной из первых рекомендательных систем была система Интернет-магазина Amazon. Более совершенная рекомендательная система была разработана компанией Google. В этой системе впервые был применен механизм сбора информации о пользователях с помощью cookies при посещении ими сайта поисковой системы и построение профиля каждого пользователя на основе трека его запросов. В 1992 г. в качестве основного алгоритма для рекомендательных систем был предложен метод коллаборативной фильтрации. Это позволило рекомендательной системе генерировать предложения не только на основе персонального трека запросов пользователя, но и на основе треков других пользователей из одного с ним кластера. Разработка этой системы выявила ряд проблем построения рекомендательных систем, которые потребовали разработки новых алгоритмов, специфических для этого класса систем обработки данных. Две из таких проблем продолжают привлекать внимание разработчиков. Первая из этих проблем носит название проблемы масштабируемости, а вторая - холодного старта. Наличие проблемы масштабируемости требует от алгоритмов рекомендательных систем возможность неограниченного наращивания числа, как пользователей, так и числа вариантов возможных рекомендаций. При этом наращивание не должно требовать замены в коде программы реализации алгоритмов и повторной обработки всех уже обработанных данных и допускать высокую параллельность вычислений. Проблема холодного старта заключается в необходимости обеспечения работоспособности алгоритма для генерации рекомендаций пользователям, которые впервые вошли в систему, и информация о них отсутствует или чрезвычайно бедна. Разработка алгоритмов, разрешающих эти проблемы, позволяет строить рекомендательные системы, которые являются адаптивными по отношению к росту числа пользователей и товаров (в электронной коммерции) и к объему данных, имеющихся о пользователях.

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

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

Предмет исследования. Структуры данных и алгоритмы выбора релевантных рекомендаций.

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

Для достижения поставленной цели, в работе решаются следующие научные и практические задачи.

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

2. Разработка алгоритма выбора рекомендаций в условиях холодного старта.

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

4. Проведение вычислительных экспериментов, подтверждающих работоспособность разработанных алгоритмов

5. Разработка на основе разработанных методов архитектуры системы для выбора релевантных рекомендаций (рекламных сообщений) в телекоммуникационных системах.

Положения, выносимые на защиту:

1. Модель данных в виде графов тесного мира может использоваться как самоорганизующаяся структура данных для алгоритмов рекомендательных систем.

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

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

4. Эвристический алгоритм поиска релевантных элементов на паре графов с

помощью построения метрики, индуцированной функцией релевантности.

5. Способ выбора релевантных информационных сообщений в

телекоммуникационных сетях и системы для его осуществления.

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

Научная новизна.

• Предложена и разработана новая модель данных в виде графа тесного мира для представления объектов рекомендательной системы, авторские права защищены патентами [4], [5].

• Поставлена задача генерации релевантных рекомендаций как задачи дискретной оптимизации на паре графов, позволяющая использовать эвристические алгоритмы поиска на графах М5№" - метризованного тесного мира, которая отличается от известных, основанных на матричных представлениях данных.

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

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

Практическая ценность.

Результаты исследований, полученные автором в работе (графовые модели данных и алгоритмы поиска релевантных рекомендаций), нацелены на методы и алгоритмы интеллектуальной поддержки при принятии управленческих решений в технических, экономических системах и использованы в проекте ООО «МераЛабс»

«Ads-While-Waiting», получившем поддержку ФПИ Российской Венчурной Компании, в совместных работах с компанией - оператором связи стандарта 4G «Основа Телеком» и в работепо Федеральной целевой программе Министерства образования и науки РФ в рамках ГК №14.574.21.0034 от 17.06.2014, выполняемой ФГБОУВПО НГТУ им. P.E. Алексеева, так же включены в учебный процесс кафедры «Информатики и систем управления» НГТУ им. P.E. Алексеева.

Апробация работы и внедрение результатов исследования.

Основные результаты работы представлялись на третьей Всероссийской конференции «Нелинейная динамика в когнитивных исследованиях», VI-й Всероссийской научно-практической конференции «Нечеткие системы и мягкие вычисления-2014 городе Санкт-Петербурге, а также Международной научной конференции «Информационные системы и технологии» 2012-2014гг (ИСТ-2012, ИСТ-2013, ИСТ-2014).

Публикации. По теме диссертационной работы опубликовано 10 научных работ, включая три публикации в изданиях из списка изданий, рекомендованных ВАК РФ, получены патент на изобретение и патент на полезную модель.

Структура н объем диссертации. Диссертация изложена на 99 страницах, состоит из введения, четырёх глав, заключения, списка литературы.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

коллаборативной фильтрации используется информация о поведении всех пользователей в прошлом — например, информация об их покупках или оценках. Основная проблема этого типа рекомендательных систем — «холодный старт»: отсутствие данных о недавно появившихся в системе пользователях или объектах. С увеличением количества пользователей в системе, появляется проблема масштабируемости. Также, многие системы должны моментально реагировать на онлайн запросы от всех пользователей, независимо от истории их покупок и оценок, что требует ещё большей масштабируемости. Необходимость хорошей масштабируемости проектируемых алгоритмов обусловлена тем фактом, что и число объектов выбора (размер множества предпочтений) и число субъектов выбора (размер множества клиентов, пользователей) в начальный период после развертывания системы невелик, но растет по ходу эксплуатации. Алгоритмы должны хорошо работать с ростом размеров этих множеств до очень больших значений (105-108) и не требовать модернизации достаточно долгое время. В последнем разделе главы излагается подход автора к решению проблемы холодного старта. Алгоритм должен обеспечивать формирование значений функции релевантности на основе эмпирического оценивания. Построение алгоритмов самоорганизации множеств объектов и субъектов предпочтений в ходе эволюции функции релевантности и дальнейшее ее эффективное использование на множествах больших размеров является ключевой идеей настоящей работы.

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

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

Во второй главе поставлена и решена задача построения модели пространства предпочтений. В основу модели положен тот факт, что множество сервисов Y в силу конечности может быть ассоциировано с множеством вершин графа. Тогда топология на этом множестве будет задана выбором ребер графа. Задание графа на Y может осуществляться различными способами в зависимости от требований к эффективности построенных на графе алгоритмов жадного поиска, как наиболее простого класса алгоритмов. Ключевой идеей работы является использование модели трансформирующегося, самоорганизовывающегося пространства предпочтений, в котором остается тот же носитель, то есть набор вершин графа, а топология меняется в процессе обучения. В состоянии "холодного старта", когда алгоритм находится в зоне неопределенности, т.е. для указанного клиента не определено значение функции предпочтения на сервисе, топология на Y должна удовлетворять требованию быстрого перебора всех сервисов с вызовом внешнего алгоритма оценки значения этой функции. Это означает, что граф должен иметь диаметр, существенно меньший по сравнению с его размером. Графы, которые обладают малым диаметром при "небольшом" по сравнению с полным графом числом ребер, известны как графы "тесного мира" (Small World Graphs). В работе рассмотрены графы, которые называют в литературе графы

Барабаши-Альберта или безмасштабные (Scale Free). Для таких графов распределение степени вершины к подчиняется степенному закону, а диаметр - пропорционален логарифму размера графа N. Произведена оценка числа шагов, за которое может быть в среднем достигнута любая вершина графа тесного мира при осуществлении на каждом шаге выбора одного из соседей вершины. Показано, что среднее число шагов для достижения любой вершины из любой начальной будет даваться следующей оценкой(С-некоторая константа).

Л' .V

М = D I = C1*N * COnlNW

к=х k=i

Таким образом, показано, что при наделении множества поиска топологией ScaleFree графа тесного мира со степенным распределением степени вершины процедура поиска в условиях "холодного старта" будет весьма эффективной по числу шагов для решения задачи дискретной оптимизации эвристическим перебором. В некоторых приложениях требуется накладывать дополнительные ограничения на возможные топологии пространства поиска. В работе найдена подходящая модель для типичного случая в виде так называемых графов Кэйли, относящихся к фрактальным графам - Limited Degree Fractal (LDF). Эти графы могут позволить ограничить число шагов выбора на каждом шаге движения, однако для значительной части вершин графа степень вершины окажется равной единице, что потребует реверсного движения при осуществлении поиска. Были сконструированы графы, которые обладают свойством тесного мира, т.е. логарифмической зависимостью диаметра ог размера, ограниченной степенью вершины и минимальной дисперсией степени вершины. Для большого числа вершин графические изображения становятся малопригодными и описание графа матрицей смежности или таблицей соседей становится более приемлемым для практических целей. В работе рассматриваются возможности построения и иных эффективных топологий на множестве сервисов в условиях нахождения аргументов в зоне неопределенности. Показано, как может быть сконструирован граф пространства предпочтений для случая, когда известны все (или почти все) значения матрицы релевантности (предпочтений). Элементами матрицы являются числа, принадлежащие отрезку [0,1] и имеющие смысл уровня предпочтения конкретного сервиса конкретным клиентом или релевантности каждого сервиса для каждого клиента. Каждый ¡-й столбец этой матрицы можно рассматривать как координатный вектор соответствующего этому столбцу сервиса из Y. При таком рассмотрении множество Y

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

При выборе метрики ¿/для любой пары точек Vi,i'i е расстояние Pit через соответствующие элементы матрицы предпочтений определяется следующим образом:

гг.

рц ~ Xhti-^J

ь=1

Для конструирования графа, с топологией, согласованной с введенной метрикой воспользуемся методом, называемым построением графов метризованного тесного мира MSW (Metrized Small World). Для этих графов топологическое (число ребер) является согласованным с метрическим расстоянием между вершинами и в среднем оценивается логарифмической величиной от размера графа, числа его вершин. При этом существует простой алгоритм жадного поиска, приводящий в среднем за логарифмическое число шагов к отысканию ближайших по метрике вершин. В работе предложено, начиная с произвольной начальной точки на Y собирать граф MSW, в котором ближайшим в топологии графа (число ребер в пути) вершинам соответствуют точки с минимальным расстоянием. Следует заметить, что максимальное число ближайших соседей для каждой из вершин, оказывается равным внутренней размерности пространства из столбцов матрицы предпочтений, которая, как правило, оказывается существенно меньше т.

Третий случай конструирования топологии пространства предпочтений представляет собой промежуточный между рассмотренными выше: частично определенная матрица предпочтений (релевантности).

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

Р\ 1 * Аз Р|4 Рг\ Р22 * Р2А Ри Рп Рзз />34

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

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

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

Рассмотрены три варианта конструирования топологий, соответствующие случаю холодного старта, известной матрицы релевантности (предпочтений) и недоопределенной матрицы.

Разработан жадный алгоритм поиска решения на сконструированных графах (с сконструированной топологией).

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

*е 1 лАек'

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

Г И ги - rtM r2i i"2i - rzM

r.v, r.v, _ rNM Если значения элементов матрицы релевантности равны либо 0. либо 1, то говорят, что задана булева релевантность, то есть для любой пары запрос-ответ о их релевантности можно утверждать, только да или нет.Более сложный случай определяет возможностью оценивать уровень релевантности. В этом случае можно ввести функцию релевантности rel:

X X У -» [О, ll; 0 < ге1(х^у'у) < 1

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

В этом случае задача переходит в категорию задач дискретной оптимизации. Сведем задачу максимизации релевантности к задаче дискретного программирования. Вместо

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

d-.X ) = -!n(reíí0r7;j у,))

£?<*,у):Я"хУ-* (0,со)-| Задача: найти алгоритм отыскания максимально релевантной точки у. е Y;d(x. у.) = minу)

."с Г

В изложенной постановке задача относится к классу трудноразрешимых задач дискретной оптимизации. Точные методы для высокоразмерных задач в этом случае приводят к недопустимо большому числу вычислений. Поэтому в работе предложены и разработаны эвристические приближенные алгоритмы. Основной идеей главы является предложение свести задачу на поиск релевантного ответа из Y на запрос из X при известной функции релевантности reí ( . , . ) к нескольким задачам локального поиска на множестве Y. В основу метода положено оснащение этого множества графом со специальными свойствами, известными как MSW (MetrizedSmallWorld) для поиска локального минимума. Классический подход применения метода локальной оптимизации сводится к наделению множества Y любой произвольной метрикой, назначением начальной точки и радиуса окрестности локального поиска. Алгоритм поиска минимума в этом случае сводится к поиску локального минимума в выбранной окрестности и перехода к новой начальной точке, в качестве которой назначается найденная на предыдущем локальном шаге точка минимума. В работе предлагается решение, на основе разработанного во второй главе алгоритма эвристического поиска на MSW графе, сконструированном на множестве Y. Однако топологию графа предлагается построить на основе внутреннего расстояния индуцированного отношением релевантности. Основная идея подхода состоит в том, что в множестве X некоторым образом выбирается подмножество из М "представительных" элементов, далее называемый базисом в X. Обозначим это подмножество

Хв - fot,,-Хт)

Определим для каждой точки из Y расстояния релевантности

ук е y.d(yk.xBl) = ditt. Vi = l.M

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

сетка размерности М. Теперь определим функцию внутреннего расстояния на У с помощью этой координатной системы, задавая ее значения как:

При правильном выборе множества Хв введенная функция расстояния удовлетворит всем аксиомам метрики. Введенная таким образом функция расстояния, индуцированная исходным отношением релевантности, используется для построения необходимого для эффективного поиска решений графа М8\У. На рис.1 приведена иллюстрация построения координатного пространства и графа на нем.

В работе обсуждается выбор множества Хв. В главе проиллюстрирована методику выбора базиса и результаты построения графа на У на упрошенном

примере работы системы релевантного выбора.

Рис. 1. Построение координатного пространства на Ус помощью базисного подмножества в X.

Для нахождения значения функции расстояния релевантности между элементами множеств X и У была использовать пробная модельная функция:

Эта функция была сконструирована так, чтобы отразить типичные особенности функций расстояния релевантности. Располагая координатами точек в У можно построить М5Ш граф.

м

еНхь.уп~> = Iк' - 2кп + и* - 14бк - 146и +

/

*

•.....................

Рис. 2. Фрагмент М8\У графа для примера

Используя программную реализацию метода оптимизации на MSW графах Metrized Small World Prototype, были построены таблицы, иллюстрирующие решения задач эвристической оптимизации. Алгоритм находит кандидатов на роль максимально релевантного ответа, среди которых всегда находится точное значение, обеспечивающее нулевое значение функции расстояния релевантности, если такой ответ существует.

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

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

В первом параграфе четвертой главы приводится описание имплементации предложенных алгоритмов в сервисы быстро растущего рынка телевизоров, имеющих прямой выход в Интернет (SmartTV). Многие поставщики сервисов для просмотра видео и аудиозаписей применяют изощренные методы выработки рекомендаций (например, Netflix), основанные на коллаборативной фильтрации. В работе сконструированы базовые алгоритмы навигации в множестве ТВ-каналов. Значением функции предпочтения будем считать среднее время, проведенное клиентом на канале

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

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

109. \5"

\ 1М>11"

V 2„

• 12,

Рнс.З. \1S\V граф каналов построенный, по предпочтениям клиента

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

предложенный и описанный в главе три. В общем случае разработанные способ и система предназначены для формирования и передачи (доставки) целевого рекламного контента (рекламного сообщения) с учетом предполагаемых потребительских предпочтений абонентов или любой иной информации оператором определенному абоненту и/или определенной группе абонентов инфокоммуникативных сетей во время запроса мульдимедийного сервиса, например, голосовой и/нли видео связи, ресурсов IP-TV, обмена текстовыми сообщениями. Таким образом, наиболее востребованным техническое решение будет в мобильной и фиксированной телефонной и видеосвязях сетей поколений NGN, 3G, LTE, в компьютерных системах мультимедийной связи Skype, 00V00, при обработке вызовов в call center.B работе приводится разработанная функциональная схема такой системы (рис.4).

Рис.4. Функциональная схема системы встраивания сообщений в процесс исходящего соединения в мультимедийных телекоммуникационных сетях.

Рекомендательная система реализуется в исполняемом алгоритмена сервере SCSC, используя данные об абонентах и рекламные сообщения, хранящиеся в соответствующих БД (блоки 116 и 17). Экспериментальная версия системы была развернута в ходе совместных работ с компанией НСС в телекоммуникационной сети UMTS и начаты работы по реализации экспериментальной системы в сети 4GLTE компании «Основа Телеком». Проект создания и развертывания системы такого типа

прошел экспертизу Фонда посевных инвестиций Российской венчурной компании и

получил рекомендации на получение инвестиций.

В заключении диссертации сформулированы основные результаты работы.

В приложениях диссертации приведены копии документов, подтверждающие

практическое использование результатов исследований.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В работе получены следующие основные результаты:

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

2. Предложена модель представления данных для объектов рекомендательных систем в виде специальных типов графов тесного мира.

3. Разработано решение проблемы холодного старта как построения эффективного алгоритма поиска в пространстве предпочтений.

4. Разработан алгоритм эффективного конструирования пространства предпочтений путем адаптивного перестроения ребер графа рекомендаций.

5. Предложена постановка задачи генерации релевантных рекомендаций как дискретной оптимизации на паре пространств графов.

6. Предложен метод и разработан алгоритм получения метрики, индуцированной функцией релевантности для конструирования графа М5\У(метризованного тесного мира) в качестве пространства предпочтений или пространства пользователей.

7. Разработан эвристический алгоритм генерирования рекомендаций на основе поискового процесса на графе МБУ/.

8. Разработан способ генерации релевантных рекомендаций (рекламных сообщений) посредством инфокоммуникативных сетей и система для его осуществления, запатентованные в РФ (патенты РФ К и 2461879 от 20.09.2012 и 1Ш 112466 от 10.01.2012).

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ в ведущих рецензируемых научных журналах и изданиях из перечня ВАК министерства образования и науки РФ и приравненных к ним:

1. Бритвина, Е.В. Алгоритм поиска максимально релевантных элементов на основе метризованного графа тесного мира [Текст] / Е.В. Бритвина// Вестник Нижегородского университета им. Н.И. Лобачевского № 4, период, науч. издание. - Н. Новгород:, ННГУ.-2014.-№4,- С. 178-181.

2. Бритвина, Е.В. Алгоритм самоорганизации пространства поиска в больших системах с нечетким выбором / Е.В. Бритвина // Электронный научный журнал «Современные проблемы науки и образования», ISSN 2070-7428, №6,2014. - Режим доступа: http://www.science-education.ru/120-17176

3. Бритвина, Е.В. Сегментирование рекомендательной системы с использованием метода организации соединения клиент-сервер, основанного на программно-конфигурируемых сетях и применении протокола с быстрым перескоком IP адреса/ Е.В. Бритвина // Электронный научный журнал «Современные проблемы науки и образования», ISSN 2070-7428, №6, 2014. - Режим доступа: http://www.science-education.ru/120-16875

Патенты:

4. Пономарев Д.М., Крылов В.В., Бритвина Е.В. Система доставки целевой рекламы и/или информации абоненту посредством инфокоммуникативных сетей. Патент на полезную модель RU 112466, опубликовано 10.01.2012.

5. Пономарев Д.М., Крылов В.В., Бритвина Е.В. Система доставки целевой рекламы и/или информации абоненту посредством инфокоммуникативных сетей и система для его осуществления. Патент на изобретение RU 2461879, опубликовано 20.09.2012.

в прочих научных журналах и изданиях:

6. Бритвина, Е.В. Самоорганизация пространства поиска в больших системах с нечетким выбором/ Е.В. Бритвина, В.В. Крылов// VI Всероссийская научно-практическая конференция «Нечеткие системы и мягкие вычисления-2014», Санкт-Петербург, 2014 г.

7. Бритвина, Е.В. Самоорганизация пространства поиска в больших системах с нечетким выбором/ Е.В. Бритвина, В.В. Крылов, Ю.А. Мальков// Труды Ш Всероссийской конференции «Нелинейная динамика в когнитивных исследованиях», ИПФ РАН, Нижний Новгород, 2013 с. 20-21.

8. Бритвина Е.В., Крылов B.B. Графовые модели данных и алгоритмы для рекомендательных систем. - Saarbrucken, Deutschland: LAP LAMBERT Academic Publishing, 2015, 86 c.

9. Бритвина E.B. Крылов В.В., Мальков Ю.А. Алгоритм максимизации релевантности, использующий графовые модели данных. // Труды НГТУ №2,2013- с.75-83

10. Бритвина, Е.В. Анализ производительности поисковой системы контента реального времени/ Е.В. Бритвина, В.В. Крылов, Д.О. Орел// Сборник трудов международной конференции ИС'Г-2009, Н. Новгород, НГТУ, 2009

Лнчнын вклад автора. Все основные положения диссертации разработаны автором. В работах, написанных в соавторстве, автору принадлежат разработка моделей данных и алгоритмов поиска [1,5,6,7], разработка функциональной архитектуры и базового алгоритма системы [3,4].

Подписано в печать 27.04.15. Формат 60 х 84 '/16. Бумага офсетная. Печать трафаретная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 300.

Нижегородский государственный технический университет им. P.E. Алексеева. Типография НГТУ. 603950, Нижний Новгород, ул. Минина, 24.