Coincidencia difusa de los nombres de productos

Question

Necesito hacer coincidir automáticamente los nombres de los productos (cámaras, computadoras portátiles, TV-s, etc.) que provienen de diferentes fuentes con un nombre canónico en la base de datos.

Por ejemplo "Canon PowerShot a20IS", "A20 nuevas PowerShot IS de Canon" y "cámara digital Canon PS A20IS" todos debemos partido "Canon PowerShot A20 está a". He trabajado con levenshtein distancia con algunos heurísticos añadidos (eliminando palabras comunes obvias, asignando un mayor costo a los cambios en los números, etc.), que funciona hasta cierto punto, pero no lo suficientemente bien por desgracia.

El principal problema es que incluso los cambios de una sola letra en palabras clave relevantes pueden marcar una gran diferencia, pero no es fácil detectar cuáles son las palabras clave relevantes. Considere, por ejemplo, tres nombres de producto:
Lenovo T400
Lenovo R400
Nueva Lenovo T400, Core 2 Duo
Los dos primeros son ridículamente cadenas similares de cualquier punto de vista (bueno, podría ayudar a soundex para distinguir el T y el R en este caso, pero los nombres también podrían ser 400T y 400R), el primero y el tercero están bastante separados unos de otros como cadenas, pero son el mismo producto.

Obviamente, el algoritmo de coincidencia no puede ser un 100% preciso, mi objetivo es hacer coincidir automáticamente alrededor del 80% de los nombres con una gran confianza.

Cualquier idea o referencias se aprecia mucho

Answer 1

Es posible que desee crear una lógica que ignora la combinación de letras/número de números de modelo (ya que son casi siempre muy similar).

Answer 2

Spell checking me vienen a la mente los algoritmos.

Aunque no pude encontrar una buena implementación de muestra, creo que puede modificar un algoritmo básico de corrección ortográfica para obtener resultados satisfactorios. es decir, trabajar con palabras como una unidad en lugar de un personaje.

las partes y piezas que quedan en mi memoria:

1. eliminar todas la palabras comunes (un, una, el, nuevo). Lo que es "común" depende del contexto.
2. Tome la primera letra de cada palabra y su longitud y conviértala en una palabra clave.
3. Cuando aparece una palabra sospechosa, busca palabras con la misma o similar tecla de palabra.

Podría no resolver sus problemas directamente ... pero decir que estabas buscando ideas, ¿verdad?

:-)

Answer 3

Creo que esto se reducen a distinguir las palabras clave como Lenovo de la paja como Nueva.

Me gustaría ejecutar algunos análisis sobre la base de datos de nombres para identificar palabras clave. Podría usar un código similar al utilizado para generar una nube de palabras.

Luego, editaba a mano la lista para eliminar cualquier cosa obviamente chaff, como quizás New es realmente común pero no clave.

A continuación, tendrá una lista de palabras clave que pueden utilizarse para ayudar a identificar similitudes. Asociaría el nombre "en bruto" con sus palabras clave y usaría esas palabras clave al comparar dos o más nombres sin procesar para similitudes (literalmente, porcentaje de palabras clave compartidas).

¿No es una solución perfecta por ningún tramo, pero no creo que esté esperando una?

Answer 4

No tengo ninguna experiencia con este tipo de problema, pero creo que una implementación muy ingenua sería tokenizar el término de búsqueda y buscar coincidencias que contengan cualquiera de los tokens.

"Canon PowerShot A20 ES", por ejemplo, tokenizes en:

• Canon
• Powershot
• A20
• ES

que coincida con cada uno de los otros elementos quieres aparecer en los resultados Por supuesto, esta estrategia probablemente produzca una gran cantidad de coincidencias falsas también.

Otra estrategia sería almacenar "palabras clave" con cada elemento, como "cámara", "canon", "cámara digital" y búsqueda basada en elementos que tienen palabras clave coincidentes. Además, si almacenó otros atributos como Creador, Marca, etc., podría buscar en cada uno de estos.

Answer 5

La respuesta de edg está en la dirección correcta, creo que es necesario distinguir las palabras clave de la pelusa.

El contexto es importante. Para tomar su ejemplo, Core 2 Duo es peludo cuando mira dos instancias de un T400, pero no cuando mira un paquete OEM de CPU.

Si puede marcar en su base de datos qué partes de la forma canónica del nombre de un producto son más importantes y deben aparecer de una forma u otra para identificar un producto, debe hacerlo. ¿Tal vez mediante el uso de algún tipo de marcado semántico? ¿Puede permitirse tener una marca humana en la base de datos?

