Графовые рекомендации на Python: от словаря к Dijkstra

Графовые рекомендации: почему словарь — это тупик

Большинство учебных рекомендательных проектов — это просто поиск по словарю: вы вводите «комедия» — получаете список комедий. Это работает, но именно поэтому такие проекты забываются: словарь может сказать, что похоже, но никогда не покажет, что интересно отличается. Я хотел второе. Поэтому я смоделировал каталог как взвешенный граф — и в итоге нашёл вид сходства, который не проектировал специально.

Данные: 40 строк, 5 атрибутов

Проект называется CreatorRoute. Он рекомендует форматы коротких видео: вы называете ролик, который вам понравился, и получаете близкие совпадения плюс несколько намеренных «выбросов». Данные — 40 строк вручную написанных видео, пять атрибутов: id, title, niche, hook_type, length, editing_style, cta_type.

4, Stop posting at 9am, marketing, contrarian, short, jump-cut, comment
23, Stop using this transition, editing, contrarian, short, jump-cut, comment

Запомните эти две строки — они важны позже. Единственное правило, которого я придерживался при написании датасета: каждое значение атрибута должно повторяться в нескольких строках. Уникальные значения создают изолированные узлы, а изолированные узлы делают граф непроходимым. Если бы у каждого видео был свой уникальный hook_type, не было бы рёбер для обхода.

Построение графа: вес ребра — обратное число общих атрибутов

Каждое видео — узел. Два узла соединяются ребром, если у них есть хотя бы один общий атрибут. Вес ребра — обратное число общих атрибутов:

ATTRIBUTES = ["niche", "hook_type", "length", "editing_style", "cta_type"]

def shared_attributes(a, b):
    # Считаем, сколько атрибутов совпало у двух видео
    return sum(1 for attr in ATTRIBUTES if a[attr] == b[attr])

def build_graph(items):
    # Создаём граф: для каждого id — список соседей и весов
    graph = {item_id: [] for item_id in items}
    ids = list(items)
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            a, b = items[ids[i]], items[ids[j]]
            shared = shared_attributes(a, b)
            if shared > 0:
                weight = 1 / shared
                graph[ids[i]].append((ids[j], weight))
                graph[ids[j]].append((ids[i], weight))
    return graph

Инвертирование количества — весь трюк. Четыре общих атрибута дают вес 0.25, один общий — 1.0. Чем больше общего, тем короче ребро, а значит, алгоритмы поиска кратчайшего пути ранжируют по сходству без дополнительных усилий. range(i + 1, ...) избегает двойного сравнения каждой пары.

Где BFS провалился

Мой первый план был — только поиск в ширину. Глубина 1 для близких совпадений, глубина 2 для открытий. Чисто, просто, без весов. Это не сработало. При 15 элементах BFS из любого узла достигал 10 из 14 других на глубине 1. Одного общего атрибута достаточно для ребра, а с пятью атрибутами в маленьком каталоге почти всё связано почти со всем.

BFS отвечает на вопрос «достижимо ли, и за сколько шагов». В плотном графе ответ почти всегда «да, за один шаг», что не является ранжированием. Видео с четырьмя общими атрибутами и видео с одним общим атрибутом были просто «соседями».

Где Dijkstra всё исправил

Алгоритм Дейкстры обходит тот же граф, но накапливает вес, а не считает шаги:

import heapq

def dijkstra(graph, start):
    # Расстояния от стартовой вершины до всех остальных
    distances = {start: 0}
    heap = [(0, start)]
    settled = set()
    while heap:
        dist, current = heapq.heappop(heap)
        if current in settled:
            continue
        settled.add(current)
        for neighbor, weight in graph[current]:
            new_dist = dist + weight
            if new_dist < distances.get(neighbor, float("inf")):
                distances[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    del distances[start]
    return distances

Те же соседи, но реальный порядок. Что-то на четыре пятых идентичное получает 0.25, а едва связанное — 1.0. BFS не был потрачен впустую: он теперь отвечает за список открытий, извлекая узлы на глубине 2, которые не имеют прямых общих атрибутов, но находятся в двух шагах. Два алгоритма, два вопроса, один граф.

То, что я не планировал

Вот вывод для «Stop posting at 9am» (маркетинговое видео):

Потому что вам понравилось: Stop posting at 9am
(маркетинг / контрарный / jump-cut)

  Ближайшие совпадения:
    - 3 mistakes killing your ad spend  [0.25]
    - The one word killing your CTA     [0.25]
    - Stop using this transition        [0.25]

  Стоит изучить:
    - 6 free tools I use daily
    - 5 onboarding flows that work
    - My first 1000 orders

Третье близкое совпадение — о монтаже видео. Второе — о копирайтинге. Ни одно не о маркетинге. Они в топе, потому что делят contrarian + short + jump-cut + comment. Граф незаметно научился сопоставлять по формату, а не по теме — та же форма видео, но совершенно другой предмет.

Я этого не строил. Я построил «подсчёт общих атрибутов». Отношение к теме как к одному из пяти атрибутов, а не как к первичному ключу, позволило структурному сходству проявиться самостоятельно. Словарь, ключом которого является категория, не смог бы этого обнаружить, потому что ключ отбросил бы остальные четыре атрибута до начала сравнения.

Поиск: тот же компромисс

CLI должен найти ваше видео, прежде чем рекомендовать что-либо, и это оказалось отдельным маленьким уроком по сложности. prefix_search использует бинарный поиск по отсортированному индексу — O(log n), но находит только заголовки, которые начинаются с вашего запроса. keyword_search сканирует каждый заголовок за O(n) и находит совпадения в любом месте. Поиск «ad» не находит ничего быстрым способом и четыре заголовка медленным, включая «Rewriting a bad ad live».

CLI сначала пробует быстрый способ, а затем откатывается:

def find_matches(items, index, query):
    hits = prefix_search(index, query)
    return hits if hits else keyword_search(items, query)

При 40 элементах разница неизмерима. Написание обоих методов сделало компромисс конкретным так, как чтение таблицы Big O никогда не делает.

Что бы я изменил

Датасет написан вручную, что ограничивает способность графа удивлять меня — я выбрал атрибуты, значит, частично выбрал связи. Реальные собранные данные были бы лучшим тестом. Функция build_graph имеет сложность O(n²): сравниваются все пары. При 40 элементах это нормально, при 40 000 — болезненно. Решение — сегментирование по значению атрибута и сравнение только внутри сегментов, что мне пока не понадобилось.

Атрибуты сейчас равнозначны. Общий editing_style весит столько же, сколько общий niche, что, вероятно, неверно. Разные веса — очевидный следующий эксперимент.

Практический вывод

Если вы работаете над рекомендательным проектом, сопротивляйтесь словарю. Граф — это ненамного больше кода (менее 200 строк, без зависимостей вне стандартной библиотеки), и он даёт вам место для второго алгоритма, реальную причину заботиться о весах рёбер и иногда результат, который вы не проектировали. Попробуйте взять свой каталог и построить такой граф уже сегодня — вы увидите, как неожиданные сходства всплывут сами собой.

Код: github.com/mbadr3227-sys/creatorroute