string-matching - fuzzy search javascript
Emparejamiento difuso de nombres de productos (10)
Creo que esto se reducirá a distinguir palabras clave como Lenovo de chaff como New .
Haría un 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, editaría la lista a mano para eliminar cualquier cosa, obviamente, desperdicios, como quizás Nuevo es realmente común pero no clave.
Luego tendrá una lista de palabras clave que pueden usarse para ayudar a identificar similitudes. Asociaría el nombre "sin procesar" con sus palabras clave, y usaría esas palabras cuando comparara dos o más nombres sin procesar por similitudes (literalmente, porcentaje de palabras clave compartidas).
¿No es una solución perfecta por cualquier tramo, pero no creo que esté esperando una?
Necesito hacer coincidir automáticamente los nombres de productos (cámaras, computadoras portátiles, televisores, etc.) que provienen de diferentes fuentes a un nombre canónico en la base de datos.
Por ejemplo, "Canon PowerShot a20IS" , "NUEVO powershot A20 IS de Canon" y "Cámara digital Canon PS A20IS" deben coincidir con "Canon PowerShot A20 IS" . He trabajado con levenshtein distance con algunas heurísticas adicionales (eliminar palabras comunes obvias, asignar un mayor costo a los cambios de números, etc.), lo cual funciona en cierta medida, pero no lo suficientemente bien, lamentablemente.
El problema principal es que incluso los cambios de una sola letra en las palabras clave relevantes pueden hacer una gran diferencia, pero no es fácil detectar cuáles son las palabras clave relevantes. Considere, por ejemplo, tres nombres de productos:
Lenovo T400
Lenovo R400
Nuevo Lenovo T-400, Core 2 Duo
Los dos primeros son cadenas ridículamente similares según cualquier estándar (ok, soundex podría ayudar a distinguir la T y la R en este caso, pero los nombres también podrían ser 400T y 400R), la primera y la tercera están bastante alejadas una de la otra. Cuerdas, pero son el mismo producto.
Obviamente, el algoritmo de coincidencia no puede ser 100% preciso, mi objetivo es hacer coincidir automáticamente alrededor del 80% de los nombres con una alta confianza.
Cualquier idea o referencia es muy apreciada.
Creo que la respuesta de Edg va en la dirección correcta: es necesario distinguir las palabras clave de la pelusa.
El contexto importa. Para tomar su ejemplo, Core 2 Duo es una pelusa cuando observa 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 de un nombre de producto son más importantes y deben aparecer en una forma u otra para identificar un producto, debe hacerlo. Tal vez a través del uso de algún tipo de marcado semántico? ¿Puede permitirse tener un humano marcado la base de datos?
Puede intentar definir clases de equivalencia para cosas como "T-400", "T400", "T 400", etc. Tal vez un conjunto de reglas que digan "los números se unen más fuertemente que las letras adjuntas a esos números".
Desglosar en casos basados en el fabricante, número de modelo, etc. puede ser un buen enfoque. Le recomendaría que consulte las técnicas de detección de términos para tratar de lograrlo: http://www.worldcat.org/isbn/9780262100854
Diseñar todo en un marco flexible que está mayormente basado en reglas, donde las reglas pueden modificarse según sus necesidades y los malos patrones emergentes (lea: cosas que rompen su algoritmo) también sería una buena idea. De esta manera, podría mejorar el rendimiento del sistema basándose en datos del mundo real.
Es posible que desee crear una lógica que ignore la combinación de letras y números de los números de modelo (ya que son casi siempre muy similares).
Es posible que pueda hacer uso de una búsqueda de trigrama para esto. Debo admitir que nunca he visto el algoritmo para implementar un índice, sino que lo he visto trabajar en aplicaciones farmacéuticas, donde hace frente muy bien con nombres de medicamentos mal escritos. Es posible que pueda aplicar el mismo tipo de lógica a este problema.
Ese es exactamente el problema en el que estoy trabajando en mi tiempo libre. Lo que se me ocurrió es: basado en palabras clave, restringir el alcance de la búsqueda:
En este caso podrías tener alguna jerarquía:
tipo -> empresa -> modelo
para que coincida con "Cámara digital" para un tipo
"Canon" para la compañía y allí quedaría mucho más limitado para buscar.
Se podría reducir esto aún más introduciendo líneas de productos, etc. Pero el punto principal es que, probablemente, esto debe hacerse de forma iterativa.
Este es un problema de vinculación de registros . La biblioteca dedupe python proporciona una implementación completa, pero incluso si no usa python, la documentación tiene una buena visión general de cómo abordar este problema .
Brevemente, dentro del paradigma estándar, esta tarea se divide en tres etapas
- Compara los campos, en este caso solo el nombre. Puede usar uno o más comparadores para esto, por ejemplo, una distancia de edición como la distancia de Levenshtein o algo así como la distancia de coseno que compara el número de palabras comunes.
- Convierta una matriz de puntajes de distancia en una probabilidad de que un par de registros sean realmente lo mismo
- Agrupe esas puntuaciones de probabilidad por pares en grupos de registros que probablemente todos se refieran a la misma cosa.
La comprensión clave aquí es que usted tiene una métrica de distancia adecuada. De hecho no es tu problema en absoluto. Tu problema está en la clasificación.
Dejame darte un ejemplo. Digamos que tienes 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é hay una diferencia en la clasificación? Eso es porque Bar Y1 es un valor atípico, mientras que Foo Y1 no lo es.
Lo gracioso es que en realidad no es necesario hacer mucho trabajo para determinar estos grupos por adelantado. Simplemente haces una clasificación recursiva. Comienzas con un nodo por grupo y luego agregas 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 sus cadenas serán idénticas, pronto obtendrá subárboles grandes con entradas idénticas. La recursión termina con el supernodo que contiene en la raíz del árbol.
Ahora mapee los nombres canónicos contra este árbol. Verás rápidamente que cada una coincidirá con un subárbol completo. Ahora, usa las distancias entre estos árboles para elegir el límite 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.
No tengo ninguna experiencia con este tipo de problema, pero creo que una implementación muy ingenua sería establecer el término de búsqueda y buscar coincidencias que contengan alguno de los tokens.
"Canon PowerShot A20 IS", por ejemplo, se muestra en:
- Canon
- Disparo de energía
- A20
- ES
que coincidiría con cada uno de los otros elementos que desea mostrar en los resultados. Por supuesto, esta estrategia probablemente también producirá un montón de falsas coincidencias.
Otra estrategia sería almacenar "palabras clave" con cada elemento, como "cámara", "canon", "cámara digital" y realizar búsquedas basadas en elementos que tengan palabras clave coincidentes. Además, si almacena otros atributos como Creador, Marca, etc., puede buscar en cada uno de estos.
Podemos utilizar el servicio de Datadecision para productos coincidentes.
Le permitirá hacer coincidir automáticamente los datos de su producto mediante algoritmos estadísticos. Esta operación se realiza después de definir un umbral de puntuación de confianza.
Todos los datos que no se pueden hacer coincidir 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 la coincidencia de datos la próxima vez que importe datos nuevos.
Los algoritmos de comprobación de ortografía vienen a la mente.
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.
Los bits y piezas que quedan en mi memoria:
- Quita todas las palabras comunes (a, an, the, new). Lo que es "común" depende del contexto.
- Tome la primera letra de cada palabra y su longitud y haga de ella una clave de palabra.
- Cuando aparece una palabra sospechosa, busca palabras con la misma palabra o similar.
Puede que no resuelva sus problemas directamente ... pero usted dice que estaba buscando ideas, ¿verdad?
:-)