Calculo de "distancias" entre descripciones

[mgaitan]

Una discusión planteada originalmente en https://github.com/mgaitan/preciosa/issues/18#issuecomment-35226119

El problema no se circunscribe a COTO Digital y es el siguiente:

• Tenemos una base de datos de productos con UPC conocido. La utilidad del UPC es poder asociar precios de distintas sucursales univocamente al producto que corresponda.
• Hay (y habrá) fuentes de datos (ejemplo #18) que no explicitan el UPC. ¿A qué producto asociamos el precio?

Necesitamos un algoritmo que pueda encontrar este el UPC de destino más probable para una descripción de texto dada (posiblemente reforzada por otros datos, como texto de la marca, o demás).

Dependiendo de la certeza en esta busqueda se puede dar por conocido el producto y asociar a traves de un modelo auxiliar, la sucursal/cadena, algun identificador del item de entrada y este UPC de destino (por ejemplo codigo PLU de coto, o la URL a la pagina de detalle del producto online de la fuente de datos)

Si del algoritmo resultaran multiples UPC probables, se podria derivar a una tarea para voluntarios (pero acotada a los que "creemos que pueden ser"

[mgaitan]

Este es el comantario de Juan Cabral originalmente en el ticket #18

---

Primero no es hamming es levenshtein

(manteniendonos en algo facil) Esto lo resolveria asi:

Supongamos que Adolfo y Schultz estan usando el programa y cargan dos productos iguales pero de manera distinto por ejemplo:

Schultz carga: "Chukrut den von fürer niéin" Adolfo carga: "Chucrut den von furer nein"

Como notaras Adolfo se olvido del acento en la letra... primer paso normalizar palabras y chucut esta escrito distinto

Schultz quedaria: "chukrut den von furer niein" Adolfo : "chucrut den von furer nein"

La diferencia que queda ahora es la C y la K en chukrut... si pasamos por el algoritmo de distancia de demerau-levenshtein que esta aca

http://mwh.geek.nz/2009/04/26/python-damerau-levenshtein-distance

print dameraulevenshtein("chukrut den von furer niein", "chucrut den von furer nein") => 2

Podes decir que 2 es suficiente mente cercano para ser lo mismo (podes comparar precios para ver si no se va de mambo y puede ser otra cosa)

Lo que no estas seguro mandalo a una interfaz de mergeo manual de products

[mgaitan]

Postgres tiene una implementacion de levenshtein.

sino estudiar http://django-haystack.readthedocs.org con alguno de los motores si tiene algo de esto

[jazzido]

Tuve un problema parecido cuando estaba haciendo dondevoto

La métrica de similaridad de strings que mejor me funcionó es trigram matching —Postgres lo implementa en el módulo pg_trgm—. Acá hay un query de ejemplo

Un posible enfoque es definir empíricamente un umbral de similaridad t, y asumir que todos los pares de strings con similaridad > t, nombran a la misma entidad. Claramente, hay que ser bastante conservador con ese valor.

[matiasb]

Yendo para el lado de búsqueda de texto, quizás se podría probar con Whoosh (http://whoosh.readthedocs.org), que es uno de los motores que se pueden usar con Haystack (haystack suena como demasiada infraestructura para el problema a resolver).

Whoosh permitiría indexar las descripciones y hacer búsquedas sobre ellas, usando algún sistema de scoring: http://whoosh.readthedocs.org/en/latest/searching.html#scoring-and-sorting.

Hacer una prueba rápida no debería ser complicado (es pure-python, bastante customizable, no se requiere otro sistema corriendo en algún lado, etc). Además, si eventualmente se usara la info indexada para el público (búsquedas, productos similares a este, etc), se podría ir agregando la funcionalidad encima (o eventualmente, decidirse por haystack que resuelve mucho y para cualquier otro motor).

[mgaitan]

2014-02-24 18:40 GMT-03:00 Matias Bordese notifications@github.com:

Hacer una prueba rápida no debería ser complicado (es pure-python, bastante customizable, no se requiere otro sistema corriendo en algún lado, etc).

Manu, podés hacer una prueba de concepto? si necesitas te busco raw data que deberiamos intentar matchear, en CSV o algo que puedas probar sin montar todo el django.

mgaitan.github.io textosyprextextos.com.ar

[jazzido]

Manu, podés hacer una prueba de concepto? si necesitas te busco raw data que deberiamos intentar matchear, en CSV o algo que puedas probar sin montar todo el django.

Pasame un dump de la tabla en la que haya que buscar matches; haré lo posible.

No prometo nada, estoy medio atareado :(

Manuel Aristarán http://jazzido.com

[jazzido]

Acá ya me pongo pretencioso: si tenés una "ground truth" (es decir, strings que vos sepas que nombran a un determinado producto), genial. Es útil para testear el algoritmo.

Manuel Aristarán http://jazzido.com

2014-02-24 19:37 GMT-03:00 Manuel Aristarán jazzido@jazzido.com:

Manu, podés hacer una prueba de concepto? si necesitas te busco raw data

que deberiamos intentar matchear, en CSV o algo que puedas probar sin montar todo el django.

Pasame un dump de la tabla en la que haya que buscar matches; haré lo posible.

No prometo nada, estoy medio atareado :(

Manuel Aristarán http://jazzido.com

[jazzido]

Más preguntas: supongamos que entra un producto p y queremos encontrar un match en la base de productos existentes.

• La categoría de p la sabemos?
• Y el fabricante?

Pregunto esto porque puede ser útil para restringir el espacio de búsqueda antes de hacer similaridad de strings.

[jazzido]

Esto es bastante sofisticado pero tiene ideas interesantes: Toward an adaptive String Similarity Measure for Matching Product Offers

[mgaitan]

2014-02-24 20:00 GMT-03:00 Manuel Aristarán notifications@github.com:

La categoría de p la sabemos? Y el fabricante?

La categoría sí y la marca/fabricante es menester del ticket #82, pero se supone que también la sabremos.

mgaitan.github.io textosyprextextos.com.ar

[jazzido]

OK. Pasame data cuando puedas.

[adsodemelk]

Yo estuve jugando con este modulo y hace lo que promete:

https://pypi.python.org/pypi/Distance

[mgaitan]

@jazzido me colgué con la data

Este fixture es basicamente un dump de los productos que conocemos hasta el momento, que tiene codigo https://github.com/mgaitan/preciosa/raw/develop/fixtures/productos.json

acá tenemos otra gran lista de productos (scrapeados de Coto) que no le conocemos el codigo. https://drive.google.com/file/d/0ByLwJpAElIr0MzdQanRoZV90R0U/edit?usp=sharing

sirve eso?

[ajlopez]

No es exactamente lo que piden para este issue, pero tengo un search en JavaScript, y un servicio web en Node

https://github.com/ajlopez/Annalisa/tree/master/samples/preciosa

Es facil de probar.

Le falta el tema de la palabra aproximada. Pero es piece of cake. Solo que ahora ya me voy a luchar por mi pitanza

Nos leemos!

@ajlopez

[ajlopez]

Deploye en heroku

Pueden probar http://preciosaannalisa.herokuapp.com/api/search?q=arcor%20jugo

tambien tienen analizar un texto y obtener informacion: http://preciosaannalisa.herokuapp.com/api/analyze?q=fanta%20pomelo%201%20lt

@ajlopez

[ajlopez]

Deploye en heroki

Pueden probar http://preciosaannalisa.herokuapp.com/api/search?q=arcor%20jugo

Pero tambien busca aproximada http://preciosaannalisa.herokuapp.com/api/search?q=arcar%20jugo

SI ES QUE NO ENCUENTRA arcar como palabra conocida

En el finde, agrego alguna variante al search de palabra aproximada

@ajlopez

[ajlopez]

Si les sirve de benchmark, escribi unos scripts python de comando de linea, para usar el search de preciosa annalisa de Heroku

https://github.com/ajlopez/PythonSamples/tree/master/Preciosa

[jazzido]

Tarde pero seguro: un par de scripts quick and dirty para probar el trigram matching de PostgreSQL:

https://github.com/jazzido/producto-similaridades

@mgaitan: La base se carga con el productos.json que mandaste. Los strings de ejemplo que están en el README salen de coto.csv.

Cualquier cosa, avisen.

[jazzido]

Se me ocurre que esto puede ser una herramienta de apoyo para el chequeo manual de los voluntarios. Si queremos hacer algo no supervisado, hay que laburar bocha más :)

[mgaitan]

genial Manuel, muchas gracias! lo estaremos probando en breve.

2014-03-05 18:38 GMT-03:00 Manuel Aristarán notifications@github.com:

Se me ocurre que esto puede ser una herramienta de apoyo para el chequeo manual de los voluntarios. Si queremos hacer algo no supervisado, hay que laburar bocha más :)

— Reply to this email directly or view it on GitHubhttps://github.com/mgaitan/preciosa/issues/80#issuecomment-36797111 .

mgaitan.github.io textosyprextextos.com.ar

[mgaitan]

@jazzido eso que hiciste, que yo "sospechaba" que se podía pero desconocía cómo, me dió la punta para buscar _"django + pgtrgm" y, por supuesto, encontré algo :smiley_cat:

salió forkcito con algunos pull request al proyecto original, acá

https://github.com/mgaitan/djorm-ext-pgtrgm

un ejemplo de cómo está funcionando en este PR

¡muchas gracias por mostrarnos la luz!

[mgaitan]

Respecto al ticket #80 en sí, por supuesto esto ayuda un montón, pero creo que hay que complementarlo con Annalisa de #82 by @ajlopez .

Es decir, además del puntaje que nos da por similaridad de descipción, considerar si Annalisa detectó la misma marca, el mismo contenido, y darle "puntaje extra". Con qué ponderación es una tarea de ajuste fino, pero sería bueno hacer algunas pruebas.

¿cómo lo ven?

[jazzido]

Buenísimo que sirvió de algo!

[jazzido]

Es decir, además del puntaje que nos da por similaridad de descipción, considerar si Annalisa detectó la misma marca, el mismo contenido, y darle "puntaje extra". Con qué ponderación es una tarea de ajuste fino, pero sería bueno hacer algunas pruebas.

Lo mejor es armar (manualmente?) una ground truth. Es decir, un mapeo que sabés cierto. Con ese dataset, podés laburar tranquilo en armar una buena heurística de matcheo sin tener regresiones.