Una guía sobre cómo construir un algoritmo de búsqueda difusa con FuzzyWuzzy y HMNI
Cheng
5 de marzo·6 min de lectura
En este artículo, lo guiaré a través de mis pensamientos sobre cómo construir un algoritmo de búsqueda difusa. Un caso de uso muy práctico de este algoritmo es que podemos usarlo para encontrar nombres alternativos para una marca que diga ‘Amazon’ y queremos que devuelva cadenas como ‘AMZ’, ‘AMZN’ o ‘AMZN MKTP’.
El artículo sigue un esquema como el siguiente:
- Búsqueda difusa con FuzzyWuzzy
- Búsqueda difusa con el HMNI
- Búsqueda difusa con algoritmo integrado
- Devuelve una tabla de nombres alternativos
Buscar con FuzzyWuzzy
seatgeek / fuzzywuzzy
Encadenamiento de cadenas difuso como un jefe. Utiliza la distancia de Levenshtein para calcular las diferencias entre secuencias en un …
github.com
FuzzyWuzzy es una gran biblioteca de Python que se puede usar para completar un trabajo de búsqueda difusa. Básicamente, utiliza la distancia de Levenshtein para calcular la diferencia / distancia entre secuencias.
Según a Wikipedia, la distancia de Levenshtein es una métrica para evaluar el número mínimo de ediciones de un solo carácter (inserciones, eliminaciones o sustituciones) necesarias para cambiar una palabra por otra. Esto significa que la métrica de evaluación dentro de FuzzyWuzzy puede ser muy buena para realizar una búsqueda aproximada de las palabras mal escritas y capturar la subsecuencia común más larga entre entradas.
Pero para algunos casos, por ejemplo, la abreviatura de nombres de marca, sabiendo solo la diferencia a nivel de personaje, probablemente no sea suficiente. También tendría sentido conocer la diferencia fonética y semántica antes de devolver las coincidencias de nombres más similares.
Por lo tanto, me gustaría presentar otra biblioteca llamada HMNI que puede ayudarnos a verificar la similitud fonética entre las entradas, pero primero permítanme construir un conjunto de datos de muestra para una prueba más adecuada.
Empezando por la librería FuzzyWuzzy, para instalarla podríamos ejecutar los siguientes comandos:
# Using PIP via PyPI
pip install fuzzywuzzy# Or the following to install python-Levenshtein too
pip install fuzzywuzzy[speedup]
Luego, continuaremos creando un conjunto de datos de muestra para nuestra prueba.
# Sample Dataset
df = pd.DataFrame(index =['AMAZON', 'Netflix', 'PayPal', 'Apple', 'Spotify', 'Apple', 'Facebook', 'Google', 'Starbucks'],
columns = ['AMZ', 'PP', 'FACEBK', 'SPTF*', 'APPL', 'STARBK', 'GG', 'Starbucks TORONTO', 'NFLIX'])# Print
df
Tenemos los índices de fila configurados como los nombres de marca completos y los nombres de columna configurados como abreviaturas potenciales de estas marcas.
Ahora, podemos definir una función que toma dos cadenas como entrada y devuelve una puntuación de similitud como salida. En FuzzyWuzzy, podemos usar la función fuzz.ratio () para calcular la puntuación de similitud entre dos entradas.
# Customized similarity function with FuzzyWuzzy
def similarity_fuzzy(word1, word2):
score = fuzz.ratio(word1, word2)
d = score/100
return d
Ahora, solo necesitamos implementar el similarity_fuzzy funcionan en cada par del índice de la fila y el nombre de la columna para reemplazar estos valores NaN con puntuaciones de similitud.
from tqdm import tqdmfor i in tqdm(range(8)): # range in number of rows
for j in range(9): # range in number of columns
df.loc[df.index[i], df.columns[j]] = similarity_fuzzy(str(df.index[i]), str(df.columns[j]))
df
Como podemos ver, el FuzzyWuzzy no funciona muy bien para encontrar las abreviaturas correctas para los nombres de marca de entrada. La razón principal por la que creo que es porque las abreviaturas han perdido muchos caracteres, por lo que la métrica de usar la distancia de Levenshtein no es la solución óptima para este caso.
¡Y este es el lugar donde creo que una nueva perspectiva de la similitud fonética informática debería ser de gran ayuda!
Busca con el HMNI
Christopher-Thornton / hmni
Coincidencia aproximada de nombres con aprendizaje automático. Realice tareas comunes de coincidencia de nombres difusos, incluida la puntuación de similitud …
github.com
Generalmente, HMNI es una biblioteca que sigue el proceso cognitivo de aplicar lógica blanda para aproximar la ortografía y fonético características (sonoras).
Un gran artículo para explorar:
Coincidencia aproximada de nombres con aprendizaje automático
Apilamiento de algoritmos fonéticos, métricas de cadenas e incrustación de caracteres para la coincidencia semántica de nombres
haciadatascience.com
Para probar el rendimiento de coincidencia de nombres difusos con el HMNI, podemos seguir los mismos pasos que para el FuzzyWuzzy.
Para instalar el HMNI:
# Using PIP via PyPI
pip install hmni
Para inicializar un objeto Matcher:
import hmni
matcher = hmni.Matcher(model='latin')
Para personalizar nuestra función de similitud:
def similarity_hmni(word1, word2):
d = matcher.similarity(word1, word2)
return d
Entonces, podemos probar el similitud_hmni función en el mismo conjunto de datos de muestra para comparar el rendimiento.
La diferencia es muy obvia entre FuzzyWuzzy y HMNI. HMNI parece ser mejor para encontrar las abreviaturas de las entradas de la marca en función de las características fonéticas potenciales.
Pero todavía no significa que no haya ninguna desventaja de usar HMNI. Por ejemplo, al observar ‘PayPal’ y ‘Apple’, encontramos que HMNI tiende a ser malo para separar estas dos marcas, ya que las puntuaciones de similitud son 0,71 y 0,41 y 0,66 y 0,94 respectivamente. Esto puede causar cierta confusión si agregamos más entradas al conjunto de datos. Además, para la coincidencia exacta entre ‘Starbucks’ y ‘Starbucks Toronto’, el HMNI debería tener más confianza en su predicción, pero ahora solo devuelve un valor de 0,5.
Buscar con un algoritmo integrado
Esto probablemente significa que deberíamos considerar integrar ambas dimensiones, la similitud fonética y la distancia de Levenshtein para lograr un equilibrio óptimo.
Mi solución a esto es simple. Simplemente agregue dos funciones juntas en una nueva función y ajustaremos los pesos para determinar los puntajes de salida finales.
def similarity_calculator(word1, word2):
score_1 = fuzz.ratio(word1, word2) # score from fuzzywuzzy
score_2 = matcher.similarity(word1, word2) # score from hmni
score_1 = score_1/100
score = 0.2*score_1 + 0.8*score_2 # customize your own weights
return score
Al integrar estas dos funciones juntas, parece que alcanzamos un equilibrio en el que podemos establecer un 60% como umbral para separar coincidencias y no coincidencias. A excepción de Starbucks, probablemente deberíamos buscar estas coincidencias de grandes marcas directamente utilizando el .encontrar() función en python.
Último paso
Ahora, el trabajo restante es crear una tabla de coincidencias de nombres alternativos principales para las entradas de la marca. Para el conjunto de datos de muestra, elijo devolver solo la coincidencia superior con la puntuación de similitud más alta. El código tiene el siguiente aspecto:
# Return a new column 'Max' that contains the alternative names for each brand input
df['Max'] = df.astype(float).idxmax(axis=1)# Create a new dataframe 'result' to display only the input & output columns
result = pd.DataFrame(list(df.index), columns=['Input'])
result['Alternative Names'] = list(df.Max)
result
Su resultado final se verá como un conjunto de datos anterior.
Gracias por tu lectura Y espero que este artículo pueda ser útil para cualquiera que esté buscando una guía sobre cómo crear un algoritmo de búsqueda difusa con aprendizaje automático.
Creo que este artículo podría ser un gran comienzo para que desarrolle su propio algoritmo de búsqueda difusa 🙂
¡Gracias de nuevo!
Nos vemos en el próximo artículo ~