Нечеткое совпадение названий продуктов

Question

Мне нужно автоматически сопоставить названия продуктов (камеры, ноутбуки, телевизоры и т. Д.), Которые поступают из разных источников, с каноническим именем в базе данных.

Например "Canon PowerShot a20IS" , "НОВЫЙ powershot A20 IS от Canon" и "Цифровая камера Canon PS A20IS" все должны соответствовать "Canon PowerShot A20 IS" . Я работал с дистанцией Левенштейна с некоторыми дополнительными эвристиками (убирая очевидные общие слова, назначая более высокие затраты на изменение чисел и т. Д.), Что работает в некоторой степени, но, к сожалению, недостаточно хорошо.

Основная проблема заключается в том, что даже однобуквенные изменения в релевантных ключевых словах могут иметь огромное значение, но определить, какие из них являются релевантными, нелегко. Для примера рассмотрим три названия продуктов:
Lenovo T400
Lenovo R400
Новый Lenovo T-400, Core 2 Duo
Первые две строки смехотворно похожи по любому стандарту (хорошо, soundex может помочь различать T и R в этом случае, но имена могут также быть 400T и 400R), первая и третья довольно далеки друг от друга, так как строки, но это один и тот же продукт.

Очевидно, что алгоритм сопоставления не может быть точным на 100%, моя цель - автоматически сопоставить около 80% имен с высокой достоверностью.

Любые идеи или ссылки высоко ценится

Answer 1

Ключевое понимание здесь в том, что у вас есть правильная метрика расстояния. Это на самом деле не ваша проблема вообще. Ваша проблема в классификации.

Позвольте привести пример. Скажем, у вас есть 20 записей для Foo X1 и 20 для Foo Y1. Вы можете смело предположить, что они две группы. С другой стороны, если у вас есть 39 записей для столбца X1 и 1 для столбца Y1, вы должны рассматривать их как одну группу.

Теперь расстояние X1 <-> Y1 одинаково в обоих примерах, так почему же существует разница в классификации? Это потому, что Bar Y1 является выбросом, а Foo Y1 - нет.

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

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

Answer 2

Я думаю, что это будет сводиться к тому, чтобы отличать ключевые слова, такие как Lenovo от мякины, такие как Новый .

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

Тогда я бы отредактировал список вручную, чтобы удалить что-нибудь явно потертое, как, может быть, New на самом деле является обычным, но не ключевым.

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

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

Answer 3

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

Контекст имеет значение. В качестве примера можно привести Core 2 Duo, если смотреть на два экземпляра T400, но не на OEM-пакет процессора.

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

Вы можете попытаться определить классы эквивалентности для таких вещей, как «Т-400», «Т400», «Т 400» и т. Д. Может быть, набор правил, которые говорят: «числа связываются сильнее, чем буквы, прикрепленные к этим числам».

Хорошим подходом может быть разбивка на случаи на основе производителя, номера модели и т. Д. Я бы порекомендовал вам взглянуть на методы определения терминов, чтобы попытаться сделать это: http://www.worldcat.org/isbn/9780262100854

Хорошей идеей было бы также спроектировать все в гибкой среде, которая в основном основана на правилах, где правила могут быть изменены в зависимости от ваших потребностей и возникающих плохих шаблонов (читай: вещи, которые нарушают ваш алгоритм). Таким образом, вы сможете улучшить производительность системы, основываясь на реальных данных.

Answer 4

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

Answer 5

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

Вкратце, в рамках стандартной парадигмы эта задача разбита на три этапа

1. Сравните поля, в данном случае только имя. Для этого вы можете использовать один или несколько компараторов, например, расстояние редактирования, например, расстояние Левенштейна, или что-то вроде расстояния косинуса, которое сравнивает количество общих слов.
2. Превратите массив для оценки расстояния в вероятность того, что пара записей действительно об одном и том же
3. Сгруппируйте эти попарные вероятностные оценки в группы записей, которые, вероятно, все ссылаются на одно и то же.

Answer 6

Мы можем использовать сервис Datadecision для соответствующих продуктов.

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

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

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

Answer 7

Это именно та проблема, над которой я работаю в свободное время. Я придумал: по ключевым словам сузить область поиска:

в этом случае вы можете иметь некоторую иерархию:

тип -> компания -> модель

чтобы вы соответствовали «Цифровая камера» для вида

«Canon» для компании, и у вас останется гораздо более узкая область поиска.

Вы можете сделать это еще дальше, представив линейки продуктов и т. Д. Но главное, это, вероятно, должно быть сделано итеративно.

Answer 8

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

«Canon PowerShot A20 IS», например, размечается на:

• Canon
• Powershot
• A20
• IS

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

Другая стратегия заключается в хранении «ключевых слов» с каждым элементом, таких как «камера», «канон», «цифровая камера», и поиск по элементам, которые имеют соответствующие ключевые слова. Кроме того, если вы сохранили другие атрибуты, такие как Maker, Brand и т. Д., Вы можете выполнить поиск по каждому из них.

Answer 9

Проверка орфографии алгоритмы приходят на ум.

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

Кусочки и кусочки, которые остались в моей памяти:

1. Вычеркните все распространенные слова (a, an, the, new). Что является «общим», зависит от контекста.
2. Возьмите первую букву каждого слова и его длину и сделайте это ключевым словом.
3. Когда появляется подозрительное слово, ищет слова с таким же или похожим ключом слова.

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

: -)

Answer 10

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