Всем привет! Меня зовут Александра Зенченко, я ведущий инженер-программист в EPAM. Я разрабатываю решения, которые помогают нашим клиентам повысить эффективность работы и в основном включают в себя часть машинного обучения.
В своем последнем проекте я работал над созданием системы рекомендаций в сфере логистики.
Я хочу поделиться своим опытом и рассказать, как с помощью алгоритмов помочь перевезти груз из Мюнхена в Женеву.
Несколько слов о рекомендательных системах
Наверняка каждый с ними встречался не раз.Рекомендательные системы — это программы и сервисы, которые пытаются предсказать, что конкретному пользователю может быть интересно/нужно/полезно, и показать это ему.
«Вам нравятся эти кроссовки? Вам также может понадобиться ветровка, пульсометр и еще 15 спортивных вещей».
.
В последние годы бренды очень активно внедряют в свою работу рекомендательные системы, поскольку от такого решения «выигрывает» и продавец, и покупатель.
Потребители получают инструмент, который помогает им в короткие сроки сделать выбор из бесконечного разнообразия товаров и услуг, а у бизнеса растут продажи и аудитория.
Что нам дано?
Я работал над проектом для крупной глобальной компании, которая предоставляет своим клиентам SaaS-решение для грузовой биржи или платформу грузовой биржи.Звучит непонятно, но что происходит на самом деле: с одной стороны, на платформе регистрируются пользователи, у которых есть груз и его нужно куда-то отправить.
Они размещают запрос по типу «Есть партия декоративной косметики, которую нужно завтра доставить из Амстердама в Антверпен» и ждем ответа.
С другой стороны, у нас есть люди или компании с грузовиками – грузовыми перевозчиками.
Допустим, они уже выполнили свой стандартный еженедельный рейс с доставкой йогуртов из Парижа в Брюссель.
Им нужно вернуться и, чтобы не ехать с пустым грузовиком, найти какой-нибудь груз для перевозки на обратном пути.
Для этого грузоперевозчики заходят на площадку моего клиента и производят поиск, указывая направление и, возможно, тип груза (или груза), подходящего для фуры.
Система собирает заявки от грузоотправителей и показывает их грузоперевозчикам.
В таких платформах важен баланс спроса и предложения.
Здесь спросом пользуются грузы от грузоперевозчиков и машины от грузоотправителей, а предложение наоборот: автомобили от перевозчиков и товары от компаний.
Баланс довольно сложно поддерживать по ряду причин, например:
- Закрытые связи между грузоперевозчиком и клиентом.
Когда водитель часто работает только с определенным клиентом, это не очень хорошо отражается на платформе.
Если грузоотправитель уйдет с рынка, сервис может потерять и грузоперевозчика, поскольку он станет клиентом другой логистической компании.
- Наличие грузов, которые никто не хочет перевозить.
Это происходит, когда небольшие компании размещают заявки на перевозки, а затем они не обновляются и, соответственно, быстро перестают быть активными.
Это могло бы отпугнуть целевую аудиторию от перехода на конкурентный сервис и показать грузоотправителям, что подходящие заказы можно найти не только у тех компаний, с которыми они привыкли работать.
С учетом всех пожеланий стоял передо мной задача: разработать систему рекомендаций, которая сразу после входа на платформу будет показывать доступных на данный момент операторов связи соответствующий груз и угадайте, что они хотят перевезти и куда.
Эту систему предполагалось интегрировать в уже существующую грузовую биржевую платформу.
Как мы будем «угадывать»?
Наша система рекомендаций, как и другие, работает путем анализа пользовательских данных.И есть несколько источников, которыми можно оперировать:
- Во-первых, открытая информация о заявках на грузоперевозки.
- Во-вторых, платформа предоставляет данные о перевозчике.
Когда пользователь заключает договор с нашими клиентами, он может указать, сколько у него грузовиков и какого типа.
Но, к сожалению, после этого эти данные не обновляются.
И единственное, на что мы можем положиться – это на страну грузоперевозчика, поскольку она, скорее всего, не изменится.
- В-третьих, система сохраняет историю поисков пользователей за несколько лет: как самые последние запросы, так и запросы годичной давности.
Поэтому мы решили сосредоточиться на выявлении закономерностей или шаблонов, по которым пользователь ищет товары для перевозки.
То есть мы не рекомендуем груз, а подбираем направление , наиболее подходящий на сегодняшний день для этого пользователя.
И мы найдем груз, используя стандартный поисковый механизм.
Как правило, популярные поисковые запросы основаны на географической информации и дополнительных параметрах, таких как тип грузовика или перевозимого продукта.
Это довольно легко отследить, ведь подобные предпочтения практически не меняются.
Ниже я привел данные запросов одного из пользователей за 3 дня.
Порядок заполнения следующий: 1 графа – страна отправления, 2 – страна назначения, 3 – регион отправления, 4 – регион назначения.
Видно, что у этого пользователя есть определенные предпочтения в странах и провинциях.
Но так происходит не у всех и не всегда.
Очень часто перевозчик указывает только страну назначения или не указывает регион отправления; например, он находится в Бельгии и может приехать в любую провинцию, чтобы забрать груз.
В целом запросы бывают разных типов: «страна-страна», «страна-регион», «регион-страна» или «регион-регион» (оптимальный вариант).
Испытания алгоритмов
Как известно, стратегии создания рекомендательных систем в основном делятся на контентную фильтрацию и коллаборативную фильтрацию.На основе этой классификации я начал строить возможные решения.
Я взял фотографию из Hub.forklog.com
Многие источники утверждают, что системы совместной фильтрации работают лучше.
Все просто: мы пытаемся найти пользователей, похожих на нас, со схожими моделями поведения и рекомендуем нашему пользователю те же запросы, что и у них.
В общем, это решение было первым вариантом, который я представил клиентам.
Но они с ним не согласились и сказали, что это не сработает. Ведь все очень сильно зависит от того, где сейчас находится грузовик, куда он перевозил груз, где он обитает и куда ему удобнее ехать.
Обо всем этом мы не знаем, поэтому так сложно полагаться на поведение других пользователей, даже если они, на первый взгляд, похожи.
Теперь о контент-ориентированных системах.
Работают они следующим образом: сначала определяется и создается профиль пользователя, а затем производится подбор рекомендаций на основе его характеристик.
Вполне хороший вариант, но в нашем случае есть пара нюансов.
Во-первых, за одним пользователем может стоять целая группа людей, ищущих груз для множества фур и заходящих с разных IP. Во-вторых, из точных данных мы имеем только страну перевозчика, а информация о количестве грузовиков и их типах примерно «появляется» только в запросах, которые делает пользователь.
То есть, чтобы построить контентную систему для нашего проекта, нам необходимо посмотреть запросы каждого пользователя и постараться найти среди них самые популярные.
Наша первая система рекомендаций не использовала сложных алгоритмов.
Мы постарались присвоить рейтинг запросам и найти самые популярные поисковые запросы, чтобы рекомендовать их.
Чтобы протестировать концепцию, наша команда работала с реальными пользователями: отправляла им рекомендации, а затем собирала отзывы.
В принципе, результат перевозчикам понравился.
После этого я сравнил наши рекомендации с тем, что искали операторы связи в те же дни, и увидел, что система очень хорошо работает для пользователей со стабильным поведением.
Но, к сожалению для тех, кто сделал более широкий круг запросов, точность рекомендаций оказалась не очень высокой — система нуждалась в доработке.
Я продолжал разбираться, с чем мы здесь имеем дело.
По сути, это скрытая марковская модель, где за каждым пользователем может стоять группа людей.
Более того, пользователи могут находиться в различных скрытых состояниях: нет информации о том, где сейчас находится их грузовик, сколько человек на одном аккаунте и когда в следующий раз им нужно куда-то поехать.
Готовых решений по изготовлению скрытой марковской модели на тот момент я не знал, поэтому решил найти что-то попроще.
Соответствуйте PageRank
Поэтому я обратил внимание на алгоритм PageRank, когда-то созданный основателями Google Сергеем Брином и Ларри Пейджем, который до сих пор используется этой поисковой системой для рекомендации сайтов пользователям.PageRank представляет все интернет-пространство в виде графа, где каждая веб-страница является своим узлом.
Используя его, вы можете рассчитать «важность» (или ранг) каждого узла.
PageRank принципиально отличается от существовавших до него алгоритмов поиска, поскольку он основан не на содержании страниц, а на ссылках, которые расположены внутри них.
То есть рейтинг каждой страницы зависит от количества и качества ссылок, указывающих на нее.
Брин и Пейдж доказали сходимость этого алгоритма, а это значит, что мы всегда можем вычислить ранг любого узла ориентированного графа и прийти к значениям, которые не изменятся.
Давайте посмотрим на его формулу: 
- ПР(П) – рейтинг конкретной страницы
- Н - количество страниц
- я — другие страницы
- О — количество исходящих ссылок
- д – понижающий коэффициент. Когда пользователь что-то ищет, в определенный момент он останавливается, перестает переходить по ссылкам со страницы на страницу и начинает искать что-то другое.
Убывающий множитель подсказывает нам момент, когда произойдет переход к новому поиску.
0 ≤ d ≤ 1 – обычно d равно 0,85. В нашей модели я сохранил это значение.
Важно помнить, что вначале всем узлам присваивается одинаковый вес, равный 1/количество узлов.
Вы можете видеть, что узел A здесь стал самым важным, несмотря на то, что, как и C, на него указывают только два узла.
Но ранг узлов, указывающих на А, выше, чем ранг узлов, указывающих на С.
Предположения и решение
Итак, PageRank описывает марковский процесс без скрытых состояний.С его помощью мы всегда найдем итоговый вес каждого узла, но не сможем отслеживать изменения в графике.
Алгоритм действительно хороший, нам удалось его адаптировать и повысить точность результатов.
Для этого мы взяли модификацию PageRank — алгоритм Personalized PageRank, который отличается от базового тем, что переход всегда осуществляется к ограниченному числу узлов.
То есть, когда пользователю надоедает «переходить» по ссылкам, он переключается не на случайный узел, а на один из заданного набора.
Узлами графа в нашем случае будут запросы пользователей.
Поскольку наш алгоритм должен давать рекомендации на предстоящий день, я разделил все запросы для каждого оператора по дням.
Теперь построим граф: узел А соединяется с узлом Б, если поиск типа В следует за поиском типа А, то есть поиск типа А был осуществлен пользователем до дня поиска маршрута Б.
Например: «Париж – Брюссель» во вторник (А), а в среду Брюссель – Кёльн (Б).
А некоторые пользователи делают много запросов в день, поэтому между собой соединяются сразу несколько узлов, и в результате мы получаем достаточно сложные графы.
Чтобы добавить информацию о важности перехода от одного поиска к другому, мы добавили веса к ребрам графа.
Вес ребра A-B — это количество случаев, когда пользователь искал B после поиска A. Также очень важно учитывать новизну запросов, потому что пользователь меняет свой шаблон: он может переместить или реорганизовать основной тип перевозки, после которой ему не захочется ехать на пустом грузовике.
Поэтому нужно следить за историей маршрутов — добавляем переменную, которая также будет влиять на вес узла.
Стоит учитывать сезонность: мы можем знать, что, например, в сентябре перевозчик чаще ходит во Францию, а в октябре – в Германию.
Соответственно, больший вес можно придать тем услугам, которые «популярны» в определенном месяце.
Кроме того, мы полагаемся на информацию о том, что пользователь искал в последний раз.
Это помогает косвенно предположить, где может находиться грузовик.
Результат
Все реализовано на платформе Google. У нас есть OLTP-приложение, откуда данные запроса поступают и попадают в BigQuery, где формируются дополнительные представления и таблицы, содержащие уже обработанную информацию.
Для ускорения и распараллеливания обработки больших объемов данных была использована библиотека DASK. В нашем решении все данные переносятся в Cloud Storage, потому что DASK работает только с ним и не взаимодействует с BigQuery. В Kubernetes созданы два Jobs, один из которых передает данные из BigQuery в Cloud Storage, а второй дает рекомендации.
Происходит это так: Джоб берет данные о парах запросов из Cloud Storage, обрабатывает их, формирует рекомендации на ближайший день и отправляет обратно в BigQuery. Оттуда уже в формате .
json мы можем передать рекомендации в OLTP-приложение, где их увидят пользователи.
Точность рекомендаций оценивается в Таблице, где наши рекомендации сравниваются с тем, что на самом деле искал пользователь, а также его реакцией (понравилось или нет).
Конечно, хотелось бы поделиться результатами.
Вот, например, пользователь, который каждый день делает 14 поисковых запросов «страна-страна».
Мы рекомендовали ему такую же сумму: 
Оказалось, что наши варианты полностью совпали с тем, что он искал.
Граф этого пользователя состоит из около 1000 различных запросов, но мы смогли очень точно угадать, что его заинтересует. Второй пользователь в среднем делает 8 разных запросов каждые 2 дня, причем ищет как в формате «страна-страна», так и с указанием конкретного региона отправления.
К тому же страны происхождения и доставки совершенно разные.
Поэтому мы не могли всё «угадать» и точность результатов была ниже: 
Обратите внимание, что у пользователя есть 2 графика с разным весом.
В одном точность достигла 38%, а это значит, что около 3 из 8 рекомендованных нами вариантов оказались актуальными.
И, возможно, если мы найдем груз на этих маршрутах, пользователь выберет их.
Последний и самый простой пример.
Каждый день человек совершает около 2 поисков.
У него очень стабильные шаблоны, не слишком много предпочтений и простой график.
Точность наших прогнозов составляет 100%.
Производительность в фактах
- Наши алгоритмы работают на 4 стандартных процессорах и 10 ГБ памяти.
- Объемы данных — до 1 миллиарда записей.
- Создание рекомендаций для всех пользователей, которых около 20 000, занимает 18 минут.
- Библиотека DASK используется для распараллеливания, а библиотека NetworkX — для алгоритма PageRank.
Представление поведения пользователей грузовой биржевой платформы в виде графика и использование PageRank позволяет точно угадать их будущие предпочтения и, таким образом, построить эффективные рекомендательные системы.
Теги: #Машинное обучение #Алгоритмы #искусственный интеллект #машинное обучение #системы рекомендаций #pagerank
-
Трудно Ли Найти Веб-Хостинг Mac?
19 Oct, 24 -
Плюсы/Минусы При Смене Компании
19 Oct, 24 -
Ctf От Bi.zone На Zeronights2016
19 Oct, 24 -
Фортуна Обращается К Open Xml
19 Oct, 24