Puede tratar de definir clases de equivalencia para cosas como "T-400", "T400", "T 400" etc. Quizás un conjunto de reglas que diga "los números se atan con más fuerza que las letras asociadas a esos números".

El desglose en casos según el fabricante, el número de modelo, etc. podría ser un buen enfoque. Yo recomendaría que estudie técnicas de detección de términos para tratar de lograr eso: http://www.worldcat.org/isbn/9780262100854

Diseñando todo en un marco flexible basado principalmente en reglas, donde las reglas se pueden modificar en función de sus necesidades y de los malos patrones emergentes (léase: cosas que rompen su algoritmo) sería una buena idea, también. De esta forma, podrá mejorar el rendimiento del sistema en función de los datos del mundo real.

Answer 6

Ese es exactamente el problema en el que estoy trabajando en mi tiempo libre.Lo que se me ocurrió es: basado en palabras clave de restringir el alcance de la búsqueda:

en este caso, usted podría tener alguna jerarquía:

tipo -> empresa -> modelo

de manera que usted emparejaría "Cámara digital" para un tipo

"Canon" para la compañía y allí usted quedaría con un alcance mucho más estrecho para buscar.

Puede trabajar en esto aún más con la introducción de líneas de productos, etc. Pero el punto principal es que esto probablemente tiene que hacerse de forma iterativa.

Answer 7

Es posible que pueda hacer uso de un trigram search para esto. Debo admitir que nunca he visto el algoritmo para implementar un índice, pero lo he visto trabajando en aplicaciones farmacéuticas, donde realmente funciona muy bien con nombres de drogas mal escritos. Es posible que pueda aplicar el mismo tipo de lógica a este problema.

Answer 8

La clave aquí es que tiene una medida de distancia adecuada. De hecho, ese no es su problema en absoluto. Tu problema está en la clasificación.

Déjeme darle un ejemplo. Supongamos que tiene 20 entradas para el Foo X1 y 20 para el Foo Y1. Puedes asumir con seguridad que son dos grupos. Por otro lado, si tiene 39 entradas para la barra X1 y 1 para la barra Y1, debe tratarlas como un solo grupo.

Ahora, la distancia X1 < -> Y1 es la misma en ambos ejemplos, entonces ¿por qué existe una diferencia en la clasificación? Eso es porque Bar Y1 es un valor atípico, mientras que Foo Y1 no lo es.

Lo curioso es que en realidad no es necesario hacer un gran trabajo para determinar estos grupos por adelantado. Simplemente haces una clasificación recursiva. Comienza con un nodo por grupo y luego agrega un supernodo para los dos nodos más cercanos. En el supernodo, almacene la mejor suposición, el tamaño de su subárbol y la variación en él. Como muchas de tus cadenas serán idénticas, pronto obtendrás grandes subárboles con entradas idénticas. La recursión termina con el supernodo que contiene la raíz del árbol.

Ahora asigna los nombres canónicos a este árbol. Verá rápidamente que cada uno coincidirá con un subárbol completo. Ahora, use las distancias entre estos árboles para seleccionar el corte de distancia para esa entrada. Si tiene productos Foo X1 y Foo Y1 en la base de datos, la distancia de corte deberá ser menor para reflejar eso.

Answer 9

Podemos usar el Datadecision service para productos que coincidan.

Le permitirá hacer coincidir automáticamente los datos de su producto utilizando algoritmos estadísticos. Esta operación se realiza después de definir una puntuación umbral de confianza.

Todos los datos que no se pueden emparejar automáticamente deberán revisarse manualmente a través de una interfaz de usuario dedicada.

El servicio en línea utiliza tablas de búsqueda para almacenar sinónimos, así como su historial de coincidencia manual. Esto le permite mejorar la automatización de coincidencia de datos la próxima vez que importe datos nuevos.

Answer 10

Esto es un problema de record linkage. El dedupe python library proporciona una implementación completa, pero incluso si no utiliza Python, la documentación tiene un good overview of how to approach this problem.

En pocas palabras, dentro del paradigma estándar, esta tarea se divide en tres etapas

1. Compare las esferas, y en este caso sólo el nombre. Puede usar uno o más comparadores para esto, por ejemplo, una distancia de edición como la distancia Levenshtein o algo así como la distancia del coseno que compara el número de palabras comunes.
2. Convierta una matriz en los puntajes de distancia en una probabilidad de que un par de registros sean realmente lo mismo
3. Agrupe los puntajes de probabilidades pairwise en grupos de registros que probablemente todos se refieran a la misma cosa.