Алгоритм BFS в рекомендательных системах: практическое руководство по выбору и реализации

В мире рекомендательных систем машинное обучение и глубокие нейронные сети часто занимают центральное место. Однако классические алгоритмы на графах, такие как поиск в ширину (BFS — Breadth-First Search), остаются мощными, интерпретируемыми и эффективными инструментами в арсенале инженера. BFS не предсказывает рейтинги, как матричные разложения, а исследует структуру связей между объектами (пользователями, товарами, контентом). Выбор BFS в качестве основы или компонента рекомендательной системы требует понимания его сильных сторон, ограничений и конкретных сценариев применения.

Основная идея использования BFS — это рекомендация на основе обхода графа. Представьте себе граф, где вершины — это товары, а ребра — связи между ними (например, «часто покупают вместе», «похож по характеристикам», «нравится одним пользователям»). Стартуя от товара, который пользователь уже просмотрел или купил (исходная вершина), BFS систематически обходит граф, сначала посещая ближайших «соседей», затем соседей соседей и так далее. Это позволяет находить не только прямые аналоги, но и косвенно связанные товары, расширяя ассортимент рекомендаций.

Когда выбирать BFS? Во-первых, когда критически важна интерпретируемость результата. В отличие от «черного ящика» нейросетей, путь рекомендации, сгенерированный BFS, можно легко объяснить: «Мы рекомендуем этот товар, потому что он часто покупается с тем, что вы уже смотрели, или похож на него по свойствам X и Y». Это ценно для регулируемых отраслей и для построения доверия пользователей.

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

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

Однако выбор BFS требует тщательной проработки структуры графа. Качество рекомендаций напрямую зависит от качества ребер. Какие связи вы строите? Совместные покупки (co-purchases)? Совместные просмотры в рамках сессии? Семантическое сходство на основе описаний? Связи, выведенные через коллаборативную фильтрацию? Эксперты советуют комбинировать несколько типов ребер с разными весами. Например, ребро «купили вместе» может иметь больший вес, чем ребро «похожи по описанию».

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

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

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