Исследование и разработка алгоритмов рекомендательных систем на основе информационных моделей динамики пользовательского опыта в сетях предоставления услуг тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Деревицкий Иван Владиславович

• Деревицкий Иван Владиславович
• кандидат наук
• 2020

Оглавление диссертации кандидат наук Деревицкий Иван Владиславович

СОДЕРЖАНИЕ

Реферат

Synopsis

Введение

ГЛАВА 1. Подходы к построению рекомендательных систем в сетях предоставления услуг

1.1 Интерпретируемые алгоритмы рекомендательных систем в сетях предоставления услуг

1.2 Контентные рекомендательные системы

1.3 Коллаборативные рекомендательные системы

1.4 Экспертные рекомендательные системы

1.5 Контекстные рекомендательные системы

Выводы к главе

ГЛАВА 2. Моделирование информационных процессов в сетях предоставления услуг для задач ранжирования рекомендаций

2.1 Информационная модель сетей предоставления услуг

2.1.1 Сущности и акторы информационной модели

2.1.2 Информационные процессы в СПУ

2.1.3 Мотивационная модель выбора пользователем ТПУ

2.2 Оптимизация удовлетворенности пользователей в сети предоставления услуг на основе формализма максимального потока

2.2.1 Основные понятия и определения

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

2.2.2.1 Задача ранжирования ТПУ

2.2.2.2 Задача рекомендации ТПУ в физическом пространстве на основе формализма максимального потока

2.2.2.3 Задача оптимального размещения ТПУ

2.3 Информационные процессы на основе пользовательского опыта

2.3.1 Формализация пользовательского опыта

5

2.3.2 Классификация пользовательского опыта

2.3.3 Модель генерации пользовательского опыта

2.3.4 Процедура усвоения пользовательского опыта

2.4 Метод и алгоритм ранжирования многопараметрических рекомендаций ТПУ на основе усвоения пользовательского опыта

2.4.1 Процедура усвоения для задачи ранжирования ТПУ

2.4.2 Метод ранжирования ТПУ в СПУ на основе максимизации совокупной удовлетворенности динамических сетей

Выводы к главе

ГЛАВА 3. Платформа динамических рекомендаций точек предоставления услуг

3.1 Компонент получения данных пользовательского опыта

3.2 Компонент предфильтрации данных

3.3 Компонент усвоения пользовательского опыта

3.4 Компонент рекомендации точек предоставления услуг

Выводы к главе

ГЛАВА 4. Результаты экспериментальных исследований эффективности подхода к решению прямой и обратной задач рекомендации ТПУ на предметных примерах

4.1 Экспериментальные исследования задачи ранжирования на примере рекомендации заведений общественного питания в Санкт-Петербурге

4.1.1 Данные о системе предоставления услуг общественного питания108

4.1.2 Сравнительный анализ эффективности предложенного подхода для задачи рекомендации предприятий общественного питания

4.1.3 Реализация сервиса рекомендации заведений общественного питания в Санкт-Петербурге на основе платформы рекомендации ТПУ

4.2 Экспериментальные исследования задачи ранжирования на примере рекомендации продуктов финансовой организации

4.2.1 Данные интернет-запросов клиентов финансовой организации

4.2.2 Сравнение эффективности предложенного подхода к рекомендации ТПУ с классическими алгоритмами

4.3 Экспериментальные исследования задачи ранжирования на примере банковских отделений

4.3.1 Данные о посещениях банковских отделений

4.3.2 Решение задачи ранжирования на примере посещения банковских отделений

4.4 Экспериментальные исследования обратной задачи ранжирования - эффективного размещения ТПУ на примере расположения уличных

дефибрилляторов

Выводы к главе

ЗАКЛЮЧЕНИЕ

Заключение

Публикации автора по теме диссертации

Введение диссертации (часть автореферата) на тему «Исследование и разработка алгоритмов рекомендательных систем на основе информационных моделей динамики пользовательского опыта в сетях предоставления услуг»

Реферат

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

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

Целью диссертационной работы является повышение качества1 решения задачи ранжирования рекомендаций точек предоставления услуг (ТПУ2) в многопользовательских

1 Мерой качества являются: величина случайной ошибки определения ранга элемента, ошибки первого и второго рода при определении наилучшего элемента для конкретного клиента, а также значения агрегированной целевой функции (совокупная удовлетворенность пользователя)

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

системах поддержки принятия решений при неопределенности и изменчивости внешней среды.

Для достижения цели в ходе диссертационного исследования ставятся следующие задачи:

- разработка модели информационного процесса динамического усвоения3 пользовательского опыта, обеспечивающей оценивание функции релевантности ТПУ;

- разработка метода и алгоритма рекомендаций ТПУ на основе модели пользовательского опыта с учетом его социальной, временной и пространственной компонентов;

- разработка метода решения обратной задачи размещения ТПУ на основе данных пользовательского опыта;

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

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

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

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

Научная новизна исследования обусловлена тем, что впервые предложен рекомендательный метод и алгоритм для сетей ТПУ на основе формализма определения максимального потока на динамической сети. Он позволяет: (а) ранжировать рекомендации точек предоставления услуг, совокупно учитывая пространственно-временные и социальные характеристики пользовательских предпочтений, (б) за счет динамического усвоения пользовательского опыта обеспечивать релевантность ранжирования при

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

