Averigua si el nombre de una empresa es muy similar a otro: Python
normalization matching (8)
Estoy trabajando con una gran base de datos de empresas.
Me gustaría poder comparar la similitud de dos nombres comerciales para ver si es posible que estén duplicados.
A continuación, se incluye una lista de los nombres de empresas que deberían probar que tienen una alta probabilidad de ser duplicados. ¿Cuál es una buena manera de hacerlo?
George Washington Middle Schl George Washington School Santa Fe East Inc Santa Fe East Chop''t Creative Salad Co Chop''t Creative Salad Company Manny and Olga''s Pizza Manny''s & Olga''s Pizza Ray''s Hell Burger Too Ray''s Hell Burgers El Sol El Sol de America Olney Theatre Center for the Arts Olney Theatre 21 M Lounge 21M Lounge Holiday Inn Hotel Washington Holiday Inn Washington-Georgetown Residence Inn Washington,DC/Dupont Circle Residence Inn Marriott Dupont Circle Jimmy John''s Gourmet Sandwiches Jimmy John''s Omni Shoreham Hotel at Washington D.C. Omni Shoreham Hotel
Busqué "distancia de edición de Python" y esta biblioteca fue el primer resultado: http://www.mindrot.org/projects/py-editdist/
Otra biblioteca de Python que hace el mismo trabajo está aquí: http://pypi.python.org/pypi/python-Levenshtein/
Una distancia de edición representa la cantidad de trabajo que necesita realizar para convertir una cadena en otra siguiendo solo operaciones de edición simples, generalmente basadas en caracteres. Cada operación (subestación, eliminación, inserción, a veces transposición) tiene un costo asociado y la distancia de edición mínima entre dos cadenas es una medida de cuán diferentes son las dos.
En su caso particular, es posible que desee ordenar las cadenas de modo que encuentre la distancia para ir de la más larga a la más corta y penalice menos las eliminaciones de caracteres (porque veo que en muchos casos una de las cadenas es casi una subcadena de la otra) . Así que la eliminación no debería ser penalizada mucho.
También puede hacer uso de este código de ejemplo: http://norvig.com/spell-correct.html
Considere usar la biblioteca Diff-Match-Patch . Le interesaría el proceso Diff: aplicar una diferencia en su texto puede darle una buena idea de las diferencias, junto con una representación programática de las mismas.
Hay una gran biblioteca para buscar cadenas similares / difusas para python: fuzzywuzzy . Es una bonita biblioteca de envoltorios sobre la medición de distancia Levenshtein mencionada. Aquí cómo se podrían analizar sus nombres:
#!/usr/bin/env python
from fuzzywuzzy import fuzz
names = [
("George Washington Middle Schl",
"George Washington School"),
("Santa Fe East Inc",
"Santa Fe East"),
("Chop''t Creative Salad Co",
"Chop''t Creative Salad Company"),
("Manny and Olga''s Pizza",
"Manny''s & Olga''s Pizza"),
("Ray''s Hell Burger Too",
"Ray''s Hell Burgers"),
("El Sol",
"El Sol de America"),
("Olney Theatre Center for the Arts",
"Olney Theatre"),
("21 M Lounge",
"21M Lounge"),
("Holiday Inn Hotel Washington",
"Holiday Inn Washington-Georgetown"),
("Residence Inn Washington,DC/Dupont Circle",
"Residence Inn Marriott Dupont Circle"),
("Jimmy John''s Gourmet Sandwiches",
"Jimmy John''s"),
("Omni Shoreham Hotel at Washington D.C.",
"Omni Shoreham Hotel"),
]
if __name__ == ''__main__'':
for pair in names:
print "{:>3} :: {}".format(fuzz.partial_ratio(*pair), pair)
>>> 79 :: (''George Washington Middle Schl'', ''George Washington School'')
>>> 100 :: (''Santa Fe East Inc'', ''Santa Fe East'')
>>> 100 :: ("Chop''t Creative Salad Co", "Chop''t Creative Salad Company")
>>> 86 :: ("Manny and Olga''s Pizza", "Manny''s & Olga''s Pizza")
>>> 94 :: ("Ray''s Hell Burger Too", "Ray''s Hell Burgers")
>>> 100 :: (''El Sol'', ''El Sol de America'')
>>> 100 :: (''Olney Theatre Center for the Arts'', ''Olney Theatre'')
>>> 90 :: (''21 M Lounge'', ''21M Lounge'')
>>> 79 :: (''Holiday Inn Hotel Washington'', ''Holiday Inn Washington-Georgetown'')
>>> 69 :: (''Residence Inn Washington,DC/Dupont Circle'', ''Residence Inn Marriott Dupont Circle'')
>>> 100 :: ("Jimmy John''s Gourmet Sandwiches", "Jimmy John''s")
>>> 100 :: (''Omni Shoreham Hotel at Washington D.C.'', ''Omni Shoreham Hotel'')
Otra forma de resolver este tipo de problemas podría ser Elasticsearch , que también admite búsquedas difusas.
Lo que puede hacer es separar las palabras con espacios en blanco, comas, etc., y luego cuenta el número de palabras que tiene en común con otro nombre y agrega un número de palabras de tres en tres antes de que se considere "similar".
La otra forma es hacer lo mismo, pero toma las palabras y empíjalas para cada personaje. Luego, para cada palabra que necesita comparar si las letras se encuentran en el mismo orden (de ambos lados) para una cantidad x de caracteres (o porcentaje), entonces puede decir que la palabra también es similar.
Ej: tienes plaza y plaza.
Luego verifica por caracteres y encuentra que los cuadrados están todos en cuadrado y en el mismo orden, entonces es una palabra similar.
Los algoritmos que se basan en la distancia Levenshtein son buenos (no son perfectos) pero su principal desventaja es que son muy lentos para cada comparación y en cuanto al hecho de que tendría que comparar todas las combinaciones posibles.
Otra forma de resolver el problema sería usar incrustación o bolsa de palabras para transformar el nombre de cada compañía (después de un poco de limpieza y preposesión) en un vector de números. Y después de eso, aplica un método de ML supervisado o no supervisado, dependiendo de lo que esté disponible.
Me gustaría añadir algunos ejemplos a la excelente respuesta aceptada. Probado en Python 2.7.
Análisis
Vamos a usar este nombre extraño como ejemplo.
name = "THE | big,- Pharma: LLC" # example of a company name
Podemos comenzar por eliminar los términos legales de control (aquí LLC). Para hacer eso, hay una impresionante biblioteca de Python en cleanco , que hace exactamente eso:
from cleanco import cleanco
name = cleanco(name).clean_name() # ''THE | big,- Pharma''
Eliminar toda la puntuación:
name = name.translate(None, string.punctuation) # ''THE big Pharma''
(Para las cadenas Unicode, el siguiente código funciona en su lugar ( source , regex ):
import regex
name = regex.sub(ur"[[:punct:]]+", "", name) # u''THE big Pharma''
Dividir el nombre en tokens usando NLTK :
import nltk
tokens = nltk.word_tokenize(name) # [''THE'', ''big'', ''Pharma'']
Minúsculas todas las fichas:
tokens = [t.lower() for t in tokens] # [''the'', ''big'', ''pharma'']
Eliminar las palabras de parada. Tenga en cuenta que podría causar problemas con compañías como On Mars que se asociarán incorrectamente con Mars , porque On es una palabra clave.
from nltk.corpus import stopwords
tokens = [t for t in tokens if t not in stopwords.words(''english'')] # [''big'', ''pharma'']
No cubro los caracteres acentuados y especiales aquí (las mejoras son bienvenidas).
Pareo
Ahora, cuando hemos asignado todos los nombres de empresas a tokens, queremos encontrar los pares coincidentes. Podría decirse que la similitud de Jaccard (o Jaro-Winkler) es mejor que Levenstein para esta tarea, pero aún no es lo suficientemente buena. La razón es que no tiene en cuenta la importancia de las palabras en el nombre (como lo hace TF-IDF). Así que las palabras comunes como "Compañía" influyen en la puntuación tanto como las palabras que podrían identificar de forma única el nombre de la empresa.
Para mejorar eso, puedes usar un truco de similitud de nombres que se sugiere en esta impresionante serie de publicaciones (no en la mía). Aquí hay un ejemplo de código de él:
# token2frequency is just a word counter of all words in all names
# in the dataset
def sequence_uniqueness(seq, token2frequency):
return sum(1/token2frequency(t)**0.5 for t in seq)
def name_similarity(a, b, token2frequency):
a_tokens = set(a.split())
b_tokens = set(b.split())
a_uniq = sequence_uniqueness(a_tokens)
b_uniq = sequence_uniqueness(b_tokens)
return sequence_uniqueness(a.intersection(b))/(a_uniq * b_uniq) ** 0.5
Usando eso, puede hacer coincidir los nombres con una similitud que exceda cierto umbral. Como un enfoque más complejo, también puede tomar varios puntajes (por ejemplo, este puntaje de unicidad, Jaccard y Jaro-Winkler) y entrenar un modelo de clasificación binaria usando algunos datos etiquetados, lo que, dado un número de puntajes, dará salida si el par candidato es un partido o no Más sobre esto se puede encontrar en la misma publicación del blog.
Podría usar la distancia de Levenshtein, que podría usarse para medir la diferencia entre dos secuencias (básicamente una distancia de edición).
Levenshtein Distancia en Python
def levenshtein_distance(a,b):
n, m = len(a), len(b)
if n > m:
# Make sure n <= m, to use O(min(n,m)) space
a,b = b,a
n,m = m,n
current = range(n+1)
for i in range(1,m+1):
previous, current = current, [i]+[0]*n
for j in range(1,n+1):
add, delete = previous[j]+1, current[j-1]+1
change = previous[j-1]
if a[j-1] != b[i-1]:
change = change + 1
current[j] = min(add, delete, change)
return current[n]
if __name__=="__main__":
from sys import argv
print levenshtein_distance(argv[1],argv[2])
Recientemente hice una tarea similar, aunque estaba haciendo coincidir los datos nuevos con los nombres existentes en una base de datos, en lugar de buscar duplicados dentro de un conjunto. La coincidencia de nombres es en realidad una tarea bien estudiada, con una serie de factores que van más allá de lo que consideraría para unir cadenas genéricas.
Primero, recomiendo echar un vistazo a un artículo, Cómo jugar el "Juego de nombres": recuperación de patentes que compara diferentes heurísticas de Raffo y Lhuillery. La versión publicada está here , y un PDF está disponible gratuitamente here . Los autores proporcionan un buen resumen, comparando una serie de estrategias de coincidencia diferentes. Consideran tres etapas, que llaman análisis, comparación y filtrado.
El análisis consiste en aplicar varias técnicas de limpieza. Algunos ejemplos:
- Estandarización de letras (por ejemplo, en minúsculas)
- Estandarización de la puntuación (por ejemplo, las comas deben ir seguidas de espacios)
- Estandarizar espacios en blanco (por ejemplo, convertir todas las ejecuciones de espacios en blanco en espacios individuales)
- Estandarización de caracteres acentuados y especiales (por ejemplo, conversión de letras acentuadas a equivalentes ASCII)
- Estandarizar los términos de control legal (por ejemplo, convertir "Co." en "Compañía")
En mi caso, doblé todas las letras en minúsculas, reemplacé toda puntuación con espacios en blanco, reemplazé los caracteres acentuados por homólogos sin acento, eliminé todos los demás caracteres especiales y eliminé los términos de control legal desde el principio y el final de los nombres que siguen a una lista.
La coincidencia es la comparación de los nombres analizados. Esto podría ser una simple coincidencia de cadenas, la distancia de edición, Soundex o Metaphone, la comparación de los conjuntos de palabras que forman los nombres, o la comparación de conjuntos de letras o n -grams (secuencias de letras de longitud n ). El enfoque de n -gram es bastante bueno para los nombres, ya que ignora el orden de las palabras y ayuda mucho con cosas como "departamento de ejemplos" vs. "departamento de ejemplos". De hecho, es muy efectivo comparar bigramas (2 gramos, pares de caracteres) usando algo simple como el índice Jaccard . A diferencia de otras sugerencias, la distancia Levenshtein es uno de los enfoques más pobres cuando se trata de la coincidencia de nombres.
En mi caso, hice el emparejamiento en dos pasos, primero comparando los nombres analizados para la igualdad y luego utilizando el índice Jaccard para los conjuntos de bigramas en el resto. En lugar de calcular realmente todos los valores del índice Jaccard para todos los pares de nombres, primero puse un límite en el valor máximo posible para el índice Jaccard para dos conjuntos de tamaño dado, y solo calculé el índice Jaccard si ese límite superior era lo suficientemente alto como para potencialmente ser útil La mayoría de los pares de nombres aún eran lo suficientemente diferentes como para que no fueran coincidencias, pero redujo drásticamente el número de comparaciones hechas.
El filtrado es el uso de datos auxiliares para rechazar falsos positivos de las etapas de análisis y coincidencia. Una versión simple sería ver si los nombres coincidentes corresponden a negocios en diferentes ciudades y, por lo tanto, a diferentes negocios. Ese ejemplo podría aplicarse antes del emparejamiento, como un tipo de filtrado previo. Posteriormente se podrían aplicar controles más complicados o que requieren más tiempo.
No hice mucho filtrado. Revisé los países en busca de las empresas para ver si eran iguales, y eso fue todo. Realmente no había muchas posibilidades en los datos, algunas restricciones de tiempo descartaron cualquier búsqueda extensa de datos adicionales para aumentar el filtrado, y de todos modos se planificó una verificación manual.