Алгоритм наилучшего совпадения пар предметов при оценке сходства

Question

Я пытаюсь сопоставить два списка продуктов по названию.

Продукты поступают с разных веб-сайтов, и их названия могут различаться у разных веб-сайтов различными способами, например, "iPhone 128ГБ " против " Apple iPhone 128GB ".

Списки товаров пересекаются, но не равны, и один не является надмножеством другого;т.е. некоторые продукты из списка A отсутствуют в списке B, и наоборот.

Учитывая алгоритм, который сравнивает две строки (названия продуктов) и возвращает оценку сходства между 0и 1 (у меня уже есть удовлетворительная реализация здесь), Я ищу алгоритм, который выполняет оптимальное соответствие списка A списку B.

Другими словамиЯ думаю, что я ищу алгоритм, который максимизирует сумму всех одинаковых оценок в матчах.

Обратите внимание, что продукт из одного списка должен соответствовать не более чем одному продукту из другого списка.

Моя первоначальная идея

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

и т. Д.

Меня беспокоит эта нативная реализация, которая заключается в том, что если позднее в цикле есть лучшее совпадение, то продуктс B уже был присвоен другому продукту с A на предыдущей итерации, сопоставление не является оптимальным.

Улучшенная версия

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

• предварительно рассчитать оценки сходства для всех A - B пар
• , отбросить сходства ниже, чем используемый порогвыше
• порядок по сходству, сначала самый высокий
• для каждой пары, если ни продукт A, ни продукт B не были сопоставлены, соответствует этим продуктам .

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

Меня беспокоит то, что очень интенсивно использует вычислительные ресурсы и памятьive : скажем, у меня есть 5000 товаров в обоих списках, то есть 25 000 000 баллов сходства для предварительного вычисления и потенциального хранения в памяти (или базе данных);на самом деле он будет ниже из-за минимально необходимого порога, но он все равно может стать очень большим и по-прежнему интенсивно использовать процессор.

Я что-то пропустил?

Есть ли более эффективный алгоритм, которыйвыдает тот же вывод, что и эта улучшенная версия?

Answer 1

Ваша модель может быть переформулирована в терминах графа: рассмотрим полный взвешенный двудольный граф, где вершины первой части - это имена из списка A, вершины второй части - это имена из списка B, а ребра - взвешенные с предварительно вычисленными показателями сходства.

Теперь ваша проблема выглядит очень близко к плотной Assignment_problem , оптимальное решение которой можно найти с помощью Венгерского алгоритма (O (n³) сложность).

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

Answer 2

Ваш второй алгоритм должен обеспечивать приличный вывод, но он не оптимален. Проверьте следующий случай:

Set0 Set1 
A    C
B    D

Similarities:
A-C = 900
A-D = 850
B-C = 850
B-D = 0

Your algorithm's output: [(A,C), (B,D)]. Value 900.
Optimal output: [(A,D), (B,C)]. Value 1700.  

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