Алгоритмы сопоставления на основе пересечения ключевых слов

Question

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

Вот пример:

buyer_keywords = {"furry", "four legs", "likes catnip", "has claws"} 

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

seller_keywords[1] = {"furry", "four legs", "arctic circle", "white"}
seller_keywords[2] = {"likes catnip", "furry", 
                      "hates mice", "yarn-lover", "whiskers"}

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

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

seller_keywords[1] = {"furry":.05, 
                      "four legs":.05, 
                      "arctic circle":.8, 
                      "white":.1}

seller_keywords[2] = {"likes catnip":.5, 
                      "furry":.4, 
                      "hates mice":.02, 
                      "yarn-lover":.02, 
                      "whiskers":.06}

Теперь мы можем суммировать значение попаданий: теперь Продавец 1 получает оценку 0, а Продавец 2 - 0,9. Пока все хорошо, но теперь мы можем получить третьего продавца с очень ограниченным набором неописательных ключевых слов:

seller_keywords[3] = {"furry":1}

Это катапультирует их наверх для любого попадания по их единственному ключевому слову, что не очень хорошо.

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

Answer 1

Я думаю, вы хотите использовать косинусное сходство ; это базовая техника, которая делает вас довольно далеким от первого взлома. Интуитивно вы создаете вектор, в котором каждый известный вам тег имеет определенный индекс:

terms[0] --> aardvark
terms[1] --> anteater
...
terms[N] --> zuckerberg

Затем вы создаете векторы в этом пространстве для каждого человека:

person1[0] = 0     # this person doesn't care about aardvarks
person1[1] = 0.05  # this person cares a bit about anteaters
...
person1[N] = 0

Каждый человек теперь является вектором в этом N-мерном пространстве. Затем вы можете использовать косинусное сходство, чтобы вычислить сходство между их парами. Расчетно, это в основном то же самое, что запросить угол между двумя векторами. Вы хотите, чтобы косинус был близок к 1, что означает, что векторы примерно коллинеарны - что они имеют одинаковые значения для большинства измерений.

Чтобы улучшить эту метрику, вы можете использовать tf-idf взвешивание для элементов в вашем векторе. Tf-idf преуменьшает важность популярных терминов (например, «iPhone») и пропагандирует важность непопулярных терминов, с которыми этот человек, по-видимому, особенно связан.

Комбинирование взвешивания tf-idf и косинусного сходства хорошо подходит для большинства подобных приложений.

Answer 2

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

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

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

Привет