4 Работа выполнена в рамках совместного проекта с Наньянгским технологическим университетом (Сингапур)

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

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

Практическую значимость работы составляют:

- программная платформа динамических рекомендаций ТПУ;

- программный комплекс для автоматизированного решения задачи многокритериальной рекомендации точек интереса;

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

- программный комплекс для решения задачи размещения точек интереса.

Внедрение результатов работы. Разработанные системы внедрены в оперативную деятельность ПАО «Банк "Санкт-Петербург"», также использованы в международном проекте по размещению уличных дефибрилляторов совместно с Наньянгским технологическим университетом, г. Сингапур.

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

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

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

Соответствие паспорту специальности 05.13.17:

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

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

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

- Clustering Interest Graphs for Customer Segmentation Problems, Sixth International Conference on Social Networks Analysis, Management and Security, Гранада, 2019;

- Multiagent Context-Dependent Model of Opinion Dynamics in a Virtual Society, International Conference On Computational Science, Уси, 2018;

- Simulation of emergency care for patients with ACS in Saint Petersburg for ambulance decision making, International Conference on Computational Science, Цюрих, 2017.

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

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

Бухановский А.В. во всех работах, выполненных в соавторстве, обеспечивал постановку задач и участвовал в интерпретации результатов исследований.

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

предложенного метода для прикладных задач, а также метод решения обратной задачи -размещения ТПУ.

Данная работа выполнена при поддержке Министерства науки и высшего образования РФ, проект тематики научных исследований №075-03-2020-139/2 (2019-1339)

Заключение диссертации по теме «Теоретические основы информатики», Деревицкий Иван Владиславович

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

- разработана модель информационного процесса усвоения сущностей пользовательского опыта в системе предоставления услуг;

квадратах 200х200 метров; такие расстояния в городской среде находятся за пределами видимости и слишком велики для "ручной" транспортировки пациентов.

- на основе проведенного аналитического обзора в главе 1 сформулированы и обоснованы требования к математическому обеспечению для решения задачи рекомендации точек предоставления услуг;

- разработан адаптивный метод построения алгоритма рекомендации точек предоставления услуг интереса на основе информационных моделей динамики пользовательского опыта и задаче о максимальном потоке на динамической сети;

- экспериментально исследована работа адаптивного метода для решения задачи рекомендации ТПУ для различных наборов данных;

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

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

Список литературы диссертационного исследования кандидат наук Деревицкий Иван Владиславович, 2020 год

References

Black, J. J. (2005). International EMS Systems: United Kingdom. Resuscitation(64), 21-29.

Brailsford, S. C. (2004). Emergency and on-demand health care: modelling a large complex system. Journal of the Operational Research Society, 55(1), 34-42.

Chick, S. S. (2003). Modeling Ambulance Service Of The Austrian Red Cross. Proceedings of the 2003 Winter Simulation Conference, (pp. 1701-1706).

Gayathri, N. &. (2014). A novel technique for optimal vehicle routing. In Electronics and Communication Systems (ICECS) (pp. 1-5). IEEE.

Gendreau.M. L, (2001). A dynamic model and parallel tabu search heuristic for real-time ambulance relocation. Parallel computing, 27(12), 1641-1653.

Huang, R. K. (2010). Facility location for large-scale emergencies. Annals of Operations Research, 181(1), 271-286.

Kergosien, Y. B. (2015). A Generic and Flexible Simulation-Based Analysis Tool for EMS Management. International Journal of Production Research, 1-18.

Lopez, B. I. (2005). A multi-agent system to support ambulance coordination in time-critical patient treatment. In 7th Simposio Argentino de Intelligencia Artiflcial-ASAI2005.

Maxwell, M. S. (2010). Approximate dynamic programming for ambulance redeployment. INFORMS Journal on Computing, 22(2), 266-281.

Meinzer, N. (2014). Dynamic Emergency Ambulance Fleet Allocation and Management. Master Thesis.

Nordin, N. A. (2011). An application of the A* algorithm on the ambulance routing. Humanities, Science and Engineering (CHUSER) (pp. 855-859). IEEE.

Panahi, S. &. (2009). Dynamic shortest path in ambulance routing based on GIS. International Journal ofGeoinformatics, 5(1).

Patel, A., & Waters, N. (2012). Using Geographic Information Systems for Health Research, hi Application of Geographic Information Systems. hiTech.

ReVelle, C. (1989). Review, extension and prediction in emergency service siting models. European Journal of Operational Research, 40(1), 58-69.

Roessler, M. &. (2006). EMS systems in Germany. Resuscitation(6S), 45-49.

Rokos,I., Henry, T., Weittenhiller, B., Bjerke, C., Bates, E., & French, W. (2013). Mission: Lifeline STEMI Networks Geospatial Information Systems (GIS) Maps. Critical Pathways in Cardiology, 12(2), 43A4.

Steg, G„ James, S„ Atar, D., Badano, L„ Lundqvist, C„ Borger, M„ . . . Fox, K. (2012). ESC Guidelines for the management of acute myocardial infarction in patients presenting with ST-segment elevation. European heart journal, 33(20), 2569-2619.

World Health Organization. (2014). The 10 leading causes of death in the world, 2000 and 2011. Fact sheet N,310.